2 * Fast, portable, and easy-to-use Twofish implementation,
4 * Copyright (c) 2002 by Niels Ferguson.
5 * (See further down for the almost-unrestricted licensing terms.)
7 * --------------------------------------------------------------------------
8 * There are two files for this implementation:
9 * - twofish.h, the header file.
10 * - twofish.c, the code file.
12 * To incorporate this code into your program you should:
13 * - Check the licensing terms further down in this comment.
14 * - Fix the two type definitions in twofish.h to suit your platform.
15 * - Fix a few definitions in twofish.c in the section marked
16 * PLATFORM FIXES. There is one important ones that affects
17 * functionality, and then a few definitions that you can optimise
18 * for efficiency but those have no effect on the functionality.
19 * Don't change anything else.
20 * - Put the code in your project and compile it.
22 * To use this library you should:
23 * - Call Twofish_initialise() in your program before any other function in
25 * - Use Twofish_prepare_key(...) to convert a key to internal form.
26 * - Use Twofish_encrypt(...) and Twofish_decrypt(...) to encrypt and decrypt
28 * See the comments in the header file for details on these functions.
29 * --------------------------------------------------------------------------
31 * There are many Twofish implementation available for free on the web.
32 * Most of them are hard to integrate into your own program.
33 * As we like people to use our cipher, I thought I would make it easier.
34 * Here is a free and easy-to-integrate Twofish implementation in C.
35 * The latest version is always available from my personal home page at
36 * http://niels.ferguson.net/
38 * Integrating library code into a project is difficult because the library
39 * header files interfere with the project's header files and code.
40 * And of course the project's header files interfere with the library code.
41 * I've tried to resolve these problems here.
42 * The header file of this implementation is very light-weight.
43 * It contains two typedefs, a structure, and a few function declarations.
44 * All names it defines start with "Twofish_".
45 * The header file is therefore unlikely to cause problems in your project.
46 * The code file of this implementation doesn't need to include the header
47 * files of the project. There is thus no danger of the project interfering
48 * with all the definitions and macros of the Twofish code.
49 * In most situations, all you need to do is fill in a few platform-specific
50 * definitions in the header file and code file,
51 * and you should be able to run the Twofish code in your project.
52 * I estimate it should take you less than an hour to integrate this code
53 * into your project, most of it spent reading the comments telling you what
56 * For people using C++: it is very easy to wrap this library into a
57 * TwofishKey class. One of the big advantages is that you can automate the
58 * wiping of the key material in the destructor. I have not provided a C++
59 * class because the interface depends too much on the abstract base class
60 * you use for block ciphers in your program, which I don't know about.
62 * This implementation is designed for use on PC-class machines. It uses the
63 * Twofish 'full' keying option which uses large tables. Total table size is
64 * around 5-6 kB for static tables plus 4.5 kB for each pre-processed key.
65 * If you need an implementation that uses less memory,
66 * take a look at Brian Gladman's code on his web site:
67 * http://fp.gladman.plus.com/cryptography_technology/aes/
68 * He has code for all AES candidates.
69 * His Twofish code has lots of options trading off table size vs. speed.
70 * You can also take a look at the optimised code by Doug Whiting on the
72 * http://www.counterpane.com/twofish.html
73 * which has loads of options.
74 * I believe these existing implementations are harder to re-use because they
75 * are not clean libraries and they impose requirements on the environment.
76 * This implementation is very careful to minimise those,
77 * and should be easier to integrate into any larger program.
79 * The default mode of this implementation is fully portable as it uses no
80 * behaviour not defined in the C standard. (This is harder than you think.)
81 * If you have any problems porting the default mode, please let me know
82 * so that I can fix the problem. (But only if this code is at fault, I
83 * don't fix compilers.)
84 * Most of the platform fixes are related to non-portable but faster ways
85 * of implementing certain functions.
87 * In general I've tried to make the code as fast as possible, at the expense
88 * of memory and code size. However, C does impose limits, and this
89 * implementation will be slower than an optimised assembler implementation.
90 * But beware of assembler implementations: a good Pentium implementation
91 * uses completely different code than a good Pentium II implementation.
92 * You basically have to re-write the assembly code for every generation of
93 * processor. Unless you are severely pressed for speed, stick with C.
95 * The initialisation routine of this implementation contains a self-test.
96 * If initialisation succeeds without calling the fatal routine, then
97 * the implementation works. I don't think you can break the implementation
98 * in such a way that it still passes the tests, unless you are malicious.
99 * In other words: if the initialisation routine returns,
100 * you have successfully ported the implementation.
101 * (Or not implemented the fatal routine properly, but that is your problem.)
103 * I'm indebted to many people who helped me in one way or another to write
104 * this code. During the design of Twofish and the AES process I had very
105 * extensive discussions of all implementation issues with various people.
106 * Doug Whiting in particular provided a wealth of information. The Twofish
107 * team spent untold hours discussion various cipher features, and their
108 * implementation. Brian Gladman implemented all AES candidates in C,
109 * and we had some fruitful discussions on how to implement Twofish in C.
110 * Jan Nieuwenhuizen tested this code on Linux using GCC.
112 * Now for the license:
113 * The author hereby grants a perpetual license to everybody to
114 * use this code for any purpose as long as the copyright message is included
115 * in the source code of this or any derived work.
117 * Yes, this means that you, your company, your club, and anyone else
118 * can use this code anywhere you want. You can change it and distribute it
119 * under the GPL, include it in your commercial product without releasing
120 * the source code, put it on the web, etc.
121 * The only thing you cannot do is remove my copyright message,
122 * or distribute any source code based on this implementation that does not
123 * include my copyright message.
125 * I appreciate a mention in the documentation or credits,
126 * but I understand if that is difficult to do.
127 * I also appreciate it if you tell me where and why you used my code.
129 * Please send any questions or comments to niels@ferguson.net
137 * DISCLAIMER: As I'm giving away my work for free, I'm of course not going
138 * to accept any liability of any form. This code, or the Twofish cipher,
139 * might very well be flawed; you have been warned.
140 * This software is provided as-is, without any kind of warrenty or
141 * guarantee. And that is really all you can expect when you download
142 * code for free from the Internet.
144 * I think it is really sad that disclaimers like this seem to be necessary.
145 * If people only had a little bit more common sense, and didn't come
146 * whining like little children every time something happens....
151 * Version 0.0, 2002-08-30
153 * Version 0.1, 2002-09-03
154 * Added disclaimer. Improved self-tests.
155 * Version 0.2, 2002-09-09
156 * Removed last non-portabilities. Default now works completely within
157 * the C standard. UInt32 can be larger than 32 bits without problems.
158 * Version 0.3, 2002-09-28
159 * Bugfix: use <string.h> instead of <memory.h> to adhere to ANSI/ISO.
160 * Rename BIG_ENDIAN macro to CPU_IS_BIG_ENDIAN. The gcc library
161 * header <string.h> already defines BIG_ENDIAN, even though it is not
167 * Minimum set of include files.
168 * You should not need any application-specific include files for this code.
169 * In fact, adding you own header files could break one of the many macros or
170 * functions in this file. Be very careful.
171 * Standard include files will probably be ok.
174 //#include <QString> /* for memset(), memcpy(), and memcmp() */
183 * Fix the type definitions in twofish.h first!
185 * The following definitions have to be fixed for each particular platform
186 * you work on. If you have a multi-platform program, you no doubt have
187 * portable definitions that you can substitute here without changing the
193 * Function called if something is fatally wrong with the implementation.
194 * This fatal function is called when a coding error is detected in the
195 * Twofish implementation, or when somebody passes an obviously erroneous
196 * parameter to this implementation. There is not much you can do when
197 * the code contains bugs, so we just stop.
199 * The argument is a string. Ideally the fatal function prints this string
200 * as an error message. Whatever else this function does, it should never
201 * return. A typical implementation would stop the program completely after
202 * printing the error message.
204 * This default implementation is not very useful,
205 * but does not assume anything about your environment.
206 * It will at least let you know something is wrong....
207 * I didn't want to include any libraries to print and error or so,
208 * as this makes the code much harder to integrate in a project.
210 * Note that the Twofish_fatal function may not return to the caller.
211 * Unfortunately this is not something the self-test can test for,
212 * so you have to make sure of this yourself.
214 * If you want to call an external function, be careful about including
215 * your own header files here. This code uses a lot of macros, and your
216 * header file could easily break it. Maybe the best solution is to use
217 * a separate extern statement for your fatal function.
220 //#define Twofish_fatal(pmsgx) { MessageBox(GetDesktopWindow(), _T(pmsgx), _T("Twofish Fatal Error"), MB_OK); }
224 * The rest of the settings are not important for the functionality
225 * of this Twofish implementation. That is, their default settings
226 * work on all platforms. You can change them to improve the
227 * speed of the implementation on your platform. Erroneous settings
228 * will result in erroneous implementations, but the self-test should
234 * Macros to rotate a Twofish_UInt32 value left or right by the
235 * specified number of bits. This should be a 32-bit rotation,
236 * and not rotation of, say, 64-bit values.
238 * Every encryption or decryption operation uses 32 of these rotations,
239 * so it is a good idea to make these macros efficient.
241 * This fully portable definition has one piece of tricky stuff.
242 * The UInt32 might be larger than 32 bits, so we have to mask
243 * any higher bits off. The simplest way to do this is to 'and' the
244 * value first with 0xffffffff and then shift it right. An optimising
245 * compiler that has a 32-bit type can optimise this 'and' away.
247 * Unfortunately there is no portable way of writing the constant
248 * 0xffffffff. You don't know which suffix to use (U, or UL?)
249 * The quint32_MASK definition uses a bit of trickery. Shift-left
250 * is only defined if the shift amount is strictly less than the size
251 * of the UInt32, so we can't use (1<<32). The answer it to take the value
252 * 2, cast it to a UInt32, shift it left 31 positions, and subtract one.
253 * Another example of how to make something very simple extremely difficult.
256 * The rotation macros are straightforward.
257 * They are only applied to UInt32 values, which are _unsigned_
258 * so the >> operator must do a logical shift that brings in zeroes.
259 * On most platforms you will only need to optimise the ROL32 macro; the
260 * ROR32 macro is not inefficient on an optimising compiler as all rotation
261 * amounts in this code are known at compile time.
263 * On many platforms there is a faster solution.
264 * For example, MS compilers have the __rotl and __rotr functions
265 * that generate x86 rotation instructions.
267 #define quint32_MASK ( (((Twofish_UInt32)2)<<31) - 1 )
270 #define ROL32(x,n) ( (x)<<(n) | ((x) & quint32_MASK) >> (32-(n)) )
271 #define ROR32(x,n) ( (x)>>(n) | ((x) & quint32_MASK) << (32-(n)) )
273 #define ROL32(x,n) (_lrotl((x), (n)))
274 #define ROR32(x,n) (_lrotr((x), (n)))
278 * Select data type for q-table entries.
280 * Larger entry types cost more memory (1.5 kB), and might be faster
281 * or slower depending on the CPU and compiler details.
283 * This choice only affects the static data size and the key setup speed.
284 * Functionality, expanded key size, or encryption speed are not affected.
285 * Define to 1 to get large q-table entries.
287 #define LARGE_Q_TABLE 0 /* default = 0 */
291 * Method to select a single byte from a UInt32.
292 * WARNING: non-portable code if set; might not work on all platforms.
294 * Inside the inner loop of Twofish it is necessary to access the 4
295 * individual bytes of a UInt32. This can be done using either shifts
296 * and masks, or memory accesses.
298 * Set to 0 to use shift and mask operations for the byte selection.
299 * This is more ALU intensive. It is also fully portable.
301 * Set to 1 to use memory accesses. The UInt32 is stored in memory and
302 * the individual bytes are read from memory one at a time.
303 * This solution is more memory-intensive, and not fully portable.
304 * It might be faster on your platform, or not. If you use this option,
305 * make sure you set the CPU_IS_BIG_ENDIAN flag appropriately.
307 * This macro does not affect the conversion of the inputs and outputs
308 * of the cipher. See the CONVERT_USING_CASTS macro for that.
310 #define SELECT_BYTE_FROM_quint32_IN_MEMORY 0 /* default = 0 */
314 * Method used to read the input and write the output.
315 * WARNING: non-portable code if set; might not work on all platforms.
317 * Twofish operates on 32-bit words. The input to the cipher is
318 * a byte array, as is the output. The portable method of doing the
319 * conversion is a bunch of rotate and mask operations, but on many
320 * platforms it can be done faster using a cast.
321 * This only works if your CPU allows UInt32 accesses to arbitrary Byte
324 * Set to 0 to use the shift and mask operations. This is fully
327 * Set to 1 to use a cast. The Byte * is cast to a UInt32 *, and a
328 * UInt32 is read. If necessary (as indicated by the CPU_IS_BIG_ENDIAN
329 * macro) the byte order in the UInt32 is swapped. The reverse is done
330 * to write the output of the encryption/decryption. Make sure you set
331 * the CPU_IS_BIG_ENDIAN flag appropriately.
332 * This option does not work unless a UInt32 is exactly 32 bits.
334 * This macro only changes the reading/writing of the plaintext/ciphertext.
335 * See the SELECT_BYTE_FROM_quint32_IN_MEMORY to affect the way in which
336 * a UInt32 is split into 4 bytes for the S-box selection.
338 #define CONVERT_USING_CASTS 0 /* default = 0 */
343 * Only relevant if SELECT_BYTE_FROM_quint32_IN_MEMORY or
344 * CONVERT_USING_CASTS is set.
346 * Set to 1 on a big-endian machine, and to 0 on a little-endian machine.
347 * Twofish uses the little-endian convention (least significant byte first)
348 * and big-endian machines (using most significant byte first)
349 * have to do a few conversions.
351 * CAUTION: This code has never been tested on a big-endian machine,
352 * because I don't have access to one. Feedback appreciated.
354 #define CPU_IS_BIG_ENDIAN 0
358 * Macro to reverse the order of the bytes in a UInt32.
359 * Used to convert to little-endian on big-endian machines.
360 * This macro is always tested, but only used in the encryption and
361 * decryption if CONVERT_USING_CASTS, and CPU_IS_BIG_ENDIAN
362 * are both set. In other words: this macro is only speed-critical if
363 * both these flags have been set.
365 * This default definition of SWAP works, but on many platforms there is a
366 * more efficient implementation.
368 #define BSWAP(x) ( (ROL32((x),8) & 0x00ff00ff) | (ROR32((x),8) & 0xff00ff00) )
372 * END OF PLATFORM FIXES
373 * =====================
375 * You should not have to touch the rest of this file.
380 * Convert the external type names to some that are easier to use inside
381 * this file. I didn't want to use the names Byte and UInt32 in the
382 * header file, because many programs already define them and using two
383 * conventions at once can be very difficult.
384 * Don't change these definitions! Change the originals
385 * in twofish.h instead.
387 /* A Byte must be an unsigned integer, 8 bits long. */
388 // typedef Twofish_Byte Byte;
389 /* A UInt32 must be an unsigned integer at least 32 bits long. */
390 // typedef Twofish_UInt32 UInt32;
394 * Define a macro ENDIAN_CONVERT.
396 * We define a macro ENDIAN_CONVERT that performs a BSWAP on big-endian
397 * machines, and is the identity function on little-endian machines.
398 * The code then uses this macro without considering the endianness.
401 #if CPU_IS_BIG_ENDIAN
402 #define ENDIAN_CONVERT(x) BSWAP(x)
404 #define ENDIAN_CONVERT(x) (x)
409 * Compute byte offset within a UInt32 stored in memory.
411 * This is only used when SELECT_BYTE_FROM_quint32_IN_MEMORY is set.
413 * The input is the byte number 0..3, 0 for least significant.
414 * Note the use of sizeof() to support UInt32 types that are larger
417 #if CPU_IS_BIG_ENDIAN
418 #define BYTE_OFFSET( n ) (sizeof(Twofish_UInt32) - 1 - (n) )
420 #define BYTE_OFFSET( n ) (n)
425 * Macro to get Byte no. b from UInt32 value X.
426 * We use two different definition, depending on the settings.
428 #if SELECT_BYTE_FROM_quint32_IN_MEMORY
429 /* Pick the byte from the memory in which X is stored. */
430 #define SELECT_BYTE( X, b ) (((Twofish_Byte *)(&(X)))[BYTE_OFFSET(b)])
432 /* Portable solution: Pick the byte directly from the X value. */
433 #define SELECT_BYTE( X, b ) (((X) >> (8*(b))) & 0xff)
437 /* Some shorthands because we use byte selection in large formulae. */
438 #define b0(X) SELECT_BYTE((X),0)
439 #define b1(X) SELECT_BYTE((X),1)
440 #define b2(X) SELECT_BYTE((X),2)
441 #define b3(X) SELECT_BYTE((X),3)
445 * We need macros to load and store UInt32 from/to byte arrays
446 * using the least-significant-byte-first convention.
448 * GET32( p ) gets a UInt32 in lsb-first form from four bytes pointed to
450 * PUT32( v, p ) writes the UInt32 value v at address p in lsb-first form.
452 #if CONVERT_USING_CASTS
454 /* Get UInt32 from four bytes pointed to by p. */
455 #define GET32( p ) ENDIAN_CONVERT( *((Twofish_UInt32 *)(p)) )
456 /* Put UInt32 into four bytes pointed to by p */
457 #define PUT32( v, p ) *((Twofish_UInt32 *)(p)) = ENDIAN_CONVERT(v)
461 /* Get UInt32 from four bytes pointed to by p. */
464 (Twofish_UInt32)((p)[0]) \
465 | (Twofish_UInt32)((p)[1])<< 8 \
466 | (Twofish_UInt32)((p)[2])<<16 \
467 | (Twofish_UInt32)((p)[3])<<24 \
469 /* Put UInt32 into four bytes pointed to by p */
470 #define PUT32( v, p ) \
471 (p)[0] = (Twofish_Byte)(((v) ) & 0xff); \
472 (p)[1] = (Twofish_Byte)(((v) >> 8) & 0xff); \
473 (p)[2] = (Twofish_Byte)(((v) >> 16) & 0xff); \
474 (p)[3] = (Twofish_Byte)(((v) >> 24) & 0xff)
479 void Twofish_fatal(const char* msg){
480 qFatal("Twofish: Fatal Error: %s", msg);
486 * Test the platform-specific macros.
487 * This function tests the macros defined so far to make sure the
488 * definitions are appropriate for this platform.
489 * If you make any mistake in the platform configuration, this should detect
490 * that and inform you what went wrong.
491 * Somewhere, someday, this is going to save somebody a lot of time,
492 * because misbehaving macros are hard to debug.
494 static void test_platform()
496 /* Buffer with test values. */
497 Twofish_Byte buf[] = {0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0};
503 * Some sanity checks on the types that can't be done in compile time.
504 * A smart compiler will just optimise these tests away.
505 * The pre-processor doesn't understand different types, so we cannot
506 * do these checks in compile-time.
510 * The first check in each case is to make sure the size is correct.
511 * The second check is to ensure that it is an unsigned type.
513 if( ((Twofish_UInt32)((Twofish_UInt32)1 << 31) == 0) || ((Twofish_UInt32)-1 < 0 ))
515 Twofish_fatal( "Twofish code: Twofish_UInt32 type not suitable" );
517 if( (sizeof( Twofish_Byte ) != 1) || (((Twofish_Byte)-1) < 0) )
519 Twofish_fatal( "Twofish code: Twofish_Byte type not suitable" );
523 * Sanity-check the endianness conversions.
524 * This is just an aid to find problems. If you do the endianness
525 * conversion macros wrong you will fail the full cipher test,
526 * but that does not help you find the error.
527 * Always make it easy to find the bugs!
529 * Detail: There is no fully portable way of writing UInt32 constants,
530 * as you don't know whether to use the U or UL suffix. Using only U you
531 * might only be allowed 16-bit constants. Using UL you might get 64-bit
532 * constants which cannot be stored in a UInt32 without warnings, and
533 * which generally behave subtly different from a true UInt32.
534 * As long as we're just comparing with the constant,
535 * we can always use the UL suffix and at worst lose some efficiency.
536 * I use a separate '32-bit constant' macro in most of my other code.
540 * Start with testing GET32. We test it on all positions modulo 4
541 * to make sure we can handly any position of inputs. (Some CPUs
542 * do not allow non-aligned accesses which we would do if you used
543 * the CONVERT_USING_CASTS option.
545 if( (GET32( buf ) != 0x78563412UL) || (GET32(buf+1) != 0x9a785634UL)
546 || (GET32( buf+2 ) != 0xbc9a7856UL) || (GET32(buf+3) != 0xdebc9a78UL) )
548 Twofish_fatal( "Twofish code: GET32 not implemented properly" );
552 * We can now use GET32 to test PUT32.
553 * We don't test the shifted versions. If GET32 can do that then
558 if( GET32( buf ) != 0x69029c36UL )
560 Twofish_fatal( "Twofish code: PUT32 not implemented properly" );
564 /* Test ROL and ROR */
565 for( i=1; i<32; i++ )
567 /* Just a simple test. */
570 x ^= (C>>i) ^ (C<<(32-i));
571 y ^= (C<<i) ^ (C>>(32-i));
574 * Now all we check is that x is zero in the least significant
575 * 32 bits. Using the UL suffix is safe here, as it doesn't matter
576 * if we get a larger type.
578 if( (x & 0xffffffffUL) != 0 )
580 Twofish_fatal( "Twofish ROL or ROR not properly defined." );
584 /* Test the BSWAP macro */
585 if( BSWAP(C) != 0x12345678UL )
588 * The BSWAP macro should always work, even if you are not using it.
589 * A smart optimising compiler will just remove this entire test.
591 Twofish_fatal( "BSWAP not properly defined." );
594 /* And we can test the b<i> macros which use SELECT_BYTE. */
595 if( (b0(C)!=0x12) || (b1(C) != 0x34) || (b2(C) != 0x56) || (b3(C) != 0x78) )
598 * There are many reasons why this could fail.
599 * Most likely is that CPU_IS_BIG_ENDIAN has the wrong value.
601 Twofish_fatal( "Twofish code: SELECT_BYTE not implemented properly" );
607 * Finally, we can start on the Twofish-related code.
608 * You really need the Twofish specifications to understand this code. The
609 * best source is the Twofish book:
610 * "The Twofish Encryption Algorithm", by Bruce Schneier, John Kelsey,
611 * Doug Whiting, David Wagner, Chris Hall, and Niels Ferguson.
612 * you can also use the AES submission document of Twofish, which is
613 * available from my list of publications on my personal web site at
614 * http://niels.ferguson.net/.
616 * The first thing we do is write the testing routines. This is what the
617 * implementation has to satisfy in the end. We only test the external
618 * behaviour of the implementation of course.
623 * Perform a single self test on a (plaintext,ciphertext,key) triple.
625 * key array of key bytes
626 * key_len length of key in bytes
630 static void test_vector( Twofish_Byte key[], int key_len, Twofish_Byte p[16], Twofish_Byte c[16] )
632 Twofish_Byte tmp[16]; /* scratch pad. */
633 Twofish_key xkey; /* The expanded key */
637 /* Prepare the key */
638 Twofish_prepare_key( key, key_len, &xkey );
641 * We run the test twice to ensure that the xkey structure
642 * is not damaged by the first encryption.
643 * Those are hideous bugs to find if you get them in an application.
647 /* Encrypt and test */
648 Twofish_encrypt( &xkey, p, tmp );
649 if( memcmp( c, tmp, 16 ) != 0 )
651 Twofish_fatal( "Twofish encryption failure" );
654 /* Decrypt and test */
655 Twofish_decrypt( &xkey, c, tmp );
656 if( memcmp( p, tmp, 16 ) != 0 )
658 Twofish_fatal( "Twofish decryption failure" );
662 /* The test keys are not secret, so we don't need to wipe xkey. */
667 * Check implementation using three (key,plaintext,ciphertext)
668 * test vectors, one for each major key length.
670 * This is an absolutely minimal self-test.
671 * This routine does not test odd-sized keys.
673 static void test_vectors()
676 * We run three tests, one for each major key length.
677 * These test vectors come from the Twofish specification.
678 * One encryption and one decryption using randomish data and key
679 * will detect almost any error, especially since we generate the
680 * tables ourselves, so we don't have the problem of a single
681 * damaged table entry in the source.
684 /* 128-bit test is the I=3 case of section B.2 of the Twofish book. */
685 static Twofish_Byte k128[] = {
686 0x9F, 0x58, 0x9F, 0x5C, 0xF6, 0x12, 0x2C, 0x32,
687 0xB6, 0xBF, 0xEC, 0x2F, 0x2A, 0xE8, 0xC3, 0x5A,
689 static Twofish_Byte p128[] = {
690 0xD4, 0x91, 0xDB, 0x16, 0xE7, 0xB1, 0xC3, 0x9E,
691 0x86, 0xCB, 0x08, 0x6B, 0x78, 0x9F, 0x54, 0x19
693 static Twofish_Byte c128[] = {
694 0x01, 0x9F, 0x98, 0x09, 0xDE, 0x17, 0x11, 0x85,
695 0x8F, 0xAA, 0xC3, 0xA3, 0xBA, 0x20, 0xFB, 0xC3
698 /* 192-bit test is the I=4 case of section B.2 of the Twofish book. */
699 static Twofish_Byte k192[] = {
700 0x88, 0xB2, 0xB2, 0x70, 0x6B, 0x10, 0x5E, 0x36,
701 0xB4, 0x46, 0xBB, 0x6D, 0x73, 0x1A, 0x1E, 0x88,
702 0xEF, 0xA7, 0x1F, 0x78, 0x89, 0x65, 0xBD, 0x44
704 static Twofish_Byte p192[] = {
705 0x39, 0xDA, 0x69, 0xD6, 0xBA, 0x49, 0x97, 0xD5,
706 0x85, 0xB6, 0xDC, 0x07, 0x3C, 0xA3, 0x41, 0xB2
708 static Twofish_Byte c192[] = {
709 0x18, 0x2B, 0x02, 0xD8, 0x14, 0x97, 0xEA, 0x45,
710 0xF9, 0xDA, 0xAC, 0xDC, 0x29, 0x19, 0x3A, 0x65
713 /* 256-bit test is the I=4 case of section B.2 of the Twofish book. */
714 static Twofish_Byte k256[] = {
715 0xD4, 0x3B, 0xB7, 0x55, 0x6E, 0xA3, 0x2E, 0x46,
716 0xF2, 0xA2, 0x82, 0xB7, 0xD4, 0x5B, 0x4E, 0x0D,
717 0x57, 0xFF, 0x73, 0x9D, 0x4D, 0xC9, 0x2C, 0x1B,
718 0xD7, 0xFC, 0x01, 0x70, 0x0C, 0xC8, 0x21, 0x6F
720 static Twofish_Byte p256[] = {
721 0x90, 0xAF, 0xE9, 0x1B, 0xB2, 0x88, 0x54, 0x4F,
722 0x2C, 0x32, 0xDC, 0x23, 0x9B, 0x26, 0x35, 0xE6
724 static Twofish_Byte c256[] = {
725 0x6C, 0xB4, 0x56, 0x1C, 0x40, 0xBF, 0x0A, 0x97,
726 0x05, 0x93, 0x1C, 0xB6, 0xD4, 0x08, 0xE7, 0xFA
729 /* Run the actual tests. */
730 test_vector( k128, 16, p128, c128 );
731 test_vector( k192, 24, p192, c192 );
732 test_vector( k256, 32, p256, c256 );
737 * Perform extensive test for a single key size.
739 * Test a single key size against the test vectors from section
740 * B.2 in the Twofish book. This is a sequence of 49 encryptions
741 * and decryptions. Each plaintext is equal to the ciphertext of
742 * the previous encryption. The key is made up from the ciphertext
743 * two and three encryptions ago. Both plaintext and key start
745 * We should have designed a cleaner recurrence relation for
746 * these tests, but it is too late for that now. At least we learned
747 * how to do it better next time.
748 * For details see appendix B of the book.
751 * key_len Number of bytes of key
752 * final_value Final plaintext value after 49 iterations
754 static void test_sequence( int key_len, Twofish_Byte final_value[] )
756 Twofish_Byte buf[ (50+3)*16 ]; /* Buffer to hold our computation values. */
757 Twofish_Byte tmp[16]; /* Temp for testing the decryption. */
758 Twofish_key xkey; /* The expanded key */
762 /* Wipe the buffer */
763 memset( buf, 0, sizeof( buf ) );
766 * Because the recurrence relation is done in an inconvenient manner
767 * we end up looping backwards over the buffer.
770 /* Pointer in buffer points to current plaintext. */
772 for( i=1; i<50; i++ )
776 * This automatically checks that key_len is valid.
778 Twofish_prepare_key( p+16, key_len, &xkey );
780 /* Compute the next 16 bytes in the buffer */
781 Twofish_encrypt( &xkey, p, p-16 );
783 /* Check that the decryption is correct. */
784 Twofish_decrypt( &xkey, p-16, tmp );
785 if( memcmp( tmp, p, 16 ) != 0 )
787 Twofish_fatal( "Twofish decryption failure in sequence" );
789 /* Move on to next 16 bytes in the buffer. */
793 /* And check the final value. */
794 if( memcmp( p, final_value, 16 ) != 0 )
796 Twofish_fatal( "Twofish encryption failure in sequence" );
799 /* None of the data was secret, so there is no need to wipe anything. */
804 * Run all three sequence tests from the Twofish test vectors.
806 * This checks the most extensive test vectors currently available
807 * for Twofish. The data is from the Twofish book, appendix B.2.
809 static void test_sequences()
811 static Twofish_Byte r128[] = {
812 0x5D, 0x9D, 0x4E, 0xEF, 0xFA, 0x91, 0x51, 0x57,
813 0x55, 0x24, 0xF1, 0x15, 0x81, 0x5A, 0x12, 0xE0
815 static Twofish_Byte r192[] = {
816 0xE7, 0x54, 0x49, 0x21, 0x2B, 0xEE, 0xF9, 0xF4,
817 0xA3, 0x90, 0xBD, 0x86, 0x0A, 0x64, 0x09, 0x41
819 static Twofish_Byte r256[] = {
820 0x37, 0xFE, 0x26, 0xFF, 0x1C, 0xF6, 0x61, 0x75,
821 0xF5, 0xDD, 0xF4, 0xC3, 0x3B, 0x97, 0xA2, 0x05
824 /* Run the three sequence test vectors */
825 test_sequence( 16, r128 );
826 test_sequence( 24, r192 );
827 test_sequence( 32, r256 );
832 * Test the odd-sized keys.
834 * Every odd-sized key is equivalent to a one of 128, 192, or 256 bits.
835 * The equivalent key is found by padding at the end with zero bytes
836 * until a regular key size is reached.
838 * We just test that the key expansion routine behaves properly.
839 * If the expanded keys are identical, then the encryptions and decryptions
840 * will behave the same.
842 static void test_odd_sized_keys()
844 Twofish_Byte buf[32];
846 Twofish_key xkey_two;
850 * We first create an all-zero key to use as PRNG key.
851 * Normally we would not have to fill the buffer with zeroes, as we could
852 * just pass a zero key length to the Twofish_prepare_key function.
853 * However, this relies on using odd-sized keys, and those are just the
854 * ones we are testing here. We can't use an untested function to test
857 memset( buf, 0, sizeof( buf ) );
858 Twofish_prepare_key( buf, 16, &xkey );
860 /* Fill buffer with pseudo-random data derived from two encryptions */
861 Twofish_encrypt( &xkey, buf, buf );
862 Twofish_encrypt( &xkey, buf, buf+16 );
864 /* Create all possible shorter keys that are prefixes of the buffer. */
865 for( i=31; i>=0; i-- )
867 /* Set a byte to zero. This is the new padding byte */
870 /* Expand the key with only i bytes of length */
871 Twofish_prepare_key( buf, i, &xkey );
873 /* Expand the corresponding padded key of regular length */
874 Twofish_prepare_key( buf, i<=16 ? 16 : (i<= 24 ? 24 : 32), &xkey_two );
876 /* Compare the two */
877 if( memcmp( &xkey, &xkey_two, sizeof( xkey ) ) != 0 )
879 Twofish_fatal( "Odd sized keys do not expand properly" );
883 /* None of the key values are secret, so we don't need to wipe them. */
888 * Test the Twofish implementation.
890 * This routine runs all the self tests, in order of importance.
891 * It is called by the Twofish_initialise routine.
893 * In almost all applications the cost of running the self tests during
894 * initialisation is insignificant, especially
895 * compared to the time it takes to load the application from disk.
896 * If you are very pressed for initialisation performance,
897 * you could remove some of the tests. Make sure you did run them
898 * once in the software and hardware configuration you are using.
900 static void self_test()
902 /* The three test vectors form an absolute minimal test set. */
906 * If at all possible you should run these tests too. They take
907 * more time, but provide a more thorough coverage.
911 /* Test the odd-sized keys. */
912 test_odd_sized_keys();
917 * And now, the actual Twofish implementation.
919 * This implementation generates all the tables during initialisation.
920 * I don't like large tables in the code, especially since they are easily
921 * damaged in the source without anyone noticing it. You need code to
922 * generate them anyway, and this way all the code is close together.
923 * Generating them in the application leads to a smaller executable
924 * (the code is smaller than the tables it generates) and a
925 * larger static memory footprint.
927 * Twofish can be implemented in many ways. I have chosen to
928 * use large tables with a relatively long key setup time.
929 * If you encrypt more than a few blocks of data it pays to pre-compute
930 * as much as possible. This implementation is relatively inefficient for
931 * applications that need to re-key every block or so.
935 * We start with the t-tables, directly from the Twofish definition.
936 * These are nibble-tables, but merging them and putting them two nibbles
937 * in one byte is more work than it is worth.
939 static Twofish_Byte t_table[2][4][16] = {
941 {0x8,0x1,0x7,0xD,0x6,0xF,0x3,0x2,0x0,0xB,0x5,0x9,0xE,0xC,0xA,0x4},
942 {0xE,0xC,0xB,0x8,0x1,0x2,0x3,0x5,0xF,0x4,0xA,0x6,0x7,0x0,0x9,0xD},
943 {0xB,0xA,0x5,0xE,0x6,0xD,0x9,0x0,0xC,0x8,0xF,0x3,0x2,0x4,0x7,0x1},
944 {0xD,0x7,0xF,0x4,0x1,0x2,0x6,0xE,0x9,0xB,0x3,0x0,0x8,0x5,0xC,0xA}
947 {0x2,0x8,0xB,0xD,0xF,0x7,0x6,0xE,0x3,0x1,0x9,0x4,0x0,0xA,0xC,0x5},
948 {0x1,0xE,0x2,0xB,0x4,0xC,0x3,0x7,0x6,0xD,0xA,0x5,0xF,0x9,0x0,0x8},
949 {0x4,0xC,0x7,0x5,0x1,0x6,0x9,0xA,0x0,0xE,0xD,0x8,0x2,0xB,0x3,0xF},
950 {0xB,0x9,0x5,0x1,0xC,0x3,0xD,0xE,0x6,0x4,0x7,0xF,0x2,0x0,0x8,0xA}
955 /* A 1-bit rotation of 4-bit values. Input must be in range 0..15 */
956 #define ROR4BY1( x ) (((x)>>1) | (((x)<<3) & 0x8) )
959 * The q-boxes are only used during the key schedule computations.
960 * These are 8->8 bit lookup tables. Some CPUs prefer to have 8->32 bit
961 * lookup tables as it is faster to load a 32-bit value than to load an
962 * 8-bit value and zero the rest of the register.
963 * The LARGE_Q_TABLE switch allows you to choose 32-bit entries in
964 * the q-tables. Here we just define the Qtype which is used to store
965 * the entries of the q-tables.
968 typedef Twofish_UInt32 Qtype;
970 typedef Twofish_Byte Qtype;
974 * The actual q-box tables.
975 * There are two q-boxes, each having 256 entries.
977 static Qtype q_table[2][256];
981 * Now the function that converts a single t-table into a q-table.
984 * t[4][16] : four 4->4bit lookup tables that define the q-box
985 * q[256] : output parameter: the resulting q-box as a lookup table.
987 static void make_q_table( Twofish_Byte t[4][16], Qtype q[256] )
989 int ae,be,ao,bo; /* Some temporaries. */
991 /* Loop over all input values and compute the q-box result. */
992 for( i=0; i<256; i++ ) {
994 * This is straight from the Twofish specifications.
996 * The ae variable is used for the a_i values from the specs
997 * with even i, and ao for the odd i's. Similarly for the b's.
999 ae = i>>4; be = i&0xf;
1000 ao = ae ^ be; bo = ae ^ ROR4BY1(be) ^ ((ae<<3)&8);
1001 ae = t[0][ao]; be = t[1][bo];
1002 ao = ae ^ be; bo = ae ^ ROR4BY1(be) ^ ((ae<<3)&8);
1003 ae = t[2][ao]; be = t[3][bo];
1005 /* Store the result in the q-box table, the cast avoids a warning. */
1006 q[i] = (Qtype) ((be<<4) | ae);
1012 * Initialise both q-box tables.
1014 static void initialise_q_boxes() {
1015 /* Initialise each of the q-boxes using the t-tables */
1016 make_q_table( t_table[0], q_table[0] );
1017 make_q_table( t_table[1], q_table[1] );
1022 * Next up is the MDS matrix multiplication.
1023 * The MDS matrix multiplication operates in the field
1024 * GF(2)[x]/p(x) with p(x)=x^8+x^6+x^5+x^3+1.
1025 * If you don't understand this, read a book on finite fields. You cannot
1026 * follow the finite-field computations without some background.
1028 * In this field, multiplication by x is easy: shift left one bit
1029 * and if bit 8 is set then xor the result with 0x169.
1031 * The MDS coefficients use a multiplication by 1/x,
1032 * or rather a division by x. This is easy too: first make the
1033 * value 'even' (i.e. bit 0 is zero) by xorring with 0x169 if necessary,
1034 * and then shift right one position.
1035 * Even easier: shift right and xor with 0xb4 if the lsbit was set.
1037 * The MDS coefficients are 1, EF, and 5B, and we use the fact that
1038 * EF = 1 + 1/x + 1/x^2
1040 * in this field. This makes multiplication by EF and 5B relatively easy.
1042 * This property is no accident, the MDS matrix was designed to allow
1043 * this implementation technique to be used.
1045 * We have four MDS tables, each mapping 8 bits to 32 bits.
1046 * Each table performs one column of the matrix multiplication.
1047 * As the MDS is always preceded by q-boxes, each of these tables
1048 * also implements the q-box just previous to that column.
1051 /* The actual MDS tables. */
1052 static Twofish_UInt32 MDS_table[4][256];
1054 /* A small table to get easy conditional access to the 0xb4 constant. */
1055 static Twofish_UInt32 mds_poly_divx_const[] = {0,0xb4};
1057 /* Function to initialise the MDS tables. */
1058 static void initialise_mds_tables()
1061 Twofish_UInt32 q,qef,q5b; /* Temporary variables. */
1063 /* Loop over all 8-bit input values */
1064 for( i=0; i<256; i++ )
1067 * To save some work during the key expansion we include the last
1068 * of the q-box layers from the h() function in these MDS tables.
1071 /* We first do the inputs that are mapped through the q0 table. */
1074 * Here we divide by x, note the table to get 0xb4 only if the
1076 * This sets qef = (1/x)*q in the finite field
1078 qef = (q >> 1) ^ mds_poly_divx_const[ q & 1 ];
1080 * Divide by x again, and add q to get (1+1/x^2)*q.
1081 * Note that (1+1/x^2) = 5B in the field, and addition in the field
1082 * is exclusive or on the bits.
1084 q5b = (qef >> 1) ^ mds_poly_divx_const[ qef & 1 ] ^ q;
1086 * Add q5b to qef to set qef = (1+1/x+1/x^2)*q.
1087 * Again, (1+1/x+1/x^2) = EF in the field.
1092 * Now that we have q5b = 5B * q and qef = EF * q
1093 * we can fill two of the entries in the MDS matrix table.
1094 * See the Twofish specifications for the order of the constants.
1096 MDS_table[1][i] = (q <<24) | (q5b<<16) | (qef<<8) | qef;
1097 MDS_table[3][i] = (q5b<<24) | (qef<<16) | (q <<8) | q5b;
1099 /* Now we do it all again for the two columns that have a q1 box. */
1101 qef = (q >> 1) ^ mds_poly_divx_const[ q & 1 ];
1102 q5b = (qef >> 1) ^ mds_poly_divx_const[ qef & 1 ] ^ q;
1105 /* The other two columns use the coefficient in a different order. */
1106 MDS_table[0][i] = (qef<<24) | (qef<<16) | (q5b<<8) | q ;
1107 MDS_table[2][i] = (qef<<24) | (q <<16) | (qef<<8) | q5b;
1113 * The h() function is the heart of the Twofish cipher.
1114 * It is a complicated sequence of q-box lookups, key material xors,
1115 * and finally the MDS matrix.
1116 * We use lots of macros to make this reasonably fast.
1119 /* First a shorthand for the two q-tables */
1120 #define q0 q_table[0]
1121 #define q1 q_table[1]
1124 * Each macro computes one column of the h for either 2, 3, or 4 stages.
1125 * As there are 4 columns, we have 12 macros in all.
1127 * The key bytes are stored in the Byte array L at offset
1128 * 0,1,2,3, 8,9,10,11, [16,17,18,19, [24,25,26,27]] as this is the
1129 * order we get the bytes from the user. If you look at the Twofish
1130 * specs, you'll see that h() is applied to the even key words or the
1131 * odd key words. The bytes of the even words appear in this spacing,
1132 * and those of the odd key words too.
1134 * These macros are the only place where the q-boxes and the MDS table
1137 #define H02( y, L ) MDS_table[0][q0[q0[y]^L[ 8]]^L[0]]
1138 #define H12( y, L ) MDS_table[1][q0[q1[y]^L[ 9]]^L[1]]
1139 #define H22( y, L ) MDS_table[2][q1[q0[y]^L[10]]^L[2]]
1140 #define H32( y, L ) MDS_table[3][q1[q1[y]^L[11]]^L[3]]
1141 #define H03( y, L ) H02( q1[y]^L[16], L )
1142 #define H13( y, L ) H12( q1[y]^L[17], L )
1143 #define H23( y, L ) H22( q0[y]^L[18], L )
1144 #define H33( y, L ) H32( q0[y]^L[19], L )
1145 #define H04( y, L ) H03( q1[y]^L[24], L )
1146 #define H14( y, L ) H13( q0[y]^L[25], L )
1147 #define H24( y, L ) H23( q0[y]^L[26], L )
1148 #define H34( y, L ) H33( q1[y]^L[27], L )
1151 * Now we can define the h() function given an array of key bytes.
1152 * This function is only used in the key schedule, and not to pre-compute
1153 * the keyed S-boxes.
1155 * In the key schedule, the input is always of the form k*(1+2^8+2^16+2^24)
1156 * so we only provide k as an argument.
1159 * k input to the h() function.
1160 * L pointer to array of key bytes at
1161 * offsets 0,1,2,3, ... 8,9,10,11, [16,17,18,19, [24,25,26,27]]
1162 * kCycles # key cycles, 2, 3, or 4.
1164 static Twofish_UInt32 h( int k, Twofish_Byte L[], int kCycles )
1167 /* We code all 3 cases separately for speed reasons. */
1169 return H02(k,L) ^ H12(k,L) ^ H22(k,L) ^ H32(k,L);
1171 return H03(k,L) ^ H13(k,L) ^ H23(k,L) ^ H33(k,L);
1173 return H04(k,L) ^ H14(k,L) ^ H24(k,L) ^ H34(k,L);
1175 /* This is always a coding error, which is fatal. */
1176 Twofish_fatal( "Twofish h(): Illegal argument" );
1183 * Pre-compute the keyed S-boxes.
1184 * Fill the pre-computed S-box array in the expanded key structure.
1185 * Each pre-computed S-box maps 8 bits to 32 bits.
1187 * The S argument contains half the number of bytes of the full key, but is
1188 * derived from the full key. (See Twofish specifications for details.)
1189 * S has the weird byte input order used by the Hxx macros.
1191 * This function takes most of the time of a key expansion.
1194 * S pointer to array of 8*kCycles Bytes containing the S vector.
1195 * kCycles number of key words, must be in the set {2,3,4}
1196 * xkey pointer to Twofish_key structure that will contain the S-boxes.
1198 static void fill_keyed_sboxes( Twofish_Byte S[], int kCycles, Twofish_key * xkey )
1202 /* We code all 3 cases separately for speed reasons. */
1204 for( i=0; i<256; i++ )
1206 xkey->s[0][i]= H02( i, S );
1207 xkey->s[1][i]= H12( i, S );
1208 xkey->s[2][i]= H22( i, S );
1209 xkey->s[3][i]= H32( i, S );
1213 for( i=0; i<256; i++ )
1215 xkey->s[0][i]= H03( i, S );
1216 xkey->s[1][i]= H13( i, S );
1217 xkey->s[2][i]= H23( i, S );
1218 xkey->s[3][i]= H33( i, S );
1222 for( i=0; i<256; i++ )
1224 xkey->s[0][i]= H04( i, S );
1225 xkey->s[1][i]= H14( i, S );
1226 xkey->s[2][i]= H24( i, S );
1227 xkey->s[3][i]= H34( i, S );
1231 /* This is always a coding error, which is fatal. */
1232 Twofish_fatal( "Twofish fill_keyed_sboxes(): Illegal argument" );
1237 /* A flag to keep track of whether we have been initialised or not. */
1238 static int Twofish_initialised = 0;
1241 * Initialise the Twofish implementation.
1242 * This function must be called before any other function in the
1243 * Twofish implementation is called.
1244 * This routine also does some sanity checks, to make sure that
1245 * all the macros behave, and it tests the whole cipher.
1247 void Twofish_initialise()
1249 /* First test the various platform-specific definitions. */
1252 /* We can now generate our tables, in the right order of course. */
1253 initialise_q_boxes();
1254 initialise_mds_tables();
1256 /* We're finished with the initialisation itself. */
1257 Twofish_initialised = 1;
1260 * And run some tests on the whole cipher.
1261 * Yes, you need to do this every time you start your program.
1262 * It is called assurance; you have to be certain that your program
1263 * still works properly.
1270 * The Twofish key schedule uses an Reed-Solomon code matrix multiply.
1271 * Just like the MDS matrix, the RS-matrix is designed to be easy
1272 * to implement. Details are below in the code.
1274 * These constants make it easy to compute in the finite field used
1277 * We use Bytes for the RS computation, but these are automatically
1278 * widened to unsigned integers in the expressions. Having unsigned
1279 * ints in these tables therefore provides the fastest access.
1281 static unsigned int rs_poly_const[] = {0, 0x14d};
1282 static unsigned int rs_poly_div_const[] = {0, 0xa6 };
1286 * Prepare a key for use in encryption and decryption.
1287 * Like most block ciphers, Twofish allows the key schedule
1288 * to be pre-computed given only the key.
1289 * Twofish has a fairly 'heavy' key schedule that takes a lot of time
1290 * to compute. The main work is pre-computing the S-boxes used in the
1291 * encryption and decryption. We feel that this makes the cipher much
1292 * harder to attack. The attacker doesn't even know what the S-boxes
1293 * contain without including the entire key schedule in the analysis.
1295 * Unlike most Twofish implementations, this one allows any key size from
1296 * 0 to 32 bytes. Odd key sizes are defined for Twofish (see the
1297 * specifications); the key is simply padded with zeroes to the next real
1298 * key size of 16, 24, or 32 bytes.
1299 * Each odd-sized key is thus equivalent to a single normal-sized key.
1302 * key array of key bytes
1303 * key_len number of bytes in the key, must be in the range 0,...,32.
1304 * xkey Pointer to an Twofish_key structure that will be filled
1305 * with the internal form of the cipher key.
1307 void Twofish_prepare_key( Twofish_Byte key[], int key_len, Twofish_key * xkey )
1309 /* We use a single array to store all key material in,
1310 * to simplify the wiping of the key material at the end.
1311 * The first 32 bytes contain the actual (padded) cipher key.
1312 * The next 32 bytes contain the S-vector in its weird format,
1313 * and we have 4 bytes of overrun necessary for the RS-reduction.
1315 Twofish_Byte K[32+32+4];
1317 int kCycles; /* # key cycles, 2,3, or 4. */
1320 Twofish_UInt32 A, B; /* Used to compute the round keys. */
1322 Twofish_Byte * kptr; /* Three pointers for the RS computation. */
1323 Twofish_Byte * sptr;
1326 Twofish_Byte b,bx,bxx; /* Some more temporaries for the RS computation. */
1328 /* Check that the Twofish implementation was initialised. */
1329 if( Twofish_initialised == 0 )
1332 * You didn't call Twofish_initialise before calling this routine.
1333 * This is a programming error, and therefore we call the fatal
1336 * I could of course call the initialisation routine here,
1337 * but there are a few reasons why I don't. First of all, the
1338 * self-tests have to be done at startup. It is no good to inform
1339 * the user that the cipher implementation fails when he wants to
1340 * write his data to disk in encrypted form. You have to warn him
1341 * before he spends time typing his data. Second, the initialisation
1342 * and self test are much slower than a single key expansion.
1343 * Calling the initialisation here makes the performance of the
1344 * cipher unpredictable. This can lead to really weird problems
1345 * if you use the cipher for a real-time task. Suddenly it fails
1346 * once in a while the first time you try to use it. Things like
1347 * that are almost impossible to debug.
1349 Twofish_fatal( "Twofish implementation was not initialised." );
1352 * There is always a danger that the Twofish_fatal routine returns,
1353 * in spite of the specifications that it should not.
1354 * (A good programming rule: don't trust the rest of the code.)
1355 * This would be disasterous. If the q-tables and MDS-tables have
1356 * not been initialised, they are probably still filled with zeroes.
1357 * Suppose the MDS-tables are all zero. The key expansion would then
1358 * generate all-zero round keys, and all-zero s-boxes. The danger
1359 * is that nobody would notice as the encryption function still
1360 * mangles the input, and the decryption still 'decrypts' it,
1361 * but now in a completely key-independent manner.
1362 * To stop such security disasters, we use blunt force.
1363 * If your program hangs here: fix the fatal routine!
1365 for(;;) ; /* Infinite loop, which beats being insecure. */
1368 /* Check for valid key length. */
1369 if( key_len < 0 || key_len > 32 )
1372 * This can only happen if a programmer didn't read the limitations
1375 Twofish_fatal( "Twofish_prepare_key: illegal key length" );
1377 * A return statement just in case the fatal macro returns.
1378 * The rest of the code assumes that key_len is in range, and would
1379 * buffer-overflow if it wasn't.
1381 * Why do we still use a programming language that has problems like
1382 * buffer overflows, when these problems were solved in 1960 with
1383 * the development of Algol? Have we not leared anything?
1388 /* Pad the key with zeroes to the next suitable key length. */
1389 memcpy( K, key, key_len );
1390 memset( K+key_len, 0, sizeof(K)-key_len );
1393 * Compute kCycles: the number of key cycles used in the cipher.
1394 * 2 for 128-bit keys, 3 for 192-bit keys, and 4 for 256-bit keys.
1396 kCycles = (key_len + 7) >> 3;
1397 /* Handle the special case of very short keys: minimum 2 cycles. */
1404 * From now on we just pretend to have 8*kCycles bytes of
1405 * key material in K. This handles all the key size cases.
1409 * We first compute the 40 expanded key words,
1410 * formulas straight from the Twofish specifications.
1412 for( i=0; i<40; i+=2 )
1415 * Due to the byte spacing expected by the h() function
1416 * we can pick the bytes directly from the key K.
1417 * As we use bytes, we never have the little/big endian
1420 * Note that we apply the rotation function only to simple
1421 * variables, as the rotation macro might evaluate its argument
1424 A = h( i , K , kCycles );
1425 B = h( i+1, K+4, kCycles );
1428 /* Compute and store the round keys. */
1432 xkey->K[i+1] = ROL32( B, 9 );
1435 /* Wipe variables that contained key material. */
1439 * And now the dreaded RS multiplication that few seem to understand.
1440 * The RS matrix is not random, and is specially designed to compute the
1441 * RS matrix multiplication in a simple way.
1443 * We work in the field GF(2)[x]/x^8+x^6+x^3+x^2+1. Note that this is a
1444 * different field than used for the MDS matrix.
1445 * (At least, it is a different representation because all GF(2^8)
1446 * representations are equivalent in some form.)
1448 * We take 8 consecutive bytes of the key and interpret them as
1449 * a polynomial k_0 + k_1 y + k_2 y^2 + ... + k_7 y^7 where
1450 * the k_i bytes are the key bytes and are elements of the finite field.
1451 * We multiply this polynomial by y^4 and reduce it modulo
1452 * y^4 + (x + 1/x)y^3 + (x)y^2 + (x + 1/x)y + 1.
1453 * using straightforward polynomial modulo reduction.
1454 * The coefficients of the result are the result of the RS
1455 * matrix multiplication. When we wrote the Twofish specification,
1456 * the original RS definition used the polynomials,
1457 * but that requires much more mathematical knowledge.
1458 * We were already using matrix multiplication in a finite field for
1459 * the MDS matrix, so I re-wrote the RS operation as a matrix
1460 * multiplication to reduce the difficulty of understanding it.
1461 * Some implementors have not picked up on this simpler method of
1462 * computing the RS operation, even though it is mentioned in the
1465 * It is possible to perform these computations faster by using 32-bit
1466 * word operations, but that is not portable and this is not a speed-
1469 * We explained the 1/x computation when we did the MDS matrix.
1471 * The S vector is stored in K[32..64].
1472 * The S vector has to be reversed, so we loop cross-wise.
1474 * Note the weird byte spacing of the S-vector, to match the even
1475 * or odd key words arrays. See the discussion at the Hxx macros for
1478 kptr = K + 8*kCycles; /* Start at end of key */
1479 sptr = K + 32; /* Start at start of S */
1481 /* Loop over all key material */
1486 * Initialise the polynimial in sptr[0..12]
1487 * The first four coefficients are 0 as we have to multiply by y^4.
1488 * The next 8 coefficients are from the key material.
1490 memset( sptr, 0, 4 );
1491 memcpy( sptr+4, kptr, 8 );
1494 * The 12 bytes starting at sptr are now the coefficients of
1495 * the polynomial we need to reduce.
1498 /* Loop over the polynomial coefficients from high to low */
1500 /* Keep looping until polynomial is degree 3; */
1503 /* Pick up the highest coefficient of the poly. */
1507 * Compute x and (x+1/x) times this coefficient.
1508 * See the MDS matrix implementation for a discussion of
1509 * multiplication by x and 1/x. We just use different
1510 * constants here as we are in a
1511 * different finite field representation.
1513 * These two statements set
1515 * bxx= (x + 1/x) * b
1517 bx = (Twofish_Byte)((b<<1) ^ rs_poly_const[ b>>7 ]);
1518 bxx= (Twofish_Byte)((b>>1) ^ rs_poly_div_const[ b&1 ] ^ bx);
1521 * Subtract suitable multiple of
1522 * y^4 + (x + 1/x)y^3 + (x)y^2 + (x + 1/x)y + 1
1523 * from the polynomial, except that we don't bother
1524 * updating t[0] as it will become zero anyway.
1531 /* Go to the next coefficient. */
1535 /* Go to next S-vector word, obeying the weird spacing rules. */
1539 /* Wipe variables that contained key material. */
1542 /* And finally, we can compute the key-dependent S-boxes. */
1543 fill_keyed_sboxes( &K[32], kCycles, xkey );
1545 /* Wipe array that contained key material. */
1546 memset( K, 0, sizeof( K ) );
1551 * We can now start on the actual encryption and decryption code.
1552 * As these are often speed-critical we will use a lot of macros.
1556 * The g() function is the heart of the round function.
1557 * We have two versions of the g() function, one without an input
1558 * rotation and one with.
1559 * The pre-computed S-boxes make this pretty simple.
1561 #define g0(X,xkey) \
1562 (xkey->s[0][b0(X)]^xkey->s[1][b1(X)]^xkey->s[2][b2(X)]^xkey->s[3][b3(X)])
1564 #define g1(X,xkey) \
1565 (xkey->s[0][b3(X)]^xkey->s[1][b0(X)]^xkey->s[2][b1(X)]^xkey->s[3][b2(X)])
1568 * A single round of Twofish. The A,B,C,D are the four state variables,
1569 * T0 and T1 are temporaries, xkey is the expanded key, and r the
1572 * Note that this macro does not implement the swap at the end of the round.
1574 #define ENCRYPT_RND( A,B,C,D, T0, T1, xkey, r ) \
1575 T0 = g0(A,xkey); T1 = g1(B,xkey);\
1576 C ^= T0+T1+xkey->K[8+2*(r)]; C = ROR32(C,1);\
1577 D = ROL32(D,1); D ^= T0+2*T1+xkey->K[8+2*(r)+1]
1580 * Encrypt a single cycle, consisting of two rounds.
1581 * This avoids the swapping of the two halves.
1582 * Parameter r is now the cycle number.
1584 #define ENCRYPT_CYCLE( A, B, C, D, T0, T1, xkey, r ) \
1585 ENCRYPT_RND( A,B,C,D,T0,T1,xkey,2*(r) );\
1586 ENCRYPT_RND( C,D,A,B,T0,T1,xkey,2*(r)+1 )
1588 /* Full 16-round encryption */
1589 #define ENCRYPT( A,B,C,D,T0,T1,xkey ) \
1590 ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 0 );\
1591 ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 1 );\
1592 ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 2 );\
1593 ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 3 );\
1594 ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 4 );\
1595 ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 5 );\
1596 ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 6 );\
1597 ENCRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 7 )
1600 * A single round of Twofish for decryption. It differs from
1601 * ENCRYTP_RND only because of the 1-bit rotations.
1603 #define DECRYPT_RND( A,B,C,D, T0, T1, xkey, r ) \
1604 T0 = g0(A,xkey); T1 = g1(B,xkey);\
1605 C = ROL32(C,1); C ^= T0+T1+xkey->K[8+2*(r)];\
1606 D ^= T0+2*T1+xkey->K[8+2*(r)+1]; D = ROR32(D,1)
1609 * Decrypt a single cycle, consisting of two rounds.
1610 * This avoids the swapping of the two halves.
1611 * Parameter r is now the cycle number.
1613 #define DECRYPT_CYCLE( A, B, C, D, T0, T1, xkey, r ) \
1614 DECRYPT_RND( A,B,C,D,T0,T1,xkey,2*(r)+1 );\
1615 DECRYPT_RND( C,D,A,B,T0,T1,xkey,2*(r) )
1617 /* Full 16-round decryption. */
1618 #define DECRYPT( A,B,C,D,T0,T1, xkey ) \
1619 DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 7 );\
1620 DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 6 );\
1621 DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 5 );\
1622 DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 4 );\
1623 DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 3 );\
1624 DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 2 );\
1625 DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 1 );\
1626 DECRYPT_CYCLE( A,B,C,D,T0,T1,xkey, 0 )
1629 * A macro to read the state from the plaintext and do the initial key xors.
1630 * The koff argument allows us to use the same macro
1631 * for the decryption which uses different key words at the start.
1633 #define GET_INPUT( src, A,B,C,D, xkey, koff ) \
1634 A = GET32(src )^xkey->K[ koff]; B = GET32(src+ 4)^xkey->K[1+koff]; \
1635 C = GET32(src+ 8)^xkey->K[2+koff]; D = GET32(src+12)^xkey->K[3+koff]
1638 * Similar macro to put the ciphertext in the output buffer.
1639 * We xor the keys into the state variables before we use the PUT32
1640 * macro as the macro might use its argument multiple times.
1642 #define PUT_OUTPUT( A,B,C,D, dst, xkey, koff ) \
1643 A ^= xkey->K[ koff]; B ^= xkey->K[1+koff]; \
1644 C ^= xkey->K[2+koff]; D ^= xkey->K[3+koff]; \
1645 PUT32( A, dst ); PUT32( B, dst+ 4 ); \
1646 PUT32( C, dst+8 ); PUT32( D, dst+12 )
1650 * Twofish block encryption
1653 * xkey expanded key array
1654 * p 16 bytes of plaintext
1655 * c 16 bytes in which to store the ciphertext
1657 void Twofish_encrypt( Twofish_key * xkey, Twofish_Byte p[16], Twofish_Byte c[16])
1659 Twofish_UInt32 A,B,C,D,T0,T1; /* Working variables */
1661 /* Get the four plaintext words xorred with the key */
1662 GET_INPUT( p, A,B,C,D, xkey, 0 );
1664 /* Do 8 cycles (= 16 rounds) */
1665 ENCRYPT( A,B,C,D,T0,T1,xkey );
1667 /* Store them with the final swap and the output whitening. */
1668 PUT_OUTPUT( C,D,A,B, c, xkey, 4 );
1673 * Twofish block decryption.
1676 * xkey expanded key array
1677 * p 16 bytes of plaintext
1678 * c 16 bytes in which to store the ciphertext
1680 void Twofish_decrypt( Twofish_key * xkey, Twofish_Byte c[16], Twofish_Byte p[16])
1682 Twofish_UInt32 A,B,C,D,T0,T1; /* Working variables */
1684 /* Get the four plaintext words xorred with the key */
1685 GET_INPUT( c, A,B,C,D, xkey, 4 );
1687 /* Do 8 cycles (= 16 rounds) */
1688 DECRYPT( A,B,C,D,T0,T1,xkey );
1690 /* Store them with the final swap and the output whitening. */
1691 PUT_OUTPUT( C,D,A,B, p, xkey, 0 );
1695 * Using the macros it is easy to make special routines for
1696 * CBC mode, CTR mode etc. The only thing you might want to
1697 * add is a XOR_PUT_OUTPUT which xors the outputs into the
1698 * destinationa instead of overwriting the data. This requires
1699 * a XOR_PUT32 macro as well, but that should all be trivial.
1701 * I thought about including routines for the separate cipher
1702 * modes here, but it is unclear which modes should be included,
1703 * and each encryption or decryption routine takes up a lot of code space.
1704 * Also, I don't have any test vectors for any cipher modes