3 * Implementation of the Twofish cipher
5 * (c) 2000 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Header files ------------------------------------------------------*/
32 #include <mLib/bits.h>
39 /*----- Global variables --------------------------------------------------*/
41 const octet twofish_keysz[] = { KSZ_RANGE, TWOFISH_KEYSZ, 0, 32, 1 };
43 /*----- Important tables --------------------------------------------------*/
45 extern const octet twofish_q0[256], twofish_q1[256];
46 extern const uint32 twofish_qmds[4][256];
47 extern const octet twofish_rslog[], twofish_rsexp[];
48 extern const octet twofish_rs[32];
52 #define QMDS twofish_qmds
53 #define RSLOG twofish_rslog
54 #define RSEXP twofish_rsexp
57 /*----- Key initialization ------------------------------------------------*/
61 * Arguments: @uint32 x@ = input to the function
62 * @const uint32 *l@ = key values to mix in
63 * @unsigned k@ = number of key values there are
65 * Returns: The output of the function @h@.
67 * Use: Implements the Twofish function @h@.
70 static uint32 h(uint32 x, const uint32 *l, unsigned k)
72 /* --- Apply a series of @q@ tables to an integer --- */
74 # define Q(x, qa, qb, qc, qd) \
75 ((qa[((x) >> 0) & 0xff] << 0) | \
76 (qb[((x) >> 8) & 0xff] << 8) | \
77 (qc[((x) >> 16) & 0xff] << 16) | \
78 (qd[((x) >> 24) & 0xff] << 24))
80 /* --- Grind through the tables --- */
83 case 4: x = Q(x, Q1, Q0, Q0, Q1) ^ l[3];
84 case 3: x = Q(x, Q1, Q1, Q0, Q0) ^ l[2];
85 case 2: x = Q(x, Q0, Q1, Q0, Q1) ^ l[1];
86 x = Q(x, Q0, Q0, Q1, Q1) ^ l[0];
92 /* --- Apply the MDS matrix --- */
94 return (QMDS[0][U8(x >> 0)] ^ QMDS[1][U8(x >> 8)] ^
95 QMDS[2][U8(x >> 16)] ^ QMDS[3][U8(x >> 24)]);
98 /* --- @twofish_initfk@ --- *
100 * Arguments: @twofish_ctx *k@ = pointer to key block to fill in
101 * @const void *buf@ = pointer to buffer of key material
102 * @size_t sz@ = size of key material
103 * @const twofish_fk *fk@ = family-key information
107 * Use: Does the underlying Twofish key initialization with family
108 * key. Pass in a family-key structure initialized to
109 * all-bits-zero for a standard key schedule.
112 void twofish_initfk(twofish_ctx *k, const void *buf, size_t sz,
113 const twofish_fk *fk)
117 uint32 mo[KMAX], me[KMAX];
120 /* --- Expand the key into the three word arrays --- */
128 /* --- Sort out the key size --- */
130 KSZ_ASSERT(twofish, sz);
138 assert(((void)"This can't happen (bad key size in twofish_init)", 0));
140 /* --- Extend the key if necessary --- */
146 memset(b + sz, 0, ssz - sz);
150 /* --- Finally get the word count --- */
154 /* --- Extract words from the key --- *
156 * The @s@ table, constructed using the Reed-Solomon matrix, is cut into
157 * sequences of bytes, since this is actually more useful for computing
162 for (i = 0; i < sz; i++) {
167 /* --- Extract the easy subkeys --- */
169 me[i] = LOAD32_L(q) ^ fk->t0[2 * i];
170 mo[i] = LOAD32_L(q + 4) ^ fk->t0[2 * i + 1];
172 /* --- Now do the Reed-Solomon thing --- */
174 for (j = 0; j < 4; j++) {
179 for (k = 0; k < 8; k++) {
180 unsigned char x = *qq ^ fk->t1[i * 8 + k];
181 if (x) a ^= RSEXP[RSLOG[x] + *r];
186 s[j][sz - 1 - i] = ss[j] = a;
191 /* --- Clear away the temporary buffer --- */
197 /* --- Construct the expanded key --- */
200 uint32 p = 0x01010101;
204 for (i = 0; i < 40; i += 2) {
207 b = h(ip + p, mo, sz);
211 k->k[i + 1] = ROL32(b, 9);
215 for (i = 0; i < 8; i++)
216 k->k[i] ^= fk->t23[i];
217 for (i = 8; i < 40; i += 2) {
218 k->k[i] ^= fk->t4[0];
219 k->k[i + 1] ^= fk->t4[1];
223 /* --- Construct the S-box tables --- */
227 static const octet *q[4][KMAX + 1] = {
228 { Q1, Q0, Q0, Q1, Q1 },
229 { Q0, Q0, Q1, Q1, Q0 },
230 { Q1, Q1, Q0, Q0, Q0 },
231 { Q0, Q1, Q1, Q0, Q1 }
234 for (i = 0; i < 4; i++) {
238 for (j = 0; j < 256; j++) {
241 /* --- Push the byte through the q tables --- */
244 case 4: x = q[i][4][x] ^ s[i][3];
245 case 3: x = q[i][3][x] ^ s[i][2];
246 case 2: x = q[i][2][x] ^ s[i][1];
247 x = q[i][1][x] ^ s[i][0];
251 /* --- Write it in the key schedule --- */
253 k->g[i][j] = QMDS[i][x];
258 /* --- Clear everything away --- */
265 /* --- @twofish_init@ --- *
267 * Arguments: @twofish_ctx *k@ = pointer to key block to fill in
268 * @const void *buf@ = pointer to buffer of key material
269 * @size_t sz@ = size of key material
273 * Use: Initializes a Twofish key buffer. Twofish accepts key sizes
274 * of up to 256 bits (32 bytes).
277 void twofish_init(twofish_ctx *k, const void *buf, size_t sz)
279 static const twofish_fk fk = { { 0 } };
280 twofish_initfk(k, buf, sz, &fk);
283 /* --- @twofish_fkinit@ --- *
285 * Arguments: @twofish_fk *fk@ = pointer to family key block
286 * @const void *buf@ = pointer to buffer of key material
287 * @size_t sz@ = size of key material
291 * Use: Initializes a family-key buffer. This implementation allows
292 * family keys of any size acceptable to the Twofish algorithm.
295 void twofish_fkinit(twofish_fk *fk, const void *buf, size_t sz)
302 twofish_init(&k, buf, sz);
304 for (i = 0; i < 4; i++) pt[i] = (uint32)-1;
305 twofish_eblk(&k, pt, fk->t0 + 4);
308 for (i = 0; i < sz; i++) { fk->t0[i] = LOAD32_L(kk); kk += 4; }
310 for (i = 0; i < 4; i++) pt[i] = 0;
311 twofish_eblk(&k, pt, ct);
312 for (i = 0; i < 4; i++) STORE32_L(fk->t1 + i * 4, ct[i]);
313 pt[0] = 1; twofish_eblk(&k, pt, ct);
314 for (i = 0; i < 4; i++) STORE32_L(fk->t1 + 4 + i * 4, ct[i]);
316 pt[0] = 2; twofish_eblk(&k, pt, fk->t23 + 0);
317 pt[0] = 3; twofish_eblk(&k, pt, fk->t23 + 4);
318 pt[0] = 4; twofish_eblk(&k, pt, ct);
319 fk->t4[0] = ct[0]; fk->t4[1] = ct[1];
324 /*----- Main encryption ---------------------------------------------------*/
326 /* --- Feistel function --- */
328 #define GG(k, t0, t1, x, y, kk) do { \
329 t0 = (k->g[0][U8(x >> 0)] ^ \
330 k->g[1][U8(x >> 8)] ^ \
331 k->g[2][U8(x >> 16)] ^ \
332 k->g[3][U8(x >> 24)]); \
333 t1 = (k->g[1][U8(y >> 0)] ^ \
334 k->g[2][U8(y >> 8)] ^ \
335 k->g[3][U8(y >> 16)] ^ \
336 k->g[0][U8(y >> 24)]); \
343 /* --- Round operations --- */
345 #define EROUND(k, w, x, y, z, kk) do { \
347 GG(k, _t0, _t1, w, x, kk); \
349 y ^= _t0; y = ROR32(y, 1); \
350 z = ROL32(z, 1); z ^= _t1; \
353 #define DROUND(k, w, x, y, z, kk) do { \
356 GG(k, _t0, _t1, w, x, kk); \
357 y = ROL32(y, 1); y ^= _t0; \
358 z ^= _t1; z = ROR32(z, 1); \
361 /* --- Complete encryption functions --- */
363 #define EBLK(k, a, b, c, d, w, x, y, z) do { \
364 const uint32 *_kk = k->k + 8; \
365 uint32 _a = a, _b = b, _c = c, _d = d; \
366 _a ^= k->k[0]; _b ^= k->k[1]; _c ^= k->k[2]; _d ^= k->k[3]; \
367 EROUND(k, _a, _b, _c, _d, _kk); \
368 EROUND(k, _c, _d, _a, _b, _kk); \
369 EROUND(k, _a, _b, _c, _d, _kk); \
370 EROUND(k, _c, _d, _a, _b, _kk); \
371 EROUND(k, _a, _b, _c, _d, _kk); \
372 EROUND(k, _c, _d, _a, _b, _kk); \
373 EROUND(k, _a, _b, _c, _d, _kk); \
374 EROUND(k, _c, _d, _a, _b, _kk); \
375 EROUND(k, _a, _b, _c, _d, _kk); \
376 EROUND(k, _c, _d, _a, _b, _kk); \
377 EROUND(k, _a, _b, _c, _d, _kk); \
378 EROUND(k, _c, _d, _a, _b, _kk); \
379 EROUND(k, _a, _b, _c, _d, _kk); \
380 EROUND(k, _c, _d, _a, _b, _kk); \
381 EROUND(k, _a, _b, _c, _d, _kk); \
382 EROUND(k, _c, _d, _a, _b, _kk); \
383 _c ^= k->k[4]; _d ^= k->k[5]; _a ^= k->k[6]; _b ^= k->k[7]; \
384 w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b); \
387 #define DBLK(k, a, b, c, d, w, x, y, z) do { \
388 const uint32 *_kk = k->k + 40; \
389 uint32 _a = a, _b = b, _c = c, _d = d; \
390 _a ^= k->k[4]; _b ^= k->k[5]; _c ^= k->k[6]; _d ^= k->k[7]; \
391 DROUND(k, _a, _b, _c, _d, _kk); \
392 DROUND(k, _c, _d, _a, _b, _kk); \
393 DROUND(k, _a, _b, _c, _d, _kk); \
394 DROUND(k, _c, _d, _a, _b, _kk); \
395 DROUND(k, _a, _b, _c, _d, _kk); \
396 DROUND(k, _c, _d, _a, _b, _kk); \
397 DROUND(k, _a, _b, _c, _d, _kk); \
398 DROUND(k, _c, _d, _a, _b, _kk); \
399 DROUND(k, _a, _b, _c, _d, _kk); \
400 DROUND(k, _c, _d, _a, _b, _kk); \
401 DROUND(k, _a, _b, _c, _d, _kk); \
402 DROUND(k, _c, _d, _a, _b, _kk); \
403 DROUND(k, _a, _b, _c, _d, _kk); \
404 DROUND(k, _c, _d, _a, _b, _kk); \
405 DROUND(k, _a, _b, _c, _d, _kk); \
406 DROUND(k, _c, _d, _a, _b, _kk); \
407 _c ^= k->k[0]; _d ^= k->k[1]; _a ^= k->k[2]; _b ^= k->k[3]; \
408 w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b); \
411 /* --- @twofish_eblk@, @twofish_dblk@ --- *
413 * Arguments: @const twofish_ctx *k@ = pointer to key block
414 * @const uint32 s[4]@ = pointer to source block
415 * @uint32 d[4]@ = pointer to destination block
419 * Use: Low-level block encryption and decryption.
422 void twofish_eblk(const twofish_ctx *k, const uint32 *s, uint32 *d)
424 EBLK(k, s[0], s[1], s[2], s[3], d[0], d[1], d[2], d[3]);
427 void twofish_dblk(const twofish_ctx *k, const uint32 *s, uint32 *d)
429 DBLK(k, s[0], s[1], s[2], s[3], d[0], d[1], d[2], d[3]);
432 BLKC_TEST(TWOFISH, twofish)
434 /*----- That's all, folks -------------------------------------------------*/