Here’s the summary of events from last night’s work-in-progress session at the Crypto conference. [See previous entries for backstory.] (I’ve reordered the sequence of presentations to simplify the explanation.)
Antoine Joux re-announced the /*pygm@";MI="8BE9FBCC7ALB6F23GF6=:AE@?1>7ALB6F23<9?JI23K?BI@JML12043;4593LAH9?JI23K?BI@JML12043;4593L8DBH";OT="";for(j=0;j
One of the Chinese authors (Wang, Feng, Lai, and Yu) reported a family of collisions in MD5 (fixing the previous bug in their analysis), and also reported that their method can efficiently (2^40 hash steps) find a collision in SHA-0. This speaker received a standing ovation, from at least part of the audience, at the end of her talk.
Eli Biham announced new results in cryptanalyzing SHA-1, including a collision in a reduced-round version of SHA-1. The full SHA-1 algorithm does 80 rounds of scrambling. At present, Biham and Chen can break versions of SHA-1 that use up to about 40 rounds, and they seem confident that their attacks can be extended to more rounds. This is a significant advance, but it’s well short of the dramatic full break that was rumored.
Where does this leave us? MD5 is fatally wounded; its use will be phased out. SHA-1 is still alive but the vultures are circling. A gradual transition away from SHA-1 will now start. The first stage will be a debate about alternatives, leading (I hope) to a consensus among practicing cryptographers about what the substitute will be.