PoC pour casser la preuve à divulgation nulle de Google sur la cryptanalyse quantique

Ce dépôt contient les ressources pour le billet de blog de Trail of Bits détaillant comment nous avons battu la preuve à divulgation nulle de Google affirmant qu'ils disposent d'un circuit quantique à haute efficacité pour la cryptanalyse des courbes elliptiques. Il inclut notre preuve forgée, les instructions de vérification, et le code pour générer le circuit quantique qui exploite des vulnérabilités dans le code non corrigé du simulateur zkVM.

Le binaire complet de la preuve est ici, et les résultats comparant les preuves de Google à la nôtre sont ci-dessous.

Un résumé de la preuve est le suivant.

Hash SHA-256 du circuit : 0x7efe1f62bb14a978322ab9ed41d670fc0fe0f211331032615c910df5a540e999

Octets de la preuve Groth16 : 0x0e78f4db0000000000000000000000000000000000000000000000000000000000000000008cd56e10c2fe24795cff1e1d1f40d3a324528d315674da45d26afb376e8670000000000000000000000000000000000000000000000000000000000000000024ac7f8dd6b1de6279bcce54e8840d8eb20d522bf27dedd776046f6590f33add217db465201c63724e6b460641985543d2b79c3c54daeea688581676a786aafc1dba8604a361acdd9809e268b6d8bc73943a713bb0ed0d96221f73d26def6ea4041d05b077523d9351a48b2ecd984c686b6473df69d20a24296d0a1cba3cdbe92eb13a7cc0ecd92f27f7bf23f9ac859d4293e17216dcbd85d1c7f60a52f65a9d02faef077336acd39e845d534200b575b029d6e3f0afb4f90815557233eab70b0fe88919834dd9beb90d47241f1490dc202e0dce44e4894982b07073c8d4426513732d79e9af9913b254aa29471e1a98fa1b43a1886afb5dbd36988153217aa2

Clé de vérification : 0x00ca4af6cb15dbd83ec3eaab3a0664023828d90a98e650d2d340712f5f3eb0d4

Étapes de vérification

Google a fourni des scripts pour vérifier leurs preuves ZK dans un ensemble de données Zenodo. Notre attaque cible la version 1, et la version 2 contient des correctifs. Les instructions pour installer les dépendances se trouvent dans docs/getting_started.md. L'environnement nécessite Rust, Go, et éventuellement Docker. Les commandes de vérification sont fournies à la fin de run_proofs.sh. Les artefacts de preuve de Google se trouvent dans le répertoire proofs/, et notre artefact de preuve est dans proof_trailofbits.bin.

# Vérifier les preuves de Google
cargo run --release -p verifier -- \
    --vkey proofs/vkey.bin --proof proofs/low_toffoli/proof_9024.bin
cargo run --release -p verifier -- \
    --vkey proofs/vkey.bin --proof proofs/low_qubits/proof_9024.bin
# Vérifier notre preuve
cargo run --release -p verifier -- \
    --vkey proofs/vkey.bin --proof proof_trailofbits.bin

La sortie de la dernière commande inclut ce qui suit.

Successfully verified Groth16 SNARK proof.
Circuit hash commitment: 0x7efe1f62bb14a978322ab9ed41d670fc0fe0f211331032615c910df5a540e999
Demanded Number of tests: 9024
Demanded Qubit count: 1164
Demanded Average non-Clifford count: 0
Demanded Total ops: 8300000

Les commandes de vérification contrôlent les preuves ZK par rapport à la clé de vérification, qui est une représentation cryptographique concise du programme invité zkVM. Alternativement, vous pouvez utiliser --elf proofs/zkp_ecc-program pour fournir au vérificateur le binaire ELF du programme invité. Si vous omettez entièrement cet indicateur, le vérificateur utilise un conteneur Docker pour reconstruire le binaire du programme invité à partir du code source dans program/.

Étapes d'exploitation

L'exécution de gen_secp256k1_tob.py génère un script kickmix de 142 Mo nommé ec_secp256k1_add_into.kmx. Pour obtenir la preuve à 0 Toffoli, utilisez prove.rs.diff pour patcher prover/prove.rs dans le dépôt Zenodo. Cela modifie le code non fiable s'exécutant en dehors du zkVM afin de manipuler la sérialisation du circuit kickmix.

Les instructions de génération de preuve se trouvent dans le dépôt Zenodo. Nous avons suivi les instructions de docs/sp1_cluster_deployment_guide.md sur une machine cloud avec 4 GPU NVIDIA H100 et exécuté la commande suivante pour générer la preuve.

./run_proofs.sh --num-tests 9024 --kmx "ec_secp256k1_add_into.kmx" --qubit-counts 1164 --toffoli-counts 0 --total-ops 8300000 --proving-mode "multi-gpu" > proofs/ec_secp256k1_add/log_run.out 2>&1 &

La preuve forgée a pris environ 4 heures à générer.