X-Git-Url: https://git.distorted.org.uk/~mdw/storin/blobdiff_plain/4643f89a9addf5c66e64ca7dbb9145298531208b..c0bfb7f905ac7b3219be1f2cd8cb23ef6e3803d1:/storin.tex diff --git a/storin.tex b/storin.tex index cd36172..6a958f2 100644 --- a/storin.tex +++ b/storin.tex @@ -1,6 +1,6 @@ %%% -*-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 %%% @@ -10,6 +10,18 @@ %%%----- 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. %%% @@ -28,6 +40,7 @@ \usepackage{mathenv} \usepackage{amsfonts} \usepackage{mdwmath} +\usepackage{url} \usepackage[all, dvips]{xy} \def\ror{\mathbin{>\!\!>\!\!>}} @@ -38,6 +51,7 @@ \def\seq#1{{\langle #1 \rangle}} \def\hex#1{\texttt{#1}_{16}} +\let\msgid=\url \sloppy @@ -228,22 +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. +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} @@ -254,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} = @@ -264,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} = @@ -281,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)$. @@ -438,16 +454,18 @@ 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. +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. @@ -483,37 +501,98 @@ 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 @@ -530,19 +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{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{} -\end{thebibliography} +\bibliographystyle{alpha} +\bibliography{cryptography,mdw} %%%----- That's all, folks --------------------------------------------------