oleh: Johan

latar belakang

Kerentanan Frozen Heart diberi nama oleh tim Trail of Bits, di mana Frozen merupakan singkatan dari Forging Of Zero kNowledge proofs dan Heart merujuk kepada transformasi Fiat-Shamir, yang merupakan inti dari banyak sistem pembuktian. Kerentanan tersebut mengacu pada penerapan transformasi "Fiat-Shamir yang lemah", yang hanya melakukan hashing pada sebagian pesan pembuktian tanpa melakukan hashing pada informasi publik (seperti parameter, masukan publik, dsb.), sehingga mengakibatkan masalah keamanan.

Di bawah ini kami akan melakukan analisis menyeluruh terhadap kerentanan ini. Pertama-tama mari kita bahas apa itu transformasi Fiat-Shamir.

Transformasi Fiat-Shamir

Transformasi Fiat-Shamir, juga dikenal sebagai Heuristik Fiat-Shamir atau Paradigma Fiat-Shamir, adalah transformasi yang diusulkan oleh Fiat dan Shamir pada tahun 1986 untuk mengubah protokol bukti pengetahuan nol interaktif menjadi protokol bukti pengetahuan nol non-interaktif. . Transformasi ini dicapai dengan mengganti tantangan acak dalam protokol dengan keluaran fungsi hash. Dengan cara ini, pembuktian dapat membuat bukti dan mengirimkannya ke verifikator tanpa memerlukan tantangan dan respons interaktif.

Bukti Schnorr merupakan protokol pembuktian tanpa pengetahuan interaktif yang memungkinkan pembuktian untuk membuktikan kepada pemeriksa bahwa suatu pernyataan itu benar tanpa mengungkapkan rincian pernyataan tersebut, sementara pemeriksa dapat melakukan verifikasi interaktif. Biasanya digunakan dalam situasi di mana pembuktian mengetahui nilai rahasia tanpa mengungkapkannya.

Dengan bantuan transformasi Fiat-Shamir, bukti interaktif Schnorr dapat diubah menjadi non-interaktif.

Schnorr dapat diimplementasikan pada medan hingga atau kurva eliptik (EC), dengan spesifikasi teknis yang pada dasarnya sama, kecuali untuk grup siklik yang mendasarinya. Di bawah ini kami terutama menggambarkan kedua proses ini dalam bentuk medan terbatas [1]:

* Simbol:

  • Alice: identitas yang diasumsikan oleh pembuktian dalam protokol

  • Bob: identitas yang diasumsikan dari validator dalam protokol

  • a | b: a membagi b

  • a || b: gabungan dari a dan b

  • [a, b]: interval bilangan bulat, termasuk a dan b

  • t: jumlah bit tantangan yang dipilih oleh Bob

  • H: fungsi hash kriptografi yang aman

  • p: bilangan prima besar

  • q: faktor prima besar dari p-1, yaitu q | p-1

  • Zp*: grup perkalian bilangan bulat modulo p

  • Gq: subgrup dari Zp* dengan orde prima q

  • g: pembangkit Gq

  • g^d: g dipangkatkan d

  • a mod b: a modulo b

  • Fp: suatu bidang berhingga dengan p elemen, dimana p adalah bilangan prima

Implementasi berdasarkan bidang terbatas

1. Interaktif

Pertama, Alice menghitung A = g^a mod p, dimana kunci pribadi a mengambil nilai [0, q-1], dan kemudian menerbitkan kunci publik A;

Kemudian, tanpa mengungkapkan a, Alice membuktikan kepada Bob bahwa dia mengetahui kunci pribadi a yang sesuai dengan A:

Jika pemeriksaan benar, maka kita dapat membuktikan bahwa Alice mengetahui a , sebagai berikut:

Alasan mengapa Bob perlu menghasilkan c acak di sini adalah karena jika penyerang mengetahui nilai ini sebelum menerbitkan A, ia dapat memalsukan bukti tanpa mengetahui a yang sebenarnya. Penyerang memalsukan (A, V, r) sebagai berikut:

1) Hasilkan nilai acak r

2) Metode perhitungan V tetap tidak berubah, misal

Setelah Verifikator menerima ketiga parameter tersebut, ia mensubstitusikannya ke dalam rumus verifikasi dan verifikasi pun dapat lolos. Tetapi jika kita melihat proses pembangkitan parameter ini, mereka tidak ada hubungannya dengan nilai rahasia a yang harus dibuktikan.
2. Non-interaktif

Transformasi non-interaktif juga sangat mudah. ​​Berdasarkan transformasi interaktif, proses Bob yang secara acak menghasilkan c diubah ke bentuk Hash dari parameter:

Implementasi berdasarkan kurva eliptik

Pertama, Alice menghitung A = G x [a], dimana kunci pribadi a mengambil nilai [0, n-1], dan kemudian menerbitkan kunci publik A;

Kemudian, Alice membuktikan kepada Bob bahwa dia mengetahui kunci pribadi a yang sesuai dengan A tanpa mengungkapkan a:

Jika pemeriksaan benar, maka kita dapat membuktikan bahwa Alice mengetahui a , sebagai berikut:

Implementasi non-interaktif sama dengan implementasi berbasis medan terbatas yang disebutkan di atas, dan tidak akan dijelaskan secara rinci.

Transformasi Fiat-Shamir yang lemah

Dalam implementasi non-interaktif di atas, angka acak:

Ini adalah cara yang benar dan aman untuk menghasilkan, namun sayangnya, dalam beberapa makalah awal, proses ini tidak dijelaskan secara rinci, melainkan hanya dijelaskan sebagai:

Hal ini menimbulkan masalah keamanan, yang kami sebut transformasi Fiat-Shamir yang lemah, yang dapat digunakan untuk memalsukan bukti dengan melakukan pra-perhitungan A dan menipu verifikator.

Rekonstruksi parameter (A, r) menggunakan:

1. Hasilkan nilai acak

2. Hitung a=(v-r)/c, metode perhitungannya tetap sama

3. Perhitungan

Kita dapat melihat bahwa A menjadi parameter yang independen dari a, dan mensubstitusikannya ke dalam persamaan verifikasi:

dapat sama dengan V

Artinya, penyerang dapat melewati protokol autentikasi tanpa mengetahui nilai rahasianya.

Ada juga beberapa makalah [3] yang menjelaskan proses ini sebagai berikut:

Konten yang diungkapkan adalah sama.

Kerentanan Bingxin

Tim Trail of Bits menerbitkan sebuah artikel [2] yang menunjukkan bahwa terdapat kerentanan dalam implementasi Fiat-Sharmir di sistem ZKP seperti Bulletproofs dan Plonk, yang memungkinkan pengguna jahat untuk memalsukan bukti untuk pernyataan acak.

Mengambil Plonk sebagai contoh, pada Putaran 2, 3, 4, dan 5 pembuatan bukti, algoritma Fiat-Shamir digunakan untuk menghasilkan angka acak.

Dalam makalah [3], banyak implementasi sumber terbuka dari sistem bukti pengetahuan-nol modern disurvei dan 36 ditemukan menggunakan transformasi Fiat-Shamir yang lemah, termasuk Bulletproofs, Plonk, Spartan, dan VDF Wesolowski. Seorang penyerang dapat menghasilkan bukti yang lolos verifikasi tanpa mengetahui rahasia bukti yang valid.

Contoh Kerentanan

1. gnark

Di sini, fs adalah contoh komputasi Fiat-Shamir. Saat menghitung parameter z(X) dalam pembuktian Round2, masukan publik tidak terikat pada tantangan, yang memungkinkan pemalsuan informasi pembuktian.

2. snarkjs

Selain itu, karena publicSignals tidak disertakan, informasi bukti dapat dipalsukan.

Meringkaskan

Dari konten yang diungkapkan, kita dapat melihat universalitas dan sifat luas dari kerentanan ini, yang akan menyebabkan kerusakan serius pada bukti tanpa pengetahuan. Dalam aplikasi praktis, kita perlu memperhatikan peninjauan kebenaran implementasi Fiat-Shamir dan menambahkan publik data saksi ke dalamnya. Dalam pembuatan angka acak, cegah penyerang memalsukan bukti.

Akhirnya, kami ingin mengucapkan terima kasih kepada Safeheron, penyedia layanan penyimpanan mandiri aset digital terkemuka yang menyediakan saran teknis profesional.

Dokumen Referensi:

[1]. https://datatracker.ietf.org/doc/html/rfc8235

[2]. https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/

[3]. https://eprint.iacr.org/2023/691.pdf