Seed Kurva NIST Terpecahkan: 5 Mitos Asal-usul ECDSA

Selama dua puluh lima tahun, seed kurva ECDSA dari NIST adalah kasus dingin paling dekat dengan 'kasus tak terpecahkan' di dunia kriptografi terapan. Lima nilai 160-bit yang tampak acak, diserahkan NIST dari NSA tanpa penjelasan sama sekali, menopang tanda tangan untuk segala hal mulai dari koneksi TLS Anda hingga transaksi Bitcoin. Minggu ini kasusnya ditutup, dan jawabannya hampir memalukan: seed-nya merupakan output dari generator lrand48() di library C, di-seed dengan timestamp Unix dari tahun 1997 dan 1998. Cuma itu. Tidak ada hash dari passphrase rahasia, tidak ada mesin eksotis — srand48(time(NULL)), pola persis yang diajarkan setiap kursus keamanan agar tidak pernah dipakai.

Penemuan ini datang dari model riset Anthropic, yang diarahkan ke masalah ini oleh seorang karyawan yang penasaran. Model itu mengenali signature statistik dari linear congruential generator era 1990-an dalam konstanta yang dipublikasikan, lalu menjalankan state-nya mundur sampai ketemu tanggal-tanggal kalender. Saya sudah cukup lama mengaudit sistem kriptografi untuk tahu ini penting — bukan karena kurvanya rusak (tidak), tapi karena ini meruntuhkan beberapa hal yang dengan yakin dipercaya industri kita. Mari kita bahas mitosnya satu per satu.

Mitos 1: Konstanta Tak Terjelaskan Berarti Ada Backdoor Tersembunyi

Kecurigaannya sebenarnya tidak gila. Saat NIST mempublikasikan kurva FIPS 186-2 pada tahun 2000, tiap kurva disertai seed yang hash-nya menentukan koefisien b kurva. NIST menyebut seed itu menjamin kurva 'verifiably random' — tapi tidak bisa atau tidak mau menjelaskan bagaimana seed itu sendiri dihasilkan. Koblitz dan Menezes menulis makalah panjang tentang kontroversi ini, dengan judul yang sengaja menyindir: 'A Riddle Wrapped in an Enigma.' Petunjuk terbaik komunitas datang dari Jerry Solinas di NSA, yang pada 2015 mengingat bahwa inputnya adalah hash dari sebuah frasa lucu, kira-kira seperti 'Give Bob and Jerry a raise.' Ia wafat pada 2023 tanpa ada yang berhasil memulihkan detailnya.

Kenyataan yang tidak enak bagi para penganut teori konspirasi, termasuk saya sendiri kadang-kadang: 'tidak terjelaskan' biasanya berarti 'tidak terdokumentasi', bukan 'jahat'. Proses pembuatannya sebenarnya adalah seorang developer menjalankan program C kecil, membiarkan PRNG default men-seed dirinya dari jam dinding, lalu mengambil kandidat pertama yang menghasilkan kurva yang layak dipakai. Seed P-256 yang dipublikasikan adalah kandidat nomor 1.842 dari sebuah run yang dimulai pukul 01.52 dini hari, 16 Agustus 1997. Itu bukan cara kerja badan intelijen yang menyelipkan jebakan teori bilangan. Itu seorang engineer pukul satu pagi yang menjalankan loop sampai keluar sesuatu yang valid.

Saya sudah sering melihat pola ini dalam incident review, lebih banyak dari yang bisa saya hitung. Ada nilai konfigurasi yang misterius, konstanta ajaib yang tidak terdokumentasi, langkah deployment yang tidak ada yang bisa jelaskan — dan postmortem-nya ternyata mengungkap itu jalan pintas yang masuk akal waktu itu oleh engineer yang capek, dan tidak pernah dicatat. Dosa NSA di sini bukan membuat backdoor di kurva-kurva itu. Dosanya adalah mengirim konstanta kriptografi ke seluruh dunia tanpa README.

Mitos 2: Metode Pembuatan Membuktikan Seleksinya Jujur

Sekarang bagian koreksi berlebihan. Banyak komentar minggu ini memperlakukan 'ternyata cuma timestamp' sebagai pembuktian mutlak. Bukan begitu, dan para peneliti di balik temuan ini berhati-hati untuk menyatakannya. Mengetahui bagaimana kandidatnya dibuat tidak memberi tahu Anda bagaimana kurva final dipilih — dan pemilihan itu berlangsung berbulan-bulan, dari Mei 1997 sampai April 1998.

Buktinya bisa ditafsirkan dua arah. Dalam run P-256, kandidat 876 juga menghasilkan kurva dengan orde prima dan ukuran yang tepat, dibangun dengan konvensi parameter yang sama — tapi dilewati. Kurva yang dipublikasikan adalah kandidat 1.842. Run P-224 melewatkan tiga kurva yang layak; run ANSI X9.62 melewatkan tujuh lagi. Kita hanya bisa melihat riwayat lengkap kandidat yang dibuang untuk yang masih terjangkau dalam catatan run. Jika seseorang menginginkan kurva dengan properti langka tertentu, secara prinsip mereka bisa mencari di antara timestamp sampai ketemu satu, lalu diam saja soal timestamp-nya. 'Melakukannya dan tidak bilang-bilang' selalu menjadi opsi.

Pendapat saya, setelah bertahun-tahun mengikuti riset kurva lemah: hipotesis backdoor memang terluka parah tapi belum mati secara formal. Kandidat yang dilewati jumlahnya cukup sedikit sehingga cherry-picking akan berarti kurva lemah itu umum dan mudah ditemukan — yang bertentangan dengan dua dekade kriptanalisis publik. Tidak ada yang pernah mempublikasikan distinguisher yang bisa memisahkan kurva ini dari kurva acak. Tapi 'tidak ada kelemahan yang diketahui' dan 'terbukti tidak ada kelemahan' adalah dua pernyataan yang berbeda, dan posisi yang jujur adalah yang pertama. Ini persis celah antara spesifikasi dan implementasi yang terjadi di level standar: spesifikasinya bilang 'verifiably random', dan implementasinya adalah 'apa pun yang ditunjukkan jam'.

Seed dibuat seperti cara seorang mahasiswa pascasarjana akan melakukannya: PRNG standar dan jam sistem. Skandalnya tidak pernah ada di matematikanya. Yang hilang adalah dokumentasinya.

Mitos 3: PRNG Lama yang Lemah Aman Selama Hanya Dipakai Sekali

Ini mitos yang seharusnya membuat setiap engineer yang pernah mengetik srand(time(NULL)) langsung duduk tegak. Seluruh tabir misteri selama dua puluh lima tahun itu ada karena satu properti desain dari lrand48(): ia membocorkan strukturnya sendiri. Generator ini hanya mengembalikan 31 bit teratas dari state 48-bit, sehingga output-nya selalu punya bit teratas bernilai nol. Jika ditulis sebagai word 32-bit, empat dari sepuluh seed kurva biner menunjukkan bit teratas nol di dua puluh word berturut-turut — kejadian dengan probabilitas sekitar satu banding 58.000 jika distribusinya uniform. Signature-nya sebenarnya kasatmata bagi siapa pun yang mau melihat.

Dari situ, serangannya murah sekali. Untuk memulihkan state kurva biner, Anda ambil output word pertama, brute-force 2^17 bit rendah yang tersembunyi, lalu cek apakah empat word berikutnya cocok. Itu hanya butuh beberapa milidetik komputasi. Untuk kurva prima, seed menyimpan lebih sedikit bit per output, jadi memulihkan state memerlukan serangan LCG terpotong klasik: modelkan sebagai masalah lattice dan hajar dengan LLL basis reduction. Materi standar, harfiah. Begitu state didapat, LCG bisa dijalankan mundur semudah maju, jadi Anda mundurkan sampai terlihat bentuk inisialisasi srand48 — bit rendah sama dengan 0x330E — lalu baca timestamp yang dipakai sebagai seed.

# The whole mystery, reproduced
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

Pelajarannya berlaku lebih luas dari badan standar. Setiap nilai 'tampak acak' yang Anda keluarkan — session token, request ID, salt, nama file — membawa sidik jari dari generator yang membuatnya. Jika generator itu adalah linear congruential engine atau Mersenne Twister, beberapa output saja sudah cukup merekonstruksi state internal, dan semua yang dihasilkan sebelum dan sesudahnya menjadi bisa diprediksi. Satu kali pemakaian, dua puluh lima tahun lalu, dalam file yang dimaksudkan agar terlihat seperti noise, terbukti bisa dibalik sepenuhnya. Saat saya mereview kode yang memakai RNG non-kriptografis untuk hal apa pun yang bisa diamati penyerang, ini adalah kisah perang yang akan saya kutip dari sekarang.

Mitos 4: Konstanta 'Nothing-Up-My-Sleeve' Tidak Pernah Jadi Perlindungan yang Sebenarnya

Gagasan 'nothing-up-my-sleeve' — menurunkan konstanta dari sesuatu yang jelas tidak bersalah, seperti digit pi — ada untuk membatasi derajat kebebasan perancangnya. Jika saya bisa menunjukkan konstanta saya berasal dari prosedur publik yang kaku, saya tidak punya ruang untuk menyelundupkan backdoor. Seed NIST gagal dalam tes ini secara prosedural: prosedurnya rahasia, jadi batas derajat kebebasannya tidak diketahui. Tapi yang sebenarnya dibongkar episode ini adalah: tes sleeve itu lebih lemah dari yang selama ini kita pura-pura percaya, bahkan ketika ia berfungsi.

Pertimbangkan apa yang sebenarnya diberikan oleh 'terverifikasi acak dari timestamp'. Timestamp hanya memberi sekitar 31 bit entropi untuk jendela waktu yang masuk akal. Siapa pun — termasuk penulis aslinya — bisa menggiling jutaan timestamp, menghasilkan jutaan kurva kandidat, lalu hanya mempublikasikan yang diinginkan, bersama seed-nya yang tampak polos. Jika kurva dengan kelemahan rahasia ada dengan rasio satu per sejuta, pencarian timestamp akan menemukannya dalam semalam. Seed membuktikan dari mana angka itu berasal dan hampir tidak mengatakan apa-apa tentang mengapa yang itu dipilih. Hal yang sama berlaku untuk skema hash-dari-passphrase, dan itulah sebabnya rumor soal frasa lucu Solinas juga tidak pernah benar-benar menenangkan.

Praktik modern yang lebih kuat adalah konstruksi kurva yang kaku: pilih koefisien terkecil yang memenuhi daftar kriteria keamanan publik, dengan aturan seleksi yang sudah ditetapkan sebelum pencarian dimulai. Itulah filosofi di balik Curve25519, dan alasan argumen kekakuan Dan Bernstein mengubah cara komunitas mengevaluasi kurva. Perlindungan nyata terhadap konstanta jahat tidak pernah berupa cerita turunan yang manis. Itu adalah meminimalkan ruang pencarian, mempublikasikan kriteria di muka, dan punya cukup mata independen pada matematikanya sehingga properti tersembunyi tidak bisa tetap tersembunyi. Mengaudit konstanta berarti mengaudit proses yang menyaringnya — dan itulah sebabnya pertanyaan-pertanyaan yang belum terjawab di sini (kandidat yang dilewati, base point P-256 dan sejenisnya yang belum dijelaskan, seed B-163 yang belum teridentifikasi) layak tetap terbuka di catatan, bukan dilupakan begitu saja di tengah perayaan.

Mitos 5: LLM Hanya Mengulang Hafalan — Mereka Tidak Bisa Melakukan Kriptanalisis Orisinal

Ini mitos yang paling menyakitkan, karena saya pernah percaya pada versi dari mitos ini. Masalah terbuka ini tidak terpecahkan selama seperempat abad meski ada hadiah publik sebesar $36.864 dan perhatian serius dari amatir yang cakap. Beberapa peneliti di Anthropic sudah mengejarnya sendiri, mengikuti petunjuk 'hash dari frasa lucu', dan tidak menemukan apa-apa. Lalu sebuah model riset internal, ditanya tanpa diberi tahu soal rumor itu, mencoba sudut pandang yang berbeda dalam waktu kurang dari setengah jam: alih-alih menebak input hash, ia bertanya perangkat lunak apa yang mungkin menghasilkan seed tersebut, menghipotesiskan PRNG library C era 1990-an, menulis pemindai yang menggeser diri di setiap seed sambil menguji 34 kombinasi generator dan potongan output, menemukan pola bit teratas nol, menjalankan serangan lattice pada output yang terpotong, dan menelusuri state itu mundur sampai ke tanggal-tanggal kalender.

Perhatikan apa sebenarnya alur kerja itu. Ini bukan recall — tidak ada dokumen pelatihan yang memuat jawabannya, karena jawabannya memang tidak ada di mana pun. Ini adalah pembentukan hipotesis ditambah penggunaan tool ditambah verifikasi, yang merupakan bentuk asli dari pekerjaan kriptanalisis. Model itu bahkan memeriksa kewarasannya sendiri di tengah jalan: apakah ini lingkungan uji simulasi, apakah hal yang sejelas ini benar-benar bisa tidak ditemukan selama 25 tahun, apakah kecocokan 160-bit dari seed 32-bit menyingkirkan kebetulan? Skeptisisme terhadap diri sendiri seperti itulah yang saya harapkan dari analis manusia, dan jujur saja, beberapa analis manusia melewatkannya. Kami sudah lama menguji mitos seputar apa yang sebenarnya dilakukan model-model ini di situs ini, dan ini adalah data point yang bersih: LLM sekarang bisa menjalankan penalaran forensik multi-langkah terhadap artefak dunia nyata, bukan sekadar benchmark.

Argumen balasan yang adil dari praktisi menyangkut provenance. Model itu tidak menemukan sendiri pemulihan state LCG atau LLL — ia berdiri di atas puluhan tahun kriptanalisis yang dipublikasikan oleh peneliti yang bernama maupun tidak, dan ia tidak bisa memberi tahu makalah siapa yang membentuk pendekatannya. Itu mengganggu saya lebih sedikit dibanding banyak orang lain. Pemindai, kode verifikasi, dan skrip reproduksinya bersifat publik; manusia di tim yang mengarahkan pertanyaan dan memvalidasi hasilnya. Mari kita akui pembagian kerjanya dengan jujur: mesin menyediakan pencarian hipotesis yang tak kenal lelah, manusia menyediakan penilaian dan akuntabilitas. Hadiah $36.864 yang diberikan kepada Internet Security Research Group adalah cara yang elegan untuk menutup perkara ini.

Apa Dampaknya bagi Audit Keamanan

Jadi di mana posisi engineer yang bekerja di lapangan? Ada beberapa pergeseran konkret dalam cara saya mendekati audit dari sekarang. Pertama, perlakukan setiap konstanta ajaib dalam protokol atau codebase sebagai artefak forensik, bukan fakta alam. Tanyakan generator apa yang mungkin menghasilkannya, periksa sidik jari struktural — bit teratas yang bias, word berurutan yang berkorelasi LCG, pemulihan state yang masuk akal secara timestamp — sebelum menerima 'ini acak' sebagai jawaban. Tooling untuk ini sekarang tersedia dengan sangat mudah.

Kedua, jika Anda mempublikasikan konstanta, publikasikan juga generatornya. Source code, input yang persis, lingkungan yang persis. 'Terverifikasi acak' tanpa resep yang bisa direproduksi hanya akan membeli dua puluh lima tahun kecurigaan dan hadiah di atas warisan Anda. Ketiga, tetaplah pakai P-256 — temuan ini meningkatkan kepercayaan pada kurva, bukan menurunkannya, dan model ancaman nyata untuk kurva elliptic adalah perangkat keras kuantum, bukan jam workstation tahun 1997. Tapi baca pertanyaan terbuka itu dengan jujur: base point yang belum dijelaskan dan kandidat yang dilewati adalah ujung longgar, dan kerja keamanan yang matang berarti menjaganya tetap tercatat.

Pelajaran terdalamnya adalah soal memori institusional. Jerry Solinas mengingat lelucon tentang kenaikan gaji yang ternyata salah. Menurut ucapannya sendiri, arsipnya mungkin masih tersimpan di hard drive dekat Tabut Perjanjian. Satu-satunya alasan kita tahu kebenarannya hari ini adalah karena output itu sendiri menyimpan struktur yang cukup untuk mengaku. Sistem Anda sekarang juga sedang menulis pengakuannya sendiri, dalam setiap ID, token, dan konstanta yang Anda kirim. Pastikan mereka mengaku sesuatu yang bisa Anda banggakan.