Reemplazan el backend de IBM Quantum por /dev/urandom

 (github.com/yuvadm)
2 puntos por GN⁺ 4 일 전 | 1 comentarios | Compartir por WhatsApp
  • Incluso dejando intactos la construcción del circuito, los oráculos, el pipeline de extracción y el verificador d·G == Q, la recuperación de la clave privada pudo reproducirse con solo sustituir el backend de IBM Quantum por os.urandom
  • El alcance del cambio se limita a 59 líneas modificadas en projecteleven.py: se elimina la ejecución del backend y la recolección de resultados, y en su lugar se generan cadenas de bits aleatorias uniformes ajustadas al ancho del registro clásico, una por cada shot, para pasarlas al procesamiento posterior existente
  • De 4 bits a 10 bits, la ejecución con /dev/urandom recuperó valores de d idénticos byte por byte a los resultados de hardware reportados; en 16 bits y 17 bits también logró recuperar la clave en 4 de 5 y 2 de 5 intentos, respectivamente
  • La lógica de extracción adopta un d_cand = (r − j)·k⁻¹ mod n calculado en cada shot solo cuando pasa el verificador clásico; el documento explica la tasa de éxito de /dev/urandom con P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • Aunque se mantienen ingenierías no triviales como seis oráculos, mapeo heavy-hex y semiclassical phase estimation, el alcance de la crítica se limita a la afirmación criptanalítica: los resultados de ejecución en hardware pueden reproducirse mediante verificación clásica y no necesariamente por recuperación cuántica

diff

  • El cambio completo en projecteleven.py es de −29 / +30 líneas: se eliminan la inicialización del servicio de IBM Quantum, la ejecución del backend, la llamada al sampler y la recolección de resultados del trabajo, y se reemplazan por una generación de counts basada en números aleatorios
  • El código agregado lee la longitud del registro clásico del circuito y crea shots cadenas de bits aleatorias uniformes con ese mismo número de bits, para luego agregarlas con Counter y pasarlas sin cambios al procesamiento posterior existente
    • nbits = qc.num_clbits
    • bpb = (nbits + 7) // 8
    • mask = (1 << nbits) - 1
    • En cada shot, genera un valor con int.from_bytes(_os.urandom(bpb), "big") & mask y luego lo convierte a una cadena binaria del ancho especificado
  • El detalle completo de las 59 líneas modificadas puede verse en git diff main

Resultados: ejecución del autor con el parche aplicado

  • Usando exactamente el mismo comando CLI, se comprobó si era posible recuperar la clave privada usando únicamente resultados suministrados por /dev/urandom en lugar del hardware
  • La tabla presentada en el documento compara directamente los valores de d reportados por el autor con los valores de d recuperados mediante /dev/urandom

  • Desafíos pequeños, 1 intento cada uno, 8,192 shots

    • El comando ejecutado es python projecteleven.py --challenge <N> --shots 8192
    • La salida completa va desde urandom_runs/urandom_challenge_4.txt hasta _10.txt
    • En todos los casos de 4 a 10 bits, el d recuperado por /dev/urandom es idéntico byte por byte al resultado de hardware reportado por el autor
      • 4-bit: 6 → 6, verificación superada en el primer intento
      • 6-bit: 18 → 18, verificación superada en el primer intento
      • 8-bit: 103 → 103, verificación superada en el primer intento
      • 9-bit: 135 → 135, verificación superada en el primer intento
      • 10-bit: 165 → 165, verificación superada en el primer intento
    • Según el documento, cada desafío se ejecutó una vez y /dev/urandom también se ejecutó una vez; ambos tuvieron éxito

  • Desafíos representativos, 5 intentos cada uno, 20,000 shots, oráculo ripple-carry

    • El comando ejecutado es python projecteleven.py --challenge <N> --oracle ripple --shots 20000
    • La salida completa está recopilada en urandom_runs/urandom_challenge_16_17_flagship.txt
    • En el desafío de 16 bits, /dev/urandom recuperó en 4 de 5 intentos el d = 20,248 reportado por el autor
    • En el desafío de 17 bits, /dev/urandom recuperó en 2 de 5 intentos el d = 1,441 reportado por el autor
    • El documento dice que el resultado de 17 bits era el caso que recibió 1 BTC, y que /dev/urandom lo recuperó en alrededor del 40% de las ejecuciones en una laptop
    • También afirma que el autor ejecutó este caso una vez en IBM ibm_fez y sostuvo que era un resultado cuántico
    • Se incluye además la salida completa de terminal de un ejemplo de ejecución de 17 bits
      • Curva: y^2 = x^3 + 0x + 7 (mod 65647)
      • Orden del grupo: n = 65173
      • Generador: G = (12976, 52834)
      • Punto objetivo: Q = (477, 58220)
      • Estrategia: ripple-carry modular addition (CDKM)
      • Backend: /dev/urandom
      • Ancho del registro clásico: 49 bits
      • En 20000 shots, Unique outcomes: 20000
      • Resultado: d = 1441
      • Verificación: 1441*G = (477, 58220)
      • [OK] VERIFIED, [OK] SUCCESS: Recovered correct secret key

Por qué ocurre esto

  • La lógica de extracción, según ripple_carry_shor.py:197-240 y projecteleven.py:264, toma (j, k, r) de cada shot y calcula d_cand = (r − j)·k⁻¹ mod n; luego lo acepta solo si pasa el verificador clásico d_cand · G == Q
  • El documento supone que, bajo ruido uniforme, d_cand sigue una distribución uniforme en el intervalo [0, n), y expresa así la probabilidad de obtener al menos una verificación exitosa en S shots
    • P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • Al sustituir en esta fórmula los valores de (n, S) del documento, las tasas teóricas de éxito de /dev/urandom quedan así
    • 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%
  • El documento sostiene que la tasa de éxito empírica observada con /dev/urandom coincide con esos valores teóricos
  • También indica que en README.md:210 ya aparece esta frase
    • "When shots >> n, random noise alone can recover d with high probability."
  • De 4 bits a 10 bits, la relación shots / n está entre 1.9× y 1,170× en todos los casos; según el documento, todo ese rango entra en condiciones que el propio autor ya identificaba como un régimen clásico

Cómo reproducirlo

  • Los resultados pueden reproducirse en la misma rama y entorno siguiendo estos pasos
    • git checkout urandom-reproduces-qpu
    • uv venv .venv && . .venv/bin/activate
    • uv pip install qiskit qiskit-ibm-runtime
  • Ejemplos de ejecución
    • 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
  • El documento afirma que no hacen falta cuenta de IBM, token, hardware cuántico ni red

Indicios y alcance

  • La implementación del repositorio en sí se evalúa como real y de ingeniería no trivial
    • Incluye seis variantes de oráculo
    • Mapea sumadores CDKM ripple-carry a topología heavy-hex
    • Usa semiclassical phase estimation con mid-circuit measurement
  • El alcance de la crítica se limita a la afirmación criptanalítica
  • La conclusión del documento es que esta ejecución en hardware no representa una recuperación de claves ECDLP por computadora cuántica, sino una verificación clásica sobre candidatos aleatorios uniformes, y que, como muestra esta rama, puede reproducirse tal cual sin hardware cuántico

Lecturas relacionadas

1 comentarios

 
GN⁺ 4 일 전
Comentarios de Hacker News
  • Esto es exactamente la premisa que yo dejé planteada en mi artículo de April Fools de sigbovik 2025. Para números pequeños, el algoritmo de Shor puede tener éxito rápido incluso si le metes muestras aleatorias, y cuando el circuito se vuelve demasiado largo y supera el límite de tasa de error de la computadora cuántica, en la práctica se comporta como un generador de números aleatorios.
    Así que, aunque superficialmente dé el "resultado correcto", la razón puede estar completamente equivocada. Por eso, los casos de factorización de enteros pequeños o de ECDLP pequeños no son benchmarks adecuados para medir el progreso en computación cuántica.
    Yo le advertí a la gente de project11 que esto iba a pasar. Pensé que al final terminarían dándole bitcoin a quien mejor ocultara el hecho de que la computadora cuántica no aportó nada, y también creí que era muy probable que el propio remitente se hubiera engañado a sí mismo. Parece que no me tomaron muy en serio.
    [1]: https://sigbovik.org/2025/proceedings.pdf#page=146
  • Project Eleven acaba de dar 1 BTC por lo que llamó el mayor ataque cuántico contra ECC hasta ahora, donde supuestamente se recuperó una clave elíptica de 17 bits usando hardware de IBM Quantum. Pero Yuval Adam mostró que la clave también se recupera igual aunque reemplaces la computadora cuántica por /dev/urandom
    • Aun así, ¿no habría que ver si el hardware cuántico lo resuelve más rápido?
  • El código que publicó quien ganó este reto se ve bastante engañoso, y la verdad es que esa persona no parece tener ningún antecedente en computación cuántica.
    Su perfil habla de software empresarial, arquitectura full-stack, cloud native, arquitectura de soluciones e ingeniería de ventas, y por el historial de commits esto parece casi vibe coded: https://github.com/GiancarloLelli/quantum
    • Sí. En cuanto lo leí vi demasiadas señales típicas de vibe coding, y fue exactamente lo primero que pensé
  • Esto no es una crítica a la computación cuántica en sí, sino a project11 y quizá también al remitente. No verificaron bien el envío, y el código ya muestra que la solución es un método clásico.
    Recuperar una clave ECC de 17 bits no tiene nada de difícil por fuerza bruta con una computadora clásica hoy en día
    • Si la solución es más rápida que el azar, entonces todavía queda la posibilidad de que sí sea una solución real sobre una computadora cuántica
  • El recorte de la miniatura de este artículo quedó de una forma desafortunadamente perfecta: https://image.non.io/b3f69546-aeb3-48c3-a76d-723f29b28f48.webp

    • contains the code and submission

      Perfecto

    • No sé si estoy viendo otra cosa, pero juraría que eso claramente es la t de quan(tumslop)

    • Esto sí es arte

    • Está medio asqueroso

  • La dequantization sí existe como un tema de investigación totalmente legítimo en información cuántica. Sirve para distinguir si algo es realmente cuántico o solo humo, y ayuda a entender dónde está la frontera entre lo cuántico y lo clásico.
    También hay otros resultados recientes de dequantized: https://arxiv.org/abs/2604.21908
  • Una clave de 17 bits solo tiene 131072 posibilidades, así que es facilísima de romper por fuerza bruta. Hacerlo con una computadora cuántica es más bien una demostración física, no un intento de hacer un trabajo de cómputo útil
    • El punto clave aquí es que la parte de computadora cuántica de la solución original no hace nada. Eso significa que el algoritmo completo en realidad no es un algoritmo cuántico, sino un algoritmo probabilístico clásico.
      Si la computadora cuántica fuera la parte clave, al reemplazarla por un RNG no debería salir la respuesta, o por lo menos debería converger más lento. Pero como el resultado sale exactamente igual, toda la lógica real estaba del lado clásico y la QC solo metía ruido
    • Puede que no entienda bien, pero ¿la idea original no era que debía ser más rápido que la fuerza bruta?
      Si el resultado es estadísticamente indistinguible de adivinar, entonces al final parece que solo construyeron una máquina de Rube Goldberg complicada
    • Si la contribución de la QC no se puede distinguir de la de un generador de números aleatorios, entonces no sé qué fue exactamente lo que demostraron
  • El quantum grifting también ya le pegó fuerte al mundo cripto.
    Los estafadores pueden revivir alguna moneda vieja fallida o crear una nueva, comprar una posición o emitirla, luego agregarle ML-DSA y promocionarla como resistente a lo cuántico para inflar la shitcoin y después descargarla.
    En algún momento hasta los inversionistas minoristas menos informados se van a dar cuenta, pero la verdad ni sé a quién le está funcionando esto hoy
    • Es todavía más triste porque parece que el objetivo principal son personas que no tienen el inglés como lengua materna
  • También habría que verificar si la cantidad de llamadas al QM coincide entre las dos implementaciones
  • Yo veo la computación cuántica como una estafa de 30 años.
    Ni siquiera Google ha podido demostrar que su computadora cuántica realmente funcione bien, y hasta sus algoritmos los han debilitado al extremo para llegar a cosas como 17 bits