From 4643f89a9addf5c66e64ca7dbb9145298531208b Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Thu, 25 May 2000 19:46:22 +0000
Subject: [PATCH] Improve analysis section.

---
 storin.tex | 123 +++++++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 95 insertions(+), 28 deletions(-)

diff --git a/storin.tex b/storin.tex
index d9cb84c..cd36172 100644
--- a/storin.tex
+++ b/storin.tex
@@ -1,6 +1,6 @@
 %%% -*-latex-*-
 %%%
-%%% $Id: storin.tex,v 1.2 2000/05/21 21:43:26 mdw Exp $
+%%% $Id: storin.tex,v 1.3 2000/05/25 19:46:22 mdw Exp $
 %%%
 %%% Definition of the cipher
 %%%
@@ -10,6 +10,9 @@
 %%%----- Revision history ---------------------------------------------------
 %%%
 %%% $Log: storin.tex,v $
+%%% Revision 1.3  2000/05/25 19:46:22  mdw
+%%% Improve analysis section.
+%%%
 %%% Revision 1.2  2000/05/21 21:43:26  mdw
 %%% Fix a couple of typos.
 %%%
@@ -34,6 +37,8 @@
 \def\xor{\oplus}
 \def\seq#1{{\langle #1 \rangle}}
 
+\def\hex#1{\texttt{#1}_{16}}
+
 \sloppy
 
 \title{Storin: A block cipher for digital signal processors}
@@ -234,9 +239,11 @@ then encrypted again using the new subkeys.  The next four subkey words are
 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 accept user keys up to 36 words (864 bits) long.
-It is unrealistic, however, to expect this much strength from the cipher.  We
-recommend against using keys longer than 5 words (120 bits).
+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).
 
 
 \subsection{Encryption}
@@ -342,18 +349,18 @@ $C^{-1}(\mathbf{x}_0) = K^{-1}_8(\mathbf{x}_8)$.
 The matrix $\mathbf{M}$ and its inverse $\mathbf{M}^{-1}$ are:
 \begin{eqnarray*}[rl]
   \mathbf{M} = &
-  \begin{pmatrix}[[>{\hbox\bgroup\ttfamily}c<{\egroup}]
-    f7a413 & 54bd81 & 447550 & ff4449 \\
-    f31e87 & d85388 & de32cb & 40e3d7 \\
-    d9db1d & 551b45 & e9d19f & e443de \\
-    4b949a & 4d435d & ef0a17 & b784e1
+  \begin{pmatrix}
+    \hex{f7a413} & \hex{54bd81} & \hex{447550} & \hex{ff4449} \\
+    \hex{f31e87} & \hex{d85388} & \hex{de32cb} & \hex{40e3d7} \\
+    \hex{d9db1d} & \hex{551b45} & \hex{e9d19f} & \hex{e443de} \\
+    \hex{4b949a} & \hex{4d435d} & \hex{ef0a17} & \hex{b784e1}
   \end{pmatrix} \\
   \mathbf{M}^{-1} = &
-  \begin{pmatrix}[[>{\hbox\bgroup\ttfamily}c<{\egroup}]
-    17391b & fafb4b & a66823 & f2efb6 \\
-    13e0e5 & 2ed5e4 & b2cfff & d9cdb5 \\
-    2af462 & 33826d & de66a1 & eb6c85 \\
-    c2f423 & e904a3 & e772d8 & d791f1
+  \begin{pmatrix}
+    \hex{17391b} & \hex{fafb4b} & \hex{a66823} & \hex{f2efb6} \\
+    \hex{13e0e5} & \hex{2ed5e4} & \hex{b2cfff} & \hex{d9cdb5} \\
+    \hex{2af462} & \hex{33826d} & \hex{de66a1} & \hex{eb6c85} \\
+    \hex{c2f423} & \hex{e904a3} & \hex{e772d8} & \hex{d791f1}
   \end{pmatrix}
 \end{eqnarray*}
 
@@ -399,8 +406,7 @@ Consider a vector $\mathbf{x}$ and its product with the matrix $\mathbf{M}
 entry $j$ in the product depends on whether the entry in row $j$, column $i$
 of $\mathbf{M}$ is even.  Criterion 2 ensures the following:
 \begin{itemize}
-\item A top-bit change in a single word or three words affects three words in
-  the output.
+\item A top-bit change in a single word affects three words in the output.
 \item A top-bit change in two words affects two words in the output.
 \end{itemize}
 
@@ -426,22 +432,54 @@ achieved after three rounds of Storin.
 \subsection{Key schedule notes}
 
 The key schedule is intended to be adequate for bulk encryption; it doesn't
-provide good key agility, and isn't intended to.  The key schedule accepts an
-arbitrary number of 24-bit words, although expecting 864 bits of security
-from the cipher is not realistic.  The suggested maximum of 5 words (120
-bits) seems more sensible.  This maximum can be raised easily when our
-understanding of the cipher increases our confidence in it.
+provide good key agility, and isn't intended to.  The key schedule accepts up
+to 28 words of user key, although expecting 672 bits of security from the
+cipher is not realistic.  The suggested maximum of 5 words (120 bits) seems
+more sensible.  This maximum can be raised easily when our understanding of
+the cipher increases our confidence in it.
 
 The key schedule is strongly reminiscent of Blowfish \cite{blowfish}.  Use of
 existing components of the cipher, such as the matrix multiplication and the
 cipher itself, help reduce the amount of code required in the implementation.
 
-There is an interesting feature of the key schedule: the output of the first
+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.
+the matrix and linear transformation.  See figure~\ref{fig:bfkeysched}.
 
+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.
+
+\begin{figure}
+\centering
+\leavevmode
+\begin{xy}
+  \xycompile{
+    \POS 0; <0.7cm, 0cm>:
+    \POS (0, 0) ="o" +(3, 0) ="w"
+    \ar "o" *+{P[0]}; p-(0, 1) *{\xor} ="x"
+    \ar "x" -(1, 0) *+[l]{P[0]}; "x"
+    \ar@{-} "x"; p-(0, 2) ="as"
+    \ar "w" *+{P[1]}; p-(0, 2) *{\xor} ="x"
+    \ar "o"-(0, 2); "x" |-*+[F]{F}
+    \ar@{-} "x"; p-(0, 1) ="bs"
+    \ar@{-} "as"; "bs"-(0, 1) ="w"
+    \ar@{-} "bs"; "as"-(0, 1) ="o"
+    \ar "o"; p-(0, 1) *+{P[1] \xor F(0)} ="x"
+    \ar "x"; p-(0, 1) *{\xor} ="x"
+    \ar "x" -(1, 0) *+[l]{P[1]}; "x"
+    \ar "x"; p-(0, 2) *+{F(0)}
+    \ar "w"; p-(0, 1) *+{0} ="x"
+    \ar "x"; p-(0, 2) *{\xor} ="x"
+    \ar "o"-(0, 3); "x" |-*+[F]{F}
+    \ar "x"; p-(0, 1) *+{F^2(0)}}
+\end{xy}
+\caption{Blowfish key schedule: $P[2]$ and $P[3]$ don't depend on $P[0]$ and
+  $P[1]$.}
+\label{fig:bfkeysched}
+\end{figure}
 
 \subsection{Attacking Storin}
 
@@ -453,6 +491,30 @@ 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.
 
+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) \]
+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) \]
+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}) \]
+This characteristic is non-iterative, and can't be extended to more rounds.
+
+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.
+
 One possible avenue of attack worth exploring is to attempt to cause zero
 words to be input into the first-round matrix by choosing plaintext words
 identical to subkey words for the first round.  Causing $n$ matrix input
@@ -470,11 +532,16 @@ received with interest.
 
 
 \begin{thebibliography}{99}
-\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',
-    \textit{Dr Dobb's Journal}, vol. 19 no. 4, April 1994, pp. 38--40}
+\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,
+  Hartung-Gorre Verlag Konstanz, Technische Hochschule (Zurich), 1992
+\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',
+  sci.crypt article, message-id
+  \texttt{<slrn8iqhaq.872.mdw@mull.ncipher.com>}
 \end{thebibliography}
 
 %%%----- That's all, folks --------------------------------------------------
-- 
2.11.0

