| 1 | %%% -*-latex-*- |
| 2 | %%% |
| 3 | %%% $Id: storin.tex,v 1.5 2000/07/02 15:22:34 mdw Exp $ |
| 4 | %%% |
| 5 | %%% Definition of the cipher |
| 6 | %%% |
| 7 | %%% (c) 2000 Mark Wooding |
| 8 | %%% |
| 9 | |
| 10 | %%%----- Revision history --------------------------------------------------- |
| 11 | %%% |
| 12 | %%% $Log: storin.tex,v $ |
| 13 | %%% Revision 1.5 2000/07/02 15:22:34 mdw |
| 14 | %%% Overhaul of differential cryptanalysis, including a new attack. |
| 15 | %%% |
| 16 | %%% Revision 1.4 2000/05/28 00:39:32 mdw |
| 17 | %%% Fix some errors. |
| 18 | %%% |
| 19 | %%% Revision 1.3 2000/05/25 19:46:22 mdw |
| 20 | %%% Improve analysis section. |
| 21 | %%% |
| 22 | %%% Revision 1.2 2000/05/21 21:43:26 mdw |
| 23 | %%% Fix a couple of typos. |
| 24 | %%% |
| 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 | |
| 46 | \def\hex#1{\texttt{#1}_{16}} |
| 47 | |
| 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 | |
| 98 | \def\figstart#1{% |
| 99 | \POS 0;<1cm,0cm>:% |
| 100 | \turnradius{4pt}% |
| 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" |
| 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 | |
| 140 | \def\figwhite#1#2#3#4#5{% |
| 141 | \ar @{.} "a"-(0.5, 0); p+(8, 0) |
| 142 | \POS "a"+(8, -1)*[r]\txt{Postwhitening} |
| 143 | \figkeymix{#1}{#2}{#3}{#4} |
| 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} |
| 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{ |
| 200 | \figstart{} |
| 201 | \figround{0}{1}{2}{3}{Round 1} |
| 202 | \figround{4}{5}{6}{7}{Round 2} |
| 203 | \figgap |
| 204 | \figwhite{32}{33}{34}{35}{'}} |
| 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{ |
| 224 | \figstart{'} |
| 225 | \figiround{32}{33}{34}{35}{Round 1} |
| 226 | \figiround{28}{29}{30}{31}{Round 2} |
| 227 | \figgap |
| 228 | \figwhite{0}{1}{2}{3}{}} |
| 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 | |
| 248 | The Storin key schedule can in theory accept user keys up to 36 words (864 |
| 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. |
| 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} = & |
| 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} |
| 364 | \end{pmatrix} \\ |
| 365 | \mathbf{M}^{-1} = & |
| 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} |
| 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, |
| 382 | and are particularly good at matrix multiplication. The decision to use a |
| 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} |
| 416 | \item A top-bit change in a single word affects three words in the output. |
| 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 |
| 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. |
| 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 | |
| 452 | The restriction of the key schedule to 28 words is due to an interesting |
| 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. |
| 459 | |
| 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} |
| 491 | |
| 492 | \subsection{Attacking Storin} |
| 493 | |
| 494 | \subsubsection{Differential cryptanalysis} |
| 495 | |
| 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 |
| 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 | \] |
| 505 | holds with probability 1 through the matrix multiplication. |
| 506 | Differentials in the linear transform are easy to find; for example: |
| 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 | \] |
| 514 | We can continue through the second round's matrix multiplication with a |
| 515 | truncated differential, again with probability 1: |
| 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 | \] |
| 554 | This characteristic is non-iterative, and can't be extended to more rounds. |
| 555 | |
| 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 | |
| 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 | |
| 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} |
| 604 | \bibitem{storin-collide} |
| 605 | M. Fisher, |
| 606 | `Yet another block cipher: Storin', |
| 607 | sci.crypt article, message-id \texttt{<8gjctn\$9ct\$1@nnrp1.deja.com>} |
| 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, |
| 612 | Hartung-Gorre Verlag Konstanz, Technische Hochschule (Zurich), 1992 |
| 613 | \bibitem{blowfish} |
| 614 | B. Schneier, |
| 615 | `The Blowfish Encryption Algorithm', |
| 616 | \textit{Dr Dobb's Journal}, vol. 19 no. 4, April 1994, pp. 38--40 |
| 617 | \bibitem{storin-tdiff} |
| 618 | M. D. Wooding, |
| 619 | `Yet another block cipher: Storin', |
| 620 | sci.crypt article, message-id |
| 621 | \texttt{<slrn8iqhaq.872.mdw@mull.ncipher.com>} |
| 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: |