4.6.1. Classical and Implementation Attacks
💡 First Principle: The theoretical strength of a cryptographic algorithm is its ceiling — implementation decisions, protocol design, and operational practices determine whether the system actually reaches that ceiling or falls catastrophically short.
Exhaustive Key Search (Brute Force)
Brute force tries every possible key until the correct one is found. The work required is 2^n for an n-bit key. This establishes the baseline that all other attacks try to beat:
| Key Length | Keys to Try | Feasibility |
|---|---|---|
| 56-bit (DES) | 2^56 = 7.2 × 10^16 | Broken in hours with specialized hardware (EFF DES Cracker, 1998) |
| 128-bit (AES-128) | 2^128 = 3.4 × 10^38 | Infeasible with any foreseeable classical computing |
| 256-bit (AES-256) | 2^256 = 1.2 × 10^77 | Infeasible even against quantum computing (Grover reduces to 2^128) |
Dictionary attacks are a targeted variant: instead of trying every key, the attacker tries keys derived from common passwords, phrases, and leaked credential lists. This is why password-derived keys require key stretching (PBKDF2, bcrypt, Argon2) — to make each guess computationally expensive.
Birthday Attack
The birthday attack exploits the birthday paradox: in a set of n possible values, a collision (two inputs producing the same output) is expected after approximately √n attempts — far fewer than the n attempts intuition suggests.
For hash functions, this means a hash with an n-bit output can be collision-attacked in approximately 2^(n/2) operations, not 2^n:
| Hash | Output Size | Brute-Force Preimage | Birthday Collision |
|---|---|---|---|
| MD5 | 128 bits | 2^128 | 2^64 (feasible — demonstrated) |
| SHA-1 | 160 bits | 2^160 | 2^80 (feasible — SHAttered, 2017) |
| SHA-256 | 256 bits | 2^256 | 2^128 (infeasible) |
This is why MD5 (128-bit) and SHA-1 (160-bit) are deprecated for digital signatures — their collision resistance is insufficient against birthday attacks with modern compute. SHA-256 remains secure because 2^128 birthday attack operations are beyond reach.
Rainbow Tables and Salting
Rainbow tables are precomputed lookup tables mapping hash outputs back to their inputs for common passwords. An attacker who steals a database of unsalted password hashes looks up each hash in the rainbow table and recovers the password instantly — no computation needed.
Salting defeats rainbow tables by prepending a unique random value to each password before hashing. Two users with the password "Welcome1" produce entirely different hashes because their salts differ. The attacker would need a separate rainbow table for every possible salt value — computationally equivalent to brute force.
Side-Channel Attacks
Side-channel attacks extract secret information not from the algorithm's mathematical output but from its physical implementation:
| Channel | What Leaks | Example Attack |
|---|---|---|
| Timing | Execution time varies with secret data | Comparing HMAC signatures character-by-character; early exit on first mismatch reveals how many characters matched |
| Power analysis | CPU power consumption correlates with operations on secret bits | Simple/differential power analysis (SPA/DPA) extracts AES keys from smart cards |
| Electromagnetic | EM emissions from CPU correlate with processed data | TEMPEST-class attacks capturing emissions from air-gapped systems |
| Cache timing | Memory access patterns reveal secret-dependent branches | Flush+Reload and Prime+Probe extract keys from co-located VMs |
The defense against timing attacks is constant-time comparison — always comparing all bytes regardless of where the first mismatch occurs. Most languages provide constant-time comparison functions (Python: hmac.compare_digest(), Java: MessageDigest.isEqual()).
Padding Oracle Attacks
CBC-mode encryption requires plaintext to be padded to a block boundary. If the decrypting system reveals whether the padding is valid (through different error messages, response times, or HTTP status codes), an attacker can decrypt the entire ciphertext without the key — one byte at a time.
The POODLE attack against SSL 3.0 and the Lucky Thirteen attack against TLS 1.0 CBC mode exploited this class of vulnerability. This is a primary reason AES-GCM (authenticated encryption that does not use padding) replaced AES-CBC as the recommended mode.
Meet-in-the-Middle Attack
This attack targets double encryption. Naively, encrypting with DES twice (2DES) seems to double the key space from 2^56 to 2^112. The meet-in-the-middle attack encrypts the plaintext with all possible first keys and decrypts the ciphertext with all possible second keys, looking for a match in the middle — reducing the effective work to 2^57, barely better than single DES.
This is why 2DES was never adopted and 3DES uses three operations (encrypt-decrypt-encrypt with two or three independent keys) — the meet-in-the-middle attack does not scale linearly against three stages.
⚠️ Exam Trap: The birthday attack reduces collision resistance to 2^(n/2), NOT preimage resistance. Finding any two inputs that hash to the same value (collision) is much easier than finding an input that matches a specific hash value (preimage). MD5's collision vulnerability makes it unsuitable for digital signatures (where collision resistance matters), but its preimage resistance is still sufficient for file integrity checksums in non-adversarial contexts — though SHA-256 should be used regardless.
Reflection Question: An organization uses HMAC-SHA256 for API request authentication. A security review finds the HMAC comparison uses standard string equality (==). Explain the specific attack this enables, how many requests an attacker would need to forge a valid HMAC, and what the fix is.
