×

Cryptanalysis of ISO/IEC 9796-1. (English) Zbl 1146.68366

Summary: We describe two different attacks against the ISO/IEC 9796-1 signature standard for RSA and Rabin. Both attacks consist in an existential forgery under a chosen-message attack: the attacker asks for the signature of some messages of his choice, and is then able to produce the signature of a message that was never signed by the legitimate signer. The first attack is a variant of Desmedt and Odlyzko’s attack and requires a few hundreds of signatures. The second attack is more powerful and requires only three signatures.

MSC:

68P25 Data encryption (aspects in computer science)

Software:

NTL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Coppersmith, S. Halevi, C. Jutla, ISO 9796-1 and the new forgery strategy, Research contribution to P1363, 1999. Available at http://grouper.ieee.org/groups/1363/contrib.html.
[2] Coron, J. S.; Naccache, D.; Stern, J. P., On the security of RSA padding, Proceedings of Crypto ’99, 1-18 (1999), Berlin: Springer, Berlin · Zbl 0940.94010
[3] Desmedt, Y.; Odlyzko, A., A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, Proceedings of Crypto ’85, 516-522 (1985), Berlin: Springer, Berlin
[4] Dickman, K., On the frequency of numbers containing prime factors of a certain relative magnitude, Ark. Mat. Astron. Fys., 22A, 10, 1-14 (1930) · JFM 56.0178.04
[5] Goldwasser, S.; Micali, S.; Rivest, R., A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. Comput., 17, 2, 281-308 (1988) · Zbl 0644.94012
[6] Grieu, F., A chosen message attack on the ISO/IEC 9796-1 signature scheme, Advances in Cryptology—Eurocrypt 2000, 70-80 (2000), Berlin: Springer, Berlin · Zbl 1082.94519
[7] Guillou, L.; Quisquater, J.-J.; Walker, M.; Landrock, P.; Shaer, C., Precautions taken against various attacks in ISO/IEC DIS 9796, Proceedings of Eurocrypt’ 90, 465-473 (1990), Berlin: Springer, Berlin · Zbl 0825.94198
[8] ISO/IEC 9796, Information Technology—Security Techniques—Digital Signature Scheme Giving Message Recovery, Part 1: Mechanisms Using Redundancy, 1991.
[9] Lanczos, C., An iterative method for the solution of the eigenvalue problem of linear differential and integral operator, J. Res. Nat. Bur. Standards, 45, 255-282 (1950)
[10] Lenstra, H. W. Jr., Factoring integers with elliptic curves, Ann. Math., 126, 2, 649-673 (1987) · Zbl 0629.10006
[11] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A., Handbook of Applied Cryptography (1996), Boca Raton: CRC Press, Boca Raton · Zbl 0868.94001
[12] Misarsky, J.-F., How (not) to design RSA signature schemes, Public-Key Cryptography, 14-28 (1998), Berlin: Springer, Berlin · Zbl 1067.94553
[13] Rivest, R.; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public key cryptosystems, Commun. ACM, 21, 120-126 (1978) · Zbl 0368.94005
[14] V. Shoup, Number Theory C++ Library (NTL) version 5.3.1. Available at www.shoup.net.
[15] Stinson, D., Cryptography: Theory and Practice (1995), Boca Raton: CRC Press, Boca Raton · Zbl 0855.94001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.