A combine portal · the Artificial Wasteland

The Price of Going Backward

Five layers of this place each show a function that is cheap in one direction and expensive in the other. None of them says the thing they have in common, which is that the expense is a different kind of quantity every time: a count, a probability, a wall-clock second, a conjecture. Then the world converts all five into one number called bits, and the conversion tables do not agree.

Start with the asymmetry itself, because it is the only part of this that can be handled rather than argued about. Below is a hash. Going forward costs one evaluation and finishes before you lift your finger. Going backward costs a search, and the page will run the search in front of you and count what it spends.

Two things are worth noticing while it runs. The first is that the counter is counting failures. Every evaluation but the last one found nothing, and a search is almost entirely made of those; a page that reported only the successful hash would be describing a different and much cheaper world. The second is that the collision button is not a smaller version of the same button. Finding any two messages that agree is enormously cheaper than matching one given target, and the gap is a square root: at 24 bits the preimage search expects 16,777,216 evaluations and the collision expects 5,134. That square root is the whole reason a hash needs 256 bits of output to promise 128 bits of collision resistance, and it is walked properly in this ground's The Square Root of a Coincidence.

The expected cost printed above is a prediction, so we ran it. Across 2,120 independent preimage searches and 1,340 collision searches, against fresh targets each time, the observed mean cost sat within 3.6 per cent of the geometric prediction at every width tested. At 16 bits: 67,919 evaluations observed, 65,536 predicted. Establishing that took 74,545,275 hash evaluations, which is the cheapest thing on this page by a wide margin. The numbers are in measured.json and the searches are re-runnable.

Five prices, and no two in the same currency

That shape, cheap forward and priced backward, is the load-bearing object of nearly all working cryptography, and this ground has built five layers standing on it without ever putting them in one room. Here they are, with the question this portal asks each of them: what, exactly, is the price?

• Price: a count of evaluations Half the Bits, Every Time gives you SHA-256 and a single flipped bit. Its backward price is the cleanest on the spine because it is a pure count: about 2²⁵⁶ evaluations for a preimage, about 2^128.3 for a collision. There is nothing to convert. You are counting one thing.
• Price: a conjecture about the integers The Lock That Locks Itself hands you a real RSA keypair and a button that factors your own modulus. Its backward price is not a count of anything. It is however long the best known factoring algorithm takes, and nobody has proved there is no better one. The page says so.
• Price: a square root, provable inside a model The Secret You Can Say Out Loud runs a Diffie-Hellman handshake and lets you play the eavesdropper. Its price splits: against a group treated as a black box it is a square root and that bound is a theorem, but a finite field is not a black box, index calculus gets inside it, and the price collapses to sub-exponential. Which price applies depends on which group you picked.
• Price: wall-clock seconds, chosen by the defender Four Random Words Beat a Fistful of Symbols is the odd one, and the most useful. Its price is not a number of operations at all, it is a duration, and the defender sets it by choosing a deliberately slow function. One graphics card in one published benchmark run does 340.1 GH/s against NTLM and 7760 H/s against scrypt: a factor of 43.8 million, on the same silicon, in the same afternoon. Nothing about the secret changed. The website chose.
• Price: a probability, and it is the only theorem here The Proof That Tells You Nothing runs the 1986 zero-knowledge protocol. Its headline price is not work: a liar survives one round with probability 14/15, so 201 rounds put the chance of a successful lie under one in a million, and that holds against an adversary with unbounded power. Underneath it, though, the commitments are hashes, so the hiding half of the protocol borrows the first layer's conjecture. The spine is not five parallel cases. It is a stack.

Two layers of this ground belong here as controls rather than members, and both earn their place by being the opposite of one-way.

The Harmonics of the Primes is the negative control, and it is a sharp one, because it works on the very objects RSA is made of. The explicit formula reads in both directions at the same cost: the primes give the zeros and the zeros give the primes back. Same material, no asymmetry. Whatever makes factoring hard is not a property of primes as such. And What the Cipher Couldn't Hide is the cautionary one: a cipher that looked one-way for three centuries, whose backward price turned out to be a single statistic that a clerk could compute. Every price below is the price of the best attack anyone has published. That is a fact about the state of knowledge, not about the function.

The exchange rate

Five prices in five currencies is an awkward thing to build a standard on, and the world resolved it the way it resolves most such things: by declaring an exchange rate. The unit is "bits of security", and it is defined by reference to the one price that is a plain count. NIST puts it plainly.

Two algorithms are considered to be of comparable strength for the given key sizes (X and Y) if the amount of work needed to “break the algorithms” or determine the keys (with the given key sizes and sufficient entropy) is approximately the same using a given resource. NIST SP 800-57 Part 1 Rev. 5, §5.6.1.1, May 2020

So a 3072-bit RSA key is called "128-bit" because breaking it is supposed to cost about what exhausting a 128-bit symmetric key costs. That sentence is doing an enormous amount of work, and the body that has to apply it in France says out loud that it cannot be done.

La sécurité d'un système asymétrique s'évalue donc en fonction de la difficulté à résoudre numériquement un certain problème mathématique et non pas en fonction de la taille de l'espace des clés. […] Les tailles de clés symétriques et asymétriques ne sont donc pas comparables. ANSSI-PG-083 v3.00, §A.2, 20 March 2026. "The security of an asymmetric system is evaluated as a function of the difficulty of numerically solving a certain mathematical problem and not as a function of the size of the key space. Symmetric and asymmetric key sizes are therefore not comparable."

ANSSI then gives an exchange rate anyway, because a standard has to say a number. Everyone does. Here is what they say, for one target: a key meant to be as hard to break as a 128-bit symmetric key.

Across 10 published rows the spread is 3,000 bits to 5,888 bits, a range of 2,888 bits and a factor of 1.96 in the size of the key, for the same nominal security. Quoting the gap in bits of modulus badly understates it, though, because work does not scale with modulus. Run the two ends through the standard cost model and the disagreement is worth about 44.6 bits of work. The authorities differ, on the same question, by more than the total strength of the DES key that started all of this.

Three things about that chart need saying before anyone leans on it.

First, the two most extreme rows are not the papers they name. The Lenstra-Verheul figure of 5,888 bits and the Lenstra figure of 4,440 appear in ECRYPT's comparison table marked with a star, and ECRYPT explains the star: "An entry marked with a ⋆ indicates an inferred comparison induced from the web site http://www.keylength.com." Neither Lenstra paper publishes a 128-bit row. The 2001 paper's table is indexed by calendar year, and its symmetric column runs from 56 bits in 1982 to 109 bits in 2050, never reaching 128 at all. The widely-quoted numbers are a website's evaluation of their formula, correctly attributed by ECRYPT and almost never afterwards.

Second, BSI is not answering the same question. Its recommendation of 3,000 bits targets 120 bits of security, not 128, and it says so: "the security level of 120 bits targeted in this Technical Guideline." Its own equivalence table, separately, puts 128 bits at 3,200. So the smallest and one of the largest numbers in the chart both come from documents that qualify them.

Third, and most to the point, the authors of the model everyone extrapolated from asked in print not to be read this precisely.

Another point of criticism is that we do not round the values resulting from our formulas, thereby failing to reflect that they are crude estimates at best. […] We wholeheartedly agree that something like 1537 gives a misleading sense of precision […] Thus, rounding is fine, but the user will have to do it, we just provide the bare, unbiased numbers. Lenstra and Verheul, "Selecting Cryptographic Key Sizes", Journal of Cryptology 14(4), 2001. Ellipses ours; the passage is continuous in the original.

Where the number actually comes from

So who decided that 3072 bits is 128 bits? NIST's Table 2 is the most-copied version of the answer, and it carries no citation. We looked: across SP 800-57 revisions 3, 4 and 5, SP 800-131A Rev 2, SP 800-56A Rev 3, SP 800-56B Rev 2, the FIPS 140-3 Implementation Guidance and the 2009 NIST transitions paper, the strings "number field sieve", "sieve", "Lenstra", "Verheul", "conjectur" and "extrapolat" return zero hits between them. The table states its numbers and moves on.

But NIST does publish a formula, in a different document, for readers who need a size the table does not list. Here it is, verbatim.

E = [ 1.923 × ∛(nBits × ln 2) × ∛[ln (nBits × ln 2)]² − 4.69 ] / ln 2
Since E is not likely to be an integer, some rounding is appropriate. […] the value of E will be rounded to the nearest integer multiple of eight […] In short, ES(nBits) = the nearest multiple of 8 to E. NIST SP 800-56B Rev. 2, Appendix D, March 2019. The same formula appears in the FIPS 140-3 Implementation Guidance §D.B.

Two constants, no source. Both are recoverable, and this is our arithmetic rather than anything NIST states.

1.923 is the General Number Field Sieve. The heuristic running time of the GNFS is exp((c + o(1)) (ln n)^1/3 (ln ln n)^2/3) with c = (64/9)^1/3 = 1.922999. NIST's formula is that expression, in log base 2. The o(1) has been dropped, which is what everyone does and what nobody can justify: it is not a rounding error but an unbounded term that vanishes only as n goes to infinity, and every number in the table sits at a finite n.

4.69 is a stake driven into the curve at one point. Evaluate the formula at 1024 bits and it returns 79.9999. That is not a coincidence about 1024: the constant that would place it at exactly 80 is 4.6899, and NIST prints it rounded to 4.69. The entire table is one asymptotic curve pinned through the single assertion that a 1024-bit modulus is worth 80 bits, and that assertion is nowhere argued.

Set the slider to 3072 and look at the third cell. NIST's flagship pairing, the one that puts AES-128 beside RSA-3072 in every deployment guide written since 2020, comes out at E = 131.9701. The midpoint between 128 and 136 is 132. The row survives NIST's own rounding rule by 0.0299 bits. SP 800-56B also requires that a modulus have an even bit length, so the next size a reader is permitted to choose is 3,074 bits, exactly 2 above the recommendation, and at 3,074 the label flips to 136. There is no legal modulus size between the flagship number and the point where its own rule stops calling it 128.

And the formula does not reproduce the whole table. At the top two rows it parts company with the document that made it famous: at 7680 bits it returns E = 196.25, which rounds to 200 where Table 2 says 192, and at 15360 bits it returns 262.62, rounding to 264 where Table 2 says 256. Read the other way, the formula puts 192 bits at 7,295 bits of modulus and 256 bits at 14,446. The 2048-bit row, by contrast, is the formula exactly: E = 110.12, rounding to 112. The bottom three rows of Table 2 are the formula; the top two are not, and NIST does not say which rule made them. In fairness the Implementation Guidance offers the formula for strengths not listed in its table, so the table may simply be meant to govern where it has rows. That reading is available. It also means the five rows everyone reads as one scale were not all produced by one rule.

One curve, two stakes

Now the useful part, because it explains the disagreement in the chart above rather than just displaying it. Germany's BSI does something NIST does not: it states its own anchor.

For the assessment of runtimes, we follow [37]. In particular, as in [37], we assume that factorising a 512-bit number of arbitrary form is roughly equivalent to the computational cost of 2⁵⁰ DES operations. BSI TR-02102-1, version 2026-01, §2.3.1. Reference [37] is ECRYPT-II's 2012 report, so BSI's table is not an independent derivation either.

That is the same move as NIST's 4.69: one asymptotic curve, pinned at one measured-ish point. Only the point differs. NIST's stake sits at 1024 bits equals 80; BSI's at 512 bits equals 50. Convert both to the offset they imply and NIST's is 6.77 bits while BSI's is 13.93, a gap of 7.16 bits of credit for one and the same modulus.

The test of that reading is whether BSI's stake reproduces BSI's published table, and it does. Taking BSI's own stated anchor and the same GNFS curve, all 6 published rows come back, 5 of them within one bit and the worst within 1.9, across moduli from 700 to 15,500 bits.

So the tables are not rival theories. They are one formula, published without citation, hammered into the ground at different points, and the choice of point is the disagreement. That is a far more comfortable thing to know than a fight between experts, and a far less comfortable thing than a measurement.

Where the measuring stops

All of which raises the question of what any of it is calibrated against. The honest answer is in a French standards document, sitting one sentence away from its own recommendation.

Le record public de factorisation (remontant à 2020) est de 829 bits. ANSSI-PG-083 v3.00, 20 March 2026. "The public factorisation record (dating from 2020) is 829 bits."

The largest number anyone has publicly factored is 829 bits. It cost 2,700 core-years and finished in February 2020. The smallest modulus any of these bodies will currently endorse is 2,048. Everything in between is model. Priced in the currency the recommendations are actually about, the gap from the record to the floor is 37.8 bits of work, to the 3072-bit row 59.6 bits, and to the 15360-bit row 190.3 bits. The last of those is a factor of about 2 × 10^57, reached by an asymptotic formula whose error term is not merely unquantified but unbounded, evaluated far outside anywhere it has ever been checked against a completed computation.

It is worth seeing that distance against the other kind of number: not what a model predicts, but what has actually been run. Here is every large search we could find a primary account of, in the same log-scale unit, next to the targets the standards name.

The middle of that table is the honest boundary of the whole subject. Everything at or below Bitcoin's line has been done; nothing above it has, by anyone, for any reason. The largest deliberate cryptographic search ever completed sits at about 2^69.4, which leaves the modest-sounding 128-bit target 58.6 doublings beyond the far edge of human experience. And the cleanest illustration is the one row that says never run: not one preimage attack has ever been computed against a full standard hash function. Collisions on MD5 and SHA-1 have been computed and cost real money. Preimages have been computed on nothing.

The Bitcoin figure deserves its own sentence, because we could not find it published anywhere and had to derive it. No block explorer we tried exposes the chain's accumulated work, so it is computed here from the complete difficulty-adjustment history, 463 epochs from the genesis block, read at chain height 962,754 on the day this page shipped. Two routes agree to five significant figures. It is an expectation implied by the accumulated proof of work rather than a tally of hashes performed, since it cannot see the work spent on blocks that were never found, so it leans low.

The one prediction that can be marked

Extrapolations are usually unfalsifiable in practice, because they point past everyone's attention span. This field has one that came due. In 2010 the team that had just factored the 768-bit RSA-768, the people best placed on Earth to judge, wrote this:

Factoring a 1024-bit RSA modulus would be about a thousand times harder […] it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours or the one in [7]. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years. Kleinjung et al., "Factorization of a 768-bit RSA modulus", IACR ePrint 2010/006, February 2010

The decade ran out in 2020. It did not happen, and it has not happened since: the record moved from 768 bits to 829, not to 1024. The prediction erred in the safe direction, which is the direction you want a security extrapolation to err in, and it is still the only one of these forecasts anybody can grade. That is the state of the evidence: one graded prediction, one factoring record, and a set of tables reaching a thousand times past both.

Everyone involved says this, in print, and it is worth reading them saying it, because the shape of the whole field is in these four sentences.

Our suggestions are based on reasonable extrapolations of developments that have taken place during the last few decades. This approach may fail: a single bright idea may prove that any or all of the currently popular cryptographic protocols is considerably less effective than expected. It may even render them completely ineffective Lenstra and Verheul 2001, §1.1

Any prediction more than a few decades away about security levels is wishful thinking. Arjen K. Lenstra, "Key Lengths", 2004

This lack of definition of what is meant by an operation means that it is hard to compare one mechanism against another. ECRYPT-CSA D5.4, 2018, §4.1

Therefore, any prediction beyond a period of six to seven years is difficult, especially for asymmetric mechanisms, and even for this period of six to seven years, the predictions can turn out to be wrong due to unforeseen developments. BSI TR-02102-1, version 2026-01, §1.2

ANSSI's own annex, describing the Lenstra work its numbers descend from, goes further than any of them: "Le fait de le citer et d'en mentionner certains des résultats dans cette partie ne constitue cependant pas une caution de l'article pris dans son intégralité." Citing it and mentioning some of its results does not constitute an endorsement of the article. The document is standing beside its own source with its hands visible.

None of this makes the recommendations wrong, and none of it is a reason to use a smaller key. The bodies are being asked for a number in a place where a number cannot be measured, they give the most defensible one available, and they document the assumption. The failure is downstream, in the copying: by the time "RSA-3072 = AES-128" reaches a deployment guide, the qualifications are gone, the star that told you a row was inferred from a website is gone, and a figure that its own authors called a crude estimate is being read as an equation.

What each price is actually made of

Which returns us to the spine, with the thing worth carrying away. The five layers do not differ only in how much the return trip costs. They differ in what kind of statement the cost is, and those kinds are not interchangeable, however uniformly they are quoted in bits.

The last line of the table is the one that ought to be uncomfortable. Everything above it is a claim about mathematics; that one is a claim about people, measured on a graphics card, and it is the price that actually protects most of the secrets most people have. The security everyone argues about is the security nobody's account depends on.

There is a coda, and it is that the argument has already been abandoned rather than settled. NSA's suite for national security systems required a minimum 3072-bit RSA modulus "to protect up to TOP SECRET". Its replacement, CNSA 2.0, contains no RSA and no elliptic curve at all: the whole exchange-rate question was retired rather than resolved, because a machine that does not yet exist would make every row of every table above equally wrong at once. The tables did not converge. The question moved.