Chosen messages attack on ISO 9796-1 signatures
Francois Grieu
This announces a chosen messages attack against ISO/IEC 9796-1.
ISO/IEC 9796-1 is an international standard defining a digital signature
scheme giving message recovery [1]. It adds redundancy to a message before
applying an RSA or Rabin cryptosystem, as a protection against several
potential threats [2].
For odd public exponents, the new attack constructs sets of 4 messages such
that the signature of any one message can be derived from the signature of
the 3 others, and the public key. Bigger sets can be constructed, allowing k
forgeries from k+2 signatures. For a given modulus size, the same messages
work for any modulus and any odd exponent. The attack is computationally
inexpensive. It is not an attack on the RSA or Rabin cryptosystems.
The method is quite different from the forgery strategy on a 1-bit variant of
ISO/IEC 9796-1 disclosed by Coron, Naccache and Stern in [3], although their
paper gave the motivation to work on an attack against full ISO/IEC 9796-1.
The attack is likely to be a threat only to systems that use ISO/IEC 9796-1
in ways that allow an attacker to obtain signatures of mostly chosen
messages. It is urged to quickly revise such systems.
The method will be explained in a forthcoming paper released not before
October 1, 1999. In the meantime, examples and preliminary versions of the
paper will be privately circulated for review (giving an example here would
reveal the attack without prior notice, which could be viewed as hostile).
As a cheap timestamping, here is the SHA1 hash of a witness file with example
messages for 1024 bit keys: 117AA5EFE71474809FB21C75E0D5F766E4E5B083
Francois Grieu <fgr...@innovatron.fr>
Technical director, Innovatron.
1, rue Danton - 75006 Paris, France.
References:
[1] ISO/IEC 9796-1:1998, "Information technology - Security techniques - Digital
signature scheme giving message recovery <AD> Part 1: Mechanisms using redundanc
y"
[2] Louis Guillou and Jean-Jacques Quisquater, "Precautions taken against
various potential attacks in ISO/IEC DIS 9796", Advances in Cryptology -
EuroCrypt '90, Springer-Verlag.
[3] Jean-Sebastien Coron, David Naccache, and Julien P. Stern, "A New Signature
Forgery Strategy applicable to ISO-9796-1/2, ECash(tm), PKCS#1 V2.0, ANSI X9.31,
SSL-3.02", to appear; preliminary version circulated as ISO/IEC JTC1/SC27 N2329.
[4] Robert D. Silverman and David Naccache, "Recent Results on Signature
Forgery", <http://www.rsa.com/rsalabs/html/sigforge.html>
[5] Louis Guillou, "Report of the SC27/WG2 ad hoc meeting in Paris, France,
May 14, 1999 on Signature forgery attacks", circulated as ISO/IEC
JTC1/SC27 N2355.
[6] Don Coppersmith, Shai Halevi, Charanjit Jutla, "Some countermeasures against
the new forgery strategy", circulated as ISO/IEC JTC1/SC27 N2362.
Roger Schlafly
Francois Grieu wrote in message <7qe5ce$1sb$1...@scream.auckland.ac.nz>...
>ISO/IEC 9796-1 is an international standard defining a digital signature
>scheme giving message recovery [1]. It adds redundancy to a message before
>applying an RSA or Rabin cryptosystem, as a protection against several
>potential threats [2].
>
>For odd public exponents, the new attack constructs sets of 4 messages such
>that the signature of any one message can be derived from the signature of
>the 3 others, and the public key.
IEEE P1363 is currently finalizing a standard that includes this
signature scheme. Some of us are trying to get it removed, but
there is controversy. It might get left in.
For more info on IEEE P1363, see
http://grouper.ieee.org/groups/1363/