Keanehan lain dalam algoritma GOST Grasshopper dan Stribog

Hai% nama pengguna%!

Algoritma kriptografi di Rusia tidak melalui kompetisi terbuka, mereka hanya mengecewakan kita. Dan cepat atau lambat itu akan kembali kepada kita. Artikel ini adalah tentang studi GOST kami selanjutnya.


Pada tahun 2016, para peneliti menunjukkan bahwa tabel permutasi dalam hashing dan algoritma enkripsi Rusia Kuznechik dan Stribog memiliki struktur yang jauh dari acak. Ini sudah terjadi setelah kesalahan sepele ditemukan di Stribog, mengurangi durabilitasnya dari 2 ⁵¹² menjadi ^2.266 .

Pada tanggal 29 Januari 2019, sebuah studi baru , Partitions in S-Box of Streebog dan Kuznyechik, diterbitkan, yang dengan jelas mengisyaratkan kemungkinan teoritis dari pintu belakang dalam algoritma ini.

Jadi, S-Box - atau tabel penggantian, adalah elemen kunci keamanan dalam banyak enkripsi simetris dan algoritma hashing. Contoh dari tabel seperti itu ditunjukkan pada gambar.



Secara umum, tabel ini memetakan satu urutan bit ke yang lain. Namun dengan prinsip apa selalu menjadi pertanyaan besar.

Instansi pemerintah sering terbatas pada penerbitan tanpa penjelasan rasional. Dalam kasus DES, NSA mengusulkan untuk mengubah S-Box sebelum algoritma menjadi standar. Hanya setelah bertahun-tahun barulah menjadi jelas bahwa perubahan ini benar-benar meningkatkan resistensi DES terhadap pembacaan sandi diferensial.

Dalam kasus GOST baru, tidak semuanya cerah. Para penulis menyatakan bahwa tabel substitusi dipilih secara acak. Berikut ini adalah slide dari presentasi algoritma, yang menunjukkan bahwa penulis memilih tabel secara acak. Sehingga tidak memiliki struktur eksplisit yang akan membantu menghasilkan cryptanalysis yang efektif. (Merah adalah apa yang mereka pilih)



Meja ini



Tapi pertama-tama, ternyata, itu tidak dihasilkan secara acak, tetapi dengan bantuan algoritma yang licik, yang diambil pada tahun 2015.



Kedua, penulis tidak meninggalkan upaya untuk mencari tahu alasan pendekatan ini terhadap desain S-Box dan menemukan hasil yang sangat menarik.

Ternyata algoritma yang membentuk tabel penggantian lebih dari satu. Kelompok peneliti yang berbeda menggambarkan algoritma yang sangat berbeda yang hampir tidak memiliki kesamaan, tetapi sampai pada tabel yang sama.

Hal ini mengarahkan penulis studi asli untuk mempelajari lebih dalam struktur algoritma ini dan menemukan elemen-elemen umum yang berhasil mereka peroleh.

Tklog

TKlog adalah konstruksi permutasi yang penulis kriptoanalisis dinamai kantor Rusia TK-26, tempat Grasshopper dan Stribog dibuat. Penjelasannya jauh di luar ruang lingkup artikel ini, mereka yang ingin dapat merujuk ke aslinya . Singkatnya, properti utamanya adalah penggunaan logaritma diskrit, seperti dalam kriptografi asimetris.

Yang penting adalah kenyataan bahwa kedua versi fungsi penggantian dari algoritma GOST adalah kasus khusus dari desain TKlog. Serta fungsi pengganti lain dari algoritma BelT Belarusia . Fungsinya berbeda, tetapi turun ke satu.



Fakta bahwa ada sangat sedikit opsi konversi TKlog yang berbeda menunjukkan penggunaan yang disengaja dari struktur non-acak ini dan bukan yang acak yang ditunjukkan kepada kami di slide.

Partisi menjadi kelas yang berdekatan

Properti utama konversi TKlog adalah ia berfungsi dengan apa yang disebut cosets. Dan membandingkan satu sama lain.

Masalahnya adalah bahwa kelas-kelas yang berdekatan ini adalah multiplikatif, seperti pada semua algoritma konvensional. Dan mereka aditif.

Jadi, satu-satunya kasus yang diketahui ketika kelas aditif yang berdekatan digunakan dalam fungsi mengganti cipher blok adalah pembuatan khusus dari pintu belakang . Informasi tentang ini ada di 2016.

Pintu belakang semacam itu disebut NOBUS, abbr. dari NObody But US, ini adalah kerentanan yang hanya dapat dieksploitasi oleh penulis algoritme itu sendiri.

Alih-alih sebuah kesimpulan

Para penulis cryptanalysis tidak menyajikan serangan baru pada algoritma GOST yang ada, tetapi mereka mengajukan pertanyaan yang adil tentang kesesuaian seluruh sirkus ini dengan tabel permutasi yang diduga acak.

NSA baru-baru ini mencoba untuk mendorong algoritma simetris yang ringan, Simon dan Speck, ke dalam standar. Dan fakta memiliki meja pengganti dengan desain, deskripsi yang tidak disediakan, sudah cukup untuk mengusir mereka dengan kain kencing dari mana-mana.

Kami tidak memiliki kesempatan seperti itu.

PS jangan lupa bahwa Stribog digunakan untuk menghasilkan parameter dari kurva elips GOST baru. Menggunakannya, konstanta mistis W hash.