From cb946298dbe944c543ae38fe2c8be46ea44732e2 Mon Sep 17 00:00:00 2001 Message-Id: From: Mark Wooding Date: Sun, 2 Jul 2000 15:22:34 +0000 Subject: [PATCH] Overhaul of differential cryptanalysis, including a new attack. Organization: Straylight/Edgeware From: Mark Wooding --- storin.tex | 116 ++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 98 insertions(+), 18 deletions(-) diff --git a/storin.tex b/storin.tex index 313b534..1115d24 100644 --- a/storin.tex +++ b/storin.tex @@ -1,6 +1,6 @@ %%% -*-latex-*- %%% -%%% $Id: storin.tex,v 1.4 2000/05/28 00:39:32 mdw Exp $ +%%% $Id: storin.tex,v 1.5 2000/07/02 15:22:34 mdw Exp $ %%% %%% Definition of the cipher %%% @@ -10,6 +10,9 @@ %%%----- Revision history --------------------------------------------------- %%% %%% $Log: storin.tex,v $ +%%% 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. %%% @@ -488,26 +491,95 @@ round-2 key in a part of the cipher earlier than the postwhitening stage. \subsection{Attacking Storin} +\subsubsection{Differential cryptanalysis} + 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) \] +\[ \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. +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{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. @@ -529,14 +601,22 @@ received with interest. \begin{thebibliography}{99} -\bibitem{storin-collide} M. Fisher, `Yet another block cipher: Storin', +\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, +\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', +\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', +\bibitem{storin-tdiff} + M. D. Wooding, + `Yet another block cipher: Storin', sci.crypt article, message-id \texttt{} \end{thebibliography} -- [mdw]