Alat pengembang · SHA kalkulator hash
Penjelasan Merkle–Damgård: Konstruksi di Balik SHA-1 dan SHA-2
· Latar belakang
sha-256 kriptografi browser-apis
Fungsi kompresi ukuran tetap tidak dapat melakukan hashing pada input sewenang-wenangnya sendiri. Merkle–Damgård merantainya blok demi blok; posting ini menjelaskan konstruksi, ide pembuktiannya dan kelemahan yang dibawanya.
Masukan sewenang-wenang, keluaran tetap — masalah yang harus diselesaikan terlebih dahulu oleh setiap fungsi hash
Fungsi hash harus memetakan masukan sembarang ke keluaran tetap. Pesan berukuran tiga byte dan pesan berukuran tiga megabita harus menghasilkan keluaran tepat 256 bits untuk SHA-256. Hashnya harus deterministik, sehingga masukan yang sama selalu menghasilkan keluaran yang sama. Outputnya harus terlihat acak; mengubah satu bit masukan akan mengubah kira-kira setengah bit keluaran.
Pada pandangan pertama, ini adalah persyaratan yang kontradiktif, karena algoritma cepat tunggal tidak dapat menangani pesan dengan panjang sewenang-wenang dan menghasilkan keluaran dengan lebar tetap yang seragam. Konstruksi Merkle–Damgård menyelesaikan masalah ini dengan menggunakan fungsi kompresi ukuran tetap berulang kali, memasukkan output dari setiap aplikasi ke input aplikasi berikutnya. Konstruksi ini digunakan oleh SHA-1 dan seluruh SHA-2 (SHA-256, SHA-384 dan SHA-512).
Fungsi kompresi — mixer berukuran tetap yang mengambil status dan blok serta mengembalikan status baru
Fungsi kompresi adalah primitif kriptografi inti yang mendukung hash Merkle–Damgård. Dibutuhkan status berukuran tetap, biasanya 256 bits untuk SHA-256 atau 512 bits untuk SHA-512, dan blok masukan berukuran tetap, biasanya 512 bits untuk SHA-256 atau 1024 bits untuk SHA-512. Fungsi kompresi menggabungkannya menggunakan operasi bitwise, rotasi, dan pencarian tabel, menghasilkan status baru dengan ukuran yang sama. Fungsi ini harus tahan benturan: sulit menemukan dua pasangan (status, blok) berbeda yang menghasilkan keluaran yang sama.
Fungsi kompresi itu sendiri bukanlah fungsi hash yang lengkap—fungsi ini tidak menangani panjang masukan yang berubah-ubah, dan bahkan tidak menangani masukan pertama, yang tidak memiliki status sebelumnya. Sebaliknya, itu adalah blok bangunan dimana konstruksi yang lebih besar dibangun. Fungsi kompresi adalah satu-satunya operasi kriptografi yang berjalan berulang kali; yang lainnya adalah pembukuan yang menghubungkan fungsi ini ke hash penuh.
Chaining dan vektor inisialisasi — bagaimana blok saling mengumpan dari keadaan awal yang tetap
Vektor inisialisasi adalah keadaan awal yang tetap, dipilih dengan hati-hati untuk menghindari kesimetrian atau kelemahan. Untuk SHA-256, IV adalah delapan kata 32-bit yang berasal dari bagian pecahan akar kuadrat dari delapan bilangan prima pertama. Nilai-nilai ini bersifat arbitrer namun deterministik, sehingga setiap implementasi menghasilkan hasil yang sama. Blok pesan pertama dicampur dengan IV menggunakan fungsi kompresi, menghasilkan keadaan baru. Blok pesan kedua dicampur dengan keadaan tersebut, menghasilkan keadaan baru lainnya, dan seterusnya melalui setiap blok pesan.
Jaringan ini adalah bagian yang krusial: output dari satu blok bergantung pada semua blok sebelumnya, jadi mengubah bit apa pun dari blok sebelumnya akan mengubah semua blok berikutnya. Pada saat blok terakhir diproses, status berisi informasi tentang setiap bit masukan. Padding adalah trik yang membuat konstruksi ini terdengar. Sebuah pesan tidak selalu terbagi rata menjadi beberapa blok. Konstruksi Merkle–Damgård menggunakan penguatan MD: menambahkan satu bit ke pesan, lalu menambahkan angka nol hingga tersisa hampir satu blok penuh, lalu menambahkan panjang pesan asli.
Padding dengan panjang pesan — mengapa penguatan MD adalah hal yang membuat konstruksi terdengar baik
Argumen keamanan Merkle–Damgård mengatakan bahwa jika fungsi kompresi tahan benturan, maka keseluruhan hash juga tahan benturan. Buktinya adalah pengurangan: jika Anda dapat menemukan tabrakan di hash, Anda dapat mengekstrak tabrakan pada fungsi kompresi, yang bertentangan dengan asumsi bahwa fungsi kompresi sulit untuk bertabrakan. Intuisinya adalah setiap tumbukan dalam hash pada akhirnya akan menghasilkan tumbukan pada salah satu pemanggilan fungsi kompresi, karena keadaan diteruskan sepenuhnya.
Kelemahan di Merkle – Damgård ditemukan seiring berjalannya waktu, meskipun konstruksi dasarnya sudah baik. Perpanjangan panjangnya salah satunya: penyerang yang melihat intisari suatu pesan dapat memperluas pesan tersebut dan menghitung intisari yang valid untuk pesan yang lebih panjang tanpa mengetahui apa pun tentang masukannya. Serangan preimage kedua adalah hal lain: jika ada pesan, menemukan pesan berbeda dengan hash yang sama lebih mudah daripada yang seharusnya untuk beberapa jenis pesan. Kelemahan ini memotivasi desain SHA-3, yang menggunakan pendekatan berbeda yang disebut konstruksi spons.
Padding pengkodean panjang memisahkan pesan-pesan yang diisi; bukti keamanan penuh berada di luar bukti penyimpanan
Fungsi kompresi untuk SHA-256 mengambil status 256-bit (delapan kata 32-bit) dan blok 512-bit. Operasi ini menggunakan putaran 64, yang masing-masing mencampurkan status dengan konstanta dan kata dari blok. Pencampurannya menggunakan operasi bitwise: XOR, AND, NOT. Ia menggunakan rotasi dan pergeseran yang menggerakkan bit tanpa mengubah bit mana yang disetel. Ia menggunakan pencarian tabel yang menyediakan pencampuran non-linier yang tidak dapat dicapai oleh XOR saja.
SHA-512 menggunakan konstruksi yang sama dengan SHA-256 tetapi dengan operasi 64-bit, bukan operasi 32-bit. Statusnya adalah 512 bits (delapan 64-bit kata), dan ukuran bloknya adalah 1024 bits. Fungsi kompresi memiliki putaran 80, bukan 64, dan konstanta serta pencarian tabelnya berbeda. Untuk SHA-384, status dan fungsi kompresi sama dengan SHA-512, tetapi hanya 384 bits pertama dari status akhir yang dihasilkan. 128 bits terakhir dibuang. Pemotongan inilah yang menyebabkan SHA-384 tahan terhadap perpanjangan panjang.
Perpanjangan panjang adalah batas konstruksi yang diverifikasi; klaim motivasi multitabrakan dan SHA-3 dihilangkan
Keamanan hash Merkle–Damgård bergantung pada beberapa properti yang dimiliki. Fungsi kompresi harus tahan benturan, jadi menyerangnya secara langsung tidak mungkin dilakukan. Skema padding harus memastikan bahwa pesan yang berbeda menghasilkan bentuk padding yang berbeda, sehingga setiap tumbukan dalam hash harus melibatkan tumbukan fungsi kompresi. Ukuran blok dan ukuran negara harus cukup besar sehingga kekerasan tidak dapat dilakukan. Status yang lebih luas memperbesar ruang pencarian umum, namun artikel ini tidak mencantumkan jumlah operasi atau tanggal kelayakan tanpa derivasi sebaris dan sumber yang ditinjau.
Jika penyerang menemukan kelemahan dalam fungsi kompresi, atau jika komputer kuantum menjadi praktis dan dapat mencari ruang tidak terstruktur dalam waktu sqrt(2^n) dan bukan dalam waktu 2^n, maka margin keamanan akan terkikis. Kelemahan yang memotivasi SHA-3 bukanlah putusnya fungsi kompresi, namun masalah perpanjangan panjang dan kerentanan struktural lainnya. Konstruksi spons menghindari hal ini dengan tidak pernah mempublikasikan keadaan internalnya secara penuh.
Apa yang tidak tercakup di sini — fungsi putaran spesifik SHA-256, dibahas dalam pos terpisah
Bagaimana konstruksi Merkle–Damgård menangani setiap ukuran masukan adalah konsekuensi praktis dari desainnya. Pisahkan pesan menjadi blok 512-bit, masukkan blok terakhir, proses setiap blok melalui fungsi kompresi secara berurutan, dan keluarkan status akhir. Untuk input satu byte, padding menghasilkan blok 512-bit (satu byte pesan, satu bit padding, 447 bits nol, dan 64 bits untuk panjangnya). Jumlah kompresi adalah jumlah blok 512-bit, yang sebanding dengan panjang pesan.
Setiap intisari yang dihasilkan kalkulator hash ToolAcre SHA berasal dari konstruksi ini. Intisari 64-karakter SHA-256 adalah status 256-bit terakhir yang dicetak dalam heksadesimal. Intisari 128 karakter SHA-512 adalah status 512-bit terakhir yang dicetak dalam heksadesimal. Intisari 96 karakter SHA-384 adalah 384 bits pertama dari status 512-bit terakhir. Padding di belakang layar memastikan bahwa setiap pesan yang mungkin dihasilkan menghasilkan jumlah blok yang tepat dan lebar intisari yang tepat. Ini adalah konstruksi standar Merkle – Damgård yang berjalan di browser.
Kesimpulan: kerangka yang sama di balik empat algoritme — setiap intisari yang dihasilkan kalkulator hash ToolAcre SHA berasal dari konstruksi ini
Memahami konstruksinya berguna untuk mengetahui mengapa intisari selalu memiliki lebar yang sama dan mengapa mengubah satu bit masukan akan mengubah keseluruhan intisari. Properti rantai berarti bahwa setiap bit masukan mempengaruhi setiap bit keluaran melalui serangkaian operasi pencampuran. Perubahan satu bit di awal pesan akan disebarkan melalui semua kompresi berikutnya, sehingga intisari akhirnya benar-benar berbeda. Properti ini disebut efek longsoran dan merupakan tanda dari fungsi hash suara.
Konstruksi Merkle–Damgård telah digunakan selama beberapa dekade dan menjadi dasar dari fungsi hash yang paling banyak digunakan. SHA-1 dan SHA-2 dibangun berdasarkan konstruksi ini, dan banyak sistem yang diterapkan mengandalkan keluarannya. Konstruksinya sudah mapan dan bukan bersifat eksperimental, namun sejarah tersebut tidak membuat setiap penggunaan menjadi aman; perpanjangan panjang adalah salah satu batas yang didokumentasikan. Memahami konstruksi ini membantu pengembang memahami mengapa properti keamanan tertentu berlaku dan mengapa vektor serangan tertentu ada.