<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Oct 4, 2013 at 10:23 AM, John Kelsey <span dir="ltr"><<a href="mailto:crypto.jmk@gmail.com" target="_blank">crypto.jmk@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Oct 4, 2013, at 10:10 AM, Phillip Hallam-Baker <<a href="mailto:hallam@gmail.com">hallam@gmail.com</a>> wrote:<br>

...<br>
<div class="im">> 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.<br>

<br>
</div>Just a couple nitpicks:<br>
<br>
a.  Dobbertin 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 of MD5 where one of the constants had been modified in one bit position. </div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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.<br>
</blockquote><div><br></div><div>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.</div><div><br></div><div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
...<br>
<div class="im">> Proofs are good for getting tenure. They produce papers 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.  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.<br>
</blockquote><div><br></div><div>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.</div>
<div><br></div><div>The oracle model is informative but does not necessarily need to be reduced to symbolic logic to make a point.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #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).  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.<br>
</blockquote><div><br></div><div>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. </div>
<div><br></div><div>But oddly enough I am currently working on a paper that presents a formalized approach. </div></div><br clear="all"><div><br></div>-- <br>Website: <a href="http://hallambaker.com/">http://hallambaker.com/</a><br>

</div></div>