Brute-force

A brute-force attack consists in enumerating every possible key of a cipher and testing each one until you obtain a plausible decryption. Conceptually it’s the simplest attack: no clever insight required, just patience and machine time. And conceptually it’s the most powerful: if the key exists, you’ll eventually hit it. No blind spot, no hypothesis to validate.

The whole question is how long it takes.

Cipher scale against brute-force

Cipher	Key space	Brute-force time
Caesar	25 shifts	Human: 5 min
ROT	25 shifts	Human: 5 min (same as Caesar)
Affine	12 × 26 = 312 (a, b) pairs	Human: 30 min
Monoalphabetic substitution	26! ≈ 4 × 10²⁶	Pure brute-force infeasible, but frequency analysis cracks it in minutes
Vigenère, 5-letter key	26⁵ ≈ 12 million	Computer: trivial
Vigenère, 12-letter key	26¹² ≈ 9 × 10¹⁶	Same league as DES
DES (1977)	2⁵⁶ ≈ 7 × 10¹⁶	EFF Deep Crack 1998: 56 hours
AES-128	2¹²⁸	Every computer on Earth: billions of years
AES-256	2²⁵⁶	More than atoms in the visible universe
One-time pad (key as long as message)	As large as the message	Even the right key is indistinguishable from a fake

The table illustrates the golden rule: it’s the logarithm of the key space (in bits) that determines resistance to brute-force. Each bit added to the key doubles the attack cost. Going from 56 bits (DES) to 64 bits (naive double DES) no longer suffices today; going to 128 (AES-128) leaves the realm of the feasible entirely.

The one-time pad twist

The one-time pad deserves a special mention. Its resistance to brute-force is infinite — not because the key space is bigger than AES, but because every key produces a plausible decryption. With key K1, your ciphertext XY9R gives HELLO; with another key K2, the same ciphertext gives WORLD; with another, ATTACK; with another, RETREAT. No way to distinguish the “real” key from a bogus one. That’s what Shannon proved in 1949 under the name perfect secrecy.

Classical optimizations

Pure brute-force is rarely run as-is. You speed it up:

• Plausibility ordering: try statistically likely keys first (dictionary words for Vigenère, birthdays for 4-digit codes, top common passwords — 123456, password, qwerty).
• Parallelization: a GPU runs billions of tests per second. A rented GPU farm (cloud) cuts the time further.
• Precomputed tables (rainbow tables): store hashes of millions of passwords ahead of time; the attack becomes a lookup.
• Pruning: on Vigenère, try short keys (3-7 letters) first — they cover the overwhelming majority of real cases.

Defenses: KDF, salt, rate limiting

For live systems (passwords, authentication), you deliberately slow brute-force down:

• KDF (Key Derivation Function): hash the password with Argon2, bcrypt or scrypt — functions designed to be slow and memory-heavy. A legitimate verification takes 100 ms; an attacker testing a billion candidates takes years.
• Salt: add random unique bytes to the password before hashing. An attacker can no longer precompute a universal rainbow table; they must redo the work for each user.
• Rate limiting: 5 failed attempts and the account locks temporarily. Online brute-force becomes impossible. (Offline against a leaked database, salt + KDF remain the last barrier.)

When brute-force actually wins

Two real-world examples where brute-force isn’t just theoretical:

• Bitcoin mining is, deliberately, a giant brute-force exercise. Miners try billions of nonces per second, hoping to land on one whose SHA-256 hash starts with enough zeros. The “proof of work” that secures the network is precisely the impossibility of avoiding the brute-force step.
• WPA2 Wi-Fi passwords: once an attacker captures the handshake of a connection (a few packets), they can run an offline dictionary-plus-brute-force attack against it. Tools like hashcat on a GPU farm test millions of candidates per second. A weak passphrase falls in hours.

Brute-force as upper bound

Note: brute-force is always lurking in the background as the upper bound on crackability. A “real” cryptanalytic attack (differential analysis, side-channel) is only worth pursuing if it’s faster than brute-force. When AES-256 is announced as having a theoretical attack in 2²⁵⁴ operations, that’s faster than 2²⁵⁶ — hence a valid attack — even though it remains entirely infeasible in practice.

Key takeaways:

• Brute-force = try every key. Always possible, not always reasonable.
• The logarithm of the key space is what matters. Each bit doubles the cost.
• For live systems, slowing brute-force down matters as much as choosing a good algorithm: KDF (Argon2, bcrypt) + salt + rate limiting.
• Brute-force is the upper bound: any “real” cryptanalytic attack is measured against it.