1# Computational records (verified rows only)23Date: 2026-11-01. Every row cites a key in `paper/references.bib`; figures are those stated in the4paper abstracts or in the Certicom challenge document, not extrapolations.56## A. Elliptic-curve discrete logarithm computations78| Instance | Group-order size | Field type | Hardware | Completed | Source | Notes |9|---|---|---|---|---|---|---|10| 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 |11| 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`) |12| 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 |13| ECC2-109 (Certicom Level I) | 109 bits | binary, random | distributed (≈2.1·10^7 machine-days) | Apr. 8, 2004 | `certicom2009challenge` | |14| 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 |15| 113-bit Koblitz curve | 113 bits | binary, Koblitz | 18-core Virtex-6 FPGA cluster | 2014 ("extrapolated 24 days") | `wenger2014solving` | first FPGA-cluster ECDLP record |16| 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 |17| 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 |18| 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`) |1920Gap to secp256k1: the subgroup order n ≈ 2^256, so generic rho needs ≈ √(πn/4) ≈ 2^127.5 group21operations with the negation map — about 2^71 times the 112-bit computation (`bos2012solving`,22`bernstein2011correct`).2324## B. SHA-256 (and SHA-2 family) reduced-step cryptanalysis2526Type legend: C = collision (standard IV, hash function); SFS = semi-free-start collision (attacker chooses27the chaining value, same for both messages); FS = free-start collision (two different chaining values);28P = preimage on the hash function; PP = (pseudo-)preimage on the compression function. SHA-256 has 6429steps, SHA-512 has 80.3031| Function | Type | Steps | Complexity | Practical (example given)? | Year / venue | Source |32|---|---|---|---|---|---|---|33| SHA-256 | C | 21 | high-probability differential (≈2^19 per later analysis) | yes | FSE 2008 | `nikolic2008collisions` |34| SHA-256 | SFS | 23 | — | yes | FSE 2008 | `nikolic2008collisions` |35| SHA-256 | SFS near-collision (15/256 bits differ) | 25 | — | yes | FSE 2008 | `nikolic2008collisions` |36| SHA-256 | C | 23 / 24 | 2^18 / 2^28.5 | yes (pairs given) | SAC 2008 | `indesteege2008collisions` |37| SHA-512 | C | 23 / 24 | 2^44.9 / 2^53.0 | theoretical | SAC 2008 | `indesteege2008collisions` |38| SHA-256 | FS near-collision | 31 | — | — | SAC 2008 | `indesteege2008collisions` |39| 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` |40| 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` |41| SHA-256 | C | 27 | practical | yes | ASIACRYPT 2011 | `mendel2011finding` |42| SHA-256 | SFS | 32 | practical | yes | ASIACRYPT 2011 | `mendel2011finding` |43| SHA-256 | C | 28 | practical | yes | EUROCRYPT 2013 | `mendel2013improving` |44| SHA-256 | C | 31 | ≤ 2^65.5 (two-block) | theoretical | EUROCRYPT 2013 | `mendel2013improving` |45| SHA-256 | SFS | 38 | practical | yes | EUROCRYPT 2013 | `mendel2013improving` |46| SHA-512 | SFS | 38 | 2^40.5 | yes | FSE 2014 | `eichlseder2014branching` |47| SHA-512, SHA-512/224, SHA-512/256 | C | 27 | practical | yes | ASIACRYPT 2015 | `dobraunig2015analysis` |48| SHA-512/224 ; SHA-512/256 | FS | 44 ; 43 | practical | yes | ASIACRYPT 2015 | `dobraunig2015analysis` |49| SHA-256 | SFS | 39 | practical | yes (first 39-step SFS pair) | EUROCRYPT 2024 | `li2024new` |50| SHA-224 | FS | 40 | practical (previous theoretical bound 2^110) | yes | EUROCRYPT 2024 | `li2024new` |51| SHA-512 | C | 28 | practical | yes (first) | EUROCRYPT 2024 | `li2024new` |52| SHA-512 | C | 31 | theoretical | no | EUROCRYPT 2024 | `li2024new` |53| SHA-256 | C | 31 | ≈1.2 h on 64 threads, negligible memory | **yes (first practical 31-step pair)** | ASIACRYPT 2024 (best paper) | `li2024first` |54| SHA-256 | C | 37 | theoretical (first attack beyond 31 steps in 12 years) | no | ePrint 2026/232 | `zhang2026collision` |55| SHA-256 | SFS (SAT + CAS) | 38 | solver-based reproduction ("modified initialization vector") | yes | SC-Square 2024 | `alamgir2024sha256` |56| SHA-256 | C (pure SAT, no CAS) | ≤ 28 | — | yes | SC-Square 2024 | `alamgir2024sha256` |57| SHA-256 | P | 43 | 2^254.9 (pseudo-preimage 2^251.9), memory ≈ 2^6 words | theoretical | ASIACRYPT 2009 | `aoki2009preimages` |58| SHA-512 | P | 46 | 2^511.5 (pseudo-preimage 2^509) | theoretical | ASIACRYPT 2009 | `aoki2009preimages` |59| SHA-256 | P (hash function) | 45 | close to 2^256 (biclique) | theoretical | FSE 2012 | `khovratovich2012bicliques` |60| SHA-256 | PP (compression function) | 52 | close to 2^256 (biclique) | theoretical | FSE 2012 | `khovratovich2012bicliques` |61| SHA-512 | P / PP | 50 / 57 | close to 2^512 (biclique) | theoretical | FSE 2012 | `khovratovich2012bicliques` |62| SHA-1 (for comparison) | C (full 80 steps) | 80 | ≈2^63.1 | yes (SHAttered) | CRYPTO 2017 | `stevens2017first` |63| SHA-1 | chosen-prefix C (full) | 80 | ≈2^63.4 | yes | USENIX Security 2020 | `leurent2020sha1` |6465Summary of the state of the art for SHA-256 (as of 2026-11-01): practical collisions up to 31 steps,66theoretical collisions up to 37 steps, practical semi-free-start collisions up to 39 steps, theoretical67preimages up to 45 steps (52 for the compression function). No attack on the full 64-step function is68known; the generic bounds 2^128 (collision) and 2^256 (preimage) stand.69