The Skein Algorithm

The Skein Algorithm

Introduction

Skein is a hash function designed by Bruce Schneier, Niels Ferguson, and a team of colleagues. It was one of the five finalists of the NIST SHA-3 competition. In 2012, NIST chose Keccak as the winner, but Skein stays interesting because it takes a very different path.

Most hash functions are built from a custom compression function. Skein is built from a block cipher. The cipher is Threefish, which has no S-boxes, only additions, rotations, and XORs. Skein chains the cipher with a mode called Unique Block Iteration, or UBI. A small value called the tweak tells the cipher where it is in the input, so that every block is processed in a different way. This one design handles the message, the configuration, and an output of any length. The FAQ explains how Skein and Threefish differ.

Table of Contents

• History and Standards
• Threefish in Brief
• The Tweak
• Unique Block Iteration
• The Whole Hash
• Variants and Options
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

The Skein team was led by Bruce Schneier and Niels Ferguson. It also included Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker. They submitted Skein to the SHA-3 competition in 2008. The reference implementation by Doug Whiting was released into the public domain.

In December 2010, NIST named five finalists: BLAKE, Grøstl, JH, Keccak, and Skein. Keccak won in October 2012 and became SHA-3. During the competition, the designers changed one constant in the Threefish key schedule, which gave version 1.3 of the algorithm. They say that this makes rotational distinguisher attacks much less efficient. This is the version in this guide, and the one that the test vectors used here come from. The authors claim a speed of 6.1 cycles per byte on a 64-bit Intel Core 2 Duo, which was fast for the time.

Threefish in Brief

Threefish is a tweakable block cipher. It encrypts a block under a key and a 128-bit tweak. The block and the key have the same size, which is 256, 512, or 1024 bits, and they are split into 4, 8, or 16 words of 64 bits. The cipher runs 72 rounds for the two smaller sizes and 80 rounds for the largest.

Each round has two parts. The Mix step takes words in pairs. For a pair (x0, x1) and a rotation constant r, it computes:

y0 = x0 + x1
y1 = rotl(x1, r) xor y0

A fixed permutation then moves the words around, so that the next Mix step pairs different words. Every four rounds, a subkey is added to all words. The subkeys come from the key words, from the tweak, and from a counter, so each subkey is different. After the last round, a final subkey is added. The Threefish guide explains the cipher in detail. Skein uses it in one direction only, as an encryption function.

The Tweak

The 128-bit tweak is what makes Skein work. It holds the following fields:

Field	Bits	Meaning
Position	0 to 95	The number of bytes processed so far, including the current block
Reserved	96 to 111	Reserved for future use, and always zero
Tree level	112 to 118	The level in a hash tree, which is zero for plain hashing
BitPad	119	Set when the last byte of an input is only partly used, because the input is not a whole number of bytes
Type	120 to 125	What the data is: 4 for the configuration, 48 for the message, 63 for the output
First	126	1 for the first block of the data
Final	127	1 for the last block of the data

Plain hashing of whole bytes leaves the reserved bits, the tree level, and BitPad at zero. With these fields, no two blocks in a Skein computation are ever processed under the same tweak. The same block of data at a different position, or with a different type, goes through a different cipher. This is the “unique” in Unique Block Iteration.

Unique Block Iteration

UBI turns the tweakable cipher into a hash of any length. It is close to the old Matyas-Meyer-Oseas mode. The message is cut into blocks of the state size, and the last block is padded with zeros. If the message is empty, it still gets one block of zeros. Each block then updates the chaining value like this:

chain = Threefish( key = chain, tweak = tweak_for_this_block, plaintext = block )  xor  block

So the chaining value is the key of the cipher, and the message block is the plaintext. The cipher output is XORed with the message block. This is the feed-forward, and it makes the step one-way. Without it, anyone could run the cipher backwards.

The Whole Hash

Skein runs UBI three times, in these stages:

1. Configuration. UBI with an all-zero chaining value hashes a configuration string, with type 4. The string is always 32 bytes, so it is a single block, and that block carries both the first and the final flag. The string holds the name SHA3, the version number 1, and the requested output length in bits. The result, G0, is the starting value for everything else. Because the length is part of it, a 256-bit digest is not a prefix of a 512-bit digest.
2. Message. UBI with G0 as the chaining value hashes the message, with type 48. The result is G1.
3. Output. UBI with G1 hashes the counter 0, as an 8-byte little-endian number, with type 63. Each counter gives one block as large as the state. For longer outputs, it hashes the counters 1, 2, and so on, and joins the blocks. The digest is simply the first bytes of the joined result.

This last stage works like a counter mode. It makes Skein an extendable hash function, whose output can be longer than the state.

Variants and Options

The name of a variant has two numbers. Skein-512-256 has a 512-bit internal state and a 256-bit output. The designers call Skein-512 their primary proposal. Skein-256 is smaller, and Skein-1024 is larger, with a wider security margin and 80 rounds.

Besides plain hashing, Skein supports a number of optional features through other types of UBI input. They include a key for MACs, a personalization string, a nonce, tree hashing for parallel hardware, a stream cipher, and key derivation. This guide covers the plain hash, which uses only the three types above.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose a variant, type a message of up to 127 bytes, and click Hash. The log shows every block of the configuration, the message, and the output. For each block, it lists the input, every subkey addition, the state after each group of four rounds, and the feed-forward that gives the next chaining value. Each row is the state as 4, 8, or 16 words of 64 bits. When it ends, the page tells you how many of the digest bits change when one bit of your message is flipped.

A Worked Example

This follows the message abc with Skein-512-512.

The configuration. The 32-byte string is 5348413301000000000200000000000000000000000000000000000000000000. Its first eight bytes are 5348413301000000, which is SHA3, the version 1, and two zero bytes. The next eight bytes are 0002000000000000, which is 512 in little-endian. The rest is zero. The tweak has position 32, type 4, and both the first and final flags. As two words it is 0000000000000020 and c400000000000000.

The first block. The key is 64 zero bytes. The cipher adds a parity word, 1bd11bdaa9fc1a22, which is the constant C240 XORed with the key words, so the key has nine words. Subkey 0 is 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000020 c400000000000000 0000000000000000. Only the two words that hold the tweak are not zero. Adding it to the configuration gives 0000000133414853 0000000000000200 0000000000000000 0000000000000000 0000000000000000 0000000000000020 c400000000000000 0000000000000000.

The first Mix step takes the first two words, 0000000133414853 and 0000000000000200, with the rotation 46. The sum is y0 = 0000000133414a53. Rotating the second word gives 0080000000000000, and XORing it with y0 gives y1 = 0080000133414a53. The 72 rounds repeat this for every pair of words, with a new subkey after every four rounds. At the end, XORing the cipher output with the configuration gives:

G0 = 4903adff749c51ce 0d95de399746df03 8fd1934127c79bce 9a255629ff352cb1 5db62599df6ca7b0 eabe394ca9d5c3f4 991112c71a75b523 ae18a40b660fcc33

This is the precomputed starting value for Skein-512-512. The Skein specification lists it in Appendix B, as the output of the configuration step, and the eight words match.

The message. The block is abc followed by 61 zero bytes. The tweak has position 3, type 48, and the first and final flags, so it is 0000000000000003 and f000000000000000. The chaining value G0 is the key, and the cipher produces this output:

b2fd505fb5d455d4 c4316c6844358122 f7f000a7a46cc8e4 0f8efa51c0e46716 31351c742452d1a9 bc467fcdfc32cdfc 789b9d1cac148ab8 d46dbb377d95c084

XORing with the block changes only the first word, and the new chaining value is:

G1 = b2fd505fb5b737b5 c4316c6844358122 f7f000a7a46cc8e4 0f8efa51c0e46716 31351c742452d1a9 bc467fcdfc32cdfc 789b9d1cac148ab8 d46dbb377d95c084

The output. The input is the counter 0, as 8 bytes, padded with zeros, with position 8, type 63, and both flags, so the tweak is 0000000000000008 and ff00000000000000. One block is enough for 512 bits, so the digest is:

8f5dd9ec798152668e35129496b029a960c9a9b88662f7f9482f110b31f9f938
93ecfb25c009baad9e46737197d5630379816a886aa05526d3a70df272d96e75

With Skein-512-256, the same message gives 0977b339c3c85927071805584d5460d8f20da8389bbe97c59b1cfac291fe9527, which is not a prefix of the 512-bit digest. The empty message gives c8877087da56e072870daa843f176e9453115929094c3a40c463a196c29bf7ba with Skein-256-256 and bc5b4c50925519c290cc634277ae3d6257212395cba733bbad37a4af0fa06af41fca7903d06564fea7a2d3730dbdb80c1f85562dfcc070334ea4d1d9e72cba7a with Skein-512-512. Flipping one bit of abc changes 257 of the 512 digest bits.

Python Implementation

This is a complete Skein, in two files. The first is the Threefish cipher, which is the one from the Threefish guide. The second is Skein itself, which is short because UBI is a small loop.

# 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()}")

# skein.py
#
# Skein (version 1.3), the hash function by Bruce Schneier, Niels Ferguson and
# their team, a finalist of the NIST SHA-3 competition. It is built on the
# Threefish block cipher from threefish.py. Skein chains the cipher with
# Unique Block Iteration (UBI): the chaining value is the key, the message
# block is the plaintext, and a 128-bit tweak tells the cipher where it is.

import threefish

# the type field of the tweak
TYPE_CONFIG, TYPE_MESSAGE, TYPE_OUTPUT = 4, 48, 63


def tweak_bytes(position, block_type, first, final):
    """The 128-bit tweak: a byte counter, the type of the data, and flags for the first and last block."""
    high = (block_type << 56) | (int(first) << 62) | (int(final) << 63)
    return position.to_bytes(8, "little") + high.to_bytes(8, "little")


def ubi(chain, message, block_type):
    """Hash a message of any length into a chaining value of the same size as the chain."""
    size = len(chain)
    blocks = max(1, -(-len(message) // size))
    padded = message + bytes(blocks * size - len(message))
    for i in range(blocks):
        block = padded[i * size:(i + 1) * size]
        position = min(len(message), (i + 1) * size)
        tweak = tweak_bytes(position, block_type, i == 0, i == blocks - 1)
        encrypted = threefish.encrypt_block(chain, tweak, block)
        chain = bytes(a ^ b for a, b in zip(encrypted, block))
    return chain


def config_string(output_bits):
    """The 32-byte configuration: the name SHA3, version 1, the output length, and zeros."""
    return b"SHA3" + (1).to_bytes(2, "little") + bytes(2) + output_bits.to_bytes(8, "little") + bytes(16)


def skein(message, state_bits=512, output_bits=None):
    """Skein-<state_bits>-<output_bits>. The state is 256, 512 or 1024 bits, and the output can have any whole number of bytes."""
    output_bits = output_bits or state_bits
    chain = ubi(bytes(state_bits // 8), config_string(output_bits), TYPE_CONFIG)
    chain = ubi(chain, message, TYPE_MESSAGE)
    out = b""
    counter = 0
    while 8 * len(out) < output_bits:
        out += ubi(chain, counter.to_bytes(8, "little"), TYPE_OUTPUT)
        counter += 1
    return out[:output_bits // 8]


if __name__ == "__main__":
    for text in (b"", b"abc", b"The quick brown fox jumps over the lazy dog"):
        print("Skein-512-256(%r) = %s" % (text.decode(), skein(text, 512, 256).hex()))
    print("Skein-512-512('') = " + skein(b"").hex())

Running the second file produces this output:

Skein-512-256('') = 39ccc4554a8b31853b9de7a1fe638a24cce6b35a55f2431009e18780335d2621
Skein-512-256('abc') = 0977b339c3c85927071805584d5460d8f20da8389bbe97c59b1cfac291fe9527
Skein-512-256('The quick brown fox jumps over the lazy dog') = b3250457e05d3060b1a4bbc1428bc75a3f525ca389aeab96cfa34638d96e492a
Skein-512-512('') = bc5b4c50925519c290cc634277ae3d6257212395cba733bbad37a4af0fa06af41fca7903d06564fea7a2d3730dbdb80c1f85562dfcc070334ea4d1d9e72cba7a

I checked this code against several independent sources before writing it up. It reproduces the published digests for all three state sizes in the test vectors published with the Go package for Skein. It also reproduces 1,036 vectors from Botan for Skein-512 with output sizes of 224, 256, 384, and 512 bits, for messages of many different lengths. The empty-message digests and the quick brown fox digests quoted on Wikipedia match too.

Security Status

No attack on the full Skein is known. The designers argue that its security rests on Threefish, and the competition gave it a lot of public analysis. The best published results cover only some of the rounds.

In 2010, Khovratovich and Nikolic used rotational cryptanalysis to attack 39 of the 72 rounds of Threefish-256 and 42 of the 72 rounds of Threefish-512. Later that year, Khovratovich, Nikolic, and Rechberger combined rotational cryptanalysis with a rebound attack. They found rotational collisions for about 53 of the 72 rounds of the Skein-256 compression function and 57 of the 72 rounds of the Skein-512 compression function. The same holds for the Threefish cipher. The authors state that these results do not threaten the full-round hash.

Version 1.3 changed the Threefish key schedule constant from 0x5555555555555555 to 0x1BD11BDAA9FC1A22. The designers wrote that this does not change the speed in a measurable way, but it greatly lowers the efficiency of rotational distinguisher attacks. They also wrote that they were not convinced such distinguishers had real-world consequences, and that the fix was so simple that it seemed prudent. The tweak note and the rebound paper are both dated 25 October 2010, so this guide does not claim that one caused the other.

A 512-bit digest gives 256 bits of collision resistance, and a 256-bit digest gives 128 bits. The UBI design is meant to resist length extension, because the tweak marks the last block of every input and the output is a separate stage. Skein is not a NIST standard, and it is rarely seen in new protocols. It remains a respected design with a large margin, and a good one to study.

FAQ

What is the difference between Skein and Threefish?

Threefish is the block cipher, and Skein is the hash function built on it. Skein uses Threefish to hash each block, with a different tweak every time. Threefish can also be used alone for encryption.

Why does the output length change the whole digest?

The output length is part of the configuration string, which is the first thing that Skein hashes. So Skein-512-256 and Skein-512-512 start from different values of G0, and their digests are unrelated. This also means a shorter digest is never just the start of a longer one.

Why is Skein not SHA-3?

NIST picked Keccak in 2012. NIST’s final report praised Keccak for a design that differs from SHA-2, a large security margin, and good efficiency in hardware. Skein was among the five finalists and was not broken.

Can Skein make longer outputs than its state?

Yes, because the output stage hashes the counters 0, 1, 2, and so on, and joins the blocks. So Skein-512 can produce 1024 bits or more, for example for key derivation.

Can I use Skein as a MAC or a stream cipher?

The design includes both, through a key input and a stream cipher mode. They use other UBI types. Standard libraries rarely support them, so HMAC is the usual choice for a MAC.

References

1. Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., and Walker, J. “The Skein Hash Function Family.” Version 1.3, 2010. Available at: https://www.schneier.com/academic/skein/

2. Khovratovich, D., Nikolic, I., and Rechberger, C. “Rotational Rebound Attacks on Reduced Skein.” ASIACRYPT 2010, Lecture Notes in Computer Science 6477, Springer. Available at: https://eprint.iacr.org/2010/538

3. Khovratovich, D. and Nikolic, I. “Rotational Cryptanalysis of ARX.” Fast Software Encryption (FSE) 2010, Springer.

4. Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., and Walker, J. “The Skein Hash Function Family: NIST Round 3 Tweak Description.” 25 October 2010. Available at: https://www.schneier.com/wp-content/uploads/2010/12/skein-1.3-modifications.pdf

5. NIST. “Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition.” NISTIR 7896, 2012.

6. Auernhammer, A. “Skein for Go, test vectors.” Available at: https://github.com/aead/skein

7. Wikipedia. “Skein (hash function).” Available at: https://en.wikipedia.org/wiki/Skein_(hash_function)