From cb946298dbe944c543ae38fe2c8be46ea44732e2 Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Sun, 2 Jul 2000 15:22:34 +0000
Subject: [PATCH] Overhaul of differential cryptanalysis, including a new
 attack.

---
 storin.tex | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 98 insertions(+), 18 deletions(-)

diff --git a/storin.tex b/storin.tex
index 313b534..1115d24 100644
--- a/storin.tex
+++ b/storin.tex
@@ -1,6 +1,6 @@
 %%% -*-latex-*-
 %%%
-%%% $Id: storin.tex,v 1.4 2000/05/28 00:39:32 mdw Exp $
+%%% $Id: storin.tex,v 1.5 2000/07/02 15:22:34 mdw Exp $
 %%%
 %%% Definition of the cipher
 %%%
@@ -10,6 +10,9 @@
 %%%----- Revision history ---------------------------------------------------
 %%%
 %%% $Log: storin.tex,v $
+%%% Revision 1.5  2000/07/02 15:22:34  mdw
+%%% Overhaul of differential cryptanalysis, including a new attack.
+%%%
 %%% Revision 1.4  2000/05/28 00:39:32  mdw
 %%% Fix some errors.
 %%%
@@ -488,26 +491,95 @@ round-2 key in a part of the cipher earlier than the postwhitening stage.
 
 \subsection{Attacking Storin}
 
+\subsubsection{Differential cryptanalysis}
+
 There is a two-round truncated differential \cite{storin-tdiff}, which can be
 used to break Storin reduced to only 2 rounds.  The differential
-\[ (\hex{800000}, \hex{800000}, \hex{800000}, 0) \to
-      (0, 0, \hex{800000}, 0) \]
+\[ \begin{pmatrix}
+     1 \lsl 23 \\ 1 \lsl 23 \\ 1 \lsl 23 \\ 0
+   \end{pmatrix} \to
+   \begin{pmatrix}
+     0 \\ 0 \\ 1 \lsl 23 \\ 0
+   \end{pmatrix}
+\]
 holds with probability 1 through the matrix multiplication.
 Differentials in the linear transform are easy to find; for example:
-\[ (0, 0, \hex{800000}, 0) \to (0, 0, \hex{800800}, 0) \]
+\[ \begin{pmatrix}
+     0 \\ 0 \\ 1 \lsl 23 \\ 0
+   \end{pmatrix} \to
+   \begin{pmatrix}
+     0 \\ 0 \\ (1 \lsl 23) \xor (1 \lsl 11) \\ 0
+   \end{pmatrix}
+\]
 We can continue through the second round's matrix multiplication with a
 truncated differential, again with probability 1:
-\[ (0, 0, \hex{800800}, 0) \to
-      (\hex{???000}, \hex{???800}, \hex{???800}, \hex{???800}) \]
-The following linear transform can be commuted with the postwhitening by
-applying a trivial reversible transformation to the postwhitening keys, and
-we can apply it to the ciphertext.  If we do this, we can combine the
-differentials above to construct a probability-1 characteristic for a 2-round
-variant of Storin:
-\[ (\hex{800000}, \hex{800000}, \hex{800000}, 0) \to
-      (\hex{???000}, \hex{???800}, \hex{???800}, \hex{???800}) \]
+\[ \begin{pmatrix}
+     0 \\ 0 \\ (1 \lsl 23) \xor (1 \lsl 11) \\ 0
+   \end{pmatrix} \to
+   \begin{pmatrix}
+     \delta_0 \lsl 12 \\
+     (\delta_1 \lsl 12) \xor (1 \lsl 11) \\
+     (\delta_2 \lsl 12) \xor (1 \lsl 11) \\
+     (\delta_3 \lsl 12) \xor (1 \lsl 11) \\
+   \end{pmatrix}
+\]
+where the $\delta_i$ are unknown 12-bit values.  Applying the linear
+transformation to this output difference gives us
+\[ \begin{pmatrix}
+     \delta_0 \lsl 12 \\
+     (\delta_1 \lsl 12) \xor (1 \lsl 11) \\
+     (\delta_2 \lsl 12) \xor (1 \lsl 11) \\
+     (\delta_3 \lsl 12) \xor (1 \lsl 11) \\
+   \end{pmatrix} \to
+   \begin{pmatrix}
+     (\delta_0 \lsl 12) \xor \delta_0 \\
+     (\delta_1 \lsl 12) \xor \delta_1 \xor (1 \lsl 11) \\
+     (\delta_2 \lsl 12) \xor \delta_2 \xor (1 \lsl 11) \\
+     (\delta_3 \lsl 12) \xor \delta_3 \xor (1 \lsl 11) \\
+   \end{pmatrix}
+\]
+A subsequent key-mixing or postwhitening stage won't affect the difference.
+We can therefore combine the differentials above to construct a probability-1
+truncated differential for a 2-round variant of Storin:
+\[ \begin{pmatrix}
+     1 \lsl 23 \\ 1 \lsl 23 \\ 1 \lsl 23 \\ 0
+   \end{pmatrix} \to
+   \begin{pmatrix}
+     (\delta_0 \lsl 12) \xor \delta_0 \\
+     (\delta_1 \lsl 12) \xor \delta_1 \xor (1 \lsl 11) \\
+     (\delta_2 \lsl 12) \xor \delta_2 \xor (1 \lsl 11) \\
+     (\delta_3 \lsl 12) \xor \delta_3 \xor (1 \lsl 11) \\
+   \end{pmatrix}
+\]
 This characteristic is non-iterative, and can't be extended to more rounds.
 
+The differential can be converted into a key-recovery attack against $n$
+rounds fairly easily, by obtaining the ciphertext for an appropriate
+plaintext pair and guessing the $n - 2$ round keys, testing the guesses by
+working backwards and finding out whether the expected output difference is
+visible.  The attack requires a pair of chosen plaintexts, and
+$O(2^{96(n - 2)})$ work.  It is only more efficient than exhaustive search
+when the key is longer than $96(n - 2)$ bits.
+
+This attack can be improved.  Consider a 3-round variant of Storin, where the
+objective is to discover the postwhitening keys.  The postwhitening stage can
+be commuted with the linear transform simply by applying the transform to the
+postwhitening keys.  We do this, and guess the least significant 12 bits of
+each of the (transformed) postwhitening key words.  Working through the
+matrix multiplication mod $2^{12}$ rather than mod $2^{24}$ then gives us the
+12 least significant bits of the state words on input to the matrix.  Further
+key bits can then be guessed and tested, four at a time, to recover the
+remaining postwhitening key bits, by ensuring that the differences in the
+more significant bits of the third round matrix input obey the characteristic
+described above.  This requires only about $2^{48}$ work, and may be extended
+to further rounds by exhaustively searching for the extra round keys.
+
+This attack can break Storin with $n$ rounds ($n \ge 3$) with minimal chosen
+plaintext and $O(2^{48 + 96(n - 3)})$ work.  This is the best attack known
+against Storin.
+
+\subsubsection{Other attacks}
+
 In \cite{storin-collide}, Matthew Fisher speculates on breaking 2 rounds of
 Storin by forcing collisions in the matrix multiplication outputs.  This
 attack doesn't extend to more than two rounds either.
@@ -529,14 +601,22 @@ received with interest.
 
 
 \begin{thebibliography}{99}
-\bibitem{storin-collide} M.  Fisher, `Yet another block cipher: Storin',
+\bibitem{storin-collide}
+  M.  Fisher,
+  `Yet another block cipher: Storin',
   sci.crypt article, message-id \texttt{<8gjctn\$9ct\$1@nnrp1.deja.com>}
-\bibitem{idea} X. Lai, `On the Design and Security of Block Ciphers', ETH
-  Series in Informatics Processing, J. L. Massey (editor), vol. 1,
+\bibitem{idea}
+  X. Lai,
+  `On the Design and Security of Block Ciphers',
+  ETH Series in Informatics Processing, J. L. Massey (editor), vol. 1,
   Hartung-Gorre Verlag Konstanz, Technische Hochschule (Zurich), 1992
-\bibitem{blowfish} B. Schneier, `The Blowfish Encryption Algorithm',
+\bibitem{blowfish}
+  B. Schneier,
+  `The Blowfish Encryption Algorithm',
   \textit{Dr Dobb's Journal}, vol. 19 no. 4, April 1994, pp. 38--40
-\bibitem{storin-tdiff} M. D. Wooding, `Yet another block cipher: Storin',
+\bibitem{storin-tdiff}
+  M. D. Wooding,
+  `Yet another block cipher: Storin',
   sci.crypt article, message-id
   \texttt{<slrn8iqhaq.872.mdw@mull.ncipher.com>}
 \end{thebibliography}
-- 
2.11.0

