CuRvE

Kegagalan yang menarik bukanlah pada ECDSA itu sendiri. Perkhidmatan menjana satu skalar rahsia, kemudian membenarkan pemain menggantikan parameter lengkung eliptik sambil diam-diam menggunakan semula skalar yang sama. Akibatnya, kunci tandatangan berubah menjadi logaritma diskret pada kumpulan yang boleh dipengaruhi pemain.

Saat sempadan kepercayaan runtuh

Aliran yang terdedah itu setara dengan:

curve = curve_from_player_parameters()
base = curve.random_point()
public = secret_scalar * base

Bagi lengkung tetap yang dipilih dengan teliti, mendapatkan secret_scalar daripada base dan public sepatutnya sukar. Namun di sini, pemain boleh memilih lengkung yang tertib kumpulannya mempunyai komponen licin (smooth) yang besar. Pasangan awam tersebut kemudian mendedahkan skalar yang sama dalam kumpulan tempat logaritma diskret sengaja dijadikan jauh lebih mudah.

Semakan input turut beroperasi pada integer yang dihantar sebelum pustaka lengkung mengurangkannya modulo nombor perdana medan. Oleh itu, integer yang kongruen dengan pekali kecil boleh melepasi semakan saiz sambil tetap menghasilkan pekali kecil yang dikehendaki dalam medan tersebut.

Membina tertib kumpulan yang berguna

Dua keluarga lengkung memudahkan pencarian tertib:

• keluarga j = 1728, diwakili oleh lengkung dengan sebutan pemalar sifar;
• keluarga j = 0, diwakili oleh lengkung dengan pekali linear sifar.

Bagi setiap calon, pembinaan semula mengira tertib lengkung dan memfaktorkannya. Matlamatnya bukan tertib yang licin sepenuhnya. Memadai untuk mengumpulkan faktor kuasa perdana ke dalam modulus licin M yang cukup besar untuk mengehadkan skalar yang digunakan semula, sambil meninggalkan sebarang faktor besar yang diperlukan perkhidmatan dalam kofaktor selebihnya.

Ada satu butiran praktikal: titik asas rawak tidak semestinya mempunyai tertib penuh lengkung. Serangan mesti menggunakan tertib titik sebenar dan hanya mengekalkan faktor yang benar-benar membahagi subkumpulan tersebut.

Mendapatkan baki skalar

Dengan Q = dG, Pohlig–Hellman memecahkan logaritma diskret kepada masalah yang lebih kecil bagi setiap kuasa perdana yang membahagi bahagian licin tertib titik:

1. unjurkan G dan Q ke dalam setiap subkumpulan kuasa perdana;
2. selesaikan logaritma diskret yang lebih kecil dalam subkumpulan tersebut;
3. gabungkan bakinya menggunakan Chinese Remainder Theorem;
4. peroleh d mod M tanpa perlu meneka keseluruhan skalar sekali gus.

Cabaran itu menambah kekangan kedua: skalar ialah representasi integer big-endian bagi tepat 21 aksara ASCII huruf kecil. Jika r ialah baki yang diperoleh, setiap calon berbentuk:

d = r + kM

Panjang yang diketahui memberikan julat angka yang sempit. Memastikan kesemua 21 bait berada antara huruf kecil a dan z menyingkirkan hampir semua calon. Nilai yang tinggal boleh disahkan tanpa keraguan dengan menguji sama ada dG menyamai titik awam yang diberikan.

Memalsukan tandatangan yang sah

Setelah skalar diketahui, langkah terakhir hanyalah aritmetik ECDSA biasa dalam subkumpulan yang dipilih. Pilih nonce yang mempunyai songsangan modulo tertib titik, terbitkan r daripada titik nonce, kemudian kira:

s = inverse(nonce) * (message_digest + r * d) mod point_order

Pembinaan semula mengesahkan tandatangan palsu itu secara setempat sebelum menggunakan laluan pengesahan cabaran.

Pengajaran pertahanan

• Jangan gunakan semula skalar rahsia merentasi kumpulan atau parameter domain yang dikawal penyerang.
• Sahkan unsur medan kanonik selepas pengurangan, bukan sekadar panjang bit representasi yang dihantar.
• Sahkan lengkung, tertib subkumpulan, dan titik asas sebagai satu kesatuan.
• Anggap penjanaan rahsia berstruktur, seperti rentetan huruf kecil dengan panjang tetap, sebagai pengurangan entropi yang besar sebaik sahaja maklumat modular bocor.

Halaman acara: V1T CTF 2026 di CTFtime.