How does an exhaustive key search (brute force) work, and what determines its computational cost?

Question

Accepted Answer

An exhaustive key search is a known-plaintext attack that tries every possible key until the correct one is found — it costs $k$ operations where $k = 2^n$ for an n-bit key.

* Time to search the whole key space on a single 10⁶ ops/s chip — every extra bit doubles the effort. *
How it works:

Obtain at least one known plaintext-ciphertext pair $(M, C)$
For each possible key $K_i$: check if $E(M, K_i) = C$ or $D(C, K_i) = M$
If match found → key discovered

Requirements:

Key space size $k$ must equal $2^n$ (all keys equally likely, maximum entropy)
On average, you find the key after testing k/2 keys
Building a complete lookup table requires exactly k operations

Concrete brute-force times (1 million operations/sec per chip):

Key Size
Key Space
1 Chip
1,000 Chips
10 Million Chips

32 bit
$4.3 	imes 10^9$
1h 12min
4.3 sec
—

56 bit
$7.2 	imes 10^{16}$
2,304 years
2.3 years
~2 hours

64 bit
$1.8 	imes 10^{19}$
600,000 years
581 years
22 days

128 bit
$3.4 	imes 10^{38}$
$10^{25}$ years
$10^{22}$ years
$10^{18}$ years

Key takeaway: Each additional bit doubles the brute-force effort. This exponential growth is why 128-bit and 256-bit keys are considered secure against brute force for the foreseeable future.
Go deeper:

Brute-force attack (Wikipedia) — exhaustive key search and its theoretical limits.
 Key size (Wikipedia) — how many bits actually buy how much security.

Key Size	Key Space	1 Chip	1,000 Chips	10 Million Chips
32 bit	$4.3 \times 10^9$	1h 12min	4.3 sec	—
56 bit	$7.2 \times 10^{16}$	2,304 years	2.3 years	~2 hours
64 bit	$1.8 \times 10^{19}$	600,000 years	581 years	22 days
128 bit	$3.4 \times 10^{38}$	$10^{25}$ years	$10^{22}$ years	$10^{18}$ years