3 * $Id: twofish.c,v 1.4 2004/04/02 01:03:49 mdw Exp $
5 * Implementation of the Twofish cipher
7 * (c) 2000 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.4 2004/04/02 01:03:49 mdw
34 * Miscellaneous constification.
36 * Revision 1.3 2002/01/13 13:37:59 mdw
37 * Add support for Twofish family keys.
39 * Revision 1.2 2000/06/22 18:58:00 mdw
40 * Twofish can handle keys with any byte-aligned size.
42 * Revision 1.1 2000/06/17 12:10:17 mdw
47 /*----- Header files ------------------------------------------------------*/
51 #include <mLib/bits.h>
56 #include "twofish-tab.h"
59 /*----- Global variables --------------------------------------------------*/
61 const octet twofish_keysz
[] = { KSZ_RANGE
, TWOFISH_KEYSZ
, 0, 32, 1 };
63 /*----- Important tables --------------------------------------------------*/
65 static const octet q0
[256] = TWOFISH_Q0
, q1
[256] = TWOFISH_Q1
;
66 static const uint32 qmds
[4][256] = TWOFISH_QMDS
;
67 static const octet rslog
[] = TWOFISH_RSLOG
, rsexp
[] = TWOFISH_RSEXP
;
68 static const octet rs
[32] = TWOFISH_RS
;
70 /*----- Key initialization ------------------------------------------------*/
74 * Arguments: @uint32 x@ = input to the function
75 * @const uint32 *l@ = key values to mix in
76 * @unsigned k@ = number of key values there are
78 * Returns: The output of the function @h@.
80 * Use: Implements the Twofish function @h@.
83 static uint32
h(uint32 x
, const uint32
*l
, unsigned k
)
85 /* --- Apply a series of @q@ tables to an integer --- */
87 # define Q(x, qa, qb, qc, qd) \
88 ((qa[((x) >> 0) & 0xff] << 0) | \
89 (qb[((x) >> 8) & 0xff] << 8) | \
90 (qc[((x) >> 16) & 0xff] << 16) | \
91 (qd[((x) >> 24) & 0xff] << 24))
93 /* --- Grind through the tables --- */
96 case 4: x
= Q(x
, q1
, q0
, q0
, q1
) ^ l
[3];
97 case 3: x
= Q(x
, q1
, q1
, q0
, q0
) ^ l
[2];
98 case 2: x
= Q(x
, q0
, q1
, q0
, q1
) ^ l
[1];
99 x
= Q(x
, q0
, q0
, q1
, q1
) ^ l
[0];
105 /* --- Apply the MDS matrix --- */
107 return (qmds
[0][U8(x
>> 0)] ^ qmds
[1][U8(x
>> 8)] ^
108 qmds
[2][U8(x
>> 16)] ^ qmds
[3][U8(x
>> 24)]);
111 /* --- @twofish_initfk@ --- *
113 * Arguments: @twofish_ctx *k@ = pointer to key block to fill in
114 * @const void *buf@ = pointer to buffer of key material
115 * @size_t sz@ = size of key material
116 * @const twofish_fk *fk@ = family-key information
120 * Use: Does the underlying Twofish key initialization with family
121 * key. Pass in a family-key structure initialized to
122 * all-bits-zero for a standard key schedule.
125 void twofish_initfk(twofish_ctx
*k
, const void *buf
, size_t sz
,
126 const twofish_fk
*fk
)
130 uint32 mo
[KMAX
], me
[KMAX
];
133 /* --- Expand the key into the three word arrays --- */
141 /* --- Sort out the key size --- */
143 KSZ_ASSERT(twofish
, sz
);
151 assert(((void)"This can't happen (bad key size in twofish_init)", 0));
153 /* --- Extend the key if necessary --- */
159 memset(b
+ sz
, 0, ssz
- sz
);
163 /* --- Finally get the word count --- */
167 /* --- Extract words from the key --- *
169 * The @s@ table, constructed using the Reed-Solomon matrix, is cut into
170 * sequences of bytes, since this is actually more useful for computing
175 for (i
= 0; i
< sz
; i
++) {
180 /* --- Extract the easy subkeys --- */
182 me
[i
] = LOAD32_L(q
) ^ fk
->t0
[2 * i
];
183 mo
[i
] = LOAD32_L(q
+ 4) ^ fk
->t0
[2 * i
+ 1];
185 /* --- Now do the Reed-Solomon thing --- */
187 for (j
= 0; j
< 4; j
++) {
192 for (k
= 0; k
< 8; k
++) {
193 unsigned char x
= *qq
^ fk
->t1
[i
* 8 + k
];
194 if (x
) a
^= rsexp
[rslog
[x
] + *r
];
199 s
[j
][sz
- 1 - i
] = ss
[j
] = a
;
204 /* --- Clear away the temporary buffer --- */
210 /* --- Construct the expanded key --- */
213 uint32 p
= 0x01010101;
217 for (i
= 0; i
< 40; i
+= 2) {
220 b
= h(ip
+ p
, mo
, sz
);
224 k
->k
[i
+ 1] = ROL32(b
, 9);
228 for (i
= 0; i
< 8; i
++)
229 k
->k
[i
] ^= fk
->t23
[i
];
230 for (i
= 8; i
< 40; i
+= 2) {
231 k
->k
[i
] ^= fk
->t4
[0];
232 k
->k
[i
+ 1] ^= fk
->t4
[1];
236 /* --- Construct the S-box tables --- */
240 static const octet
*q
[4][KMAX
+ 1] = {
241 { q1
, q0
, q0
, q1
, q1
},
242 { q0
, q0
, q1
, q1
, q0
},
243 { q1
, q1
, q0
, q0
, q0
},
244 { q0
, q1
, q1
, q0
, q1
}
247 for (i
= 0; i
< 4; i
++) {
251 for (j
= 0; j
< 256; j
++) {
254 /* --- Push the byte through the q tables --- */
257 case 4: x
= q
[i
][4][x
] ^ s
[i
][3];
258 case 3: x
= q
[i
][3][x
] ^ s
[i
][2];
259 case 2: x
= q
[i
][2][x
] ^ s
[i
][1];
260 x
= q
[i
][1][x
] ^ s
[i
][0];
264 /* --- Write it in the key schedule --- */
266 k
->g
[i
][j
] = qmds
[i
][x
];
271 /* --- Clear everything away --- */
278 /* --- @twofish_init@ --- *
280 * Arguments: @twofish_ctx *k@ = pointer to key block to fill in
281 * @const void *buf@ = pointer to buffer of key material
282 * @size_t sz@ = size of key material
286 * Use: Initializes a Twofish key buffer. Twofish accepts key sizes
287 * of up to 256 bits (32 bytes).
290 void twofish_init(twofish_ctx
*k
, const void *buf
, size_t sz
)
292 static const twofish_fk fk
= { { 0 } };
293 twofish_initfk(k
, buf
, sz
, &fk
);
296 /* --- @twofish_fkinit@ --- *
298 * Arguments: @twofish_fk *fk@ = pointer to family key block
299 * @const void *buf@ = pointer to buffer of key material
300 * @size_t sz@ = size of key material
304 * Use: Initializes a family-key buffer. This implementation allows
305 * family keys of any size acceptable to the Twofish algorithm.
308 void twofish_fkinit(twofish_fk
*fk
, const void *buf
, size_t sz
)
315 twofish_init(&k
, buf
, sz
);
317 for (i
= 0; i
< 4; i
++) pt
[i
] = (uint32
)-1;
318 twofish_eblk(&k
, pt
, fk
->t0
+ 4);
321 for (i
= 0; i
< sz
; i
++) { fk
->t0
[i
] = LOAD32_L(kk
); kk
+= 4; }
323 for (i
= 0; i
< 4; i
++) pt
[i
] = 0; twofish_eblk(&k
, pt
, ct
);
324 for (i
= 0; i
< 4; i
++) STORE32_L(fk
->t1
+ i
* 4, ct
[i
]);
325 pt
[0] = 1; twofish_eblk(&k
, pt
, ct
);
326 for (i
= 0; i
< 4; i
++) STORE32_L(fk
->t1
+ 4 + i
* 4, ct
[i
]);
328 pt
[0] = 2; twofish_eblk(&k
, pt
, fk
->t23
+ 0);
329 pt
[0] = 3; twofish_eblk(&k
, pt
, fk
->t23
+ 4);
330 pt
[0] = 4; twofish_eblk(&k
, pt
, ct
);
331 fk
->t4
[0] = ct
[0]; fk
->t4
[1] = ct
[1];
336 /*----- Main encryption ---------------------------------------------------*/
338 /* --- Feistel function --- */
340 #define GG(k, t0, t1, x, y, kk) do { \
341 t0 = (k->g[0][U8(x >> 0)] ^ \
342 k->g[1][U8(x >> 8)] ^ \
343 k->g[2][U8(x >> 16)] ^ \
344 k->g[3][U8(x >> 24)]); \
345 t1 = (k->g[1][U8(y >> 0)] ^ \
346 k->g[2][U8(y >> 8)] ^ \
347 k->g[3][U8(y >> 16)] ^ \
348 k->g[0][U8(y >> 24)]); \
355 /* --- Round operations --- */
357 #define EROUND(k, w, x, y, z, kk) do { \
359 GG(k, _t0, _t1, w, x, kk); \
361 y ^= _t0; y = ROR32(y, 1); \
362 z = ROL32(z, 1); z ^= _t1; \
365 #define DROUND(k, w, x, y, z, kk) do { \
368 GG(k, _t0, _t1, w, x, kk); \
369 y = ROL32(y, 1); y ^= _t0; \
370 z ^= _t1; z = ROR32(z, 1); \
373 /* --- Complete encryption functions --- */
375 #define EBLK(k, a, b, c, d, w, x, y, z) do { \
376 const uint32 *_kk = k->k + 8; \
377 uint32 _a = a, _b = b, _c = c, _d = d; \
378 _a ^= k->k[0]; _b ^= k->k[1]; _c ^= k->k[2]; _d ^= k->k[3]; \
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 EROUND(k, _a, _b, _c, _d, _kk); \
384 EROUND(k, _c, _d, _a, _b, _kk); \
385 EROUND(k, _a, _b, _c, _d, _kk); \
386 EROUND(k, _c, _d, _a, _b, _kk); \
387 EROUND(k, _a, _b, _c, _d, _kk); \
388 EROUND(k, _c, _d, _a, _b, _kk); \
389 EROUND(k, _a, _b, _c, _d, _kk); \
390 EROUND(k, _c, _d, _a, _b, _kk); \
391 EROUND(k, _a, _b, _c, _d, _kk); \
392 EROUND(k, _c, _d, _a, _b, _kk); \
393 EROUND(k, _a, _b, _c, _d, _kk); \
394 EROUND(k, _c, _d, _a, _b, _kk); \
395 _c ^= k->k[4]; _d ^= k->k[5]; _a ^= k->k[6]; _b ^= k->k[7]; \
396 w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b); \
399 #define DBLK(k, a, b, c, d, w, x, y, z) do { \
400 const uint32 *_kk = k->k + 40; \
401 uint32 _a = a, _b = b, _c = c, _d = d; \
402 _a ^= k->k[4]; _b ^= k->k[5]; _c ^= k->k[6]; _d ^= k->k[7]; \
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 DROUND(k, _a, _b, _c, _d, _kk); \
408 DROUND(k, _c, _d, _a, _b, _kk); \
409 DROUND(k, _a, _b, _c, _d, _kk); \
410 DROUND(k, _c, _d, _a, _b, _kk); \
411 DROUND(k, _a, _b, _c, _d, _kk); \
412 DROUND(k, _c, _d, _a, _b, _kk); \
413 DROUND(k, _a, _b, _c, _d, _kk); \
414 DROUND(k, _c, _d, _a, _b, _kk); \
415 DROUND(k, _a, _b, _c, _d, _kk); \
416 DROUND(k, _c, _d, _a, _b, _kk); \
417 DROUND(k, _a, _b, _c, _d, _kk); \
418 DROUND(k, _c, _d, _a, _b, _kk); \
419 _c ^= k->k[0]; _d ^= k->k[1]; _a ^= k->k[2]; _b ^= k->k[3]; \
420 w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b); \
423 /* --- @twofish_eblk@, @twofish_dblk@ --- *
425 * Arguments: @const twofish_ctx *k@ = pointer to key block
426 * @const uint32 s[4]@ = pointer to source block
427 * @uint32 d[4]@ = pointer to destination block
431 * Use: Low-level block encryption and decryption.
434 void twofish_eblk(const twofish_ctx
*k
, const uint32
*s
, uint32
*d
)
436 EBLK(k
, s
[0], s
[1], s
[2], s
[3], d
[0], d
[1], d
[2], d
[3]);
439 void twofish_dblk(const twofish_ctx
*k
, const uint32
*s
, uint32
*d
)
441 DBLK(k
, s
[0], s
[1], s
[2], s
[3], d
[0], d
[1], d
[2], d
[3]);
444 BLKC_TEST(TWOFISH
, twofish
)
446 /*----- That's all, folks -------------------------------------------------*/