What is a table lookup attack, and how does it trade time for storage compared to exhaustive key search?
A table lookup precomputes all encryptions of a chosen plaintext under every possible key, stores them in a database, then looks up the answer instantly — it's a chosen-plaintext attack that trades computation time for storage space.
Preparation phase (offline):
- Choose a plaintext (e.g., "ATTACK")
- Encrypt it under every possible key → $k$ encryptions
- Store all $(key, ciphertext)$ pairs in a database → $k$ entries
Attack phase (online):
- Feed the chosen plaintext into the target encryption device
- Get back the ciphertext
- Look it up in the database → instant key recovery
Storage requirements:
| Key Size | Entries | Storage Needed |
|---|---|---|
| 32 bit | $4.3 \times 10^9$ | ~6 CDs |
| 56 bit | $7.2 \times 10^{16}$ | 50,000 hard drives |
| 64 bit | $1.8 \times 10^{19}$ | $1.5 \times 10^7$ hard drives |
| 128 bit | $3.4 \times 10^{38}$ | $5.4 \times 10^{26}$ hard drives |
For 128 bits in perspective: The table would require about 2 million times more data than all data exchanged globally in 2025 (~175 ZettaBytes). If the entire Earth were made of silicon storage, it could hold a table for about 157-bit keys.
Tip: Table lookup is the exact opposite of key search: key search uses zero storage but maximum time; table lookup uses maximum storage but zero time (during the attack).
Go deeper:
Brute-force attack (Wikipedia) — precomputation as the storage-for-time extreme of brute force.