\documentstyle{llncs}

\setlength{\unitlength}{.8pt}

\newcommand{\bigsplus}{\framebox(8,8){$+$}}

\title{Weak Keys for IDEA}
\author{Joan Daemen, Ren\'{e} Govaerts and Joos Vandewalle}
\institute{Katholieke Universiteit Leuven, Laboratorium ESAT\\
Kardinaal Mercierlaan 94, B-3001 Heverlee, Belgium\\
\verb+email: joan.daemen@esat.kuleuven.ac.be+}

\begin{document}
\maketitle

\begin{abstract}
%
Large classes of weak keys have been found for the block cipher algorithm
IDEA, previously known as IPES \cite{ipes}. IDEA has a 128-bit key and encrypts 
blocks of 64 bits. For a class of $2^{23}$ keys IDEA exhibits a linear
factor. For a certain class of $2^{35}$ keys the cipher has a global 
characteristic with probability 1. For another class of $2^{51}$ keys only two 
encryptions and solving a set of 16 nonlinear boolean equations with 12 
variables is sufficient to test if the used key belongs to this class. If it 
does, its particular value can be calculated efficiently. It is shown that the
problem of weak keys can be eliminated by slightly modifying the key 
schedule of IDEA.
%
\end{abstract}
\section{Introduction}
%
At Eurocrypt '90 the block cipher proposal PES (Proposed Encryption Standard)
was presented \cite{pes}. At Eurocrypt '91 the same authors presented a 
modification of PES, called IPES (Improved PES) \cite{ipes}. The reason for 
this modification were new insights based on differential cryptanalysis 
\cite{biham}. IPES has become commercialized under the name IDEA 
(International Data Encryption Algorithm).

IDEA is an iterated cipher consisting of 8 similar rounds and a single output 
transformation. The building blocks of the round function are
multiplication modulo $2^{16}+1$, addition modulo $2^{16}$ and bitwise XOR.
IDEA has a 128-bit key and encrypts/decrypts data in blocks of 64 bits.

With exception of the key schedule, the IDEA decryption 
process is the same as its encryption process. The computational graph of the 
IDEA algorithm is shown in Fig.1. The encryption round keys are 16-bit 
substrings of the global key as specified in Table 1. The decryption 
round keys can be derived from the encryption round keys.
%
\begin{figure}
\begin{center}
\begin{picture}(360,500)(0,-140)

\begin{thicklines}

\put(40,320){\makebox(0,0){$X_1$}}
\put(80,320){\makebox(0,0){$X_2$}}
\put(280,320){\makebox(0,0){$X_3$}}
\put(320,320){\makebox(0,0){$X_4$}}

\put(40,310){\vector(0,-1){25}}
\put(80,310){\vector(0,-1){25}}
\put(280,310){\vector(0,-1){25}}
\put(320,310){\vector(0,-1){25}}

\put(0,280){\makebox(0,0){$Z_1^{(1)}$}}
\put(10,280){\vector(1,0){25}}
\put(40,280){\makebox(0,0){$\bigodot$}}
\put(80,280){\makebox(0,0){\bigsplus}}
\put(110,280){\vector(-1,0){25}}
\put(120,280){\makebox(0,0){$Z_2^{(1)}$}}
\put(240,280){\makebox(0,0){$Z_3^{(1)}$}}
\put(250,280){\vector(1,0){25}}
\put(280,280){\makebox(0,0){\bigsplus}}
\put(320,280){\makebox(0,0){$\bigodot$}}
\put(350,280){\vector(-1,0){25}}
\put(360,280){\makebox(0,0){$Z_4^{(1)}$}}

\put(40,275){\vector(0,-1){170}}
\put(80,275){\vector(0,-1){190}}
\put(280,275){\vector(0,-1){170}}
\put(320,275){\vector(0,-1){190}}

\put(40,240){\makebox(0,0){$\bullet$}}
\put(40,240){\vector(1,0){115}}
\put(160,240){\makebox(0,0){$\bigoplus$}}
\put(280,240){\makebox(0,0){$\bullet$}}
\put(280,240){\vector(-1,0){115}}

\put(160,235){\vector(0,-1){50}}

\put(80,220){\makebox(0,0){$\bullet$}}
\put(80,220){\vector(1,0){115}}
\put(200,220){\makebox(0,0){$\bigoplus$}}
\put(320,220){\makebox(0,0){$\bullet$}}
\put(320,220){\vector(-1,0){115}}

\put(200,215){\vector(0,-1){30}}

\put(120,180){\makebox(0,0){$Z_5^{(1)}$}}
\put(130,180){\vector(1,0){25}}
\put(160,180){\makebox(0,0){$\bigodot$}}
\put(165,180){\vector(1,0){30}}
\put(200,180){\makebox(0,0){\bigsplus}}

\put(160,175){\vector(0,-1){30}}
\put(200,175){\vector(0,-1){30}}

\put(160,140){\makebox(0,0){\bigsplus}}
\put(195,140){\vector(-1,0){30}}
\put(200,140){\makebox(0,0){$\bigodot$}}
\put(230,140){\vector(-1,0){25}}
\put(240,140){\makebox(0,0){$Z_6^{(1)}$}}

\put(160,135){\line(0,-1){55}}
\put(200,135){\line(0,-1){35}}

\put(40,100){\makebox(0,0){$\bigoplus$}}
\put(200,100){\vector(-1,0){155}}
\put(200,100){\makebox(0,0){$\bullet$}}
\put(200,100){\vector(1,0){75}}
\put(280,100){\makebox(0,0){$\bigoplus$}}

\put(40,95){\vector(0,-1){75}}
\put(280,95){\line(0,-1){25}}

\put(80,80){\makebox(0,0){$\bigoplus$}}
\put(160,80){\vector(-1,0){75}}
\put(160,80){\makebox(0,0){$\bullet$}}
\put(160,80){\vector(1,0){155}}
\put(320,80){\makebox(0,0){$\bigoplus$}}

\put(80,75){\line(0,-1){5}}
\put(320,75){\vector(0,-1){55}}

\put(80,70){\line(5,-1){200}}
\put(280,70){\line(-5,-1){200}}

\put(280,30){\vector(0,-1){10}}
\put(80,30){\vector(0,-1){10}}

\put(40,14){\makebox(0,0){$\vdots$}}
\put(80,14){\makebox(0,0){$\vdots$}}
\put(180,10){\makebox(0,0){(7 more rounds)}}
\put(280,14){\makebox(0,0){$\vdots$}}
\put(320,14){\makebox(0,0){$\vdots$}}

\put(40,0){\vector(0,-1){55}}
\put(80,0){\line(0,-1){5}}
\put(280,0){\line(0,-1){5}}
\put(320,0){\vector(0,-1){55}}

\put(80,-5){\line(5,-1){200}}
\put(280,-5){\line(-5,-1){200}}

\put(80,-45){\vector(0,-1){10}}
\put(280,-45){\vector(0,-1){10}}

\put(0,-60){\makebox(0,0){$Z_1^{(9)}$}}
\put(10,-60){\vector(1,0){25}}
\put(40,-60){\makebox(0,0){$\bigodot$}}
\put(80,-60){\makebox(0,0){\bigsplus}}
\put(110,-60){\vector(-1,0){25}}
\put(120,-60){\makebox(0,0){$Z_2^{(9)}$}}
\put(240,-60){\makebox(0,0){$Z_3^{(9)}$}}
\put(250,-60){\vector(1,0){25}}
\put(280,-60){\makebox(0,0){\bigsplus}}
\put(320,-60){\makebox(0,0){$\bigodot$}}
\put(350,-60){\vector(-1,0){25}}
\put(360,-60){\makebox(0,0){$Z_4^{(9)}$}}

\put(40,-65){\vector(0,-1){15}}
\put(80,-65){\vector(0,-1){15}}
\put(280,-65){\vector(0,-1){15}}
\put(320,-65){\vector(0,-1){15}}

\put(40,-90){\makebox(0,0){$Y_1$}}
\put(80,-90){\makebox(0,0){$Y_2$}}
\put(280,-90){\makebox(0,0){$Y_3$}}
\put(320,-90){\makebox(0,0){$Y_4$}}

\put(20,-120)
{$X_i,Y_i, Z^{(r)}_i$ : 16-bit plaintext, ciphertext and key subblocks}
\put(20,-135){$\bigoplus$ : bitwise XOR}  
\put(200,-135){\bigsplus\ : addition mod $2^{16}$}
\put(20,-150){$\bigodot$ : multiplication mod $2^{16}+1$ with 0000 (HEX) 
$\equiv 2^{16}$}

\end{thicklines}

\end{picture}
\end{center}
\caption{the encryption process of IDEA.}
\end{figure}
%
\begin{table}
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|}\hline
$r$ & $Z_1$ & $Z_2$ & $Z_3$ & $Z_4$ & $Z_5$ & $Z_6$ \\ \hline
1 &  0--15  &  16--31  &  32--47  &  48--63 &  64--79  &  80--95 \\
2 & 96--111 & 112--127 &  25--40  &  41--56 &  57--72  &  73--88 \\
3 & 89--104 & 105--120 & 121--8   &   9--24 &  50--65  &  66--81 \\
4 & 82--97  &  98--113 & 114--1   &   2--17 &  18--33  &  34--49 \\
5 & 75--90  &  91--106 & 107--122 & 123--10 &  11--26  &  27--42 \\
6 & 43--58  &  59--74  & 100--115 & 116--3  &   4--19  &  20--35 \\
7 & 36--51  &  52--67  &  68--83  &  84--99 & 125--12  &  13--28 \\
8 & 29--44  &  45--60  &  61--76  &  77--92 &  93--108 & 109--124 \\
9 & 22--37  &  38--53  &  54--69  &  70--85 &   ---   &    ---   \\ \hline
\end{tabular}
\end{center}
\caption{Derivation of the encryption round keys of the global 128-bit 
key. The key bits are indexed starting from 0. The most significant bit 
(MSB) of the round keys are the bits with the lowest global index.}
\end{table}
%
\section{Linearities in the Modular Arithmetic Operations}
%
Let $x_i$ denote the $i$-th bit in the binary 
representation of the number $X$, i.e. $X = \sum 2^i x_i$.
The bits of $Y = X+Z \bmod{2^n}$ are given by 
\begin{equation}
y_i = x_i \oplus z_i \oplus c_i
\end{equation}
with $c_i$ a carry bit that only depends on bits with indices {\em smaller 
than} $i$. The LSB of $Y$ ($y_0$) is simply equal to $x_0 \oplus z_0$.
Propagation of the MSBs of $X$ and $Z$ into $Y$ is restricted to linear 
propagation (over $\bbbz_2^{16}$) into the MSB of $Y$. 

For the multiplication by $-1$ (0000 HEX) modulo $2^{16}+1$ as defined in the 
IDEA block cipher it can easily be checked that 
\begin{equation}
-1 \odot A = \bar{A} + 2 \bmod{2^{16}}
\end{equation}
with $\bar{A}$ the bitwise complement of $A$. Therefore multiplication by
$-1$ inherits the linearity properties of the addition modulo $2^n$.
%
\section{Classes of Weak Keys yielding Linear Factors}
%
The use of multiplicative subkeys with value $1 \mbox{ or } -1$ give rise to 
{\em linear factors} \cite{chaum} in the round function. In the context of 
this paper a linear factor is a linear equation in key, input and output bits 
that holds for all possible {\em inputs}. The linear factors can be revealed 
by expressing the sum (modulo 2) of LSBs of the output subblocks of an IDEA 
round in terms of input and key bits.

As an example, we will express the XOR of the LSBs of the first and second 
output subblock of a round: $y_1 \oplus y_2$ (with the indices denoting the 
subblock number). From Fig.1 it can be seen that 
$y_1 \oplus y_2 = (X_1 \cdot Z_1)|_0 \oplus 1 \oplus x_3 \oplus z_3$. If 
$Z_1 = (-)1$, i.e. if the 15 MSB bits of the $Z_1$ are 0, 
\begin{equation}
y_1 \oplus y_2 = x_1 \oplus x_3 \oplus z_1 \oplus z_3 \oplus 1 \enspace .
\end{equation} 
If the key bits are considered as (albeit unknown) constants, this linear
factor can be interpreted as the propagation of knowledge from 
$x_1 \oplus x_3 \mbox{ to } y_1 \oplus y_2$, denoted by 
$(1,0,1,0) \rightarrow (1,1,0,0)$. 
Similar factors and their corresponding conditions on subkey blocks can be 
found for all 15 combinations of LSB output bits and are listed in Table 2.
%
\begin{table}
\begin{center}
\begin{tabular}{ccccc} \hline
\makebox[35mm]{linear factor} & \makebox[1cm]{$Z_1$} & \makebox[1cm]{$Z_4$} & 
\makebox[1cm]{$Z_5$} & \makebox[1cm]{$Z_6$} \\ 
\hline
$(0,0,0,1) \rightarrow (0,0,1,0) $ &   -   & $(-)1$ &   -   & $(-)1$  \\
$(0,0,1,0) \rightarrow (1,0,1,1) $ &   -   &   -   & $(-)1$  & $(-)1$  \\
$(0,0,1,1) \rightarrow (1,0,0,1) $ &   -   & $(-)1$ & $(-)1$  &   -   \\
$(0,1,0,0) \rightarrow (0,0,0,1) $ &   -   &   -   &   -   & $(-)1$  \\
$(0,1,0,1) \rightarrow (0,0,1,1) $ &   -   & $(-)1$ &   -   &   -   \\
$(0,1,1,0) \rightarrow (1,0,1,0) $ &   -   &   -   & $(-)1$  &   -   \\
$(0,1,1,1) \rightarrow (1,0,0,0) $ &   -   & $(-)1$ & $(-)1$  & $(-)1$  \\
$(1,0,0,0) \rightarrow (0,1,1,1) $ & $(-)1$ &   -   & $(-)1$  & $(-)1$  \\
$(1,0,0,1) \rightarrow (0,1,0,1) $ & $(-)1$ & $(-)1$ & $(-)1$  &   -   \\
$(1,0,1,0) \rightarrow (1,1,0,0) $ & $(-)1$ &   -   &   -   &   -   \\
$(1,0,1,1) \rightarrow (1,1,1,0) $ & $(-)1$ & $(-)1$ &   -   & $(-)1$  \\
$(1,1,0,0) \rightarrow (0,1,1,0) $ & $(-)1$ &   -   & $(-)1$  &   -   \\
$(1,1,0,1) \rightarrow (0,1,0,0) $ & $(-)1$ & $(-)1$ & $(-)1$  & $(-)1$  \\
$(1,1,1,0) \rightarrow (1,1,0,1) $ & $(-)1$ &   -   &   -   & $(-)1$  \\
$(1,1,1,1) \rightarrow (1,1,1,1) $ & $(-)1$ & $(-)1$ &   -   &   -   \\
\hline
\end{tabular}
\end{center}
\caption{Linear factors in the round function with conditions on the subkeys.}
\end{table}

Multiple-round linear factors can be found by combining linear factors
where the involved intermediate terms cancel out. For every round
this gives conditions on subkeys that can be converted to conditions 
on global key bits using Table 1. An example is given in Table 3 for the
global linear factor $(1,0,1,0) \rightarrow (0,1,1,0)$. The global key
bits whose indices are given in this table must be 0. Since key bits 
with indices in 26-28, 72-74 or 111-127 don't appear, there are
$2^{23}$ global keys that have this linear factor. This is called a {\em
class of weak keys} since membership can easily be checked by observing 
some corresponding plaintext-ciphertext combinations. 
%
\begin{table}
\begin{center}
\begin{tabular}{lccc}\hline
round & \makebox[25mm]{input term} &  \makebox[15mm]{$Z_1$}  & 
\makebox[15mm]{$Z_5$} \\ \hline
1     & $(1,0,1,0)$  &  0--14  &    -    \\
2     & $(1,1,0,0)$  & 96--110 & 57--71  \\
3     & $(0,1,1,0)$  &    -    & 50--64  \\
4     & $(1,0,1,0)$  &  82--96 &    -    \\ 
5     & $(1,1,0,0)$  &  75--89 & 11--25  \\
6     & $(0,1,1,0)$  &    -    &  4--18  \\
7     & $(1,0,1,0)$  &  36--50 &    -    \\
8     & $(1,1,0,0)$  &  29--44 & 93--107 \\ 
9     & $(0,1,1,0)$  &    -    &    -    \\ \hline
\end{tabular}
\end{center}
\caption{Conditions on key bits for linear factor 
$(1,0,1,0) \rightarrow (0,1,1,0)$} 
\end{table}
%
\section{Classes of Weak Keys yielding Characteristics with Probability 1}
%
In this section differential cryptanalysis \cite{biham} is applied where 
`difference' is defined by bitwise XOR. The use of multiplicative subkeys 
with value $1 \mbox{ or } -1$ gives rise to characteristics with probability 1 
in the round function.

A round is executed for a pair of inputs $X \mbox{ and }X^*$ with a given 
XOR $X' = X \oplus X^*$. Let $\nu$ be the 16-bit block 8000 (HEX), i.e. the 
MSB is 1 and all other bits are 0. 

Suppose $X \mbox{ and }X^*$ only differ in the MSB bit of the 4-th subblock,
hence $X'_1 = X'_2 = X'_3 = 0 \mbox{ and } X'_4 = \nu$. If $Z_4 = (-)1$ this
will still be the case after the application of $Z_1 \mbox{ to } Z_4$. The 
left input to the MA structure is the same for $X \mbox{ and } X^*$. The right
input differs by $\nu$. This XOR propagates unchanged through the top right 
(TR) addition to the bottom right (BR) multiplication by $Z_6$. If this is 
equal to $(-)1$, the output XOR is again $\nu$. This difference propagates
unchanged through the BL addition and the XORs to the 4 subblocks. The output 
difference $Y'$ of the round is equal to $(\nu,\nu,\nu,0)$. Hence if the
15 MSB of both $Z_4 \mbox{ and } Z_6$ are 0, the input XOR $(0,0,0,\nu)$
gives rise to the output XOR $(\nu,\nu,\nu,0)$ with probability 1, denoted
by $(0,0,0,\nu) \Rightarrow (\nu,\nu,\nu,0)$.
A similar analysis can be made for any other of the 
15 possible nonzero input XORs where only the MSB bits of the subblocks are 
allowed to be 1. The results are listed in Table 4.
\begin{table}
\begin{center}
\begin{tabular}{ccccc} \hline
\makebox[35mm]{characteristic} & \makebox[1cm]{$Z_1$} & \makebox[1cm]{$Z_4$} & 
\makebox[1cm]{$Z_5$} & \makebox[1cm]{$Z_6$} \\ 
\hline
$(0,0,0,\nu) \Rightarrow (\nu,\nu,\nu,0)$ & -   & $(-)1$ & -   & $(-)1$  \\
$(0,0,\nu,0)   \Rightarrow  (\nu,0,0,0)$  & -   & -  & $(-)1$  & $(-)1$  \\
$(0,0,\nu,\nu) \Rightarrow  (0,\nu,\nu,0)$ & -   & $(-)1$ & $(-)1$  & -   \\
$(0,\nu,0,0)   \Rightarrow  (\nu,\nu,0,\nu)$ & -   & -  &   -   & $(-)1$  \\
$(0,\nu,0,\nu) \Rightarrow  (0,0,\nu,\nu)$   & -   & $(-)1$ & -   & -   \\
$(0,\nu,\nu,0) \Rightarrow  (0,\nu,0,\nu)$   & -   & -  & $(-)1$  &   -   \\
$(0,\nu,\nu,\nu) \Rightarrow (\nu,0,\nu,\nu)$ & - & $(-)1$ & $(-)1$ & $(-)1$ \\
$(\nu,0,0,0)     \Rightarrow (0,\nu,0,0)$ & $(-)1$ & - & $(-)1$  & $(-)1$  \\
$(\nu,0,0,\nu)   \Rightarrow (\nu,0,\nu,0)$ & $(-)1$ & $(-)1$  & $(-)1$  & - \\
$(\nu,0,\nu,0)   \Rightarrow (\nu,\nu,0,0)$ & $(-)1$ & - &   -   &   -   \\
$(\nu,0,\nu,\nu) \Rightarrow (0,0,\nu,0)$ & $(-)1$ & $(-)1$  & - & $(-)1$  \\
$(\nu,\nu,0,0)   \Rightarrow (\nu,0,0,\nu)$ & $(-)1$ & - & $(-)1$  &   -   \\
$(\nu,\nu,0,\nu) \Rightarrow (0,\nu,\nu,\nu)$ & $(-)1$ & $(-)1$ & $(-)1$ & $(-)1$ \\
$(\nu,\nu,\nu,0) \Rightarrow (0,0,0,\nu)$ & $(-)1$ & - &   -   & $(-)1$  \\
$(\nu,\nu,\nu,\nu) \Rightarrow (\nu,\nu,\nu,\nu)$ & $(-)1$ & $(-)1$ & - & - \\
\hline
\end{tabular}
\end{center}
\caption{XOR propagation in the round function with conditions on the subkeys.}
\end{table}
%

The propagation of a given XOR for multiple rounds can be easily studied
by letting the output XOR be the input XOR to the following round. The 
conditions on the subkeys can be read in Table 4.

An example for the plaintext XOR $(0,\nu,0,\nu)$ is given in Table 5.
It can be seen that for keys with only nonzero bits on positions 26--40, 
72--76 and 108--122 the output XOR must be equal to $(0,\nu,\nu,0)$. This 
is the largest class we found, comprising a total of $2^{35}$ keys. 
Membership can be checked by performing 2 encryptions 
where the plaintexts have a chosen difference and observing the difference 
in the ciphertexts. A similar table can be constructed for any input XOR 
consisting of $\nu$ and 0.
%
\begin{table}
\begin{center}
\begin{tabular}{lccc}\hline
round & \makebox[25mm]{input xor} & \makebox[15mm]{$Z_4$} & 
\makebox[15mm]{$Z_5$} \\ \hline
1     & $(0,\nu,0,\nu)$  &  48--62 &    -   \\
2     & $(0,0,\nu,\nu)$  &  41--55 & 57--71 \\
3     & $(0,\nu,\nu,0)$  &     -   & 50--64 \\
4     & $(0,\nu,0,\nu)$  &   2--16 &    -   \\
5     & $(0,0,\nu,\nu)$  & 123--9 & 11--25 \\
6     & $(0,\nu,\nu,0)$  &     -   &  4--18 \\
7     & $(0,\nu,0,\nu)$  &  84--98 &    -   \\
8     & $(0,0,\nu,\nu)$  &  77--91 & 93--107\\
9     & $(0,\nu,\nu,0)$  &     -   &    -   \\ \hline
\end{tabular}
\end{center}
\caption{Propagation of plaintext XOR $(0,\nu,0,\nu)$ in IDEA.}
\end{table}
%
\section{Expanding Classes of Weak Keys}
%
Classes of weak keys can sometimes be significantly expanded at the cost of 
some more effort in the checking for membership. Omitting in Table 5 the 
conditions for the subkeys of round 8 gives rise to the class of $2^{51}$ 
keys with nonzero bits on positions 26--40, 72--83 and 99--122. We will show 
that both checking for membership and calculation of the specific key can be 
performed efficiently.
%
\subsection{The Membership Test}
%
The input XOR of round 8 is equal to the output XOR of round 7 and 
is guaranteed to be equal to $(0,0,\nu,\nu)$ by the conditions on the subkeys
of the first 7 rounds. Using the fact that $Z_3^{(9)}$,
consisting of global key bits 54--69 is 0000 for these keys it can easily be 
derived that
\begin{equation}
Y'_3 \oplus \nu = 
({Z_1^{(9)}}^{-1} \cdot Y_1^*) \oplus ({Z_1^{(9)}}^{-1} \cdot Y_1) \enspace .
\end{equation}
This can be verified by inspecting Fig.2.
In (4) only $Z_1^{(9)}$ is unknown. This subkey consists of global
key bits 22--37. For the given class only the 12 LSB may differ from 0. If the
global key does not belong to the class of weak keys, the probability that
(4) has a solution is $1/{16}$. Additional encryptions can be performed to
eliminate these solutions. Every pair of encryptions yields an equation 
for $Z_1^{(9)}$ similar to (4). 
%
\begin{figure}
\begin{center}
\begin{picture}(360,330)(0,-20)

\begin{thicklines}

\put(20,320){\makebox(0,0){\framebox(24,12){0}}}
\put(100,320){\makebox(0,0){\framebox(24,12){0}}}
\put(260,320){\makebox(0,0){\framebox(24,12){$\nu$}}}
\put(340,320){\makebox(0,0){\framebox(24,12){$\nu$}}}

\put(40,310){\vector(0,-1){25}}
\put(80,310){\vector(0,-1){25}}
\put(280,310){\vector(0,-1){25}}
\put(320,310){\vector(0,-1){25}}

\put(0,280){\makebox(0,0){$Z_1^{(8)}$}}
\put(10,280){\vector(1,0){25}}
\put(40,280){\makebox(0,0){$\bigodot$}}
\put(80,280){\makebox(0,0){\bigsplus}}
\put(110,280){\vector(-1,0){25}}
\put(120,280){\makebox(0,0){$Z_2^{(8)}$}}
\put(240,280){\makebox(0,0){$Z_3^{(8)}$}}
\put(250,280){\vector(1,0){25}}
\put(280,280){\makebox(0,0){\bigsplus}}
\put(320,280){\makebox(0,0){$\bigodot$}}
\put(350,280){\vector(-1,0){25}}
\put(360,280){\makebox(0,0){$Z_4^{(8)}$}}

\put(40,275){\vector(0,-1){170}}
\put(80,275){\vector(0,-1){190}}
\put(280,275){\vector(0,-1){170}}
\put(320,275){\vector(0,-1){190}}

\put(20,260){\makebox(0,0){\framebox(24,12){0}}}
\put(100,260){\makebox(0,0){\framebox(24,12){0}}}
\put(260,260){\makebox(0,0){\framebox(24,12){$\nu$}}}
\put(340,260){\makebox(0,0){\framebox(24,12){$K$}}}

\put(40,240){\makebox(0,0){$\bullet$}}
\put(40,240){\vector(1,0){115}}
\put(160,240){\makebox(0,0){$\bigoplus$}}
\put(280,240){\makebox(0,0){$\bullet$}}
\put(280,240){\vector(-1,0){115}}

\put(160,235){\vector(0,-1){50}}

\put(80,220){\makebox(0,0){$\bullet$}}
\put(80,220){\vector(1,0){115}}
\put(200,220){\makebox(0,0){$\bigoplus$}}
\put(320,220){\makebox(0,0){$\bullet$}}
\put(320,220){\vector(-1,0){115}}

\put(200,215){\vector(0,-1){30}}

\put(140,200){\makebox(0,0){\framebox(24,12){$\nu$}}}
\put(220,200){\makebox(0,0){\framebox(24,12){$K$}}}

\put(120,180){\makebox(0,0){$Z_5^{(8)}$}}
\put(130,180){\vector(1,0){25}}
\put(160,180){\makebox(0,0){$\bigodot$}}
\put(165,180){\vector(1,0){30}}
\put(200,180){\makebox(0,0){\bigsplus}}

\put(160,175){\vector(0,-1){30}}
\put(200,175){\vector(0,-1){30}}

\put(160,140){\makebox(0,0){\bigsplus}}
\put(195,140){\vector(-1,0){30}}
\put(200,140){\makebox(0,0){$\bigodot$}}
\put(230,140){\vector(-1,0){25}}
\put(240,140){\makebox(0,0){$Z_6^{(8)}$}}

\put(140,120){\makebox(0,0){\framebox(24,12){$M$}}}
\put(220,120){\makebox(0,0){\framebox(24,12){$L$}}}

\put(160,135){\line(0,-1){55}}
\put(200,135){\line(0,-1){35}}

\put(40,100){\makebox(0,0){$\bigoplus$}}
\put(200,100){\vector(-1,0){155}}
\put(200,100){\makebox(0,0){$\bullet$}}
\put(200,100){\vector(1,0){75}}
\put(280,100){\makebox(0,0){$\bigoplus$}}

\put(40,95){\vector(0,-1){75}}
\put(280,95){\vector(0,-1){100}}

\put(80,80){\makebox(0,0){$\bigoplus$}}
\put(160,80){\vector(-1,0){75}}
\put(160,80){\makebox(0,0){$\bullet$}}
\put(160,80){\vector(1,0){155}}
\put(320,80){\makebox(0,0){$\bigoplus$}}

\put(80,75){\vector(0,-1){55}}
\put(320,75){\vector(0,-1){55}}

\put(20,35){\makebox(0,0){\framebox(24,12){$L$}}}
\put(100,35){\makebox(0,0){\framebox(24,12){$M$}}}
\put(256,35){\makebox(0,0){\framebox(32,12){$L \oplus \nu$}}}
\put(348,35){\makebox(0,0){\framebox(40,12){$M \oplus K$}}}

\put(0,15){\makebox(0,0){$Z_1^{(9)}$}}
\put(10,15){\vector(1,0){25}}
\put(40,15){\makebox(0,0){$\bigodot$}}
\put(80,15){\makebox(0,0){\bigsplus}}
\put(110,15){\vector(-1,0){25}}
\put(120,15){\makebox(0,0){$Z_2^{(9)}$}}
\put(320,15){\makebox(0,0){$\bigodot$}}
\put(350,15){\vector(-1,0){25}}
\put(360,15){\makebox(0,0){$Z_4^{(9)}$}}

\put(40,10){\vector(0,-1){15}}
\put(80,10){\vector(0,-1){15}}
\put(320,10){\vector(0,-1){15}}

\put(40,-15){\makebox(0,0){$Y_1$}}
\put(80,-15){\makebox(0,0){$Y_2$}}
\put(280,-15){\makebox(0,0){$Y_3$}}
\put(320,-15){\makebox(0,0){$Y_4$}}

\end{thicklines}

\end{picture}
\end{center}
\caption{XOR propagation of $X' = (0,\nu,0,\nu)$ through the last round of 
IDEA for keys with only nonzero bits on positions 26--40, 72--83 and 99--122. 
The XORs are indicated in boxes.}
\end{figure}
%
\subsection{The Determination of the Key}
%
The value of the 12 unknown bits of $Z_1^{(9)}$ are already determined by the
membership test. The following step is the determination of the 3 unknown bits
of $Z_2^{(9)}$, the 12 unknown bits of $Z_4^{(9)}$ and the 7 unknown bits of 
$Z_4^{(8)}$. A consistency check can be executed on these bits in the following
way. Suppose $Z_2^{(9)} \mbox{ and } Z_4^{(9)}$ are known. In this case it is 
possible to calculate the difference that is denoted by $K$ in Fig.2.
For this value $K$ there must be a vector $A$ (with MSB 0) such that
%
\begin{equation}
K = (Z_4^{(8)} \cdot A ) \oplus (Z_4^{(8)} \cdot (A \oplus \nu ))
  = (Z_4^{(8)} \cdot A ) \oplus ((Z_4^{(8)} \cdot A) + (Z_4^{(8)} \cdot 2^{15}))
\end{equation}
%
For a given vector $K$ it is easy to find the possible values of $Z_4^{(8)}$.
Only values of $Z_4^{(8)}$ with the 9 LSB equal to 0 are valid. This information
can be calculated in advance for every value of $K$ and stored in an array of 
$2^{16}$ lists. The average number of possible $Z_4^{(8)}$ per $K$ value 
turns out to be smaller than 1. Through this table, the observed value of $K$ 
specifies a set of possible $Z_4^{(8)}$ values. If the set is empty, the chosen
values for $Z_2^{(9)} \mbox{ and } Z_4^{(9)}$ must have been wrong. If the set
is not empty, the $K$ value resulting from another pair of encryptions 
(with input XOR at round 8 equal to $(0,0,\nu,\nu)$ ) can be observed. The 
correct value for $Z_4^{(8)}$ must be in the list for both observed values of 
$K$. This can be repeated until there is no value for $Z_4^{(8)}$ left. 
The correct values for $Z_2^{(9)} \mbox{ and } Z_4^{(9)}$ are
found if there is a value for $Z_4^{(8)}$ that is consistent for all the
(say a maximum of 8) encryption pairs. 
Now 34 bits are fixed. The remaining 17 bits can easily be
found by exhaustively trying all remaining $2^{17}$ possibilities and 
comparing it with any plaintext-ciphertext pair obtained during the attack.

The complete workload of the key determination is 16 chosen 
plaintext-difference encryptions, about $2^{15}$ modular additions, 
multiplications and table-lookups and $2^{17}$ key search encryptions.
%
\section{A Modified IDEA Without Weak Keys}
%
In the present specification of IDEA the conditions for weak multiplicative 
round keys are converted to the condition that global key bits must be 0. 
In Table 3 and 5 it can be seen that many global key bits appear more than 
once in the conditions. 

Now let $\hat{Z}^{(r)}_i = \alpha \oplus Z^{(r)}_i$ with $\alpha$ a fixed 
nonzero binary vector. If in IDEA the subkeys $Z^{(r)}_i$ are replaced by 
$\hat{Z}^{(r)}_i$, the conditions for weak multiplicative keys are 
converted to the condition that some global key bits must be 0 and some
must be 1. The vector $\alpha$ must be chosen such that for all potential 
multiple-round linear factors and characteristics, the conditions on the 
subkeys give conflicting conditions on global key bits. Because of the
large overlap between subkeys, the exact value of $\alpha$ is not critical.
For instance, for $\alpha =$ 0DAE (HEX) no weak keys were found.
%
\section{Conclusions}
%
Large classes of weak keys have been found for the block cipher IDEA. 
These keys are weak in the sense that it takes only a very small amount of
effort to detect their use. It is possible to eliminate the weak key problem
by slightly modifying the key schedule of IDEA.
%
\begin{thebibliography}{15}
\bibitem[1]{pes}X. Lai and J.L. Massey, A Proposal for a New Block Encryption
Standard, {\em Advances in Cryptology--Eurocrypt' 90},
Springer-Verlag, Berlin 1991, pp. 389--404.
\bibitem[2]{ipes}X. Lai, J.L. Massey and S. Murphy, Markov Ciphers and 
Differential Cryptanalysis, {\em Advances in Cryptology--Eurocrypt' 91},
Springer-Verlag, Berlin 1991, pp. 17--38. 
\bibitem[3]{biham}E. Biham and A. Shamir, Differential Cryptanalysis of
DES-like Cryptosystems, {\em Journal of Cryptology\/}, Springer-Verlag,
Vol. 4, No. 1, pp. 3--72, 1991.
\bibitem[4]{chaum}D. Chaum, J.-H. Evertse, Cryptanalysis of DES with a 
Reduced Number of Rounds, Sequences of Linear Factors in Block Ciphers,
{\em Advances in Cryptology, Proceedings of Crypto 85}, pp. 192--211, 1985. 
\end{thebibliography}
\end{document}

