Computational records (verified rows only)
Date: 2026-11-01. Every row cites a key in paper/references.bib; figures are those stated in the
paper abstracts or in the Certicom challenge document, not extrapolations.
A. Elliptic-curve discrete logarithm computations
| Instance | Group-order size | Field type | Hardware | Completed | Source | Notes |
|---|---|---|---|---|---|---|
| ECCp-79 / -89 / -97 (Certicom exercises) | 79 / 89 / 97 bits | prime | distributed PCs | Dec. 1997 / Jan. 1998 / Mar. 1998 | certicom2009challenge |
Certicom table 6.2.2 |
| ECC2K-108 (Certicom Level I) | 108 bits | binary, Koblitz | distributed (≈1.3·10^6 machine-days) | Apr. 4, 2000 | certicom2009challenge |
Frobenius automorphism exploited (cf. gallant2000improving, wiener1999faster) |
| ECCp-109 (Certicom Level I) | 109 bits | prime | distributed (≈9.0·10^6 machine-days) | Oct. 15, 2002 | certicom2009challenge |
2.1·10^16 expected curve operations |
| ECC2-109 (Certicom Level I) | 109 bits | binary, random | distributed (≈2.1·10^7 machine-days) | Apr. 8, 2004 | certicom2009challenge |
|
| secp112r1 (112-bit prime field) | 112 bits | prime | cluster of ~215 PlayStation 3 (Cell) consoles, EPFL | July 2009 (published 2012) | bos2012solving |
Pollard rho with "sloppy reduction"; still the largest completed prime-field ECDLP found in this survey |
| 113-bit Koblitz curve | 113 bits | binary, Koblitz | 18-core Virtex-6 FPGA cluster | 2014 ("extrapolated 24 days") | wenger2014solving |
first FPGA-cluster ECDLP record |
| sect113r1 (SECG binary curve) | 113 bits | binary, random | 10 Kintex-7 FPGAs, 900·10^6 iterations/s, "several months" | 2015 (JCEN 2016) | wenger2016harder |
negation map + fruitless-cycle handling |
| sect113r2 (SECG binary curve) | 113 bits ("prime order very slightly larger than the previous record holder") | binary, random | Spartan-6 / larger FPGAs, 3 cores per Spartan-6 | 2016 | bernstein2016faster |
"new size record for completed ECDL computations" per abstract; the paper also benchmarks (does not solve) a curve over a 127-bit field |
| ECCp-131, ECC2-131, ECC2K-130 | 131 / 131 / 130 bits | prime / binary / Koblitz | — | open (no end date in Nov. 2009 Certicom document; no later completion found) | certicom2009challenge |
ECC2K-130 attack plan described in ePrint 2009/541 (not cited as a record, see unverified.md) |
Gap to secp256k1: the subgroup order n ≈ 2^256, so generic rho needs ≈ √(πn/4) ≈ 2^127.5 group
operations with the negation map — about 2^71 times the 112-bit computation (bos2012solving,
bernstein2011correct).
B. SHA-256 (and SHA-2 family) reduced-step cryptanalysis
Type legend: C = collision (standard IV, hash function); SFS = semi-free-start collision (attacker chooses the chaining value, same for both messages); FS = free-start collision (two different chaining values); P = preimage on the hash function; PP = (pseudo-)preimage on the compression function. SHA-256 has 64 steps, SHA-512 has 80.
| Function | Type | Steps | Complexity | Practical (example given)? | Year / venue | Source |
|---|---|---|---|---|---|---|
| SHA-256 | C | 21 | high-probability differential (≈2^19 per later analysis) | yes | FSE 2008 | nikolic2008collisions |
| SHA-256 | SFS | 23 | — | yes | FSE 2008 | nikolic2008collisions |
| SHA-256 | SFS near-collision (15/256 bits differ) | 25 | — | yes | FSE 2008 | nikolic2008collisions |
| SHA-256 | C | 23 / 24 | 2^18 / 2^28.5 | yes (pairs given) | SAC 2008 | indesteege2008collisions |
| SHA-512 | C | 23 / 24 | 2^44.9 / 2^53.0 | theoretical | SAC 2008 | indesteege2008collisions |
| SHA-256 | FS near-collision | 31 | — | — | SAC 2008 | indesteege2008collisions |
| SHA-256 | C | 23 / 24 | 2^11.5 / 2^28.5 (2^15.5 with a 2^32 table) | yes (pairs given) | INDOCRYPT 2008 | sanadhya2008new |
| SHA-512 | C | 23 / 24 | 2^16.5 / 2^32.5 (2^22.5 with a 2^64 table) | yes (first 24-step SHA-512 pair) | INDOCRYPT 2008 | sanadhya2008new |
| SHA-256 | C | 27 | practical | yes | ASIACRYPT 2011 | mendel2011finding |
| SHA-256 | SFS | 32 | practical | yes | ASIACRYPT 2011 | mendel2011finding |
| SHA-256 | C | 28 | practical | yes | EUROCRYPT 2013 | mendel2013improving |
| SHA-256 | C | 31 | ≤ 2^65.5 (two-block) | theoretical | EUROCRYPT 2013 | mendel2013improving |
| SHA-256 | SFS | 38 | practical | yes | EUROCRYPT 2013 | mendel2013improving |
| SHA-512 | SFS | 38 | 2^40.5 | yes | FSE 2014 | eichlseder2014branching |
| SHA-512, SHA-512/224, SHA-512/256 | C | 27 | practical | yes | ASIACRYPT 2015 | dobraunig2015analysis |
| SHA-512/224 ; SHA-512/256 | FS | 44 ; 43 | practical | yes | ASIACRYPT 2015 | dobraunig2015analysis |
| SHA-256 | SFS | 39 | practical | yes (first 39-step SFS pair) | EUROCRYPT 2024 | li2024new |
| SHA-224 | FS | 40 | practical (previous theoretical bound 2^110) | yes | EUROCRYPT 2024 | li2024new |
| SHA-512 | C | 28 | practical | yes (first) | EUROCRYPT 2024 | li2024new |
| SHA-512 | C | 31 | theoretical | no | EUROCRYPT 2024 | li2024new |
| SHA-256 | C | 31 | ≈1.2 h on 64 threads, negligible memory | yes (first practical 31-step pair) | ASIACRYPT 2024 (best paper) | li2024first |
| SHA-256 | C | 37 | theoretical (first attack beyond 31 steps in 12 years) | no | ePrint 2026/232 | zhang2026collision |
| SHA-256 | SFS (SAT + CAS) | 38 | solver-based reproduction ("modified initialization vector") | yes | SC-Square 2024 | alamgir2024sha256 |
| SHA-256 | C (pure SAT, no CAS) | ≤ 28 | — | yes | SC-Square 2024 | alamgir2024sha256 |
| SHA-256 | P | 43 | 2^254.9 (pseudo-preimage 2^251.9), memory ≈ 2^6 words | theoretical | ASIACRYPT 2009 | aoki2009preimages |
| SHA-512 | P | 46 | 2^511.5 (pseudo-preimage 2^509) | theoretical | ASIACRYPT 2009 | aoki2009preimages |
| SHA-256 | P (hash function) | 45 | close to 2^256 (biclique) | theoretical | FSE 2012 | khovratovich2012bicliques |
| SHA-256 | PP (compression function) | 52 | close to 2^256 (biclique) | theoretical | FSE 2012 | khovratovich2012bicliques |
| SHA-512 | P / PP | 50 / 57 | close to 2^512 (biclique) | theoretical | FSE 2012 | khovratovich2012bicliques |
| SHA-1 (for comparison) | C (full 80 steps) | 80 | ≈2^63.1 | yes (SHAttered) | CRYPTO 2017 | stevens2017first |
| SHA-1 | chosen-prefix C (full) | 80 | ≈2^63.4 | yes | USENIX Security 2020 | leurent2020sha1 |
Summary of the state of the art for SHA-256 (as of 2026-11-01): practical collisions up to 31 steps, theoretical collisions up to 37 steps, practical semi-free-start collisions up to 39 steps, theoretical preimages up to 45 steps (52 for the compression function). No attack on the full 64-step function is known; the generic bounds 2^128 (collision) and 2^256 (preimage) stand.