How Cryptographers Measure Impossible: Security Levels, Proofs, and Real Failures
Before You Read
You should already know: what a symmetric cipher and a public-key (asymmetric) scheme are, roughly what XOR does to bits, and that brute force means trying every possible key. No math background beyond logarithms is assumed, log2() gets explained inline.
By the end you’ll understand why “secure” is not one property but a spectrum with a name for each rung: informational security (unbreakable, period), computational security (unbreakable in any practical amount of time), bit security (a number that lets you compare wildly different ciphers on one scale), and the gap between provable security (backed by a math reduction) and heuristic security (backed by years of failed attacks). You’ll also see why key generation is trivial for symmetric keys and a small research project for asymmetric ones, and why two of the worst cryptographic disasters in the last twenty years had nothing to do with any cipher being “broken” in the mathematical sense.
Informational Security: Impossible Even With Infinite Time
Most of the time when people say a cipher is “secure,” they mean something practical: nobody can afford to break it. But there’s a stricter, older notion that has nothing to do with affordability. A cipher has informational security if the ciphertext gives an attacker literally zero information about the plaintext, even if that attacker has infinite time and infinite compute. Not “too slow to try everything,” but “trying everything doesn’t help, because every possible answer looks equally correct.”
The one-time pad is the classic example. You take a message, generate a truly random key exactly as long as the message, and XOR them together. Because the key is random and never reused, every possible plaintext of that length is a valid decryption under some key. There’s no mathematical test, no shortcut, no amount of extra computation that lets you rank one candidate plaintext above another. This is a binary property, a cipher either has it or it doesn’t, there’s no “80% informationally secure.” That rigidity is exactly why it’s mostly a theoretical benchmark rather than something you build products around: it demands a key as long as the message, used exactly once, distributed as securely as the message itself would need to be. In practice, this makes the one-time pad an object lesson, not a product.
Here’s the mechanism laid bare with a 3-bit ciphertext. Fix the ciphertext at 101 and XOR it against every one of the 8 possible 3-bit keys:
# Fixed 3-bit ciphertext, try every possible 3-bit key.
ciphertext = 0b101
print("key | plaintext")
for key in range(8):
plaintext = ciphertext ^ key
print(f"{key:03b} | {plaintext:03b}")Running it produces all 8 possible plaintexts, one per key:
key | plaintext
000 | 101
001 | 100
010 | 111
011 | 110
100 | 001
101 | 000
110 | 011
111 | 010Every 3-bit string from 000 to 111 shows up exactly once. An attacker staring at 101 with unlimited time to spend still has no way to prefer one row over another, there’s no “check” built into the math that flags a correct key. Scale that idea up to a real message and a real random key the same length, and the same logic holds no matter how long you let the attacker think about it.
flowchart LR
subgraph Informational["Informational security (OTP)"]
A["Ciphertext"] --> B["Try every key"]
B --> C["All plaintexts equally valid<br/>no way to tell which is real"]
end
subgraph Computational["Computational security (typical cipher)"]
D["Ciphertext"] --> E["Try every key"]
E --> F["Only one key decrypts<br/>to a sensible plaintext"]
F --> G["Just needs enough<br/>time/hardware to find it"]
endComputational Security: Impossible in Practice
Almost nothing you use day to day is informationally secure, and that’s fine, because informational security isn’t the bar that matters for practical systems. What matters is computational security: breaking the cipher is theoretically possible, but it costs so much time, hardware, or money that no realistic adversary can pull it off.
The formal version of this idea is written as a pair, (t, ε). A scheme is (t, ε)-secure if any attacker limited to t total operations succeeds with probability at most ε. It’s worth sitting with what that actually says: ε is a ceiling on the odds of success, not a promise that spending exactly t operations guarantees a break. For a well-designed n-bit key cipher with no shortcut better than brute force, ε tracks how much of the keyspace an attacker’s budget lets them search. Double the operations you can afford and you double your odds of hitting the right key, and that scaling continues linearly until your budget reaches 2^n, at which point you’ve searched everything and success is certain.
To make “impossible in practice” concrete, imagine a toy cipher, call it BoltCipher-48, using a 48-bit key. Suppose an attacker has a beefy GPU cluster checking 5 billion keys a second. How long does exhausting the keyspace take at 48 bits versus at other sizes?
# Brute force time for various keyspace sizes at a fixed attack rate.
rate = 5e9 # keys checked per second (beefy GPU cluster)
seconds_per_year = 365 * 24 * 3600
sizes = [32, 48, 64, 96]
print("bits | keyspace | seconds | years")
for bits in sizes:
keyspace = 2 ** bits
seconds = keyspace / rate
years = seconds / seconds_per_year
print(f"{bits:4d} | 2^{bits:<10d}| {seconds:14.2e} | {years:14.2e}")bits | keyspace | seconds | years
32 | 2^32 | 8.59e-01 | 2.72e-08
48 | 2^48 | 5.63e+04 | 1.79e-03
64 | 2^64 | 3.69e+09 | 1.17e+02
96 | 2^96 | 1.58e+19 | 5.02e+11A 32-bit key falls in under a second, a coffee break of an attack. BoltCipher-48’s 48-bit key lasts about 56,300 seconds, roughly 15.6 hours: annoying to wait for, but well within reach of anyone renting cloud GPUs for a weekend, which is exactly why 48 bits is considered a broken key size today. Push the same cipher’s key to 96 bits and the picture flips completely: about 5.02 x 10^11 years to exhaust, vastly longer than the age of the universe. Same attack, same hardware, same brute-force strategy, the only thing that changed is the exponent, and that’s the entire difference between “practically breakable” and “practically impossible.”
Measuring Security in Bits
Comparing ciphers by key length alone gets misleading fast, because key length and actual difficulty of breaking a cipher aren’t always the same number. The standard fix is to describe security in bits: if the best known attack against a scheme needs about 2^k operations, that scheme has k-bit security, found by taking log2 of the attack’s operation count.
An n-bit key can never give more than n-bit security, brute force over the full keyspace always eventually works, so n bits is a hard ceiling. But the real security level can land below that ceiling for two different reasons. First, a smarter-than-brute-force attack might exist, one that needs meaningfully fewer than 2^n operations, which knocks the effective security down even though the key is still n bits long. Second, and this shows up constantly in public-key cryptography, the underlying math problem might just be easier to solve than searching the full key space would suggest. RSA is the textbook case: a 3072-bit RSA key is estimated at roughly 128-bit security, not 3072-bit security, because the best known way to break RSA is to factor the modulus, and factoring a number is far more tractable than trying every possible 3072-bit string.
Picture a second toy cipher, BreezeCipher-96, with a 96-bit key that has a designed-in flaw: a meet-in-the-middle attack cuts the real cost to about 2^64 operations. Its key size says 96 bits, its actual security level says 64. That’s the same mismatch that shows up in RSA-3072, just invented for illustration instead of buried in number theory. Here’s log2 turning a handful of raw operation counts, including that 2^64 figure, into bit-security numbers directly:
import math
cases = [
("8,000,000 operations", 8_000_000),
("5e9 ops/sec for 1 year", 5e9 * 365 * 24 * 3600),
("2^64 operations", 2 ** 64),
("2^96 operations", 2 ** 96),
]
print("scenario | operations | bit-security")
for label, ops in cases:
bits = math.log2(ops)
print(f"{label:29s} | {ops:14.3e} | {bits:6.2f}")scenario | operations | bit-security
8,000,000 operations | 8.000e+06 | 22.93
5e9 ops/sec for 1 year | 1.577e+17 | 57.13
2^64 operations | 1.845e+19 | 64.00
2^96 operations | 7.923e+28 | 96.00Notice the middle row: a full year of a 5-billion-keys-per-second attacker only buys about 57 bits of effective security removed, nowhere near enough to touch a 96-bit key on its own. That gap between raw operation counts and the bit-security number they translate to is exactly why security levels, not key lengths, are the unit cryptographers actually compare.
flowchart TD
A["n-bit key"] --> B{"Best known attack?"}
B -->|"only brute force"| C["security level = n bits"]
B -->|"smarter attack exists<br/>e.g. meet-in-the-middle"| D["security level < n bits<br/>(BreezeCipher-96: 96-bit key, 64-bit security)"]
B -->|"structured problem<br/>e.g. factoring"| E["security level << n bits<br/>(RSA-3072: 3072-bit key, ~128-bit security)"]Full Attack Cost: Beyond Raw Operation Counts
Bit security is a clean single number, but it only counts operations. Real attackers have more levers than that: whether the work can be split across many machines at once (parallelism), how expensive it is to touch memory versus just compute (memory), whether a one-time expensive setup can be reused forever after (precomputation), and how many separate targets they’re willing to settle for hitting just one of (number of targets). Each of these can shrink the effective cost of an attack well below what the raw bit-security number implies.
Parallelism
An attack made of independent guesses, where trying key #5000 doesn’t depend on the result of trying key #4999, splits cleanly across N processors for roughly an N-times speedup. An attack built as a sequential chain, where each step needs the previous step’s output before it can run, gets no benefit from extra cores no matter how many you add: you can’t compute step two before step one finishes, full stop.
Picture “ChainKDF,” a key-derivation function that hashes its input 2^32 times in a row, each hash feeding the next. Compare it to a brute-force search over a 2^32 keyspace, where each guess is independent of every other guess. Hand both problems 1,024 GPUs. The brute-force search finishes roughly 1,024 times faster, because you can split the keyspace 1,024 ways and run them all at once. ChainKDF finishes in exactly the same time it would have taken on a single GPU, because step 2^31 still can’t start before step 2^31 minus 1 is done, and no amount of extra silicon changes that dependency.
Memory and Precomputation
Not all operations cost the same in wall-clock time, and that’s mostly about where the data lives. A register read is the baseline, roughly 1 cycle. L1 cache costs around 4 cycles, L2 around 12, L3 around 40, and a trip out to main DRAM costs around 200 cycles, two orders of magnitude slower than the register case. An attack’s real speed depends heavily on which of these tiers it actually hits, not just how many logical steps it has on paper.
Precomputation changes the economics further by letting an attacker pay an expensive cost exactly once. Imagine attacking a weak, unsalted 32-bit password-hashing scheme. An attacker spends three days building a 500 GB precomputed hash-chain table, an expensive “offline” phase done a single time. After that, cracking any newly captured hash from that same scheme takes under a second, an “online” phase that’s nearly free because all the hard work was already paid for up front. The scheme’s nominal strength never changed, what changed is that the cost got moved from “per attack” to “once, ever.”
Number of Targets
Brute-forcing one specific n-bit key takes about 2^n attempts on average. But an attacker rarely cares about one specific key, they usually just want to recover any one of many. If an attacker holds M independently-keyed targets and is happy to crack any single one of them, the expected number of attempts drops to about 2^n / M, because every guess has M chances to match instead of just one.
Concretely: an attacker holds 8,192 (2^13) intercepted messages, each under its own 64-bit key. Cracking one named message still costs about 2^64 attempts. But cracking at least one of the 8,192 costs only about 2^51 on average, a real, substantial reduction that comes purely from having more targets to aim at, no smarter math required.
Putting It Together: Effective Attack Cost
Stack all four factors onto a single scenario and watch a security level dissolve. Start from a 96-bit baseline and apply, one at a time: 2^16 parallel cores, a precomputed table that cuts online cost by 2^20, willingness to accept any one of 2^16 targets, and roughly 20 years of Moore’s-law-style efficiency gains (about 1 bit lost every 2 years).
# Cumulative erosion of effective bit-security from a 96-bit baseline.
baseline = 96
parallel_loss = 16 # 2^16 parallel cores
precompute_loss = 20 # precomputed table cuts online cost by 2^20
targets_loss = 16 # willing to hit any 1 of 2^16 targets
time_loss = 10 # 20 years at ~1 bit lost every 2 years
scenarios = []
running = baseline
scenarios.append(("baseline", running))
running -= parallel_loss
scenarios.append(("+parallelism", running))
running -= precompute_loss
scenarios.append(("+precomputation", running))
running -= targets_loss
scenarios.append(("+targets", running))
running -= time_loss
scenarios.append(("+time (20yr)", running))
for label, bits in scenarios:
print(f"{label:18s}: {bits} bits")baseline : 96 bits
+parallelism : 80 bits
+precomputation : 60 bits
+targets : 44 bits
+time (20yr) : 34 bitsBy the time every factor is applied, a scheme that looked like it offered 96-bit security on paper has an effective attack cost closer to 34 bits, well within brute-force range of a single modern machine. None of the math changed, the cipher is exactly as strong as it always was, what changed is how generously we’re allowed to model the attacker.
Choosing a Security Level
Given all that erosion, how do real systems pick a number and call it done? In practice, security targets cluster at two levels. 128 bits covers everyday use: encrypted traffic, stored secrets, anything you want safe for the foreseeable future against realistic attackers. 256 bits gets chosen when designers want headroom, either against decades of future hardware and algorithmic improvement, or against quantum algorithms that can roughly halve the effective security margin of some schemes.
There’s a legitimate exception to treating 128 bits as a floor: short-lived secrets. A one-time unlock code that’s worthless sixty seconds after issue can safely use 64 or 80 bits, because there’s no realistic window in which an attacker could brute-force it before it expires anyway. Garage-door remote codes and one-time SMS codes both lean on exactly this logic, their security lives in seconds, not years, so the bit count that would look alarmingly weak for a long-term key is perfectly fine for them.
On the other end, past 256 bits, extra key length stops buying anything. To feel the scale here: counting to 2^64 is comparable to counting every grain of sand on every beach on Earth, an absurd but not truly incomprehensible number. Counting to 2^80 is closer to counting every star in every galaxy in the observable universe. 2^128 dwarfs both again: it’s in the range of the number of atoms in a large mountain range. No plausible stack of faster hardware, cleverer algorithms, or quantum speedups closes a gap that size, which is why security levels beyond 256 bits are effectively wasted bits rather than genuine extra defense.
Provable Security: Proofs, Reductions, and Their Limits
Some cryptographic schemes come with something stronger than “nobody’s broken it yet,” they come with a proof. But it’s worth being precise about what that proof actually claims, because it’s easy to overstate. A security proof works by reduction: you show that any hypothetical attacker capable of breaking the scheme could be repurposed into an algorithm that solves some other problem everyone already believes is hard. So breaking the scheme can never be easier than solving that other problem, whatever it is. That’s a relative guarantee, not an absolute one.
There are two common styles of reduction. One anchors to a math problem directly: RSA’s proof ties recovering the private key to factoring the modulus n = pq. If someone found a way to break RSA without factoring, that would itself be a factoring breakthrough, which nobody has produced despite decades of trying. The other style anchors to a different cryptographic primitive instead of raw math: assume some single permutation or block cipher is unbreakable, then show that any attack on a hash function or stream cipher built on top of it would double as an attack on that inner primitive. This doesn’t create trust from nothing, it transfers trust from one component to another.
Either way, the guarantee is conditional. It holds only if the underlying hard problem stays hard, and only against the specific attack model the proof actually covers. History has real cases where reductions turned out to have flaws, or covered too narrow a model, or where the math held perfectly while an implementation bug undermined everything the proof never addressed.
SIKE is the sharpest recent example. Supersingular Isogeny Key Encapsulation was a post-quantum key-exchange candidate that survived years of public cryptanalysis and made it to the final round of NIST’s post-quantum standardization process, about as strong a vote of confidence as cryptography hands out. In 2022, a classical (non-quantum) mathematical attack broke it completely, recovering the secret key on an ordinary laptop in about an hour. The underlying hard problem it relied on simply turned out to be far more tractable than the field had believed, and no amount of prior scrutiny had caught that.
Paul Kocher’s 1996 timing attack shows the other failure mode. He recovered RSA and DSA private keys by measuring tiny differences in how long decryption operations took to run, a side channel that has nothing to do with factoring. The math behind RSA’s proof was untouched, it said nothing about timing at all, which is precisely the point: the proof only covers the attack model it was written for, and implementation details live outside that model entirely.
flowchart LR
A["Attacker breaks<br/>the scheme"] --> B["Reduction converts<br/>this into an algorithm"]
B --> C["Algorithm solves a<br/>believed-hard problem<br/>(factoring, or a primitive)"]
C --> D["Nobody has solved<br/>that problem before"]
D -.->|"contradiction"| A
E["Proof covers:<br/>this attack model only"] -.->|"doesn't cover"| F["Timing side channels,<br/>implementation bugs,<br/>a wrong hardness assumption"]Heuristic Security: Trust Earned Through Failed Attacks
Not every widely trusted cipher has a proof like RSA’s. AES, along with most symmetric ciphers, has no reduction tying its strength to some other hard problem. There isn’t an “other problem” to point to, the internal mixing rounds of AES aren’t standing in for anything else, they’re the actual object under attack.
So where does trust in AES come from? Years of public cryptanalysis. Researchers repeatedly attack reduced-round versions of the cipher, versions run for fewer of the repeated internal mixing steps (“rounds”) than the real thing uses. The gap between the total number of rounds the full cipher runs and the largest number of rounds anyone has managed to break meaningfully faster than brute force is called the security margin. A large, stable margin that’s held up under years of sustained, well-funded attack effort becomes the practical stand-in for a mathematical proof, earned rather than derived.
Picture a generic cipher, FooBlock-16, running 16 total rounds. Suppose years of published cryptanalysis have only managed to break the first 7 rounds significantly faster than brute force. That’s a security margin of 9 rounds, more than half the cipher’s total rounds have never been dented. The field would consider the full 16-round FooBlock-16 solidly trustworthy in practice, not because anyone proved it can’t be broken, but because a lot of very motivated, very qualified people have tried and consistently fallen short.
Generating Strong Keys: Symmetric vs Asymmetric
A cipher’s security level is only as good as the key actually protecting it, which raises a practical question: how do you generate one? The answer looks completely different depending on whether you’re generating a symmetric key or an asymmetric key pair.
A symmetric key is just a random bit string of the right length. Any one of the 2^n possible n-bit strings is an equally valid AES key or equally valid MAC key, there’s no structure to satisfy beyond “the right number of unpredictable bits.” That means a cryptographic PRNG’s raw output can be used directly as the key, no further processing, no validity checking, nothing to reject.
An asymmetric key pair is a different kind of object entirely. An RSA modulus has to be the product of two large primes. An elliptic-curve private key has to be a scalar that generates a valid point on the curve. You can’t just hand over raw random bits and call it a key, because almost no random bit string happens to satisfy that structure. Instead, the random bits get used as a seed that feeds into a key-generation algorithm, one that searches for and constructs an object with the required mathematical properties. That search is exactly why asymmetric key generation is slower and more involved than symmetric key generation.
Generating a symmetric key
There’s genuinely nothing more to it than asking a CSPRNG for n bits and using them as-is. Here it is generating a 128-bit key twice, back to back, with secrets.token_bytes:
import secrets
key1 = secrets.token_bytes(16)
key2 = secrets.token_bytes(16)
print("key 1:", key1.hex())
print("key 2:", key2.hex())key 1: 41442bda4453a61679701ae0e62c9cad
key 2: bcc28ff1232e04fb05c4e6984078822eTwo calls, two completely independent, unpredictable 128-bit values. No search, no rejection, no waiting.
Attempting to build an asymmetric key from scratch
Try the same “just grab random bits” approach for RSA and it falls apart immediately: a random n-bit integer is essentially never prime. Generating an RSA modulus instead means repeatedly generating random odd numbers of the target bit length and testing each one for primality, over and over, until one passes, then doing the whole thing again for a second prime. That loop has no equivalent on the symmetric side at all.
The following generates two 512-bit primes using a hand-rolled Miller-Rabin primality test (no external library), counting how many odd candidates get tried before each prime is found, then multiplies them into a toy RSA modulus:
import random
def is_probable_prime(n, rounds=20):
if n < 2:
return False
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
if n % p == 0:
return n == p
d = n - 1
r = 0
while d % 2 == 0:
d //= 2
r += 1
for _ in range(rounds):
a = random.randrange(2, n - 1)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def find_prime(bits):
tries = 0
while True:
tries += 1
candidate = random.getrandbits(bits) | (1 << (bits - 1)) | 1
if is_probable_prime(candidate):
return candidate, tries
random.seed()
p, tries_p = find_prime(512)
q, tries_q = find_prime(512)
n = p * q
print(f"prime p found after {tries_p} candidates")
print(f"prime q found after {tries_q} candidates")
print(f"modulus n bit length: {n.bit_length()}")prime p found after 352 candidates
prime q found after 35 candidates
modulus n bit length: 1023This run needed 352 candidates for the first prime and 35 for the second, both in the right ballpark for the prime number theorem’s rough density estimate of about 1 prime per ln(2^512) ≈ 355 integers near that size, but since the search only tests odd candidates, expect a hit roughly every 177 odd numbers tried. Run it again and you’d get different candidate counts (primality testing involves randomized checks and the exact primes found will differ), but the same rough density, because that’s a property of how primes are distributed, not of any one run.
flowchart TD
subgraph Sym["Symmetric key generation"]
S1["Ask CSPRNG for n bits"] --> S2["Use directly as key"]
end
subgraph Asym["Asymmetric key generation (RSA)"]
A1["Generate random odd<br/>candidate of target bit length"] --> A2{"Passes primality<br/>test?"}
A2 -->|"no"| A1
A2 -->|"yes"| A3["Keep as prime p"]
A3 --> A4["Repeat for prime q"]
A4 --> A5["n = p * q<br/>(the modulus)"]
endReal-World Failures in Seemingly Strong Cryptography
Everything above assumes the cipher and the key-generation process are doing what they’re supposed to. Some of the worst cryptographic failures in the last twenty years happened when that assumption quietly broke, not because any cipher’s math was wrong, but because something underneath the math, a component the proof never scrutinized, was compromised or buggy.
Dual_EC_DRBG is the clearest case of the first kind. It was a pseudorandom number generator built on elliptic-curve math, standardized by NIST in 2006 and marketed with a security rationale tied to the elliptic curve discrete log problem, the same kind of hard-problem justification that gives RSA its proof. It turned out to contain specially chosen constants that let whoever selected them predict all of the generator’s future output after seeing just a small amount of it. Documents leaked by Edward Snowden in 2013 confirmed the NSA had engineered exactly that relationship. RSA Security’s BSAFE library shipped Dual_EC_DRBG as its default random number generator, which meant every key generated on top of it, however strong the surrounding cipher looked on paper, was potentially predictable to whoever held the backdoor.
The 2008 Debian OpenSSL bug is the second kind of failure, no backdoor, just a mistake. A well-intentioned code cleanup accidentally stripped out the lines feeding real entropy into OpenSSL’s random number generator on Debian and Ubuntu systems. For close to two years, the only effective source of randomness left was the process ID, which tops out at around 32,768 possible values. Every SSH key, SSL certificate, and other cryptographic key generated on an affected system during that window came from a keyspace small enough to exhaustively enumerate in minutes, no matter what the key labeled itself as, 1024-bit or 2048-bit RSA meant nothing when the actual entropy behind it fit in fifteen bits.
Both incidents share the same lesson: bit security, provable security, and heuristic security are all statements about the cipher’s math. Neither statement says anything about the random number generator feeding it keys, and both of these failures happened entirely in that gap.
Key Takeaways
- Informational security means an attacker with infinite time still can’t distinguish the right key, achieved by the one-time pad, but rarely practical outside theory.
- Computational security accepts that breaking a cipher is possible in principle and instead asks whether it’s affordable, formalized as
(t, ε): at mostεsuccess probability withintoperations. - Bit security condenses “how hard is the best known attack” into one number via
log2, and it can sit below the raw key size, as in RSA-3072’s roughly 128-bit security or a cipher with a meet-in-the-middle shortcut. - Real attack cost depends on more than operation counts: parallelism, memory access patterns, precomputation, and the number of acceptable targets can all shrink effective security well below the bit-security figure on paper.
- Provable security offers a conditional, relative guarantee via reduction to a hard problem or another primitive, it can still fail if that hard problem turns out easier than believed (SIKE) or if the attack model never covered the real threat (timing side channels).
- Heuristic security, the basis for trust in AES and most symmetric ciphers, comes from a large, stable security margin surviving years of public cryptanalysis rather than from a formal proof.
- Symmetric keys are raw random bits used directly, asymmetric keys need a structured search (like hunting for primes), and some of history’s worst cryptographic failures (Dual_EC_DRBG, the Debian OpenSSL bug) came from broken randomness underneath otherwise sound designs, not from broken math.