Commit | Line | Data |
---|---|---|

e6e0e332 MW |
1 | %%% -*-latex-*- |

2 | %%% | |

4643f89a | 3 | %%% $Id: storin.tex,v 1.3 2000/05/25 19:46:22 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 $ | |

4643f89a MW |
13 | %%% Revision 1.3 2000/05/25 19:46:22 mdw |

14 | %%% Improve analysis section. | |

15 | %%% | |

31b692a0 MW |
16 | %%% Revision 1.2 2000/05/21 21:43:26 mdw |

17 | %%% Fix a couple of typos. | |

18 | %%% | |

e6e0e332 MW |
19 | %%% Revision 1.1 2000/05/21 11:28:30 mdw |

20 | %%% Initial check-in. | |

21 | %%% | |

22 | ||

23 | %%%----- Preamble ----------------------------------------------------------- | |

24 | ||

25 | \documentclass[a4paper]{article} | |

26 | \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts} | |

27 | \usepackage{mdwtab} | |

28 | \usepackage{mathenv} | |

29 | \usepackage{amsfonts} | |

30 | \usepackage{mdwmath} | |

31 | \usepackage[all, dvips]{xy} | |

32 | ||

33 | \def\ror{\mathbin{>\!\!>\!\!>}} | |

34 | \def\rol{\mathbin{<\!\!<\!\!<}} | |

35 | \def\lsr{\mathbin{>\!\!>}} | |

36 | \def\lsl{\mathbin{<\!\!<}} | |

37 | \def\xor{\oplus} | |

38 | \def\seq#1{{\langle #1 \rangle}} | |

39 | ||

4643f89a MW |
40 | \def\hex#1{\texttt{#1}_{16}} |

41 | ||

e6e0e332 MW |
42 | \sloppy |

43 | ||

44 | \title{Storin: A block cipher for digital signal processors} | |

45 | \author{Mark Wooding (\texttt{mdw@nsict.org})} | |

46 | ||

47 | %% --- The cipher diagrams --- | |

48 | ||

49 | \def\figkeymix#1#2#3#4{% | |

50 | \ar "a"; p-(0, 0.5)*{\xor} ="a" \ar "a"+(1, 0) *+[r]{k_{#1}}; "a"% | |

51 | \ar "b"; p-(0, 0.5)*{\xor} ="b" \ar "b"+(1, 0) *+[r]{k_{#2}}; "b"% | |

52 | \ar "c"; p-(0, 0.5)*{\xor} ="c" \ar "c"+(1, 0) *+[r]{k_{#3}}; "c"% | |

53 | \ar "d"; p-(0, 0.5)*{\xor} ="d" \ar "d"+(1, 0) *+[r]{k_{#4}}; "d"% | |

54 | } | |

55 | ||

56 | \def\figmatrix{% | |

57 | \POS "a"+(3, -1) *++=(7, 0)[F]u\txt{Matrix multiply} ="m"% | |

58 | \ar "a"; "m"+U-(3, 0) \ar "b"; "m"+U-(1, 0)% | |

59 | \ar "c"; "m"+U+(1, 0) \ar "d"; "m"+U+(3, 0)% | |

60 | } | |

61 | ||

62 | \def\figlintrans{% | |

63 | \ar "m"+D-(3, 0); "a"-(0, 2.25)*{\xor} ="a"% | |

64 | \POS "a"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |

65 | \ar `r "a"+(0, 0.5); p+(1, 0) "x" \ar "x"; "a"% | |

66 | \ar "m"+D-(1, 0); "b"-(0, 2.25)*{\xor} ="b"% | |

67 | \POS "b"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |

68 | \ar `r "b"+(0, 0.5); p+(1, 0) "x" \ar "x"; "b"% | |

69 | \ar "m"+D+(1, 0); "c"-(0, 2.25)*{\xor} ="c"% | |

70 | \POS "c"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |

71 | \ar `r "c"+(0, 0.5); p+(1, 0) "x" \ar "x"; "c"% | |

72 | \ar "m"+D+(3, 0); "d"-(0, 2.25)*{\xor} ="d"% | |

73 | \POS "d"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |

74 | \ar `r "d"+(0, 0.5); p+(1, 0) "x" \ar "x"; "d"% | |

75 | } | |

76 | ||

77 | \def\figilintrans{% | |

78 | \ar "a"; "a"-(0, 1)*{\xor} ="a"% | |

79 | \POS "a"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |

80 | \ar `r "a"+(0, 0.5); p+(1, 0) "x" \ar "x"; "a"% | |

81 | \ar "b"; "b"-(0, 1)*{\xor} ="b"% | |

82 | \POS "b"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |

83 | \ar `r "b"+(0, 0.5); p+(1, 0) "x" \ar "x"; "b"% | |

84 | \ar "c"; "c"-(0, 1)*{\xor} ="c"% | |

85 | \POS "c"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |

86 | \ar `r "c"+(0, 0.5); p+(1, 0) "x" \ar "x"; "c"% | |

87 | \ar "d"; "d"-(0, 1)*{\xor} ="d"% | |

88 | \POS "d"+(1, 0) *+[F]{{} \lsr 12} ="x"% | |

89 | \ar `r "d"+(0, 0.5); p+(1, 0) "x" \ar "x"; "d"% | |

90 | } | |

91 | ||

31b692a0 | 92 | \def\figstart#1{% |

e6e0e332 MW |
93 | \POS 0;<1cm,0cm>:% |

94 | \turnradius{4pt}% | |

31b692a0 MW |
95 | \ar @{-} (0, 0) *+{a#1}; p-(0, 0.5) ="a" |

96 | \ar @{-} (2, 0) *+{b#1}; p-(0, 0.5) ="b" | |

97 | \ar @{-} (4, 0) *+{c#1}; p-(0, 0.5) ="c" | |

98 | \ar @{-} (6, 0) *+{d#1}; p-(0, 0.5) ="d" | |

e6e0e332 MW |
99 | } |

100 | ||

101 | \def\figround#1#2#3#4#5{% | |

102 | \ar @{.} "a"-(0.5, 0); p+(8, 0)% | |

103 | \POS "a"+(8, -1.75) *[r]\txt{#5}% | |

104 | \figkeymix{#1}{#2}{#3}{#4}% | |

105 | \figmatrix% | |

106 | \figlintrans% | |

107 | \ar @{-} "a"; p-(0, .5) ="a" | |

108 | \ar @{-} "b"; p-(0, .5) ="b" | |

109 | \ar @{-} "c"; p-(0, .5) ="c" | |

110 | \ar @{-} "d"; p-(0, .5) ="d" | |

111 | } | |

112 | ||

113 | \def\figiround#1#2#3#4#5{% | |

114 | \ar @{.} "a"-(0.5, 0); p+(8, 0)% | |

115 | \POS "a"+(8, -1.75) *[r]\txt{#5}% | |

116 | \figkeymix{#1}{#2}{#3}{#4}% | |

117 | \figilintrans% | |

118 | \figmatrix% | |

119 | \ar @{-} "m"+D-(3, 0); p-(0, .5) ="a" | |

120 | \ar @{-} "m"+D-(1, 0); p-(0, .5) ="b" | |

121 | \ar @{-} "m"+D+(1, 0); p-(0, .5) ="c" | |

122 | \ar @{-} "m"+D+(3, 0); p-(0, .5) ="d" | |

123 | } | |

124 | ||

125 | \def\figgap{% | |

126 | \ar @{.} "a"-(0.5, 0); p+(8, 0) | |

127 | \POS "a"+(8, -1)*[r]\txt{Six more rounds} | |

128 | \ar @{--} "a"; "a"-(0, 2) ="a" | |

129 | \ar @{--} "b"; "b"-(0, 2) ="b" | |

130 | \ar @{--} "c"; "c"-(0, 2) ="c" | |

131 | \ar @{--} "d"; "d"-(0, 2) ="d" | |

132 | } | |

133 | ||

31b692a0 | 134 | \def\figwhite#1#2#3#4#5{% |

e6e0e332 MW |
135 | \ar @{.} "a"-(0.5, 0); p+(8, 0) |

136 | \POS "a"+(8, -1)*[r]\txt{Postwhitening} | |

137 | \figkeymix{#1}{#2}{#3}{#4} | |

31b692a0 MW |
138 | \ar "a"; p-(0, 1) *+{a#5} |

139 | \ar "b"; p-(0, 1) *+{b#5} | |

140 | \ar "c"; p-(0, 1) *+{c#5} | |

141 | \ar "d"; p-(0, 1) *+{d#5} | |

e6e0e332 MW |
142 | } |

143 | ||

144 | \begin{document} | |

145 | \maketitle | |

146 | ||

147 | %%%----- The main text ------------------------------------------------------ | |

148 | ||

149 | \begin{abstract} | |

150 | We present Storin: a new 96-bit block cipher designed to play to the | |

151 | strengths of current digital signal processors (DSPs). In particular, DSPs | |

152 | tend to provide single-cycle multiply-and-accumulate operations, making | |

153 | matrix multiplications very cheap. Working in an environment where | |

154 | multiplication is as fast as exclusive-or changes the usual perceptions | |

155 | about which operations provide good cryptographic strength cheaply. The | |

156 | scarcity of available memory, for code and for tables, and a penalty for | |

157 | nonsequential access to data also make traditional block ciphers based | |

158 | around substitution tables unsuitable. | |

159 | \end{abstract} | |

160 | ||

161 | \tableofcontents | |

162 | ||

163 | \section{Definition of the cipher} | |

164 | ||

165 | \subsection{Overview} | |

166 | ||

167 | Storin is an eight-round SP network operating on 96-bit blocks. The block | |

168 | cipher uses 36 24-bit subkey words, derived from a user key by the key | |

169 | schedule. | |

170 | ||

171 | The 96-bit input is split into four 24-bit words. Each round then processes | |

172 | these four words, using the following three steps: | |

173 | \begin{enumerate} | |

174 | \item Mixing in of some key material. Four 24-bit subkey words are XORed | |

175 | with the four data words. | |

176 | \item A matrix multiplication mod $2^{24}$. The four words are treated as a | |

177 | column vector and premultiplied by a $4 \times 4$ vector using addition and | |

178 | multiplication mod $2^{24}$. This is the main nonlinear step in the | |

179 | cipher, and it also provides most of the cipher's diffusion. | |

180 | \item A simple linear transformation, which replaces each word $x$ by $x \xor | |

181 | (x \lsr 12)$. | |

182 | \end{enumerate} | |

183 | The four data words output by the final round are XORed with the last four | |

184 | subkey words in a final postwhitening stage and combined to form the 96-bit | |

185 | ciphertext. | |

186 | ||

187 | The cipher structure is shown diagrammatically in figure~\ref{fig:cipher}. | |

188 | ||

189 | \begin{figure} | |

190 | \centering | |

191 | \leavevmode | |

192 | \begin{xy} | |

193 | \xycompile{ | |

31b692a0 | 194 | \figstart{} |

e6e0e332 MW |
195 | \figround{0}{1}{2}{3}{Round 1} |

196 | \figround{4}{5}{6}{7}{Round 2} | |

197 | \figgap | |

31b692a0 | 198 | \figwhite{32}{33}{34}{35}{'}} |

e6e0e332 MW |
199 | \end{xy} |

200 | \caption{The Storin encryption function} | |

201 | \label{fig:cipher} | |

202 | \end{figure} | |

203 | ||

204 | Since the matrix used in step 2 is chosen to be invertible, the cipher can be | |

205 | inverted readily, simply by performing the inverse steps in the reverse | |

206 | order. Since the postwhitening stage is the same as a key mixing stage, | |

207 | decryption can be viewed as eight rounds consisting of key mixing, linear | |

208 | transformation and matrix multiplication, followed by a postwhitening stage. | |

209 | Thus, the structure of the inverse cipher is very similar to the forwards | |

210 | cipher, and uses the same components. The decryption function is shown | |

211 | diagrammatically in figure~\ref{fig:decipher}. | |

212 | ||

213 | \begin{figure} | |

214 | \centering | |

215 | \leavevmode | |

216 | \begin{xy} | |

217 | \xycompile{ | |

31b692a0 | 218 | \figstart{'} |

e6e0e332 MW |
219 | \figiround{32}{33}{34}{35}{Round 1} |

220 | \figiround{28}{29}{30}{31}{Round 2} | |

221 | \figgap | |

31b692a0 | 222 | \figwhite{0}{1}{2}{3}{}} |

e6e0e332 MW |
223 | \end{xy} |

224 | \caption{The Storin decryption function} | |

225 | \label{fig:decipher} | |

226 | \end{figure} | |

227 | ||

228 | The key schedule is designed to be simple and to reuse the cipher components | |

229 | already available. Given a user key, which is a sequence of one or more | |

230 | 24-bit words, it produces the 36 subkey words required by the cipher. The | |

231 | key schedule is very similar to Blowfish \cite{blowfish}. The subkey array | |

232 | is assigned an initial constant value derived from the matrix used in the | |

233 | cipher. Words from the user key are XORed into the array, starting from the | |

234 | beginning, and restarting from the beginning of the user key when all the | |

235 | user key words are exhausted. A 96-bit block is initialized to zero, and | |

236 | enciphered with Storin, using the subkeys currently in the array. The first | |

237 | four subkey words are then replaced with the resulting ciphertext, which is | |

238 | then encrypted again using the new subkeys. The next four subkey words are | |

239 | replaced with the ciphertext, and the process continues, nine times in all, | |

240 | until all of the subkey words have been replaced. | |

241 | ||

4643f89a MW |
242 | The Storin key schedule can in theory accept user keys up to 36 words (864 |

243 | bits) long. However, there are possible security problems with keys shorter | |

244 | than 28 words (672 bits). We believe that it's unrealistic to expect this | |

245 | much strength from the cipher and recommend against using keys longer than 5 | |

246 | words (120 bits). | |

e6e0e332 MW |
247 | |

248 | ||

249 | \subsection{Encryption} | |

250 | ||

251 | We define $\mathcal{W} = \mathbb{Z}_{2^{24}}$ to be set of 24-bit words, and | |

252 | $\mathcal{P} = \mathcal{W}^4$ to be the set of four-entry column vectors over | |

253 | $\mathcal{W}$. Storin plaintext blocks are members of $\mathcal{P}$. | |

254 | ||

255 | The Storin encryption function uses 36 24-bit words of key material $k_0$, | |

256 | $k_1$, \ldots, $k_{35}$, which are produced from the user key by the key | |

257 | schedule, described below. The key-mixing operation $K_i: \mathcal{P} | |

258 | \rightarrow \mathcal{P}$ is defined for $0 \le i < 9$ by: | |

259 | \[ | |

260 | K_i \begin{pmatrix} a \\ b \\ c \\d \end{pmatrix} | |

261 | = | |

262 | \begin{pmatrix} | |

263 | a \xor k_{4i} \\ b \xor k_{4i+1} \\ c \xor k_{4i+2} \\ d \xor k_{4i+3} | |

264 | \end{pmatrix} | |

265 | \] | |

266 | ||

267 | The matrix multiplication operation $M: \mathcal{P} \to \mathcal{P}$ | |

268 | is described by $M(\mathbf{x}) = \mathbf{M} \mathbf{x}$, where $\mathbf{M}$ | |

269 | is a fixed invertible $4 \times 4$ matrix over $\mathcal{W}$. The value of | |

270 | $\mathbf{M}$ is defined below. | |

271 | ||

272 | The linear transformation $L: \mathcal{P} \to \mathcal{P}$ is defined by: | |

273 | \[ | |

274 | L \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} | |

275 | = | |

276 | \begin{pmatrix} | |

277 | a \xor (a \lsr 12) \\ | |

278 | b \xor (b \lsr 12) \\ | |

279 | c \xor (c \lsr 12) \\ | |

280 | d \xor (d \lsr 12) | |

281 | \end{pmatrix} | |

282 | \] | |

283 | ||

284 | The round function $R_i: \mathcal{P} \to \mathcal{P}$ is defined for $0 \le i | |

285 | < 8$ by | |

286 | \[ R_i(\mathbf{x}) = L\bigl(\mathbf{M} K_i(\mathbf{x}) \bigr) \] | |

287 | ||

288 | The cipher $C: \mathcal{P} \to \mathcal{P}$ is defined in terms of $R_i$ and | |

289 | $K_i$. Let $\mathbf{x}_0 \in \mathcal{P}$ be a plaintext vector. Let | |

290 | $\mathbf{x}_{i+1} = R_i(\mathbf{x}_i)$ for $0 \le i < 8$. Then we define | |

291 | $C(\mathbf{x})$ by setting $C(\mathbf{x}_0) = K_8(\mathbf{x}_8)$. | |

292 | ||

293 | ||

294 | \subsection{Key schedule} | |

295 | ||

296 | The key schedule converts a user key, which is a sequence of 24-bit words, | |

297 | into the 36 subkeys required by the cipher. | |

298 | ||

299 | For $i \ge 0$, we define that | |

300 | \[ | |

301 | \begin{pmatrix} | |

302 | m_{16i + 0} & m_{16i + 1} & m_{16i + 2} & m_{16i + 3} \\ | |

303 | m_{16i + 4} & m_{16i + 5} & m_{16i + 6} & m_{16i + 7} \\ | |

304 | m_{16i + 8} & m_{16i + 9} & m_{16i + 10} & m_{16i + 11} \\ | |

305 | m_{16i + 12} & m_{16i + 13} & m_{16i + 14} & m_{16i + 15} | |

306 | \end{pmatrix} | |

307 | = \mathbf{M}^{i + 2} | |

308 | \] | |

309 | ||

310 | Let the user-supplied key be $u_0$, $u_1$, \ldots, $u_{n-1}$, for some $n > | |

311 | 0$. We define the sequence $z_0$, $z_1$, \ldots\ by | |

312 | \[ z_i = m_i \xor u_{i \bmod n} \] | |

313 | for $i \ge 0$. | |

314 | ||

315 | Denote the result of encrypting vector $\mathbf{x}$ using subkeys from the | |

316 | sequence $\seq{w} = w_0, w_1, \ldots, w_{35}$ as $C_{\seq{w}}(\mathbf{x})$. | |

317 | We define the key schedule to be $k_0$, $k_1$, \ldots, $k_{35}$, where: | |

318 | \begin{eqlines*} | |

319 | \seq{p^{(i)}} = k_0, k_1, \ldots, k_{4i-1}, z_{4i}, z_{4i+1}, \ldots \\ | |

320 | \mathbf{x}_0 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}; \qquad | |

321 | \begin{pmatrix} k_{4i} \\ k_{4i+1} \\ k_{4i+2} \\ k_{4i+3} \end{pmatrix} | |

322 | = \mathbf{x}_{i+1} = C_{\seq{p^{(i)}}}(\mathbf{x}_i) | |

323 | \end{eqlines*} | |

324 | ||

325 | ||

326 | \subsection{Decryption} | |

327 | ||

328 | The individual operations used during encryption are all invertible. Key | |

329 | mixing is inverted by taking keys from the other end of the array: | |

330 | \[ K^{-1}_i(\mathbf{x}) = K_{8-i}(\mathbf{x}) \] | |

331 | The matrix multiplication may be inverted simply by using the inverse matrix | |

332 | $\mathbf{M}^{-1}$: | |

333 | \[ M^{-1}(\mathbf{x}) = \mathbf{M}^{-1} \mathbf{x} \] | |

334 | Finally, the linear transformation is its own inverse: | |

335 | \[ L^{-1}(\mathbf{x}) = L(\mathbf{x}) \] | |

336 | The inverse round function can now be defined as: | |

337 | \[ R^{-1}_i(\mathbf{x}) = | |

338 | \mathbf{M}^{-1} L\bigl(K^{-1}_i(\mathbf{x})\bigr) \] | |

339 | ||

340 | The decryption function $C^{-1}: \mathcal{P} \to \mathcal{P}$ is defined | |

341 | in terms of $R^{-1}$ and $K^{-1}$ in a very similar way to encryption. Let | |

342 | $\mathbf{x}_0$ be a ciphertext vector. Let $\mathbf{x}_{i+1} = | |

343 | R^{-1}_i(\mathbf{x}_i)$ for $0 \le i < 8$. Then we define | |

344 | $C^{-1}(\mathbf{x}_0) = K^{-1}_8(\mathbf{x}_8)$. | |

345 | ||

346 | ||

347 | \subsection{Constants} | |

348 | ||

349 | The matrix $\mathbf{M}$ and its inverse $\mathbf{M}^{-1}$ are: | |

350 | \begin{eqnarray*}[rl] | |

351 | \mathbf{M} = & | |

4643f89a MW |
352 | \begin{pmatrix} |

353 | \hex{f7a413} & \hex{54bd81} & \hex{447550} & \hex{ff4449} \\ | |

354 | \hex{f31e87} & \hex{d85388} & \hex{de32cb} & \hex{40e3d7} \\ | |

355 | \hex{d9db1d} & \hex{551b45} & \hex{e9d19f} & \hex{e443de} \\ | |

356 | \hex{4b949a} & \hex{4d435d} & \hex{ef0a17} & \hex{b784e1} | |

e6e0e332 MW |
357 | \end{pmatrix} \\ |

358 | \mathbf{M}^{-1} = & | |

4643f89a MW |
359 | \begin{pmatrix} |

360 | \hex{17391b} & \hex{fafb4b} & \hex{a66823} & \hex{f2efb6} \\ | |

361 | \hex{13e0e5} & \hex{2ed5e4} & \hex{b2cfff} & \hex{d9cdb5} \\ | |

362 | \hex{2af462} & \hex{33826d} & \hex{de66a1} & \hex{eb6c85} \\ | |

363 | \hex{c2f423} & \hex{e904a3} & \hex{e772d8} & \hex{d791f1} | |

e6e0e332 MW |
364 | \end{pmatrix} |

365 | \end{eqnarray*} | |

366 | ||

367 | ||

368 | ||

369 | \section{Rationale and analysis} | |

370 | ||

371 | \subsection{Design decisions} | |

372 | ||

373 | The initial objective was to produce a cipher which played to the particular | |

374 | strengths of digital signal processors. DSPs tend to have good multipliers, | |

31b692a0 | 375 | and are particularly good at matrix multiplication. The decision to use a |

e6e0e332 MW |
376 | matrix multiplication over $\mathbb{Z}_{2^{24}}$ seemed natural, given that |

377 | 24 bits is a commonly offered word size. | |

378 | ||

379 | The choice of a 96-bit block is also fairly natural. A 2 word (48-bit) block | |

380 | is clearly too small, and a 3 word (72-bit) block is a little on the small | |

381 | side too. | |

382 | ||

383 | ||

384 | \subsection{Matrix multiplication over $\mathbb{Z}_{2^{24}}$} | |

385 | ||

386 | Integer multiplication on a DSP is a cheap source of nonlinearity. Note that | |

387 | bit $i$ of the result depends on all of the bits in the operands of lesser or | |

388 | equal significance.position $i$ downwards. | |

389 | ||

390 | The decision to make the $4 \times 4$ matrix fixed was taken fairly early on. | |

391 | Generating invertible matrices from key material seemed like too much work to | |

392 | expect from the DSP. | |

393 | ||

394 | The matrix is generated pseudorandomly from a seed string, using SHA-1. The | |

395 | criteria we used to choose the matrix are: | |

396 | \begin{enumerate} | |

397 | \item The matrix must be invertible. | |

398 | \item Exactly one entry in each row and column of the matrix must be even. | |

399 | \end{enumerate} | |

400 | Criterion 1 is obvious. Criterion 2 encourages diffusion between the entries | |

401 | in the block vector. Note that if a matrix satisfies the second criterion, | |

402 | its inverse also does. | |

403 | ||

404 | Consider a vector $\mathbf{x}$ and its product with the matrix $\mathbf{M} | |

405 | \mathbf{x}$. Whether the top bit of entry $i$ in $\mathbf{x}$ affects | |

406 | entry $j$ in the product depends on whether the entry in row $j$, column $i$ | |

407 | of $\mathbf{M}$ is even. Criterion 2 ensures the following: | |

408 | \begin{itemize} | |

4643f89a | 409 | \item A top-bit change in a single word affects three words in the output. |

e6e0e332 MW |
410 | \item A top-bit change in two words affects two words in the output. |

411 | \end{itemize} | |

412 | ||

413 | The seed string used is \texttt{matrix-seed-string}. The program which | |

414 | generates the matrix is included with the Storin example source code. | |

415 | ||

416 | \subsection{The linear transformation} | |

417 | ||

418 | A bit change in one of the inputs to the matrix can only affect bits at that | |

419 | position and higher in the output. The linear transformation at the end of | |

420 | the round aims to provide diffusion from the high-order bits back to the | |

421 | low-order bits. | |

422 | ||

423 | A single high-order bit change in the input to a round will affect the | |

424 | high-order bits of three words in the output of the matrix multiply. The | |

425 | linear transformation causes it to affect bits in the low halves of each of | |

426 | these words. The second round's multiplication causes these bits to affect | |

427 | the whole top halves of all of the output words. The linear transformation | |

428 | propagates this change to the bottom halves. Complete avalanche is therefore | |

429 | achieved after three rounds of Storin. | |

430 | ||

431 | ||

432 | \subsection{Key schedule notes} | |

433 | ||

434 | The key schedule is intended to be adequate for bulk encryption; it doesn't | |

4643f89a MW |
435 | provide good key agility, and isn't intended to. The key schedule accepts up |

436 | to 28 words of user key, although expecting 672 bits of security from the | |

437 | cipher is not realistic. The suggested maximum of 5 words (120 bits) seems | |

438 | more sensible. This maximum can be raised easily when our understanding of | |

439 | the cipher increases our confidence in it. | |

e6e0e332 MW |
440 | |

441 | The key schedule is strongly reminiscent of Blowfish \cite{blowfish}. Use of | |

442 | existing components of the cipher, such as the matrix multiplication and the | |

443 | cipher itself, help reduce the amount of code required in the implementation. | |

444 | ||

4643f89a MW |
445 | The restriction of the key schedule to 28 words is due to an interesting |

446 | property, also shared by Blowfish \cite{blowfish}: the output of the first | |

e6e0e332 MW |
447 | round of the second encryption is zero. To see why this is so, it is enough |

448 | to note that the first round key has just been set equal to what is now the | |

449 | plaintext; the result of the key mixing stage is zero, which is unaffected by | |

4643f89a | 450 | the matrix and linear transformation. See figure~\ref{fig:bfkeysched}. |

e6e0e332 | 451 | |

4643f89a MW |
452 | A limit of 28 words is chosen to ensure that the round-1 key affects the |

453 | round-2 key in a part of the cipher earlier than the postwhitening stage. | |

454 | ||

455 | \begin{figure} | |

456 | \centering | |

457 | \leavevmode | |

458 | \begin{xy} | |

459 | \xycompile{ | |

460 | \POS 0; <0.7cm, 0cm>: | |

461 | \POS (0, 0) ="o" +(3, 0) ="w" | |

462 | \ar "o" *+{P[0]}; p-(0, 1) *{\xor} ="x" | |

463 | \ar "x" -(1, 0) *+[l]{P[0]}; "x" | |

464 | \ar@{-} "x"; p-(0, 2) ="as" | |

465 | \ar "w" *+{P[1]}; p-(0, 2) *{\xor} ="x" | |

466 | \ar "o"-(0, 2); "x" |-*+[F]{F} | |

467 | \ar@{-} "x"; p-(0, 1) ="bs" | |

468 | \ar@{-} "as"; "bs"-(0, 1) ="w" | |

469 | \ar@{-} "bs"; "as"-(0, 1) ="o" | |

470 | \ar "o"; p-(0, 1) *+{P[1] \xor F(0)} ="x" | |

471 | \ar "x"; p-(0, 1) *{\xor} ="x" | |

472 | \ar "x" -(1, 0) *+[l]{P[1]}; "x" | |

473 | \ar "x"; p-(0, 2) *+{F(0)} | |

474 | \ar "w"; p-(0, 1) *+{0} ="x" | |

475 | \ar "x"; p-(0, 2) *{\xor} ="x" | |

476 | \ar "o"-(0, 3); "x" |-*+[F]{F} | |

477 | \ar "x"; p-(0, 1) *+{F^2(0)}} | |

478 | \end{xy} | |

479 | \caption{Blowfish key schedule: $P[2]$ and $P[3]$ don't depend on $P[0]$ and | |

480 | $P[1]$.} | |

481 | \label{fig:bfkeysched} | |

482 | \end{figure} | |

e6e0e332 MW |
483 | |

484 | \subsection{Attacking Storin} | |

485 | ||

486 | A brief\footnote{About three days' worth on a 300MHz Pentium II.} | |

487 | computerized analysis of the matrix multiplication failed to turn up any | |

488 | high-probability differential characteristics. While an exhaustive search | |

489 | was clearly not possible, the program tested all differentials of Hamming | |

490 | weight 5 or less, and then random differentials, applying each to a suite of | |

491 | $2^{13}$ different 96-bit inputs chosen at random. No output difference was | |

492 | noted more than once. | |

493 | ||

4643f89a MW |
494 | There is a two-round truncated differential \cite{storin-tdiff}, which can be |

495 | used to break Storin reduced to only 2 rounds. The differential | |

496 | \[ (\hex{800000}, \hex{800000}, \hex{800000}, 0) \to | |

497 | (0, 0, \hex{800000}, 0) \] | |

498 | holds with probability 1 through the matrix multiplication. | |

499 | Differentials in the linear transform are easy to find; for example: | |

500 | \[ (0, 0, \hex{800000}, 0) \to (0, 0, \hex{800800}, 0) \] | |

501 | We can continue through the second round's matrix multiplication with a | |

502 | truncated differential, again with probability 1: | |

503 | \[ (0, 0, \hex{800800}, 0) \to | |

504 | (\hex{???000}, \hex{???800}, \hex{???800}, \hex{???800}) \] | |

505 | The following linear transform can be commuted with the postwhitening by | |

506 | applying a trivial reversible transformation to the postwhitening keys, and | |

507 | we can apply it to the ciphertext. If we do this, we can combine the | |

508 | differentials above to construct a probability-1 characteristic for a 2-round | |

509 | variant of Storin: | |

510 | \[ (\hex{800000}, \hex{800000}, \hex{800000}, 0) \to | |

511 | (\hex{???000}, \hex{???800}, \hex{???800}, \hex{???800}) \] | |

512 | This characteristic is non-iterative, and can't be extended to more rounds. | |

513 | ||

514 | In \cite{storin-collide}, Matthew Fisher speculates on breaking 2 rounds of | |

515 | Storin by forcing collisions in the matrix multiplication outputs. This | |

516 | attack doesn't extend to more than two rounds either. | |

517 | ||

e6e0e332 MW |
518 | One possible avenue of attack worth exploring is to attempt to cause zero |

519 | words to be input into the first-round matrix by choosing plaintext words | |

520 | identical to subkey words for the first round. Causing $n$ matrix input | |

521 | words to be zero clearly takes $O(2^{24n})$ time. If a method can be found | |

522 | to detect when zero words have been input to the matrix, this can be used to | |

523 | discover the subkey words rather more rapidly than exhaustive search. We | |

524 | can't see a way to exploit this at the moment, but it could be a fruitful | |

525 | place to look for cryptanalysis. | |

526 | ||

527 | ||

528 | \section{Conclusion} | |

529 | ||

530 | We have presented a new block cipher, Storin. Any cryptanalysis will be | |

531 | received with interest. | |

532 | ||

533 | ||

534 | \begin{thebibliography}{99} | |

4643f89a MW |
535 | \bibitem{storin-collide} M. Fisher, `Yet another block cipher: Storin', |

536 | sci.crypt article, message-id \texttt{<8gjctn\$9ct\$1@nnrp1.deja.com>} | |

537 | \bibitem{idea} X. Lai, `On the Design and Security of Block Ciphers', ETH | |

538 | Series in Informatics Processing, J. L. Massey (editor), vol. 1, | |

539 | Hartung-Gorre Verlag Konstanz, Technische Hochschule (Zurich), 1992 | |

540 | \bibitem{blowfish} B. Schneier, `The Blowfish Encryption Algorithm', | |

541 | \textit{Dr Dobb's Journal}, vol. 19 no. 4, April 1994, pp. 38--40 | |

542 | \bibitem{storin-tdiff} M. D. Wooding, `Yet another block cipher: Storin', | |

543 | sci.crypt article, message-id | |

544 | \texttt{<slrn8iqhaq.872.mdw@mull.ncipher.com>} | |

e6e0e332 MW |
545 | \end{thebibliography} |

546 | ||

547 | %%%----- That's all, folks -------------------------------------------------- | |

548 | ||

549 | \end{document} | |

550 | ||

551 | %%% Local Variables: | |

552 | %%% mode: latex | |

553 | %%% TeX-master: t | |

554 | %%% End: |