%%% -*-latex-*-
%%%
-%%% $Id: storin.tex,v 1.3 2000/05/25 19:46:22 mdw Exp $
+%%% $Id: storin.tex,v 1.7 2001/03/11 23:46:56 mdw Exp $
%%%
%%% Definition of the cipher
%%%
%%%----- 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.
%%%
\usepackage{mathenv}
\usepackage{amsfonts}
\usepackage{mdwmath}
+\usepackage{url}
\usepackage[all, dvips]{xy}
\def\ror{\mathbin{>\!\!>\!\!>}}
\def\seq#1{{\langle #1 \rangle}}
\def\hex#1{\texttt{#1}_{16}}
+\let\msgid=\url
\sloppy
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.
+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 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}
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}
=
\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}
=
\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)$.
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.
+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 \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 (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.
\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.
-
-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) \]
+\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:
-\[ (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.
-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.
+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
We have presented a new block cipher, Storin. Any cryptanalysis will be
received with interest.
-
-\begin{thebibliography}{99}
-\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}
+\bibliographystyle{alpha}
+\bibliography{cryptography,mdw}
%%%----- That's all, folks --------------------------------------------------