Crypto - News

Second Preimages on n-bit Hash Functions for Much Less than 2^n Work

John Kelsey and Bruce Schneier

Abstract. We provide a second preimage attack on all n-bit iterated hash functions with Damgard-Merkle strengthening and n-bit itermediate states, allowing a second preimage to be found for a 2^k-message-block message with about k * 2^{n/2+1} + 2^{n-k+1} work. Using SHA1 as an example, our attack can find a second preimage for a 2^{60} byte message in 2^{106} work, rather than the previously expected 2^{160} work. We also provide slightly cheaper ways to find multicollisions than the method of Joux. Both of these results are based on expandable messages--patterns for producing messages of varying length, which all collide on the intermediate hash result immediately after processing the message. We also provide algorithms for finding expandable messages for a hash function, using only a small multiple of the work done to find a single collision in the hash function.

Autor: VK

Heuristické vyhledání souvisejících článků v archívu NEWS

• Time´s up for SHA-1 hash algo, but one in five websites still use it
• RC4-hash - nová hashovací funkce opírající se o algoritmus RC4
• End-to-end email encryption with no central point of attack
• ECRYPT Position Paper: Recent Collision Attacks on Hash Functions
• Vl.Klíma: A New Concept of Hash Functions SNMAC Using a Special Block Cipher and NMAC/HMAC Constructions