projects / u / mdw / catacomb / blob
? search:


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