Is a block cipher "broken" as soon as an attack exists that is faster than brute force?
No. Practically every cipher has some attack faster than brute force; what counts is the effort of the best attack, which should currently be at least $2^{112}$.
Why "faster than brute force" is the normal case:
- There is (presumably) no symmetric algorithm that cannot be attacked faster than exhaustive key search. Time-memory trade-offs (TMTO) always beat brute force, and so do differential and linear cryptanalysis.
- For asymmetric schemes it is true by design: 3072-bit RSA, DH or Elgamal keys and 256–512-bit elliptic-curve keys could never be brute-forced, yet they are attacked through the underlying math problem.
Meet-in-the-middle attacks in numbers:
| Algorithm | Brute force | Best attack | Note |
|---|---|---|---|
| Double DES | $2^{112}$ | $\approx 2^{57}$ | Useless |
| 3DES, 2 keys | $2^{112}$ | $\approx 2^{60}$ | Too weak |
| 3DES, 3 keys | $2^{168}$ | $\approx 2^{112}$ | Still allowed until 2030 |
| AES-128 | $2^{128}$ | $\approx 2^{126}$ | Biclique attack |
| AES-192 | $2^{192}$ | $\approx 2^{189}$ | Biclique attack |
| AES-256 | $2^{256}$ | $\approx 2^{254}$ | Biclique attack |
| AES-256 | $2^{256}$ | $\approx 2^{224}$ | Could perhaps be avoided with more rounds |
The biclique attack is a meet-in-the-middle attack. Formally it makes AES "faster than brute force", but it saves only about 2 bits, so AES remains perfectly secure. 3-key 3DES drops by 56 bits and still meets the $2^{112}$ bar; 2-key 3DES falls far below it.
Exam pattern: judge a cipher by the work factor of its best known attack compared with the required security level, not by whether any shortcut exists.
Go deeper:
Biclique attack (Wikipedia) — the meet-in-the-middle variant behind the 2^126 figure for AES-128.- Shor's algorithm (Wikipedia) — the polynomial-time break of RSA, DH and ECC.
- Post-quantum cryptography (Wikipedia) — the algorithms being built to survive Shor.