%%% -*-latex-*-
%%%
-%%% $Id: storin.tex,v 1.4 2000/05/28 00:39:32 mdw Exp $
+%%% $Id: storin.tex,v 1.6 2001/03/11 23:22:53 mdw Exp $
%%%
%%% Definition of the cipher
%%%
%%%----- Revision history ---------------------------------------------------
%%%
%%% $Log: storin.tex,v $
+%%% 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.
%%%
\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 known problems with keys longer than 28 words
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
+The round function $R_i \colon \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 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} (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.
+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}
-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 --------------------------------------------------
~mdw / storin / blobdiff