[Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?

[Phillip Hallam-Baker]

On Fri, Oct 4, 2013 at 10:23 AM, John Kelsey <crypto.jmk at gmail.com> wrote:

> On Oct 4, 2013, at 10:10 AM, Phillip Hallam-Baker <hallam at 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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131004/8269df56/attachment.html>