The SEAL Stream Cipher

The SEAL Stream Cipher

Introduction

SEAL is a stream cipher designed for fast software encryption on 32-bit processors. It has one feature that most stream ciphers lack. You can ask for any part of the keystream directly, without generating everything before it. That makes it a natural fit for encrypting a disk, where you want to read sector 5,000 without touching sectors 1 to 4,999.

The cipher is a pseudorandom function family. A 160-bit key and a 32-bit position index n together select one 4,096-byte block of keystream. Different values of n give blocks that behave as if they were independent.

Table of Contents

• History
• The Tables
• Initialization
• The Main Loop
• Random Access
• Byte Order
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History

Phillip Rogaway, then at the University of California, Davis, and Don Coppersmith of IBM designed SEAL. According to Wikipedia, the first version was published in 1994, and the current version, 3.0, in 1997. The journal version of the paper, “A Software-Optimized Encryption Algorithm,” appeared in the Journal of Cryptology in 1998.

SEAL is built for machines with a 32-bit word size and plenty of RAM. Wikipedia quotes a speed of around 4 cycles per byte. Two United States patents cover SEAL, and both are assigned to IBM.

The Tables

SEAL does most of its work with tables. The tables are built once from the key, and building them is the only slow step. The key is five 32-bit words, a0 to a4, read big-endian.

To make table entries, SEAL needs a way to turn the key into a long sequence of pseudorandom words. It does that with the compression function of SHA-1. The function Γ(i) is defined like this:

1. Set the five SHA-1 chaining words to the key words a0 to a4.
2. Make a 16-word message block. Word 0 is i div 5, and the other fifteen words are zero.
3. Run one SHA-1 compression, without any padding, and take word number i mod 5 of the result.

Each compression gives five words, so five consecutive values of i share one run of SHA-1. SEAL then fills three tables:

Table	Size	Entries
T	512 words	T[i] = Γ(i)
S	256 words	S[i] = Γ(0x1000 + i)
R	16 words	R[i] = Γ(0x2000 + i)

Together the tables take about 3 KB of memory. The size of R depends on a parameter L, the number of keystream bits produced for each position index. This guide uses the usual choice, L = 32768 bits, or 4,096 bytes, which gives 4 × L / 8192 = 16 words in R. In general R has 4 × L / 8192 words, and L is a multiple of 8192.

Initialization

Before producing keystream for position n, SEAL fills four 32-bit registers a, b, c, and d. They mix n with four words of R, using rotations so that every register sees a different view of n:

a = n                 ^ R[4l]
b = (n rotated right 8)  ^ R[4l+1]
c = (n rotated right 16) ^ R[4l+2]
d = (n rotated right 24) ^ R[4l+3]

Here l selects a group of four words from R, and it runs from 0 to 3 as the keystream for one position index unfolds. SEAL then runs a short warm-up. Each pass is four dependent table lookups. Take a as an example:

p = a & 0x7FC            (bits 2 to 10 of a, as a byte offset into T)
b = b + T[p / 4]
a = a rotated right 9

The same step repeats with b updating c, then c updating d, then d updating a. The warm-up does this pass twice, and then it saves four values, n1 = d, n2 = b, n3 = a, and n4 = c. One more pass follows, and the registers are ready.

Interactive Visualizer

The visualizer above runs this exact algorithm. Enter a 160-bit key, a 32-bit position index, and up to 64 bytes of message in hex. The log shows the four registers after initialization and after every 16 bytes of keystream. Each 16-byte block is one pass of the main loop.

The Main Loop

The main loop runs 64 times, and each pass produces four output words, which is 16 bytes. In each pass SEAL does eight table lookups, with additions, XORs, and rotations in between. Each new offset is built from the previous offset and a register, for example p = (p + c) & 0x7FC, so every lookup both updates a register and decides where the next lookup goes. The four registers then give four words by combining them with entries of S:

output words:  b + S[4i],  c ^ S[4i+1],  d + S[4i+2],  a ^ S[4i+3]

After the words are written, SEAL mixes in the saved values. On even passes it uses n1 and n2. On odd passes it uses n3 and n4:

even i:  a += n1,  b += n2,  c ^= n1,  d ^= n2
odd  i:  a += n3,  b += n4,  c ^= n3,  d ^= n4

The 64 passes make 8,192 bits. With L = 32768, SEAL does this four times for one position index, with l = 0, 1, 2, 3 selecting a different group of four words of R each time. That gives 4,096 bytes. After that the position index goes up by one, and the process starts over with n + 1.

Random Access

Because the whole keystream depends only on the key and on n, SEAL can start at any position index. To read the bytes starting at offset k, work out n = k div 4096 and run the loop from there. A short skip inside the block costs only the passes needed to reach it.

This is the property that sets SEAL apart. A cipher like RC4 must produce every earlier byte before it reaches the one you want. With SEAL, each 4,096-byte segment can be produced on its own, which suits disks and databases.

Byte Order

SEAL 3.0 comes in two forms, differing only in how words become bytes. The big-endian form reads the key as big-endian words and writes every keystream word out most significant byte first. The Crypto++ library also defines a little-endian form. This guide and its visualizer cover only the big-endian form, which is the one with the published test vector.

A Worked Example

This is the Crypto++ test vector, which uses the key 67452301 efcdab89 98badcfe 10325476 c3d2e1f0, written as five words, and the position index n = 013577af. The key words are the same as the SHA-1 initial values.

Tables. Running one SHA-1 compression with the key as the chaining state and an all-zero block gives the five words 92b404e5 56588ced 6c1acd4e bf053f68 09f73a93. These are Γ(0) to Γ(4), so T[0] = 92b404e5, T[1] = 56588ced, T[2] = 6c1acd4e, and T[3] = bf053f68. The next block, with word 0 set to 1, gives cd5f176a b863f14e 2b014a2f 4407e646 38665610. The last table entry is T[511] = 19ccf158. The S table starts with S[0] = 907c1e3d and S[1] = ce71ef0a, and it ends with S[255] = 0b5a0949. The first four entries of R are 5021758d, ce577c11, fa5bd5dd, and 366d1b93.

Registers. The position index 013577af rotated right by 8, 16, and 24 bits is af013577, 77af0135, and 3577af01. XORing with R[0] to R[3] gives a = 51140222, b = 61564966, c = 8df4d4e8, and d = 031ab492.

The first lookup. For this a, the offset is p = a & 0x7FC = 0x220, which is entry 136 of T. That entry is 0dfbf185. Adding it to b gives b = 6f523aeb, and rotating a right by 9 bits gives 11288a01.

After initialization. The saved values are n1 = 26d532b7, n2 = c95d8d09, n3 = 819d1873, and n4 = 66abb5bb. After the third pass, a = f6b5a88c, b = 0f49a264, c = f548d67f, and d = bb30e46b.

The first pass of the main loop. The first pass leaves the registers a, b, c, and d at 2d09ebb3 a723e758 55f52b96 5bc8c416. The four output words are b + S[0] = 37a00595, c ^ S[1] = 9b84c49c, d + S[2] = a4be1e05, and a ^ S[3] = 0673530f, which are the first 16 keystream bytes. Pass 0 is even, so n1 and n2 are then mixed in, and the registers become 53df1e6a 70817461 73201921 9295491f, which is the first row of the visualizer’s log.

Keystream. The first 32 bytes are:

37a005959b84c49ca4be1e050673530f
5fb097fdf6a13fbd6c2cdecd81fdee7c

They agree with the start of the Crypto++ vector. The last 16 bytes of the 4,096-byte segment are 4d1a6134fed9fede636504aa691e08e4. The next 16 bytes after that are eabd614999b4e8efc6ed3e4a441f9c5f, which is also the start of the keystream for n + 1. That shows how the position index rolls over.

Encryption. The 49-byte message SEAL generates a keystream from a position index. is 5345414c2067656e6572617465732061206b657973747265616d2066726f6d206120706f736974696f6e20696e6465782e in hex. XORed with the keystream it gives:

64e544d9bbe3a1f2c1cc7f716300736e7fdbf28485d54dd80d41feabf392835c4b9db3881749ee966fcf02ea810335fdef

Python Implementation

This is a complete SEAL 3.0, big-endian: the SHA-1 compression function, the tables, the initialization, the main loop, and encryption. It generates keystream from any position index.

# seal.py
#
# SEAL 3.0, the software-optimized stream cipher by Phillip Rogaway and
# Don Coppersmith. It is a length-increasing pseudorandom function: a 160-bit
# key and a 32-bit position index n select one of 2^32 keystream segments.
# Setup builds three tables from the key with the SHA-1 compression function.
# Keystream is then produced with additions, XORs, rotations and table lookups.
#
# This is the big-endian variant. The key is read as five big-endian 32-bit
# words, and every keystream word is written out big-endian.

MASK = 0xFFFFFFFF
L = 32768            # keystream bits produced per value of n
BITS_PER_ITERATION = 8192


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


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


def sha1_compress(state, block):
    """One SHA-1 compression: 5 state words and 16 message words in, 5 words out."""
    w = list(block)
    for t in range(16, 80):
        w.append(rol(w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16], 1))
    a, b, c, d, e = state
    for t in range(80):
        if t < 20:
            f, k = (b & c) | (~b & d), 0x5A827999
        elif t < 40:
            f, k = b ^ c ^ d, 0x6ED9EBA1
        elif t < 60:
            f, k = (b & c) | (b & d) | (c & d), 0x8F1BBCDC
        else:
            f, k = b ^ c ^ d, 0xCA62C1D6
        temp = (rol(a, 5) + (f & MASK) + e + k + w[t]) & MASK
        a, b, c, d, e = temp, a, rol(b, 30), c, d
    return [(s + v) & MASK for s, v in zip(state, (a, b, c, d, e))]


def gamma(key_words, i):
    """Word i of the key-derived sequence: one SHA-1 compression gives 5 words."""
    z = sha1_compress(key_words, [i // 5] + [0] * 15)
    return z[i % 5]


def make_tables(key):
    if len(key) != 20:
        raise ValueError("SEAL keys are 20 bytes")
    kw = [int.from_bytes(key[4 * i:4 * i + 4], "big") for i in range(5)]
    t = [gamma(kw, i) for i in range(512)]
    s = [gamma(kw, 0x1000 + i) for i in range(256)]
    r = [gamma(kw, 0x2000 + i) for i in range(4 * (L // BITS_PER_ITERATION))]
    return t, s, r


def rounds(a, b, c, d, t):
    # 0x7FC keeps bits 2 to 10 of a register: a multiple of 4 below 2048, a byte offset of a 32-bit entry of T (p >> 2 is the index)
    """One pass of four dependent table lookups, used during initialization."""
    p = a & 0x7FC
    b = (b + t[p >> 2]) & MASK
    a = ror(a, 9)
    p = b & 0x7FC
    c = (c + t[p >> 2]) & MASK
    b = ror(b, 9)
    p = c & 0x7FC
    d = (d + t[p >> 2]) & MASK
    c = ror(c, 9)
    p = d & 0x7FC
    a = (a + t[p >> 2]) & MASK
    d = ror(d, 9)
    return a, b, c, d


def segment(tables, n, l):
    """Generate the 8192 bits (256 words) for position index n and sub-block l."""
    t, s, r = tables
    # set-up: mix n and its rotations with four words of R
    a = n ^ r[4 * l]
    b = ror(n, 8) ^ r[4 * l + 1]
    c = ror(n, 16) ^ r[4 * l + 2]
    d = ror(n, 24) ^ r[4 * l + 3]
    for _ in range(2):
        a, b, c, d = rounds(a, b, c, d, t)
    n1, n2, n3, n4 = d, b, a, c
    a, b, c, d = rounds(a, b, c, d, t)
    words = []
    # the main loop: eight table lookups per pass, then four output words mixed with S
    for i in range(64):
        p = a & 0x7FC
        a = ror(a, 9)
        b = (b + t[p >> 2]) & MASK
        b ^= a
        q = b & 0x7FC
        b = ror(b, 9)
        c ^= t[q >> 2]
        c = (c + b) & MASK
        p = (p + c) & 0x7FC
        c = ror(c, 9)
        d = (d + t[p >> 2]) & MASK
        d ^= c
        q = (q + d) & 0x7FC
        d = ror(d, 9)
        a ^= t[q >> 2]
        a = (a + d) & MASK
        p = (p + a) & 0x7FC
        b ^= t[p >> 2]
        a = ror(a, 9)
        q = (q + b) & 0x7FC
        c = (c + t[q >> 2]) & MASK
        b = ror(b, 9)
        p = (p + c) & 0x7FC
        d ^= t[p >> 2]
        c = ror(c, 9)
        q = (q + d) & 0x7FC
        d = ror(d, 9)
        a = (a + t[q >> 2]) & MASK
        words += [(b + s[4 * i]) & MASK, c ^ s[4 * i + 1], (d + s[4 * i + 2]) & MASK, a ^ s[4 * i + 3]]
        if i & 1:
            a = (a + n3) & MASK
            b = (b + n4) & MASK
            c ^= n3
            d ^= n4
        else:
            a = (a + n1) & MASK
            b = (b + n2) & MASK
            c ^= n1
            d ^= n2
    return words


def keystream(key, n, length, tables=None):
    """The first `length` bytes of keystream for position index n. Pass tables=make_tables(key) to reuse them."""
    tables = tables or make_tables(key)
    out = bytearray()
    sub = 0
    while len(out) < length:
        for w in segment(tables, n, sub):
            out += w.to_bytes(4, "big")
        sub += 1
        if sub == L // BITS_PER_ITERATION:
            sub = 0
            n = (n + 1) & MASK
    return bytes(out[:length])


def crypt(key, n, data, tables=None):
    return bytes(a ^ b for a, b in zip(data, keystream(key, n, len(data), tables)))


if __name__ == "__main__":
    key = bytes.fromhex("67452301efcdab8998badcfe10325476c3d2e1f0")
    n = 0x013577AF
    message = b"SEAL generates a keystream from a position index."
    ciphertext = crypt(key, n, message)
    print("Key:        " + key.hex())
    print("Index n:    %08x" % n)
    print("Keystream:  " + keystream(key, n, 16).hex())
    print("Plaintext:  " + message.hex())
    print("Ciphertext: " + ciphertext.hex())
    print("Recovered:  " + crypt(key, n, ciphertext).decode())

Running it produces this output:

Key:        67452301efcdab8998badcfe10325476c3d2e1f0
Index n:    013577af
Keystream:  37a005959b84c49ca4be1e050673530f
Plaintext:  5345414c2067656e6572617465732061206b657973747265616d2066726f6d206120706f736974696f6e20696e6465782e
Ciphertext: 64e544d9bbe3a1f2c1cc7f716300736e7fdbf28485d54dd80d41feabf392835c4b9db3881749ee966fcf02ea810335fdef
Recovered:  SEAL generates a keystream from a position index.

I checked this code in two ways before writing it up. The SHA-1 compression function matches Python’s hashlib on four messages. The cipher reproduces all 4,096 bytes of the Crypto++ test vector, which the Crypto++ authors say they checked in part against a vector in the 1997 SEAL paper. I wrote the code from the Crypto++ source, so this is a check against one implementation and its vector, and I could not find a second independent implementation to compare.

Limitations

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

• Built for speed in C. The Python version is slow, and SEAL’s strength is the way it uses fast table lookups on real hardware.
• Not constant-time. Every lookup uses an index that depends on secret data, so real software must consider cache-timing leaks.
• Setup is expensive. Building the tables needs hundreds of SHA-1 compressions and about 3 KB of memory, so SEAL suits keys that are used for a long time.
• No authentication. SEAL only hides data, and a changed ciphertext goes undetected.
• Patents. Two IBM patents cover SEAL, which limited its use.

Security Status

SEAL has not been broken in the sense of recovering the key, but it has been shown to be distinguishable from a random function. Helena Handschuh and Henri Gilbert published a statistical attack at FSE 1997 that can tell the output from random after about 2³⁴ bytes. Scott Fluhrer later published a cryptanalysis of the SEAL 3.0 pseudorandom function family at FSE 2001.

Those results do not give practical key recovery, but they show that SEAL does not behave like an ideal random function over very long outputs. Modern stream ciphers such as ChaCha20 are faster on current processors and do not have these limits. SEAL is mostly of historical and educational interest today.

FAQ

What is special about SEAL?

It is a pseudorandom function family, so you can jump straight to any segment of the keystream. Most stream ciphers must produce all earlier keystream first.

Why does SEAL use SHA-1?

SHA-1’s compression function is a convenient, well-studied source of pseudorandom words. SEAL uses it only to build its tables from the key. The cipher itself does not hash anything.

Is SEAL still used?

It is rarely used today. Two IBM patents covered it, and faster, freer ciphers like ChaCha20 and AES in counter mode took its place. It remains a useful example of a cipher with random access.

Is SEAL secure?

No practical key recovery is known. Statistical attacks can distinguish its output from random after a large amount of data, so it is no longer a good choice for new designs.

What are the L and n parameters?

The position index n is a 32-bit number that selects a segment of keystream. The parameter L is how many bits each n gives. This guide uses L = 32768, so each segment is 4,096 bytes.

References

1. Rogaway, P. and Coppersmith, D. “A Software-Optimized Encryption Algorithm.” Journal of Cryptology 11(4), 1998.

2. Handschuh, H. and Gilbert, H. “χ² Cryptanalysis of the SEAL Encryption Algorithm.” Fast Software Encryption (FSE) 1997.

3. Fluhrer, S. “Cryptanalysis of the SEAL 3.0 Pseudorandom Function Family.” Fast Software Encryption (FSE) 2001.

4. Dai, W. and Janke, L. “seal.cpp: SEAL 3.0 in Crypto++.” Available at: https://github.com/weidai11/cryptopp/blob/master/seal.cpp

5. Wikipedia. “SEAL (cipher).” Available at: https://en.wikipedia.org/wiki/SEAL_(cipher)