PoC для взлома доказательства Google с нулевым разглашением квантового криптоанализа

Этот репозиторий содержит ресурсы для статьи в блоге Trail of Bits, подробно описывающей, как мы обошли доказательство Google с нулевым разглашением о том, что у них есть высокоэффективная квантовая схема для криптоанализа эллиптических кривых. Включает наше поддельное доказательство, инструкции по верификации и код для генерации квантовой схемы, использующей уязвимости в незапатченном коде симулятора zkVM.

Полный бинарный файл доказательства находится здесь, а результаты сравнения доказательств Google с нашими приведены ниже.

Краткое описание доказательства следующее.

Хэш SHA-256 схемы: 0x7efe1f62bb14a978322ab9ed41d670fc0fe0f211331032615c910df5a540e999

Байты доказательства Groth16: 0x0e78f4db0000000000000000000000000000000000000000000000000000000000000000008cd56e10c2fe24795cff1e1d1f40d3a324528d315674da45d26afb376e8670000000000000000000000000000000000000000000000000000000000000000024ac7f8dd6b1de6279bcce54e8840d8eb20d522bf27dedd776046f6590f33add217db465201c63724e6b460641985543d2b79c3c54daeea688581676a786aafc1dba8604a361acdd9809e268b6d8bc73943a713bb0ed0d96221f73d26def6ea4041d05b077523d9351a48b2ecd984c686b6473df69d20a24296d0a1cba3cdbe92eb13a7cc0ecd92f27f7bf23f9ac859d4293e17216dcbd85d1c7f60a52f65a9d02faef077336acd39e845d534200b575b029d6e3f0afb4f90815557233eab70b0fe88919834dd9beb90d47241f1490dc202e0dce44e4894982b07073c8d4426513732d79e9af9913b254aa29471e1a98fa1b43a1886afb5dbd36988153217aa2

Ключ верификации: 0x00ca4af6cb15dbd83ec3eaab3a0664023828d90a98e650d2d340712f5f3eb0d4

Шаги верификации

Google предоставил скрипты для верификации их ZK-доказательств в наборе данных Zenodo. Наша атака нацелена на версию 1, а версия 2 содержит исправления. Инструкции по установке зависимостей находятся в docs/getting_started.md. Окружение требует Rust, Go и опционально Docker. Команды для верификации приведены в конце run_proofs.sh. Артефакты доказательств Google находятся в каталоге proofs/, а наш артефакт доказательства — в proof_trailofbits.bin.

# Verify Google's proofs
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
# Verify our proof
cargo run --release -p verifier -- \
    --vkey proofs/vkey.bin --proof proof_trailofbits.bin

Вывод последней команды включает следующее.

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

Команды верификации проверяют ZK-доказательства по ключу верификации, который является кратким криптографическим представлением гостевой программы zkVM. Альтернативно, вы можете использовать --elf proofs/zkp_ecc-program, чтобы предоставить верификатору ELF-бинарный файл гостевой программы. Если полностью опустить этот флаг, верификатор использует Docker-контейнер для пересборки бинарного файла гостевой программы из исходного кода в program/.

Шаги эксплуатации

Запуск gen_secp256k1_tob.py генерирует Kickmix-скрипт размером 142 МБ с именем ec_secp256k1_add_into.kmx. Чтобы получить доказательство с 0 Toffoli, используйте prove.rs.diff для патча prover/prove.rs в репозитории Zenodo. Это модифицирует ненадежный код, выполняемый вне zkVM, для манипуляции сериализацией схемы Kickmix.

Инструкции по генерации доказательства находятся в репозитории Zenodo. Мы следовали инструкциям в docs/sp1_cluster_deployment_guide.md на облачной машине с 4 GPU NVIDIA H100 и выполнили следующую команду для генерации доказательства.

./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 &

Генерация поддельного доказательства заняла около 4 часов.