Halevi and Krawczyk proposed a message randomization algorithm called RMX as a front-end tool to the hash-then-sign digital signature schemes such as DSS and RSA in order to free their reliance on the collision resistance property of the hash functions. They have shown that to forge a RMX-hash-then-sign signature scheme, one has to solve a cryptanalytical task which is related to finding second preimages for the hash function. In this article, we will show how to use Dean’s method of finding expandable messages for finding a second preimage in the Merkle-Damgård hash function to existentially forge a signature scheme based on a t-bit RMX-hash function which uses the Davies-Meyer compression functions (e.g., MD4, MD5, SHA family) in 2 t/2 chosen messages plus 2 t/2 + 1 off-line operations of the compression function and similar amount of memory. This forgery attack also works on the signature schemes that use Davies-Meyer schemes and a variant of RMX published by NIST in its Draft Special Publication (SP) 800-106. We discuss some important applications of our attack.
|Publication status||Published - 2009|
|Event||Advances in Cryptology - EUROCRYPT 2009 : 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Cologne, Germany|
Duration: 1 Jan 2009 → …
Conference number: 28
|Conference||Advances in Cryptology - EUROCRYPT 2009 : 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques|
|Period||01/01/2009 → …|
- Digital signatures,Hash functions,Davies-Meyer, Randomized hashing