Kriptografi terapan. Bagaimana kami mengembalikan bitcoin sebesar 300 ribu dolar

Saya akan berbagi dengan Anda satu cerita. Sekitar dua puluh tahun yang lalu, saya menerima gelar dalam bidang fisika, tetapi terlibat dalam rekayasa terbalik dan pembacaan sandi. Perusahaan kami AccessData bekerja pada akhir 90-an dan awal 2000-an. Kemudian pemerintah AS secara bertahap mencabut pembatasan pada ekspor kriptografi, namun, perlindungan kata sandi di sebagian besar program masih agak tidak berguna. Kami mengambil program kantor, saya melakukan reverse engineering dan menemukan algoritma enkripsi, dan kemudian merusak perlindungan kriptografi.

Itu adalah aliran teka-teki matematika yang menarik, tapi tidak terlalu sulit. Sepanjang waktu saya menulis tentang empat puluh cracker kata sandi. Kami menjualnya kepada pengguna rumahan, administrator sistem, dan lembaga penegak hukum lokal dan federal. Saya harus pergi ke pusat pelatihan penegakan hukum federal di Glinko beberapa kali untuk menjelaskan kepada orang-orang dari Secret Service, FBI dan ATF dasar - dasar kriptografi dan bagaimana menggunakan produk kami.

Saya terutama ingat dua proyek. Yang pertama adalah Microsoft Word 97. Sebelum muncul, file dienkripsi menggunakan XOR byte teks yang jelas dan string 16 byte yang dihasilkan dari kata sandi. Bytes paling umum dalam file Word biasanya 0x00, 0xFF, atau 0x20 (spasi), jadi kami hanya memilih karakter yang paling umum di setiap kolom dan memeriksa 3 hingga ¹⁶ opsi. Pemulihan kunci biasanya terjadi secara instan, tetapi agar orang tidak berpikir bahwa mereka telah membuang-buang uang, kami memasukkan animasi kecil yang mirip dengan adegan peretas Hollywood dengan banyak karakter acak, dari mana kata sandi yang benar secara bertahap muncul.

Microsoft Word 97 telah mengubah segalanya. Mungkin MSDN juga mengungkapkan format enkripsi, tetapi perusahaan kecil kami tidak mampu berlangganan. Dan bukan fakta bahwa kita akan diizinkan untuk menulis program peretasan setelah menerima informasi. Untuk memahami, dalam SoftICE saya mengatur breakpoint segera setelah memasukkan kata sandi, dan kemudian perlahan-lahan naik tumpukan sampai saya menemukan suatu algoritma. Ini sebelum rilis IDA Pro, jadi saya memiliki lusinan halaman cetakan dengan kode assembler bergaris-garis dengan spidol merah di dinding saya. Saya sangat senang ketika saya akhirnya menemukan jawabannya. Pada saat itu, Microsoft hanya diizinkan mengekspor kriptografi 40-bit, sehingga perusahaan patuh menerapkan kriptografi yang diizinkan secara ketat: mereka berulang kali mengacak kata sandi dalam MD5 menggunakan "garam" (byte yang dipilih secara acak dari file),untuk mendapatkan kunci 40-bit, maka garam ditambahkan ke dalamnya dan hash lagi. Memeriksa kata sandi pada komputer pada waktu itu membutuhkan sekitar setengah detik. Kami harus menggunakan serangan kamus karena hampir tidak mungkin untuk memecahkan kata sandi dengan kekerasan. Akibatnya, kami menulis cracker kata sandi untuk perusahaan dan agensi besar. Program ini mengeksekusi bruteforce dari ruang kunci 40-bit menggunakan instruksi MMX Pentium yang mewah ini. Saya mendengar bahwa dia pernah bekerja selama sembilan bulan sebelum saya mengambil kata sandi.Program ini mengeksekusi bruteforce dari ruang kunci 40-bit menggunakan instruksi MMX Pentium yang mewah ini. Saya mendengar bahwa dia pernah bekerja selama sembilan bulan sebelum saya mengambil kata sandi.Program ini mengeksekusi bruteforce dari ruang kunci 40-bit menggunakan instruksi MMX Pentium yang mewah ini. Saya mendengar bahwa dia pernah bekerja selama sembilan bulan sebelum saya mengambil kata sandi.

Proyek lain yang sangat menyenangkan adalah arsip zip. Phil Katz, pencipta PKZIP, membuat keputusan yang tidak biasa pada waktu itu untuk mendokumentasikan format file-nya dan memasukkan dokumentasi ini dalam paket perangkat lunak, yang menjadikan ZIP format favorit untuk pengembang. Roger Schlafly mengembangkan stream cipher untuk mengenkripsi arsip. Standar zip dengan cepat menjadi yang paling populer di bawah Windows, dan banyak format lain, seperti file java .jar dan dokumen OpenOffice, sebenarnya file zip dengan struktur direktori tertentu di dalamnya. Versi open source dari program ini disebut InfoZIP, itu adalah dasar dari hampir semua pengarsip zip berpemilik, seperti WinZip. Ketika saya mulai meretas WinZip, ia menguasai 95% pasar.

Eli Biham dan Paul Kocher menerbitkan deskripsi serangan dengan plaintext yang diketahui (teks sebelum enkripsi), tetapi dalam kasus kami, plaintext yang dikenal diarsipkan . Untuk mendapatkan kode Huffman di awal file terkompresi, Anda pada dasarnya membutuhkan seluruh file. Serangan itu praktis tidak berguna untuk penegakan hukum.

Zip cipher berisi 96 bit keadaan internal, dibagi menjadi tiga blok 32-bit yang disebut key0, key1dankey2. Yang pertama dan ketiga adalah keadaan internal dua salinan CRC32, register geser linier dengan umpan balik (model matematika sederhana yang memungkinkan Anda untuk membuat urutan pseudorandom). Singkatnya, untuk memperbarui keadaan dengan byte data baru, Anda menggeser semuanya ke bawah dengan satu byte (membuang byte yang lebih rendah), dan kemudian melakukan XOR dengan konstanta dari tabel konversi yang diindeks oleh byte data setelah XOR dengan byte yang lebih rendah. key1Apakah keadaan internal generator congruent terpotong terpotong (TLCG). Untuk memperbarui keadaan internalnya, kami menambahkan byte data, dikalikan dengan konstanta, yang akan kami panggilc, dan tambahkan satu. Cipher bekerja sebagai berikut: masukkan byte data dalam CRC32 pertama, lalu ambil byte bawah dan masukkan dalam TLCG, lalu ambil byte atas dari sana dan masukkan dalam CRC32 kedua, kemudian ambil state dan square (kurang-lebih), lalu keluarkan byte kedua menghasilkan aliran byte. Untuk menginisialisasi 96 bit status internal, Anda mulai dengan status dikenal dan mengenkripsi kata sandi, dan kemudian mengenkripsi sepuluh byte garam.

PKZIP mendapatkan byte garamnya, mengalokasikan memori tanpa menginisialisasi, sehingga berisi bit bahan dari program atau gambar yang sedang berjalan, atau dokumen, apa pun. Ini berfungsi dengan baik pada Windows, tetapi pada banyak sistem Unix, memori diinisialisasi secara otomatis ketika dialokasikan. InfoZIP memilih byte garam menggunakan fungsirandBahasa C. Dia menginisialisasi keadaan generator angka acak dengan membuat cap waktu XOR pada ID proses, dan kemudian menghasilkan sepuluh byte per file. Dalam hal ini, mengetahui cap waktu dan pengidentifikasi proses, dimungkinkan, secara teoritis, untuk memulihkan byte header, yang, pada gilirannya, memungkinkan untuk melakukan serangan oleh Biham dan Kocher. Tampaknya penulis InfoZIP tahu tentang serangan ini karena mereka melangkah lebih jauh - dan mengenkripsi header menggunakan kata sandi. Dengan demikian, penyerang hanya memiliki dua kali plaintext terenkripsi, dan serangan itu tidak akan berhasil.

Saya perhatikan ini, karena kata sandi sama di kedua pass, byte pertama dari stream sama di masing-masing pass. Dengan cara yang sama seperti ketika sakelar lampu diaktifkan dua kali, sakelar tetap berada di tempat ia berada di awal, ketika byte diulangi XOR dengan byte stream yang sama, tetap tidak tersentuh. Ini memungkinkan saya untuk mengembangkan serangan yang sangat kuat hanya pada ciphertext : setelah menerima lima file terenkripsi dalam arsip, saya bisa menampilkan keadaan internal fungsirandtanpa harus melihat cap waktu atau mengetahui proses ID. Lalu saya bisa menghasilkan tajuk tidak terenkripsi asli. Karena hanya beberapa bit di setiap bagian cipher memengaruhi bagian selanjutnya, saya juga bisa menebak beberapa bit status dan memeriksa apakah mendekode byte berikutnya dua kali memberikan jawaban yang saya harapkan. Ketika saya bergerak maju, saya harus menebak semakin sedikit bagian dari kunci itu. Setiap file tambahan juga diizinkan untuk mengecualikan lebih banyak bahan kunci potensial; pada saat itu, butuh beberapa jam di satu desktop. Saya menerbitkan sebuah artikel tentang ini dan mendapat kesempatan untuk mempresentasikannya di Jepang pada konferensi Fast Software Encryption 2001.

Segera saya meninggalkan AccessData, bekerja untuk sebuah startup di jaringan saraf selama setahun, menghabiskan tiga tahun belajar untuk gelar master dalam ilmu komputer di Universitas Auckland dengan Chris Kaloud, memulai studi doktoral saya dengan fisikawan matematika John Baez di University of California Riverside, bekerja selama enam tahun Sebagai bagian dari tim Keamanan Terapan Google, ia menyelesaikan doktornya dan beberapa tahun kemudian menjadi CTO dari startup baru.

Sekitar setengah tahun yang lalu, secara tak terduga saya menerima pesan di LinkedIn dari seorang pria Rusia. Dia membaca artikel yang saya tulis 19 tahun lalu dan ingin tahu apakah serangan itu akan berhasil pada arsip yang hanya berisi dua file. Analisis cepat menunjukkan bahwa itu membutuhkan sejumlah besar daya komputasi dan uang. Karena hanya ada dua file, pada setiap tahap pemilihan ada banyak kesalahan positif. Hasilnya adalah ^2.773 kunci yang mungkin untuk pengujian, hampir 10 sextillion. Saya menghitung bahwa cluster besar pada GPU akan bekerja selama satu tahun, dan biayanya sekitar 100 ribu dolar. Dia memukul saya, mengatakan bahwa dia setuju untuk menghabiskan begitu banyak uang untuk mengembalikan kunci.

Faktanya adalah bahwa pada Januari 2016, dia membeli bitcoin sekitar $ 10-15 ribu dan meletakkan kunci dalam file zip terenkripsi. Sekarang harganya lebih dari $ 300 ribu, dan dia tidak bisa mengingat kata sandi. Untungnya, dia masih memiliki laptop asli, dan dia tahu persis waktu enkripsi. Karena InfoZip mengeluarkan entropi berdasarkan stempel waktu, ini berjanji untuk secara signifikan mengurangi jumlah opsi kunci yang mungkin "menjadi hanya" 10 trilyun - dan membuat serangan itu cukup layak dalam beberapa bulan di pertanian GPU rata-rata. Kami menandatangani kontrak dan saya mulai bekerja.

Saya menghabiskan beberapa waktu untuk memulihkan serangan yang dijelaskan dalam artikel. Yang membuatku kecewa, ada beberapa detail rumit yang aku lewatkan dalam artikel itu, tetapi aku menyelesaikannya lagi. Dan kemudian saya menemukan bahwa saya telah membuat kesalahan besar dalam mengevaluasi jumlah perhitungan!

Dalam serangan awal saya, saya menebak byte tinggi dari tombol key1 · c, key1 · c ² , key1 · c ³ dan key1 · c ⁴ . Pada saat saya menebak byte keempat ini, saya tahu keadaan lengkap dari sisa cipher; Saya hanya perlu mengkonversi empat byte ini ke key1 asli, dan hanya itu. Saya akan pergi ke ruang negara 32-bit untuk key1 dan memeriksa masing-masing untuk melihat apakah itu memberikan byte tinggi yang benar. Namun, di sini harus memeriksa kunci trilyun; jika Anda perlu melakukan 2 ³² tes pada masing-masing, itu akan memakan waktu beberapa ratus ribu tahun.

Samar-samar saya ingat bahwa beberapa pekerjaan telah dilakukan pada kriptanalisis TLCG melalui pengurangan basis kisi, jadi saya menggali artikel aslinya. Jadi itu! Itu hanya perlu untuk menentukan kisi-kisi dengan vektor basis yang diberikan oleh ³² dan tingkat konstan dari TLCG, dan kemudian membuat pengurangan basis kisi. Pada basis dikurangi, saya bisa mengembalikan keadaan asli dari byte tinggi dengan hanya mengalikan matriks.

Setidaknya itulah idenya. Butuh lima byte untuk mendapatkan satu-satunya hasil yang benar, dan pada waktu itu saya hanya memiliki empat serangan. Proses yang dijelaskan dalam artikel ini jarang memberikan jawaban yang benar. Namun, saya tahu bahwa jawabannya harus dekat dengan yang benar, sehingga saya bisa membahas semua nilai yang mungkin dari key1 dan memeriksa perbedaan antara jawaban yang nyata dan yang benar. Perbedaannya selalu menjadi salah satu dari 36 vektor! Dengan pengoptimalan ini, saya dapat mengurangi pencarian menjadi hanya 36 opsi, bukan empat miliar. Kami masih dalam bisnis.

Selanjutnya, kami dihadapkan dengan masalah mentransfer data antara mesin dengan GPU. Mitra bisnis saya, Nash Foster, terlibat dalam implementasi GPU. Dia menasihati saya seberapa cepat berbagai operasi dilakukan, dan menulis sebagian besar struktur pendukung untuk aplikasi dengan kode saya untuk cracking kripto. Bagaimana cara mendapatkan petabyte kunci kandidat ini untuk pengujian GPU? Mereka akan menganggur hampir sepanjang waktu, melemparkan inti mereka untuk mengantisipasi pekerjaan. Terpikir oleh saya bahwa pada setiap tahap serangan saya banyak bit diperiksa, dan kemudian hanya satu dari sekitar 65 ribu kandidat yang diselamatkan. Jika saya bisa menemukan cara untuk outputbit-bit ini didasarkan pada informasi yang tersedia, dan tidak hanya memaksa mereka, saya akan menghemat banyak pekerjaan dan, yang lebih penting, banyak lalu lintas jaringan. Masalahnya di sini adalah algoritma yang terlalu rumit, mewakili campuran bidang terbatas dengan cincin bilangan bulat, tetapi mereka tidak cocok satu sama lain.

Saya memikirkan serangan cryptanalytic lain yang saya tahu. Salah satunya adalah serangan "bertemu di tengah". Dia tampak kandidat yang menjanjikan. Serangan diterapkan ke blok cipher ketika ia menggunakan satu bagian dari bahan utama untuk melakukan bagian pertama dari enkripsi, dan bagian lainnya untuk bagian kedua. Ini diterapkan pada cipher zip, tetapi bahan kuncinya jauh melebihi jumlah bit di tengah. Kemudian terpikir oleh saya, bagaimana jika kita menggunakan linearitas CRC32: jika kita melakukan operasi XOR pada dua output CRC32 terakhir, maka hasilnya akan terlepas dari key2! Alih-alih menghitung negara perantara dari cipher dan menyimpannya dalam sebuah tabel, saya akan menghitung XOR dari dua negara perantara dan menyimpannya.

Saya menulis pertemuan diferensial "pertemuan di tengah" dan meluncurkannya di laptop saya. Panggung, yang dulunya memakan waktu beberapa jam, sekarang selesai hanya dalam beberapa detik. Tahap selanjutnya, yang bisa memakan waktu seminggu di farm GPU, berakhir dalam beberapa jam pada satu CPU yang kuat. Saya tidak bisa mengoptimalkan serangan tahap ketiga cukup untuk mempengaruhi kecepatan keseluruhan, tetapi tidak perlu untuk memindahkan data sepenuhnya: kami hanya menghitung kandidat untuk setiap GPU di komputer dengan kartu-kartu ini. Nash menulis kode GPU yang bekerja dengan kecepatan luar biasa.

Serangan itu berlangsung sepuluh hari dan berakhir dengan kegagalan.

Hati saya hancur. Apakah kita kehilangan salah satu kunci yang mungkin? Kami kembali dan melihat pengidentifikasi proses maksimum pada laptopnya dan menemukan bahwa itu beberapa bit lebih dari yang kami harapkan, dan karena itu ada sedikit lebih banyak sumber benih yang mungkin untuk rand. Saya juga memeriksa ulang semua kode kami. Mungkin kita melewatkan sesuatu? Mungkin versi pada CPU bekerja entah bagaimana berbeda dari pada GPU? Akhirnya, saya menemukan bahwa versi pada GPU tidak dapat menemukan kunci yang benar ketika berada di urutan kedua dalam daftar kandidat, tetapi hanya yang pertama. Mengaduk-aduk kode, kami menemukan bahwa kami bingung indeks blok dengan indeks aliran ketika menghitung offset dalam struktur data.

Kami memperbaiki kesalahan, menjalankan kembali kode dan menemukan kunci yang benar dalam sehari. Klien kami sangat puas dan memberi kami bonus besar karena menemukan kunci begitu cepat dan menghemat begitu banyak uang di luar perkiraan awal kami.

Sekarang saya sedang mencari pekerjaan. Jika Anda memiliki masalah yang menarik dengan analisis teknis atau optimasi, beri tahu saya.

---