projects / u / mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Rearrange the file tree.
[u/mdw/catacomb] / symm / twofish.c
1 /* -*-c-*-
2 *
3 * Implementation of the Twofish cipher
4 *
5 * (c) 2000 Straylight/Edgeware
6 */
7
8 /*----- Licensing notice --------------------------------------------------*
9 *
10 * This file is part of Catacomb.
11 *
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
16 *
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
21 *
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 * MA 02111-1307, USA.
26 */
27
28 /*----- Header files ------------------------------------------------------*/
29
30 #include <assert.h>
31
32 #include <mLib/bits.h>
33
34 #include "blkc.h"
35 #include "gcipher.h"
36 #include "twofish.h"
37 #include "twofish-tab.h"
38 #include "paranoia.h"
39
40 /*----- Global variables --------------------------------------------------*/
41
42 const octet twofish_keysz[] = { KSZ_RANGE, TWOFISH_KEYSZ, 0, 32, 1 };
43
44 /*----- Important tables --------------------------------------------------*/
45
46 static const octet q0[256] = TWOFISH_Q0, q1[256] = TWOFISH_Q1;
47 static const uint32 qmds[4][256] = TWOFISH_QMDS;
48 static const octet rslog[] = TWOFISH_RSLOG, rsexp[] = TWOFISH_RSEXP;
49 static const octet rs[32] = TWOFISH_RS;
50
51 /*----- Key initialization ------------------------------------------------*/
52
53 /* --- @h@ --- *
54 *
55 * Arguments: @uint32 x@ = input to the function
56 * @const uint32 *l@ = key values to mix in
57 * @unsigned k@ = number of key values there are
58 *
59 * Returns: The output of the function @h@.
60 *
61 * Use: Implements the Twofish function @h@.
62 */
63
64 static uint32 h(uint32 x, const uint32 *l, unsigned k)
65 {
66 /* --- Apply a series of @q@ tables to an integer --- */
67
68 # define Q(x, qa, qb, qc, qd) \
69 ((qa[((x) >> 0) & 0xff] << 0) | \
70 (qb[((x) >> 8) & 0xff] << 8) | \
71 (qc[((x) >> 16) & 0xff] << 16) | \
72 (qd[((x) >> 24) & 0xff] << 24))
73
74 /* --- Grind through the tables --- */
75
76 switch (k) {
77 case 4: x = Q(x, q1, q0, q0, q1) ^ l[3];
78 case 3: x = Q(x, q1, q1, q0, q0) ^ l[2];
79 case 2: x = Q(x, q0, q1, q0, q1) ^ l[1];
80 x = Q(x, q0, q0, q1, q1) ^ l[0];
81 break;
82 }
83
84 #undef Q
85
86 /* --- Apply the MDS matrix --- */
87
88 return (qmds[0][U8(x >> 0)] ^ qmds[1][U8(x >> 8)] ^
89 qmds[2][U8(x >> 16)] ^ qmds[3][U8(x >> 24)]);
90 }
91
92 /* --- @twofish_initfk@ --- *
93 *
94 * Arguments: @twofish_ctx *k@ = pointer to key block to fill in
95 * @const void *buf@ = pointer to buffer of key material
96 * @size_t sz@ = size of key material
97 * @const twofish_fk *fk@ = family-key information
98 *
99 * Returns: ---
100 *
101 * Use: Does the underlying Twofish key initialization with family
102 * key. Pass in a family-key structure initialized to
103 * all-bits-zero for a standard key schedule.
104 */
105
106 void twofish_initfk(twofish_ctx *k, const void *buf, size_t sz,
107 const twofish_fk *fk)
108 {
109 # define KMAX 4
110
111 uint32 mo[KMAX], me[KMAX];
112 octet s[4][KMAX];
113
114 /* --- Expand the key into the three word arrays --- */
115
116 {
117 size_t ssz;
118 const octet *p, *q;
119 octet b[32];
120 int i;
121
122 /* --- Sort out the key size --- */
123
124 KSZ_ASSERT(twofish, sz);
125 if (sz <= 16)
126 ssz = 16;
127 else if (sz <= 24)
128 ssz = 24;
129 else if (sz <= 32)
130 ssz = 32;
131 else
132 assert(((void)"This can't happen (bad key size in twofish_init)", 0));
133
134 /* --- Extend the key if necessary --- */
135
136 if (sz == ssz)
137 p = buf;
138 else {
139 memcpy(b, buf, sz);
140 memset(b + sz, 0, ssz - sz);
141 p = b;
142 }
143
144 /* --- Finally get the word count --- */
145
146 sz = ssz / 8;
147
148 /* --- Extract words from the key --- *
149 *
150 * The @s@ table, constructed using the Reed-Solomon matrix, is cut into
151 * sequences of bytes, since this is actually more useful for computing
152 * the S-boxes.
153 */
154
155 q = p;
156 for (i = 0; i < sz; i++) {
157 octet ss[4];
158 const octet *r = rs;
159 int j;
160
161 /* --- Extract the easy subkeys --- */
162
163 me[i] = LOAD32_L(q) ^ fk->t0[2 * i];
164 mo[i] = LOAD32_L(q + 4) ^ fk->t0[2 * i + 1];
165
166 /* --- Now do the Reed-Solomon thing --- */
167
168 for (j = 0; j < 4; j++) {
169 const octet *qq = q;
170 unsigned a = 0;
171 int k;
172
173 for (k = 0; k < 8; k++) {
174 unsigned char x = *qq ^ fk->t1[i * 8 + k];
175 if (x) a ^= rsexp[rslog[x] + *r];
176 qq++;
177 r++;
178 }
179
180 s[j][sz - 1 - i] = ss[j] = a;
181 }
182 q += 8;
183 }
184
185 /* --- Clear away the temporary buffer --- */
186
187 if (p == b)
188 BURN(b);
189 }
190
191 /* --- Construct the expanded key --- */
192
193 {
194 uint32 p = 0x01010101;
195 uint32 ip = 0;
196 int i;
197
198 for (i = 0; i < 40; i += 2) {
199 uint32 a, b;
200 a = h(ip, me, sz);
201 b = h(ip + p, mo, sz);
202 b = ROL32(b, 8);
203 a += b; b += a;
204 k->k[i] = U32(a);
205 k->k[i + 1] = ROL32(b, 9);
206 ip += 2 * p;
207 }
208
209 for (i = 0; i < 8; i++)
210 k->k[i] ^= fk->t23[i];
211 for (i = 8; i < 40; i += 2) {
212 k->k[i] ^= fk->t4[0];
213 k->k[i + 1] ^= fk->t4[1];
214 }
215 }
216
217 /* --- Construct the S-box tables --- */
218
219 {
220 unsigned i;
221 static const octet *q[4][KMAX + 1] = {
222 { q1, q0, q0, q1, q1 },
223 { q0, q0, q1, q1, q0 },
224 { q1, q1, q0, q0, q0 },
225 { q0, q1, q1, q0, q1 }
226 };
227
228 for (i = 0; i < 4; i++) {
229 unsigned j;
230 uint32 x;
231
232 for (j = 0; j < 256; j++) {
233 x = j;
234
235 /* --- Push the byte through the q tables --- */
236
237 switch (sz) {
238 case 4: x = q[i][4][x] ^ s[i][3];
239 case 3: x = q[i][3][x] ^ s[i][2];
240 case 2: x = q[i][2][x] ^ s[i][1];
241 x = q[i][1][x] ^ s[i][0];
242 break;
243 }
244
245 /* --- Write it in the key schedule --- */
246
247 k->g[i][j] = qmds[i][x];
248 }
249 }
250 }
251
252 /* --- Clear everything away --- */
253
254 BURN(me);
255 BURN(mo);
256 BURN(s);
257 }
258
259 /* --- @twofish_init@ --- *
260 *
261 * Arguments: @twofish_ctx *k@ = pointer to key block to fill in
262 * @const void *buf@ = pointer to buffer of key material
263 * @size_t sz@ = size of key material
264 *
265 * Returns: ---
266 *
267 * Use: Initializes a Twofish key buffer. Twofish accepts key sizes
268 * of up to 256 bits (32 bytes).
269 */
270
271 void twofish_init(twofish_ctx *k, const void *buf, size_t sz)
272 {
273 static const twofish_fk fk = { { 0 } };
274 twofish_initfk(k, buf, sz, &fk);
275 }
276
277 /* --- @twofish_fkinit@ --- *
278 *
279 * Arguments: @twofish_fk *fk@ = pointer to family key block
280 * @const void *buf@ = pointer to buffer of key material
281 * @size_t sz@ = size of key material
282 *
283 * Returns: ---
284 *
285 * Use: Initializes a family-key buffer. This implementation allows
286 * family keys of any size acceptable to the Twofish algorithm.
287 */
288
289 void twofish_fkinit(twofish_fk *fk, const void *buf, size_t sz)
290 {
291 twofish_ctx k;
292 uint32 pt[4], ct[4];
293 const octet *kk;
294 unsigned i;
295
296 twofish_init(&k, buf, sz);
297
298 for (i = 0; i < 4; i++) pt[i] = (uint32)-1;
299 twofish_eblk(&k, pt, fk->t0 + 4);
300
301 kk = buf; sz /= 4;
302 for (i = 0; i < sz; i++) { fk->t0[i] = LOAD32_L(kk); kk += 4; }
303
304 for (i = 0; i < 4; i++) pt[i] = 0; twofish_eblk(&k, pt, ct);
305 for (i = 0; i < 4; i++) STORE32_L(fk->t1 + i * 4, ct[i]);
306 pt[0] = 1; twofish_eblk(&k, pt, ct);
307 for (i = 0; i < 4; i++) STORE32_L(fk->t1 + 4 + i * 4, ct[i]);
308
309 pt[0] = 2; twofish_eblk(&k, pt, fk->t23 + 0);
310 pt[0] = 3; twofish_eblk(&k, pt, fk->t23 + 4);
311 pt[0] = 4; twofish_eblk(&k, pt, ct);
312 fk->t4[0] = ct[0]; fk->t4[1] = ct[1];
313
314 BURN(k);
315 }
316
317 /*----- Main encryption ---------------------------------------------------*/
318
319 /* --- Feistel function --- */
320
321 #define GG(k, t0, t1, x, y, kk) do { \
322 t0 = (k->g[0][U8(x >> 0)] ^ \
323 k->g[1][U8(x >> 8)] ^ \
324 k->g[2][U8(x >> 16)] ^ \
325 k->g[3][U8(x >> 24)]); \
326 t1 = (k->g[1][U8(y >> 0)] ^ \
327 k->g[2][U8(y >> 8)] ^ \
328 k->g[3][U8(y >> 16)] ^ \
329 k->g[0][U8(y >> 24)]); \
330 t0 += t1; \
331 t1 += t0; \
332 t0 += kk[0]; \
333 t1 += kk[1]; \
334 } while (0)
335
336 /* --- Round operations --- */
337
338 #define EROUND(k, w, x, y, z, kk) do { \
339 uint32 _t0, _t1; \
340 GG(k, _t0, _t1, w, x, kk); \
341 kk += 2; \
342 y ^= _t0; y = ROR32(y, 1); \
343 z = ROL32(z, 1); z ^= _t1; \
344 } while (0)
345
346 #define DROUND(k, w, x, y, z, kk) do { \
347 uint32 _t0, _t1; \
348 kk -= 2; \
349 GG(k, _t0, _t1, w, x, kk); \
350 y = ROL32(y, 1); y ^= _t0; \
351 z ^= _t1; z = ROR32(z, 1); \
352 } while (0)
353
354 /* --- Complete encryption functions --- */
355
356 #define EBLK(k, a, b, c, d, w, x, y, z) do { \
357 const uint32 *_kk = k->k + 8; \
358 uint32 _a = a, _b = b, _c = c, _d = d; \
359 _a ^= k->k[0]; _b ^= k->k[1]; _c ^= k->k[2]; _d ^= k->k[3]; \
360 EROUND(k, _a, _b, _c, _d, _kk); \
361 EROUND(k, _c, _d, _a, _b, _kk); \
362 EROUND(k, _a, _b, _c, _d, _kk); \
363 EROUND(k, _c, _d, _a, _b, _kk); \
364 EROUND(k, _a, _b, _c, _d, _kk); \
365 EROUND(k, _c, _d, _a, _b, _kk); \
366 EROUND(k, _a, _b, _c, _d, _kk); \
367 EROUND(k, _c, _d, _a, _b, _kk); \
368 EROUND(k, _a, _b, _c, _d, _kk); \
369 EROUND(k, _c, _d, _a, _b, _kk); \
370 EROUND(k, _a, _b, _c, _d, _kk); \
371 EROUND(k, _c, _d, _a, _b, _kk); \
372 EROUND(k, _a, _b, _c, _d, _kk); \
373 EROUND(k, _c, _d, _a, _b, _kk); \
374 EROUND(k, _a, _b, _c, _d, _kk); \
375 EROUND(k, _c, _d, _a, _b, _kk); \
376 _c ^= k->k[4]; _d ^= k->k[5]; _a ^= k->k[6]; _b ^= k->k[7]; \
377 w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b); \
378 } while (0)
379
380 #define DBLK(k, a, b, c, d, w, x, y, z) do { \
381 const uint32 *_kk = k->k + 40; \
382 uint32 _a = a, _b = b, _c = c, _d = d; \
383 _a ^= k->k[4]; _b ^= k->k[5]; _c ^= k->k[6]; _d ^= k->k[7]; \
384 DROUND(k, _a, _b, _c, _d, _kk); \
385 DROUND(k, _c, _d, _a, _b, _kk); \
386 DROUND(k, _a, _b, _c, _d, _kk); \
387 DROUND(k, _c, _d, _a, _b, _kk); \
388 DROUND(k, _a, _b, _c, _d, _kk); \
389 DROUND(k, _c, _d, _a, _b, _kk); \
390 DROUND(k, _a, _b, _c, _d, _kk); \
391 DROUND(k, _c, _d, _a, _b, _kk); \
392 DROUND(k, _a, _b, _c, _d, _kk); \
393 DROUND(k, _c, _d, _a, _b, _kk); \
394 DROUND(k, _a, _b, _c, _d, _kk); \
395 DROUND(k, _c, _d, _a, _b, _kk); \
396 DROUND(k, _a, _b, _c, _d, _kk); \
397 DROUND(k, _c, _d, _a, _b, _kk); \
398 DROUND(k, _a, _b, _c, _d, _kk); \
399 DROUND(k, _c, _d, _a, _b, _kk); \
400 _c ^= k->k[0]; _d ^= k->k[1]; _a ^= k->k[2]; _b ^= k->k[3]; \
401 w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b); \
402 } while (0)
403
404 /* --- @twofish_eblk@, @twofish_dblk@ --- *
405 *
406 * Arguments: @const twofish_ctx *k@ = pointer to key block
407 * @const uint32 s[4]@ = pointer to source block
408 * @uint32 d[4]@ = pointer to destination block
409 *
410 * Returns: ---
411 *
412 * Use: Low-level block encryption and decryption.
413 */
414
415 void twofish_eblk(const twofish_ctx *k, const uint32 *s, uint32 *d)
416 {
417 EBLK(k, s[0], s[1], s[2], s[3], d[0], d[1], d[2], d[3]);
418 }
419
420 void twofish_dblk(const twofish_ctx *k, const uint32 *s, uint32 *d)
421 {
422 DBLK(k, s[0], s[1], s[2], s[3], d[0], d[1], d[2], d[3]);
423 }
424
425 BLKC_TEST(TWOFISH, twofish)
426
427 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)