[147510] in cryptography@c2.net mail archive
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was:
daemon@ATHENA.MIT.EDU (Phillip Hallam-Baker)
Sat Oct 5 10:42:38 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <DF4767A2-C14A-48E4-9676-E6B4ED5CE886@gmail.com>
Date: Fri, 4 Oct 2013 13:06:52 -0400
From: Phillip Hallam-Baker <hallam@gmail.com>
To: John Kelsey <crypto.jmk@gmail.com>
Cc: "cryptography@metzdowd.com" <cryptography@metzdowd.com>,
ianG <iang@iang.org>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============2344609087442212912==
Content-Type: multipart/alternative; boundary=089e0149373c2cf57704e7ed54ef
--089e0149373c2cf57704e7ed54ef
Content-Type: text/plain; charset=ISO-8859-1
On Fri, Oct 4, 2013 at 10:23 AM, John Kelsey <crypto.jmk@gmail.com> wrote:
> On Oct 4, 2013, at 10:10 AM, Phillip Hallam-Baker <hallam@gmail.com>
> wrote:
> ...
> > Dobertin demonstrated a birthday attack on MD5 back in 1995 but it had
> no impact on the security of certificates issued using MD5 until the attack
> was dramatically improved and the second pre-image attack became feasible.
>
> Just a couple nitpicks:
>
> a. Dobbertin wasn't doing a birthday (brute force collision) attack, but
> rather a collision attack from a chosen IV.
>
Well if we are going to get picky, yes it was a collision attack but the
paper he circulated in 1995 went beyond a collision from a known IV, he had
two messages that resulted in the same output when fed a version of MD5
where one of the constants had been modified in one bit position.
> b. Preimages with MD5 still are not practical. What is practical is
> using the very efficient modern collision attacks to do a kind of herding
> attack, where you commit to one hash and later get some choice about which
> message gives that hash.
>
I find the preimage nomencalture unnecessarily confusing and have to look
up the distinction between first second and platform 9 3/4s each time I do
a paper.
> ...
> > Proofs are good for getting tenure. They produce papers that are very
> citable.
>
> There are certainly papers whose only practical importance is getting a
> smart cryptographer tenure somewhere, and many of those involve proofs.
> But there's also a lot of value in being able to look at a moderately
> complicated thing, like a hash function construction or a block cipher
> chaining mode, and show that the only way anything can go wrong with that
> construction is if some underlying cryptographic object has a flaw. Smart
> people have proposed chaining modes that could be broken even when used
> with a strong block cipher. You can hope that security proofs will keep us
> from doing that.
>
Yes, that is what I would use them for. But I note that a very large
fraction of the field has studied formal methods, including myself and few
of us find them to be quite as useful as the academics think them to be.
The oracle model is informative but does not necessarily need to be reduced
to symbolic logic to make a point.
> Now, sometimes the proofs are wrong, and almost always, they involve a lot
> of simplification of reality (like most proofs aren't going to take
> low-entropy RNG outputs into account). But they still seem pretty valuable
> to me for real-world things. Among other things, they give you a
> completely different way of looking at the security of a real-world thing,
> with different people looking over the proof and trying to attack things.
>
I think the main value of formal methods turns out to be pedagogical. When
you teach students formal methods they quickly discover that the best way
to deliver a proof is to refine out every bit of crud possible before
starting and arrive at an appropriate level of abstraction.
But oddly enough I am currently working on a paper that presents a
formalized approach.
--
Website: http://hallambaker.com/
--089e0149373c2cf57704e7ed54ef
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><br><div class=3D"gmail=
_quote">On Fri, Oct 4, 2013 at 10:23 AM, John Kelsey <span dir=3D"ltr"><=
<a href=3D"mailto:crypto.jmk@gmail.com" target=3D"_blank">crypto.jmk@gmail.=
com</a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">On Oct 4, 2013, at 10:10 AM, Phillip Hallam-=
Baker <<a href=3D"mailto:hallam@gmail.com">hallam@gmail.com</a>> wrot=
e:<br>
...<br>
<div class=3D"im">> Dobertin demonstrated a birthday attack on MD5 back =
in 1995 but it had no impact on the security of certificates issued using M=
D5 until the attack was dramatically improved and the second pre-image atta=
ck became feasible.<br>
<br>
</div>Just a couple nitpicks:<br>
<br>
a. =A0Dobbertin wasn't doing a birthday (brute force collision) attack,=
but rather a collision attack from a chosen IV.<br></blockquote><div><br><=
/div><div>Well if we are going to get picky, yes it was a collision attack =
but the paper he circulated in 1995 went beyond a collision from a known IV=
, he had two messages that resulted in the same output when fed a version o=
f MD5 where one of the constants had been modified in one bit position.=A0<=
/div>
<div><br></div><div>=A0</div><blockquote class=3D"gmail_quote" style=3D"mar=
gin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
b. =A0Preimages with MD5 still are not practical. =A0What is practical is u=
sing the very efficient modern collision attacks to do a kind of herding at=
tack, where you commit to one hash and later get some choice about which me=
ssage gives that hash.<br>
</blockquote><div><br></div><div>I find the preimage nomencalture unnecessa=
rily confusing and have to look up the distinction between first second and=
platform 9 3/4s each time I do a paper.</div><div><br></div><div>=A0</div>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
...<br>
<div class=3D"im">> Proofs are good for getting tenure. They produce pap=
ers that are very citable.<br>
<br>
</div>There are certainly papers whose only practical importance is getting=
a smart cryptographer tenure somewhere, and many of those involve proofs. =
=A0But there's also a lot of value in being able to look at a moderatel=
y complicated thing, like a hash function construction or a block cipher ch=
aining mode, and show that the only way anything can go wrong with that con=
struction is if some underlying cryptographic object has a flaw. =A0Smart p=
eople have proposed chaining modes that could be broken even when used with=
a strong block cipher. =A0You can hope that security proofs will keep us f=
rom doing that.<br>
</blockquote><div><br></div><div>Yes, that is what I would use them for. Bu=
t I note that a very large fraction of the field has studied formal methods=
, including myself and few of us find them to be quite as useful as the aca=
demics think them to be.</div>
<div><br></div><div>The oracle model is informative but does not necessaril=
y need to be reduced to symbolic logic to make a point.</div><div>=A0</div>=
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Now, sometimes the proofs are wrong, and almost always, they involve a lot =
of simplification of reality (like most proofs aren't going to take low=
-entropy RNG outputs into account). =A0But they still seem pretty valuable =
to me for real-world things. =A0Among other things, they give you a complet=
ely different way of looking at the security of a real-world thing, with di=
fferent people looking over the proof and trying to attack things.<br>
</blockquote><div><br></div><div>I think the main value of formal methods t=
urns out to be pedagogical. When you teach students formal methods they qui=
ckly discover that the best way to deliver a proof is to refine out every b=
it of crud possible before starting and arrive at an appropriate level of a=
bstraction.=A0</div>
<div><br></div><div>But oddly enough I am currently working on a paper that=
presents a formalized approach.=A0</div></div><br clear=3D"all"><div><br><=
/div>-- <br>Website: <a href=3D"http://hallambaker.com/">http://hallambaker=
.com/</a><br>
</div></div>
--089e0149373c2cf57704e7ed54ef--
--===============2344609087442212912==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============2344609087442212912==--
