%&LaTeX (tells OzTeX to use LaTeX format)
%%% this is meaningless outside MPW [addmenu Custom 'TexIt/@' 'save "{active}"; OzTeX "{active}"']
%%% this is meaningless outside MPW [save "{active}"; OzTeX "{active}"]
%%% this is meaningless outside MPW [find 394 "{active}"]
\documentclass{llncs}
%%%\usepackage{latexsym}
\usepackage{amsmath}
%%%\usepackage{amsfonts}
%%%\usepackage{amssymb}
\begin{document}
\def\CAT{\;\|\;}
\def\LCM{\mbox{ lcm}}
\def\GCD{\mbox{ gcd}}
\def\MOD{\mbox{ mod\:}}
\title{A Chosen Messages Attack on\\the ISO/IEC 9796--1 Signature Scheme}
\author{Fran\c{c}ois Grieu
\institute{Spirtech, 1 rue Danton, 75006 Paris, France\\
\email{francois.grieu@spirtech.com}}}
\date{March 1, 2000}
\maketitle
\begin{abstract}
We introduce an attack against the ISO/IEC 9796--1 digital signature scheme using redundancy,
taking advantage of the multiplicative property of the RSA and Rabin cryptosystems.
The forged signature of 1 message is obtained from the signature of 3 others for any public exponent $v$.
For even $v$, the modulus is factored from the signature of 4 messages, or just 2 for $v=2$.
The attacker must select the above messages from a particular message subset,
which size grows exponentialy with the public modulus bit size.
The attack is computationally inexpensive, and works for any modulus of
$16 z$, $16 z \pm 1$, or $16 z \pm 2$ bits.
This prompts the need to revise ISO/IEC 9796--1, or avoid its use in situations where an
adversary could obtain the signature of even a few mostly chosen messages.
\end{abstract}
\section{Introduction}
ISO/IEC 9796--1 \cite{iso9796of1991} \cite{iso9796p1of1998} is
an international standard specifying a digital signature scheme giving message recovery,
designed primarily for the RSA and Rabin public key cryptosystems.
To sign a message $M$, it is first transformed by inserting redundant information
obtained by simple transformations of individual bytes of $M$,
producing the expanded message $\tilde{M}$;
then the private key function $\mathcal{S}$ of the cryptosystem is applied,
producing the signature $\ddot{M} = \mathcal{S}(\tilde{M})$.
To verify an alleged signature $\ddot{M}'$, the public key function
$\mathcal{V}$ of the cryptosystem is applied,
producing an alleged expanded message $\tilde{M}' = \mathcal{V}(\ddot{M}')$;
then the alleged message $M'$ is recovered from $\tilde{M}'$ by straightforward
extraction, and it is checked $\tilde{M}'$ is what it should be under the
signature production process.
ISO/IEC 9796--1 expansion makes it highly improbable that a randomly generated
value is an acceptable signature. It meets precise design criterias in order to guard
against a variety of other attacks, see \cite{gui:qui} and \cite{iso9796p1of1998}.
The recently introduced Coron--Naccache--Stern forgery strategy of \cite{cor:nac:ste}
is effective on a slightly simplified variant of ISO/IEC 9796--1.
Motivated by this breakthrough and unaware of an extension to the full standard in \cite{cop:hal:jut2},
the author made an independent effort to attack ISO/IEC 9796--1 and discovered a new, simple and effective method.
In a nutshell, we efficiently construct many message pairs $A,B$ with $\tilde{A}/\tilde{B}$ equal to a common ratio.
Forgery follows from the multiplicative property of the cryptosystem used: $\mathcal{S}(xy) = \mathcal{S}(x)\mathcal{S}(y)$.
\section{Definitions}
When there is no ambiguity, we assimilate a bit string of fixed length
and the integer having this binary representation.
Following ISO/IEC 9796--1 unless stated otherwise, we use the notations
\[{
\begin{tabular}{c@{\quad}l}
$x\CAT y$ & Concatenation of bitstrings $x$ and $y$.\\
$x{\oplus}y$ & Bitwise exclusive OR of bitstrings $x$ and $y$.\\
$[x]_i$ & The bitstring of exactly $i$ bits with ${{[x]}_i}\equiv{x\MOD{2^i}}$.\\
$\LCM(x,y)$ & Least Common Multiple of $x$ and $y$.\\
$\GCD(x,y)$ & Greatest Common Divisor of $x$ and $y$.\\
$v$ & Public verification exponent.\\
$k$ & Number of bits in public modulus.\\
& \quad\textsc{nb}: the standard \cite{iso9796of1991} often use $k_s=k-1$.\\
$n$ & Public modulus of $k$ bits, thus with $2^{k-1} \leq n < 2^k$.\\
$p, q$ & Secret factors of $n$, with $n = p\:q$.\\
& \quad if $v$ is odd, $p-1$ and $q-1$ are prime with $v$.\\
& \quad if $v$ is even, $(p-1)/2$ and $(q-1)/2$ are prime with $v$,\\
& \qquad $p \equiv 3 \MOD 4$ and $q \equiv p+4 \MOD 8$.\\
$(\!x|n\!)$ & Jacobi symbol of $x$ with respect to $n$, used for even $v$ only.\\
& \quad $(\!x|n\!) = (\!x|p\!)(\!x|q\!) = (x^{(p-1)/2}\MOD p) (x^{(q-1)/2}\MOD q)$.\\
& \quad For even $v$ the construction of $p$ and $q$ is such that $(\!2|n\!)=-1$.\\
& \quad $(\!x|n\!)$ can be efficiently computed without knowledge of $p$ and $q$.\\
$s$ & Secret signing exponent.\\
& \quad if $v$ is odd, $s\;v\equiv{1}\MOD{\LCM({p-1},{q-1})}$,\\
& \qquad and as a consequence $(x^s)^v \equiv x\MOD n$ for any $x$.\\
& \quad if $v$ is even, $s\;v\equiv{1}\MOD{\LCM({p-1},{q-1})}/2$,\\
& \qquad and as a consequence $(x^s)^v \equiv x\MOD n$ if $(\!x|n\!)=+1$.\\
$z$ & Number of bytes a message fits in; $z\leq{\lfloor{(k+2)/16}\rfloor}$.\\
$M$ & Message to sign, which breaks up into the $z$ bytes string\\
& \quad $m_z\CAT m_{z-1}\CAT ..\CAT m_2\CAT m_1$\\
$\tilde{M}$ & Message as expanded according to ISO/IEC 9796--1 (see below).\\
& \quad\textsc{nb}: $\tilde{M}$ is noted $Ir$ in \cite{iso9796of1991} and also $Sr$ in \cite{iso9796p1of1998}.\\
$\ddot{M}$ & The signature of M.\quad \textsc{nb}: $\ddot{M}$ is noted $\Sigma(M)$ in \cite{iso9796of1991} and \cite{iso9796p1of1998}.\\
& \quad if $v$ is odd, $\ddot{M}=\min(\tilde{M}^s\MOD n,\;
n-\:\tilde{M}^s\MOD n)$\\
& \quad if $v$ is even, assuming $\GCD(\tilde{M},n)=1$ which is highly probable,\\
&\qquad$\ddot{M}=\min\biggl(\!\!$\Large$\bigl(\!\frac{\tilde{M}}{2^{(1-(\tilde{M}|n))/2}}\!\bigr)^{\!s}\!\!$\normalsize$\MOD n,\;
n-\:$\Large$\bigl(\!\frac{\tilde{M}}{2^{(1-(\tilde{M}|n))/2}}\!\bigr)^{\!s}\!\!$\normalsize$\MOD n\!\biggr)$
\end{tabular}
}\]
We restrict our attack and our description of ISO/IEC 9796--1
to the cases ${k}\equiv{0}\mbox{, }{\pm{1}}\mbox{, or }{\pm{2}}\MOD{16}$,
which covers many common choices of moduli, and to messages of $z=\lfloor(k+2)/16\rfloor$ bytes,
the maximum allowed message size.
With these restrictions, the construction of the redundant message amounts to
the local transformation of each byte $m_i$ of the message by an injection $F_i$,
yielding the redundant message
\[{
\tilde{M} = F_z(m_z)\CAT F_{z-1}(m_{z-1})\CAT..\CAT F_2(m_2)\CAT F_1(m_1)
}\]
with the injections $F_i$ transforming an individual byte $m_i$ of two $4$ bit digits $x\CAT y$ as defined by
\begin{equation}{
\begin{tabular}{c@{$(x\CAT y) =\:$}l}
$F_1$ & $\Pi(x)\CAT \Pi(y)\CAT y\CAT [\mathtt{6}]_4$\\
$F_i$ & $\Pi(x)\CAT \Pi(y)\CAT x\CAT y\quad\text{ for } 1*b-a$.
It is handy to group $\bar{a}_i$, $\bar{b}_i$ into a single \textit{link} defined as
\begin{equation}{
l_i = \bar{a}_i+\bar{b}_i+1 \qquad\mbox{with}\quad1\le l_i}.
\bibitem {iso9796p1of1998}
ISO/IEC 9796--1 Second edition Final Committee Draft. Information technology -- Security techniques -- Digital signature
scheme giving message recovery -- Part 1: Mechanisms using redundancy.\\
Circulated as ISO/IEC JTC1/SC27 N2175 (1998).
\bibitem {gui:qui}
Guillou, L. C. and Quisquater, J. J. and Walker, M. and Landrock, P. and Shaer, C.:
Precautions taken against various potential attacks in ISO/IEC {DIS} 9796.
Advances in Cryptology - EuroCrypt '90 (1990) 465--473.
\bibitem {cor:nac:ste}
Coron, J. S. and Naccache, D. and Stern, J. P.:
A new signature forgery strategy applicable to ISO 9796--1/2, ECASH$\mathrm{^{TM}}$, PKCS\#1 V2.0, ANSI X9.31, SSL-3.02.\\
Circulated as ISO/IEC JTC1/SC27 N2329 alias WG2 N429 (1999).
\bibitem {cop:hal:jut}
Coppersmith, D. and Halevi, S. and Jutla, C.:
Some countermeasures against the new forgery strategy (Working Draft).\\
Circulated as ISO/IEC JTC1/SC27 N2362 (1999).
\bibitem {cop:hal:jut2}
Coppersmith, D. and Halevi, S. and Jutla, C.:
ISO 9796--1 and the new forgery strategy (Working Draft) (1999).\\
See \texttt{}.
\bibitem {joy:qui}
Joye, M. and Quisquater, J.J.:
On Rabin-type Signatures (Working Draft)\\
Circulated as ISO/IEC JTC1/SC27/WG2 N449 (1999).
\bibitem {hac}
Menezes, A. and van Oorschot, P. and Vanstone, S.:
Handbook of Applied Cryptography (1997).
CRC Press, ed.\\
See \texttt{}.
\end{thebibliography}
\end{document}
*