In message <20050720122616.GB8395@pauli.thundrix.ch>, Tonnerre writes:
>
>On Tue, Jul 19, 2005 at 02:02:17PM -0700, Matt Thomas wrote:
>> 4) Allow various algorithms: SHA1, MD5, etc.
>
>Don't allow MD5! Also, SHA1 is a candidate that shouldn't be trusted just
>like this. Why?
>
> - people might use it
> - people might decide to use it for security relevant functions
> - people are thereby prone to the typical MD5 bit flipping attacks et al.
>
>I'm talking myself blue in the face on that: Don't use md5.
>

It depends on what the purpose of the checksum is.  I got the 
impression from Matt's original note that he was concerned about 
correctness, not security.  For that purpose, MD5 is fine.

For security purposes, it's more dubious.  But a lot depends on your 
threat model.  As I noted the last time you raised the issue of MD5, 
the problem we're dealing with today is a collision attack, not a 
preimage attack.  In other words, if you've built the kernel yourself, 
you don't have to worry about someone substituting a different kernel 
with the same MD5 hash.  (Besides, if they could substitute a kernel, 
they'd change the hash at the same time.  This isn't a digital 
signature or even an out-of-band hash we're talking about!)

The threat from the MD5 problem arises if (a) someone you trust (but 
shouldn't) builds two kernels, one good and one evil, with the same
hash.  That's easy to do.  For an example of how to do this, see
http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions .
Furthermore, this person somehow has the power to substitute the evil 
kernel for the good one, but only partially -- they don't have the 
power to change the hash in the downloaded kernel, but do have the 
power to switch the rest of the kernel.

Somehow, I'm not impressed by this as a realistic threat.

As for SHA-1, the attack is what's known in the crypto business as a 
"certificational attack".  That is, it's not a real threat (even a real 
collision threat), but the algorithm isn't as strong as it's supposed 
to be.  It's a 2^69 workfactor attack.  If we use the 1997 DES-cracking 
engine as our benchmark, we need something with 2^13 more computational 
power, at a minimum.  (I've seen no published analyses of how much work 
has to be done for each step of Wang's attack on SHA-1, and I haven't 
had the chance to do it myself.)  Deep Crack cost US$250,000; assuming 
a 2^5 improvement because of Moore's Law since then, the cost of a SHA-1 
cracker is US$640M.  That may be within the reach of a major 
government, but they probably haven't bothered -- even at the height of 
the battle over U.S. crypto export policy 10 years ago, there was less 
than no effort to sabotage hash functions or other authentication-only 
primitives.  That said, it's definitely time to start phasing out SHA-1, 
but it's hardly a crisis.  

The question, then, is what situations do pose a realistic threat 
environment, given the hash function problems.  The situation arises 
when your enemy can prepare two different versions of the file that 
have the same hash.  It could have been a problem for pkgsrc, but that 
was converted from MD5 to SHA-1 quite a while ago.  A more serious
example is email: I wouldn't not rely on signed email that used MD5 as
the hash function.  That's a change people can and should make now.

Returning to the topic at hand -- for these purposes, I see no problem
with MD5, though SHA-1 wouldn't hurt.  We should think about the
relationship of this application to verifiedexec; its hashes are
out of band, which does pose a different threat model.  But especially
for the latter, it makes sense to think about cost.  Here's what
it cost to run various hashes on my /netbsd, on an i386 laptop running
on battery at 600 Mhz:

MD5        0.14s real     0.11s user     0.02s system
SHA-1      0.17s real     0.16s user     0.00s system
RMD160     0.28s real     0.27s user     0.01s system
SHA-256    0.48s real     0.45s user     0.01s system
SHA-384    1.08s real     1.03s user     0.01s system
SHA-512    1.08s real     1.04s user     0.01s system

I don't care about an extra second of CPU time when rebooting -- this
isn't Windows; I don't do it that often! -- but if we merge it with
verifiedexec, it's an issue at runtime for many other programs.