🧖🏿 🧖🏾 ☀️ Tentang kode GOST, Belalang, SBox-nya, dan benih yang hilang 🤾🏻 🚶 ☯️

Hai% nama pengguna%!

Kami baru saja kembali dari konferensi EuroCrypt 2019, di mana kami bertemu orang-orang yang sangat pintar dan pada saat yang sama mempelajari fakta-fakta baru yang sangat ofensif tentang GOST SBox.

Jadi, ini adalah pendekatan kedua untuk proyektil. Diperbaiki dan ditambah.

Kali ini tidak akan ada slide merah-biru yang tidak dapat dipahami, tetapi akan ada dokumen asli dari komite ISO dengan penjelasan dari penulis Grasshopper.

Dan bahkan tantangan di akhir!

Ayo pergi.

Program pendidikan pertama. Pada artikel sebelumnya tidak, kali ini saya benar.

Chaint Plaintext Attack (CPA) yang Dipilih

Kami mulai dengan model serangan dasar pada cipher blok.

Dalam model ini, penyerang tahu segalanya tentang cryptosystem kecuali kunci enkripsi. Dia dapat membuat plaintext apa saja, mendapatkan ciphertext yang sesuai dan tugasnya adalah menghitung kuncinya, karena ini adalah satu-satunya variabel.

Cipher blok dalam situasi ini dapat dianggap sebagai substitusi pseudo-acak. Fungsi yang cocok dengan blok plaintext ke blok ciphertext sedemikian rupa sehingga tidak mungkin untuk menentukan hubungan di antara mereka.

Block cipher yang ideal dapat dibayangkan sebagai sebuah meja besar, di mana secara horizontal akan ada semua kunci yang mungkin dari 000 ... 000 hingga 111 ... 111, secara vertikal - semua teks terbuka yang mungkin juga dari 000 ... 000 hingga 111 ... 111 , dan di tempat persimpangan mereka - ciphertext yang dibuat secara acak yang secara unik akan mengaitkan sepasang "key - plaintext". Untuk membuat tabel seperti itu dalam kehidupan nyata tidak mungkin karena ukurannya, sehingga ditiru dengan menggunakan berbagai algoritma blok enkripsi.

Serangan pada cipher blok dapat disebut berhasil jika kita dapat menentukan "keacakan" yang digunakan algoritma untuk memilih ciphertext yang sesuai dengan plaintext. Keacakan ini memungkinkan dalam kasus terburuk untuk menghitung kunci enkripsi.

(Non) linearitas

Proses enkripsi dalam cipher blok dapat diwakili oleh formula sederhana
C = M x K
di mana C adalah ciphertext, M adalah plaintext, K adalah kunci enkripsi, dan x adalah cipher blok.

Rumus ini secara visual mirip dengan rumus persamaan persamaan linear y = kx + b, grafiknya adalah garis lurus.

Setiap garis lurus dapat dikembalikan hanya dalam dua poin. Dan pada saat yang sama, kami benar-benar tidak ingin itu dalam dua pasang plaintext - ciphertext, Anda dapat mengembalikan kunci enkripsi. Untuk ini, lapisan khusus ditambahkan ke algoritma enkripsi yang bertanggung jawab untuk non- linearitas. Lapisan-lapisan ini dirancang untuk mencegah kemungkinan menghitung hubungan antara plaintext, ciphertext, dan kunci.

Kualitas mereka sangat penting untuk keamanan algoritma.

Apa itu SBox?

Ini adalah lapisan nonlinier yang sama. Sebuah fungsi yang, dalam kasus Grasshopper dan beberapa cipher lainnya, secara unik memetakan satu byte ke byte lain.

Sangat sering diatur oleh tabel korespondensi sederhana, misalnya ini:

Karena kalau tidak, itu tidak dapat dijelaskan. Sekilas.

Mengapa SBox penting?

Karena itu adalah satu - satunya fungsi non-linear di seluruh cipher. Tanpa itu, memecahkan cipher tidak akan mudah, tetapi sangat sederhana, menghadirkannya sebagai sistem persamaan linear. Karena itu, fungsi substitusi sangat diperhatikan. Bahkan ada latihan praktis untuk meretas AES dengan SBox linier.

Mengapa Anda tidak bisa membuat satu SBox yang aman sama sekali?

Masalahnya adalah bahwa kriptografi bukanlah ilmu pasti. Satu-satunya algoritma enkripsi yang terbukti kuat adalah pad sekali pakai . Semua yang lain adalah upaya malu-malu untuk masuk ke dalam rentang pengetahuan yang tersedia bagi kita, yang setnya tidak begitu bagus.
Kita tidak tahu pasti apakah RSA atau AES atau kurva eliptik tahan, tetapi kita tahu bahwa hal-hal ini dan itu pasti tidak mungkin . Semua di antaranya adalah kreativitas.

Oleh karena itu paranoia yang konstan tentang berbagai "konstanta ajaib" dan poin-poin lain yang dianggap aman oleh para penulis algoritma, tetapi tidak dapat membuktikannya .

Bagaimana cara membuat SBox?

Berbagai varian SBox adalah 256 !, yaitu sekitar 2 ¹⁶⁸⁴ . Pilihannya besar dan selama bertahun-tahun pembacaan sandi, metrik dan karakteristik telah dikembangkan yang seharusnya dimiliki SBox, tahan terhadap serangan yang dikenal saat ini. Tentu saja, pembuat tabel berpikir untuk tahun yang akan datang dan mencoba untuk membuat pengganti yang akan tahan bahkan terhadap serangan yang ditemukan dalam 5-10 tahun. Tapi ini lebih dari kategori sihir dan perdukunan.

Ada dua pendekatan yang berbeda secara mendasar untuk menciptakan SBox.

Yang pertama adalah pencarian acak. Pengembang membuat tabel acak, melihat karakteristik mereka dan menyaring yang tidak cocok. Ini berlanjut sampai pengembang puas dengan apa yang mereka temukan.

Di dunia yang beradab, ini terjadi, misalnya, sebagai berikut:

Beberapa nilai awal diambil, misalnya, kutipan dari buku atau beberapa digit pertama dari Pi
Berjalan melalui hash
Hasil hash digunakan sebagai data untuk membentuk SBox.
Jika SBox tidak cocok, ambil hash saat ini dan kembali ke langkah 2

Jadi siapa pun dapat mereproduksi proses ini dan memastikan bahwa setidaknya persyaratan minimum untuk pencarian pseudo-acak terpenuhi.

Apakah Anda tahu di mana benih dari algoritma simetris utama negara pergi? Hilang ! Saya pikir mereka tidak secara khusus memberi tahu mereka, rahasianya ada di sana atau sesuatu, tetapi rekan-rekan Rusia di EuroCrypt mengatakan bahwa selama pengembangan algoritma pada 2007, untuk beberapa alasan tidak ada yang berpikir bahwa akan perlu untuk membenarkan desain tabel pencarian, dan nilai-nilai dari mana itu keluar selamanya. hilang. Ceritanya indah, tapi jangan lupa bahwa algoritme itu dibuat bukan di sekolah saat istirahat, tetapi di dalam perut FSB.

Cara kedua adalah membuat SBox sendiri, dipandu oleh alat matematika yang tersedia. Itulah yang dilakukan penulis AES, dan mereka melakukannya dengan cukup baik. Jika kita membandingkan nonlinearitas SBox AES, SM4 (standar Cina) dan Belalang (menggunakan SBox yang sama dengan hash Stribog), maka hasilnya tidak akan mendukung yang terakhir

Non-linearitas AES (min, maks) = (112.0, 112.0)
Non-linearitas SM4 (min, maks) = (112.0, 112.0)
Streebog non-linearitas (min, maks) = (102.0, 110.0)

Kode perhitungan nonlinier menggunakan Transform Walsh dan tersedia di sini.

Documents

Saya mendapat dua dokumen dari ISO. Yang pertama, desainer Grasshopper menjelaskan bagaimana mereka menciptakan SBox, di lain, komite membahas argumen mereka.

dari dokumen pertama kami tertarik pada dua kutipan:

dan

Saya berharap topik dengan "Leo Perrin sendiri muncul dengan gagasan bahwa penulis mencari SBox secara acak" sekarang ditutup.

Dari penjelasan desainer berikut ini

Mereka benar-benar mencari SBox dengan cara semu-acak (diberikan kriteria keamanan)
Tidak ada struktur tersembunyi yang diduga diletakkan di dalamnya.

Dan di tempat ini mereka benar-benar kacau.

Apa itu struktur?

Struktur seperti yang diterapkan pada tabel pencarian adalah algoritma yang menjelaskan tabel ini.

Dokumen tersebut menyebutkan AES. Tetapi tabel pencarian untuk AES pada awalnya dibuat bukan dengan pencarian acak, tetapi dengan bantuan beberapa teknik matematika yang memungkinkan kita untuk menggambarkan lapisan nonlinear dengan beberapa rumus . Ini, kebetulan, adalah keunikan AES.

Sebaliknya, jika Anda mencari SBox secara acak, maka seharusnya tidak ada struktur seperti itu di dalamnya dan masalah dengan Grasshopper SBox adalah bahwa kata-kata perancang algoritma sangat berbeda dari fakta. Saya menulis tentang struktur belalang yang disebut TKLog dalam artikel sebelumnya , kali ini mari kita bicara tentang struktur secara umum.

Kompleksitas kolmogorov

Ini adalah hasil penelitian dari artikel terbaru Leo Perrin tentang Belalang.

Pertimbangan utama untuk artikel tentang struktur di Grasshopper SBox adalah bahwa "di hampir semua SBox Anda dapat menemukan beberapa struktur jika Anda mau." Dan "walaupun probabilitas menemukan struktur yang Leo temukan dapat diabaikan, jika ada SBox lain, maka akan ada yang lain, juga dengan probabilitas yang tidak signifikan."

Katakanlah begitu. Tapi Ternyata, adalah mungkin untuk mendapatkan "tingkat struktur" SBox tertentu, yang tidak tergantung pada kemungkinan jatuh ke dalam satu atau lain struktur.

Tapi itu tergantung pada ukuran algoritma yang diperlukan untuk menghasilkan SBox ini!

Ini disebut kompleksitas Kolmogorov.

Jika Anda membayangkan SBox sebagai string byte, maka dalam kasus string acak, seharusnya tidak ada algoritma yang menghasilkan string ini dan pada saat yang sama lebih kecil dari string ini.

Untuk belalang

Jadi, ukuran SBox adalah 256 byte. Berikut adalah versi yang dapat dibaca dari kode kepengarangan Leo Perrin, yang mengimplementasikan tabel Grasshopper. Pada input adalah sumber byte, pada output adalah byte yang sesuai dari Grasshopper SBox. Kondisi utama untuk algoritma semacam itu adalah larangan penggunaan bahasa atau struktur platform yang dengan curang mengurangi ukuran program. Misalnya, jika di suatu tempat di dalam pustaka standar ada konstanta yang mengandung setengah dari SBox, maka Anda tidak dapat menggunakannya.

Tantangan - tulis program yang lebih kecil dari SBox.

unsigned char p(unsigned char x){
    unsigned char
        s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
        k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};    
    if(x) {
        unsigned char l=1, a=2;
        while(a!=x) {
            a=(a<<1)^(a>>7)*29;
            l++;
        }
        if (l%17) return 252^k[l%17]^s[l/17];
        else return 252^k[l/17];
    }
    else return 252;
}

, SBox «» , , SBox. 416 , .

, :

p(x){
  unsigned char
      *t="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",
      a=2,l=0,b=17;
  while(x && (l++,a^x)) a=2*a^a/128*29;
  return l%b ? t[l%b]^t[b+l/b]^b : t[l/b]^188;
}

196 , 23% SBox. . , :

p(x){char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8";int l=256,b=17;while(--l*x^l)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

SBox :

int main() {
   for(int i = 0; i < 256; i++){
       if (i % 16 == 0){
           printf("\n");
       }
    printf("%d, ", (unsigned char)p(i));    
   }
}

, SBox .
153 . — ANSI, 7 , 8. 1071 ~134 . , .

, Cortex-M4 80 ( ).

, 64 .

, ?

, , .

, 4 Sbox, SBox , .

. , « » AES (60 , GolfScript), .

— . , — .

— SBox. , . , .

( ), , 4 , SBox. , — , . 4 , , , . , , , 11 , , . , side project ¯\_(ツ)_/¯.

ISO . . .

, , , SBox . . , , .

Curve25519 Daniel J. Bernstein Tanja Lange, ISO . , , , SBox. . .

, .

, . ISO, , EuroCrypt.

, ( SBox), RFC 7801, .

, SBox, (, ). , , , . V2 .

. , « , ».

, ? , AES - .

, , , , . .

Challenge!

SBox , , . , 256 . . . — , .

— 58 Stax. « » SBox.

.

Tentang kode GOST, Belalang, SBox-nya, dan benih yang hilang