3 %%% $Id: storin.tex,v 1.6 2001/03/11 23:22:53 mdw Exp $
5 %%% Definition of the cipher
7 %%% (c) 2000 Mark Wooding
10 %%%----- Revision history ---------------------------------------------------
12 %%% $Log: storin.tex,v $
13 %%% Revision 1.6 2001/03/11 23:22:53 mdw
14 %%% Use BibTeX for the paper bibliography.
16 %%% Revision 1.5 2000/07/02 15:22:34 mdw
17 %%% Overhaul of differential cryptanalysis, including a new attack.
19 %%% Revision 1.4 2000/05/28 00:39:32 mdw
22 %%% Revision 1.3 2000/05/25 19:46:22 mdw
23 %%% Improve analysis section.
25 %%% Revision 1.2 2000/05/21 21:43:26 mdw
26 %%% Fix a couple of typos.
28 %%% Revision 1.1 2000/05/21 11:28:30 mdw
32 %%%----- Preamble -----------------------------------------------------------
34 \documentclass[a4paper]{article
}
35 \usepackage[palatino, helvetica, courier, maths=cmr
]{mdwfonts
}
41 \usepackage[all,
dvips]{xy
}
43 \def\ror{\mathbin{>\!\!>\!\!>
}}
44 \def\rol{\mathbin{<\!\!<\!\!<
}}
45 \def\lsr{\mathbin{>\!\!>
}}
46 \def\lsl{\mathbin{<\!\!<
}}
48 \def\seq#1{{\langle #1 \rangle}}
50 \def\hex#1{\texttt{#1}_
{16}}
55 \title{Storin: A block cipher for digital signal processors
}
56 \author{Mark Wooding (
\texttt{mdw@nsict.org
})
}
58 %% --- The cipher diagrams ---
60 \def\figkeymix#1#2#3#4{%
61 \ar "a"; p-(
0,
0.5)*
{\xor} ="a"
\ar "a"+(
1,
0) *+
[r
]{k_
{#1}}; "a"
%
62 \ar "b"; p-(
0,
0.5)*
{\xor} ="b"
\ar "b"+(
1,
0) *+
[r
]{k_
{#2}}; "b"
%
63 \ar "c"; p-(
0,
0.5)*
{\xor} ="c"
\ar "c"+(
1,
0) *+
[r
]{k_
{#3}}; "c"
%
64 \ar "d"; p-(
0,
0.5)*
{\xor} ="d"
\ar "d"+(
1,
0) *+
[r
]{k_
{#4}}; "d"
%
68 \POS "a"+(
3, -
1) *++=(
7,
0)
[F
]u
\txt{Matrix multiply
} ="m"
%
69 \ar "a"; "m"+U-(
3,
0)
\ar "b"; "m"+U-(
1,
0)
%
70 \ar "c"; "m"+U+(
1,
0)
\ar "d"; "m"+U+(
3,
0)
%
74 \ar "m"+D-(
3,
0); "a"-(
0,
2.25)*
{\xor} ="a"
%
75 \POS "a"+(
1,
0) *+
[F
]{{} \lsr 12} ="x"
%
76 \ar `r "a"+(
0,
0.5); p+(
1,
0) "x"
\ar "x"; "a"
%
77 \ar "m"+D-(
1,
0); "b"-(
0,
2.25)*
{\xor} ="b"
%
78 \POS "b"+(
1,
0) *+
[F
]{{} \lsr 12} ="x"
%
79 \ar `r "b"+(
0,
0.5); p+(
1,
0) "x"
\ar "x"; "b"
%
80 \ar "m"+D+(
1,
0); "c"-(
0,
2.25)*
{\xor} ="c"
%
81 \POS "c"+(
1,
0) *+
[F
]{{} \lsr 12} ="x"
%
82 \ar `r "c"+(
0,
0.5); p+(
1,
0) "x"
\ar "x"; "c"
%
83 \ar "m"+D+(
3,
0); "d"-(
0,
2.25)*
{\xor} ="d"
%
84 \POS "d"+(
1,
0) *+
[F
]{{} \lsr 12} ="x"
%
85 \ar `r "d"+(
0,
0.5); p+(
1,
0) "x"
\ar "x"; "d"
%
89 \ar "a"; "a"-(
0,
1)*
{\xor} ="a"
%
90 \POS "a"+(
1,
0) *+
[F
]{{} \lsr 12} ="x"
%
91 \ar `r "a"+(
0,
0.5); p+(
1,
0) "x"
\ar "x"; "a"
%
92 \ar "b"; "b"-(
0,
1)*
{\xor} ="b"
%
93 \POS "b"+(
1,
0) *+
[F
]{{} \lsr 12} ="x"
%
94 \ar `r "b"+(
0,
0.5); p+(
1,
0) "x"
\ar "x"; "b"
%
95 \ar "c"; "c"-(
0,
1)*
{\xor} ="c"
%
96 \POS "c"+(
1,
0) *+
[F
]{{} \lsr 12} ="x"
%
97 \ar `r "c"+(
0,
0.5); p+(
1,
0) "x"
\ar "x"; "c"
%
98 \ar "d"; "d"-(
0,
1)*
{\xor} ="d"
%
99 \POS "d"+(
1,
0) *+
[F
]{{} \lsr 12} ="x"
%
100 \ar `r "d"+(
0,
0.5); p+(
1,
0) "x"
\ar "x"; "d"
%
106 \ar @
{-
} (
0,
0) *+
{a
#1}; p-(
0,
0.5) ="a"
107 \ar @
{-
} (
2,
0) *+
{b
#1}; p-(
0,
0.5) ="b"
108 \ar @
{-
} (
4,
0) *+
{c
#1}; p-(
0,
0.5) ="c"
109 \ar @
{-
} (
6,
0) *+
{d
#1}; p-(
0,
0.5) ="d"
112 \def\figround#1#2#3#4#5{%
113 \ar @
{.
} "a"-(
0.5,
0); p+(
8,
0)
%
114 \POS "a"+(
8, -
1.75) *
[r
]\txt{#5}%
115 \figkeymix{#1}{#2}{#3}{#4}%
118 \ar @
{-
} "a"; p-(
0,
.5) ="a"
119 \ar @
{-
} "b"; p-(
0,
.5) ="b"
120 \ar @
{-
} "c"; p-(
0,
.5) ="c"
121 \ar @
{-
} "d"; p-(
0,
.5) ="d"
124 \def\figiround#1#2#3#4#5{%
125 \ar @
{.
} "a"-(
0.5,
0); p+(
8,
0)
%
126 \POS "a"+(
8, -
1.75) *
[r
]\txt{#5}%
127 \figkeymix{#1}{#2}{#3}{#4}%
130 \ar @
{-
} "m"+D-(
3,
0); p-(
0,
.5) ="a"
131 \ar @
{-
} "m"+D-(
1,
0); p-(
0,
.5) ="b"
132 \ar @
{-
} "m"+D+(
1,
0); p-(
0,
.5) ="c"
133 \ar @
{-
} "m"+D+(
3,
0); p-(
0,
.5) ="d"
137 \ar @
{.
} "a"-(
0.5,
0); p+(
8,
0)
138 \POS "a"+(
8, -
1)*
[r
]\txt{Six more rounds
}
139 \ar @
{--
} "a"; "a"-(
0,
2) ="a"
140 \ar @
{--
} "b"; "b"-(
0,
2) ="b"
141 \ar @
{--
} "c"; "c"-(
0,
2) ="c"
142 \ar @
{--
} "d"; "d"-(
0,
2) ="d"
145 \def\figwhite#1#2#3#4#5{%
146 \ar @
{.
} "a"-(
0.5,
0); p+(
8,
0)
147 \POS "a"+(
8, -
1)*
[r
]\txt{Postwhitening
}
148 \figkeymix{#1}{#2}{#3}{#4}
149 \ar "a"; p-(
0,
1) *+
{a
#5}
150 \ar "b"; p-(
0,
1) *+
{b
#5}
151 \ar "c"; p-(
0,
1) *+
{c
#5}
152 \ar "d"; p-(
0,
1) *+
{d
#5}
158 %%%----- The main text ------------------------------------------------------
161 We present Storin: a new
96-bit block cipher designed to play to the
162 strengths of current digital signal processors (DSPs). In particular, DSPs
163 tend to provide single-cycle multiply-and-accumulate operations, making
164 matrix multiplications very cheap. Working in an environment where
165 multiplication is as fast as exclusive-or changes the usual perceptions
166 about which operations provide good cryptographic strength cheaply. The
167 scarcity of available memory, for code and for tables, and a penalty for
168 nonsequential access to data also make traditional block ciphers based
169 around substitution tables unsuitable.
174 \section{Definition of the cipher
}
176 \subsection{Overview
}
178 Storin is an eight-round SP network operating on
96-bit blocks. The block
179 cipher uses
36 24-bit subkey words, derived from a user key by the key
182 The
96-bit input is split into four
24-bit words. Each round then processes
183 these four words, using the following three steps:
185 \item Mixing in of some key material. Four
24-bit subkey words are XORed
186 with the four data words.
187 \item A matrix multiplication mod $
2^
{24}$. The four words are treated as a
188 column vector and premultiplied by a $
4 \times 4$ vector using addition and
189 multiplication mod $
2^
{24}$. This is the main nonlinear step in the
190 cipher, and it also provides most of the cipher's diffusion.
191 \item A simple linear transformation, which replaces each word $x$ by $x
\xor
194 The four data words output by the final round are XORed with the last four
195 subkey words in a final postwhitening stage and combined to form the
96-bit
198 The cipher structure is shown diagrammatically in figure~
\ref{fig:cipher
}.
206 \figround{0}{1}{2}{3}{Round
1}
207 \figround{4}{5}{6}{7}{Round
2}
209 \figwhite{32}{33}{34}{35}{'
}}
211 \caption{The Storin encryption function
}
215 Since the matrix used in step
2 is chosen to be invertible, the cipher can be
216 inverted readily, simply by performing the inverse steps in the reverse
217 order. Since the postwhitening stage is the same as a key mixing stage,
218 decryption can be viewed as eight rounds consisting of key mixing, linear
219 transformation and matrix multiplication, followed by a postwhitening stage.
220 Thus, the structure of the inverse cipher is very similar to the forwards
221 cipher, and uses the same components. The decryption function is shown
222 diagrammatically in figure~
\ref{fig:decipher
}.
230 \figiround{32}{33}{34}{35}{Round
1}
231 \figiround{28}{29}{30}{31}{Round
2}
233 \figwhite{0}{1}{2}{3}{}}
235 \caption{The Storin decryption function
}
239 The key schedule is designed to be simple and to reuse the cipher components
240 already available. Given a user key, which is a sequence of one or more
241 24-bit words, it produces the
36 subkey words required by the cipher. The
242 key schedule is very similar to Blowfish
\cite{Schneier:
1994:DNV
}. The
243 subkey array is assigned an initial constant value derived from the matrix
244 used in the cipher. Words from the user key are XORed into the array,
245 starting from the beginning, and restarting from the beginning of the user
246 key when all the user key words are exhausted. A
96-bit block is initialized
247 to zero, and enciphered with Storin, using the subkeys currently in the
248 array. The first four subkey words are then replaced with the resulting
249 ciphertext, which is then encrypted again using the new subkeys. The next
250 four subkey words are replaced with the ciphertext, and the process
251 continues, nine times in all, until all of the subkey words have been
254 The Storin key schedule can in theory accept user keys up to
36 words (
864
255 bits) long. However, there are known problems with keys longer than
28 words
256 (
672 bits), and these large keys are forbidden. We expect that with long
257 keys, attacks will be found which are more efficient than an exhaustive
258 search of the keyspace; we therefore (conservatively) recommend
5 word
259 (
120-bit) keys as a practical maximum.
262 \subsection{Encryption
}
264 We define $
\mathcal{W
} =
\mathbb{Z
}_
{2^
{24}}$ to be set of
24-bit words, and
265 $
\mathcal{P
} =
\mathcal{W
}^
4$ to be the set of four-entry column vectors over
266 $
\mathcal{W
}$. Storin plaintext blocks are members of $
\mathcal{P
}$.
268 The Storin encryption function uses
36 24-bit words of key material $k_0$,
269 $k_1$,
\ldots, $k_
{35}$, which are produced from the user key by the key
270 schedule, described below. The key-mixing operation $K_i
\colon \mathcal{P
}
271 \to \mathcal{P
}$ is defined for $
0 \le i <
9$ by:
273 K_i
\begin{pmatrix
} a \\ b \\ c \
\d \end{pmatrix
}
276 a
\xor k_
{4i
} \\ b
\xor k_
{4i+
1} \\ c
\xor k_
{4i+
2} \\ d
\xor k_
{4i+
3}
280 The matrix multiplication operation $M
\colon \mathcal{P
} \to \mathcal{P
}$
281 is described by $M(
\mathbf{x
}) =
\mathbf{M
} \mathbf{x
}$, where $
\mathbf{M
}$
282 is a fixed invertible $
4 \times 4$ matrix over $
\mathcal{W
}$. The value of
283 $
\mathbf{M
}$ is defined below.
285 The linear transformation $L
\colon \mathcal{P
} \to \mathcal{P
}$ is defined by:
287 L
\begin{pmatrix
} a \\ b \\ c \\ d
\end{pmatrix
}
290 a
\xor (a
\lsr 12) \\
291 b
\xor (b
\lsr 12) \\
292 c
\xor (c
\lsr 12) \\
297 The round function $R_i
\colon \mathcal{P
} \to \mathcal{P
}$ is defined for $
0
299 \
[ R_i(
\mathbf{x
}) = L
\bigl(
\mathbf{M
} K_i(
\mathbf{x
})
\bigr) \
]
301 The cipher $C
\colon \mathcal{P
} \to \mathcal{P
}$ is defined in terms of $R_i$ and
302 $K_i$. Let $
\mathbf{x
}_0
\in \mathcal{P
}$ be a plaintext vector. Let
303 $
\mathbf{x
}_
{i+
1} = R_i(
\mathbf{x
}_i)$ for $
0 \le i <
8$. Then we define
304 $C(
\mathbf{x
})$ by setting $C(
\mathbf{x
}_0) = K_8(
\mathbf{x
}_8)$.
307 \subsection{Key schedule
}
309 The key schedule converts a user key, which is a sequence of
24-bit words,
310 into the
36 subkeys required by the cipher.
312 For $i
\ge 0$, we define that
315 m_
{16i +
0} & m_
{16i +
1} & m_
{16i +
2} & m_
{16i +
3} \\
316 m_
{16i +
4} & m_
{16i +
5} & m_
{16i +
6} & m_
{16i +
7} \\
317 m_
{16i +
8} & m_
{16i +
9} & m_
{16i +
10} & m_
{16i +
11} \\
318 m_
{16i +
12} & m_
{16i +
13} & m_
{16i +
14} & m_
{16i +
15}
323 Let the user-supplied key be $u_0$, $u_1$,
\ldots, $u_
{n-
1}$, for some $n >
324 0$. We define the sequence $z_0$, $z_1$,
\ldots\ by
325 \
[ z_i = m_i
\xor u_
{i
\bmod n
} \
]
328 Denote the result of encrypting vector $
\mathbf{x
}$ using subkeys from the
329 sequence $
\seq{w
} = w_0, w_1,
\ldots, w_
{35}$ as $C_
{\seq{w
}}(
\mathbf{x
})$.
330 We define the key schedule to be $k_0$, $k_1$,
\ldots, $k_
{35}$, where:
332 \seq{p^
{(i)
}} = k_0, k_1,
\ldots, k_
{4i-
1}, z_
{4i
}, z_
{4i+
1},
\ldots \\
333 \mathbf{x
}_0 =
\begin{pmatrix
} 0 \\
0 \\
0 \\
0 \end{pmatrix
};
\qquad
334 \begin{pmatrix
} k_
{4i
} \\ k_
{4i+
1} \\ k_
{4i+
2} \\ k_
{4i+
3} \end{pmatrix
}
335 =
\mathbf{x
}_
{i+
1} = C_
{\seq{p^
{(i)
}}}(
\mathbf{x
}_i)
339 \subsection{Decryption
}
341 The individual operations used during encryption are all invertible. Key
342 mixing is inverted by taking keys from the other end of the array:
343 \
[ K^
{-
1}_i(
\mathbf{x
}) = K_
{8-i
}(
\mathbf{x
}) \
]
344 The matrix multiplication may be inverted simply by using the inverse matrix
346 \
[ M^
{-
1}(
\mathbf{x
}) =
\mathbf{M
}^
{-
1} \mathbf{x
} \
]
347 Finally, the linear transformation is its own inverse:
348 \
[ L^
{-
1}(
\mathbf{x
}) = L(
\mathbf{x
}) \
]
349 The inverse round function can now be defined as:
350 \
[ R^
{-
1}_i(
\mathbf{x
}) =
351 \mathbf{M
}^
{-
1} L
\bigl(K^
{-
1}_i(
\mathbf{x
})
\bigr) \
]
353 The decryption function $C^
{-
1}:
\mathcal{P
} \to \mathcal{P
}$ is defined
354 in terms of $R^
{-
1}$ and $K^
{-
1}$ in a very similar way to encryption. Let
355 $
\mathbf{x
}_0$ be a ciphertext vector. Let $
\mathbf{x
}_
{i+
1} =
356 R^
{-
1}_i(
\mathbf{x
}_i)$ for $
0 \le i <
8$. Then we define
357 $C^
{-
1}(
\mathbf{x
}_0) = K^
{-
1}_8(
\mathbf{x
}_8)$.
360 \subsection{Constants
}
362 The matrix $
\mathbf{M
}$ and its inverse $
\mathbf{M
}^
{-
1}$ are:
363 \begin{eqnarray*
}[rl
]
366 \hex{f7a413
} &
\hex{54bd81
} &
\hex{447550} &
\hex{ff4449
} \\
367 \hex{f31e87
} &
\hex{d85388
} &
\hex{de32cb
} &
\hex{40e3d7
} \\
368 \hex{d9db1d
} &
\hex{551b45
} &
\hex{e9d19f
} &
\hex{e443de
} \\
369 \hex{4b949a
} &
\hex{4d435d
} &
\hex{ef0a17
} &
\hex{b784e1
}
373 \hex{17391b
} &
\hex{fafb4b
} &
\hex{a66823
} &
\hex{f2efb6
} \\
374 \hex{13e0e5
} &
\hex{2ed5e4
} &
\hex{b2cfff
} &
\hex{d9cdb5
} \\
375 \hex{2af462
} &
\hex{33826d
} &
\hex{de66a1
} &
\hex{eb6c85
} \\
376 \hex{c2f423
} &
\hex{e904a3
} &
\hex{e772d8
} &
\hex{d791f1
}
382 \section{Rationale and analysis
}
384 \subsection{Design decisions
}
386 The initial objective was to produce a cipher which played to the particular
387 strengths of digital signal processors. DSPs tend to have good multipliers,
388 and are particularly good at matrix multiplication. The decision to use a
389 matrix multiplication over $
\mathbb{Z
}_
{2^
{24}}$ seemed natural, given that
390 24 bits is a commonly offered word size.
392 The choice of a
96-bit block is also fairly natural. A
2 word (
48-bit) block
393 is clearly too small, and a
3 word (
72-bit) block is a little on the small
397 \subsection{Matrix multiplication over $
\mathbb{Z
}_
{2^
{24}}$
}
399 Integer multiplication on a DSP is a cheap source of nonlinearity. Note that
400 bit $i$ of the result depends on all of the bits in the operands of lesser or
401 equal significance.position $i$ downwards.
403 The decision to make the $
4 \times 4$ matrix fixed was taken fairly early on.
404 Generating invertible matrices from key material seemed like too much work to
407 The matrix is generated pseudorandomly from a seed string, using SHA-
1. The
408 criteria we used to choose the matrix are:
410 \item The matrix must be invertible.
411 \item Exactly one entry in each row and column of the matrix must be even.
413 Criterion
1 is obvious. Criterion
2 encourages diffusion between the entries
414 in the block vector. Note that if a matrix satisfies the second criterion,
415 its inverse also does.
417 Consider a vector $
\mathbf{x
}$ and its product with the matrix $
\mathbf{M
}
418 \mathbf{x
}$. Whether the top bit of entry $i$ in $
\mathbf{x
}$ affects
419 entry $j$ in the product depends on whether the entry in row $j$, column $i$
420 of $
\mathbf{M
}$ is even. Criterion
2 ensures the following:
422 \item A top-bit change in a single word affects three words in the output.
423 \item A top-bit change in two words affects two words in the output.
426 The seed string used is
\texttt{matrix-seed-string
}. The program which
427 generates the matrix is included with the Storin example source code.
429 \subsection{The linear transformation
}
431 A bit change in one of the inputs to the matrix can only affect bits at that
432 position and higher in the output. The linear transformation at the end of
433 the round aims to provide diffusion from the high-order bits back to the
436 A single high-order bit change in the input to a round will affect the
437 high-order bits of three words in the output of the matrix multiply. The
438 linear transformation causes it to affect bits in the low halves of each of
439 these words. The second round's multiplication causes these bits to affect
440 the whole top halves of all of the output words. The linear transformation
441 propagates this change to the bottom halves. Complete avalanche is therefore
442 achieved after three rounds of Storin.
445 \subsection{Key schedule notes
}
447 The key schedule is intended to be adequate for bulk encryption; it doesn't
448 provide good key agility, and isn't intended to. The key schedule accepts up
449 to
28 words of user key, although expecting
672 bits of security from the
450 cipher is not realistic. The suggested maximum of
5 words (
120 bits) seems
451 more sensible. This maximum can be raised easily when our understanding of
452 the cipher increases our confidence in it.
454 The key schedule is strongly reminiscent of Blowfish
455 \cite{Schneier:
1994:DNV
}. Use of existing components of the cipher, such as
456 the matrix multiplication and the cipher itself, help reduce the amount of
457 code required in the implementation.
459 The restriction of the key schedule to
28 words is due to an interesting
460 property, also shared by Blowfish (see figure~
\ref{fig:bfkeysched
}): the
461 output of the first round of the second encryption doesn't depend on the
462 previous round. To see why this is so, it is enough to note that the first
463 round key has just been set equal to what is now the plaintext; the result of
464 the key mixing stage is zero, which is unaffected by the matrix and linear
467 A limit of
28 words is chosen to ensure that the round-
1 key affects the
468 round-
2 key in a part of the cipher earlier than the postwhitening stage.
475 \POS 0; <
0.7cm,
0cm>:
476 \POS (
0,
0) ="o" +(
3,
0) ="w"
477 \ar "o" *+
{P
[0]}; p-(
0,
1) *
{\xor} ="x"
478 \ar "x" -(
1,
0) *+
[l
]{P
[0]}; "x"
479 \ar@
{-
} "x"; p-(
0,
2) ="as"
480 \ar "w" *+
{P
[1]}; p-(
0,
2) *
{\xor} ="x"
481 \ar "o"-(
0,
2); "x" |-*+
[F
]{F
}
482 \ar@
{-
} "x"; p-(
0,
1) ="bs"
483 \ar@
{-
} "as"; "bs"-(
0,
1) ="w"
484 \ar@
{-
} "bs"; "as"-(
0,
1) ="o"
485 \ar "o"; p-(
0,
1) *+
{P
[1] \xor F(
0)
} ="x"
486 \ar "x"; p-(
0,
1) *
{\xor} ="x"
487 \ar "x" -(
1,
0) *+
[l
]{P
[1]}; "x"
488 \ar "x"; p-(
0,
2) *+
{F(
0)
}
489 \ar "w"; p-(
0,
1) *+
{0} ="x"
490 \ar "x"; p-(
0,
2) *
{\xor} ="x"
491 \ar "o"-(
0,
3); "x" |-*+
[F
]{F
}
492 \ar "x"; p-(
0,
1) *+
{F^
2(
0)
}}
494 \caption{Blowfish key schedule: $P
[2]$ and $P
[3]$ don't depend on $P
[0]$ and
496 \label{fig:bfkeysched
}
499 \subsection{Attacking Storin
}
501 \subsubsection{Differential cryptanalysis
}
503 There is a two-round truncated differential
\cite{Wooding:
2000:Storin-diff
},
504 which can be used to break Storin reduced to only
2 rounds. The differential
506 1 \lsl 23 \\
1 \lsl 23 \\
1 \lsl 23 \\
0
509 0 \\
0 \\
1 \lsl 23 \\
0
512 holds with probability
1 through the matrix multiplication.
513 Differentials in the linear transform are easy to find; for example:
515 0 \\
0 \\
1 \lsl 23 \\
0
518 0 \\
0 \\ (
1 \lsl 23)
\xor (
1 \lsl 11) \\
0
521 We can continue through the second round's matrix multiplication with a
522 truncated differential, again with probability
1:
524 0 \\
0 \\ (
1 \lsl 23)
\xor (
1 \lsl 11) \\
0
528 (
\delta_1 \lsl 12)
\xor (
1 \lsl 11) \\
529 (
\delta_2 \lsl 12)
\xor (
1 \lsl 11) \\
530 (
\delta_3 \lsl 12)
\xor (
1 \lsl 11) \\
533 where the $
\delta_i$ are unknown
12-bit values. Applying the linear
534 transformation to this output difference gives us
537 (
\delta_1 \lsl 12)
\xor (
1 \lsl 11) \\
538 (
\delta_2 \lsl 12)
\xor (
1 \lsl 11) \\
539 (
\delta_3 \lsl 12)
\xor (
1 \lsl 11) \\
542 (
\delta_0 \lsl 12)
\xor \delta_0 \\
543 (
\delta_1 \lsl 12)
\xor \delta_1 \xor (
1 \lsl 11) \\
544 (
\delta_2 \lsl 12)
\xor \delta_2 \xor (
1 \lsl 11) \\
545 (
\delta_3 \lsl 12)
\xor \delta_3 \xor (
1 \lsl 11) \\
548 A subsequent key-mixing or postwhitening stage won't affect the difference.
549 We can therefore combine the differentials above to construct a probability-
1
550 truncated differential for a
2-round variant of Storin:
552 1 \lsl 23 \\
1 \lsl 23 \\
1 \lsl 23 \\
0
555 (
\delta_0 \lsl 12)
\xor \delta_0 \\
556 (
\delta_1 \lsl 12)
\xor \delta_1 \xor (
1 \lsl 11) \\
557 (
\delta_2 \lsl 12)
\xor \delta_2 \xor (
1 \lsl 11) \\
558 (
\delta_3 \lsl 12)
\xor \delta_3 \xor (
1 \lsl 11) \\
561 This characteristic is non-iterative, and can't be extended to more rounds.
563 The differential can be converted into a key-recovery attack against $n$
564 rounds fairly easily, by obtaining the ciphertext for an appropriate
565 plaintext pair and guessing the $n -
2$ round keys, testing the guesses by
566 working backwards and finding out whether the expected output difference is
567 visible. The attack requires a pair of chosen plaintexts, and
568 $O(
2^
{96(n -
2)
})$ work. It is only more efficient than exhaustive search
569 when the key is longer than $
96(n -
2)$ bits.
571 This attack can be improved. Consider a
3-round variant of Storin, where the
572 objective is to discover the postwhitening keys. The postwhitening stage can
573 be commuted with the linear transform simply by applying the transform to the
574 postwhitening keys. We do this, and guess the least significant
12 bits of
575 each of the (transformed) postwhitening key words. Working through the
576 matrix multiplication mod $
2^
{12}$ rather than mod $
2^
{24}$ then gives us the
577 12 least significant bits of the state words on input to the matrix. Further
578 key bits can then be guessed and tested, four at a time, to recover the
579 remaining postwhitening key bits, by ensuring that the differences in the
580 more significant bits of the third round matrix input obey the characteristic
581 described above. This requires only about $
2^
{48}$ work, and may be extended
582 to further rounds by exhaustively searching for the extra round keys.
584 This attack can break Storin with $n$ rounds ($n
\ge 3$) with minimal chosen
585 plaintext and $O(
2^
{48 +
96(n -
3)
})$ work. This is the best attack known
588 \subsubsection{Other attacks
}
590 In
\cite{Fisher:
2000:Storin-collide
}, Matthew Fisher speculates on breaking
2
591 rounds of Storin by forcing collisions in the matrix multiplication outputs.
592 This attack doesn't extend to more than two rounds either.
594 One possible avenue of attack worth exploring is to attempt to cause zero
595 words to be input into the first-round matrix by choosing plaintext words
596 identical to subkey words for the first round. Causing $n$ matrix input
597 words to be zero clearly takes $O(
2^
{24n
})$ time. If a method can be found
598 to detect when zero words have been input to the matrix, this can be used to
599 discover the subkey words rather more rapidly than exhaustive search. We
600 can't see a way to exploit this at the moment, but it could be a fruitful
601 place to look for cryptanalysis.
606 We have presented a new block cipher, Storin. Any cryptanalysis will be
607 received with interest.
609 \bibliographystyle{alpha
}
610 \bibliography{cryptography,mdw
}
612 %%%----- That's all, folks --------------------------------------------------