Breaking DES with Brute-Force Key Search

Breaking DES with Brute-Force Key Search

Introduction

DES survived more than twenty years of public cryptanalysis. Differential and linear cryptanalysis both exist, and both need huge amounts of chosen or known plaintext. In practice, DES fell to something far less elegant. Someone simply tried every key. The base guide calls its 56-bit key its fatal weakness. This post shows what that means in code. It runs a genuine exhaustive key search against real, full 16-round DES. The attacker knows one plaintext block, its ciphertext, and most of the key. The loop fills in the rest.

Table of Contents

• Why Brute Force Is the Real Attack
• The Attack: Try, Encrypt, Compare
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Scaling Up to Deep Crack
• Limitations of This Attack
• FAQ
• References

Why Brute Force Is the Real Attack

Every other breaker in this category exploits a structural flaw. Fermat’s method exploits primes that sit too close together. Baby-step giant-step splits an exponent in two. DES has no flaw like that to lean on. Its S-boxes were quietly hardened against differential cryptanalysis years before that attack went public. The best academic attack, Matsui’s linear cryptanalysis, needs about 2⁴³ known plaintext/ciphertext pairs. No real attacker ever gets that much.

So the practical attack is the dumbest one. A DES key is 64 bits long, but only 56 of those bits matter. The lowest bit of every byte is a parity bit, and the cipher ignores it completely. That leaves 2⁵⁶ keys, about 72 quadrillion. In 1977 that sounded safe. By 1998 it wasn’t, and nothing about DES itself had changed. Hardware had simply caught up.

The Attack: Try, Encrypt, Compare

A brute-force search needs one known plaintext block and its matching ciphertext. That’s easier to get than it sounds. File headers, protocol greetings, and padding all put predictable bytes at predictable places.

1. Build a candidate key. Fill in the key bits that are still unknown with the next value in the search. Set each byte’s parity bit so the key is well-formed. DES ignores parity, so this changes nothing about the result.
2. Encrypt the known plaintext. Run the full 16-round DES encryption under the candidate key.
3. Compare. If the output doesn’t equal the known ciphertext, move on to the next key.
4. Confirm a match. A 64-bit block matching by chance is very unlikely, though not impossible. Real searches check a second known block before trusting the result.

Written as one line, the attack searches for the key that satisfies:

find K such that  DES_K(P₁) = C₁  and  DES_K(P₂) = C₂

That’s the whole algorithm. There’s no statistics, no scoring, and no clever math. Each candidate either matches or it doesn’t.

How Many Keys to Expect

On average, a search finds the key halfway through the keyspace. The worst case needs every key. The number of false matches matters too. There are 2⁵⁶ keys but 2⁶⁴ possible ciphertext blocks. So a random wrong key matches the first block with probability 2⁻⁶⁴. Across the whole keyspace, that’s about 2⁻⁸ false alarms expected per search, or roughly one in 256 full searches. The second block makes the odds of a false alarm vanish entirely.

Scaling It Down to Run Here

A browser can’t search 2⁵⁶ keys. So this demo gives the attacker the first 6 bytes of the key and searches only the last 2. Each unknown byte carries 7 real key bits plus 1 parity bit. Two unknown bytes therefore mean 2¹⁴ = 16,384 candidates, not 2¹⁶ = 65,536. Everything else is identical to the real attack. The cipher is still full DES, with full-size blocks and the full key schedule.

A Worked Example

The visualizer’s default values reuse the DES guide’s own textbook test vector:

• True key: 133457799BBCDFF1
• Known plaintext 1: 0123456789ABCDEF
• Ciphertext 1: 85E813540F0AB405
• Known plaintext 2: Now is t (hex 4E6F772069732074)
• Ciphertext 2: AAEA30F286270F21

The attacker knows the key prefix 133457799BBC and nothing about the last two bytes.

1. Enumerate candidates. A 14-bit counter runs from 0 to 16,383. Its top 7 bits become the 7th key byte. Its bottom 7 bits become the 8th. Each byte gets its parity bit appended.
2. Search. The first 14,328 candidates all encrypt plaintext 1 to something other than 85E813540F0AB405.
3. Match. Candidate 14,329 is counter value 14,328. Its top 7 bits are 111 (0x6F), which becomes byte DF with parity. Its bottom 7 bits are 120 (0x78), which becomes byte F1. The full candidate is 133457799BBCDFF1, and it encrypts plaintext 1 to exactly 85E813540F0AB405.
4. Confirm. The same key encrypts Now is t to AAEA30F286270F21. Both blocks match, so the key is recovered.

That took 14,329 DES encryptions out of 16,384 possible. The search just happened to land late this time. The true key’s last bytes sit near the top of the counter’s range.

Python Implementation

The visualizer runs this exact search in JavaScript. Here’s the same attack in Python. The script is self-contained. Its DES section is the DES guide’s own Python code, trimmed to encryption only.

Key Features

• Real DES, self-contained. It carries the base guide’s own DES code, so it runs on its own with no extra files.
• Parity-aware enumeration. Each unknown byte is 7 searched bits plus 1 computed parity bit. That’s why 2 unknown bytes cost 2¹⁴ tries, not 2¹⁶.
• Two-block confirmation. The first block filters candidates. The second one rules out a chance collision.
• Measures its own speed. It then extrapolates how long the full 2⁵⁶ keyspace would take at the same rate.

Code

# des_brute_force.py
#
# Known-plaintext brute-force key search against real, full DES.
# The attacker knows the first 6 key bytes and searches the last 2.
# Each unknown byte carries 7 real key bits plus 1 parity bit, so
# 2 unknown bytes means 2^14 = 16,384 candidate keys. Deep Crack ran
# this exact loop over all 2^56 keys, in custom silicon.
#
# Self-contained: the DES part below is the same code as the DES guide's
# Python implementation, trimmed to encryption only.

import time

# ---- DES (from the DES guide) ----

IP = [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 = [40,8,48,16,56,24,64,32, 39,7,47,15,55,23,63,31,
      38,6,46,14,54,22,62,30, 37,5,45,13,53,21,61,29,
      36,4,44,12,52,20,60,28, 35,3,43,11,51,19,59,27,
      34,2,42,10,50,18,58,26, 33,1,41,9,49,17,57,25]

E = [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 = [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 = [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 = [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 = [1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]

SBOX = [
 [[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(bits, table):
    return [bits[i - 1] for i in table]


def bytes_to_bits(data):
    return [(byte >> (7 - i)) & 1 for byte in data for i in range(8)]


def bits_to_bytes(bits):
    return bytes(int("".join(map(str, bits[i:i + 8])), 2) for i in range(0, len(bits), 8))


def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]


def generate_subkeys(key_bytes):
    permuted = permute(bytes_to_bits(key_bytes), PC1)
    C, D = permuted[:28], permuted[28:]
    subkeys = []
    for shift in SHIFTS:
        C = C[shift:] + C[:shift]
        D = D[shift:] + D[:shift]
        subkeys.append(permute(C + D, PC2))
    return subkeys


def feistel(R, subkey):
    x = xor(permute(R, E), subkey)
    output = []
    for i in range(8):
        block = x[i * 6:(i + 1) * 6]
        row = (block[0] << 1) | block[5]
        col = (block[1] << 3) | (block[2] << 2) | (block[3] << 1) | block[4]
        val = SBOX[i][row][col]
        output.extend([(val >> 3) & 1, (val >> 2) & 1, (val >> 1) & 1, val & 1])
    return permute(output, P)


def des_block(block_bytes, subkeys):
    bits = permute(bytes_to_bits(block_bytes), IP)
    L, R = bits[:32], bits[32:]
    for subkey in subkeys:
        L, R = R, xor(L, feistel(R, subkey))
    return bits_to_bytes(permute(R + L, FP))


# ---- The brute-force attack ----


def with_odd_parity(b7):
    # 7 key bits in the top of the byte, parity bit in the lowest position
    byte = b7 << 1
    return byte | (bin(byte).count("1") % 2 == 0)


def candidate_keys(known_prefix, unknown_bytes):
    for n in range(2 ** (7 * unknown_bytes)):
        tail = bytearray()
        for i in reversed(range(unknown_bytes)):
            tail.append(with_odd_parity((n >> (7 * i)) & 0x7F))
        yield n, known_prefix + bytes(tail)


def brute_force(known_prefix, unknown_bytes, pairs):
    (p1, c1), *others = pairs
    for tried, key in candidate_keys(known_prefix, unknown_bytes):
        subkeys = generate_subkeys(key)
        if des_block(p1, subkeys) != c1:
            continue
        # A 64-bit match is already near-certain. Real searches still
        # confirm against a second known block to rule out a false hit.
        if all(des_block(p, subkeys) == c for p, c in others):
            return key, tried + 1
    return None, 2 ** (7 * unknown_bytes)


if __name__ == "__main__":
    known_prefix = bytes.fromhex("133457799BBC")
    pairs = [
        (bytes.fromhex("0123456789ABCDEF"), bytes.fromhex("85E813540F0AB405")),
        (b"Now is t", bytes.fromhex("AAEA30F286270F21")),
    ]

    start = time.perf_counter()
    key, tried = brute_force(known_prefix, 2, pairs)
    elapsed = time.perf_counter() - start

    print(f"Recovered key:   {key.hex().upper()}")
    print(f"Keys tried:      {tried:,} of {2 ** 14:,}")
    rate = tried / elapsed
    print(f"Search rate:     ~{rate:,.0f} keys/second")
    years = 2 ** 56 / rate / (365.25 * 24 * 3600)
    print(f"Full 2^56 space at this rate: ~{years:,.0f} years")

Running this against the same values as the visualizer produces:

Recovered key:   133457799BBCDFF1
Keys tried:      14,329 of 16,384
Search rate:     ~6,798 keys/second
Full 2^56 space at this rate: ~335,880 years

The first two lines match the visualizer and the worked example exactly. The last two depend on your hardware, so expect different numbers. A readable, bit-list DES in pure Python is slow. Hundreds of thousands of years is the honest price of that readability.

For Fun: The Whole Attack in 3 Lines

Same spirit as this site’s other golfed bonus sections. Not for learning the algorithm from. This version packs all of DES and the whole search into three lines, with no imports beyond the standard library. It runs on its own, with no other files needed. Line 1 holds the DES tables. Line 2 rebuilds every function as a lambda. The key schedule uses accumulate, and the 16 Feistel rounds use reduce. Line 3 runs the search and prints the same report as the readable version.

import time; from itertools import accumulate; from functools import reduce; IP=[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=[40,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31,38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29,36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27,34,2,42,10,50,18,58,26,33,1,41,9,49,17,57,25]; E=[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=[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=[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=[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=[1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]; SBOX=[[[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]]]
permute=lambda b,t:[b[i-1] for i in t]; bytes_to_bits=lambda d:[(x>>(7-i))&1 for x in d for i in range(8)]; bits_to_bytes=lambda b:bytes(int(''.join(map(str,b[i:i+8])),2) for i in range(0,len(b),8)); xor=lambda a,b:[x^y for x,y in zip(a,b)]; generate_subkeys=lambda k:[permute(c+d,PC2) for c,d in list(accumulate(SHIFTS,lambda cd,sh:(cd[0][sh:]+cd[0][:sh],cd[1][sh:]+cd[1][:sh]),initial=(lambda p:(p[:28],p[28:]))(permute(bytes_to_bits(k),PC1))))[1:]]; feistel=lambda R,sk:(lambda x:permute([b for i in range(8) for b in (lambda v:[(v>>3)&1,(v>>2)&1,(v>>1)&1,v&1])(SBOX[i][((x[i*6]<<1)|x[i*6+5])][(x[i*6+1]<<3)|(x[i*6+2]<<2)|(x[i*6+3]<<1)|x[i*6+4]])],P))(xor(permute(R,E),sk)); des_block=lambda b,sk:bits_to_bytes(permute((lambda x:x[1]+x[0])(reduce(lambda LR,k:(LR[1],xor(LR[0],feistel(LR[1],k))),sk,(lambda bits:(bits[:32],bits[32:]))(permute(bytes_to_bits(b),IP)))),FP)); with_odd_parity=lambda b7:(b7<<1)|(bin(b7<<1).count('1')%2==0); candidate_keys=lambda kp,ub:((n,kp+bytes(with_odd_parity((n>>(7*i))&0x7F) for i in reversed(range(ub)))) for n in range(2**(7*ub))); brute_force=lambda kp,ub,pairs:(lambda p1,c1,o:next(((k,t+1) for t,k in candidate_keys(kp,ub) if (lambda sk:des_block(p1,sk)==c1 and all(des_block(p,sk)==c for p,c in o))(generate_subkeys(k))),(None,2**(7*ub))))(*pairs[0],pairs[1:])
kp=bytes.fromhex("133457799BBC"); pairs=[(bytes.fromhex("0123456789ABCDEF"),bytes.fromhex("85E813540F0AB405")),(b"Now is t",bytes.fromhex("AAEA30F286270F21"))]; s=time.perf_counter(); k,t=brute_force(kp,2,pairs); e=time.perf_counter()-s; print(f"Recovered key:   {k.hex().upper()}"); print(f"Keys tried:      {t:,} of {2**14:,}"); r=t/e; print(f"Search rate:     ~{r:,.0f} keys/second"); y=2**56/r/(365.25*24*3600); print(f"Full 2^56 space at this rate: ~{y:,.0f} years")

Verified to print the same Recovered key: 133457799BBCDFF1 and Keys tried: 14,329 of 16,384 as the readable version. The search rate and year estimate depend on your hardware, just as they do above.

For Speed: The Same Search, About 6 Times Faster

This version is still pure Python and still self-contained. It runs the identical search, with no parallelism and no extra libraries. It’s faster because it removes wasted work, using three tricks:

• Whole integers instead of bit lists. Every permutation (IP, FP, E, P, PC1, PC2) is precomputed as eight byte-lookup tables. Permuting a block becomes eight table lookups OR-ed together, not 64 list operations.
• Merged S-box tables. Each S-box lookup already returns its 4 output bits shifted into their final position. One lookup replaces the row and column arithmetic.
• No key schedule inside the loop. DES’s key schedule only moves bits around, so it’s linear over XOR. The subkeys of any key equal the base prefix’s subkeys, XOR-ed with a precomputed delta for each unknown byte. Two tables of 128 entries replace 16,384 full key schedules.

It also applies the initial permutation to the known plaintext once, outside the loop. The target ciphertext is compared before the final permutation, so the loop skips that step too.

import time

IP=[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=[40,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31,38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29,
    36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27,34,2,42,10,50,18,58,26,33,1,41,9,49,17,57,25]
E=[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=[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=[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=[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=[1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]
SBOX=[[[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 _build(table, in_bits):
    """Return byte-lookup tables for a bit permutation.
    Handles duplicate sources (E expansion feeds some bits to two outputs)."""
    out_bits = len(table)
    pairs = []
    for b_idx in range(in_bits // 8):
        entries = []
        for i, src in enumerate(table):
            s = src - 1
            if b_idx * 8 <= s < (b_idx + 1) * 8:
                entries.append((s - b_idx * 8, 1 << (out_bits - 1 - i)))
        tbl = [0] * 256
        for v in range(256):
            r = 0
            for bit, mask in entries:
                if (v >> (7 - bit)) & 1:
                    r |= mask
            tbl[v] = r
        pairs.append((tbl, in_bits - 8 * (b_idx + 1)))
    return pairs

IP_SH, FP_SH = _build(IP, 64), _build(FP, 64)
E_SH,  P_SH  = _build(E, 32),  _build(P, 32)
PC1_SH, PC2_SH = _build(PC1, 64), _build(PC2, 56)
SBOX_T = [[SBOX[i][((v >> 4) & 2) | (v & 1)][(v >> 1) & 0xF] << (28 - 4 * i)
           for v in range(64)] for i in range(8)]

def _perm(x, pairs):
    r = 0
    for tbl, sh in pairs:
        r |= tbl[(x >> sh) & 0xFF]
    return r

def _subkeys(key):
    p = _perm(key, PC1_SH)
    C, D = p >> 28, p & 0xFFFFFFF
    out = []
    for sh in SHIFTS:
        C = ((C << sh) | (C >> (28 - sh))) & 0xFFFFFFF
        D = ((D << sh) | (D >> (28 - sh))) & 0xFFFFFFF
        out.append(_perm((C << 28) | D, PC2_SH))
    return out

def _encrypt_block(L, R, base, ta, tb):
    """Returns the pre-FP state as a 64-bit int (R16 || L16)."""
    for i in range(16):
        sk = base[i] ^ ta[i] ^ tb[i]
        e = 0
        for tbl, sh in E_SH: e |= tbl[(R >> sh) & 0xFF]
        x = e ^ sk
        s = 0
        for j in range(8): s |= SBOX_T[j][(x >> (42 - 6 * j)) & 0x3F]
        p = 0
        for tbl, sh in P_SH: p |= tbl[(s >> sh) & 0xFF]
        L, R = R, L ^ p
    return (R << 32) | L

def _parity(b7):
    x = b7 << 1
    return x | (bin(x).count("1") % 2 == 0)

def brute_force(prefix_hex, pairs):
    # base key with the two variable bytes zeroed
    base = _subkeys(int.from_bytes(bytes.fromhex(prefix_hex), "big") << 16)

    # Linearity of the key schedule: subkeys(K) = base ^ Δ(hi) ^ Δ(lo)
    dlo = [_subkeys(1 << b) for b in range(1, 8)]   # byte 7 key bits
    dhi = [_subkeys(1 << b) for b in range(9, 16)]  # byte 6 key bits
    def table(deltas):
        t = []
        for a in range(128):
            s = [0] * 16
            for j in range(7):
                if (a >> j) & 1:
                    for i in range(16): s[i] ^= deltas[j][i]
            t.append(s)
        return t
    TB, TA = table(dlo), table(dhi)

    p1, c1 = (int.from_bytes(b, "big") for b in pairs[0])
    others = [(int.from_bytes(p, "big"), int.from_bytes(c, "big")) for p, c in pairs[1:]]

    ip = _perm(p1, IP_SH)
    L0, R0 = ip >> 32, ip & 0xFFFFFFFF
    target1 = _perm(c1, IP_SH)   # FP^-1 == IP
    extra = [((lambda x: (x >> 32, x & 0xFFFFFFFF))(_perm(p, IP_SH)), _perm(c, IP_SH))
             for p, c in others]

    for n in range(1 << 14):
        a, b = (n >> 7) & 0x7F, n & 0x7F
        ta, tb = TA[a], TB[b]
        if _encrypt_block(L0, R0, base, ta, tb) != target1:
            continue
        if all(_encrypt_block(li, ri, base, ta, tb) == tgt for (li, ri), tgt in extra):
            return bytes.fromhex(prefix_hex) + bytes([_parity(a), _parity(b)]), n + 1
    return None, 1 << 14

if __name__ == "__main__":
    kp = "133457799BBC"
    pairs = [(bytes.fromhex("0123456789ABCDEF"), bytes.fromhex("85E813540F0AB405")),
             (b"Now is t", bytes.fromhex("AAEA30F286270F21"))]
    t0 = time.perf_counter()
    key, tried = brute_force(kp, pairs)
    el = time.perf_counter() - t0
    print(f"Recovered key:   {key.hex().upper()}")
    print(f"Keys tried:      {tried:,} of {2**14:,}")
    rate = tried / el
    print(f"Search rate:     ~{rate:,.0f} keys/second")
    print(f"Full 2^56 space at this rate: ~{2**56/rate/(365.25*24*3600):,.0f} years")

Running this faster version produces the following output:

Recovered key:   133457799BBCDFF1
Keys tried:      14,329 of 16,384
Search rate:     ~39,675 keys/second
Full 2^56 space at this rate: ~57,553 years

The key and try count match the readable version exactly. Its DES was also checked against the readable version’s on 300 random key and block pairs, with every output matching. On the machine used to write this post, it averaged about 40,500 keys per second against about 6,550. That’s roughly a 6x speedup, though the exact ratio varies between machines and Python versions.

Interactive Visualizer

Try the visualizer above, and watch the candidate keys scroll past, each one failing until the match lights up. Switch to 1 unknown byte for an instant search, or 3 bytes for about two million keys. The last panel measures this page’s real search rate. It then compares that rate against Deep Crack over the full 2⁵⁶ keyspace.

Scaling Up to Deep Crack

The demo searches 2¹⁴ keys. The real keyspace is 2⁴² times bigger, about 4.4 trillion times. That gap is what the history of breaking DES is really about.

In 1998 the Electronic Frontier Foundation built Deep Crack for under $250,000. It held 1,856 custom chips, each running this same loop in parallel. Together they tested about 90 billion keys per second. It won RSA Security’s DES Challenge II-2 in 56 hours. In January 1999, Deep Crack teamed up with distributed.net’s volunteer network. The two recovered a DES key in 22 hours and 15 minutes.

Nothing in Deep Crack was mathematically clever. Its speed came from doing the dumbest possible thing massively in parallel. That’s the lesson DES teaches. A cipher can be well designed and still be broken by its parameters alone. Later FPGA machines made the same search cheaper still. That’s why DES protects nothing today.

Limitations of This Attack

This demo shortens the search on purpose. It assumes the attacker already knows 48 of the key’s 56 bits. A real attacker knows none of them. The code has no shortcut for that. It would just need 2⁴² times longer.

The attack also needs known plaintext. Without it, the attacker needs some other way to recognize a correct decryption. English text or a known file format can work. Checking that is slower and less certain than comparing one 64-bit block.

The Python code is written to be read, not to be fast. Real brute-force tools use bitsliced DES, which processes dozens of keys at once with plain logic operations. Dedicated hardware like FPGAs or ASICs goes much further. None of that changes the algorithm, only how many keys per second it tests.

Finally, brute force only works because 2⁵⁶ is small. Against 3DES or AES, the same loop is hopeless. The keyspace is simply far too large. That’s exactly why 3DES existed. The 3DES guide explains why it runs DES three times rather than twice.

FAQ

Why does the demo search 2¹⁴ keys instead of 2¹⁶?

Each unknown key byte holds 7 real key bits and 1 parity bit. DES never uses the parity bits, so they add nothing to the search. Two bytes give 14 real bits, and 2¹⁴ = 16,384 candidates.

Could the attacker get a false match?

It can, but only rarely. A wrong key matches one 64-bit block with probability 2⁻⁶⁴. Across all 2⁵⁶ keys, that’s about one false alarm per 256 full searches. Checking a second block eliminates it.

Does DES have any shortcut that halves the work?

It does, because DES has a complementation property: flipping every bit of the key and the plaintext flips every bit of the ciphertext. With the right chosen plaintexts, one encryption tests two keys. That cuts the worst case from 2⁵⁶ to 2⁵⁵.

How fast is modern brute force against DES?

Much faster than Deep Crack. FPGA clusters and cloud services have searched the full keyspace in about a day. At that point, DES offers no real protection against a motivated attacker.

Why not just use a longer DES key?

DES’s key size is fixed by its design. The key schedule only ever reads 56 bits. The fix the industry adopted was to run DES more than once with different keys, which became 3DES.

References

1. Electronic Frontier Foundation. “Cracking DES: Secrets of Encryption Research, Wiretap Politics, and Chip Design.” O’Reilly, 1998.

2. Diffie, W. and Hellman, M. “Exhaustive Cryptanalysis of the NBS Data Encryption Standard.” IEEE Computer, 10(6), 1977.

3. Matsui, M. “Linear Cryptanalysis Method for DES Cipher.” EUROCRYPT 1993.

4. Wikipedia. “EFF DES cracker.” Available at: https://en.wikipedia.org/wiki/EFF_DES_cracker