[Cryptography] BLAKE2: "Harder, Better, Faster, Stronger" Than MD5

[Jerry Leichter]

On Mar 23, 2014, at 2:16 AM, dj at deadhat.com wrote:
> Count me as one of the engineers who have to pick a hash function to
> implement. I have that problem right now.
> 
> #1. I do not care about speed because I implement my stuff in hardware and regardless of the efficiency of the algorithm I can throw the necessary number of gates at the problem to make it run at whatever speed is required.
> 
> #2. I do care about security. Shipping insecure crypto is not an option.
> 
> #3. I do care about being able to publicly and honestly justify the
> reasons for whatever selection is made.
> 
> #3 is the killer. The justification of a couple of years ago "We use NIST
> SP800-xx because that's the standard" doesn't really fly today because
> NIST lacks the trustworthy angle. But there is no obvious consensus body
> that we can point to for sound algorithm selection. If I select Blake2,
> put it in a substantial fraction of the CPUs out there and it's
> subsequently broken, that's my fault. If I select SHA3 for the same chips
> and it's subsequently broken, that's NIST's fault but still by problem.
> ANSI X9 isn't much help, it's written by the same people that write NIST
> SPs....
I know it's going to sound like a sell-out, but ... a combination of the things everyone one of us repeats argues that you go with NIST's choice.

1.  There is no such thing as absolute security.  We know how to break many algorithms, and we have some algorithms that cannot be broken using any of the techniques we know.  But that's all we can say.  We simply do not have any kind of theory that can tell us that an algorithm is secure against attacks we haven't considered yet.  See below.

2.  Security is about mitigating risk.  It's not an absolute.

Given 1, there is not *absolute* way of choosing a cryptographic algorithm; it's always about make the best-supported guess available.  Whatever you think about NIST and any possible connection it has with NSA, the NIST *contests* have drawn some of the best minds in public cryptography, and have been held out in the open with visible participation from many other of the best minds.  DJB is very good, but he's not uniquely so.

Given 2, you have to ask the question:  What is my exposure if I use algorithm X, and it turns out to fail?  (This is for any particular value of "my".)  The fact is, it's much easier to obtain insurance (actual monetary insurance coverage, or any moral equivalent thereof - someone to cover your ass and make you hole if what you chose goes wrong) for something endorsed by NIST than for something with no official endorsement.

There's theoretical science and there's practical engineering.  Practical engineering, unlike theoretical science, is about money and practical usefulness (among other things).  These argue for going with NIST.

Thinking about one element of this more quantitatively:  What's the longest time any algorithm has remained secure against all significant published attacks?

There are no really strong analytic attacks against DES to this day, though its key is way too small by today's standards (which counts as an attack).  It's hard to exactly pin down how long DES could reasonably be considered secure, but if we go from initial publication in 1977 through the EFF DES cracker in 1998, we get about a 20 year lifetime.

AES is still going strong at 13 years from initial official publication in 2001.  (If you start the clock at entry in the competition, you get a little extra time, but it makes it hard to compare algorithms uniformly.) 

Triple-DES was published in 1998 and still appears strong at 16 years.  (Curiously, the only specific weakness Triple-DES is known to cure is brute force attack - but Rogoway showed years ago the DES-X - DES with simple XOR pre- and post-whitening - is about as strong against brute force attack as Triple-DES.  But no one seems to use it, while complaining that Triple-DES is too slow!)

There are plenty of other potential contenders (Blowfish, RC5), though the great grand-daddy appears to be IDEA:  Initial patent proposal in 1990, full patent proposal in 1991, no known attacks to date.  That puts it at 24 years or so.

It's impossible to compare the level of cryptanalytic attack brought to bear against widely used standards and against algorithms no one is using; we'll just assume the academic glory of breaking IDEA or DES would match that of breaking AES (though the monetary rewards would be much lower).

We so far have *absolutely no evidence* of a block cipher surviving more than 25 years of public cryptanalytic advances.  A prudent guess would place a lifetime in that range.

Most widely use stream ciphers have been ad hoc and have proved to be quite weak.  RC4 is the outlier.  It was designed in 1987 but the design was secret until 1994; so it's not entirely clear when to start the clock running.  One can also debate whether to stop the clock at the recent (last year or so) demonstration of practical attacks, or the 2000 work by Fluhrer and McGrew that found the weaknesses that were eventually turned into attacks.  Make your own estimate from this about a prudent guess for a lifetime.

MD5 was published in 1992 and was considered broken by 2004 - 12 years.  SHA-1 was published in 1995 but by 2005 - 10 years later - was considered to be weak.  An almost-practical attack was published in 2011.  SHA-2 was published in 2001 but was under suspicion by 2012 or so - 13 years.  Based on this history, it would be prudent to assume a maximum practical lifetime for a cryptographic hash function to be around 15 years.

In contrast, RSA was first published in 1977 and remains free of known general attacks 37 years later - though we've had to increase key sizes faster than was predicted a couple of times.  ECC was first proposed in 1985.  It took a while for the details to be worked out - widespread use didn't begin until maybe 2004.  It's difficult to compare ECC directly to RSA since unlike RSA, it's a family of systems, one per curve - and some of the initial curves were weak.

These numbers are actually quite shockingly low when you think about them.  There is certainly a degree of "infant mortality" in new cryptographic algorithms - you certainly want them to "bake in" for, say, 3 years of public visibility before you rely on them.  That leaves a practical lifetime for block ciphers of about 22 years, for hash functions of about 12 years.  That's long relative to laptop or server CPU lifetimes, but quite short relative to protocol lifetimes - and very uncomfortable relative to embedded CPU lifetimes.
                                                        -- Jerry