Bagaimana cipher SHACAL-2 dihitung?

Jan 12 2021

Saya mencoba mempelajari tentang fungsionalitas yang mendasari fungsi hash yang berbeda (saat ini SHA) dan saya cukup macet bahkan setelah menonton video Stanford tentangnya.

Salah satu metode hashing adalah dengan menggunakan konstruksi Merkel-Damgård dengan fungsi David Meyers dan blok cipher SHACAL-2.

Sejauh yang saya mengerti, MD adalah pesan yang dibagi menjadi rantai blok 64-bit yang berisi nilai blok sebelumnya atau IV (vektor awal yang ditentukan oleh fungsi hash atau kunci garam khusus). Nilai blok atau IV bersama dengan nilai blok saat ini dan beberapa kunci x bit setelah melalui fungsi SHACAL-2 kemudian cipher baru.

Apakah ini benar dipahami? Jika ini: Apa yang terjadi di dalam fungsi SHACAL? Apa itu matematika?

Saya menemukan ini tetapi tidak benar-benar menjawab pertanyaan saya: SHACAL di SHA-256

Jawaban

2 kelalaka Jan 12 2021 at 18:13

Konstruksi MD menggunakan fungsi kompresi $C$ ($F$ dalam gambar) sehingga memiliki dua masukan.

$$h_i = C(h_{i-1},m_i)$$

dan yang pertama $h_{-1} = IV$ dan yang terakhir $H = h_{2^k-1}$ adalah nilai hash.

Fungsi kompresi dapat menggunakan block cipher, dimana pesan ke block cipher adalah nilai hash sebelumnya dan kuncinya adalah pesannya. $h_i = E_{m}(h_{i-1})$

Deskripsi pertama tentang penggunaan block cipher untuk fungsi kompresi ada dalam tesis Merkle di halaman 11 . Konstruksi ini benar-benar tidak aman karena block cipher yang ada dirantai secara langsung dan dapat dibuktikan bahwa memang demikian$\mathcal{O}(2^{n/2})$ resistensi preimage kedua, bukan $\mathcal{O}(2^{n})$.

Kami tidak ingin serangan kunci terkait seperti yang ada di beberapa block-cipher seperti AES dan DES. Ini tidak menimbulkan masalah untuk enkripsi karena kunci dipilih secara acak secara seragam, namun, kunci terkait dapat digunakan untuk menyerang fungsi hash. Ini dibahas secara ekstensif oleh Mannik dan Preenel

Kami menginginkan input yang besar karena serangan tabrakan pada fungsi kompresi [1] dan karena itu lebih banyak putaran untuk diproses. Jadi desainer membuat cipher blok baru untuk konstruksi MD daripada menggunakan yang sudah ada. Untuk SHA-1 disebut SHACAL dan untuk SHA-2 disebut SHACAL-2.

Nilai pembagian tergantung pada fungsi kompresi, MD5, SHA-1, dan SHA256 menggunakan blok pesan 512-bit, SHA512 menggunakan blok pesan 1024-bit. Pesan-pesan tersebut digabungkan menjadi beberapa ukuran blok dengan ukuran pesan dikodekan di bagian akhir.

Misalnya padding SHA-512 pada NIST FIPS 180-4

Misalkan panjang pesan, $M$, aku s $\ell$bit. Tambahkan bit 1ke akhir pesan, diikuti dengan$k$ bit nol, di mana $k$ adalah solusi terkecil dan non-negatif dari persamaan $$\ell + 1 + k \equiv 896 \bmod 1024$$ Kemudian tambahkan blok 128-bit yang sama dengan nomor tersebut $\ell$ diekspresikan menggunakan representasi biner

Formalisasikan untuk ukuran blok sewenang-wenang $b$ dan $d$-bit ukuran pesan yang disandikan (64 untuk SHA-1 dan SHA256, 128 untuk SHA512.

$$\ell + 1 + k \equiv b-d \bmod b$$

Jadi kriteria desainnya adalah memiliki block cipher dengan banyak putaran, SHACAL memiliki 80, SHA-256 memiliki 64, dan SHA512 memiliki 80 putaran sambil menjaga fungsi putaran tetap sederhana.

Dan block cipher digunakan sebagai Davies-Meyer untuk membuat fungsi kompresi satu arah.

Misalnya, matematika untuk SHA256 adalah

  • $\operatorname{Ch}(E,F,G) = (E \land F) \oplus (\neg E \land G)$
  • $\operatorname{Ma}(A,B,C) = (A \land B) \oplus (A \land C) \oplus (B \land C)$
  • $\Sigma_0(A) = (A\!\ggg\!2) \oplus (A\!\ggg\!13) \oplus (A\!\ggg\!22)$
  • $\Sigma_1(E) = (E\!\ggg\!6) \oplus (E\!\ggg\!11) \oplus (E\!\ggg\!25)$

Rotasi bitwise menggunakan konstanta berbeda untuk SHA-512. Nomor yang diberikan adalah untuk SHA-256.
Yang merah$\boxplus$ berarti $ c = a + b \mod 2^{32}$, yaitu penambahan modulo.

Seperti yang bisa kita lihat, operasi sederhana yang dapat ditangani CPU, fungsi putaran ringan, dengan struktur Feistel yang sedikit rusak dan tidak seimbang.

Dan kami belajar dari algoritma Enkripsi Kecil bahwa, bahkan putaran sederhana pun bisa aman setelah 32 putaran.