Substituindo o backend do IBM Quantum por `/dev/urandom`

 (github.com/yuvadm)
2 pontos por GN⁺ 4 일 전 | 1 comentários | Compartilhar no WhatsApp
  • Mesmo substituindo apenas o backend do IBM Quantum por os.urandom, a recuperação da chave privada foi reproduzida mantendo inalterados a construção do circuito, os oráculos, o pipeline de extração e o verificador d·G == Q
  • O escopo da modificação se limita a 59 linhas alteradas em projecteleven.py: remove a execução do backend e a coleta de resultados, e gera sequências uniformes de bits aleatórios compatíveis com a largura do registrador clássico, na quantidade de shots, repassando-as ao pós-processamento existente
  • De 4 bits a 10 bits, a execução com /dev/urandom recuperou valores de d idênticos byte a byte aos resultados de hardware reportados; em 16 bits e 17 bits, também conseguiu recuperar a chave em 4 de 5 e 2 de 5 tentativas, respectivamente
  • A lógica de extração aceita, em cada shot, d_cand = (r − j)·k⁻¹ mod n apenas quando passa no verificador clássico; o documento explica a taxa de sucesso com /dev/urandom por P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • Embora mantenha engenharia não trivial como seis oráculos, mapeamento heavy-hex e semiclassical phase estimation, a crítica do documento se limita à alegação criptanalítica e mostra que os resultados de hardware podem ser reproduzidos não como recuperação quântica, mas por verificação clássica

diff

  • A alteração total em projecteleven.py tem escala de −29 / +30 lines e remove a inicialização do serviço IBM Quantum, a execução do backend, a chamada do sampler e a coleta do resultado do job, substituindo tudo por geração de counts baseada em aleatoriedade
  • O código adicionado lê o comprimento do registrador clássico do circuito, cria shots sequências uniformes de bits aleatórios com a mesma largura e as agrega com Counter, repassando-as intactas ao pós-processamento existente
    • nbits = qc.num_clbits
    • bpb = (nbits + 7) // 8
    • mask = (1 << nbits) - 1
    • Em cada shot, o valor é criado com int.from_bytes(_os.urandom(bpb), "big") & mask e convertido em uma string binária com a largura especificada
  • O conjunto completo das 59 linhas alteradas pode ser visto em git diff main

Resultados: execução do CLI do autor com o patch aplicado

  • Usando exatamente o mesmo comando de CLI, foi verificado se a chave privada podia ser recuperada apenas com resultados fornecidos por /dev/urandom, em vez de hardware
  • A tabela apresentada no documento compara diretamente o valor de d reportado pelo autor com o valor de d recuperado por /dev/urandom

  • Desafios pequenos, 1 tentativa cada, 8.192 shots

    • O comando executado é python projecteleven.py --challenge <N> --shots 8192
    • A saída completa vai de urandom_runs/urandom_challenge_4.txt até _10.txt
    • Em todos os itens de 4 bits a 10 bits, o d recuperado por /dev/urandom é idêntico byte a byte ao resultado de hardware reportado pelo autor
      • 4-bit: 6 → 6, verificação aprovada na primeira tentativa
      • 6-bit: 18 → 18, verificação aprovada na primeira tentativa
      • 8-bit: 103 → 103, verificação aprovada na primeira tentativa
      • 9-bit: 135 → 135, verificação aprovada na primeira tentativa
      • 10-bit: 165 → 165, verificação aprovada na primeira tentativa
    • Segundo o documento, cada desafio foi executado uma vez, /dev/urandom também foi executado uma vez, e ambos foram bem-sucedidos

  • Desafios principais, 5 tentativas cada, 20.000 shots, oráculo ripple-carry

    • O comando executado é python projecteleven.py --challenge <N> --oracle ripple --shots 20000
    • A saída completa está reunida em urandom_runs/urandom_challenge_16_17_flagship.txt
    • No desafio de 16 bits, /dev/urandom recuperou 4 vezes em 5 o d = 20,248 reportado pelo autor
    • No desafio de 17 bits, /dev/urandom recuperou 2 vezes em 5 o d = 1,441 reportado pelo autor
    • O documento diz que o resultado de 17 bits é o item que recebeu 1 BTC, e que /dev/urandom o recuperou em cerca de 40% das execuções em um notebook
    • O documento também diz que o autor executou esse item uma vez no IBM ibm_fez e o apresentou como resultado quântico
    • A saída de terminal de um exemplo de execução em 17 bits também é incluída integralmente
      • Curva: y^2 = x^3 + 0x + 7 (mod 65647)
      • Ordem do grupo: n = 65173
      • Gerador: G = (12976, 52834)
      • Ponto-alvo: Q = (477, 58220)
      • Estratégia: ripple-carry modular addition (CDKM)
      • Backend: /dev/urandom
      • Largura do registrador clássico: 49 bits
      • Em 20000 shots: Unique outcomes: 20000
      • Resultado: d = 1441
      • Verificação: 1441*G = (477, 58220)
      • [OK] VERIFIED, [OK] SUCCESS: Recovered correct secret key

Por que esse resultado acontece

  • A lógica de extração, com base em ripple_carry_shor.py:197-240 e projecteleven.py:264, recebe (j, k, r) de cada shot, calcula d_cand = (r − j)·k⁻¹ mod n e só o aceita quando passa no verificador clássico d_cand · G == Q
  • O documento assume que, sob ruído uniforme, d_cand segue uma distribuição uniforme no intervalo [0, n), e dá a seguinte fórmula para a probabilidade de ao menos um sucesso de verificação em S shots
    • P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • Substituindo nessa fórmula os valores (n, S) do documento, as taxas teóricas de sucesso com /dev/urandom ficam assim
    • 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%
  • O documento afirma que a taxa de sucesso empírica medida com /dev/urandom bate com esse valor teórico
  • O mesmo repositório já contém, em README.md:210, a seguinte frase
    • "When shots >> n, random noise alone can recover d with high probability."
  • Em todas as execuções de 4 bits a 10 bits, a razão shots / n fica entre 1,9× e 1.170×; o documento diz que toda essa faixa já se enquadra nas condições que o próprio autor identificava como regime clássico

Como reproduzir

  • Os resultados podem ser reproduzidos no mesmo branch e ambiente com os passos abaixo
    • git checkout urandom-reproduces-qpu
    • uv venv .venv && . .venv/bin/activate
    • uv pip install qiskit qiskit-ibm-runtime
  • Exemplos de execução
    • 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
  • O documento diz que conta IBM, token, hardware quântico e rede não são necessários

Indícios e escopo

  • A implementação do repositório em si é avaliada como engenharia real e não trivial
    • Há seis variantes de oráculo
    • O somador CDKM ripple-carry é mapeado para topologia heavy-hex
    • É usada semiclassical phase estimation com mid-circuit measurement
  • O escopo da crítica é limitado à alegação criptanalítica
  • A conclusão do documento é que essa execução em hardware não representa recuperação de chave ECDLP por computador quântico, mas sim verificação clássica de candidatos uniformemente aleatórios, e que esse branch mostra a mesma reprodução sem qualquer hardware quântico

Leituras relacionadas

1 comentários

 
GN⁺ 4 일 전
Comentários no Hacker News
  • Isso é exatamente a premissa que eu já tinha estabelecido no artigo de 1º de abril da sigbovik 2025. Para números pequenos, mesmo colocando amostras aleatórias no algoritmo de Shor, ele logo dá certo, e quando o circuito fica longo demais e ultrapassa o limite da taxa de erro do computador quântico, na prática ele passa a funcionar como um gerador de números aleatórios.
    Então, mesmo que por fora pareça produzir o "resultado correto", o motivo pode estar completamente errado. Por isso, fatoração de inteiros pequenos ou casos pequenos de ECDLP são benchmarks inadequados para medir progresso em computação quântica.
    Eu avisei o pessoal da project11 que isso aconteceria. Achei que no fim dariam bitcoin para quem melhor escondesse o fato de que o computador quântico não contribuiu em nada, e também achei bem possível que o próprio autor da submissão tivesse se enganado. Parece que não levaram isso a sério.
    [1]: https://sigbovik.org/2025/proceedings.pdf#page=146
  • A Project Eleven acabou de dar 1 BTC por aquele suposto maior ataque quântico contra ECC até agora, em que teriam recuperado uma chave elíptica de 17 bits com hardware da IBM Quantum. Só que o Yuval Adam substituiu o computador quântico por /dev/urandom e a chave continuou sendo recuperada
    • Mesmo assim, não seria preciso ver se o hardware quântico processa isso mais rápido?
  • O código publicado por quem venceu esse desafio parece um código bem enganoso, e o autor em si aparentemente não tem nenhuma formação em computação quântica
    A própria apresentação dele é voltada para software corporativo, arquitetura full-stack, cloud native, arquitetura de soluções e engenharia de vendas, e pelo histórico de commits isso parece quase vibe coded: https://github.com/GiancarloLelli/quantum
    • Sim. Assim que li, vi muitos sinais característicos de vibe coding, e foi a primeira coisa que pensei também
  • Isso não é uma crítica à computação quântica em si, e sim à project11 e talvez ao autor da submissão. Eles não validaram a submissão direito, e o código já mostra que a solução era um método clássico
    Recuperar uma chave ECC de 17 bits hoje não tem dificuldade nenhuma por força bruta em um computador clássico
    • Se a solução for mais rápida que o aleatório, ainda resta a possibilidade de ser uma solução real rodando num computador quântico
  • O recorte da miniatura dessa matéria ficou incrivelmente infeliz: https://image.non.io/b3f69546-aeb3-48c3-a76d-723f29b28f48.webp

    • contains the code and submission

      Perfeito

    • Talvez eu esteja vendo outra coisa, mas aquilo com certeza parece o t de quan(tumslop)

    • Isso é arte de verdade

    • Meio nojento

  • Dequantization realmente existe e é um tema de pesquisa totalmente legítimo em informação quântica. É útil para distinguir o que é de fato quântico do que é só cortina de fumaça, e ajuda a entender onde fica a fronteira entre o quântico e o clássico
    Também saiu recentemente outro resultado de dequantized: https://arxiv.org/abs/2604.21908
  • Uma chave de 17 bits tem só 131072 possibilidades, então é fácil demais quebrá-la por força bruta. Quebrar isso com um computador quântico é, no máximo, uma demonstração física, e está bem longe de ser uma tentativa de fazer computação útil
    • O ponto central aqui é que a parte do computador quântico na solução original não faz absolutamente nada. Isso quer dizer que o algoritmo completo, na prática, não é um algoritmo quântico, mas sim um algoritmo probabilístico clássico
      Se o computador quântico fosse essencial, ao trocá-lo por um RNG a resposta não deveria sair, ou pelo menos a convergência teria que ficar mais lenta. Mas como o resultado foi exatamente o mesmo, toda a lógica real estava do lado clássico, e o QC só acrescentou ruído
    • Posso estar deixando passar alguma coisa, mas a ideia original não era justamente ser mais rápido que força bruta?
      Se o resultado estatisticamente não se distingue de um chute, então no fim parece que só montaram uma máquina de Rube Goldberg complicada
    • Se a contribuição do QC não pode ser distinguida de um gerador de números aleatórios, então eu realmente não sei o que foi demonstrado
  • O golpismo quântico também chegou forte ao mundo cripto
    Golpistas podem ressuscitar moedas antigas fracassadas ou criar novas, comprar ou emitir uma grande quantidade e então anexar ML-DSA, divulgar aquilo como seguro contra ataques quânticos, inflar a shitcoin e depois despejar tudo
    Em algum momento até investidores de varejo menos informados vão perceber, mas sinceramente nem sei para quem isso cola hoje
    • Fica ainda mais triste porque o principal alvo parece ser pessoas que não têm o inglês como língua nativa
  • Também seria preciso verificar se o número de chamadas ao QM bate entre as duas implementações
  • Acho que computação quântica é uma fraude de 30 anos
    Nem o Google conseguiu provar que o computador quântico deles realmente funciona, e os algoritmos foram enfraquecidos a um nível extremo, a ponto de apresentarem coisas como 17 bits