X-Git-Url: https://git.distorted.org.uk/~mdw/storin/blobdiff_plain/4643f89a9addf5c66e64ca7dbb9145298531208b..cb946298dbe944c543ae38fe2c8be46ea44732e2:/storin.tex

diff --git a/storin.tex b/storin.tex
index cd36172..1115d24 100644
--- a/storin.tex
+++ b/storin.tex
@@ -1,6 +1,6 @@
 %%% -*-latex-*-
 %%%
-%%% $Id: storin.tex,v 1.3 2000/05/25 19:46:22 mdw Exp $
+%%% $Id: storin.tex,v 1.5 2000/07/02 15:22:34 mdw Exp $
 %%%
 %%% Definition of the cipher
 %%%
@@ -10,6 +10,12 @@
 %%%----- 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.
+%%%
 %%% Revision 1.3  2000/05/25 19:46:22  mdw
 %%% Improve analysis section.
 %%%
@@ -240,10 +246,11 @@ replaced with the ciphertext, and the process continues, nine times in all,
 until all of the subkey words have been replaced.
 
 The Storin key schedule can in theory accept user keys up to 36 words (864
-bits) long.  However, there are possible security problems with keys shorter
-than 28 words (672 bits).  We believe that it's unrealistic to expect this
-much strength from the cipher and recommend against using keys longer than 5
-words (120 bits).
+bits) long.  However, there are known problems with keys longer than 28 words
+(672 bits), and these large keys are forbidden.  We expect that with long
+keys, attacks will be found which are more efficient than an exhaustive
+search of the keyspace; we therefore (conservatively) recommend 5 word
+(120-bit) keys as a practical maximum.
 
 
 \subsection{Encryption}
@@ -443,11 +450,12 @@ existing components of the cipher, such as the matrix multiplication and the
 cipher itself, help reduce the amount of code required in the implementation.
 
 The restriction of the key schedule to 28 words is due to an interesting
-property, also shared by Blowfish \cite{blowfish}: the output of the first
-round of the second encryption is zero.  To see why this is so, it is enough
-to note that the first round key has just been set equal to what is now the
-plaintext; the result of the key mixing stage is zero, which is unaffected by
-the matrix and linear transformation.  See figure~\ref{fig:bfkeysched}.
+property, also shared by Blowfish \cite{blowfish} (see
+figure~\ref{fig:bfkeysched}): the output of the first round of the second
+encryption doesn't depend on the previous round.  To see why this is so, it
+is enough to note that the first round key has just been set equal to what is
+now the plaintext; the result of the key mixing stage is zero, which is
+unaffected by the matrix and linear transformation.
 
 A limit of 28 words is chosen to ensure that the round-1 key affects the
 round-2 key in a part of the cipher earlier than the postwhitening stage.
@@ -483,34 +491,95 @@ round-2 key in a part of the cipher earlier than the postwhitening stage.
 
 \subsection{Attacking Storin}
 
-A brief\footnote{About three days' worth on a 300MHz Pentium II.}
-computerized analysis of the matrix multiplication failed to turn up any
-high-probability differential characteristics.  While an exhaustive search
-was clearly not possible, the program tested all differentials of Hamming
-weight 5 or less, and then random differentials, applying each to a suite of
-$2^{13}$ different 96-bit inputs chosen at random.  No output difference was
-noted more than once.
+\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.
@@ -532,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}
