### How Risky is the Random-Oracle Model?

Gaetan Leurent and Phong Q. Nguyen

##### Abstract

RSA-FDH and many other schemes secure in the Random-Oracle Model (ROM) require a hash function with output size larger than standard sizes. We show that the random-oracle instantiations proposed in the literature for such cases are weaker than a random oracle, including the proposals by Bellare and Rogaway from 1993 and 1996, and the ones implicit in IEEE P1363 and PKCS standards: for instance, there is a practical $2^{30}$ preimage attack on BR93 for 1024-bit digests. Next, we study the security impact of hash function defects for ROM signatures. As an extreme case, we note that any hash collision would suffice to disclose the master key in the ID-based cryptosystem by Boneh et al. from FOCS '07, and the secret key in the Rabin-Williams signature for which Bernstein proved tight security at EUROCRYPT '08. Interestingly, for both of these schemes, a slight modification can prevent these attacks, while preserving the ROM security result. We give evidence that in the case of RSA and Rabin/Rabin-Williams, an appropriate PSS padding is more robust than all other paddings known.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Full version of the CRYPTO 2009 article.
Keywords
hash functionscryptanalysispublic-key cryptography
Contact author(s)
pnguyen @ di ens fr
History
2009-07-23: last of 2 revisions
See all versions
Short URL
https://ia.cr/2008/441

CC BY

BibTeX

@misc{cryptoeprint:2008/441,
author = {Gaetan Leurent and Phong Q.  Nguyen},
title = {How Risky is the Random-Oracle Model?},
howpublished = {Cryptology ePrint Archive, Paper 2008/441},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/441}},
url = {https://eprint.iacr.org/2008/441}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.