Security levels, key sizes and attack cost

A 56-bit key has about 72 quadrillion possible values, and a cluster that tests a trillion keys a second tries every one of them in 20 hours. Add 72 more bits and the same search takes longer than ten trillion years even at a million times that speed. Key sizes are a statement about that arithmetic, and so is every “at least 128 bits” in a standard.

This lesson turns it into numbers you can check. You compute brute-force times, read NIST’s table that makes AES-128, RSA-3072 and a 256-bit curve equal, use the birthday bound to size random identifiers and nonces, and see what a large quantum computer would change, ending with a two-step code lab that turns the strength table and the birthday bound into code.

What n bits of security means, in years of guessing

NIST defines security strengthsecurity strength: The work needed to break an algorithm, in bits: s bits means about 2^s operations. NIST uses the levels 112, 128, 192 and 256 to compare unlike algorithms, such as AES-128 and RSA-3072. as the amount of work needed to break an algorithm: an algorithm with s bits of strength takes about 2ˢ operations to break, where s is 112, 128, 192 or 256 (SP 800-57 and the draft NIST IR 8547). The simplest attack is an exhaustive key searchexhaustive key search: Trying every possible key until one works, also called brute force. Each extra key bit doubles its cost; for a well-designed cipher no attack does better.: try every key until one works. For a well-designed cipher no known attack does much better, so its strength is its key size. Each extra bit doubles the number of keys, and ten extra bits multiply it by 1,024. The program below turns key sizes into time at three guessing rates. The rates are assumptions, not measurements: about one fast machine, a large cluster, and a rate far beyond both, the margin designers use to be safe. Change them and run it again:

"""How long trying every key takes, at three assumed guessing rates (estimates, not measurements)."""

YEAR = 365.25 * 24 * 3600  # seconds in a year of 365.25 days


def readable(seconds):
    """A duration in the unit that keeps its number short."""
    years = seconds / YEAR
    if years >= 1e12:
        return f"{years:.1e} years".replace("e+", "e")
    for unit, size in [(1e9, "billion years"), (1e6, "million years"), (1, "years")]:
        if years >= unit:
            amount = years / unit
            return f"{amount:,.0f} {size}" if amount >= 10 else f"{amount:.1f} {size}"
    for name, size in [("days", 86400), ("hours", 3600), ("minutes", 60), ("s", 1), ("ms", 1e-3), ("µs", 1e-6)]:
        if seconds >= size:
            amount = seconds / size
            return f"{amount:,.0f} {name}" if amount >= 10 else f"{amount:.1f} {name}"
    return f"{seconds * 1e9:.1f} ns"


RATES = [10**9, 10**12, 10**18]  # guesses a second: one fast machine, a large cluster, far beyond both
print(f"{'Key':<10}{'Keys to try':<13}{'at 10^9 a second':<19}{'at 10^12 a second':<19}at 10^18 a second")
for bits in [40, 56, 64, 80, 112, 128]:
    keys = 2**bits
    times = [readable(keys / rate) for rate in RATES]
    print(f"{str(bits) + ' bits':<10}{keys:<13.2e}{times[0]:<19}{times[1]:<19}{times[2]}")
print()
print("A search that stops at the key needs half the keys on average, so half these times.")
print("Each extra bit doubles the work: 2**129 // 2**128 =", 2**129 // 2**128)

Key       Keys to try  at 10^9 a second   at 10^12 a second  at 10^18 a second
40 bits   1.10e+12     18 minutes         1.1 s              1.1 µs
56 bits   7.21e+16     2.3 years          20 hours           72 ms
64 bits   1.84e+19     585 years          214 days           18 s
80 bits   1.21e+24     38 million years   38,309 years       14 days
112 bits  5.19e+33     1.6e17 years       1.6e14 years       165 million years
128 bits  3.40e+38     1.1e22 years       1.1e19 years       1.1e13 years

A search that stops at the key needs half the keys on average, so half these times.
Each extra bit doubles the work: 2**129 // 2**128 = 2

At a trillion guesses a second, a 56-bit key falls in 20 hours and a 64-bit key in 214 days. An 80-bit key holds for 38,309 years at that rate but only 14 days at a billion billion. From 112 bits on, even the fastest rate needs 165 million years, and 128 bits needs 1.1 × 10¹³ years. A search that stops when it finds the key needs half the tries on average, which changes nothing at these scales.

Numbers this large do not fit ordinary integers, so code that computes them needs exact arithmetic. JavaScript’s Number is exact only up to 2⁵³; BigInt keeps every digit:

// Key counts are too big for ordinary numbers: JavaScript's Number is exact only up to 2^53.
// BigInt keeps every digit, so the years below are exact whole numbers (at an assumed 10^12 guesses a second).
const YEAR = 31_557_600n; // seconds in a year of 365.25 days
const RATE = 10n ** 12n; // guesses a second, an estimate for a large cluster

console.log('2 ** 128 as a Number: ', (2 ** 128).toString());
console.log('2n ** 128n as a BigInt:', (2n ** 128n).toString());
console.log('Number keeps 2^53 + 1? ', 2 ** 53 + 1 === 2 ** 53 ? 'no, it rounds to 2^53' : 'yes');
console.log();
for (const bits of [56n, 80n, 112n, 128n]) {
  const seconds = 2n ** bits / RATE; // BigInt division rounds down
  const time = seconds < YEAR ? `${(seconds / 3600n).toLocaleString('en-US')} hours` : `${(seconds / YEAR).toLocaleString('en-US')} years`;
  console.log(`${bits} bits: ${time} to try every key`);
}

2 ** 128 as a Number:  3.402823669209385e+38
2n ** 128n as a BigInt: 340282366920938463463374607431768211456
Number keeps 2^53 + 1?  no, it rounds to 2^53

56 bits: 20 hours to try every key
80 bits: 38,308 years to try every key
112 bits: 164,533,958,809,758 years to try every key
128 bits: 10,782,897,524,556,318,080 years to try every key

Why RSA needs 3072-bit keys to match AES-128

Algorithms of different kinds are broken in different ways, so equal security takes very different key sizes. NIST’s key-management recommendation, SP 800-57 Part 1, lines them up in its Table 2, and SP 800-186 places the named curves:

AES has no known attack much better than trying keys, so AES-128 gives 128 bits. RSA falls to methods that factor its modulus far faster than any key search; SP 800-57 notes that strength and key length differ for exactly this reason. That is why RSA must grow to 3,072 bits for 128 bits of strength, and to 15,360 for 256. Elliptic curves sit in between: the best known attacks need about the square root of the size of the curve’s group, so, as SP 800-186 puts it, a curve gives about half the bit length of its group order. A 256-bit curve gives 128 bits with private keys of 32 bytes.

Hash functions get two numbers in SP 800-57’s Table 3. Where collisions matter, as in digital signatures, SHA-256 gives 128 bits; where only finding an input for a given output matters, as in HMAC and key derivation, SHA-256 gives 256. The next section shows where the halving comes from.

OWASP’s ASVS 5.0 sets a floor worth adopting for any new design: every primitive at 128 bits or more, its requirement 11.2.3, which gives a 256-bit elliptic-curve key against RSA-3072 as its own example.

The birthday bound: collisions arrive at the square root

In a room of 23 people, the chance that two share a birthday is 50.7 %, although a year has 365 days. That surprise, recorded in the Handbook of Applied Cryptography as the birthday problembirthday bound: The rule that random values of b bits start to repeat after about 2^(b/2) of them. It is why a 256-bit hash gives about 128 bits of collision resistance and why random nonces have usage limits., decides the size of anything chosen at random. Among n random values of b bits, the chance that at least two are equal is about 1 − e^(−n(n − 1)/2^(b+1)), and it reaches one half after about 1.18 × 2^(b/2) values: the square root of the number of possibilities, not the number itself. Run the program, then put in your own counts:

"""The birthday bound: how likely two random values collide, exactly for small cases and by the usual formula."""
import math


def exact(n, m):
    """1 - m(m-1)...(m-n+1) / m**n: the chance that n draws from m values repeat at least once."""
    unique = 1.0
    for i in range(n):
        unique *= (m - i) / m
    return 1 - unique


def approx(n, bits):
    """1 - exp(-n(n-1) / 2^(bits+1)), computed with expm1 so that tiny chances do not round to 0."""
    return -math.expm1(-n * (n - 1) / 2 ** (bits + 1))


print(f"23 people, 365 birthdays, exact:  {exact(23, 365):.3f}")
print(f"30 people, 365 birthdays, exact:  {exact(30, 365):.3f}")
print(f"The formula for 23 people:        {-math.expm1(-23 * 22 / (2 * 365)):.3f}")
print()
counts = [10**6, 10**9, 2**32, 10**12]
print(f"{'Random bits':<13}" + "".join(f"{label:<12}" for label in ["10^6 values", "10^9", "2^32", "10^12"]) + "50 % at about")
for bits in [32, 64, 96, 122, 128]:
    cells = "".join(f"{approx(n, bits):<12.2g}" for n in counts)
    half = math.sqrt(2 * math.log(2)) * 2 ** (bits / 2)
    print(f"{bits:<13}{cells}{half:.2g} values")
print()
x = 1e-20
print("Why expm1: 1 - exp(-1e-20) =", 1 - math.exp(-x), "but -expm1(-1e-20) =", -math.expm1(-x))

23 people, 365 birthdays, exact:  0.507
30 people, 365 birthdays, exact:  0.706
The formula for 23 people:        0.500

Random bits  10^6 values 10^9        2^32        10^12       50 % at about
32           1           1           1           1           7.7e+04 values
64           2.7e-08     0.027       0.39        1           5.1e+09 values
96           6.3e-18     6.3e-12     1.2e-10     6.3e-06     3.3e+14 values
122          9.4e-26     9.4e-20     1.7e-18     9.4e-14     2.7e+18 values
128          1.5e-27     1.5e-21     2.7e-20     1.5e-15     2.2e+19 values

Why expm1: 1 - exp(-1e-20) = 0.0 but -expm1(-1e-20) = 1e-20

The exact product reproduces the Handbook’s 0.507 for 23 people and 0.706 for 30, and the formula gives 0.500 for 23. The table then shows why the square root matters:

• Hash outputs. Finding any two inputs with the same SHA-256 digest takes about 2¹²⁸ tries, not 2²⁵⁶, which is the 128 bits of collision resistance in SP 800-57’s Table 3.
• Nonces. AES-GCM usually takes a 96-bit noncenonce: A value used only once with a given key, such as the 96-bit nonce of AES-GCM. Repeating one can break the protection, so nonces come from a counter or from enough random bits., and drawn at random, 2³² of them collide with a chance of about 1.2 × 10⁻¹⁰. NIST SP 800-38D requires that chance to stay at 2⁻³² or below, and so caps a key at 2³² encryptions when its nonces are random.
• Identifiers. Random 64-bit identifiers collide with a chance of 0.39 by 2³² of them, and become even odds near 5.1 billion. A version 4 UUID has 122 random bits (RFC 9562), so a trillion of them collide with a chance of about 9.4 × 10⁻¹⁴.

The last line of the output is a trap worth knowing: for tiny chances, 1 - exp(-x) rounds to 0, while expm1 keeps the value. The second step of the code lab below asks for exactly that.

What a large quantum computer would change

None exists that can attack today’s cryptography, and RFC 9958, the IETF’s guide to post-quantum cryptography for engineers, still calls such machines theoretical. Two algorithms explain why planning has started anyway. Shor’s algorithmShor's algorithm: A quantum algorithm that factors numbers and computes discrete logarithms efficiently. On a large enough quantum computer it would break RSA, Diffie-Hellman and elliptic-curve cryptography at any key size. factors numbers and solves discrete logarithms efficiently, so it would break RSA, Diffie-Hellman and every elliptic curve outright, and longer keys would not save them. Grover’s algorithmGrover's algorithm: A quantum search algorithm with a quadratic speed-up: in theory a search of 2^128 keys would take about 2^64 steps. It weakens symmetric keys and hashes only modestly in practice. speeds up search quadratically, so in theory a 128-bit key search would need about 2⁶⁴ quantum steps. RFC 9958 argues that this matters far less in practice, because the steps cannot be split well across many machines, and concludes that AES-128 remains secure, while noting that some agencies recommend AES-256 anyway.

The urgency comes from recordings. Traffic encrypted today with RSA or elliptic-curve key exchange can be stored and decrypted once a large enough machine exists, which NIST IR 8547 and RFC 9958 both call harvest now, decrypt laterharvest now, decrypt later: Recording encrypted traffic today in order to decrypt it once a large quantum computer exists. It makes quantum-resistant key exchange urgent for secrets that must last for years.. Data that must stay secret for years needs quantum-resistant key exchange now. NIST’s draft plan for the change, step by step:

The replacements are measured against the symmetric primitives. The draft’s post-quantum security categories use AES as their yardstick: category 1 is as hard to break as AES-128, category 3 as AES-192 and category 5 as AES-256. FIPS 203 puts ML-KEM-768, the key-encapsulation mechanism NIST recommends as the default, in category 3.

Pick sizes for a new design in three questions

Three questions decide most choices: the floor your design must meet, what the key does, and how long the protection must last. Answer them in the table below, which marks what fits and says why the rest does not:

In short: at a 128-bit floor, AES-128 or AES-256 protects data under a shared key; X25519, Ed25519 or P-256 handle key agreement and signatures for data that need not outlive 2035; RSA-2048 falls short of the floor; and anything that must stay secret past 2035 against recorded traffic needs ML-KEM, in a hybrid with X25519, for its key exchange. Whatever you choose, write it into a cryptographic inventory, as ASVS 5.0 asks in requirement 11.1.2, so that the next change of algorithm or key size is a known list of places rather than a search through the code.

Practise: encode the tables in code

Two exercises turn the lesson’s tables into functions with sample tests that run on this page. The first looks up the strength of a key the way SP 800-57 and SP 800-186 give it, and its starter code makes the key-size mistake on purpose. The second computes collision chances with the birthday bound, including the 2³² nonce limit of SP 800-38D:

def security_bits(name):
    """The security strength in bits of a name such as 'AES-128', 'RSA-3072' or 'P-256'."""
    # The classic mistake: the key size is not the strength. Replace this with the lesson's tables.
    return int(name.split("-")[1])

from strength import security_bits


def raises_value_error(name):
    try:
        security_bits(name)
    except ValueError:
        return True
    return False


def test_symmetric_keys():
    """AES keys give their own size"""
    assert security_bits("AES-128") == 128
    assert security_bits("AES-256") == 256


def test_rsa_rows_of_sp_800_57():
    """RSA follows the rows of SP 800-57 Table 2, with sizes between rows rounded down"""
    expected = {"RSA-1024": 80, "RSA-2048": 112, "RSA-3072": 128, "RSA-4096": 128, "RSA-7680": 192, "RSA-15360": 256}
    for name, bits in expected.items():
        assert security_bits(name) == bits, f"{name} gives {bits} bits"


def test_named_curves_of_sp_800_186():
    """the curves follow SP 800-186"""
    expected = {"P-224": 112, "P-256": 128, "X25519": 128, "Ed25519": 128, "P-384": 192, "Ed448": 224, "P-521": 256}
    for name, bits in expected.items():
        assert security_bits(name) == bits, f"{name} gives {bits} bits"


def test_unknown_names_raise():
    """names and sizes the tables do not list raise ValueError"""
    for name in ["RSA-512", "AES-100", "DES", "P-255", "RSA-abc", "RSA-"]:
        assert raises_value_error(name), f"{name!r} should raise ValueError"

/** The security strength in bits of a name such as 'AES-128', 'RSA-3072' or 'P-256'. */
export function securityBits(name) {
  // The classic mistake: the key size is not the strength. Replace this with the lesson's tables.
  return Number(name.split('-')[1]);
}

import { test, assert } from 'mysmartcopilot:test';
import { securityBits } from './strength.mjs';

test('AES keys give their own size', () => {
  assert.equal(securityBits('AES-128'), 128);
  assert.equal(securityBits('AES-256'), 256);
});

test('RSA follows the rows of SP 800-57 Table 2, with sizes between rows rounded down', () => {
  const expected = { 'RSA-1024': 80, 'RSA-2048': 112, 'RSA-3072': 128, 'RSA-4096': 128, 'RSA-7680': 192, 'RSA-15360': 256 };
  for (const [name, bits] of Object.entries(expected)) assert.equal(securityBits(name), bits, `${name} gives ${bits} bits`);
});

test('the curves follow SP 800-186', () => {
  const expected = { 'P-224': 112, 'P-256': 128, X25519: 128, Ed25519: 128, 'P-384': 192, Ed448: 224, 'P-521': 256 };
  for (const [name, bits] of Object.entries(expected)) assert.equal(securityBits(name), bits, `${name} gives ${bits} bits`);
});

test('names and sizes the tables do not list throw', () => {
  for (const name of ['RSA-512', 'AES-100', 'DES', 'P-255', 'RSA-abc', 'RSA-']) assert.throws(() => securityBits(name), `"${name}" should throw`);
});

import math


def collision_probability(count, bits):
    """The chance that count random values of the given number of bits are not all different."""
    # Two classic mistakes: 2 ** bits where the formula has 2 ** (bits + 1), and 1 - exp(...),
    # which rounds every tiny chance to 0. Fix both.
    return 1 - math.exp(-count * count / 2**bits)

import math

from birthday import collision_probability


def close(got, want):
    return math.isclose(got, want, rel_tol=1e-9, abs_tol=0.0)


def raises_value_error(count, bits):
    try:
        collision_probability(count, bits)
    except ValueError:
        return True
    return False


def test_nist_sp_800_38d_nonce_limit():
    """2**32 random 96-bit nonces under one key: about 2**-33, the limit of NIST SP 800-38D"""
    assert close(collision_probability(2**32, 96), 1.164153217930535e-10)


def test_64_bit_identifiers():
    """2**32 random 64-bit identifiers collide with a chance of about 0.39"""
    assert close(collision_probability(2**32, 64), 0.3934693402167571)


def test_tiny_chances_are_not_zero():
    """a billion and a million 128-bit identifiers: tiny chances, but not 0"""
    assert close(collision_probability(10**9, 128), 1.4693679370584914e-21)
    assert collision_probability(10**6, 128) > 0


def test_edges():
    """no value or one value cannot collide; huge counts give a chance of 1"""
    assert collision_probability(0, 64) == 0
    assert collision_probability(1, 64) == 0
    assert close(collision_probability(10**12, 32), 1.0)


def test_bad_arguments_raise():
    """a negative count or fewer than 1 bit raises ValueError"""
    assert raises_value_error(-1, 64)
    assert raises_value_error(10, 0)

/** The chance that count random values of the given number of bits are not all different. */
export function collisionProbability(count, bits) {
  // Two classic mistakes: 2 ** bits where the formula has 2 ** (bits + 1), and 1 - exp(...),
  // which rounds every tiny chance to 0. Fix both.
  return 1 - Math.exp((-count * count) / 2 ** bits);
}

import { test, assert } from 'mysmartcopilot:test';
import { collisionProbability } from './birthday.mjs';

const close = (got, want) => Math.abs(got - want) <= 1e-9 * Math.abs(want);

test('2**32 random 96-bit nonces under one key: about 2**-33, the limit of NIST SP 800-38D', () => {
  assert.ok(close(collisionProbability(2 ** 32, 96), 1.164153217930535e-10), String(collisionProbability(2 ** 32, 96)));
});

test('2**32 random 64-bit identifiers collide with a chance of about 0.39', () => {
  assert.ok(close(collisionProbability(2 ** 32, 64), 0.3934693402167571), String(collisionProbability(2 ** 32, 64)));
});

test('a billion and a million 128-bit identifiers: tiny chances, but not 0', () => {
  assert.ok(close(collisionProbability(1e9, 128), 1.4693679370584914e-21), String(collisionProbability(1e9, 128)));
  assert.ok(collisionProbability(1e6, 128) > 0, 'a million 128-bit values');
});

test('no value or one value cannot collide; huge counts give a chance of 1', () => {
  assert.ok(collisionProbability(0, 64) === 0, 'no values');
  assert.ok(collisionProbability(1, 64) === 0, 'one value');
  assert.ok(close(collisionProbability(1e12, 32), 1));
});

test('a negative count or fewer than 1 bit throws', () => {
  assert.throws(() => collisionProbability(-1, 64));
  assert.throws(() => collisionProbability(10, 0));
});

Then take a mixed run through all five ideas: the first questions target your weakest idea, a right answer raises the level, and anything you miss comes back before you finish:

Interview questions

Warm-up (fresher to mid level): what does it mean that RSA-3072 and AES-128 both give 128 bits of security?

It means that the best known attack on each takes about 2¹²⁸ operations, so both are equally far out of reach, not that their keys are alike. For AES-128 the best attack is close to trying every key, so its 128-bit key gives 128 bits. RSA is attacked by factoring its modulus, which is much cheaper than trying keys, so it needs a 3,072-bit modulus to reach the same level, as NIST SP 800-57’s Table 2 shows; RSA-2048 only reaches 112. An elliptic curve needs about 256 bits for 128. The number lets you compare unlike algorithms and set one floor for a whole system, such as the 128 bits of ASVS 5.0. Against a large quantum computer the comparison breaks: RSA would fall outright, while AES-128 would stay secure in practice, because Grover’s search cannot be spread well across machines.

Key takeaways

• n bits of security means about 2ⁿ operations to break it; each extra bit doubles the work, and 128 bits is far beyond any search, even at a billion billion guesses a second.
• Key size equals strength only for a good symmetric cipher: AES-128, RSA-3072 and a 256-bit curve all give 128 bits, while RSA-2048 gives 112.
• Random values of b bits collide after about 2^(b/2) of them, which is why a 256-bit hash gives 128 bits of collision resistance and a key of AES-GCM with random nonces is capped at 2³² encryptions.
• Shor’s algorithm would break RSA and elliptic curves at any size and Grover’s would weaken symmetric keys only modestly, so key exchange for long-lived secrets moves to ML-KEM first.
• For a new design: a 128-bit floor, AES and modern curves today, and a hybrid post-quantum key exchange wherever data must stay secret beyond 2035.