DES and the Feistel Network

The first public standard cipher

In 1977 the US government made an IBM design, DES (Data Encryption Standard), the official cipher for unclassified data. For more than 20 years banks, ATMs and smart cards relied on it. Its 56-bit key turned out to be its weak spot. In 1998 a $250,000 machine built by the EFF found a DES key in 56 hours. AES replaced it in 2001. DES is still taught everywhere, because its design, the Feistel network, is elegant and appears in many later ciphers.

The Feistel idea

Split the block into a left half L and a right half R of 32 bits each. Every round does:

L(i) = R(i−1)
R(i) = L(i−1) XOR f(R(i−1), K(i))

The beauty is in undoing it. Given L(i) and R(i), you immediately know R(i−1) = L(i), and then L(i−1) = R(i) XOR f(L(i), K(i)). You only ever compute f forwards, so f doesn’t need to be invertible: it can be as messy as the designer likes. Decryption is the same circuit with the round keys used in reverse order.

Inside the round function f

1. Expansion E: the 32 bits of R become 48. Each group of 4 bits borrows a bit from each neighbour, so one input bit feeds two S-boxes.
2. Key mixing: XOR with the 48-bit round key.
3. S-boxes: cut the 48 bits into eight 6-bit pieces. In each piece, the outer two bits choose the row (0–3) and the middle four bits choose the column (0–15) of a 4 × 16 table. The entry is the 4-bit output. The S-boxes are the only non-linear step. Without them DES would be a set of linear equations, easy to solve.
4. Permutation P: shuffle the 32 output bits, so that each S-box feeds several S-boxes in the next round.

The key schedule

PC-1 drops the 8 parity bits and splits the remaining 56 into two 28-bit halves, C and D. Before each round both halves rotate left by 1 bit (rounds 1, 2, 9 and 16) or 2 bits (all others). PC-2 then picks 48 of the 56 bits as the round key. The rotations add up to 28, so after round 16 C and D are back where they started.

Worked example

This is the classic textbook example: key 133457799BBCDFF1, block 0123456789ABCDEF.

Note the last line: after round 16 the halves are written as (R16, L16). The final swap is undone, so encryption and decryption have the same structure.

The avalanche effect

Change one bit of the plaintext and run both blocks side by side. After the initial permutation they differ in 1 bit, after round 3 in 22, and from round 4 on in about half of the 64. That is what a good cipher must do: similar inputs must give unrelated outputs. Press Avalanche to see each round.

Why DES is retired

• The key is too short. 2⁵⁶ keys can be searched in hours with special hardware, and in about a day on rented cloud GPUs.
• Double DES doesn’t help much. A meet-in-the-middle attack breaks it in about 2⁵⁷ steps.
• Triple DES (3DES) computes E(K1, D(K2, E(K3, x))) and gives about 112 bits of security. It was used for years in payment cards, but NIST withdrew it at the end of 2023 because its 64-bit block is too small for today’s data volumes.

Today, use AES.

Code

T = lambda s: [int(x) for x in s.split()]
IP = T('58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 '
       '57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7')
FP = [IP.index(i) + 1 for i in range(1, 65)]
E = T('32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 '
      '16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1')
P = T('16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25')
PC1 = T('57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 '
        '63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4')
PC2 = T('14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 '
        '41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32')
SHIFTS = T('1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1')
S = [T(s) for s in [
    '14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13',
    '15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9',
    '10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12',
    '7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14',
    '2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3',
    '12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13',
    '4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12',
    '13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11']]

def permute(x, table, n_in):
    """Output bit i = input bit table[i] (bits numbered from 1 at the left)."""
    out = 0
    for pos in table:
        out = (out << 1) | ((x >> (n_in - pos)) & 1)
    return out

def round_keys(key):
    cd = permute(key, PC1, 64)                       # drop the 8 parity bits
    c, d = cd >> 28, cd & 0xFFFFFFF
    keys = []
    for s in SHIFTS:
        c = ((c << s) | (c >> (28 - s))) & 0xFFFFFFF  # rotate both halves left
        d = ((d << s) | (d >> (28 - s))) & 0xFFFFFFF
        keys.append(permute((c << 28) | d, PC2, 56))
    return keys

def f(r, k):
    x = permute(r, E, 32) ^ k                        # expand to 48 bits, add the key
    out = 0
    for i in range(8):                               # 8 S-boxes: 6 bits in, 4 bits out
        six = (x >> (42 - 6 * i)) & 0x3F
        row = ((six >> 4) & 2) | (six & 1)           # the two outer bits
        col = (six >> 1) & 0xF                       # the four middle bits
        out = (out << 4) | S[i][16 * row + col]
    return permute(out, P, 32)

def des(block, key, decrypt=False):
    keys = round_keys(key)[::-1] if decrypt else round_keys(key)
    x = permute(block, IP, 64)
    l, r = x >> 32, x & 0xFFFFFFFF
    for k in keys:
        l, r = r, l ^ f(r, k)                        # one Feistel round
    return permute((r << 32) | l, FP, 64)            # swap back, final permutation

c = des(0x0123456789ABCDEF, 0x133457799BBCDFF1)
print(f'{c:016X}')                                   # 85E813540F0AB405
print(f'{des(c, 0x133457799BBCDFF1, decrypt=True):016X}')   # 0123456789ABCDEF

Common mistakes

• Counting 64 key bits. Only 56 are used. The rest are parity bits.
• Forgetting the final swap. The output is FP(R16, L16), not FP(L16, R16).
• Mixing up row and column in an S-box. The row comes from the outer two bits, the column from the middle four.
• Trying to invert f for decryption. You never need to. Run the same rounds with the keys in reverse order.
• Thinking Double DES gives 112-bit security. Meet-in-the-middle brings it down to about 2⁵⁷.