How Brute Force Attacks Work

A brute force attack on a cipher tries every possible key until the correct one is found. For a key of n bits, there are 2^n possible keys. With a 3-bit key there are only 8 possibilities; with a 56-bit key there are over 72 quadrillion. The fundamental defence against brute force is choosing keys large enough that exhaustive search is computationally infeasible within any meaningful time frame.

DES (Data Encryption Standard) uses a 56-bit key, giving a keyspace of approximately 7.2 * 10^16. In 1977 this seemed enormous. By 1998 the EFF's Deep Crack machine broke DES in 56 hours for $250,000. By 2006 a dedicated cluster could break DES in less than 9 days for under $10,000. The lesson was clear: 56 bits was no longer sufficient security against a motivated adversary.

AES-128 uses 128-bit keys, giving 2^128 possible keys, approximately 3.4 * 10^38. If every atom in the observable universe were a computer performing a billion key tests per second since the Big Bang, the search would not be close to complete. Even with exponentially faster future hardware, 128-bit keys are expected to remain secure against classical brute force for the foreseeable future.

Online brute force attacks target live systems by repeatedly sending authentication requests. They are limited by network latency, server response time, and rate limiting, making them slow. Offline brute force attacks work against stolen data such as a database of password hashes. With hashes in hand, an attacker can test billions of candidates per second using local hardware with no network constraints.

Modern GPUs contain thousands of parallel processing cores optimised for floating-point arithmetic. Hashcat, the leading GPU hash cracking tool, can test over 100 billion MD5 hashes per second on a single high-end GPU. A rig with eight GPUs can test over 800 billion candidates per second. This makes poorly chosen passwords and weak hash functions vulnerable to rapid offline cracking.

Application-Specific Integrated Circuits are chips designed exclusively for one computation. Bitcoin miners use ASICs that compute SHA-256 hashes at tens of terahashes per second, far faster than any GPU. While Bitcoin ASICs compute a different operation than password cracking, the principle applies: purpose-built hardware provides orders of magnitude speedup over general-purpose hardware for specific cryptographic computations.

Moore's Law observed that transistor density roughly doubles every two years, historically bringing equivalent speedup in computing power. A key length considered secure today must remain secure across decades of future hardware improvements. Security recommendations therefore include significant safety margins. AES-128 would need 2^64 speedup in computing to become vulnerable to classical brute force, which is far beyond any plausible Moore's Law extrapolation.

NIST SP 800-57 specifies security strengths for cryptographic algorithms. 112-bit security is the current minimum for new systems. 128-bit security is recommended for long-term protection. 256-bit symmetric keys provide a safety margin beyond currently foreseeable classical computing threats. NIST recommends against 80-bit and below security levels, which are considered inadequate for any new application.

Grover's quantum search algorithm provides a quadratic speedup for unstructured search, meaning it can search a keyspace of N items in roughly sqrt(N) steps instead of N. For AES-128 this effectively reduces security to 64 bits against a quantum adversary. For AES-256 the effective security against Grover's algorithm is 128 bits, which is why 256-bit symmetric keys are recommended for post-quantum security.

To maintain 128-bit security against a quantum computer running Grover's algorithm, symmetric keys must be at least 256 bits. AES-256 is already at this size and is considered quantum-safe for symmetric encryption. For context, doubling the key length from 128 to 256 bits does not double computation for the legitimate user (it adds only a few more AES rounds) but requires squaring the attacker's quantum resources.

Security teams use brute force tools in authorised password audits to identify weak credentials before attackers do. Hashcat and John the Ripper are run against exported password hash databases to determine what fraction of passwords could be cracked. Audit results drive password policy improvements: minimum length requirements, complexity rules, and adoption of modern password hashing algorithms like bcrypt or Argon2.

How does Grover's quantum algorithm affect the effective security of AES-128?

Brute force tests every possible key; security requires keyspaces too large to enumerate in practice. DES at 56 bits was broken in 1998. AES-128 at 2^128 keys is infeasible for classical computers. GPU clusters crack hashes at hundreds of billions per second offline. Grover's quantum algorithm halves bit security, requiring 256-bit keys for 128-bit post-quantum security. NIST recommends 128-bit minimum security for new systems.