Brute-force Attack

security cryptography

Definition

Brute-force Attack

A brute-force attack is a cryptanalytic attack that systematically enumerates every candidate in a search space until the correct one is found.

Given a key space $\mathcal{K}$, the attacker tests each $k\in \mathcal{K}$ against the target (e.g. a ciphertext, a password hash, or an authentication oracle).

Properties

Exhaustiveness

A brute-force attack is guaranteed to succeed: the correct key or password is always in the search space.

Infeasibility

For a key of length $n$ bits, the expected number of trials is $2^{n-1}$. The attack is computationally infeasible for sufficiently large $n$.

Variants

Offline Brute-force

The attacker possesses a password hash or ciphertext and tests candidates locally. Limited only by available computing power.

Online Brute-force

The attacker submits guesses to a live authentication system. Rate-limited by network latency and account lockout policies.

Comparison

Attack	Search Space	Time	Memory
Dictionary	size of dictionary	fast	low
Brute-force	entire key/password space	slow	low
Rainbow table	precomputed chains	very fast (online phase)	high

Defence

Key Length

Increasing the key length $n$ exponentially expands the search space $|\mathcal{K}|=2^n$.

Rate Limiting

Online brute-force is mitigated by lockout thresholds, CAPTCHAs, and exponential backoff.

Key Stretching

Cascade hashing — slow hash functions — reduces the number of candidates an attacker can test per unit time.