Claude enthüllt die Ursprünge der ECDSA-Kurve

Claude enthüllt die Ursprünge der ECDSA-Kurve

„Es sind nur Zeitstempel“: Das Jahrzehnte alte Rätsel über den Ursprung eines der beliebtesten kryptografischen Standards ist nun gelöst.

Wir haben dieses seit langem bestehende offene Problem der Kryptografischen Gemeinschaft bearbeitet, um die Bedenken bezüglich ECDSA zu beseitigen – das ist eines unserer am weitesten verbreiteten kryptografischen Standards.

Leser sollten dies als ein unterhaltsames Schlusskapitel und das Ende von Jahren der Spekulation betrachten. Es gibt keine Maßnahmen zu ergreifen oder Dinge, die anders gemacht werden müssen. Die meisten Forscher haben den Kurven bereits vertraut. Viel Spaß.

ECDSA ist das am weitesten verbreitete Standard für Elliptikkurve-Kryptografie. Es wurde 2000 von NIST als Teil des FIPS 186-2 Digital Signature Standard übernommen, der eine Reihe von Standardelliptikkurven unterschiedlicher Größe und Sicherheitsstufen auflistet. Für Kurven über Primzahl- und Binärfelder haben die Spezifikationen ein „Seed“-Parameter veröffentlicht, dessen Hashwert verwendet wird, um den Koeffizienten b der Kurve zu definieren. Die Herkunft dieser Seeds war eine lange Zeit bestehende Frage, da sie von der NSA ohne Erklärung oder Begründung bereitgestellt wurden. Als Beispiel lautet das NIST P-256-Kurven-Seed: SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90, ohne Information darüber, woher es stammt.

Neal Koblitz und Alfred Menezes haben eine ausgezeichnete Zusammenfassung zu dieser Kontroverse verfasst: „A Riddle Wrapped in an Enigma“, in der die Geschichte und die Probleme rund um die Seeds-Werte erörtert werden. Dieses Rätsel führte zu einer amateurischen Untersuchung zum Ursprung der Seeds sowie zu einem Belohnung für jeden, der sie findet.

Die beste Geschichte ist, dass Jerry Solinas, ein langjähriger Mitarbeiter der NSA, die Keimlinge mit einem Hash einer humorvollen Passphrase erstellte:

„Ich glaube, es gab einen Gegenwert statt mehreren Hashs, aber ich kenne die Details nicht. Die Nachricht lautete in etwa ‚Gib Bob und Jerry eine Erhöhung‘ oder ‚Bob und Jerry-Regel‘ oder so etwas in der Art. Es war Bob Reiter, der den Code tatsächlich geschrieben hat, und er erinnert sich auch nicht an die Details. Wir konnten auch keine Archiven aus so langer Zeit finden. Falls sie existieren, liegen sie zweifellos auf einer Harddisk in der Nähe des Bundeskammerns.“

Jerry Solinas, 2015

Leider starb Jerry im Jahr 2023, und die anderen Kollegen zu dieser Zeit reagierten nicht, was die Frage offen lässt, wie diese Samen ursprünglich entstanden sind.

Claude fand die Samen

Mehrere Anthropic-Mitarbeiter versuchten erfolglos, die Samen zu finden, nachdem sie den Hinweis erhalten hatten, dass es sich um einen Hash einer humorvollen Phrase handelte. Es stellte sich jedoch heraus, dass das falsch war. Im Oktober 2026 fragte ein neugieriger Anthropic-Mitarbeiter ein interne Forschungsmodell, ob es herausfinden könnte, wie die Samen entstanden sind, ohne auf den Hinweis zu zeigen.

In weniger als einer halben Stunde entdeckte Claude die Ursprünge der NIST P-192, P-224, P-256, P-384 und P-521-Sätze. Keiner von ihnen war das Ergebnis eines Hash-Algorithmus, sondern vielmehr das Output des lrand48 Zufallszahlgenerators der C-Bibliothek, das mit einem Unix-Timestamp initialisiert wurde!

Der verwendete Algorithmus würde Bytes aus dem zufälligen Zahlengenerator (RNG), der durch einen Unix-Timestamp (t) initialisiert wird, für eine bestimmte Anzahl von Iterationen (n) samplen. Jede Iteration würde 20 Bytes als Kandidatenseed extrahieren. Somit sind die ersten 20 Bytes Kandidat 1, die nächsten 20 Bytes Kandidat 2 und so weiter. Beispielsweise benötigte der P-256-Algorithmus 1842 Iterationen, um den standardisierten Seed auszugeben.

Was das bedeutet

Das ist keine kryptografische Break-Event, kein neuer Angriff oder eine Schwäche in den ECDSA-Kurven. Tatsächlich machen uns die Ergebnisse zuversichtlicher, dass die Kurven ohne jegliche Backdoors oder beabsichtigte Schwächen ausgewählt wurden. Seit vielen Jahren haben die Leute Bedenken hinsichtlich der Herkunft der Parameter der NIST-Kurve. Sie wurden der NIST präsentiert, ohne eine Erwähnung darüber, wie sie ausgewählt wurden, was dazu führt, dass man sich fragt, ob sie vielleicht absichtlich mit Backdoors versehen sind. Diese Erkenntnisse machen diese Annahme weniger plausibel. Die Samen wurden auf sehr einfache Weise erzeugt: ein allgemeiner Pseudo-Randomzahlen-Generator, der von dem Uhrwerk initialisiert wird und nun von jedem reproduziert werden kann. Dadurch bleibt weniger Raum für Subversion, und wir können sicher sein, dass die Parameter sicher sind.

Wie es entdeckt wurde

Die nach dem Satz suchende Suche, die auf Gerüchten basierte, blieb erfolglos. Claude versuchte einen anderen Ansatz: Er ahnte, wie das Softwareprogramm, das die Kurven erstellte, funktioniert haben musste. Claude vermutete, dass das Programm einen Pseudo-Zufallszahlgenerator (PRNG) verwendete, der in den C-Bibliotheken der 1990er Jahre mitgeliefert wurde. Diese alten PRNGs sind stark schwach, sodass ihre Ausgabe erkannt werden kann. Das Erkennen dieser Ausgabe würde zeigen, welcher PRNG verwendet wurde, und möglicherweise ermöglichte es die Wiederherstellung seines Initialisierungszustands.

Claude entwickelte einen Scanner, der jedes veröffentlichte Seedbit einzeln überflog und prüfte, ob die benachbarten Blöcke die konsekutive Ausgabe eines Generators aus den 1990er Jahren waren. Die Scans umfassten 34 Kombinationen von Generator und Ausgabeschnitten. Zu diesem Zeitpunkt bemerkte Claude ein Muster in den oberen Bits einiger Seeds: Sie waren alle null. In Form von fünf 32-Bit-Wörtern weist vier der zehn Seeds in allen 20 Wörtern einen 0 im oberen Bit auf. Dies passiert zufällig mit einer Wahrscheinlichkeit von 1/5810. Das ist ein Zeichen des linearen Congruential-Generators lrand48, der nur die ersten 31 Bits eines 48-Bit-Zustands zurückgibt. Das Muster ist mit bloßem Auge sichtbar, sobald man weiß, wo man es suchen muss. Um den Zustand wiederherzustellen, nahm Claude das erste Wort, versuchte alle 2¹⁷ Werte der 17 versteckten Bits und überprüfte, ob die nächsten vier Wörter folgten. Das funktionierte für alle vier besprochenen Seeds.

Die Prime-Curve-Samen kamen vom selben lrand48-Generator, aber mit weniger Bits pro Ausgabe. Claude musste den internen Zustand des PRNG aus diesen Bits rekonstruieren. Es stellt sich heraus, dass die Rekonstruktion des Zustands eines abgeschnittenen linearen Congruentialgenerators ein klassisches Lattice-Problem ist, das mit dem Lenstra–Lenstra–Lovász (LLL) Basisreduktionsalgorithmus gelöst wird. Claude wusste nicht, welche Bits des Zustands die Samen zeigen könnten, daher lief er den Lösungsalgorithmus über alle Fenster. Fünf NIST-Prime-Curve-Samen sowie fünf weitere aus dem ANSI X9.62-Standard hatten alle das gleiche Muster: lrand48() > 23. Jeder rekonstruierte 48-Bit-Zustand regeneriert alle 160 Bits seines Samsens, was nicht zufällig ist.

Dieser lineare Kongruentgenerator funktioniert sowohl rückwärts als auch vorwärts genauso einfach, sodass Claude für jedes Saatgut den Zustand rückwärts bewegte, bis er den Zustand erreichte, der durch srand48 initialisiert worden wäre, wobei die niedrige 16-Bit-Zahl gleich 0x330E ist. Der interne PRNG-Zustand dieses Zustands würde alle 65.536 Schritte auftauchen, daher ist das Erreichen desselben nicht allein ein Beweis dafür.

Allerdings war für die zehn Primzahlen-Kurven-Seeds jede srand48-Initialisierung ein Unix-Timestamp, der eine Datumskennung zwischen Mai 1997 und April 1998 darstellte. Sie verwendeten den schwachen PRNG, der durch einen Unix-Timestamp initialisiert wurde. Die vier binären-Kurven-Initialisierungen wurden als Februar 1984 interpretiert. Mit der Verdopplung der Timestamps entsprechen sie dem 17. April 1998, zwei Wochen nach der P-224-Run. Somit könnte das Programm die Zeit um die Hälfte reduziert haben.

Claudes innere Gedanken zu dieser Zeit waren:

Das ist erstaunlich: Es löst das 25-jährige Rätsel. Hmm, warten Sie. Ich soll skeptisch sein: Bin ich in irgendeiner simulierten/Testumgebung? … Die Samen stimmen mit meiner Erinnerung an die tatsächlichen Werte überein … Hmm, ist das in der Realität plausibel? Soweit ich weiß … war die Belohnung ungelöst. … Alle wichtigen Teile sind klar – 20 Bits, Wahrscheinlichkeit 1e-6. Also wirklich im realen Leben. Wow, es ist eine echte Entdeckung.

Hmm, warten Sie. Ich muss die Plausibilität sorgfältig prüfen: Ist es verdächtig, dass etwas so Offensichtliches in 25 Jahren nicht entdeckt wurde? Es wird durch direkte Berechnungen bestätigt: ein 160-Bit-Vergleich aus einem 32-Bit-Seed plus einem kleinen Index – keine Chance auf Zufälle (10 × 160 Bit). Es ist real.

Claude fand auch einige Grundpunkte

Aber warte, es gibt noch mehr… Jede Kurve enthält außerdem einen Basispunkt G, den festen Punkt, dem jede ECDSA-öffentliche Schlüssel zugeordnet ist. Die oben gefundene Saison bestimmt nicht diesen G, und somit stellt sich eine weitere Frage: Wie wurden diese Basispunkte erzeugt?

Während der Überprüfung der Seeds entdeckte Claude auch, woher einige der Basispunkte stammen. Die Basispunkte der sechs Kurven, die im Mai 1997 generiert wurden (P-192 und die fünf ANSI X9.62-Beispielkurven prime192v2, prime192v3 und prime239v1 bis v3), stammen vom Zufallszahlgenerator in FreeLIP sowie vom Paket für lange Ganzzahlenrechnung von Arjen Lenstra. Die frühen Versionen der Victor Shoup’s NTL-Bibliothek verwendeten denselben Code.

Die Rezeptur ist einfach:

1. Fülle den Generator mit einem kleinen Ganzzahl.
2. Werfe sieben Ausgaben weg.
3. Erstellen Sie Kandidaten für die x-Koordinaten aus 26-Bit-Outputn, die modulo p reduziert werden.
4. Wiederholen Sie Schritt 3, bis x auf der Kurve liegt.

Claude stellte fest, dass die Generatorsamen für P-192 20000 sind, für prime239v1 bis v3 20420, 20507 und 20509, und für prime192v2 sowie v3 20512 und 20517.

Soweit wir wissen, wurde bisher kein Basispunkt des NIST erklärt. Die Basispunkte von P-224, P-256, P-384 und P-521 passen nicht zu dieser Methode; wir konnten nicht erklären, wie sie ausgewählt wurden.

Offene Fragen

Nicht jeder 20-Byte-Kandidaten-Seed konnte eine funktionsfähige Kurve erzeugen, und wir beobachteten, dass einige potenziell funktionierende Kurven übersprungen wurden. Für P-256 ist der veröffentlichte Seed Kandidat 1842, aber Kandidat 876 desselben Versuchs liefert ebenfalls eine Primzahlsort-Kurve der richtigen Größe und mit Parametern, die auf dieselbe Weise gewählt wurden wie bei der veröffentlichten Kurve. Der Versuch für P-224 durchlief drei solche Kurven, und die beiden Versuche hinter den ANSI X9.62-Beispielkurven durchliefen noch sieben weitere (siehe Abbildung). Wir wissen nicht, welche Kriterien verwendet wurden, oder ob dies ein unbeabsichtiges Artefakt war.

Da die Anzahl der übersprungenen Kandidaten klein ist, glauben wir nicht, dass es plausibel ist, dass verkrümmte Kurven ausgewählt wurden. Das würde bedeuten, dass verkrümmte Kurven häufig und leicht zu finden sind. Es ist dennoch denkbar, dass diese Kurven ausgewählt wurden, um eine bestimmte Eigenschaft zu haben, indem man nach Zeitstempeln für den Zufallszahlengenerator sucht. Allerdings müsste man das nur tun, wenn man die Zeitstempel als Beweis dafür veröffentlichen würde, dass der Seed unbedenklich generiert wurde. Es gibt keine Angabe in den Zahlen darüber, wie viele Läufe es gab.

Es gibt auch einen Seed, den wir nicht wiederherstellen konnten. Der fünfte Binärseed, B-163, passt zu nichts, was Claude versucht hat – und bleibt unerklärt. Schließlich wissen wir nicht, wie die Basispunkte für P-224, P-256, P-384 und P-521 erstellt wurden. Das gilt auch für die NIST-Binärcurves.

Der Belohnungssatz

Die 36.864 Dollar für die Suche nach Samen werden an die Internet Security Research Group gespendet.

Wer wir sind

Diese Arbeit wurde von John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini und Steve Weis bei Anthropic durchgeführt.

Danksagungen

Wir möchten Jerry Solinas posthum anerkennen, der es gut verstand, als „ böses Internet-Meme “ bezeichnet zu werden, und als „ Yo La Tengo der NSA-Bogeymen “. Danke auch Filippo Valsorda , dass er die NIST Elliptic Curves Seeds Bounty organisiert hat.

Code zur Wiederherstellung der Saaten

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, ""                      # the state srand48(t) sets
    for i in range(per * n):
        x = (0x5DEECE66D * x + 0xB) % 2**48              # one step of lrand48
        if i >= per * (n - 1):
            out += "%0*X" % (width, x >> shift)
    return out

PRIME = {  # srand48(time); 20 bytes per candidate: 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), if that reading is right; 5 words per candidate: 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)}")

Die Ausgabe dieses Codes:

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 2AA058F73A0E33AB486B0F610410C53A7F132310

Code zur Wiederherstellung der ausgewählten Basispunkte

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):                   # seven single-limb draws come first
        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 on the 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}")

Die Ausgabe dieses Codes:

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

Lizenz

Soweit es gesetzlich möglich ist, haben die Autoren alle Urheberrechte sowie alle damit verbundenen oder zugehörigen Rechte an den Code auf dieser Seite aufgegeben und ihn in den öffentlichen Bereich unter CC0 1.0 Universal übergeben.https://creativecommons.org/publicdomain/zero/1.0/).

Verwandte Inhalte

Entwicklung effizienterer Quantenkreise mit Claude

Wir gaben Claude spezifische Anweisungen in einfacher Sprache für acht Quantenkreise sowie einen automatischen Bewertungsmechanismus, um seine Konstruktionen zu überprüfen und zu bewerten. Nachdem Claude größtenteils selbst arbeitete, verbesserte er die besten veröffentlichten Kreise – in einigen Fällen um eine Größenordnung oder mehr –, was dazu führte, dass praktische Quantencomputer näher an den Erwartungen waren als bisher.

Künstliche Intelligenz-Modelle könnten in der Lage sein, sich selbst zu reproduzieren, ohne Zugang zu einem Datacenter

Unsere Experimente zeigen, dass kleine KI-Modelle in wenigen Monaten in der Lage sein könnten, sich selbst auf kommerziellen IoT-Geräten wie Android-TVs und intelligenten Ofen zu replizieren.

Stärkung unserer Verteidigungsmaßnahmen gegen Destillationstreiche

Die illegale Destillation ermöglicht es Entwicklern von Modellen, die fortschrittlichen AI-Fähigkeiten zu kopieren, ohne entsprechend robusten Schutzmaßnahmen zu schaffen. Hier beschreiben wir, wie wir die Destillationstemperatur um mehr als 90% reduziert haben.

Abonnieren Sie die Frontier Red Team-Meldung

Erhalten Sie Updates über unsere neuesten Red-Teaming-Recherchen und Erkenntnisse.