Remplacer le backend IBM Quantum par /dev/urandom

 (github.com/yuvadm)
2 points par GN⁺ 4 일 전 | 1 commentaires | Partager sur WhatsApp
  • Même en remplaçant uniquement le backend IBM Quantum par os.urandom, la récupération de la clé privée reste reproductible sans changer la construction du circuit, l’oracle, le pipeline d’extraction ni le vérificateur d·G == Q
  • La modification se limite à 59 lignes changées dans projecteleven.py : suppression de l’exécution sur le backend et de la collecte des résultats, puis génération de chaînes de bits aléatoires uniformes adaptées à la largeur du registre classique pour les transmettre au post-traitement existant, shots fois
  • De 4 bits à 10 bits, l’exécution avec /dev/urandom a retrouvé des valeurs de d identiques octet pour octet à celles rapportées pour le matériel ; pour 16 bits et 17 bits, la récupération réussit respectivement 4 fois sur 5 et 2 fois sur 5
  • La logique d’extraction retient, pour chaque shot, d_cand = (r − j)·k⁻¹ mod n uniquement si le vérificateur classique l’accepte ; le document explique le taux de réussite avec /dev/urandom par P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • Des éléments d’ingénierie non triviaux comme six oracles, le mapping heavy-hex ou la semiclassical phase estimation sont conservés, mais la critique du document se limite à l’affirmation cryptanalytique : les résultats d’exécution sur matériel seraient reproductibles non pas par récupération quantique, mais aussi par vérification classique

diff

  • L’ensemble des modifications de projecteleven.py représente −29 / +30 lines : l’initialisation du service IBM Quantum, l’exécution sur le backend, l’appel au sampler et la collecte des résultats sont retirés puis remplacés par une génération de counts fondée sur l’aléatoire
  • Le code ajouté lit la longueur du registre classique du circuit, produit shots chaînes de bits aléatoires uniformes de cette largeur, puis les agrège avec Counter avant de les transmettre telles quelles au post-traitement existant
    • nbits = qc.num_clbits
    • bpb = (nbits + 7) // 8
    • mask = (1 << nbits) - 1
    • À chaque shot, la valeur est construite via int.from_bytes(_os.urandom(bpb), "big") & mask, puis convertie en chaîne binaire à largeur fixe
  • Le détail complet des 59 lignes modifiées est disponible dans git diff main

Résultats : exécution CLI de l’auteur avec le patch

  • En réutilisant exactement les mêmes commandes CLI, le document vérifie si la clé privée peut être récupérée avec des résultats fournis par /dev/urandom au lieu du matériel
  • Le tableau présenté compare directement les valeurs de d rapportées par l’auteur avec celles retrouvées via /dev/urandom

  • Petits challenges, 1 essai chacun, 8 192 shots

    • La commande utilisée est python projecteleven.py --challenge <N> --shots 8192
    • Les sorties complètes vont de urandom_runs/urandom_challenge_4.txt à _10.txt
    • Pour tous les cas de 4 bits à 10 bits, le d retrouvé par /dev/urandom est identique octet pour octet au résultat matériel rapporté par l’auteur
      • 4-bit: 6 → 6, vérification réussie au premier essai
      • 6-bit: 18 → 18, vérification réussie au premier essai
      • 8-bit: 103 → 103, vérification réussie au premier essai
      • 9-bit: 135 → 135, vérification réussie au premier essai
      • 10-bit: 165 → 165, vérification réussie au premier essai
    • D’après le document, chaque challenge n’a été exécuté qu’une fois, et /dev/urandom aussi une seule fois ; dans les deux cas, c’est un succès

  • Challenges phares, 5 essais chacun, 20 000 shots, oracle ripple-carry

    • La commande utilisée est python projecteleven.py --challenge <N> --oracle ripple --shots 20000
    • Les sorties complètes sont regroupées dans urandom_runs/urandom_challenge_16_17_flagship.txt
    • Pour le challenge 16 bits, /dev/urandom retrouve 4 fois sur 5 la valeur d = 20,248 rapportée par l’auteur
    • Pour le challenge 17 bits, /dev/urandom retrouve 2 fois sur 5 la valeur d = 1,441 rapportée par l’auteur
    • Le document indique que le résultat 17 bits est l’élément ayant reçu 1 BTC, et qu’environ 40 % des exécutions sur un ordinateur portable avec /dev/urandom ont permis de le retrouver
    • Il indique aussi que l’auteur n’aurait exécuté ce cas qu’une seule fois sur IBM ibm_fez en l’attribuant à un résultat quantique
    • Un exemple de sortie terminal pour l’exécution 17 bits est inclus tel quel
      • Courbe : y^2 = x^3 + 0x + 7 (mod 65647)
      • Ordre du groupe : n = 65173
      • Générateur : G = (12976, 52834)
      • Point cible : Q = (477, 58220)
      • Stratégie : ripple-carry modular addition (CDKM)
      • Backend : /dev/urandom
      • Largeur du registre classique : 49 bits
      • 20000 shots avec Unique outcomes: 20000
      • Résultat : d = 1441
      • Vérification : 1441*G = (477, 58220)
      • [OK] VERIFIED, [OK] SUCCESS: Recovered correct secret key

Pourquoi obtient-on ce résultat ?

  • La logique d’extraction, d’après ripple_carry_shor.py:197-240 et projecteleven.py:264, prend pour chaque shot (j, k, r), calcule d_cand = (r − j)·k⁻¹ mod n, puis ne l’accepte que si le vérificateur classique d_cand · G == Q le valide
  • Le document suppose qu’en présence d’un bruit uniforme, d_cand suit une distribution uniforme sur [0, n), et donne la probabilité d’au moins une vérification réussie sur S shots sous la forme suivante
    • P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • En remplaçant par les valeurs (n, S) du document, les taux de réussite théoriques de /dev/urandom sont les suivants
    • 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%
  • Le document affirme que le taux de réussite empirique de /dev/urandom mesuré plus haut correspond à cette valeur théorique
  • Il précise aussi que le dépôt contient déjà la phrase suivante dans README.md:210
    • "When shots >> n, random noise alone can recover d with high probability."
  • Pour toutes les exécutions de 4 bits à 10 bits, le ratio shots / n se situe entre 1.9× et 1,170× ; le document affirme que toute cette plage relève, selon l’auteur lui-même, d’un régime classique

Comment reproduire

  • Les résultats peuvent être reproduits sur la même branche et dans le même environnement avec la procédure suivante
    • git checkout urandom-reproduces-qpu
    • uv venv .venv && . .venv/bin/activate
    • uv pip install qiskit qiskit-ibm-runtime
  • Exemples d’exécution
    • 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
  • Le document indique qu’aucun compte IBM, token, matériel quantique ni réseau n’est nécessaire

Réserves et portée

  • L’implémentation du dépôt lui-même est jugée réelle et non triviale sur le plan de l’ingénierie
    • Elle contient six variantes d’oracle
    • Elle mappe l’additionneur CDKM ripple-carry sur une topologie heavy-hex
    • Elle utilise une semiclassical phase estimation avec mid-circuit measurement
  • La portée de la critique se limite à l’affirmation cryptanalytique
  • La conclusion du document est que cette exécution sur matériel ne correspond pas à une récupération de clé ECDLP par ordinateur quantique, mais à une vérification classique de candidats uniformément aléatoires — ce que cette branche reproduit tel quel, sans matériel quantique

À lire aussi

1 commentaires

 
GN⁺ 4 일 전
Réactions sur Hacker News
  • C’est exactement la prémisse que j’avais posée dans mon article de poisson d’avril sigbovik 2025. Pour les petits nombres, même en injectant des échantillons aléatoires dans l’algorithme de Shor, on peut réussir assez vite, et dès que le circuit devient trop long et dépasse les limites du taux d’erreur de l’ordinateur quantique, il se comporte en pratique comme un générateur aléatoire.
    Donc il peut donner extérieurement le « bon résultat » alors que la raison est complètement fausse. C’est pour cela que les petites factorisations entières ou les petits cas d’ECDLP sont de mauvais benchmarks pour mesurer les progrès du calcul quantique.
    J’avais prévenu les gens de project11 que cela allait arriver. Je pensais qu’au final on donnerait des bitcoins à la personne qui aurait le mieux masqué le fait que l’ordinateur quantique n’avait rien apporté, et je pensais aussi qu’il était très probable que l’auteur de la soumission se soit lui-même trompé. Apparemment, ils ne l’ont pas pris au sérieux.
    [1]: https://sigbovik.org/2025/proceedings.pdf#page=146
  • Project Eleven vient de donner 1 BTC pour ce qu’il a présenté comme la plus grande attaque quantique contre l’ECC, en affirmant avoir récupéré une clé sur courbe elliptique de 17 bits avec du matériel IBM Quantum. Mais Yuval Adam montre qu’on récupère la clé de la même manière même en remplaçant l’ordinateur quantique par /dev/urandom
    • Il faudrait quand même vérifier si le matériel quantique le fait plus vite
  • Le code publié par la personne qui a gagné ce challenge ressemble beaucoup à du code trompeur, alors même qu’elle ne semble avoir aucun bagage en calcul quantique.
    Sa présentation parle d’enterprise software, de full-stack architecture, de cloud native, de solution architecture et de sales engineering, et quand on regarde l’historique des commits, ça ressemble presque à du vibe coded : https://github.com/GiancarloLelli/quantum
    • Oui. Dès que je l’ai lu, j’ai immédiatement vu plein de signes typiques du vibe coding, c’est vraiment la première chose à laquelle j’ai pensé
  • Ce n’est pas une attaque contre le calcul quantique en lui-même, mais contre project11 et peut-être aussi contre le soumissionnaire. Ils n’ont pas correctement vérifié la soumission, et le code montre déjà que la solution est une méthode classique.
    Récupérer une clé ECC de 17 bits n’a rien de difficile aujourd’hui par brute force sur un ordinateur classique
    • Si la solution est plus rapide que le hasard, il reste quand même possible que ce soit une vraie solution exécutée sur un ordinateur quantique
  • Le recadrage de la vignette de cet article est d’une malchance vraiment parfaite : https://image.non.io/b3f69546-aeb3-48c3-a76d-723f29b28f48.webp

    • contains the code and submission

      Parfait

    • Je ne sais pas si je regarde autre chose, mais on dirait clairement le t de quan(tumslop)

    • C’est vraiment de l’art

    • C’est un peu dégoûtant

  • La dequantization existe réellement et constitue un sujet de recherche tout à fait légitime en information quantique. C’est utile pour distinguer ce qui est réellement quantique de ce qui n’est que de la poudre aux yeux, et pour mieux comprendre où se situe la frontière entre quantique et classique.
    Il y a aussi un autre résultat récent de dequantized : https://arxiv.org/abs/2604.21908
  • Une clé de 17 bits n’offre que 131072 possibilités, donc elle se casse beaucoup trop facilement par brute force. La casser avec un ordinateur quantique tient surtout de la démonstration physique, et n’a pas grand-chose à voir avec une tentative de faire un calcul utile.
    • Le point essentiel ici, c’est que la partie ordinateur quantique de la solution d’origine ne fait en réalité rien du tout. Cela signifie que l’algorithme complet n’est pas réellement un algorithme quantique, mais un algorithme probabiliste classique.
      Si l’ordinateur quantique était essentiel, remplacer cette partie par un RNG aurait dû faire échouer la réponse ou au moins ralentir la convergence. Mais comme le résultat est exactement le même, toute la logique réelle était du côté classique, et le QC n’a fait qu’ajouter du bruit
    • Je me trompe peut-être, mais l’idée de départ n’était-elle pas justement d’être plus rapide que le brute force ?
      Si le résultat est statistiquement indiscernable d’une simple supposition, on a finalement juste fabriqué une machine de Rube Goldberg compliquée
    • Si l’apport du QC est indiscernable de celui d’un générateur aléatoire, je ne vois pas du tout ce qui a été démontré
  • Le quantum grifting a aussi fortement gagné le secteur des cryptos.
    Des escrocs peuvent ressortir d’anciens coins morts ou en créer de nouveaux, en acheter en masse ou les émettre, puis leur ajouter ML-DSA en les présentant comme quantum-safe pour faire monter leur shitcoin avant de s’en débarrasser.
    Un jour, même les investisseurs particuliers les moins informés finiront par s’en rendre compte, mais honnêtement je ne vois même pas bien sur qui ça marche actuellement
    • C’est encore plus triste si la cible principale, ce sont des personnes dont l’anglais n’est pas la langue maternelle
  • Il faut aussi vérifier si le nombre d’appels au QM correspond bien entre les deux implémentations
  • À mes yeux, le calcul quantique est une arnaque vieille de 30 ans.
    Même Google n’a pas réussi à prouver que ses ordinateurs quantiques fonctionnent réellement, et les algorithmes sont tellement affaiblis qu’on en est réduit à exhiber des choses comme 17 bits