X-Git-Url: https://git.distorted.org.uk/~mdw/storin/blobdiff_plain/e6e0e332972586b443c9ae3d031757f6778fd263..HEAD:/storin.tex

diff --git a/storin.tex b/storin.tex
index 3b66411..fdb1704 100644
--- a/storin.tex
+++ b/storin.tex
@@ -1,6 +1,6 @@
 %%% -*-latex-*-
 %%%
-%%% $Id: storin.tex,v 1.1 2000/05/21 11:28:30 mdw Exp $
+%%% $Id$
 %%%
 %%% Definition of the cipher
 %%%
@@ -10,6 +10,24 @@
 %%%----- Revision history ---------------------------------------------------
 %%%
 %%% $Log: storin.tex,v $
+%%% Revision 1.7  2001/03/11 23:46:56  mdw
+%%% Fixing to BibTeX stuff.
+%%%
+%%% Revision 1.6  2001/03/11 23:22:53  mdw
+%%% Use BibTeX for the paper bibliography.
+%%%
+%%% 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.
+%%%
+%%% Revision 1.2  2000/05/21 21:43:26  mdw
+%%% Fix a couple of typos.
+%%%
 %%% Revision 1.1  2000/05/21 11:28:30  mdw
 %%% Initial check-in.
 %%%
@@ -22,6 +40,7 @@
 \usepackage{mathenv}
 \usepackage{amsfonts}
 \usepackage{mdwmath}
+\usepackage{url}
 \usepackage[all, dvips]{xy}
 
 \def\ror{\mathbin{>\!\!>\!\!>}}
@@ -31,6 +50,9 @@
 \def\xor{\oplus}
 \def\seq#1{{\langle #1 \rangle}}
 
+\def\hex#1{\texttt{#1}_{16}}
+\let\msgid=\url
+
 \sloppy
 
 \title{Storin: A block cipher for digital signal processors}
@@ -81,13 +103,13 @@
   \ar `r "d"+(0, 0.5); p+(1, 0) "x" \ar "x"; "d"%
 }
 
-\def\figstart{%
+\def\figstart#1{%
   \POS 0;<1cm,0cm>:%
   \turnradius{4pt}%
-  \ar @{-} (0, 0) *+{a}; p-(0, 0.5) ="a"
-  \ar @{-} (2, 0) *+{b}; p-(0, 0.5) ="b"
-  \ar @{-} (4, 0) *+{c}; p-(0, 0.5) ="c"
-  \ar @{-} (6, 0) *+{d}; p-(0, 0.5) ="d"
+  \ar @{-} (0, 0) *+{a#1}; p-(0, 0.5) ="a"
+  \ar @{-} (2, 0) *+{b#1}; p-(0, 0.5) ="b"
+  \ar @{-} (4, 0) *+{c#1}; p-(0, 0.5) ="c"
+  \ar @{-} (6, 0) *+{d#1}; p-(0, 0.5) ="d"
 }
 
 \def\figround#1#2#3#4#5{%
@@ -123,14 +145,14 @@
   \ar @{--} "d"; "d"-(0, 2) ="d"
 }
 
-\def\figwhite#1#2#3#4{%
+\def\figwhite#1#2#3#4#5{%
   \ar @{.} "a"-(0.5, 0); p+(8, 0)
   \POS "a"+(8, -1)*[r]\txt{Postwhitening}
   \figkeymix{#1}{#2}{#3}{#4}
-  \ar "a"; p-(0, 1) *+{a'}
-  \ar "b"; p-(0, 1) *+{c'}
-  \ar "c"; p-(0, 1) *+{b'}
-  \ar "d"; p-(0, 1) *+{d'}
+  \ar "a"; p-(0, 1) *+{a#5}
+  \ar "b"; p-(0, 1) *+{b#5}
+  \ar "c"; p-(0, 1) *+{c#5}
+  \ar "d"; p-(0, 1) *+{d#5}
 }
 
 \begin{document}
@@ -183,11 +205,11 @@ The cipher structure is shown diagrammatically in figure~\ref{fig:cipher}.
 \leavevmode
 \begin{xy}
   \xycompile{
-    \figstart
+    \figstart{}
     \figround{0}{1}{2}{3}{Round 1}
     \figround{4}{5}{6}{7}{Round 2}
     \figgap
-    \figwhite{32}{33}{34}{35}}
+    \figwhite{32}{33}{34}{35}{'}}
 \end{xy}
 \caption{The Storin encryption function}
 \label{fig:cipher}
@@ -207,11 +229,11 @@ diagrammatically in figure~\ref{fig:decipher}.
 \leavevmode
 \begin{xy}
   \xycompile{
-    \figstart
+    \figstart{'}
     \figiround{32}{33}{34}{35}{Round 1}
     \figiround{28}{29}{30}{31}{Round 2}
     \figgap
-    \figwhite{0}{1}{2}{3}}
+    \figwhite{0}{1}{2}{3}{}}
 \end{xy}
 \caption{The Storin decryption function}
 \label{fig:decipher}
@@ -220,20 +242,24 @@ diagrammatically in figure~\ref{fig:decipher}.
 The key schedule is designed to be simple and to reuse the cipher components
 already available.  Given a user key, which is a sequence of one or more
 24-bit words, it produces the 36 subkey words required by the cipher.  The
-key schedule is very similar to Blowfish \cite{blowfish}.  The subkey array
-is assigned an initial constant value derived from the matrix used in the
-cipher.  Words from the user key are XORed into the array, starting from the
-beginning, and restarting from the beginning of the user key when all the
-user key words are exhausted.  A 96-bit block is initialized to zero, and
-enciphered with Storin, using the subkeys currently in the array.  The first
-four subkey words are then replaced with the resulting ciphertext, which is
-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).
+key schedule is very similar to Blowfish \cite{Schneier:1994:DNV}.  The
+subkey array is assigned an initial constant value derived from the matrix
+used in the cipher.  Words from the user key are XORed into the array,
+starting from the beginning, and restarting from the beginning of the user
+key when all the user key words are exhausted.  A 96-bit block is initialized
+to zero, and enciphered with Storin, using the subkeys currently in the
+array.  The first four subkey words are then replaced with the resulting
+ciphertext, which is 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 in theory accept user keys up to 36 words (864
+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}
@@ -244,8 +270,8 @@ $\mathcal{W}$.  Storin plaintext blocks are members of $\mathcal{P}$.
 
 The Storin encryption function uses 36 24-bit words of key material $k_0$,
 $k_1$, \ldots, $k_{35}$, which are produced from the user key by the key
-schedule, described below.  The key-mixing operation $K_i: \mathcal{P}
-\rightarrow \mathcal{P}$ is defined for $0 \le i < 9$ by:
+schedule, described below.  The key-mixing operation $K_i \colon \mathcal{P}
+\to \mathcal{P}$ is defined for $0 \le i < 9$ by:
 \[
   K_i \begin{pmatrix} a \\ b \\ c \\d \end{pmatrix}
   =
@@ -254,12 +280,12 @@ schedule, described below.  The key-mixing operation $K_i: \mathcal{P}
   \end{pmatrix}
 \]
 
-The matrix multiplication operation $M: \mathcal{P} \to \mathcal{P}$
+The matrix multiplication operation $M \colon \mathcal{P} \to \mathcal{P}$
 is described by $M(\mathbf{x}) = \mathbf{M} \mathbf{x}$, where $\mathbf{M}$
 is a fixed invertible $4 \times 4$ matrix over $\mathcal{W}$.  The value of
 $\mathbf{M}$ is defined below.
 
-The linear transformation $L: \mathcal{P} \to \mathcal{P}$ is defined by:
+The linear transformation $L \colon \mathcal{P} \to \mathcal{P}$ is defined by:
 \[
   L \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}
   =
@@ -271,11 +297,11 @@ The linear transformation $L: \mathcal{P} \to \mathcal{P}$ is defined by:
   \end{pmatrix}
 \]
 
-The round function $R_i: \mathcal{P} \to \mathcal{P}$ is defined for $0 \le i
-< 8$ by
-\[ R_i(\mathbf{x}) = L\bigl(\mathbf{M} K_i(\mathbf{x}) \bigr) \]
+The round function $R_i \colon \mathcal{P} \to \mathcal{P}$ is defined for $0
+\le i < 8$ by
+\[ \bigl(\mathbf{M} K_i(\mathbf{x}) \bigr) \]
 
-The cipher $C: \mathcal{P} \to \mathcal{P}$ is defined in terms of $R_i$ and
+The cipher $C \colon \mathcal{P} \to \mathcal{P}$ is defined in terms of $R_i$ and
 $K_i$.  Let $\mathbf{x}_0 \in \mathcal{P}$ be a plaintext vector.  Let
 $\mathbf{x}_{i+1} = R_i(\mathbf{x}_i)$ for $0 \le i < 8$.  Then we define
 $C(\mathbf{x})$ by setting $C(\mathbf{x}_0) = K_8(\mathbf{x}_8)$.
@@ -339,18 +365,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*}
 
@@ -362,7 +388,7 @@ The matrix $\mathbf{M}$ and its inverse $\mathbf{M}^{-1}$ are:
 
 The initial objective was to produce a cipher which played to the particular
 strengths of digital signal processors.  DSPs tend to have good multipliers,
-and are particularly good at matrix multiplication.  The decision use a
+and are particularly good at matrix multiplication.  The decision to use a
 matrix multiplication over $\mathbb{Z}_{2^{24}}$ seemed natural, given that
 24 bits is a commonly offered word size.
 
@@ -396,8 +422,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}
 
@@ -423,32 +448,151 @@ 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.
-
-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
-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.
+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{Schneier:1994:DNV}.  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.
+
+The restriction of the key schedule to 28 words is due to an interesting
+property, also shared by 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.
 
+\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}
 
-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{Wooding:2000:Storin-diff},
+which can be used to break Storin reduced to only 2 rounds.  The differential
+\[ \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:
+\[ \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:
+\[ \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{Fisher:2000: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
@@ -465,14 +609,8 @@ place to look for cryptanalysis.
 We have presented a new block cipher, Storin.  Any cryptanalysis will be
 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}
-\end{thebibliography}
+\bibliographystyle{alpha}
+\bibliography{cryptography,mdw}
 
 %%%----- That's all, folks --------------------------------------------------
 
