The Threefish Algorithm
Threefish is the tweakable block cipher inside the Skein hash function, a SHA-3 finalist. Learn how it builds a strong cipher from just addition, rotation, and XOR on 64-bit words, with no S-boxes at all.
Interactive Threefish Encryption
🔐 Threefish Encryption
The Threefish Algorithm
Introduction
Threefish is a block cipher with an unusual feature: besides the key and the data, it takes a third input, called a tweak. It works on very large blocks of 256, 512, or 1024 bits, and it uses no S-boxes and no lookup tables of any kind. Everything is built from three simple operations on 64-bit words: addition, rotation, and XOR.
The cipher was designed as the engine of the Skein hash function, one of the five finalists in the NIST SHA-3 competition. Looking at Threefish shows two modern ideas at once: a tweakable cipher, and a design style called ARX that is fast on ordinary processors and immune to cache-timing attacks.
Table of Contents
- History
- Tweakable Block Ciphers
- How Threefish Works
- The Mix Function
- The Word Permutation
- Key and Tweak Schedule
- Byte Order
- A Worked Example
- Python Implementation
- Limitations
- Security Status
- FAQ
- References
History
Threefish was published in 2008 by Bruce Schneier, Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker. They designed it as part of Skein, their entry in the NIST hash function competition. Skein was one of five finalists but did not win. NIST chose Keccak, which became SHA-3.
Threefish was never standardized separately, but it remains an interesting cipher on its own terms, because it shows how far a design can go with no S-boxes and a small number of operations. It was built for speed on 64-bit processors, and because it has no table lookups, it avoids the cache-timing side channels that affect many other ciphers.
Tweakable Block Ciphers
A normal block cipher is a function of a key and a block. A tweakable block cipher adds a third input, the tweak. The tweak is not secret, and it can be changed cheaply. Each tweak value, together with the key, selects a different permutation of the block:
ciphertext = E(key, tweak, plaintext)Why is that useful? Imagine encrypting the blocks of a large file. If each block gets its own tweak, such as its position in the file, then identical plaintext blocks encrypt to different ciphertexts, and the key never has to change. Changing a key is expensive in most ciphers because the key schedule has to rerun. Changing a tweak is nearly free.
Skein exploits this directly. It runs Threefish over each block of the message and uses the tweak to record where it is in the message and which part is being processed. That mode of operation is called Unique Block Iteration.
How Threefish Works
Threefish treats a block as a list of 64-bit words: 4 words for 256 bits, 8 words for 512 bits, and 16 words for 1024 bits. The key has the same size as the block, and the tweak is always 128 bits. The cipher runs 72 rounds for the 256-bit and 512-bit versions, and 80 rounds for the 1024-bit version.
Each round does two things:
- Mix. Pair up the words and apply the Mix function to each pair.
- Permute. Shuffle the words into a new order.
Every fourth round, before the Mix step, a subkey is added to the state. A final subkey is added after the last round. For the 256-bit and 512-bit versions that makes 19 subkey additions: 18 before rounds 1, 5, 9, and so on, and one after round 72.
Interactive Visualizer
The visualizer above runs this exact algorithm. Pick a block size, enter any 128-bit tweak, and encrypt. Each row of the log shows all the state words after a round, and the note lists the rotation amounts that round used. Change one hex digit of the tweak and watch the ciphertext change completely.
The Mix Function
The Mix function takes two 64-bit words, x0 and x1, and a rotation amount R:
y0 = x0 + x1 (mod 2^64)
y1 = (x1 <<< R) ^ y0It adds the two words, rotates the second one, and XORs the sum into it. Every step is easy to undo: given y0 and y1, XOR them to recover the rotated word, rotate back, and subtract. The rotation amount R changes from round to round. It cycles through a table of eight rows, one row per round, with a separate row entry for each pair of words.
This is the ARX pattern: Add, Rotate, XOR. None of the three operations is strong on its own, but alternating them mixes bits very well. The carry chain of the addition spreads bits upward, the rotation moves them around, and the XOR combines the results.
The Word Permutation
After the Mix step, the words are shuffled by a fixed permutation. The permutation exists so that the next round’s Mix steps pair up different words. Without it, the same two words would be mixed together again and again, and the rest of the block would never interact with them.
The permutations are fixed tables. In the formulas below, new word i is taken from position p[i] of the Mix output:
256 bits: [0, 3, 2, 1]
512 bits: [2, 1, 4, 7, 6, 5, 0, 3]
1024 bits: [0, 9, 2, 13, 6, 11, 4, 15, 10, 7, 12, 3, 14, 5, 8, 1]Key and Tweak Schedule
Threefish has a very short key schedule. The key words k0 to k(n-1) get one extra word, and the tweak words t0 and t1 get one extra word as well:
k(n) = C240 ^ k0 ^ k1 ^ ... ^ k(n-1) C240 = 0x1BD11BDAA9FC1A22
t2 = t0 ^ t1The constant C240 is fixed. It keeps the extra key word from being zero when the key is zero. It comes from the final Skein 1.3 specification. Earlier versions used 0x5555555555555555 there, and version 1.2 had already revised the rotation constants. This guide follows the final version. Subkey number s is built by rotating through the extended key and adding the tweak and a counter to three of the words:
subkey s, word i = k((s + i) mod (n + 1))
word n-3: also add t(s mod 3)
word n-2: also add t((s + 1) mod 3)
word n-1: also add sSo the tweak enters the cipher at every subkey addition, and the subkey counter s makes each subkey different even when the key and tweak are simple.
Byte Order
Threefish reads its key, tweak, and block as little-endian 64-bit words. The first eight bytes of the key form k0, with the first byte as the least significant. The Python and JavaScript code here follow that convention, and the visualizer shows each word as a number, so the byte order inside the word looks reversed compared with the input string.
A Worked Example
This example uses Threefish-256 with the key 000102...1f, the tweak 000102...0f, and the plaintext 000102...1f. The key words are:
k0 = 0706050403020100
k1 = 0f0e0d0c0b0a0908
k2 = 1716151413121110
k3 = 1f1e1d1c1b1a1918The extra key word is k4 = 1bd11bdaa9fc1a22. The tweak words are t0 = 0706050403020100 and t1 = 0f0e0d0c0b0a0908, and t2 = t0 ^ t1 = 0808080808080808.
Subkey 0. It takes k0, then k1 + t0, then k2 + t1, then k3 + 0:
0706050403020100 161412100e0c0a08 262422201e1c1a18 1f1e1d1c1b1a1918Round 1. The plaintext words are 0706050403020100 0f0e0d0c0b0a0908 1716151413121110 1f1e1d1c1b1a1918. Adding subkey 0 gives 0e0c0a0806040200 25221f1c19161310 3d3a3734312e2b28 3e3c3a3836343230. The Mix step uses rotation amounts 14, 16 on the two pairs and produces 332e29241f1a1510 b4e92f619bde1c58 7b76716c67625d58 414e475855526364. The permutation [0, 3, 2, 1] reorders it into the state after round 1:
332e29241f1a1510 414e475855526364 7b76716c67625d58 b4e92f619bde1c58Later rounds. Round 2 uses the rotation amounts 52, 57. After round 4, just before subkey 1 is added, the state is 91683a3172317cff 24fe06e24f955039 306ade55f5ce4dc7 e7c2deb6db969c8c. After round 72, just before the final subkey, it is 0b35b3ecbc048e86 cc2b6bcfed7b8127 2686a9dd1057ef61 b9b58c353e49bab0.
Result. After the final subkey addition, the four words are 2a53d108d71ea79e ef028cae9a799c49 3c9abbed1e63f969 c8c399414953c3ca, and written as bytes the ciphertext is:
9ea71ed708d1532a499c799aae8c02ef69f9631eedbb9a3ccac353494199c3c8The tweak matters. With the same key and plaintext but an all-zero tweak, the ciphertext is 762b1e65e3e95a13af0f1b963a1d43e692b8dce68a4971101a492a997b0119d5. With the tweak 01000000000000000000000000000000 it is 87d1f8b3401b86fb7b090eb2bd4d3927ce36efed5d376c27f2eb3714050fe34c. A one-bit change in the tweak changes the whole output.
Python Implementation
This is a complete Threefish for all three block sizes: key and tweak schedule, Mix, permutation, encryption, and decryption. The rotation constants were copied by a script from an independent Go implementation.
# threefish.py
#
# Threefish, the tweakable block cipher inside the Skein hash function.
# The block is 256, 512 or 1024 bits (4, 8 or 16 words of 64 bits), the key
# is as long as the block, and a 128-bit tweak is mixed in as well. There are
# no S-boxes. Every round is a Mix step (add, rotate, XOR) on pairs of words,
# followed by a fixed permutation of the words. Every fourth round a subkey
# built from the key and the tweak is added. 72 rounds for 256/512, 80 for 1024.
MASK = (1 << 64) - 1
C240 = 0x1BD11BDAA9FC1A22 # makes the extra key word nonzero for an all-zero key
ROUNDS = {4: 72, 8: 72, 16: 80}
# Rotation amounts: ROTATIONS[words][round % 8][mix index]
ROTATIONS = {
4: [
[14, 16],
[52, 57],
[23, 40],
[5, 37],
[25, 33],
[46, 12],
[58, 22],
[32, 32],
],
8: [
[46, 36, 19, 37],
[33, 27, 14, 42],
[17, 49, 36, 39],
[44, 9, 54, 56],
[39, 30, 34, 24],
[13, 50, 10, 17],
[25, 29, 39, 43],
[8, 35, 56, 22],
],
16: [
[24, 13, 8, 47, 8, 17, 22, 37],
[38, 19, 10, 55, 49, 18, 23, 52],
[33, 4, 51, 13, 34, 41, 59, 17],
[5, 20, 48, 41, 47, 28, 16, 25],
[41, 9, 37, 31, 12, 47, 44, 30],
[16, 34, 56, 51, 4, 53, 42, 41],
[31, 44, 47, 46, 19, 42, 44, 25],
[9, 48, 35, 52, 23, 31, 37, 20],
],
}
# After each round, word i of the new state is word PERMUTATION[words][i] of the Mix output.
PERMUTATION = {
4: [0, 3, 2, 1],
8: [2, 1, 4, 7, 6, 5, 0, 3],
16: [0, 9, 2, 13, 6, 11, 4, 15, 10, 7, 12, 3, 14, 5, 8, 1],
}
def rotl(x, n):
return ((x << n) | (x >> (64 - n))) & MASK
def rotr(x, n):
return rotl(x, 64 - n)
def to_words(data):
return [int.from_bytes(data[i:i + 8], "little") for i in range(0, len(data), 8)]
def to_bytes(words):
return b"".join(w.to_bytes(8, "little") for w in words)
def subkeys(key_words, tweak):
"""Return the subkeys added before round 0, 4, 8, ... and after the last round."""
n = len(key_words)
parity = C240
for w in key_words:
parity ^= w
k = key_words + [parity]
t = [tweak[0], tweak[1], tweak[0] ^ tweak[1]]
out = []
for s in range(ROUNDS[n] // 4 + 1):
sk = [k[(s + i) % (n + 1)] for i in range(n)]
sk[n - 3] = (sk[n - 3] + t[s % 3]) & MASK
sk[n - 2] = (sk[n - 2] + t[(s + 1) % 3]) & MASK
sk[n - 1] = (sk[n - 1] + s) & MASK
out.append(sk)
return out
def mix(x0, x1, rotation):
y0 = (x0 + x1) & MASK
return y0, rotl(x1, rotation) ^ y0
def unmix(y0, y1, rotation):
x1 = rotr(y1 ^ y0, rotation)
return (y0 - x1) & MASK, x1
def encrypt_block(key, tweak_bytes, block):
n = len(block) // 8
sk = subkeys(to_words(key), to_words(tweak_bytes))
v = to_words(block)
for d in range(ROUNDS[n]):
if d % 4 == 0:
v = [(x + k) & MASK for x, k in zip(v, sk[d // 4])]
f = []
for j in range(n // 2):
f.extend(mix(v[2 * j], v[2 * j + 1], ROTATIONS[n][d % 8][j]))
v = [f[PERMUTATION[n][i]] for i in range(n)]
v = [(x + k) & MASK for x, k in zip(v, sk[ROUNDS[n] // 4])]
return to_bytes(v)
def decrypt_block(key, tweak_bytes, block):
n = len(block) // 8
sk = subkeys(to_words(key), to_words(tweak_bytes))
v = [(x - k) & MASK for x, k in zip(to_words(block), sk[ROUNDS[n] // 4])]
for d in reversed(range(ROUNDS[n])):
f = [0] * n
for i in range(n):
f[PERMUTATION[n][i]] = v[i]
v = []
for j in range(n // 2):
v.extend(unmix(f[2 * j], f[2 * j + 1], ROTATIONS[n][d % 8][j]))
if d % 4 == 0:
v = [(x - k) & MASK for x, k in zip(v, sk[d // 4])]
return to_bytes(v)
if __name__ == "__main__":
key = bytes(range(32))
tweak = bytes(range(16))
plaintext = bytes(range(32))
ciphertext = encrypt_block(key, tweak, plaintext)
recovered = decrypt_block(key, tweak, ciphertext)
print(f"Key: {key.hex()}")
print(f"Tweak: {tweak.hex()}")
print(f"Plaintext: {plaintext.hex()}")
print(f"Ciphertext: {ciphertext.hex()}")
print(f"Recovered: {recovered.hex()}")
zero = encrypt_block(bytes(64), bytes(16), bytes(64))
print(f"Threefish-512, all-zero key, tweak and block: {zero.hex()}")Running it produces this output:
Key: 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
Tweak: 000102030405060708090a0b0c0d0e0f
Plaintext: 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
Ciphertext: 9ea71ed708d1532a499c799aae8c02ef69f9631eedbb9a3ccac353494199c3c8
Recovered: 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
Threefish-512, all-zero key, tweak and block: b1a2bbc6ef6025bc40eb3822161f36e375d1bb0aee3186fbd19e47c5d479947b7bc2f8586e35f0cff7e7f03084b0b7b1f1ab3961a580a3e97eb41ea14a6d7bbeThe last line is the well-known Threefish-512 result for an all-zero key, tweak, and block.
I checked this code two ways before writing it up. It reproduces Botan’s Threefish-512 test vectors. And I used it to rebuild the Skein hash on top, the way Skein actually uses Threefish, with a different tweak for every block. That construction reproduced 23 test vectors from an independent Skein implementation. They cover all three block sizes, with messages from zero to 128 bytes. It also matches the Skein digests published on Wikipedia for the empty message and for two short test sentences. A wrong rotation amount, permutation entry, or tweak rule anywhere in the cipher would change every one of those digests.
For Fun: The Same Cipher in 33 Lines
This is the same spirit as the compact bonus sections elsewhere on this site. It is not for learning the algorithm from. This version squeezes the 147-line implementation above into 33 lines. The rotation and permutation tables take one line each, and the key schedule, Mix, and block routines are tightened. It needs no imports and no other files.
MASK=(1<<64)-1;C240=0x1BD11BDAA9FC1A22;ROUNDS={4:72,8:72,16:80}
ROTATIONS={4:[[14,16],[52,57],[23,40],[5,37],[25,33],[46,12],[58,22],[32,32]],8:[[46,36,19,37],[33,27,14,42],[17,49,36,39],[44,9,54,56],[39,30,34,24],[13,50,10,17],[25,29,39,43],[8,35,56,22]],16:[[24,13,8,47,8,17,22,37],[38,19,10,55,49,18,23,52],[33,4,51,13,34,41,59,17],[5,20,48,41,47,28,16,25],[41,9,37,31,12,47,44,30],[16,34,56,51,4,53,42,41],[31,44,47,46,19,42,44,25],[9,48,35,52,23,31,37,20]]}
PERMUTATION={4:[0,3,2,1],8:[2,1,4,7,6,5,0,3],16:[0,9,2,13,6,11,4,15,10,7,12,3,14,5,8,1]}
rotl=lambda x,n: ((x<<n)|(x>>(64-n)))&MASK; rotr=lambda x,n: rotl(x,64-n)
to_words=lambda d: [int.from_bytes(d[i:i+8],"little") for i in range(0,len(d),8)]
to_bytes=lambda ws: b"".join(w.to_bytes(8,"little") for w in ws)
def subkeys(kw,tw):
n=len(kw); p=C240
for w in kw: p^=w
k=kw+[p]; t=[tw[0],tw[1],tw[0]^tw[1]]; out=[]
for s in range(ROUNDS[n]//4+1):
sk=[k[(s+i)%(n+1)] for i in range(n)]; sk[n-3]=(sk[n-3]+t[s%3])&MASK; sk[n-2]=(sk[n-2]+t[(s+1)%3])&MASK; sk[n-1]=(sk[n-1]+s)&MASK; out.append(sk)
return out
def mix(x0,x1,r): y0=(x0+x1)&MASK; return y0,rotl(x1,r)^y0
def unmix(y0,y1,r): x1=rotr(y1^y0,r); return (y0-x1)&MASK,x1
def encrypt_block(key,tweak_bytes,block):
n=len(block)//8; sk=subkeys(to_words(key),to_words(tweak_bytes)); v=to_words(block)
for d in range(ROUNDS[n]):
if d%4==0: v=[(x+k)&MASK for x,k in zip(v,sk[d//4])]
f=[]
for j in range(n//2): f.extend(mix(v[2*j],v[2*j+1],ROTATIONS[n][d%8][j]))
v=[f[PERMUTATION[n][i]] for i in range(n)]
v=[(x+k)&MASK for x,k in zip(v,sk[ROUNDS[n]//4])]
return to_bytes(v)
def decrypt_block(key,tweak_bytes,block):
n=len(block)//8; sk=subkeys(to_words(key),to_words(tweak_bytes)); v=[(x-k)&MASK for x,k in zip(to_words(block),sk[ROUNDS[n]//4])]
for d in range(ROUNDS[n]-1,-1,-1):
f=[0]*n
for i in range(n): f[PERMUTATION[n][i]]=v[i]
v=[]
for j in range(n//2): v.extend(unmix(f[2*j],f[2*j+1],ROTATIONS[n][d%8][j]))
if d%4==0: v=[(x-k)&MASK for x,k in zip(v,sk[d//4])]
return to_bytes(v)
key=bytes(range(32)); tweak=bytes(range(16)); pt=bytes(range(32)); ct=encrypt_block(key,tweak,pt); rec=decrypt_block(key,tweak,ct); print(f"Key: {key.hex()}"); print(f"Tweak: {tweak.hex()}"); print(f"Plaintext: {pt.hex()}"); print(f"Ciphertext: {ct.hex()}"); print(f"Recovered: {rec.hex()}"); zero=encrypt_block(bytes(64),bytes(16),bytes(64)); print(f"Threefish-512, all-zero key, tweak and block: {zero.hex()}")Running it prints the same six lines as the readable version, including the all-zero Threefish-512 result:
Key: 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
Tweak: 000102030405060708090a0b0c0d0e0f
Plaintext: 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
Ciphertext: 9ea71ed708d1532a499c799aae8c02ef69f9631eedbb9a3ccac353494199c3c8
Recovered: 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
Threefish-512, all-zero key, tweak and block: b1a2bbc6ef6025bc40eb3822161f36e375d1bb0aee3186fbd19e47c5d479947b7bc2f8586e35f0cff7e7f03084b0b7b1f1ab3961a580a3e97eb41ea14a6d7bbeI checked it against the readable code on 300 random keys, tweaks, and blocks, 100 for each of the three block sizes. Encryption matched every time, and decryption recovered every block. The rotation, permutation, and round tables are identical, and it reproduces the Threefish-256 example and the all-zero Threefish-512 value.
Limitations
This is a faithful teaching version of the cipher, not a production one:
- Single block only. The code encrypts one block at a time. Real use needs a mode of operation, and Skein’s own mode is a hash construction.
- Python integers are not constant-time. The cipher itself has no table lookups, but this code does not claim to be free of timing differences.
- The tweak is public. Never put secrets in the tweak, because it is not encrypted.
- Little deployment outside Skein. Threefish is used mainly inside Skein, so interoperability beyond Skein is limited.
Security Status
No attack on the full cipher is known. Published cryptanalysis covers reduced-round versions. In 2010, researchers combined rotational cryptanalysis with rebound attacks and found known-key distinguishers against 53 of the 72 rounds of Threefish-256 and 57 of the 72 rounds of Threefish-512. Those results show some structure in reduced-round versions but do not endanger the full cipher.
Skein’s security rests on Threefish, and Skein reached the final round of the SHA-3 competition without a practical break. The design’s conservative choice of many rounds, 72 for two of the three sizes, was a deliberate security margin.
FAQ
What is a tweak?
It is a public, adjustable input to the cipher, in addition to the key. Each different tweak makes the cipher behave like a different, independent permutation. Tweaks let you vary the cipher cheaply, for example per block or per message.
Why does Threefish have no S-boxes?
The designers wanted a cipher that is fast on 64-bit processors and free of table lookups. Table lookups can leak information through cache timing. Addition, rotation, and XOR run in constant time on common processors.
What does ARX mean?
It stands for Add, Rotate, XOR, the three operations that make up the cipher. Other well-known ARX designs include ChaCha20 and Speck. Each operation is weak alone, but together they mix bits thoroughly.
How is Threefish related to Skein?
Threefish is the compression engine of Skein. Skein runs Threefish over each block of a message, using the tweak to track its position, and XORs the result with the input block to form the next chaining value.
Is Threefish secure?
As far as anyone has published, yes for the full cipher. Attacks reach only reduced-round versions. Its large blocks and many rounds give a wide margin.
References
-
Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., and Walker, J. “The Skein Hash Function Family.” Submission to the NIST SHA-3 competition, version 1.3, 2010. Available at: https://www.schneier.com/academic/skein/
-
Khovratovich, D. and Nikolic, I. “Rotational Cryptanalysis of ARX.” Fast Software Encryption (FSE) 2010.
-
Khovratovich, D., Nikolic, I., and Rechberger, C. “Rotational Rebound Attacks on Reduced Skein.” ASIACRYPT 2010.
-
Wikipedia. “Threefish.” Available at: https://en.wikipedia.org/wiki/Threefish
-
Wikipedia. “Skein (hash function).” Available at: https://en.wikipedia.org/wiki/Skein_(hash_function)