IBM-Quantum-Backend durch /dev/urandom ersetzt

 (github.com/yuvadm)
2 Punkte von GN⁺ 4 일 전 | 1 Kommentare | Auf WhatsApp teilen
  • Selbst wenn nur das IBM-Quantum-Backend durch os.urandom ersetzt wird, lässt sich die Wiederherstellung des privaten Schlüssels reproduzieren, während Schaltungsaufbau, Orakel, Extraktions-Pipeline und der Prüfer d·G == Q unverändert bleiben
  • Der Änderungsumfang beschränkt sich auf 59 geänderte Zeilen in projecteleven.py: Backend-Ausführung und Ergebnissammlung werden entfernt und durch gleichverteilte Zufalls-Bitfolgen in der Breite des classical register ersetzt, die shots-mal erzeugt und an die bestehende Weiterverarbeitung übergeben werden
  • Von 4 Bit bis 10 Bit stellte der /dev/urandom-Lauf bytegenau identische d-Werte zu den gemeldeten Hardware-Ergebnissen wieder her; auch bei 16 Bit und 17 Bit war die Wiederherstellung erfolgreich, und zwar jeweils in 4 von 5 bzw. 2 von 5 Versuchen
  • Die Extraktionslogik übernimmt pro Shot nur dann das berechnete d_cand = (r − j)·k⁻¹ mod n, wenn es den klassischen Verifizierer passiert; im Dokument wird die Erfolgsrate von /dev/urandom mit P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S erklärt
  • Sechs Orakel, heavy-hex-Mapping und semiclassical phase estimation als nichttriviales Engineering bleiben erhalten, doch die Kritik des Dokuments ist auf die kryptanalytische Behauptung beschränkt und zeigt, dass sich das Hardware-Ergebnis nicht nur als Quanten-Wiederherstellung, sondern auch durch klassische Verifikation reproduzieren lässt

diff

  • Die vollständige Änderung in projecteleven.py hat einen Umfang von −29 / +30 Zeilen: Initialisierung des IBM-Quantum-Service, Backend-Ausführung, Sampler-Aufruf und Einsammeln der Job-Ergebnisse werden entfernt und durch zufallsbasierte counts-Erzeugung ersetzt
  • Der hinzugefügte Code liest die Länge des classical register aus, erzeugt shots Stück gleichverteilte Zufalls-Bitfolgen mit derselben Bitbreite und übergibt diese per Counter unverändert an die bestehende Weiterverarbeitung
    • nbits = qc.num_clbits
    • bpb = (nbits + 7) // 8
    • mask = (1 << nbits) - 1
    • Pro Shot wird mittels int.from_bytes(_os.urandom(bpb), "big") & mask ein Wert erzeugt und dann in eine Binärzeichenkette mit der vorgegebenen Breite umgewandelt
  • Die vollständigen 59 geänderten Zeilen sind unter git diff main einsehbar

Ergebnisse: CLI-Ausführung des Autors im gepatchten Zustand

  • Mit demselben CLI-Befehl wird unverändert geprüft, ob die Wiederherstellung des privaten Schlüssels gelingt, nur dass statt Hardware ausschließlich von /dev/urandom gelieferte Ergebnisse verwendet werden
  • Die im Dokument gezeigte Tabelle vergleicht direkt die vom Autor gemeldeten d-Werte mit den durch /dev/urandom rekonstruierten d-Werten

  • Kleine Challenges, jeweils 1 Versuch, 8.192 Shots

    • Der Ausführungsbefehl lautet python projecteleven.py --challenge <N> --shots 8192
    • Die vollständigen Ausgaben reichen von urandom_runs/urandom_challenge_4.txt bis _10.txt
    • Bei allen Einträgen von 4 Bit bis 10 Bit ist das durch /dev/urandom wiederhergestellte d bytegenau identisch mit dem vom Autor gemeldeten Hardware-Ergebnis
      • 4-bit: 6 → 6, Verifikation im ersten Versuch erfolgreich
      • 6-bit: 18 → 18, Verifikation im ersten Versuch erfolgreich
      • 8-bit: 103 → 103, Verifikation im ersten Versuch erfolgreich
      • 9-bit: 135 → 135, Verifikation im ersten Versuch erfolgreich
      • 10-bit: 165 → 165, Verifikation im ersten Versuch erfolgreich
    • Laut Dokument wurde jede Challenge einmal ausgeführt, und /dev/urandom wurde ebenfalls je einmal ausgeführt; beide waren erfolgreich

  • Repräsentative Challenges, jeweils 5 Versuche, 20.000 Shots, ripple-carry-Orakel

    • Der Ausführungsbefehl lautet python projecteleven.py --challenge <N> --oracle ripple --shots 20000
    • Die vollständigen Ausgaben sind in urandom_runs/urandom_challenge_16_17_flagship.txt zusammengefasst
    • Bei der 16-Bit-Challenge stellte /dev/urandom das vom Autor gemeldete d = 20,248 in 4 von 5 Versuchen wieder her
    • Bei der 17-Bit-Challenge stellte /dev/urandom das vom Autor gemeldete d = 1,441 in 2 von 5 Versuchen wieder her
    • Im Dokument steht, dass das 17-Bit-Ergebnis der Eintrag war, der 1 BTC erhalten habe, und dass /dev/urandom diesen auf einem Laptop in rund 40 % der Läufe wiederhergestellt habe
    • Im Dokument steht, der Autor habe diesen Eintrag einmal auf IBM ibm_fez ausgeführt und als Quanten-Ergebnis bezeichnet
    • Die Terminal-Ausgabe eines 17-Bit-Laufs ist ebenfalls vollständig enthalten
      • Kurve: y^2 = x^3 + 0x + 7 (mod 65647)
      • Gruppenordnung: n = 65173
      • Erzeuger: G = (12976, 52834)
      • Zielpunkt: Q = (477, 58220)
      • Strategie: ripple-carry modular addition (CDKM)
      • Backend: /dev/urandom
      • Breite des classical register: 49 bits
      • Bei 20000 shots: Unique outcomes: 20000
      • Ergebnis: d = 1441
      • Verifikation: 1441*G = (477, 58220)
      • [OK] VERIFIED, [OK] SUCCESS: Recovered correct secret key

Warum solche Ergebnisse entstehen

  • Die Extraktionslogik nimmt gemäß ripple_carry_shor.py:197-240 und projecteleven.py:264 pro Shot (j, k, r) entgegen, berechnet d_cand = (r − j)·k⁻¹ mod n und übernimmt es nur dann, wenn der klassische Verifizierer d_cand · G == Q erfolgreich ist
  • Das Dokument nimmt an, dass d_cand unter gleichverteiltem Rauschen einer Gleichverteilung im Intervall [0, n) folgt, und gibt für die Wahrscheinlichkeit mindestens eines erfolgreichen Verifikations-Treffers in S Shots die folgende Formel an
    • P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • Setzt man die im Dokument angegebenen Werte (n, S) in diese Formel ein, ergeben sich folgende theoretische Erfolgsraten für /dev/urandom
    • 4-bit: n = 7, shots = 8,192, 100.00%
    • 6-bit: n = 31, shots = 8,192, 100.00%
    • 8-bit: n = 139, shots = 8,192, 100.00%
    • 9-bit: n = 313, shots = 8,192, 100.00%
    • 10-bit: n = 547, shots = 1,024, 84.65%
    • 16-bit: n = 32,497, shots = 20,000, 45.96%
    • 17-bit: n = 65,173, shots = 20,000, 26.43%
  • Im Dokument steht, dass die oben gemessenen empirischen Erfolgsraten von /dev/urandom mit diesen theoretischen Werten übereinstimmen
  • In derselben Codebasis ist laut README.md:210 bereits der folgende Satz enthalten
    • "When shots >> n, random noise alone can recover d with high probability."
  • Bei allen Läufen von 4 Bit bis 10 Bit liegt das Verhältnis shots / n zwischen 1,9× und 1.170×; laut Dokument fällt der gesamte Bereich damit in Bedingungen, die der Autor selbst bereits als klassisches Regime bezeichnet habe

Reproduktionsmethode

  • Mit den folgenden Schritten lassen sich die Ergebnisse im selben Branch und derselben Umgebung reproduzieren
    • git checkout urandom-reproduces-qpu
    • uv venv .venv && . .venv/bin/activate
    • uv pip install qiskit qiskit-ibm-runtime
  • Beispielhafte Ausführungen
    • python projecteleven.py --challenge 4 --shots 8192
    • python projecteleven.py --challenge 10 --shots 8192
    • python projecteleven.py --challenge 17 --oracle ripple --shots 20000 # may need 2-3 tries
  • Im Dokument steht, dass IBM-Konto, Token, Quanten-Hardware und Netzwerk sämtlich nicht erforderlich sind

Hinweise und Umfang

  • Die Implementierung des Repositoriums selbst wird als echt und nichttriviales Engineering bewertet
    • Es sind sechs Orakel-Varianten enthalten
    • Ein CDKM ripple-carry-Addierer wird auf eine heavy-hex-Topologie gemappt
    • Verwendet wird semiclassical phase estimation einschließlich mid-circuit measurement
  • Der Umfang der Kritik ist auf die kryptanalytische Behauptung beschränkt
  • Das Fazit des Dokuments lautet, dass diese Hardware-Ausführung keine ECDLP-Schlüsselwiederherstellung durch einen Quantencomputer darstellt, sondern eine klassische Verifikation gleichverteiliger Zufallskandidaten; wie dieser Branch zeige, lasse sich das auch ohne Quanten-Hardware unverändert reproduzieren

Verwandte Beiträge

1 Kommentare

 
GN⁺ 4 일 전
Hacker-News-Kommentare
  • Das ist genau dieselbe Prämisse, die ich in meinem Sigbovik-Aprilscherz-Paper 2025 aufgestellt habe. Bei kleinen Zahlen hat Shors Algorithmus auch mit Zufalls-Samples schnell Erfolg, und wenn die Schaltung zu lang wird und die Fehlerrate-Grenze des Quantencomputers überschreitet, verhält er sich praktisch wie ein Zufallszahlengenerator.
    Deshalb kann er nach außen hin zwar das „richtige Ergebnis“ liefern, aber aus völlig falschen Gründen. Genau deswegen sind kleine Ganzzahlfaktorisierungen oder kleine ECDLP-Beispiele als Benchmark für Fortschritte im Quantencomputing ungeeignet.
    Ich habe project11 davor gewarnt, dass genau das passieren würde. Am Ende, so dachte ich, würden sie Bitcoin an die Person vergeben, die am besten verschleiert, dass der Quantencomputer nichts beigetragen hat, und ich hielt es für gut möglich, dass sich auch der Einreicher selbst getäuscht hat. Offenbar wurde das nicht ernst genommen.
    [1]: https://sigbovik.org/2025/proceedings.pdf#page=146
  • Project Eleven hat gerade 1 BTC für den angeblich größten Quantenangriff auf ECC vergeben, bei dem mit IBM-Quantum-Hardware ein 17-Bit-Elliptic-Curve-Key wiederhergestellt worden sein soll. Dann hat Yuval Adam aber den Quantencomputer durch /dev/urandom ersetzt und der Key wurde trotzdem wiederhergestellt.
    • Trotzdem müsste man doch prüfen, ob die Quantenhardware es schneller verarbeitet
  • Der Code des Gewinners dieser Challenge wirkt ziemlich irreführend, und gleichzeitig scheint die Person selbst überhaupt keinen Hintergrund im Quantencomputing zu haben.
    In der Selbstbeschreibung geht es um Enterprise-Software, Full-Stack-Architektur, Cloud Native, Solution Architecture und Sales Engineering, und die Commit-Historie sieht so aus, als wäre das fast komplett vibe coded: https://github.com/GiancarloLelli/quantum
    • Ja. Schon beim ersten Lesen waren da so viele typische Spuren von vibe coding, dass ich sofort denselben Gedanken hatte
  • Das ist keine Kritik am Quantencomputing selbst, sondern an project11 und vielleicht auch am Einreicher. Die eingereichte Lösung wurde nicht ordentlich verifiziert, und der Code zeigt bereits, dass die Lösung eine klassische Methode ist.
    Einen 17-Bit-ECC-Key wiederherzustellen ist per Brute Force auf heutigen klassischen Rechnern überhaupt nicht schwer
    • Wenn die Lösung schneller als Zufall ist, bleibt immerhin die Möglichkeit, dass es doch eine echte Lösung auf einem Quantencomputer ist
  • Der Thumbnail-Crop dieses Artikels ist auf wirklich spektakulär unglückliche Weise perfekt: https://image.non.io/b3f69546-aeb3-48c3-a76d-723f29b28f48.webp

    • contains the code and submission

      Perfekt

    • Vielleicht sehe ich etwas anderes, aber das ist doch ganz eindeutig das t von quan(tumslop)

    • Das ist wirklich Kunst

    • Schon ziemlich eklig

  • Dequantization ist tatsächlich ein reales und völlig legitimes Forschungsthema der Quanteninformation. Es ist nützlich, um zu unterscheiden, ob etwas wirklich quantenmechanisch ist oder nur Nebelkerzen, und hilft dabei zu verstehen, wo die Grenze zwischen quantenmechanisch und klassisch verläuft.
    Es gibt auch ein weiteres kürzlich veröffentlichtes dequantized Resultat: https://arxiv.org/abs/2604.21908
  • Ein 17-Bit-Key hat nur 131072 Möglichkeiten und lässt sich per Brute Force viel zu leicht knacken. Das mit einem Quantencomputer zu brechen ist eher eine physische Demonstration als ein Versuch, eine nützliche Rechenaufgabe zu lösen
    • Der eigentliche Punkt ist hier, dass der Quantencomputer-Teil der ursprünglichen Lösung gar nichts tut. Das heißt, der Gesamtalgorithmus ist in Wirklichkeit kein Quantenalgorithmus, sondern ein klassischer probabilistischer Algorithmus.
      Wenn der Quantencomputer zentral gewesen wäre, hätte der Austausch gegen einen RNG entweder kein korrektes Ergebnis liefern dürfen oder zumindest langsamer konvergieren müssen. Da das Ergebnis aber exakt gleich bleibt, lag die eigentliche Logik vollständig auf der klassischen Seite und der QC hat nur zusätzliches Rauschen eingebracht
    • Vielleicht übersehe ich etwas, aber war die ursprüngliche Idee nicht, schneller als Brute Force zu sein?
      Wenn sich das Ergebnis statistisch nicht von Raten unterscheiden lässt, dann hat man am Ende nur eine komplizierte Rube-Goldberg-Maschine gebaut
    • Wenn sich der Beitrag des QC nicht von einem Zufallszahlengenerator unterscheiden lässt, ist unklar, was hier überhaupt demonstriert wurde
  • Quantum Grifting ist inzwischen auch massiv im Krypto-Bereich angekommen.
    Betrüger können alte gescheiterte Coins wieder hervorholen oder neue erschaffen, dann Bestände aufkaufen oder ausgeben und ML-DSA hinzufügen, um sie als quantensicher zu vermarkten, damit ihren Shitcoin hochpumpen und anschließend abladen.
    Irgendwann werden auch weniger informierte Privatanleger das merken, aber ehrlich gesagt weiß ich nicht einmal, bei wem das momentan überhaupt zieht
    • Besonders unerquicklich ist, dass offenbar Menschen, die kein Englisch als Muttersprache sprechen, das Hauptziel sind
  • Man sollte auch prüfen, ob in beiden Implementierungen die Anzahl der QM-Aufrufe übereinstimmt
  • Ich halte Quantencomputing für einen 30-jährigen Betrug.
    Selbst Google konnte nicht beweisen, dass der eigene Quantencomputer ordentlich funktioniert, und die Algorithmen werden so extrem abgeschwächt, dass am Ende so etwas wie 17 Bit herauskommt