The Brute-Force Baseline

Change the key length and the attack speed. See the difference between an attack faster than brute force and an attack someone can really run.

Key lengthAttack costdemo

Objectives

Compute the expected work of a brute-force search.
Explain why one more key bit doubles the attacker's time.
Compare the effect of faster hardware against a longer key.
Distinguish a certificational break from a practical break.
Identify the four numbers that make a published attack readable.

50%

Move the key size and the attack rate, and watch which one matters.

A k-bit key has 2^k possible values, and brute force tries them until one works. On average it finds the key after half the key space, so the work is 2 to the power of one less than the key length.

Key size in bits

128

Keys per second, as a power of ten

What those rates look like in hardware

Reference attack rates as orders of magnitude, with the time each one needs against the selected key size.
Hardware	Keys per second	Against 128 bits
One CPU core with AES instructions a few GB per second of AES, so about 10^8 blocks: an estimate	10^8	5e+22 years
One high-end GPU thousands of cores on one card: an estimate	10^10	5e+20 years
Deep Crack with distributed.net, 1999 measured: about 2.5 x 10^11 keys per second against DES	10^11	5e+19 years
A large GPU cluster the rate these slides assume, chosen to be generous	10^12	5e+18 years
An exascale supercomputer 10^18 operations per second, about 10^3 operations per key trial	10^15	5e+15 years
The Bitcoin mining network measured, 2025: SHA-256 on single-purpose hardware, not AES keys	10^21	5e+9 years

Two of these rows are measured, the 1999 DES search and the 2025 Bitcoin hash rate. The rest are estimates, and they count different operations on different hardware, so read them as scale rather than as benchmarks. Even the largest, against a 128-bit key, is not close.

Expected search

work

2^127 keys

at 10^12 keys per second

5e+18 years

One more key bit doubles the time. A million times faster hardware gives about twenty more bits, so a longer key beats faster hardware.

Sizes in use

Key size against expected search work and expected time at the selected attack rate.
Key size	Expected search	Time
56 bits	2^55 keys	10.0 hours
112 bits	2^111 keys	8e+13 years
128 bits	2^127 keys	5e+18 years
168 bits	2^167 keys	6e+30 years
256 bits	2^255 keys	2e+57 years

56 bits is DES, and it did not stay theoretical. The EFF built Deep Crack in 1998 and recovered a DES key in about 56 hours. With distributed.net in January 1999 the pair reached roughly 2.5 x 10^11 keys per second and found a key in 22 hours, after about a quarter of the space.

A cryptanalytic attack is interesting if it is significantly cheaper than brute force. That says something about the design, and it does not follow that the cipher can be read.

Interesting is not the same as practical

an interesting attack

One that costs significantly less than the expected brute-force search. It is a statement about the design, and it is how cryptanalysis reports progress. An attack on a 128-bit cipher costing 2^126 is interesting, and it still needs 3e+18 years at the rate set above.

a practical attack

One somebody can actually run, with the data, the memory and the time it asks for. This is the one that changes what you deploy.

Read a headline attack for four numbers before believing anything about it: the number of rounds it reaches, the attack model it assumes, its time cost, and how much chosen data it needs. A small security margin does not mean the cipher is broken, it means there is less reserve against stronger future attacks.

step 1/2

CPE 645 / CS 685

The Brute-Force Baseline

The S-Box

One Round of DES