%%% -*-latex-*-
%%%
-%%% $Id: storin.tex,v 1.1 2000/05/21 11:28:30 mdw Exp $
+%%% $Id: storin.tex,v 1.4 2000/05/28 00:39:32 mdw Exp $
%%%
%%% Definition of the cipher
%%%
%%%----- Revision history ---------------------------------------------------
%%%
%%% $Log: storin.tex,v $
+%%% 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.
%%%
\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}
\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{%
\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}
\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}
\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}
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 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 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*}
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.
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}
\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
-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 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.
+
+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.
+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
\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 --------------------------------------------------
~mdw / storin / blobdiff