Bounty Seed Kurva Eliptik NIST

 (words.filippo.io)
1 poin oleh GN⁺ 2023-10-06 | 1 komentar | Bagikan ke WhatsApp
  • Seed dari 5 kurva eliptik NIST yang banyak dipakai dalam kriptografi modern berasal dari nilai yang diberikan NSA pada 1990-an, dan ada bounty $12.288 untuk menemukan teks asli sumbernya
  • Targetnya adalah P-192, P-224, P-256, P-384, P-521 dari FIPS 186-2, dan jika pemenang memilih pembayaran sebagai donasi ke lembaga amal 501(c)(3) di AS, jumlahnya menjadi 3 kali lipat, yaitu $36.864
  • Seed tersebut diketahui dibuat oleh Jerry Solinas pada 1997, dan kemungkinan berasal dari hash SHA-1 atas kalimat berbahasa Inggris, tetapi frasa aslinya hilang setelah penggantian atau peningkatan perangkat
  • Format frasa itu belum pasti, termasuk titik, baris baru, posisi dan format penghitung, serta apakah nama kurva disertakan, sehingga sekitar 12 ribu daftar hash dijadikan target serangan awal
  • Siapa pun yang pertama mengirim setidaknya 1 pre-seed akan mendapat $6.144, dan yang pertama mengirim kelima pre-seed akan mendapat sisa $6.144; urutan pengiriman ditentukan dari header Received pada server email

Target bounty dan nilai pembayaran

  • Tujuan bounty publik ini adalah menemukan nilai masukan hash (pre-seed) yang digunakan untuk membuat seed dari 5 kurva eliptik NIST
  • Total bounty ditetapkan sebesar $12.288, yaitu 12 Ki$
    • Jika pemenang memilih donasi ke lembaga amal 501(c)(3) di AS alih-alih uang tunai, totalnya naik menjadi $36.864
  • Hash yang menjadi target crack adalah 5 nilai berikut
    • 3045AE6FC8422F64ED579528D38120EAE12196D5
    • BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
    • C49D360886E704936A6678E1139D26B7819F7E90
    • A335926AA319A27A1D00896A6773A4827ACDAC73
    • D09E8800291CB85396CC6717393284AAA0DA64BA

Mengapa seed kurva NIST menimbulkan kecurigaan

  • Kurva NIST P-192, P-224, P-256, P-384, P-521 dipublikasikan dalam FIPS 186-2 pada 2000, dan mengikuti metode ANSI X9.62 yang menurunkan sebagian parameter dari output hash SHA-1 atas seed acak
  • Banyak sistem kriptografi memakai kurva NIST, terutama P-256 dan P-384
    • Kedua kurva ini termasuk dalam Commercial National Security Algorithm Suite
    • Keduanya juga dipakai pada sertifikat ECDSA X.509 yang melindungi sebagian besar web
  • Tulisan Steve Weis, NIST curve seed origins, merangkum hal-hal yang diketahui tentang seed acak dalam spesifikasi FIPS 186
    • Seed tersebut tampaknya diberikan oleh NSA
    • Diketahui dibuat oleh Jerry Solinas pada 1997
    • Kemungkinan dibuat dengan meng-hash kalimat berbahasa Inggris menggunakan SHA-1
  • Jerry Solinas pernah mengatakan bahwa seed contoh bisa berupa sesuatu seperti SHA1("Jerry deserves a raise."), tetapi frasa sebenarnya telah hilang, dan frasa serupa pun tidak cocok dengan hash yang ada

Penemuan pre-seed dapat mengurangi ketidakpercayaan

  • Dalam evaluasi terbaru, kurva NIST terlihat lebih positif dalam beberapa hal
    • complete addition formulas mengurangi footgun utama
    • Metode perancangan antarmuka yang lebih aman kini telah diketahui
    • Nilai kurva berorde prima yang kebal terhadap serangan cofactor juga makin jelas
  • Di kalangan sebagian non-praktisi, masih ada kekhawatiran bahwa NSA mungkin memilih seed secara sengaja untuk mendapatkan kurva yang lemah
  • A riddle wrapped in an enigma karya Koblitz dan Menezes berpendapat bahwa bahkan jika NSA sepenuhnya mengendalikan seed, serangan seperti itu tetap kurang meyakinkan
    • Karena itu akan memerlukan kelas kurva lemah yang cukup besar sehingga tidak ditemukan oleh akademisi maupun industri selama 25 tahun
  • Kekhawatiran ini mungkin tidak cukup berdasar, tetapi menemukan pre-seed dapat membantu mengurangi FUD seputar kurva NIST
  • Menemukan preimage berbahasa Inggris tidak sepenuhnya menjamin rigidity, tetapi dapat mengisi satu potongan yang hilang dalam sejarah kriptografi

Petunjuk yang diketahui tentang nilai masukan hash

  • Nilai masukannya kemungkinan besar adalah frasa berbahasa Inggris yang menyebut Jerry Solinas, dan mungkin juga memuat nama orang lain serta penghitung
  • Alasan kuat mengapa penghitung mungkin diperlukan adalah karena, bergantung pada ukuran bit kurva, hanya sekitar 1 dari 192 hingga 521 hash yang cocok untuk pembentukan kurva
    • Untuk kurva terbesar, ada peluang 99% bahwa penghitungnya kurang dari 2400
    • Untuk P-256, ada peluang bahwa penghitungnya kurang dari 1175
  • Seed untuk P-192 dan P-256 muncul sebagai contoh dalam standar ANSI X9.62 sebelumnya, sedangkan sisanya baru muncul dalam FIPS 186-2, sehingga struktur kalimatnya bisa berbeda
  • Target bounty hanya 5 kurva NIST berorde prima, tetapi jika biaya pengujiannya rendah, contoh lain dari ANSI X9.62 dan seed binary curve dari FIPS 186-2 juga bisa dicoba
    • ANSI prime192v2, prime192v3, prime239v1, prime239v2, prime239v3 bukan target bounty
    • NIST B-163, B-233, B-283, B-409, B-571 juga bukan target bounty

Format string yang mungkin dan daftar serangan

  • Format string itu sendiri masih menjadi misteri
    • Kalimat bisa saja diakhiri titik, atau tidak
    • Bisa ada baris baru, atau tidak
    • Penghitung bisa berupa desimal, bisa memakai leading zero, atau bisa berupa biner 16-bit atau 32-bit
    • Penghitung bisa diletakkan setelah titik atau dipisahkan dengan cara lain
    • Semua seed bisa saja dibuat dengan menambahkan penghitung berbeda pada kalimat yang sama, atau setiap seed memakai kalimat berbeda
    • Nama atau ukuran kurva mungkin disertakan dalam frasa
  • Karena ingatan manusia mudah keliru, ada kemungkinan sebagian detail dalam kesaksian tidak langsung itu salah
  • Bisa juga yang digunakan bukan penghitung, melainkan hash berulang seperti SHA-1(s), SHA-1(SHA-1(s))
  • Kandidat lain adalah memulai dari SHA-1(s) lalu menaikkan nilai hash seperti pada ANSI X9.62 Section A.3.3.1
  • Sebagai daftar target serangan, disediakan nist-and-ansi-prime-order-seeds-increments-99-percent.txt berisi sekitar 12 ribu hash
    • Daftar ini mencakup ruang probabilitas 99% untuk masing-masing prime order curve seed di FIPS 186-2 dan ANSI X9.62
    • Jika biaya memeriksa banyak hash rendah, disarankan menjadikan daftar ini sebagai target serangan
    • Jika memungkinkan, membandingkan hanya 16 byte pertama dari hash pun akan memberi hasil yang sama
  • SHA-1 sangat cepat untuk brute force, sehingga ini cocok bagi orang yang berpengalaman dalam cracking passphrase dan brute force brainwallet

Cara pengiriman dan syarat pembayaran

  • Orang pertama yang mengirim pre-seed dari 5 kurva NIST berorde prima ke seeds@filippo.io lewat email akan menerima bounty
  • Struktur pembayarannya terdiri dari dua tahap
    • Orang pertama yang mengirim minimal 1 pre-seed akan menerima setengah bounty, yaitu $6.144
    • Orang pertama yang mengirim seluruh 5 pre-seed akan menerima sisa $6.144
    • Satu orang bisa menerima kedua pembayaran ini, jadi tidak perlu menunggu sampai kelima-limanya ditemukan
  • Pemenang bisa memilih menerima uang tunai atau donasi ke lembaga amal 501(c)(3) di AS
    • Jika memilih donasi amal, nilainya menjadi 3 kali lipat
    • Pilihan lembaga amal yang bertentangan secara ekstrem dengan nilai pihak penyelenggara dapat ditolak
    • Jika penerima adalah warga AS atau warga negara Italia yang secara hukum tidak bisa menerima transfer, maka harus memilih opsi donasi amal
    • Pajak atas bounty tunai menjadi tanggung jawab penerima
  • Subjek email pengiriman harus memuat ANTISPAM agar lolos aturan allowlisting
  • Urutan pengiriman ditentukan secara final oleh header Received pada host email
  • Bounty akan kedaluwarsa jika seed menjadi diketahui publik; jika tidak, bounty tetap berlaku sampai ada pengumuman lain di halaman ini
    • Jika bounty dibatalkan atau nilainya diturunkan, akan ada pemberitahuan 6 bulan sebelumnya
  • Tidak ada batasan pada metode untuk menemukan seed
    • Brute force, tebakan cerdas, investigasi, pemulihan backup NIST lama, dan metode lain semuanya diperbolehkan
    • Ada syarat bahwa jika tidak diinginkan, penyelenggara tidak akan menanyakan metode yang digunakan

Bacaan terkait

1 komentar

 
GN⁺ 2023-10-06
Pendapat di Hacker News

  • Latar belakangnya cukup lucu: belakangan beredar cerita bahwa seed “acak” untuk NIST P-curve yang dibuat Jerry Solinas dari NSA pada 1990-an sebenarnya adalah hasil hash SHA1 dari string variasi "Give Jerry a raise"
    Saat itu, memasukkan string ke SHA1 dianggap sebagai mekanisme kepercayaan karena struktur seed akan hilang, sehingga NSA tidak bisa sengaja memilih seed yang lemah
    Namun pada 2000-an, NIST/NSA merusak reputasinya sendiri, sehingga penjelasan itu saja tidak lagi cukup untuk meredam teori konspirasi; kemudian ketika NIST ingin menunjukkan bahwa seed tersebut benign dan Jerry Solinas mencoba merekonstruksinya, konon ia justru lupa string yang ia gunakan
    Bagi penganut teori konspirasi sejati, mereka mungkin menganggap tidak akan ada yang bisa menemukan string pembuat seed ini, tetapi jika ada yang menemukannya, itu bisa menjadi pukulan cukup besar bagi teori bahwa NIST P-curve dibuat secara jahat, jadi ini bounty yang menarik

    • Menurut saya, sekalipun seseorang menemukan bahwa hash dari string seperti "Give Jerry a raise of $100000 dollars now!!!" cocok dengan seed, itu bukan bukti bahwa tidak ada niat jahat
      Sebab jika mereka mengetahui sifat khusus yang harus dimiliki kurva lemah, mereka bisa saja melakukan hash terhadap sangat banyak variasi string serupa hingga memilih konstanta dengan sifat yang diinginkan
    • Pada akhir 1990-an, metode menggunakan MD5 dan SHA1 bersama-sama untuk “ketahanan tambahan” dalam konstruksi acak juga sempat populer
      SSLv2 dan SSLv3 adalah contoh bagus, dan walaupun ukuran output-nya cocok dengan SHA1, tidak akan terlalu mengejutkan jika ternyata pipeline-nya seperti echo "$string" | md5sum | sha1sum
    • Untuk sejarah yang lebih panjang, lihat makalah Koblitz dan Menezes yang disebut dalam tulisan, “A Riddle Wrapped in an Enigma”. Makalah ini juga membahas mengapa pada 2015 NSA mengatakan kita harus bergerak ke dunia pascakuantum
      https://eprint.iacr.org/2015/1018
      https://eprint.iacr.org/2015/1018.pdf
      Dugaan backdoor serupa juga ada pada (EC)DSA, dan para pendukung RSA mengklaim NSA mendorong DSA karena telah memasang backdoor di dalamnya, tetapi tidak ada bukti, dan selama 20 tahun juga tidak ditemukan cara untuk memasang backdoor pada DSA atau ECDSA
      Ada juga anekdot bahwa dalam sebuah rapat standardisasi, perwakilan NSA pergi untuk menelepon lalu kembali dan mengatakan bahwa NSA percaya ECC cukup untuk komunikasi aman semua lembaga pemerintah AS, termasuk Federal Reserve, yang membuat semua orang terkejut
      Penyesuaian DES kemudian terbukti sebagai pertahanan terhadap differential cryptanalysis, dan sebagaimana kelemahan SHA asli, SHA-0, tidak ada pada SHA-1 final, tindakan-tindakan NSA lainnya juga dipandang mencurigakan
    • Saya pernah membakar CPU secara berlebihan untuk mencoba menemukan input yang menghasilkan nilai “acak” sekitar 166-bit yang dipakai untuk menyusun G pada secp256k1 dan secp224k1, tetapi gagal
      Pada kedua kurva, pemilihan G adalah penggandaan titik dengan koordinat x yang ukurannya secara mencurigakan pas, dan karakteristik itu sama pada kedua kurva
      Pada kurva-kurva ini, pemilihan G adalah satu-satunya input dengan entropi besar, tetapi sebenarnya dapat dibuktikan hampir tidak relevan, dan orang yang memilihnya hanya akan mengetahui satu logaritma diskret arbitrer tertentu
      Dalam protokol yang dipaksakan, ini mungkin bisa menjadi backdoor, tetapi akan sangat dibuat-buat; meski begitu, karena itulah satu-satunya parameter yang tidak diketahui, saya rasa tetap layak dicari
      Jika seed P-curve ditemukan, mungkin mirip dengan seed yang dipakai untuk titik generator kurva lain, sehingga misteri kecil itu juga bisa terpecahkan
    • Untuk tujuan seperti ini, biasanya standar yang dipakai adalah konstanta transendental seperti π atau e. Karena tidak bisa dipilih
      Frasa secara teoretis bisa dipilih agar menghasilkan hash yang diinginkan

  • GCHQ Inggris mempekerjakan lebih banyak matematikawan daripada laboratorium atau universitas mana pun di negaranya. Lembaga padanannya di AS kemungkinan juga serupa
    Pertukaran kunci Diffie-Hellman pun sudah diketahui GCHQ dan NSA sebelum Diffie dan Hellman menemukannya kembali
    Sulit untuk memastikan kemampuan dasar badan intelijen, dan ini bukan berarti mereka benar-benar mengetahui keluarga kurva lemah semacam ini, tetapi juga sulit dianggap mustahil. Bidang ini memang pekerjaan utama mereka

    • Saya rasa memang tepat untuk curiga. Terutama karena argumen bahwa hal itu mustahil disajikan seolah-olah bersifat matematis, padahal sebenarnya lebih dekat ke argumen sosial
      Biasanya argumennya adalah kalangan akademik begitu hebat sehingga kalau NSA melakukan sesuatu, pasti sudah ditemukan; dan kalau tidak setuju, orang akan dianggap menyebarkan FUD karena tidak paham. Tulisan ini juga mengulang jalur itu, tetapi bagus bahwa bounty yang terorganisasi membuat masalah ini diperlakukan lebih serius
      Saya pernah mengerjakan kriptografi di masa lalu, selama beberapa tahun secara rutin meninjau makalah kriptografi untuk pekerjaan, menghadiri konferensi dan berbicara dengan peneliti, serta mengimplementasikan beberapa kriptografi kurva eliptik yang “tidak biasa”. Dari posisi yang bukan sepenuhnya orang dalam tetapi juga bukan sepenuhnya orang luar, pandangan umum ini tampak berbahaya
      Argumen intinya ada dua: jika serangan kleptografi terhadap standardisasi kurva NIST memungkinkan, akademisi atau industri pasti sudah menemukannya; dan karena Dual_EC_DRBG langsung dicurigai, komunitas kripto terbuka berarti piawai menemukan backdoor
      Argumen pertama kurang meyakinkan. Di akademia ada masalah file drawer dan insentif “publish or perish”; jelas mana yang lebih menguntungkan bagi peneliti muda: membuat algoritma zero-knowledge proof baru lalu menerbitkan makalah yang akan dikutip, atau menyerang algoritma yang diyakini semua orang kuat dan mungkin tidak mendapat apa-apa
      Dasarnya adalah konsensus pakar bahwa “banyak orang pintar telah menelitinya secara mendalam tetapi tidak menemukan apa-apa”, tetapi karena di akademia sulit menerbitkan hasil negatif, tidak ada cara untuk mengetahui seberapa banyak upaya yang benar-benar dicurahkan
      Kleptografi, yaitu cara memasukkan backdoor ke dalam standar, juga hampir tidak berguna kecuali bagi NSA, sehingga bukan jalur karier yang bagus, dan kurang menguntungkan untuk beralih ke industri maupun mendapatkan sitasi
      Sebaliknya, NSA bisa membayar lebih tinggi daripada akademia, mempekerjakan lebih banyak peneliti daripada seluruh akademia untuk mendedikasikan diri pada riset yang berpeluang gagal tinggi atau hanya berguna untuk backdoor standar, dan selama puluhan tahun bisa melakukan riset multidisiplin yang tidak mampu dilakukan riset kriptografi akademik karena keterbatasan anggaran hardware
      Jika harus bertaruh siapa yang lebih memahami ECC, NSA atau akademia, daya tembaknya ada di pihak pemerintah dan tidak sebanding. Jumlah doktor matematika yang dipekerjakan pemerintah kira-kira bisa diperkirakan, tetapi kita tidak tahu berapa daya tembak yang benar-benar dikerahkan akademia ke ruang masalah ini
      Argumen kedua juga tidak ideal. Bukan hanya Dual_EC_DRBG, orang-orang juga langsung menyuarakan kekhawatiran terhadap kurva NIST. Bedanya hanya pada kasus pertama sudah ada algoritma yang diketahui untuk menjalankan serangan yang diperlukan, sedangkan pada kasus kedua tidak ada
      Cara untuk membuat perdebatan seperti ini tidak perlu sejak awal sudah diketahui selama puluhan tahun, dan itulah alasan kurva NIST dibuat dari output SHA1. Waktu terbaik untuk menghapus kurva NIST secara bertahap adalah puluhan tahun lalu; waktu terbaik kedua adalah sekarang
    • NSA juga mempekerjakan profesor matematika teori bilangan dari AS

  • Alasan berkontribusi pada bounty ini adalah, jika frasa itu benar-benar bisa di-crack seperti password, mengetahuinya akan punya makna historis yang besar

  • Fakta bahwa kurva eliptik NIST dibuat dengan melakukan hash terhadap seed yang diberikan NSA cukup meresahkan
    Kedengarannya seperti, “Jangan khawatir, ini dibuat dengan meng-hash kalimat sepele. Sekarang kami sudah lupa, tapi itu cuma Jerry bercanda soal kenaikan gaji”
    Sulit dipercaya mengapa tidak dilakukan verifikasi yang kuat lebih awal, dan mengapa tidak memilih seed yang lebih masuk akal, misalnya dengan mencampur seed acak dari beberapa pihak yang kepentingannya berbeda serta generator bilangan acak hardware

    • Itu terasa begitu karena kita hidup pada 2023 dan melihatnya dengan mengetahui apa yang terjadi sejak 1990-an hingga sekarang
      Cara seperti itu memang akan bagus, tetapi saat itu mungkin tidak banyak orang yang melihat kebutuhannya
    • Kalau sebagian besar traffic internet saat ini terenkripsi, orang jadi bertanya-tanya mengapa data center raksasa seperti Bluffdale diperlukan
      https://en.wikipedia.org/wiki/Utah_Data_Center

  • Ada video Profesor Dan Boneh yang menjelaskan latar belakangnya: https://youtu.be/8WDOpzxpnTE?t=892

  • Jika saya memahaminya dengan benar, apakah artinya komunitas menerima string mencurigakan yang asal-usulnya tidak diketahui, padahal sangat mudah menggantinya menjadi string yang asal-usulnya jelas dengan memasukkan input lain yang diketahui ke hash?

    • Pemahaman itu benar, jadi ini cukup katastrofik. Saya teringat “sudah hampir sampai” dan “tugasmu cuma satu”
      Sayangnya, sejauh yang saya tahu, ini satu-satunya kasus ketika ketidakmampuan disebut-sebut terkait NSA dan standar kripto; biasanya ceritanya justru ke arah sebaliknya
      Yang lebih bermasalah adalah NIST sudah punya riwayat memasukkan backdoor ke standar terkait kurva eliptik, dan bahwa mekanisme ini tidak menciptakan kepercayaan juga langsung ditunjukkan, tetapi NIST maupun NSA tidak melakukan apa pun. Sama seperti pada Dual_EC_DRBG
      Yang lebih bermasalah lagi, pada 2015 NSA secara eksplisit mengatakan agar tidak melakukan upgrade dari kurva NIST ke kurva lain setelahnya. Alasannya, komputer kuantum akan segera menjadi cukup bagus untuk mematahkan seluruh ECC, sehingga semua orang harus pindah ke kriptografi pascakuantum
      Jika ECC berfungsi dengan baik, komputer kuantum masih jauh, dan mereka ingin membuat orang tetap terikat pada kurva NIST selama mungkin, persis itulah yang akan mereka katakan
      Komunitas kripto sulit dibilang terhormat dalam situasi ini. Hampir 25 tahun sudah berlalu, dan ada kurva-kurva yang lebih baru tanpa masalah ini, jadi mengapa kurva NIST masih digunakan? Di mana upaya untuk menghentikannya secara bertahap seperti SHA1? Tulisan ini malah tampak seperti mempromosikan kurva-kurva itu

  • Jika merasa beruntung, Anda bisa mencoba menebak hash SHA1 di sini: https://wending.dev/hash_guessing/

    • Bukankah itu hanya menghasilkan SHA1 dari string input? Seperti yang disebutkan dalam tulisan, harus ada semacam counter yang disertakan
      Kalau pembuat seed di NSA tahu sedikit saja tentang kriptografi dan komputer, tidak mungkin mereka memasukkan 500 frasa berbeda secara manual sampai mendapatkan kurva yang bagus
      Sekalipun begitu, variasi yang mungkin tidak ada habisnya: menambahkan titik di akhir, mengubah huruf besar-kecil, memakai kapitalisasi gaya judul, dan seterusnya
      Daftar variasi masuk akal yang perlu dicoba hampir mustahil menjadi lengkap, tetapi jika halaman ini hanya menghasilkan hash SHA1 seperti sekarang, bahkan bila Anda menebak string dengan tepat sampai tanda baca dan huruf besar-kecilnya, menemukan hash sebenarnya praktis mustahil
      Minimal harus bisa memeriksa apakah 10 byte di depan atau belakang cocok, untuk memastikan apakah hash hasilnya adalah nilai yang dinaikkan. Meski begitu, kebanyakan hanya akan membuang-buang waktu, dan penulisnya juga pasti tahu ini tidak akan mengarah ke mana-mana
      Di halaman itu seharusnya tertulis bahwa ini hanya mainan demo, dan meskipun tebakannya benar, tidak akan membantu menemukan seed sebenarnya

  • Setelah lama menyaksikan perdebatan sengit para kriptografer, pelajaran yang saya dapat adalah “jangan bertaruh melawan Bernstein, dan jangan percaya NIST”
    Sekarang sepertinya harus direvisi menjadi “jangan bertaruh melawan Bernstein atau Filippo, dan jangan percaya NIST. Jika dua aturan ini bertentangan, tetap jangan percaya NIST”

  • Memang benar SHA-1 sudah dipecahkan, tetapi saya mengira masalahnya terutama berupa collision lewat length extension attack atau known-plaintext attack
    Kalau hanya diberi hash, saya kira mencari passphrase pada praktiknya masih sulit ditangani

    • Benar. SHA-1 masih dianggap memiliki preimage resistance
      Namun jika hipotesis struktur seed itu benar, preimage resistance tidak terlalu penting di sini. SHA-1 sangat cepat dan mudah diparalelkan, jadi seseorang yang gigih menyisir ruang variasi dari "Jerry needs a raise" punya peluang cukup besar menemukan input aslinya
    • Ini hanyalah dictionary attack, dan begitulah sebagian besar hash kata sandi dibobol
      Tidak terlalu berkaitan dengan SHA1 itu sendiri