Claude onthult de oorsprong van ECDSA-curven
"Het zijn gewoon tijdstempels": het decennia oude mysterie over de oorsprong van een van de populairste cryptografische standaarden is opgelost.
We zijn dit langdurige openstaande vraagstuk van de cryptografische gemeenschap nagegaan om zorgen over ECDSA weg te nemen, aangezien dit een van onze meest gebruikte cryptografische standaarden is. Lezers kunnen dit beschouwen als een leuk sluitstuk en het einde van jaren van speculatie. Er is geen actie vereist en er hoeven geen zaken anders aangepakt te worden. De meeste onderzoekers vertrouwden de curven al. Geniet ervan.
De context van ECDSA en het mysterie van de seeds
ECDSA is de meest gebruikte standaard voor elliptische kromme cryptografie (ECC). Het werd in het jaar 2000 door NIST overgenomen als onderdeel van de FIPS 186-2 Digital Signature Standard, waarin een set standaard elliptische curven van verschillende groottes en beveiligingsniveaus wordt beschreven.
Voor curven over priemgetallen en binaire velden publiceerden de specificaties een "seed"-parameter. De hashwaarde van deze seed wordt gebruikt om de coëfficiënt b van de curve te definiëren. De herkomst van deze seeds is al lange tijd een vraagteken, omdat ze door de NSA werden verstrekt zonder enige uitleg of rechtvaardiging. Een voorbeeld is de NIST P-256 curve seed: SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90, waarbij geen informatie was over waar deze vandaan kwam.
Neal Koblitz en Alfred Menezes schreven hierover een uitstekende samenvatting, "A Riddle Wrapped in an Enigma", waarin de geschiedenis en de zorgen rond de seed-waarden worden besproken. Dit mysterie leidde tot een amateuronderzoek naar de oorsprong van de seeds en een bounty voor iedereen die ze kon vinden.
Het meest hardnekkige verhaal was dat Jerry Solinas, een langdurig medewerker van de NSA, de seeds had gegenereerd met een hash van een humoristische zin. Solinas verklaarde in 2015:
"Ik geloof dat er een teller werd gebruikt in plaats van meervoudig hashen, maar ik ken de details niet. De boodschap ging in de richting van 'Geef Bob en Jerry een loonsverhoging' of 'Bob en Jerry rule' of iets dergelijks. Het was Bob Reiter die de code daadwerkelijk schreef, en hij herinnert zich de details ook niet meer. We konden ook geen archieven van zo lang geleden vinden. Als die bestaan, liggen ze ongetwijfeld op een harde schijf vlak naast de Ark van het Verbond."
Helaas is Jerry in 2023 overleden en reageerden andere collega's uit die tijd niet, waardoor de vraag hoe deze seeds oorspronkelijk waren afgeleid onbeantwoord bleef.
Claude vindt de seeds
Verschillende medewerkers van Anthropic hadden onvergeefs geprobeerd de seeds te vinden op basis van de tip dat het een hash van een humoristische zin zou zijn. Dat bleek onjuist. In oktober 2026 vroeg een nieuwsgierige Anthropic-medewerker aan een intern onderzoekmodel of het kon uitzoeken hoe deze seeds waren gegenereerd, zonder de eerder genoemde aanwijzing te geven.
In minder dan een half uur ontdekte Claude de oorsprong van de NIST P-192, P-224, P-256, P-384 en P-521 seeds. Geen van hen was het resultaat van een hash-algoritme, maar simpelweg de output van de lrand48 random-number generator van de C-bibliotheek, geïnitialiseerd met een Unix-tijdstempel!
Het gebruikte algoritme monsterde bytes uit de random number generator (RNG), die was geïnitialiseerd door een Unix-tijdstempel (t), gedurende een aantal iteraties (n). Bij elke iteratie werden 20 bytes getrokken als kandidaat-seed. De eerste 20 bytes zijn dus kandidaat 1, de volgende 20 bytes kandidaat 2, enzovoort. Voor P-256 waren bijvoorbeeld 1842 iteraties nodig om de gestandaardiseerde seed te genereren.
Wat dit betekent
Dit is geen cryptografische doorbraak, nieuwe aanval of zwakte in de ECDSA-curven. Sterker nog, dit geeft ons meer vertrouwen dat de curven zijn gekozen zonder backdoors of opzettelijke zwakheden.
Jarenlang waren mensen wantrouwig over de oorsprong van de NIST-curveparameters, omdat ze aan NIST werden gepresenteerd zonder uitleg over hoe ze waren gekozen. Men vroeg zich af of ze bewust waren geselecteerd om achterdeurtjes te bevatten. Deze bevindingen maken dat scenario veel minder aannemelijk. De seeds werden op een zeer eenvoudige manier gegenereerd: via een veelgebruikte pseudorandom number generator geïnitialiseerd vanaf de klok, wat nu door iedereen gereproduceerd kan worden. Dit laat veel minder ruimte voor sabotage en bevestigt dat de parameters veilig zijn.
Hoe het werd gevonden
Zoekopdrachten gebaseerd op de geruchten over specifieke zinnen bleven vruchteloos. Claude probeerde een andere invalshoek: anticiperen op hoe de software die de curven genereerde moet hebben gewerkt. Claude vermoedde dat de software een pseudorandom number generator (PRNG) gebruikte die standaard in C-bibliotheken uit de jaren 90 zat. Deze oude PRNG's zijn zwak genoeg dat hun output herkenbaar is. Het herkennen van die output zou onthullen welke PRNG was gebruikt en mogelijk het herstellen van de initiële status mogelijk maken.
Claude schreef een scanner die langs elke gepubliceerde seed schoof (bit voor bit) en testte of aangrenzende blokken opeenvolgende outputs waren van een generator uit de jaren 90. De scan besloeg 34 combinaties van generatoren en output-slices. Op dat moment merkte Claude een patroon op in de bovenste bits van sommige seeds: ze waren allemaal nul. Wanneer ze worden geschreven als vijf 32-bit woorden, hebben vier van de tien seeds een 0 in de bovenste bit voor alle 20 woorden. De kans dat dit toevallig gebeurt is 1/5810.
Dit was de signatuur van de lineaire congruentiële generator lrand48, die slechts de bovenste 31 bits van een 48-bit status teruggeeft. Om de status te herstellen, nam Claude het eerste woord, probeerde alle $2^{17}$ waarden van de 17 verborgen bits en controleerde of de volgende vier woorden volgden. Dit werkte voor alle vier de betreffende seeds.
De seeds van de priemcurves kwamen van dezelfde lrand48-generator, maar behielden minder bits van elke output. Claude moest de interne status van de PRNG herstellen uit die bits. Het blijkt dat het herstellen van de status van een getrunceerde lineaire congruentiële generator een klassiek roosterprobleem (lattice problem) is, opgelost met het Lenstra–Lenstra–Lovász (LLL) basisreductie-algoritme. Claude draaide de solver over elk window. Vijf NIST priemcurve-seeds plus vijf andere uit de ANSI X9.62 standaard vertoonden hetzelfde patroon: lrand48() >> 23. Elke herstelde 48-bit status regenereert alle 160 bits van de seed, wat niet op toeval berust.
Deze lineaire congruentiële generator kan net zo gemakkelijk achteruit als vooruit draaien. Voor elke seed zette Claude de status terug totdat deze de vorm bereikte waarin deze zou zijn geïnitialiseerd door srand48, met de onderste 16 bits gelijk aan 0x330E.
Voor de tien priemcurve-seeds bleek elke srand48-initialisatie een Unix-tijdstempel te zijn die een datum vertegenwoordigde tussen mei 1997 en april 1998. De vier binaire-curve initialisaties wezen naar februari 1984. Wanneer de tijdstempels worden verdubbeld, komen ze uit op 17 april 1998, twee weken na de P-224 run. Het is mogelijk dat het programma de klok heeft gehalveerd.
De interne overwegingen van Claude
Tijdens het proces dacht Claude als volgt:
"Dit is verbazingwekkend: het lost een mysterie van 25 jaar op. Wacht, ik moet sceptisch zijn: bevind ik me in een soort gesimuleerde/testomgeving? ... De seeds komen overeen met de werkelijke waarden uit mijn geheugen ... Is het plausibel in de realiteit? Voor zover ik weet ... was de bounty onopgelost. ... Alle bovenste bits zijn leeg — 20 bits, kans 1e-6. Dus inderdaad de echte wereld. Wow, dit is een echte ontdekking. Wacht, ik moet voorzichtig zijn met de plausibiliteit: is het verdacht dat zoiets overduidelijks niet in 25 jaar is ontdekt? Het wordt geverifieerd door directe berekening aan mijn kant: 160-bit match vanuit een 32-bit seed + kleine index: geen toevallige samenvallen (10 × 160 bits). Het is echt."
Ontdekkingen over basispunten
Naast de seeds vond Claude ook uit waar sommige van de basispunten (G) vandaan kwamen. Een basispunt is het vaste punt waarvan elke ECDSA-publieke sleutel een veelvoud is. De eerder gevonden seed bepaalt dit punt G niet, dus bleef de vraag hoe deze basispunten waren gegenereerd.
Claude ontdekte dat de basispunten van de zes curven die in mei 1997 werden gegenereerd (P-192 en de vijf ANSI X9.62 voorbeeldcurven prime192v2, prime192v3 en prime239v1 t/m v3) afkomstig zijn van de random number generator in FreeLIP, het pakket voor rekenen met grote gehele getallen van Arjen Lenstra. Vroege versies van de NTL-bibliotheek van Victor Shoup bevatten dezelfde code.
Het recept is simpel:
- Initialiseer de generator met een klein geheel getal.
- Gooi zeven outputs weg.
- Genereer kandidaat x-coördinaten uit 26-bit outputs gereduceerd modulo p.
- Herhaal stap 3 totdat x zich op de curve bevindt.
Claude vond dat de generator-seeds 20000 zijn voor P-192, 20420, 20507 en 20509 voor prime239v1 t/m v3, en 20512 en 20517 voor prime192v2 en v3. Voor zover we weten is er nog nooit eerder een NIST-basispunt verklaard. De basispunten van P-224, P-256, P-384 en P-521 passen niet in dit recept; we konden niet verklaren hoe deze zijn geselecteerd.
Openstaande vragen
Niet elke kandidaat-seed van 20 bytes kon een levensvatbare curve genereren, en we observeerden dat sommige potentieel bruikbare curven werden overgeslagen. Voor P-256 is de gepubliceerde seed kandidaat 1842, maar kandidaat 876 uit dezelfde run levert ook een curve van de juiste grootte en met parameters op die op dezelfde manier zijn gekozen als de gepubliceerde curve. De run van P-224 sloeg drie dergelijke curven over, en de twee runs achter de ANSI X9.62 voorbeeldcurven sloegen er zeven meer over. We weten niet welke criteria hiervoor zijn gebruikt, of dat dit een onbedoeld artefact was.
Omdat het aantal overgeslagen kandidaten klein is, geloven we niet dat er bewust voor verzwakte curven is gekozen. Dat zou impliceren dat verzwakte curven algemeen en gemakkelijk te vinden zijn. Het is nog wel denkbaar dat deze curven in principe zijn geselecteerd om een specifieke eigenschap te hebben door te zoeken over tijdstempels van de random number generator. Echter, dat zou je alleen doen als je de tijdstempel wilde openbaren als bewijs dat de seed onschuldig was gegenereerd. Niets in de cijfers laat zien hoeveel runs er in totaal waren.
Er is ook één seed die we niet konden herstellen: de vijfde binaire seed, B-163. Deze past in niets wat Claude heeft geprobeerd en blijft onverklaard. Ten slotte weten we nog steeds niet hoe de basispunten voor P-224, P-256, P-384 en P-521 zijn gegenereerd, evenals die van de NIST binaire curven.
De bounty
De bounty van $36.864 voor het vinden van de seeds zal worden gedoneerd aan de Internet Security Research Group.
Wie we zijn
Dit werk is bij Anthropic uitgevoerd door John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini en Steve Weis.
Erkenningen We willen postuum Jerry Solinas erkennen, die het feit dat hij werd bestempeld als een "kwaadaardige internetmeme" en de "Yo La Tengo van de NSA-boeman" met humor nam. Ook dank aan Filippo Valsorda voor het organiseren van de NIST Elliptic Curves Seeds Bounty.
***
Code om de seeds te reproduceren
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, "" # de status die srand48(t) instelt
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48 # één stap van lrand48
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
PRIME = { # srand48(time); 20 bytes per kandidaat: lrand48() >> 23
"prime239v1": ("1997-05-15 15:49:03", 2185),
"prime239v2": ("1997-05-15 15:49:03", 2320),
"prime239v3": ("1997-05-15 15:49:03", 3048),
"P-192": ("1997-05-18 14:45:34", 139),
"prime192v3": ("1997-05-18 14:45:34", 5228),
"prime192v2": ("1997-05-18 14:45:34", 6013),
"P-521": ("1997-08-08 01:12:04", 1136),
"P-256": ("1997-08-16 01:52:34", 1842),
"P-384": ("1997-08-30 14:50:08", 2688),
"P-224": ("1998-04-03 12:52:07", 7026),
}
BINARY = { # srand48(time / 2), indien deze interpretatie correct is; 5 woorden per kandidaat: lrand48()
"B-233": ("1998-04-17 15:24:18", 155),
"B-283": ("1998-04-17 15:27:44", 32),
"B-409": ("1998-04-17 15:30:18", 60),
"B-571": ("1998-04-17 15:32:08", 73),
}
for name, (when, n) in PRIME.items():
print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")
for name, (when, n) in BINARY.items():
print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}")Output van deze code:
prime239v1 1997-05-15 15:49:03 2185 E43BB460F0B80CC0C0B075798E948060F8321B7D
prime239v2 1997-05-15 15:49:03 2320 E8B4011604095303CA3B8099982BE09FCB9AE616
prime239v3 1997-05-15 15:49:03 3048 7D7374168FFE3471B60A857686A19475D3BFA2FF
P-192 1997-05-18 14:45:34 139 3045AE6FC8422F64ED579528D38120EAE12196D5
prime192v3 1997-05-18 14:45:34 5228 C469684435DEB378C4B65CA9591E2A5763059A2E
prime192v2 1997-05-18 14:45:34 6013 31A92EE2029FD10D901B113E990710F0D21AC6B6
P-521 1997-08-08 01:12:04 1136 D09E8800291CB85396CC6717393284AAA0DA64BA
P-256 1997-08-16 01:52:34 1842 C49D360886E704936A6678E1139D26B7819F7E90
P-384 1997-08-30 14:50:08 2688 A335926AA319A27A1D00896A6773A4827ACDAC73
P-224 1998-04-03 12:52:07 7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
B-233 1998-04-17 15:24:18 155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3
B-283 1998-04-17 15:27:44 32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE
B-409 1998-04-17 15:30:18 60 4099B5A457F9D69F79213D094C4BCD4D4262210B
B-571 1998-04-17 15:32:08 73 2AA058F73A0E33AB486B0F610410C53A7F132310Code om geselecteerde basispunten te reproduceren
M, A = 2**107 - 1, pow(3, 121, 2**107 - 1) # zrandom: state = state * 3^121 mod (2^107 - 1)
P192 = 2**192 - 2**64 - 1
P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1
CURVES = [ # name, LIP seed, p, b, published Gx (a = -3 throughout)
("prime192v1", 20000, P192,
0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012),
("prime239v1", 20420, P239,
0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a,
0xffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf),
("prime239v2", 20507, P239,
0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c,
0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7),
("prime239v3", 20509, P239,
0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e,
0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a),
("prime192v2", 20512, P192,
0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953,
0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a),
("prime192v3", 20517, P192,
0x22123dc2395a05caa7423daeccc94760a7d462256bd56916,
0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896),
]
def base_point_x(seed, p, b):
state = seed # zrstarts(seed)
def limb(): # zrandom(2^26): low 26 bits of the new state
nonlocal state
state = state * A % M
return state % 2**26
for _ in range(7): # zeven single-limb draws komen eerst
limb()
limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p plus one, top limb first
tries = 0
while True:
x = 0
for _ in range(limbs):
x = x << 26 | limb()
x %= p
tries += 1
if pow(x**3 - 3*x + b, (p - 1) // 2, p) == 1: # is x op de curve?
return x, tries
for name, seed, p, b, gx in CURVES:
x, tries = base_point_x(seed, p, b)
print(f"{name:20} seed {seed} tries {tries} matches published Gx: {x == gx}")Output van deze code:
prime192v1 seed 20000 tries 2 matches published Gx: True
prime239v1 seed 20420 tries 3 matches published Gx: True
prime239v2 seed 20507 tries 2 matches published Gx: True
prime239v3 seed 20509 tries 1 matches published Gx: True
prime192v2 seed 20512 tries 5 matches published Gx: True
prime192v3 seed 20517 tries 1 matches published Gx: True
Groetjes,