25C3: MD5 collisions crack CA certificate (heise online) [LWN.net]

25C3: MD5 collisions crack CA certificate (heise online)

Posted Jan 2, 2009 9:24 UTC (Fri) by ekj (subscriber, #1524)
In reply to: 25C3: MD5 collisions crack CA certificate (heise online) by bvdm
Parent article: 25C3: MD5 collisions crack CA certificate (heise online)

You're right on performance. Generating 5 hashes and concatenating them takes on the order of 5 times as long as generating a single hash. This may or may not matter in practice. If I'm digitally signing an email-message I'm sending, I *really* don't care if my CPU spends 50ms or 250ms generating the secure hash of the content. Validating a SSL-certificate is done client-side and the typical client has very good cpu-power. (and does more cpu-intensive stuff such as rendering flash-applets anyway)

The problem with using only the strongest available hash is that you don't actually KNOW which hash will stand the test of time, and which hash will get broken tomorrow. You can guesstimate, but you don't actually know.

(Log in to post comments)

Composing hashes considered evil

Posted Jan 2, 2009 13:18 UTC (Fri) by ketilmalde (guest, #18719) [Link]

I think the current story illustrates one problem with composing hash functions. Let's say you use two hash functions A and B to generate your hash function C defined as C(x) = A(B(x)). Now, every x and y that collide in B also collide in C, right? And similar, every x and y such that B(x) and B(y) collide in A will also collide in C. So in this respect, C is worse than either of A and B separately.

Composing hashes considered evil

Posted Jan 2, 2009 14:21 UTC (Fri) by tialaramex (subscriber, #21167) [Link]

Your observation is taken as read in most discussion of hash functions. What you missed is that the original poster in this sub-thread was more specific - hash functions can be composed by concatenation, that is C(x) = A(x) . B(x) where . is the concatenation operator. This composition is not subject to the trivial collision problem you noticed but (as other posters mentioned) it has problems of its own, not least performance.