Commit | Line | Data |
---|---|---|
e6e0e332 MW |
1 | %%% -*-latex-*- |
2 | %%% | |
cb946298 | 3 | %%% $Id: storin.tex,v 1.5 2000/07/02 15:22:34 mdw Exp $ |
e6e0e332 MW |
4 | %%% |
5 | %%% Definition of the cipher | |
6 | %%% | |
7 | %%% (c) 2000 Mark Wooding | |
8 | %%% | |
9 | ||
10 | %%%----- Revision history --------------------------------------------------- | |
11 | %%% | |
12 | %%% $Log: storin.tex,v $ | |
cb946298 MW |
13 | %%% Revision 1.5 2000/07/02 15:22:34 mdw |
14 | %%% Overhaul of differential cryptanalysis, including a new attack. | |
15 | %%% | |
23ec5116 MW |
16 | %%% Revision 1.4 2000/05/28 00:39:32 mdw |
17 | %%% Fix some errors. | |
18 | %%% | |
4643f89a MW |
19 | %%% Revision 1.3 2000/05/25 19:46:22 mdw |
20 | %%% Improve analysis section. | |
21 | %%% | |
31b692a0 MW |
22 | %%% Revision 1.2 2000/05/21 21:43:26 mdw |
23 | %%% Fix a couple of typos. | |
24 | %%% | |
e6e0e332 MW |
25 | %%% Revision 1.1 2000/05/21 11:28:30 mdw |
26 | %%% Initial check-in. | |
27 | %%% | |
28 | ||
29 | %%%----- Preamble ----------------------------------------------------------- | |
30 | ||
31 | \documentclass[a4paper]{article} | |
32 | \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts} | |
33 | \usepackage{mdwtab} | |
34 | \usepackage{mathenv} | |
35 | \usepackage{amsfonts} | |
36 | \usepackage{mdwmath} | |
37 | \usepackage[all, dvips]{xy} | |
38 | ||
39 | \def\ror{\mathbin{>\!\!>\!\!>}} | |
40 | \def\rol{\mathbin{<\!\!<\!\!<}} | |
41 | \def\lsr{\mathbin{>\!\!>}} | |
42 | \def\lsl{\mathbin{<\!\!<}} | |
43 | \def\xor{\oplus} | |
44 | \def\seq#1{{\langle #1 \rangle}} | |
45 | ||
4643f89a MW |
46 | \def\hex#1{\texttt{#1}_{16}} |
47 | ||
e6e0e332 MW |
48 | \sloppy |
49 | ||
50 | \title{Storin: A block cipher for digital signal processors} | |
51 | \author{Mark Wooding (\texttt{mdw@nsict.org})} | |
52 | ||
53 | %% --- The cipher diagrams --- | |
54 | ||
55 | \def\figkeymix#1#2#3#4{% | |
56 | \ar "a"; p-(0, 0.5)*{\xor} ="a" \ar "a"+(1, 0) *+[r]{k_{#1}}; "a"% | |
57 | \ar "b"; p-(0, 0.5)*{\xor} ="b" \ar "b"+(1, 0) *+[r]{k_{#2}}; "b"% | |
58 | \ar "c"; p-(0, 0.5)*{\xor} ="c" \ar "c"+(1, 0) *+[r]{k_{#3}}; "c"% | |
59 | \ar "d"; p-(0, 0.5)*{\xor} ="d" \ar "d"+(1, 0) *+[r]{k_{#4}}; "d"% | |
60 | } | |
61 | ||
62 | \def\figmatrix{% | |
63 | \POS "a"+(3, -1) *++=(7, 0)[F]u\txt{Matrix multiply} ="m"% | |
64 | \ar "a"; "m"+U-(3, 0) \ar "b"; "m"+U-(1, 0)% | |
65 | \ar "c"; "m"+U+(1, 0) \ar "d"; "m"+U+(3, 0)% | |
66 | } | |
67 | ||
68 | \def\figlintrans{% | |
69 | \ar "m"+D-(3, 0); "a"-(0, 2.25)*{\xor} ="a"% | |
70 | \POS "a"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |
71 | \ar `r "a"+(0, 0.5); p+(1, 0) "x" \ar "x"; "a"% | |
72 | \ar "m"+D-(1, 0); "b"-(0, 2.25)*{\xor} ="b"% | |
73 | \POS "b"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |
74 | \ar `r "b"+(0, 0.5); p+(1, 0) "x" \ar "x"; "b"% | |
75 | \ar "m"+D+(1, 0); "c"-(0, 2.25)*{\xor} ="c"% | |
76 | \POS "c"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |
77 | \ar `r "c"+(0, 0.5); p+(1, 0) "x" \ar "x"; "c"% | |
78 | \ar "m"+D+(3, 0); "d"-(0, 2.25)*{\xor} ="d"% | |
79 | \POS "d"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |
80 | \ar `r "d"+(0, 0.5); p+(1, 0) "x" \ar "x"; "d"% | |
81 | } | |
82 | ||
83 | \def\figilintrans{% | |
84 | \ar "a"; "a"-(0, 1)*{\xor} ="a"% | |
85 | \POS "a"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |
86 | \ar `r "a"+(0, 0.5); p+(1, 0) "x" \ar "x"; "a"% | |
87 | \ar "b"; "b"-(0, 1)*{\xor} ="b"% | |
88 | \POS "b"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |
89 | \ar `r "b"+(0, 0.5); p+(1, 0) "x" \ar "x"; "b"% | |
90 | \ar "c"; "c"-(0, 1)*{\xor} ="c"% | |
91 | \POS "c"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |
92 | \ar `r "c"+(0, 0.5); p+(1, 0) "x" \ar "x"; "c"% | |
93 | \ar "d"; "d"-(0, 1)*{\xor} ="d"% | |
94 | \POS "d"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |
95 | \ar `r "d"+(0, 0.5); p+(1, 0) "x" \ar "x"; "d"% | |
96 | } | |
97 | ||
31b692a0 | 98 | \def\figstart#1{% |
e6e0e332 MW |
99 | \POS 0;<1cm,0cm>:% |
100 | \turnradius{4pt}% | |
31b692a0 MW |
101 | \ar @{-} (0, 0) *+{a#1}; p-(0, 0.5) ="a" |
102 | \ar @{-} (2, 0) *+{b#1}; p-(0, 0.5) ="b" | |
103 | \ar @{-} (4, 0) *+{c#1}; p-(0, 0.5) ="c" | |
104 | \ar @{-} (6, 0) *+{d#1}; p-(0, 0.5) ="d" | |
e6e0e332 MW |
105 | } |
106 | ||
107 | \def\figround#1#2#3#4#5{% | |
108 | \ar @{.} "a"-(0.5, 0); p+(8, 0)% | |
109 | \POS "a"+(8, -1.75) *[r]\txt{#5}% | |
110 | \figkeymix{#1}{#2}{#3}{#4}% | |
111 | \figmatrix% | |
112 | \figlintrans% | |
113 | \ar @{-} "a"; p-(0, .5) ="a" | |
114 | \ar @{-} "b"; p-(0, .5) ="b" | |
115 | \ar @{-} "c"; p-(0, .5) ="c" | |
116 | \ar @{-} "d"; p-(0, .5) ="d" | |
117 | } | |
118 | ||
119 | \def\figiround#1#2#3#4#5{% | |
120 | \ar @{.} "a"-(0.5, 0); p+(8, 0)% | |
121 | \POS "a"+(8, -1.75) *[r]\txt{#5}% | |
122 | \figkeymix{#1}{#2}{#3}{#4}% | |
123 | \figilintrans% | |
124 | \figmatrix% | |
125 | \ar @{-} "m"+D-(3, 0); p-(0, .5) ="a" | |
126 | \ar @{-} "m"+D-(1, 0); p-(0, .5) ="b" | |
127 | \ar @{-} "m"+D+(1, 0); p-(0, .5) ="c" | |
128 | \ar @{-} "m"+D+(3, 0); p-(0, .5) ="d" | |
129 | } | |
130 | ||
131 | \def\figgap{% | |
132 | \ar @{.} "a"-(0.5, 0); p+(8, 0) | |
133 | \POS "a"+(8, -1)*[r]\txt{Six more rounds} | |
134 | \ar @{--} "a"; "a"-(0, 2) ="a" | |
135 | \ar @{--} "b"; "b"-(0, 2) ="b" | |
136 | \ar @{--} "c"; "c"-(0, 2) ="c" | |
137 | \ar @{--} "d"; "d"-(0, 2) ="d" | |
138 | } | |
139 | ||
31b692a0 | 140 | \def\figwhite#1#2#3#4#5{% |
e6e0e332 MW |
141 | \ar @{.} "a"-(0.5, 0); p+(8, 0) |
142 | \POS "a"+(8, -1)*[r]\txt{Postwhitening} | |
143 | \figkeymix{#1}{#2}{#3}{#4} | |
31b692a0 MW |
144 | \ar "a"; p-(0, 1) *+{a#5} |
145 | \ar "b"; p-(0, 1) *+{b#5} | |
146 | \ar "c"; p-(0, 1) *+{c#5} | |
147 | \ar "d"; p-(0, 1) *+{d#5} | |
e6e0e332 MW |
148 | } |
149 | ||
150 | \begin{document} | |
151 | \maketitle | |
152 | ||
153 | %%%----- The main text ------------------------------------------------------ | |
154 | ||
155 | \begin{abstract} | |
156 | We present Storin: a new 96-bit block cipher designed to play to the | |
157 | strengths of current digital signal processors (DSPs). In particular, DSPs | |
158 | tend to provide single-cycle multiply-and-accumulate operations, making | |
159 | matrix multiplications very cheap. Working in an environment where | |
160 | multiplication is as fast as exclusive-or changes the usual perceptions | |
161 | about which operations provide good cryptographic strength cheaply. The | |
162 | scarcity of available memory, for code and for tables, and a penalty for | |
163 | nonsequential access to data also make traditional block ciphers based | |
164 | around substitution tables unsuitable. | |
165 | \end{abstract} | |
166 | ||
167 | \tableofcontents | |
168 | ||
169 | \section{Definition of the cipher} | |
170 | ||
171 | \subsection{Overview} | |
172 | ||
173 | Storin is an eight-round SP network operating on 96-bit blocks. The block | |
174 | cipher uses 36 24-bit subkey words, derived from a user key by the key | |
175 | schedule. | |
176 | ||
177 | The 96-bit input is split into four 24-bit words. Each round then processes | |
178 | these four words, using the following three steps: | |
179 | \begin{enumerate} | |
180 | \item Mixing in of some key material. Four 24-bit subkey words are XORed | |
181 | with the four data words. | |
182 | \item A matrix multiplication mod $2^{24}$. The four words are treated as a | |
183 | column vector and premultiplied by a $4 \times 4$ vector using addition and | |
184 | multiplication mod $2^{24}$. This is the main nonlinear step in the | |
185 | cipher, and it also provides most of the cipher's diffusion. | |
186 | \item A simple linear transformation, which replaces each word $x$ by $x \xor | |
187 | (x \lsr 12)$. | |
188 | \end{enumerate} | |
189 | The four data words output by the final round are XORed with the last four | |
190 | subkey words in a final postwhitening stage and combined to form the 96-bit | |
191 | ciphertext. | |
192 | ||
193 | The cipher structure is shown diagrammatically in figure~\ref{fig:cipher}. | |
194 | ||
195 | \begin{figure} | |
196 | \centering | |
197 | \leavevmode | |
198 | \begin{xy} | |
199 | \xycompile{ | |
31b692a0 | 200 | \figstart{} |
e6e0e332 MW |
201 | \figround{0}{1}{2}{3}{Round 1} |
202 | \figround{4}{5}{6}{7}{Round 2} | |
203 | \figgap | |
31b692a0 | 204 | \figwhite{32}{33}{34}{35}{'}} |
e6e0e332 MW |
205 | \end{xy} |
206 | \caption{The Storin encryption function} | |
207 | \label{fig:cipher} | |
208 | \end{figure} | |
209 | ||
210 | Since the matrix used in step 2 is chosen to be invertible, the cipher can be | |
211 | inverted readily, simply by performing the inverse steps in the reverse | |
212 | order. Since the postwhitening stage is the same as a key mixing stage, | |
213 | decryption can be viewed as eight rounds consisting of key mixing, linear | |
214 | transformation and matrix multiplication, followed by a postwhitening stage. | |
215 | Thus, the structure of the inverse cipher is very similar to the forwards | |
216 | cipher, and uses the same components. The decryption function is shown | |
217 | diagrammatically in figure~\ref{fig:decipher}. | |
218 | ||
219 | \begin{figure} | |
220 | \centering | |
221 | \leavevmode | |
222 | \begin{xy} | |
223 | \xycompile{ | |
31b692a0 | 224 | \figstart{'} |
e6e0e332 MW |
225 | \figiround{32}{33}{34}{35}{Round 1} |
226 | \figiround{28}{29}{30}{31}{Round 2} | |
227 | \figgap | |
31b692a0 | 228 | \figwhite{0}{1}{2}{3}{}} |
e6e0e332 MW |
229 | \end{xy} |
230 | \caption{The Storin decryption function} | |
231 | \label{fig:decipher} | |
232 | \end{figure} | |
233 | ||
234 | The key schedule is designed to be simple and to reuse the cipher components | |
235 | already available. Given a user key, which is a sequence of one or more | |
236 | 24-bit words, it produces the 36 subkey words required by the cipher. The | |
237 | key schedule is very similar to Blowfish \cite{blowfish}. The subkey array | |
238 | is assigned an initial constant value derived from the matrix used in the | |
239 | cipher. Words from the user key are XORed into the array, starting from the | |
240 | beginning, and restarting from the beginning of the user key when all the | |
241 | user key words are exhausted. A 96-bit block is initialized to zero, and | |
242 | enciphered with Storin, using the subkeys currently in the array. The first | |
243 | four subkey words are then replaced with the resulting ciphertext, which is | |
244 | then encrypted again using the new subkeys. The next four subkey words are | |
245 | replaced with the ciphertext, and the process continues, nine times in all, | |
246 | until all of the subkey words have been replaced. | |
247 | ||
4643f89a | 248 | The Storin key schedule can in theory accept user keys up to 36 words (864 |
23ec5116 MW |
249 | bits) long. However, there are known problems with keys longer than 28 words |
250 | (672 bits), and these large keys are forbidden. We expect that with long | |
251 | keys, attacks will be found which are more efficient than an exhaustive | |
252 | search of the keyspace; we therefore (conservatively) recommend 5 word | |
253 | (120-bit) keys as a practical maximum. | |
e6e0e332 MW |
254 | |
255 | ||
256 | \subsection{Encryption} | |
257 | ||
258 | We define $\mathcal{W} = \mathbb{Z}_{2^{24}}$ to be set of 24-bit words, and | |
259 | $\mathcal{P} = \mathcal{W}^4$ to be the set of four-entry column vectors over | |
260 | $\mathcal{W}$. Storin plaintext blocks are members of $\mathcal{P}$. | |
261 | ||
262 | The Storin encryption function uses 36 24-bit words of key material $k_0$, | |
263 | $k_1$, \ldots, $k_{35}$, which are produced from the user key by the key | |
264 | schedule, described below. The key-mixing operation $K_i: \mathcal{P} | |
265 | \rightarrow \mathcal{P}$ is defined for $0 \le i < 9$ by: | |
266 | \[ | |
267 | K_i \begin{pmatrix} a \\ b \\ c \\d \end{pmatrix} | |
268 | = | |
269 | \begin{pmatrix} | |
270 | a \xor k_{4i} \\ b \xor k_{4i+1} \\ c \xor k_{4i+2} \\ d \xor k_{4i+3} | |
271 | \end{pmatrix} | |
272 | \] | |
273 | ||
274 | The matrix multiplication operation $M: \mathcal{P} \to \mathcal{P}$ | |
275 | is described by $M(\mathbf{x}) = \mathbf{M} \mathbf{x}$, where $\mathbf{M}$ | |
276 | is a fixed invertible $4 \times 4$ matrix over $\mathcal{W}$. The value of | |
277 | $\mathbf{M}$ is defined below. | |
278 | ||
279 | The linear transformation $L: \mathcal{P} \to \mathcal{P}$ is defined by: | |
280 | \[ | |
281 | L \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} | |
282 | = | |
283 | \begin{pmatrix} | |
284 | a \xor (a \lsr 12) \\ | |
285 | b \xor (b \lsr 12) \\ | |
286 | c \xor (c \lsr 12) \\ | |
287 | d \xor (d \lsr 12) | |
288 | \end{pmatrix} | |
289 | \] | |
290 | ||
291 | The round function $R_i: \mathcal{P} \to \mathcal{P}$ is defined for $0 \le i | |
292 | < 8$ by | |
293 | \[ R_i(\mathbf{x}) = L\bigl(\mathbf{M} K_i(\mathbf{x}) \bigr) \] | |
294 | ||
295 | The cipher $C: \mathcal{P} \to \mathcal{P}$ is defined in terms of $R_i$ and | |
296 | $K_i$. Let $\mathbf{x}_0 \in \mathcal{P}$ be a plaintext vector. Let | |
297 | $\mathbf{x}_{i+1} = R_i(\mathbf{x}_i)$ for $0 \le i < 8$. Then we define | |
298 | $C(\mathbf{x})$ by setting $C(\mathbf{x}_0) = K_8(\mathbf{x}_8)$. | |
299 | ||
300 | ||
301 | \subsection{Key schedule} | |
302 | ||
303 | The key schedule converts a user key, which is a sequence of 24-bit words, | |
304 | into the 36 subkeys required by the cipher. | |
305 | ||
306 | For $i \ge 0$, we define that | |
307 | \[ | |
308 | \begin{pmatrix} | |
309 | m_{16i + 0} & m_{16i + 1} & m_{16i + 2} & m_{16i + 3} \\ | |
310 | m_{16i + 4} & m_{16i + 5} & m_{16i + 6} & m_{16i + 7} \\ | |
311 | m_{16i + 8} & m_{16i + 9} & m_{16i + 10} & m_{16i + 11} \\ | |
312 | m_{16i + 12} & m_{16i + 13} & m_{16i + 14} & m_{16i + 15} | |
313 | \end{pmatrix} | |
314 | = \mathbf{M}^{i + 2} | |
315 | \] | |
316 | ||
317 | Let the user-supplied key be $u_0$, $u_1$, \ldots, $u_{n-1}$, for some $n > | |
318 | 0$. We define the sequence $z_0$, $z_1$, \ldots\ by | |
319 | \[ z_i = m_i \xor u_{i \bmod n} \] | |
320 | for $i \ge 0$. | |
321 | ||
322 | Denote the result of encrypting vector $\mathbf{x}$ using subkeys from the | |
323 | sequence $\seq{w} = w_0, w_1, \ldots, w_{35}$ as $C_{\seq{w}}(\mathbf{x})$. | |
324 | We define the key schedule to be $k_0$, $k_1$, \ldots, $k_{35}$, where: | |
325 | \begin{eqlines*} | |
326 | \seq{p^{(i)}} = k_0, k_1, \ldots, k_{4i-1}, z_{4i}, z_{4i+1}, \ldots \\ | |
327 | \mathbf{x}_0 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}; \qquad | |
328 | \begin{pmatrix} k_{4i} \\ k_{4i+1} \\ k_{4i+2} \\ k_{4i+3} \end{pmatrix} | |
329 | = \mathbf{x}_{i+1} = C_{\seq{p^{(i)}}}(\mathbf{x}_i) | |
330 | \end{eqlines*} | |
331 | ||
332 | ||
333 | \subsection{Decryption} | |
334 | ||
335 | The individual operations used during encryption are all invertible. Key | |
336 | mixing is inverted by taking keys from the other end of the array: | |
337 | \[ K^{-1}_i(\mathbf{x}) = K_{8-i}(\mathbf{x}) \] | |
338 | The matrix multiplication may be inverted simply by using the inverse matrix | |
339 | $\mathbf{M}^{-1}$: | |
340 | \[ M^{-1}(\mathbf{x}) = \mathbf{M}^{-1} \mathbf{x} \] | |
341 | Finally, the linear transformation is its own inverse: | |
342 | \[ L^{-1}(\mathbf{x}) = L(\mathbf{x}) \] | |
343 | The inverse round function can now be defined as: | |
344 | \[ R^{-1}_i(\mathbf{x}) = | |
345 | \mathbf{M}^{-1} L\bigl(K^{-1}_i(\mathbf{x})\bigr) \] | |
346 | ||
347 | The decryption function $C^{-1}: \mathcal{P} \to \mathcal{P}$ is defined | |
348 | in terms of $R^{-1}$ and $K^{-1}$ in a very similar way to encryption. Let | |
349 | $\mathbf{x}_0$ be a ciphertext vector. Let $\mathbf{x}_{i+1} = | |
350 | R^{-1}_i(\mathbf{x}_i)$ for $0 \le i < 8$. Then we define | |
351 | $C^{-1}(\mathbf{x}_0) = K^{-1}_8(\mathbf{x}_8)$. | |
352 | ||
353 | ||
354 | \subsection{Constants} | |
355 | ||
356 | The matrix $\mathbf{M}$ and its inverse $\mathbf{M}^{-1}$ are: | |
357 | \begin{eqnarray*}[rl] | |
358 | \mathbf{M} = & | |
4643f89a MW |
359 | \begin{pmatrix} |
360 | \hex{f7a413} & \hex{54bd81} & \hex{447550} & \hex{ff4449} \\ | |
361 | \hex{f31e87} & \hex{d85388} & \hex{de32cb} & \hex{40e3d7} \\ | |
362 | \hex{d9db1d} & \hex{551b45} & \hex{e9d19f} & \hex{e443de} \\ | |
363 | \hex{4b949a} & \hex{4d435d} & \hex{ef0a17} & \hex{b784e1} | |
e6e0e332 MW |
364 | \end{pmatrix} \\ |
365 | \mathbf{M}^{-1} = & | |
4643f89a MW |
366 | \begin{pmatrix} |
367 | \hex{17391b} & \hex{fafb4b} & \hex{a66823} & \hex{f2efb6} \\ | |
368 | \hex{13e0e5} & \hex{2ed5e4} & \hex{b2cfff} & \hex{d9cdb5} \\ | |
369 | \hex{2af462} & \hex{33826d} & \hex{de66a1} & \hex{eb6c85} \\ | |
370 | \hex{c2f423} & \hex{e904a3} & \hex{e772d8} & \hex{d791f1} | |
e6e0e332 MW |
371 | \end{pmatrix} |
372 | \end{eqnarray*} | |
373 | ||
374 | ||
375 | ||
376 | \section{Rationale and analysis} | |
377 | ||
378 | \subsection{Design decisions} | |
379 | ||
380 | The initial objective was to produce a cipher which played to the particular | |
381 | strengths of digital signal processors. DSPs tend to have good multipliers, | |
31b692a0 | 382 | and are particularly good at matrix multiplication. The decision to use a |
e6e0e332 MW |
383 | matrix multiplication over $\mathbb{Z}_{2^{24}}$ seemed natural, given that |
384 | 24 bits is a commonly offered word size. | |
385 | ||
386 | The choice of a 96-bit block is also fairly natural. A 2 word (48-bit) block | |
387 | is clearly too small, and a 3 word (72-bit) block is a little on the small | |
388 | side too. | |
389 | ||
390 | ||
391 | \subsection{Matrix multiplication over $\mathbb{Z}_{2^{24}}$} | |
392 | ||
393 | Integer multiplication on a DSP is a cheap source of nonlinearity. Note that | |
394 | bit $i$ of the result depends on all of the bits in the operands of lesser or | |
395 | equal significance.position $i$ downwards. | |
396 | ||
397 | The decision to make the $4 \times 4$ matrix fixed was taken fairly early on. | |
398 | Generating invertible matrices from key material seemed like too much work to | |
399 | expect from the DSP. | |
400 | ||
401 | The matrix is generated pseudorandomly from a seed string, using SHA-1. The | |
402 | criteria we used to choose the matrix are: | |
403 | \begin{enumerate} | |
404 | \item The matrix must be invertible. | |
405 | \item Exactly one entry in each row and column of the matrix must be even. | |
406 | \end{enumerate} | |
407 | Criterion 1 is obvious. Criterion 2 encourages diffusion between the entries | |
408 | in the block vector. Note that if a matrix satisfies the second criterion, | |
409 | its inverse also does. | |
410 | ||
411 | Consider a vector $\mathbf{x}$ and its product with the matrix $\mathbf{M} | |
412 | \mathbf{x}$. Whether the top bit of entry $i$ in $\mathbf{x}$ affects | |
413 | entry $j$ in the product depends on whether the entry in row $j$, column $i$ | |
414 | of $\mathbf{M}$ is even. Criterion 2 ensures the following: | |
415 | \begin{itemize} | |
4643f89a | 416 | \item A top-bit change in a single word affects three words in the output. |
e6e0e332 MW |
417 | \item A top-bit change in two words affects two words in the output. |
418 | \end{itemize} | |
419 | ||
420 | The seed string used is \texttt{matrix-seed-string}. The program which | |
421 | generates the matrix is included with the Storin example source code. | |
422 | ||
423 | \subsection{The linear transformation} | |
424 | ||
425 | A bit change in one of the inputs to the matrix can only affect bits at that | |
426 | position and higher in the output. The linear transformation at the end of | |
427 | the round aims to provide diffusion from the high-order bits back to the | |
428 | low-order bits. | |
429 | ||
430 | A single high-order bit change in the input to a round will affect the | |
431 | high-order bits of three words in the output of the matrix multiply. The | |
432 | linear transformation causes it to affect bits in the low halves of each of | |
433 | these words. The second round's multiplication causes these bits to affect | |
434 | the whole top halves of all of the output words. The linear transformation | |
435 | propagates this change to the bottom halves. Complete avalanche is therefore | |
436 | achieved after three rounds of Storin. | |
437 | ||
438 | ||
439 | \subsection{Key schedule notes} | |
440 | ||
441 | The key schedule is intended to be adequate for bulk encryption; it doesn't | |
4643f89a MW |
442 | provide good key agility, and isn't intended to. The key schedule accepts up |
443 | to 28 words of user key, although expecting 672 bits of security from the | |
444 | cipher is not realistic. The suggested maximum of 5 words (120 bits) seems | |
445 | more sensible. This maximum can be raised easily when our understanding of | |
446 | the cipher increases our confidence in it. | |
e6e0e332 MW |
447 | |
448 | The key schedule is strongly reminiscent of Blowfish \cite{blowfish}. Use of | |
449 | existing components of the cipher, such as the matrix multiplication and the | |
450 | cipher itself, help reduce the amount of code required in the implementation. | |
451 | ||
4643f89a | 452 | The restriction of the key schedule to 28 words is due to an interesting |
23ec5116 MW |
453 | property, also shared by Blowfish \cite{blowfish} (see |
454 | figure~\ref{fig:bfkeysched}): the output of the first round of the second | |
455 | encryption doesn't depend on the previous round. To see why this is so, it | |
456 | is enough to note that the first round key has just been set equal to what is | |
457 | now the plaintext; the result of the key mixing stage is zero, which is | |
458 | unaffected by the matrix and linear transformation. | |
e6e0e332 | 459 | |
4643f89a MW |
460 | A limit of 28 words is chosen to ensure that the round-1 key affects the |
461 | round-2 key in a part of the cipher earlier than the postwhitening stage. | |
462 | ||
463 | \begin{figure} | |
464 | \centering | |
465 | \leavevmode | |
466 | \begin{xy} | |
467 | \xycompile{ | |
468 | \POS 0; <0.7cm, 0cm>: | |
469 | \POS (0, 0) ="o" +(3, 0) ="w" | |
470 | \ar "o" *+{P[0]}; p-(0, 1) *{\xor} ="x" | |
471 | \ar "x" -(1, 0) *+[l]{P[0]}; "x" | |
472 | \ar@{-} "x"; p-(0, 2) ="as" | |
473 | \ar "w" *+{P[1]}; p-(0, 2) *{\xor} ="x" | |
474 | \ar "o"-(0, 2); "x" |-*+[F]{F} | |
475 | \ar@{-} "x"; p-(0, 1) ="bs" | |
476 | \ar@{-} "as"; "bs"-(0, 1) ="w" | |
477 | \ar@{-} "bs"; "as"-(0, 1) ="o" | |
478 | \ar "o"; p-(0, 1) *+{P[1] \xor F(0)} ="x" | |
479 | \ar "x"; p-(0, 1) *{\xor} ="x" | |
480 | \ar "x" -(1, 0) *+[l]{P[1]}; "x" | |
481 | \ar "x"; p-(0, 2) *+{F(0)} | |
482 | \ar "w"; p-(0, 1) *+{0} ="x" | |
483 | \ar "x"; p-(0, 2) *{\xor} ="x" | |
484 | \ar "o"-(0, 3); "x" |-*+[F]{F} | |
485 | \ar "x"; p-(0, 1) *+{F^2(0)}} | |
486 | \end{xy} | |
487 | \caption{Blowfish key schedule: $P[2]$ and $P[3]$ don't depend on $P[0]$ and | |
488 | $P[1]$.} | |
489 | \label{fig:bfkeysched} | |
490 | \end{figure} | |
e6e0e332 MW |
491 | |
492 | \subsection{Attacking Storin} | |
493 | ||
cb946298 MW |
494 | \subsubsection{Differential cryptanalysis} |
495 | ||
4643f89a MW |
496 | There is a two-round truncated differential \cite{storin-tdiff}, which can be |
497 | used to break Storin reduced to only 2 rounds. The differential | |
cb946298 MW |
498 | \[ \begin{pmatrix} |
499 | 1 \lsl 23 \\ 1 \lsl 23 \\ 1 \lsl 23 \\ 0 | |
500 | \end{pmatrix} \to | |
501 | \begin{pmatrix} | |
502 | 0 \\ 0 \\ 1 \lsl 23 \\ 0 | |
503 | \end{pmatrix} | |
504 | \] | |
4643f89a MW |
505 | holds with probability 1 through the matrix multiplication. |
506 | Differentials in the linear transform are easy to find; for example: | |
cb946298 MW |
507 | \[ \begin{pmatrix} |
508 | 0 \\ 0 \\ 1 \lsl 23 \\ 0 | |
509 | \end{pmatrix} \to | |
510 | \begin{pmatrix} | |
511 | 0 \\ 0 \\ (1 \lsl 23) \xor (1 \lsl 11) \\ 0 | |
512 | \end{pmatrix} | |
513 | \] | |
4643f89a MW |
514 | We can continue through the second round's matrix multiplication with a |
515 | truncated differential, again with probability 1: | |
cb946298 MW |
516 | \[ \begin{pmatrix} |
517 | 0 \\ 0 \\ (1 \lsl 23) \xor (1 \lsl 11) \\ 0 | |
518 | \end{pmatrix} \to | |
519 | \begin{pmatrix} | |
520 | \delta_0 \lsl 12 \\ | |
521 | (\delta_1 \lsl 12) \xor (1 \lsl 11) \\ | |
522 | (\delta_2 \lsl 12) \xor (1 \lsl 11) \\ | |
523 | (\delta_3 \lsl 12) \xor (1 \lsl 11) \\ | |
524 | \end{pmatrix} | |
525 | \] | |
526 | where the $\delta_i$ are unknown 12-bit values. Applying the linear | |
527 | transformation to this output difference gives us | |
528 | \[ \begin{pmatrix} | |
529 | \delta_0 \lsl 12 \\ | |
530 | (\delta_1 \lsl 12) \xor (1 \lsl 11) \\ | |
531 | (\delta_2 \lsl 12) \xor (1 \lsl 11) \\ | |
532 | (\delta_3 \lsl 12) \xor (1 \lsl 11) \\ | |
533 | \end{pmatrix} \to | |
534 | \begin{pmatrix} | |
535 | (\delta_0 \lsl 12) \xor \delta_0 \\ | |
536 | (\delta_1 \lsl 12) \xor \delta_1 \xor (1 \lsl 11) \\ | |
537 | (\delta_2 \lsl 12) \xor \delta_2 \xor (1 \lsl 11) \\ | |
538 | (\delta_3 \lsl 12) \xor \delta_3 \xor (1 \lsl 11) \\ | |
539 | \end{pmatrix} | |
540 | \] | |
541 | A subsequent key-mixing or postwhitening stage won't affect the difference. | |
542 | We can therefore combine the differentials above to construct a probability-1 | |
543 | truncated differential for a 2-round variant of Storin: | |
544 | \[ \begin{pmatrix} | |
545 | 1 \lsl 23 \\ 1 \lsl 23 \\ 1 \lsl 23 \\ 0 | |
546 | \end{pmatrix} \to | |
547 | \begin{pmatrix} | |
548 | (\delta_0 \lsl 12) \xor \delta_0 \\ | |
549 | (\delta_1 \lsl 12) \xor \delta_1 \xor (1 \lsl 11) \\ | |
550 | (\delta_2 \lsl 12) \xor \delta_2 \xor (1 \lsl 11) \\ | |
551 | (\delta_3 \lsl 12) \xor \delta_3 \xor (1 \lsl 11) \\ | |
552 | \end{pmatrix} | |
553 | \] | |
4643f89a MW |
554 | This characteristic is non-iterative, and can't be extended to more rounds. |
555 | ||
cb946298 MW |
556 | The differential can be converted into a key-recovery attack against $n$ |
557 | rounds fairly easily, by obtaining the ciphertext for an appropriate | |
558 | plaintext pair and guessing the $n - 2$ round keys, testing the guesses by | |
559 | working backwards and finding out whether the expected output difference is | |
560 | visible. The attack requires a pair of chosen plaintexts, and | |
561 | $O(2^{96(n - 2)})$ work. It is only more efficient than exhaustive search | |
562 | when the key is longer than $96(n - 2)$ bits. | |
563 | ||
564 | This attack can be improved. Consider a 3-round variant of Storin, where the | |
565 | objective is to discover the postwhitening keys. The postwhitening stage can | |
566 | be commuted with the linear transform simply by applying the transform to the | |
567 | postwhitening keys. We do this, and guess the least significant 12 bits of | |
568 | each of the (transformed) postwhitening key words. Working through the | |
569 | matrix multiplication mod $2^{12}$ rather than mod $2^{24}$ then gives us the | |
570 | 12 least significant bits of the state words on input to the matrix. Further | |
571 | key bits can then be guessed and tested, four at a time, to recover the | |
572 | remaining postwhitening key bits, by ensuring that the differences in the | |
573 | more significant bits of the third round matrix input obey the characteristic | |
574 | described above. This requires only about $2^{48}$ work, and may be extended | |
575 | to further rounds by exhaustively searching for the extra round keys. | |
576 | ||
577 | This attack can break Storin with $n$ rounds ($n \ge 3$) with minimal chosen | |
578 | plaintext and $O(2^{48 + 96(n - 3)})$ work. This is the best attack known | |
579 | against Storin. | |
580 | ||
581 | \subsubsection{Other attacks} | |
582 | ||
4643f89a MW |
583 | In \cite{storin-collide}, Matthew Fisher speculates on breaking 2 rounds of |
584 | Storin by forcing collisions in the matrix multiplication outputs. This | |
585 | attack doesn't extend to more than two rounds either. | |
586 | ||
e6e0e332 MW |
587 | One possible avenue of attack worth exploring is to attempt to cause zero |
588 | words to be input into the first-round matrix by choosing plaintext words | |
589 | identical to subkey words for the first round. Causing $n$ matrix input | |
590 | words to be zero clearly takes $O(2^{24n})$ time. If a method can be found | |
591 | to detect when zero words have been input to the matrix, this can be used to | |
592 | discover the subkey words rather more rapidly than exhaustive search. We | |
593 | can't see a way to exploit this at the moment, but it could be a fruitful | |
594 | place to look for cryptanalysis. | |
595 | ||
596 | ||
597 | \section{Conclusion} | |
598 | ||
599 | We have presented a new block cipher, Storin. Any cryptanalysis will be | |
600 | received with interest. | |
601 | ||
602 | ||
603 | \begin{thebibliography}{99} | |
cb946298 MW |
604 | \bibitem{storin-collide} |
605 | M. Fisher, | |
606 | `Yet another block cipher: Storin', | |
4643f89a | 607 | sci.crypt article, message-id \texttt{<8gjctn\$9ct\$1@nnrp1.deja.com>} |
cb946298 MW |
608 | \bibitem{idea} |
609 | X. Lai, | |
610 | `On the Design and Security of Block Ciphers', | |
611 | ETH Series in Informatics Processing, J. L. Massey (editor), vol. 1, | |
4643f89a | 612 | Hartung-Gorre Verlag Konstanz, Technische Hochschule (Zurich), 1992 |
cb946298 MW |
613 | \bibitem{blowfish} |
614 | B. Schneier, | |
615 | `The Blowfish Encryption Algorithm', | |
4643f89a | 616 | \textit{Dr Dobb's Journal}, vol. 19 no. 4, April 1994, pp. 38--40 |
cb946298 MW |
617 | \bibitem{storin-tdiff} |
618 | M. D. Wooding, | |
619 | `Yet another block cipher: Storin', | |
4643f89a MW |
620 | sci.crypt article, message-id |
621 | \texttt{<slrn8iqhaq.872.mdw@mull.ncipher.com>} | |
e6e0e332 MW |
622 | \end{thebibliography} |
623 | ||
624 | %%%----- That's all, folks -------------------------------------------------- | |
625 | ||
626 | \end{document} | |
627 | ||
628 | %%% Local Variables: | |
629 | %%% mode: latex | |
630 | %%% TeX-master: t | |
631 | %%% End: |