Re: [gentoo-portage-dev] Manifest signing

[Robin H. Johnson]

On Sat, Nov 19, 2005 at 06:44:34AM +0000, Ciaran McCreesh wrote:
> | First, the blatantly obvious, for the benefit of same developers, even
> | though it's not relevant to signing. It is still a weak-point and does
> | need to be addressed. Multiple-hashes!
> There is no proof that multiple hashes gives you any security beyond
> the strength of the single most secure hash algorithm. If you have two
> signatures, one of which gives you an effective strength of 100 bits
> and the other of which gives you an effective strength of 80 bits, the
> overall effective strength is not 180 bits.
I didn't claim the overall strength of combining MD5 (128 bits) and
SHA1 (160 bits) would be directly equal, but it does still exceed the
strength of either of them individually, by simple mathematical process.
More importantly for the short term, multiple-hashes are needed for
backwards compatibility - we can't ditch MD5 yet.

> See, this is why you need to be careful. Some things that you'd think
> were 'obvious' probably aren't actually true...
The Wang (2005a) attack breaks MD5 in 2^39 operations, and Wang also
claims being able to theoretically do SHA1 under 2^69 operations
(2005b), full details of the SHA1 break have not been published to date
(SHA1 is still 2^30 times harder to break than MD5 - assuming your
machine can break MD5 in 1 hour that's still conservatively 10k+ years
to break SHA1).
  
Note that Sasaki et al (2005) have signifcently improved on Wang's MD5
attack, claiming 2^30 operations.

If you consider the method of the breaks, some of the other papers have
noted that while some of the mathematics behind the Wang attack are
applicable across all classes of hash functions, many of them are not
suitable across other classes of hash functions. MD5 and SHA* are
however closely related, so they should be considered as having a
combined strength much closer to MAX(MD5,SHA*) than SUM(MD5,SHA*).

Wang et al. 2005a. How to Break MD5 and Other Hash Functions.
http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf
Wang et al. 2005b. Collision Search Attacks on SHA1.
http://theory.csail.mit.edu/~yiqun/shanote.pdf
Sasaki et al. 2005. Improved Collision Attack on MD5.
Improved Collision Attack on MD5.

For the short term, MD5+SHA1 or MD5+SHA512 allows old versions of
portage (that only support MD5) to continue to work, while offering the
security of SHA512 to newer versions of portage.

If you really wanted to be pedantic about which hash functions were
used together, you can go the whole hog in choosing functions of
different classes: SHA512+HAVAL256+TIGER192+WHIRLPOOL (throw in GOST too
if you are paranoid, it's reasonable certain that the NSA has broken
it).
But I think you'd get complaints that it would take too long to check
all of the hashes. Maybe just pick two hashes of the above to go
onwards with. I'd favour SHA512+TIGER192 as being of very different
design, and the implementations are fast.

-- 
Robin Hugh Johnson
E-Mail     : robbat2@g.o
GnuPG FP   : 11AC BA4F 4778 E3F6 E4ED  F38E B27B 944E 3488 4E85