The Serpent Algorithm

The Serpent Algorithm

Introduction

Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen and published in 1998 as an entry in the Advanced Encryption Standard competition. It made the final five and finished second to Rijndael, which became AES. Serpent is the cipher people point to when they want the safest finalist rather than the fastest one. Its designers judged that 16 rounds would resist every attack known at the time. They specified 32 anyway, as insurance against attacks nobody had found yet.

Table of Contents

• History: The AES Competition
• Design Philosophy: A Large Safety Margin
• How Serpent Works
• S-Boxes and Bitslicing
• The Linear Transformation
• Key Schedule
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History: The AES Competition

By the mid 1990s, DES was too weak and 3DES was too slow. In 1997 NIST asked the world’s cryptographers to propose a replacement, and fifteen designs entered. Five reached the final round: MARS, RC6, Rijndael, Serpent, and Twofish.

NIST judged them on security, speed, and flexibility. All five were considered secure. Rijndael won mainly because it was far more efficient in software and on small devices. Serpent had the fewest negative votes among the finalists, but its 32 rounds made it noticeably slower. The Serpent algorithm is in the public domain and has never been patented.

Design Philosophy: A Large Safety Margin

Most ciphers pick a round count close to the edge of what known attacks can break. Serpent did the opposite. The designers estimated that 16 rounds would already stop every known attack, then doubled the count to 32.

That choice shaped everything else. Serpent uses simple, heavily analyzed components: small S-boxes, a plain linear mixing layer, and a key schedule that is easy to describe. Simple parts are easier to study, and the designers wanted the cipher to survive close scrutiny for decades.

How Serpent Works

Serpent encrypts a 128-bit block with a 128, 192, or 256-bit key. The block is held as four 32-bit words, X0 to X3. Each of the first 31 rounds does three things:

1. Key mixing. XOR the four words with that round’s 128-bit subkey.
2. S-box layer. Substitute every 4-bit column using one of eight S-boxes.
3. Linear transformation. Mix bits across the four words so each S-box output spreads widely.

The last round replaces the linear transformation with a second key mixing. The cipher therefore uses 33 subkeys in total, and decryption simply runs every step backward with the inverse S-boxes and the inverse linear transformation.

Interactive Visualizer

The visualizer above runs this exact algorithm. Pick a key size, then watch the four words change round by round. The log below the words keeps every round, so you can see how quickly the output stops resembling the input.

S-Boxes and Bitslicing

Serpent has eight different S-boxes, each mapping 4 bits to 4 bits. They are used in a repeating pattern: round 0 uses S0, round 1 uses S1, and so on up to S7, then the pattern restarts. Over 32 rounds each S-box is used exactly four times.

The S-boxes were built from the 32 rows of the DES S-boxes. Each row is already a permutation of the numbers 0 to 15, and the designers chose and transformed rows to get good differential and linear properties. Using DES as the source also answered a worry of the time. Nobody could claim the designers had hidden a weakness in numbers they invented.

Here is the clever part. Serpent applies each S-box to all 32 bit columns at once. Take bit 0 of X0, X1, X2, and X3 and read them as a 4-bit number. Look that number up in the S-box and write the four result bits back. Then repeat for bit 1, bit 2, and so on up to bit 31.

This is called bitslicing. On a real processor, the 32 lookups become a short run of logic instructions, with no table and no memory access. That makes fast Serpent code naturally resistant to cache-timing attacks. The original specification also defines an initial and final permutation for a “standard” form of the cipher. Those only convert to and from the bitslice layout and cancel each other out, so bitslice code, including the code below, skips them.

The Linear Transformation

After the S-boxes, the linear transformation spreads each change. It uses only rotations, shifts, and XORs on the four words:

X0 = X0 <<< 13
X2 = X2 <<< 3
X1 = X1 ^ X0 ^ X2
X3 = X3 ^ X2 ^ (X0 << 3)
X1 = X1 <<< 1
X3 = X3 <<< 7
X0 = X0 ^ X1 ^ X3
X2 = X2 ^ X3 ^ (X1 << 7)
X0 = X0 <<< 5
X2 = X2 <<< 22

Here <<< is a rotate left and << is a plain shift. Every step can be undone, which is why decryption can reverse it exactly. The rotation amounts were chosen so that a change in one bit reaches many S-boxes in the next round, which is what makes the cipher resist differential and linear attacks.

Key Schedule

Serpent first pads the key to 256 bits. A shorter key gets a single 1 bit appended and then zeros up to the full length. The 256-bit result is read as eight little-endian words.

Those eight words are expanded into 132 more “prekey” words with this recurrence, where φ = 0x9E3779B9 is derived from the golden ratio:

w[i] = (w[i-8] ^ w[i-5] ^ w[i-3] ^ w[i-1] ^ φ ^ i) <<< 11

The 132 prekeys are grouped into 33 sets of four. Each set is then passed through an S-box, which makes the subkeys depend on the key in a nonlinear way. Subkey i uses S-box number (3 - i) mod 8, so the schedule runs through the S-boxes backward, starting with S3.

A Worked Example

The test below uses the 128-bit key 000102030405060708090a0b0c0d0e0f and the same bytes as the plaintext. The bytes are read as little-endian words, so the plaintext becomes:

X0 X1 X2 X3 = 03020100 07060504 0b0a0908 0f0e0d0c

Round 1. The first subkey is K0 = d9acacc1 f4b57314 3225025c 103119d9. XOR with the state gives daaeadc1 f3b37610 392f0b54 1f3f14d5. S-box S0 then replaces every bit column, giving e1c162bf 06404d2e 34325b85 1523c091. The linear transformation turns that into 84734587 170ada7f f088e057 077ebc6b, which is the state after round 1.

Round 32. The last round skips the linear transformation and XORs in the final subkey K32 = 2ef68e15 81bf779d 09579117 f8cb72e1. The result, written as little-endian bytes, is the ciphertext:

4c7d8a328072a22c823e4a1f3acda16d

With a 256-bit key made of the bytes 00 to 1f, the same plaintext encrypts to de269ff833e432b85b2e88d2701ce75c. Both results appear in the Linux kernel’s published Serpent test vectors.

Python Implementation

This is a complete Serpent: the real key schedule, the real S-boxes, and the real linear transformation for all three key sizes. It works in bitslice form, so there are no initial or final permutations.

# serpent.py
#
# Serpent in its bitslice form: a 128-bit block is four 32-bit words, and
# every S-box is applied to 32 four-bit columns in parallel. 32 rounds,
# 128/192/256-bit keys. Words are little-endian, as in the AES submission.

MASK = 0xFFFFFFFF
PHI = 0x9E3779B9

SBOX = [
    [3, 8, 15, 1, 10, 6, 5, 11, 14, 13, 4, 2, 7, 0, 9, 12],
    [15, 12, 2, 7, 9, 0, 5, 10, 1, 11, 14, 8, 6, 13, 3, 4],
    [8, 6, 7, 9, 3, 12, 10, 15, 13, 1, 14, 4, 0, 11, 5, 2],
    [0, 15, 11, 8, 12, 9, 6, 3, 13, 1, 2, 4, 10, 7, 5, 14],
    [1, 15, 8, 3, 12, 0, 11, 6, 2, 5, 4, 10, 9, 14, 7, 13],
    [15, 5, 2, 11, 4, 10, 9, 12, 0, 3, 14, 8, 13, 6, 7, 1],
    [7, 2, 12, 5, 8, 4, 6, 11, 14, 9, 1, 15, 13, 3, 10, 0],
    [1, 13, 15, 0, 14, 8, 2, 11, 7, 4, 12, 10, 9, 3, 5, 6],
]
SBOX_INV = [[box.index(v) for v in range(16)] for box in SBOX]


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


def ror(x, n):
    return ((x >> n) | (x << (32 - n))) & MASK


def sbox_layer(box, words):
    """Apply a 4-bit S-box to all 32 bit columns of four words at once."""
    out = [0, 0, 0, 0]
    for bit in range(32):
        v = sum(((words[j] >> bit) & 1) << j for j in range(4))
        s = box[v]
        for j in range(4):
            out[j] |= ((s >> j) & 1) << bit
    return out


def linear(x):
    x0, x1, x2, x3 = x
    x0 = rol(x0, 13)
    x2 = rol(x2, 3)
    x1 ^= x0 ^ x2
    x3 ^= x2 ^ ((x0 << 3) & MASK)
    x1 = rol(x1, 1)
    x3 = rol(x3, 7)
    x0 ^= x1 ^ x3
    x2 ^= x3 ^ ((x1 << 7) & MASK)
    x0 = rol(x0, 5)
    x2 = rol(x2, 22)
    return [x0, x1, x2, x3]


def linear_inv(x):
    x0, x1, x2, x3 = x
    x2 = ror(x2, 22)
    x0 = ror(x0, 5)
    x2 ^= x3 ^ ((x1 << 7) & MASK)
    x0 ^= x1 ^ x3
    x3 = ror(x3, 7)
    x1 = ror(x1, 1)
    x3 ^= x2 ^ ((x0 << 3) & MASK)
    x1 ^= x0 ^ x2
    x2 = ror(x2, 3)
    x0 = ror(x0, 13)
    return [x0, x1, x2, x3]


def key_schedule(key):
    """Expand a 16, 24 or 32 byte key into 33 round keys of four words."""
    if len(key) not in (16, 24, 32):
        raise ValueError("Serpent keys are 16, 24 or 32 bytes")
    padded = key + b"\x01" + b"\x00" * (31 - len(key)) if len(key) < 32 else key
    w = [int.from_bytes(padded[4 * i:4 * i + 4], "little") for i in range(8)]
    for i in range(132):
        w.append(rol(w[i] ^ w[i + 3] ^ w[i + 5] ^ w[i + 7] ^ PHI ^ i, 11))
    prekeys = w[8:]
    round_keys = []
    for r in range(33):
        box = SBOX[(3 - r) % 8]
        round_keys.append(sbox_layer(box, prekeys[4 * r:4 * r + 4]))
    return round_keys


def encrypt_block(key, block):
    rk = key_schedule(key)
    x = [int.from_bytes(block[4 * i:4 * i + 4], "little") for i in range(4)]
    for r in range(32):
        x = [a ^ b for a, b in zip(x, rk[r])]
        x = sbox_layer(SBOX[r % 8], x)
        if r < 31:
            x = linear(x)
    x = [a ^ b for a, b in zip(x, rk[32])]
    return b"".join(v.to_bytes(4, "little") for v in x)


def decrypt_block(key, block):
    rk = key_schedule(key)
    x = [int.from_bytes(block[4 * i:4 * i + 4], "little") for i in range(4)]
    x = [a ^ b for a, b in zip(x, rk[32])]
    for r in range(31, -1, -1):
        if r < 31:
            x = linear_inv(x)
        x = sbox_layer(SBOX_INV[r % 8], x)
        x = [a ^ b for a, b in zip(x, rk[r])]
    return b"".join(v.to_bytes(4, "little") for v in x)


if __name__ == "__main__":
    key = bytes(range(16))
    plaintext = bytes(range(16))

    ciphertext = encrypt_block(key, plaintext)
    recovered = decrypt_block(key, ciphertext)

    print(f"Key:        {key.hex()}")
    print(f"Plaintext:  {plaintext.hex()}")
    print(f"Ciphertext: {ciphertext.hex()}")
    print(f"Recovered:  {recovered.hex()}")

Running it produces this output:

Key:        000102030405060708090a0b0c0d0e0f
Plaintext:  000102030405060708090a0b0c0d0e0f
Ciphertext: 4c7d8a328072a22c823e4a1f3acda16d
Recovered:  000102030405060708090a0b0c0d0e0f

I checked this code against two independent sources before writing it up. It matches the Linux kernel’s published vectors for 128-bit and 256-bit keys. It also matches all 1,047 vectors in the Botan test suite, which cover 128, 192, and 256-bit keys.

One detail trips up many first attempts. The original Serpent paper writes its hex strings right to left, so its published vectors look reversed compared to what libraries use. The code here treats bytes as little-endian words, the same convention as the Linux kernel and Botan test data. If your output looks like a byte-reversed version of a published vector, that is the cause.

For Fun: The Same Cipher in 30 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 122-line implementation above into 30 lines. The eight S-boxes share a single line, and the linear transformation, key schedule, and block routines are tightened. It needs no imports and no other files.

MASK=0xFFFFFFFF;PHI=0x9E3779B9
SBOX=[[3,8,15,1,10,6,5,11,14,13,4,2,7,0,9,12],[15,12,2,7,9,0,5,10,1,11,14,8,6,13,3,4],[8,6,7,9,3,12,10,15,13,1,14,4,0,11,5,2],[0,15,11,8,12,9,6,3,13,1,2,4,10,7,5,14],[1,15,8,3,12,0,11,6,2,5,4,10,9,14,7,13],[15,5,2,11,4,10,9,12,0,3,14,8,13,6,7,1],[7,2,12,5,8,4,6,11,14,9,1,15,13,3,10,0],[1,13,15,0,14,8,2,11,7,4,12,10,9,3,5,6]];SBOX_INV=[[box.index(v) for v in range(16)] for box in SBOX]
rol=lambda x,n: ((x<<n)|(x>>(32-n)))&MASK; ror=lambda x,n: ((x>>n)|(x<<(32-n)))&MASK
def sbox_layer(box,words):
 out=[0,0,0,0]
 for bit in range(32):
  v=sum(((words[j]>>bit)&1)<<j for j in range(4)); s=box[v]
  for j in range(4): out[j]|=((s>>j)&1)<<bit
 return out
def linear(x):
 x0,x1,x2,x3=x; x0=rol(x0,13); x2=rol(x2,3); x1^=x0^x2; x3^=x2^((x0<<3)&MASK); x1=rol(x1,1); x3=rol(x3,7); x0^=x1^x3; x2^=x3^((x1<<7)&MASK); x0=rol(x0,5); x2=rol(x2,22); return [x0,x1,x2,x3]
def linear_inv(x):
 x0,x1,x2,x3=x; x2=ror(x2,22); x0=ror(x0,5); x2^=x3^((x1<<7)&MASK); x0^=x1^x3; x3=ror(x3,7); x1=ror(x1,1); x3^=x2^((x0<<3)&MASK); x1^=x0^x2; x2=ror(x2,3); x0=ror(x0,13); return [x0,x1,x2,x3]
def key_schedule(key):
 if len(key) not in (16,24,32): raise ValueError("Serpent keys are 16, 24 or 32 bytes")
 padded = key + b"\x01" + b"\x00"*(31-len(key)) if len(key)<32 else key; w = [int.from_bytes(padded[4*i:4*i+4],"little") for i in range(8)]
 for i in range(132): w.append(rol(w[i]^w[i+3]^w[i+5]^w[i+7]^PHI^i,11))
 return [sbox_layer(SBOX[(3-r)%8], w[8+4*r:12+4*r]) for r in range(33)]
def encrypt_block(key, block):
 rk = key_schedule(key); x = [int.from_bytes(block[4*i:4*i+4],"little") for i in range(4)]
 for r in range(32):
  x = [a^b for a,b in zip(x, rk[r])]; x = sbox_layer(SBOX[r%8], x); x = linear(x) if r < 31 else x
 x = [a^b for a,b in zip(x, rk[32])]
 return b"".join(v.to_bytes(4,"little") for v in x)
def decrypt_block(key, block):
 rk = key_schedule(key); x = [int.from_bytes(block[4*i:4*i+4],"little") for i in range(4)]
 x = [a^b for a,b in zip(x, rk[32])]
 for r in range(31,-1,-1):
  x = linear_inv(x) if r < 31 else x; x = sbox_layer(SBOX_INV[r%8], x); x = [a^b for a,b in zip(x, rk[r])]
 return b"".join(v.to_bytes(4,"little") for v in x)
key = bytes(range(16)); plaintext = bytes(range(16)); ciphertext = encrypt_block(key, plaintext); recovered = decrypt_block(key, ciphertext); print(f"Key:        {key.hex()}\nPlaintext:  {plaintext.hex()}\nCiphertext: {ciphertext.hex()}\nRecovered:  {recovered.hex()}")

Running it prints the same four lines as the readable version, including the Serpent-128 ciphertext from the Linux kernel and Botan vectors:

Key:        000102030405060708090a0b0c0d0e0f
Plaintext:  000102030405060708090a0b0c0d0e0f
Ciphertext: 4c7d8a328072a22c823e4a1f3acda16d
Recovered:  000102030405060708090a0b0c0d0e0f

I checked it against the readable code on 300 random keys and blocks, 100 for each key size. Encryption matched every time, and decryption recovered every block. The S-boxes are identical, and it reproduces the Serpent-256 test vector. Keys of the wrong length raise the same error.

Limitations

This implementation is a faithful teaching version, not a production one:

• Single 128-bit block only. There is no mode of operation for longer messages and no padding scheme for partial blocks.
• Slow and not constant-time. The S-box layer here looks up a table for each of 32 columns, one bit at a time. A real bitslice implementation uses pure logic instructions, which is much faster and avoids data-dependent memory access.
• No hardening of any kind. It has no protection against timing, power, or fault attacks.
• Serpent itself is not the limit. The cipher is strong. This code is for understanding the structure, so use a vetted library for real data.

Security Status

No practical attack on full 32-round Serpent is known. The best published results reach only about a third of the rounds. A 2011 attack on 11 rounds of Serpent-128 needs 2¹¹⁶ known plaintexts and 2¹⁰⁷·⁵ operations. Attacks on 12 rounds of Serpent-256 need between 2¹¹⁸ and 2²³⁷·⁵ operations depending on the variant. All of these are far beyond any real computation.

That is the payoff of the design philosophy. Even if attacks improve by a wide margin, Serpent still has room to spare. The cost is speed, since Rijndael does the same job in fewer rounds and runs much faster in software on most processors. AES also gets dedicated instructions on most modern processors, which widens the gap. Serpent is a good choice when the largest possible margin matters more than speed.

FAQ

Is Serpent still safe to use?

Yes, it is still safe. No practical attack exists, and its security margin is among the largest of any block cipher. It is available in libraries such as Botan, libgcrypt, and Crypto++, and in disk-encryption tools such as VeraCrypt. AES remains the better default because of hardware support.

Why didn’t Serpent win the AES competition?

It came down to speed. Rijndael was much more efficient in software and on constrained devices, and NIST weighed that heavily. Serpent actually had the fewest negative votes among the finalists, so its loss came from performance, not from any security concern.

Why does Serpent use 32 rounds?

The designers believed 16 rounds were enough against all known attacks. They doubled that number to leave room for future discoveries. It was a deliberate trade of speed for confidence.

What is bitslicing?

It is a way of running many small substitutions in parallel using ordinary logic instructions. Serpent treats four 32-bit words as 32 columns of four bits, and a single sequence of logic operations substitutes all 32 columns at once.

Why do some published test vectors look backward?

The original paper writes hex strings right to left. Software treats the same data as little-endian bytes, so the two notations are byte-reversed versions of each other. Always check which convention a vector uses before comparing results.

References

1. Anderson, R., Biham, E., and Knudsen, L. “Serpent: A Proposal for the Advanced Encryption Standard.” Submission to the AES competition, 1998.

2. Nechvatal, J. et al. “Report on the Development of the Advanced Encryption Standard (AES).” NIST, 2000.

3. Dunkelman, O., Indesteege, S., and Keller, N. “A Differential-Linear Attack on 12-Round Serpent.” INDOCRYPT 2008.

4. Wikipedia. “Serpent (cipher).” Available at: https://en.wikipedia.org/wiki/Serpent_(cipher)