The Twofish Algorithm

The Twofish Algorithm

Introduction

Twofish is Bruce Schneier’s direct successor to Blowfish. A team that included Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, and Niels Ferguson designed it in 1998. It was submitted to NIST’s AES competition, and it reached the final round of five candidates. It lost to Rijndael, which became AES, but it has never suffered a practical break. Twofish is free, unpatented, and open to everyone.

This guide covers the real cipher. The visualizer and the Python code below run the full Twofish with keys of 128, 192, and 256 bits. They build the S-boxes and the matrices from their definitions, and they reproduce the designers’ own test values. Every value in the worked example comes from that code, and every intermediate value of it matches the designers’ test file.

Table of Contents

• Design Goals and History
• How Twofish Works
• The Function g
• The Key Schedule
• The Pseudo-Hadamard Transform
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• Twofish vs. AES: Why Rijndael Won
• FAQ
• References

Design Goals and History

Blowfish’s biggest structural flaw was its 64-bit block size. Large amounts of data under one key expose it to birthday-bound attacks such as Sweet32. Twofish keeps the spirit of Blowfish, which is a fast, software-friendly design with key-dependent parts, and it moves to a 128-bit block, as NIST required for every AES candidate. NIST also required keys of 128, 192, and 256 bits, and Twofish supports all three.

Schneier’s own description of the cipher is short. Twofish is a 16-round Feistel network with a bijective F function made up of four key-dependent 8-by-8-bit S-boxes, a fixed 4-by-4 maximum distance separable (MDS) matrix over GF(2^8), a pseudo-Hadamard transform, bitwise rotations, and a carefully designed key schedule. The designers report 17.8 clock cycles per byte on a Pentium Pro, 1,820 clock cycles per byte for an 8-bit smart card implementation, and a hardware size of about 14,000 gates. The cipher stayed free for all uses, and the designers published reference code and test vectors with their submission.

How Twofish Works

Twofish works on 16-byte blocks. The block is read as four 32-bit little-endian words. Twofish does not split the block into two halves as DES and Blowfish do. It keeps two pairs of words and updates one pair in each round, using the other pair as the input of the round function. The whole encryption fits in a few lines:

R0, R1, R2, R3 = the four words of the block, each XORed with K0, K1, K2, K3
for r = 0 to 15:
    T0 = g(R0)
    T1 = g(rotl(R1, 8))
    F0 = (T0 + T1 + K[8 + 2r])  mod 2^32
    F1 = (T0 + 2*T1 + K[9 + 2r]) mod 2^32
    R2 = rotr(R2 xor F0, 1)
    R3 = rotl(R3, 1) xor F1
    if r < 15:  swap (R0, R1) with (R2, R3)
output words = R0 xor K4, R1 xor K5, R2 xor K6, R3 xor K7

The 40 words K0 to K39 are the subkeys. The first four, K0 to K3, are the input whitening. They are XORed into the block before the first round. The next four, K4 to K7, are the output whitening. The other 32 subkeys, two for each round, start at K8. Whitening adds protection against attacks on the outer rounds, because an attacker does not know the values that go into the first round or come out of the last.

Each round runs two copies of the function g on one pair of words. The Pseudo-Hadamard Transform mixes the two results with two subkeys into F0 and F1. These values are then XORed into the other pair, with a one-bit rotation. The pairs swap, so in the next round the updated pair feeds the function g. The small rotations are what make Twofish more than a plain Feistel network, and they are the reason that decryption is not just the same code with the subkeys reversed.

Decryption undoes the last step first. It XORs the output whitening, then runs the 16 rounds backward. In each round, R2 is rotated left by 1 and XORed with F0, and R3 is XORed with F1 and rotated right by 1. The values T0 and T1 come out the same as in encryption, because the pair that feeds g is the same. Then the pairs are swapped back, and the input whitening is XORed away.

The Function g

The function g is where Twofish gets its key-dependent S-boxes. It takes a 32-bit word, and it returns a 32-bit word, in three stages.

1. Split. The word is cut into four bytes, with the lowest byte first.
2. S-boxes. Each byte goes through a chain of fixed permutations of the 256 byte values, named q0 and q1. Between the permutations, a byte of key material is XORed in. This makes the S-box for each byte position depend on the key.
3. MDS matrix. The four bytes are multiplied by a fixed 4 by 4 matrix over the field GF(2^8). The product is again four bytes, which form the output word.

The permutations q0 and q1. The two 256-byte permutations are not typed in as 256 numbers. Each is built from four small 4-bit permutations, which are tables of 16 entries. For q0 the tables are:

817D6F320B59ECA4
ECB81235F4A6709D
BA5E6D90C8F32471
D7F4126E9B3085CA

and for q1 they are:

28BDF76E31940AC5
1E2B4C376DA5F908
4C75169A0ED82B3F
B951C3DE647F208A

To compute q(x), split the byte into its high and low 4 bits, a0 and b0. Then compute a1 = a0 xor b0, and b1 = a0 xor ror4(b0, 1) xor (8 * a0 mod 16). Look up a2 = t0[a1] and b2 = t1[b1]. Compute a3 = a2 xor b2, and b3 = a2 xor ror4(b2, 1) xor (8 * a2 mod 16). Look up a4 = t2[a3] and b4 = t3[b3]. The result is 16 * b4 + a4. Here ror4 rotates a 4-bit number right. For x = 00, the steps give a0 = 0 and b0 = 0, then a1 = 0 and b1 = 0, then a2 = 8 and b2 = E, then a3 = 6 and b3 = F, and last a4 = 9 and b4 = A. This gives q0(00) = A9, which is the first entry of the table in the reference code. The first 16 values of q0 are A9 67 B3 E8 04 FD A3 76 9A 92 80 78 E4 DD D1 38, and the first 16 values of q1 are 75 F3 C6 F4 DB 7B FB C8 4A D3 E6 6B 45 7D E8 4B. These match the tables in the designers’ reference code, byte for byte.

The chain of permutations. Let S be a list of k key words, with k equal to 2, 3, or 4 for keys of 128, 192, or 256 bits. The function h takes a word x and this list. It works on the four bytes y0 to y3 of x, and l(j,i) means byte i of the key word j:

if k = 4:   y0 = q1(y0) xor l(3,0)    y1 = q0(y1) xor l(3,1)    y2 = q0(y2) xor l(3,2)    y3 = q1(y3) xor l(3,3)
if k >= 3:  y0 = q1(y0) xor l(2,0)    y1 = q1(y1) xor l(2,1)    y2 = q0(y2) xor l(2,2)    y3 = q0(y3) xor l(2,3)
always:     y0 = q1( q0( q0(y0) xor l(1,0) ) xor l(0,0) )
            y1 = q0( q0( q1(y1) xor l(1,1) ) xor l(0,1) )
            y2 = q1( q1( q0(y2) xor l(1,2) ) xor l(0,2) )
            y3 = q0( q1( q1(y3) xor l(1,3) ) xor l(0,3) )

Larger keys add one more layer of permutations and key bytes for each extra 64 bits of key. The result (y0, y1, y2, y3) goes through the MDS matrix.

The MDS matrix. The matrix is, with its entries written in hexadecimal:

01  EF  5B  5B
5B  EF  EF  01
EF  5B  01  EF
EF  01  EF  5B

The entries are elements of GF(2^8), the field of bytes in which addition is XOR. Multiplication is the multiplication of polynomials with binary coefficients, reduced by the polynomial x^8 + x^6 + x^5 + x^3 + 1, which is 0x169. The output byte i is the XOR of the four products of row i with y0 to y3. The matrix is MDS, which means that it has the best possible diffusion for its size: a change in one input byte changes all four output bytes. This is the same role as MixColumns in AES. The function g is h with the list S of S-box key words, which the key schedule makes from the key.

The Key Schedule

The key schedule turns a key of 16, 24, or 32 bytes into two things: the list S of S-box key words for g, and the 40 subkeys. Let the key be read as 2k little-endian words M0, M1, ..., M(2k-1). The words with even numbers are Me = (M0, M2, ...), and the words with odd numbers are Mo = (M1, M3, ...).

The S-box key words. For each pair of key words, (M(2i), M(2i+1)), the 8 bytes of the pair are multiplied by a fixed 4 by 8 matrix over GF(2^8), which makes 4 bytes, that is one word S(i). This is a Reed-Solomon code, a (12,8) code over GF(2^8) with the field polynomial x^8 + x^6 + x^3 + x^2 + 1, which is 0x14D. The list S is the words in the reverse order, so the word made from the last pair of key words comes first. The matrix looks like this:

01  A4  55  87  5A  58  DB  9E
A4  56  82  F3  1E  C6  68  E5
02  A1  FC  C1  47  AE  3D  19
A4  55  87  5A  58  DB  9E  03

For example, the first 8 bytes of the 192-bit key of the designers’ second test are 0123456789ABCDEF. The four output bytes are the XORs of eight products each:

s0 = 01 xor F1 xor 91 xor 99 xor C9 xor 03 xor A9 xor 69 = F2
s1 = A4 xor 52 xor 8F xor 66 xor B2 xor B9 xor 1C xor FE = F6
s2 = 02 xor 5E xor 31 xor 50 xor AD xor 9F xor 48 xor D8 = 9F
s3 = A4 xor 37 xor 93 xor 64 xor 96 xor 90 xor A6 xor 7C = B8

So the first S-box key word is B89FF6F2, from the bytes F2 F6 9F B8 read little-endian. This is the value that the designers’ test file lists for that pair of key words. For that whole key, the list S is 45661061 B255BC4B B89FF6F2.

The subkeys. Define the constant rho = 0x01010101. For i from 0 to 19, compute:

A = h(2i * rho,     Me)
B = rotl( h((2i + 1) * rho, Mo), 8 )
K(2i)   = (A + B) mod 2^32
K(2i+1) = rotl( (A + 2B) mod 2^32, 9 )

The subkeys use the same function h as g does, but with the key words themselves in place of the S-box key words. Every subkey therefore depends on the whole key through h, and the last two lines are a Pseudo-Hadamard Transform again. The key words enter h directly here, while g uses the S-box key words that the Reed-Solomon code made from them.

The Pseudo-Hadamard Transform

The PHT is a fast, simple mixing operation. In each round it takes the two outputs T0 and T1 of g, and it makes two new values:

F0 = (T0 + T1)     mod 2^32
F1 = (T0 + 2*T1)   mod 2^32

In Twofish, two subkeys are added to these, as the round code above shows. The PHT spreads the influence of each input bit across both outputs using only additions. This is cheap on ordinary processors compared with a more complex diffusion step. Each of F0 and F1 depends on both T0 and T1. The key schedule applies the same transform to A and B, with a rotation after the second result.

Interactive Visualizer

The visualizer above runs real Twofish. Choose Encrypt or Decrypt. Enter a key as hex, with 32, 48, or 64 characters for 128, 192, or 256 bits, and one 16-byte block as 32 hex characters. Then click the button. The log shows the input words, the S-box key words of the key schedule, the whitening, and every round. For each round, it shows the two subkeys, T0, T1, the two values F0 and F1, and the four words of the state. The state is written as in the designers’ test file, so you can compare with it. When the run ends, the page runs the opposite direction on the result and tells you whether it got your input back. The default is the designers’ first test vector, so the first run ends with 9F589F5CF6122C32B6BFEC2F2AE8C35A.

A Worked Example

This is the first test vector of the designers. The key has 128 zero bits, and the block has 128 zero bits. The published ciphertext is 9F589F5CF6122C32B6BFEC2F2AE8C35A. The designers’ test file also lists every intermediate value, and the code in this guide reproduces all of them.

The key schedule. For a key of zeros, all key words are zero, so the S-box key words are zero too: both words of S are 00000000. The subkeys come from h with zero key words. For i = 0, we get A = h(0) = 6F01A38B, and h(01010101) = 53E3C3AA, which rotated left by 8 bits is B = E3C3AA53. This gives K0 = A + B = 52C54DDE, the value in the designers’ file. And A + 2B = 3688F831, which rotated left by 9 bits is K1 = 11F0626D. The 40 subkeys are:

K0 = 52C54DDE   K1 = 11F0626D
K2 = 7CAC9D4A   K3 = 4D1B4AAA
K4 = B7B83A10   K5 = 1E7D0BEB
K6 = EE9C341F   K7 = CFE14BE4
K8  = F98FFEF9   K9  = 9C5B3C17   K10 = 15A48310   K11 = 342A4D81
K12 = 424D89FE   K13 = C14724A7   K14 = 311B834C   K15 = FDE87320
K16 = 3302778F   K17 = 26CD67B4   K18 = 7A6C6362   K19 = C2BAF60E
K20 = 3411B994   K21 = D972C87F   K22 = 84ADB1EA   K23 = A7DEE434
K24 = 54D2960F   K25 = A2F7CAA8   K26 = A6B8FF8C   K27 = 8014C425
K28 = 6A748D1C   K29 = EDBAF720   K30 = 928EF78C   K31 = 0338EE13
K32 = 9949D6BE   K33 = C8314176   K34 = 07C07D68   K35 = ECAE7EA7
K36 = 1FE71844   K37 = 85C05C89   K38 = F298311E   K39 = 696EA672

The first two lines are the input whitening, the third and fourth are the output whitening, and the rest are the round subkeys.

Input whitening. The plaintext words are zero. After the XOR with K0 to K3, the state is R0 = 52C54DDE, R1 = 11F0626D, R2 = 7CAC9D4A, and R3 = 4D1B4AAA.

Round 1, the function g. The word R0 = 52C54DDE has the bytes DE 4D C5 52, with the lowest byte first. With zero key words, each byte goes through a chain of three permutations. The byte DE goes through q0, then q0, then q1, and the other bytes go through the chains of the definition above. The first permutation gives 99 28 3C 9C, the second gives 9C 19 92 C4, and the third gives y = C4 75 26 88. The MDS matrix then gives each output byte as an XOR of four products in GF(2^8):

byte 0: C4 xor BC xor 9B xor AA = 49
byte 1: F5 xor BC xor 88 xor 88 = 49
byte 2: 97 xor 32 xor 26 xor EE = 6D
byte 3: 97 xor 75 xor 88 xor AA = C0

So T0 = g(R0) = C06D4949, which is the value in the designers’ file. For T1, the word R1 rotated left by 8 bits is F0626D11, and T1 = g(F0626D11) = 41B9BFC1.

Round 1, the rest. With the subkeys K8 = F98FFEF9 and K9 = 9C5B3C17, we get F0 = T0 + T1 + K8 = FBB70803 and F1 = T0 + 2 T1 + K9 = E03C04E2. Next, R2 xor F0 = 871B9549, which rotated right by 1 is C38DCAA4. The word R3 rotated left by 1 is 9A369554, and XOR with F1 gives 7A0A91B6. The pairs swap, and the state is 52C54DDE 11F0626D C38DCAA4 7A0A91B6, with the updated pair last.

All 16 rounds. The table shows the subkeys, T0, T1, and the state after each round, in the form of the designers’ test file. In this form, the updated pair of words alternates between the first two places and the last two places from one round to the next, because the pairs swap.

Round	Subkeys	T0	T1	State after the round
1	F98FFEF9 9C5B3C17	C06D4949	41B9BFC1	52C54DDE 11F0626D C38DCAA4 7A0A91B6
2	15A48310 342A4D81	7C4536B9	67A58299	55A538DE 5C5A4DB6 C38DCAA4 7A0A91B6
3	424D89FE C14724A7	60DAC1A4	2D84C23D	55A538DE 5C5A4DB6 899063BD 893E49A9
4	311B834C FDE87320	607AAEAD	6ED2DBF9	2AE61A96 84BC42D3 899063BD 893E49A9
5	3302778F 26CD67B4	067D0B49	318EACB4	2AE61A96 84BC42D3 F14F2618 821B5F36
6	7A6C6362 C2BAF60E	58554EDB	62585CF7	0FFE0AD1 D6B87B70 F14F2618 821B5F36
7	3411B994 D972C87F	839B0017	B3A89DB0	0FFE0AD1 D6B87B70 CD0D38A1 C069BD9B
8	84ADB1EA A7DEE434	E9BC6975	F0DDA4C3	A85CE579 DE2661CE CD0D38A1 C069BD9B
9	54D2960F A2F7CAA8	54687CDF	9044BF4B	A85CE579 DE2661CE 7A39754C 973ABD2A
10	A6B8FF8C 8014C425	77FC927F	8B8678CC	013077D7 B3528BA1 7A39754C 973ABD2A
11	6A748D1C EDBAF720	E3C81108	828E7493	013077D7 B3528BA1 D57933FD F8EA8B1B
12	928EF78C 0338EE13	B33C25D6	83068533	64F0EAA1 DA27090C D57933FD F8EA8B1B
13	9949D6BE C8314176	A0AA2F81	FFF30DB7	64F0EAA1 DA27090C F64F1005 99149A52
14	07C07D68 ECAE7EA7	114C17C5	EB143CFF	B0681C46 606D0273 F64F1005 99149A52
15	1FE71844 85C05C89	677DA87D	989D1459	B0681C46 606D0273 EB27628F 2C51191D
16	F298311E 696EA672	9357B338	AC9926BF	C1708BA9 9522A3CE EB27628F 2C51191D

The output step. After round 16 there is no swap. The state is C1708BA9 9522A3CE EB27628F 2C51191D, with the updated pair first. The output words are the XORs of the unchanged pair with K4 and K5, and of the updated pair with K6 and K7:

EB27628F xor B7B83A10 = 5C9F589F
2C51191D xor 1E7D0BEB = 322C12F6
C1708BA9 xor EE9C341F = 2FECBFB6
9522A3CE xor CFE14BE4 = 5AC3E82A

The words 5C9F589F 322C12F6 2FECBFB6 5AC3E82A, written as little-endian bytes, are the ciphertext:

9F589F5CF6122C32B6BFEC2F2AE8C35A

Other key sizes. The same all-zero block under the 192-bit key 0123456789ABCDEFFEDCBA98765432100011223344556677 gives CFD1D2E5A9BE9CDF501F13B892BD2248. Under the 256-bit key 0123456789ABCDEFFEDCBA987654321000112233445566778899AABBCCDDEEFF it gives 37527BE0052334B89F0CFCCAE87CFA20. Both values are in the designers’ test file. Changing the last bit of the zero plaintext, with the 128-bit zero key, gives CA737FF1FD0FE5B8E41E90358A5F2CB1, which differs from the first ciphertext in 65 of the 128 bits.

Python Implementation

This is a complete Twofish, with all three key sizes and both directions, for one 16-byte block. Nothing is copied from a table of constants. The permutations q0 and q1 come from the 4-bit tables, the MDS and Reed-Solomon matrices are the small matrices above, and the multiplications use ordinary field arithmetic. The optional trace argument of the encryption reports every round, which is how the numbers above were collected.

# twofish.py
#
# Twofish (Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall
# and Niels Ferguson, 1998): a 128-bit block cipher with keys of 128, 192 or 256
# bits and 16 rounds. Nothing here is copied from a table of constants. The two
# 8-bit permutations q0 and q1 are built from small 4-bit tables, the MDS matrix
# and the Reed-Solomon matrix are small matrices over GF(2^8), and the rest is
# the cipher itself. Words and blocks are little-endian, as in the specification.

MASK = 0xFFFFFFFF

# q0 and q1 are made from four 4-bit permutations each
T_Q0 = ("817D6F320B59ECA4", "ECB81235F4A6709D", "BA5E6D90C8F32471", "D7F4126E9B3085CA")
T_Q1 = ("28BDF76E31940AC5", "1E2B4C376DA5F908", "4C75169A0ED82B3F", "B951C3DE647F208A")


def ror4(x, n):
    return ((x >> n) | (x << (4 - n))) & 15


def make_q(tables):
    t0, t1, t2, t3 = ([int(c, 16) for c in t] for t in tables)
    q = []
    for x in range(256):
        a0, b0 = x >> 4, x & 15
        a1 = a0 ^ b0
        b1 = a0 ^ ror4(b0, 1) ^ ((8 * a0) & 15)
        a2, b2 = t0[a1], t1[b1]
        a3 = a2 ^ b2
        b3 = a2 ^ ror4(b2, 1) ^ ((8 * a2) & 15)
        a4, b4 = t2[a3], t3[b3]
        q.append(16 * b4 + a4)
    return q


Q0 = make_q(T_Q0)
Q1 = make_q(T_Q1)


def gf_mul(a, b, poly):
    """Multiply two bytes in GF(2^8) modulo the polynomial `poly` (a 9-bit number)."""
    r = 0
    while b:
        if b & 1:
            r ^= a
        a <<= 1
        if a & 0x100:
            a ^= poly
        b >>= 1
    return r


MDS_POLY = 0x169  # x^8 + x^6 + x^5 + x^3 + 1
RS_POLY = 0x14D   # x^8 + x^6 + x^3 + x^2 + 1

MDS = ((0x01, 0xEF, 0x5B, 0x5B),
       (0x5B, 0xEF, 0xEF, 0x01),
       (0xEF, 0x5B, 0x01, 0xEF),
       (0xEF, 0x01, 0xEF, 0x5B))

RS = ((0x01, 0xA4, 0x55, 0x87, 0x5A, 0x58, 0xDB, 0x9E),
      (0xA4, 0x56, 0x82, 0xF3, 0x1E, 0xC6, 0x68, 0xE5),
      (0x02, 0xA1, 0xFC, 0xC1, 0x47, 0xAE, 0x3D, 0x19),
      (0xA4, 0x55, 0x87, 0x5A, 0x58, 0xDB, 0x9E, 0x03))

MUL_5B = [gf_mul(x, 0x5B, MDS_POLY) for x in range(256)]
MUL_EF = [gf_mul(x, 0xEF, MDS_POLY) for x in range(256)]
_MDS_TABLE = {0x01: list(range(256)), 0x5B: MUL_5B, 0xEF: MUL_EF}


def mds_multiply(y):
    """The 4x4 MDS matrix times four bytes, as one 32-bit word (the first result byte is the lowest)."""
    out = 0
    for row in range(4):
        v = 0
        for col in range(4):
            v ^= _MDS_TABLE[MDS[row][col]][y[col]]
        out |= v << (8 * row)
    return out


def rs_word(key8):
    """The Reed-Solomon code: 8 key bytes become 4 bytes of S-box key, as a 32-bit word."""
    out = 0
    for row in range(4):
        v = 0
        for col in range(8):
            v ^= gf_mul(RS[row][col], key8[col], RS_POLY)
        out |= v << (8 * row)
    return out


def rol(x, n):
    n %= 32
    return ((x << n) | (x >> (32 - n))) & MASK if n else x


def ror(x, n):
    return rol(x, 32 - (n % 32))


def h(x, words):
    """The function h: four bytes through q-permutations, mixed with the key words, then the MDS matrix.

    `words` has k key words (2, 3 or 4). The word words[0] is used in the innermost layer.
    """
    y = list(x.to_bytes(4, "little"))
    k = len(words)
    b = [[(w >> (8 * i)) & 255 for i in range(4)] for w in words]
    if k == 4:
        y = [Q1[y[0]] ^ b[3][0], Q0[y[1]] ^ b[3][1], Q0[y[2]] ^ b[3][2], Q1[y[3]] ^ b[3][3]]
    if k >= 3:
        y = [Q1[y[0]] ^ b[2][0], Q1[y[1]] ^ b[2][1], Q0[y[2]] ^ b[2][2], Q0[y[3]] ^ b[2][3]]
    y = [Q1[Q0[Q0[y[0]] ^ b[1][0]] ^ b[0][0]],
         Q0[Q0[Q1[y[1]] ^ b[1][1]] ^ b[0][1]],
         Q1[Q1[Q0[y[2]] ^ b[1][2]] ^ b[0][2]],
         Q0[Q1[Q1[y[3]] ^ b[1][3]] ^ b[0][3]]]
    return mds_multiply(y)


class Twofish:
    def __init__(self, key):
        if len(key) not in (16, 24, 32):
            raise ValueError("a Twofish key has 16, 24 or 32 bytes")
        k = len(key) // 8
        m = [int.from_bytes(key[4 * i:4 * i + 4], "little") for i in range(2 * k)]
        even, odd = m[0::2], m[1::2]
        # the S-box key words, in reverse order: the last pair of key words comes first
        self.s = [rs_word(key[8 * i:8 * i + 8]) for i in range(k)][::-1]
        self.k = []
        for i in range(20):
            a = h(2 * i * 0x01010101, even)
            b = rol(h((2 * i + 1) * 0x01010101, odd), 8)
            self.k.append((a + b) & MASK)
            self.k.append(rol((a + 2 * b) & MASK, 9))
        self.key_words = m

    def g(self, x):
        return h(x, self.s)

    def encrypt_block(self, block, trace=None):
        """block: 16 bytes. trace(round, k_a, k_b, t0, t1, f0, f1, state) is called after each round."""
        if len(block) != 16:
            raise ValueError("a block has 16 bytes")
        r = [int.from_bytes(block[4 * i:4 * i + 4], "little") ^ self.k[i] for i in range(4)]
        for rnd in range(16):
            t0 = self.g(r[0])
            t1 = self.g(rol(r[1], 8))
            ka, kb = self.k[8 + 2 * rnd], self.k[9 + 2 * rnd]
            f0 = (t0 + t1 + ka) & MASK
            f1 = (t0 + 2 * t1 + kb) & MASK
            r2 = ror(r[2] ^ f0, 1)
            r3 = rol(r[3], 1) ^ f1
            if trace:
                trace(rnd + 1, ka, kb, t0, t1, f0, f1, (r[0], r[1], r2, r3))
            r = [r2, r3, r[0], r[1]]
        # the last swap is undone by the order of the output words
        out = [r[2] ^ self.k[4], r[3] ^ self.k[5], r[0] ^ self.k[6], r[1] ^ self.k[7]]
        return b"".join(w.to_bytes(4, "little") for w in out)

    def decrypt_block(self, block, trace=None):
        """Same arguments as the trace of encrypt_block. The state passed is the one after the round."""
        if len(block) != 16:
            raise ValueError("a block has 16 bytes")
        w = [int.from_bytes(block[4 * i:4 * i + 4], "little") for i in range(4)]
        r = [w[2] ^ self.k[6], w[3] ^ self.k[7], w[0] ^ self.k[4], w[1] ^ self.k[5]]
        for rnd in range(15, -1, -1):
            # r holds the state after the swap of this round, so undo it first
            r = [r[2], r[3], r[0], r[1]]
            t0 = self.g(r[0])
            t1 = self.g(rol(r[1], 8))
            ka, kb = self.k[8 + 2 * rnd], self.k[9 + 2 * rnd]
            f0 = (t0 + t1 + ka) & MASK
            f1 = (t0 + 2 * t1 + kb) & MASK
            if trace:
                trace(rnd + 1, ka, kb, t0, t1, f0, f1, (r[0], r[1], r[2], r[3]))
            r2 = rol(r[2], 1) ^ f0
            r3 = ror(r[3] ^ f1, 1)
            r = [r[0], r[1], r2, r3]
        out = [r[0] ^ self.k[0], r[1] ^ self.k[1], r[2] ^ self.k[2], r[3] ^ self.k[3]]
        return b"".join(x.to_bytes(4, "little") for x in out)


if __name__ == "__main__":
    # the first test vector of the designers: an all-zero key and an all-zero block
    key = bytes(16)
    plaintext = bytes(16)
    cipher = Twofish(key)
    print("Key:        " + key.hex().upper())
    print("Plaintext:  " + plaintext.hex().upper())
    print("S-box words: " + " ".join("%08X" % w for w in cipher.s))
    print("K0 to K7:   " + " ".join("%08X" % w for w in cipher.k[:8]))

    def show(rnd, ka, kb, t0, t1, f0, f1, state):
        if rnd in (1, 2, 16):
            print("Round %2d: T0=%08X T1=%08X F0=%08X F1=%08X" % (rnd, t0, t1, f0, f1))

    ciphertext = cipher.encrypt_block(plaintext, show)
    print("Ciphertext: " + ciphertext.hex().upper())
    print("Recovered:  " + cipher.decrypt_block(ciphertext).hex().upper())
    # a 256-bit key, the third test of the designers' intermediate values file
    key = bytes.fromhex("0123456789ABCDEFFEDCBA987654321000112233445566778899AABBCCDDEEFF")
    cipher = Twofish(key)
    ciphertext = cipher.encrypt_block(plaintext)
    print("256-bit key " + key.hex().upper())
    print("Ciphertext: " + ciphertext.hex().upper())

Running it produces this output:

Key:        00000000000000000000000000000000
Plaintext:  00000000000000000000000000000000
S-box words: 00000000 00000000
K0 to K7:   52C54DDE 11F0626D 7CAC9D4A 4D1B4AAA B7B83A10 1E7D0BEB EE9C341F CFE14BE4
Round  1: T0=C06D4949 T1=41B9BFC1 F0=FBB70803 F1=E03C04E2
Round  2: T0=7C4536B9 T1=67A58299 F0=F98F3C62 F1=7FBA896C
Round 16: T0=9357B338 T1=AC9926BF F0=32890B15 F1=55F8A728
Ciphertext: 9F589F5CF6122C32B6BFEC2F2AE8C35A
Recovered:  00000000000000000000000000000000
256-bit key 0123456789ABCDEFFEDCBA987654321000112233445566778899AABBCCDDEEFF
Ciphertext: 37527BE0052334B89F0CFCCAE87CFA20

I checked this code against several independent sources before writing it up. I read the designers’ reference C code and its tables, and I did not run it. The permutations q0 and q1 built from the 4-bit tables are identical to the two 256-byte tables of the reference code, and the 4-bit tables are the same as in the Go package. The multiplications by 5B and EF equal the reference macros, and the Reed-Solomon matrix gives the same S-box key words as the reference code on 2,000 random keys.

The code then reproduces the designers’ file of intermediate values for all three key sizes. For each of them, it matches the S-box key words, all 40 subkeys, all 16 rounds with the state, T0, and T1, and the ciphertext, in both directions. It reproduces all 147 vectors of the tables test, all 576 vectors of the variable-key test, and all 384 vectors of the variable-text test, in both directions. It also reproduces the four Monte Carlo tests of the designers, for ECB and CBC, encryption and decryption, with 400 rows for each key size. That is 4,800 rows of 10,000 block operations each, or 48 million block operations. For speed, the Monte Carlo tests use a table-driven form of the same cipher, which gives the same blocks as the code above on 300 random keys and blocks. The code also matches the 6 vectors of the Go package, three of which come from LibTom, and the 723 vectors of Botan, which are 1,107 blocks.

The visualizer’s JavaScript was tested separately. In Node, it matches 812 vectors, in both directions, and it matches every round value of the designers’ intermediate values file. I loaded the built page in a simulated browser and clicked its buttons with the animation delays removed. That test does not show how the page looks in a real browser.

For Fun: The Whole Cipher in 39 Lines

This is the same spirit as the golfed sections elsewhere on this site. It is not for learning the algorithm from. The version below is the same cipher with the whitespace squeezed out and the helper loops folded into one-liners. It is still real Twofish with all three key sizes and both directions, and it needs no imports and no other files. Line 2 holds the eight 4-bit tables, and line 8 holds the two matrices. The h function and the Twofish class follow, and the last lines run the same demo as above.

MASK=0xFFFFFFFF
T_Q0=("817D6F320B59ECA4","ECB81235F4A6709D","BA5E6D90C8F32471","D7F4126E9B3085CA");T_Q1=("28BDF76E31940AC5","1E2B4C376DA5F908","4C75169A0ED82B3F","B951C3DE647F208A")
def ror4(x,n):return((x>>n)|(x<<(4-n)))&15
def make_q(tables):
 t0,t1,t2,t3=([int(c,16) for c in t] for t in tables);return[(lambda a0,b0:(lambda a1,b1:(lambda a2,b2:(lambda a3,b3:16*t3[b3]+t2[a3])(a2^b2,a2^ror4(b2,1)^((8*a2)&15)))(t0[a1],t1[b1]))(a0^b0,a0^ror4(b0,1)^((8*a0)&15)))(x>>4,x&15) for x in range(256)]
Q0=make_q(T_Q0);Q1=make_q(T_Q1)
def gf_mul(a,b,p):return 0 if b==0 else (a if b&1 else 0)^gf_mul((a<<1)^(p if (a<<1)&0x100 else 0),b>>1,p)
MDS_POLY=0x169;RS_POLY=0x14D;MDS=((0x01,0xEF,0x5B,0x5B),(0x5B,0xEF,0xEF,0x01),(0xEF,0x5B,0x01,0xEF),(0xEF,0x01,0xEF,0x5B));RS=((0x01,0xA4,0x55,0x87,0x5A,0x58,0xDB,0x9E),(0xA4,0x56,0x82,0xF3,0x1E,0xC6,0x68,0xE5),(0x02,0xA1,0xFC,0xC1,0x47,0xAE,0x3D,0x19),(0xA4,0x55,0x87,0x5A,0x58,0xDB,0x9E,0x03))
MUL_5B=[gf_mul(x,0x5B,MDS_POLY) for x in range(256)];MUL_EF=[gf_mul(x,0xEF,MDS_POLY) for x in range(256)];_MDS_TABLE={0x01:list(range(256)),0x5B:MUL_5B,0xEF:MUL_EF}
def mds_multiply(y):return sum((_MDS_TABLE[MDS[r][0]][y[0]]^_MDS_TABLE[MDS[r][1]][y[1]]^_MDS_TABLE[MDS[r][2]][y[2]]^_MDS_TABLE[MDS[r][3]][y[3]])<<(8*r) for r in range(4))
def rs_word(k):return sum((gf_mul(RS[r][0],k[0],RS_POLY)^gf_mul(RS[r][1],k[1],RS_POLY)^gf_mul(RS[r][2],k[2],RS_POLY)^gf_mul(RS[r][3],k[3],RS_POLY)^gf_mul(RS[r][4],k[4],RS_POLY)^gf_mul(RS[r][5],k[5],RS_POLY)^gf_mul(RS[r][6],k[6],RS_POLY)^gf_mul(RS[r][7],k[7],RS_POLY))<<(8*r) for r in range(4))
def rol(x,n):n%=32;return((x<<n)|(x>>(32-n)))&MASK if n else x
def ror(x,n):return rol(x,32-(n%32))
def h(x,words):
 y=list(x.to_bytes(4,"little"));k=len(words);b=[[(w>>(8*i))&255 for i in range(4)] for w in words];y=[Q1[y[0]]^b[3][0],Q0[y[1]]^b[3][1],Q0[y[2]]^b[3][2],Q1[y[3]]^b[3][3]] if k==4 else y;y=[Q1[y[0]]^b[2][0],Q1[y[1]]^b[2][1],Q0[y[2]]^b[2][2],Q0[y[3]]^b[2][3]] if k>=3 else y;y=[Q1[Q0[Q0[y[0]]^b[1][0]]^b[0][0]],Q0[Q0[Q1[y[1]]^b[1][1]]^b[0][1]],Q1[Q1[Q0[y[2]]^b[1][2]]^b[0][2]],Q0[Q1[Q1[y[3]]^b[1][3]]^b[0][3]]];return mds_multiply(y)
class Twofish:
 def __init__(self,key):
  if len(key) not in (16,24,32):raise ValueError("a Twofish key has 16, 24 or 32 bytes")
  k=len(key)//8;m=[int.from_bytes(key[4*i:4*i+4],"little") for i in range(2*k)];even,odd=m[0::2],m[1::2];self.s=[rs_word(key[8*i:8*i+8]) for i in range(k)][::-1];self.k=[v for i in range(20) for a,b in [(h(2*i*0x01010101,even),rol(h((2*i+1)*0x01010101,odd),8))] for v in ((a+b)&MASK,rol((a+2*b)&MASK,9))];self.key_words=m
 def g(self,x):return h(x,self.s)
 def encrypt_block(self,block,trace=None):
  if len(block)!=16:raise ValueError("a block has 16 bytes")
  r=[int.from_bytes(block[4*i:4*i+4],"little")^self.k[i] for i in range(4)]
  for rnd in range(16):
   t0=self.g(r[0]);t1=self.g(rol(r[1],8));ka,kb=self.k[8+2*rnd],self.k[9+2*rnd];f0=(t0+t1+ka)&MASK;f1=(t0+2*t1+kb)&MASK;r2=ror(r[2]^f0,1);r3=rol(r[3],1)^f1;trace and trace(rnd+1,ka,kb,t0,t1,f0,f1,(r[0],r[1],r2,r3));r=[r2,r3,r[0],r[1]]
  return b"".join(w.to_bytes(4,"little") for w in [r[2]^self.k[4],r[3]^self.k[5],r[0]^self.k[6],r[1]^self.k[7]])
 def decrypt_block(self,block,trace=None):
  if len(block)!=16:raise ValueError("a block has 16 bytes")
  r=[int.from_bytes(block[8:12],"little")^self.k[6],int.from_bytes(block[12:16],"little")^self.k[7],int.from_bytes(block[0:4],"little")^self.k[4],int.from_bytes(block[4:8],"little")^self.k[5]]
  for rnd in range(15,-1,-1):
   r=[r[2],r[3],r[0],r[1]];t0=self.g(r[0]);t1=self.g(rol(r[1],8));ka,kb=self.k[8+2*rnd],self.k[9+2*rnd];f0=(t0+t1+ka)&MASK;f1=(t0+2*t1+kb)&MASK;trace and trace(rnd+1,ka,kb,t0,t1,f0,f1,(r[0],r[1],r[2],r[3]));r2=rol(r[2],1)^f0;r3=ror(r[3]^f1,1);r=[r[0],r[1],r2,r3]
  return b"".join(x.to_bytes(4,"little") for x in [r[0]^self.k[0],r[1]^self.k[1],r[2]^self.k[2],r[3]^self.k[3]])
if __name__=="__main__":
 key=bytes(16);plaintext=bytes(16);cipher=Twofish(key)
 print("Key:        "+key.hex().upper());print("Plaintext:  "+plaintext.hex().upper());print("S-box words: "+" ".join("%08X"%w for w in cipher.s));print("K0 to K7:   "+" ".join("%08X"%w for w in cipher.k[:8]))
 def show(rnd,ka,kb,t0,t1,f0,f1,state):
  if rnd in (1,2,16):print("Round %2d: T0=%08X T1=%08X F0=%08X F1=%08X"%(rnd,t0,t1,f0,f1))
 ciphertext=cipher.encrypt_block(plaintext,show);print("Ciphertext: "+ciphertext.hex().upper());print("Recovered:  "+cipher.decrypt_block(ciphertext).hex().upper())
 key=bytes.fromhex("0123456789ABCDEFFEDCBA987654321000112233445566778899AABBCCDDEEFF");cipher=Twofish(key);ciphertext=cipher.encrypt_block(plaintext);print("256-bit key "+key.hex().upper());print("Ciphertext: "+ciphertext.hex().upper())

It prints exactly the same output as the readable version:

Key:        00000000000000000000000000000000
Plaintext:  00000000000000000000000000000000
S-box words: 00000000 00000000
K0 to K7:   52C54DDE 11F0626D 7CAC9D4A 4D1B4AAA B7B83A10 1E7D0BEB EE9C341F CFE14BE4
Round  1: T0=C06D4949 T1=41B9BFC1 F0=FBB70803 F1=E03C04E2
Round  2: T0=7C4536B9 T1=67A58299 F0=F98F3C62 F1=7FBA896C
Round 16: T0=9357B338 T1=AC9926BF F0=32890B15 F1=55F8A728
Ciphertext: 9F589F5CF6122C32B6BFEC2F2AE8C35A
Recovered:  00000000000000000000000000000000
256-bit key 0123456789ABCDEFFEDCBA987654321000112233445566778899AABBCCDDEEFF
Ciphertext: 37527BE0052334B89F0CFCCAE87CFA20

It passes every check listed above for the readable code, except the Monte Carlo tests, which I did not run on it. The 4-bit tables and the matrices equal the reference code. It matches the designers’ file of intermediate values for all three key sizes, in both directions. It reproduces all 147, 576, and 384 vectors of the three known-answer tests, the 6 vectors of the Go package, and the 723 vectors of Botan. On 600 random keys, 200 for each key size, it gives the same S-box key words, the same 40 subkeys, and the same value at every traced round as the readable code, in both directions. It is not faster, though. It takes about 89 microseconds per block, against about 86 for the readable version.

Limitations

This is a faithful teaching version of the cipher, not a production one:

• Single 16-byte block only. There is no mode of operation for longer messages and no padding for partial blocks. Encrypting each block on its own, which is ECB, leaks patterns, so real use needs a mode such as CBC or CTR.
• Table lookups depend on secret data. The S-box lookups use secret bytes as indexes, so a real implementation must consider cache-timing leaks that this plain code does not address.
• The key schedule is not optimized. The code is written to follow the definition. It takes about 90 microseconds for one block in pure Python.
• Never use this in production. Use a vetted library. Twofish itself has no known practical attack, but a plain Python version is only for learning.

Security Status

No practical attack has ever broken full 16-round Twofish. Schneier’s page for the cipher says that there is currently no successful cryptanalysis of it. Cryptanalysts found reduced-round attacks (breaking artificially weakened versions with fewer rounds) during the AES competition’s public analysis period. That’s exactly the kind of scrutiny the process was designed to surface, and Twofish held up well enough to remain a finalist throughout.

According to Wikipedia, the best published results are two. In 1999, Niels Ferguson published an impossible differential attack that breaks 6 of the 16 rounds of the 256-bit key version, using 2^256 steps. In 2000, Shiho Moriai and Yiqun Lisa Yin described a truncated differential attack on the full 16 rounds. Their paper claims a probability of 2^-57.3 per block and about 2^51 chosen plaintexts, which is roughly 32 petabytes of data. Schneier answered in 2005 that this paper did not present a full attack, only some hypothesized differential characteristics, and that there had been no extensions to these results since 2000.

The block size is large enough that the birthday bound is not a concern in practice. With 128-bit blocks, two blocks are expected to collide only after about 2^64 blocks under one key, far beyond the 2^32 blocks that make a 64-bit block cipher such as Blowfish vulnerable.

Twofish vs. AES: Why Rijndael Won

NIST’s final decision between the five AES finalists (MARS, RC6, Rijndael, Serpent, and Twofish) came down to a combination of security margin, performance across many different hardware platforms, and implementation simplicity. Rijndael (AES) was chosen primarily for its excellent performance on both high-end and constrained hardware and its comparatively simple, elegant algebraic structure. Twofish was considered highly secure (with some analysts, including Schneier’s own team, arguing it had a larger security margin than Rijndael, a view that was contested and not a consensus). But its more intricate key schedule made it somewhat slower to set up new keys and more complex to implement correctly across diverse platforms.

FAQ

Is Twofish still considered secure?

Yes, it is still considered secure. No practical attack against full-round Twofish exists. It remains a solid choice, though AES’s ubiquity, standardization, and hardware acceleration (AES-NI) make AES the default choice for nearly all new systems.

Why didn’t Twofish win the AES competition?

It wasn’t for lack of security. NIST’s decision weighed performance across many platforms and implementation simplicity alongside pure cryptographic strength, and Rijndael’s simpler structure and better all-around performance profile won out.

What key sizes does Twofish support?

It supports keys of 128, 192, and 256 bits, which are 16, 24, and 32 bytes. All three use 16 rounds. The key size changes the key schedule, where it adds one more layer of permutations in the function h for each extra 64 bits, and it changes the number of S-box key words.

What’s the Pseudo-Hadamard Transform used for?

It’s Twofish’s core diffusion step: mixing the outputs of the g-function each round using only fast addition operations. It spreads each input bit’s influence across both outputs, with minimal computational cost.

How does Twofish compare to Blowfish?

Twofish uses a 128-bit block, which fixes the Sweet32-style weakness of Blowfish’s 64-bit block. It works on four 32-bit words instead of two halves, and its key-dependent S-boxes are built from fixed permutations and a Reed-Solomon code instead of a long key setup of 521 encryptions.

Is Twofish free to use?

Yes, it is free. Schneier’s page says that Twofish is unpatented, and that the source code is uncopyrighted and license-free, so it is free for all uses.

References

1. Schneier, Bruce, Kelsey, John, Whiting, Doug, Wagner, David, Hall, Chris, and Ferguson, Niels. “Twofish: A 128-Bit Block Cipher.” AES submission, 1998. Available at: https://www.schneier.com/academic/twofish/

2. Schneier, Bruce. “Twofish reference implementation in C.” Available at: https://www.schneier.com/wp-content/uploads/2015/12/twofish-reference-c.zip

3. Schneier, Bruce. “Twofish known-answer and Monte Carlo test vectors.” Available at: https://www.schneier.com/wp-content/uploads/2015/12/twofish-kat.zip

4. Schneier, Bruce. “Twofish intermediate values (ecb_ival.txt).” Available at: https://www.schneier.com/wp-content/uploads/2015/12/ecb_ival.txt

5. NIST. “Report on the Development of the Advanced Encryption Standard (AES).” 2001. The official comparison of all five AES finalists.

6. Ferguson, Niels. “Impossible Differentials in Twofish.” Twofish Technical Report 5, 1999.

7. Moriai, Shiho and Yin, Yiqun Lisa. “Cryptanalysis of Twofish (II).” Technical report, Institute of Electronics, Information and Communication Engineers, 2000.

8. Wikipedia. “Twofish.” Available at: https://en.wikipedia.org/wiki/Twofish