The ISO/IEC 9796-1 signature standard is the first international standard for digital signatures. This paper describes two different attacks against it. Each of the two attacks constitutes existential forgery under a chosen message attack: the attacker asks for the signature of some message of his choice and is then able to produce the signature of a message that was never signed by the owner of the private key. The first attack was presented by Coppersmith, Halevi, and Jutla [1] and is a variant of another attack [2] against a slightly modified variant of the ISO/IEC 9796-1 standard. All of these variants require a few hundred signatures. The second attack was published by Grieu [3]; it uses a different technique. This attack is more powerful, as it requires only three signatures. After the publication of these attacks, the ISO/IEC 9796-1 standard was withdrawn.

Section 2 defines the RSA and Rabin signature schemes. Section 3 studies the initial variant of the attack against the ISO/IEC 9796-1 signature standard (Desmet and Odlyzsko attack) and analyzes its complexity. Then, it extends to any exponent greater than 3 in subsection 3.2, and to Rabin-Williams signatures in subsection 3.3. At the suggestion of one of the referees of the initial version of the paper, an improved attack is proposed in subsection 3.5. Section 4 is dedicated to the presentation of the ISO/IEC 9796-1 signature standard. Section 5 describes the attack constructed by Coron, Naccache, and Stern against the ISO/IEC-1 standard, in which the encoding function is modified by a single bit. Section 6 presents a complete attack against the full ISO/IEC 9796-1 standard. The second attack against the signature standard, proposed by Grieu, is described in section 7. This attack is based on a graph traversal, and constructs two message pairs whose expansions are in common ratio. This allows a forgery to be produced from only three messages.

The presentation is remarkably clear and the math is easy to understand.