Dapatkah dua string berbeda menghasilkan kode hash MD5 yang sama?

Untuk setiap aset biner kami, kami menghasilkan hash MD5. Ini digunakan untuk memeriksa apakah aset biner tertentu sudah ada dalam aplikasi kita. Tetapi mungkinkah dua aset biner yang berbeda menghasilkan hash MD5 yang sama. Jadi, apakah mungkin dua string berbeda menghasilkan hash MD5 yang sama?

Untuk sekumpulan bahkan miliaran aset, kemungkinan tabrakan acak sangat kecil - tidak ada yang perlu Anda khawatirkan. Mempertimbangkan paradoks ulang tahun , mengingat satu set aset 2 ^ 64 (atau 18.446.744.073.709.551.616), probabilitas tabrakan MD5 tunggal dalam set ini adalah 50%. Pada skala ini, Anda mungkin mengalahkan Google dalam hal kapasitas penyimpanan.

Namun, karena fungsi hash MD5 telah rusak (rentan terhadap serangan tabrakan ), setiap penyerang yang ditentukan dapat menghasilkan 2 aset yang bertabrakan dalam hitungan detik dari daya CPU. Jadi jika Anda ingin menggunakan MD5, pastikan penyerang seperti itu tidak membahayakan keamanan aplikasi Anda!

Selain itu, pertimbangkan konsekuensi jika penyerang dapat memalsukan tabrakan ke aset yang ada di database Anda. Meskipun tidak ada serangan yang diketahui ( preimage ) terhadap MD5 (per 2011), hal itu bisa menjadi mungkin dengan memperluas penelitian saat ini tentang serangan tabrakan.

Jika ini ternyata menjadi masalah, saya sarankan untuk melihat rangkaian fungsi hash SHA-2 (SHA-256, SHA-384 dan SHA-512). Kelemahannya adalah sedikit lebih lambat dan memiliki keluaran hash yang lebih lama.

MD5 adalah fungsi hash - jadi ya, dua string berbeda benar-benar dapat menghasilkan kode MD5 yang bertabrakan.

Secara khusus, perhatikan bahwa kode MD5 memiliki panjang tetap sehingga kemungkinan jumlah kode MD5 terbatas. Jumlah string (dengan panjang berapa pun), bagaimanapun, pasti tidak terbatas sehingga secara logis harus ada tabrakan.

Ya, itu mungkin. Ini sebenarnya masalah ulang tahun . Namun kemungkinan dua string yang dipilih secara acak memiliki hash MD5 yang sama sangat rendah.

Lihat ini dan pertanyaan ini sebagai contoh.

Ya, tentu saja: Hash MD5 memiliki panjang yang terbatas, tetapi ada kemungkinan string karakter yang tidak terbatas yang dapat di-hash MD5.

Ya, ada kemungkinan dua string berbeda dapat menghasilkan kode hash MD5 yang sama.

Berikut adalah tes sederhana menggunakan pesan biner yang sangat mirip dalam string hex:

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc  -
008ee33a9d58b51cfeb425b0959121c9

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca  -
008ee33a9d58b51cfeb425b0959121c9

Mereka menghasilkan jumlah SHA-1 yang berbeda, tetapi nilai hash MD5 yang sama. Kedua, stringnya sangat mirip, jadi sulit untuk menemukan perbedaan di antara keduanya.

Perbedaannya dapat ditemukan dengan perintah berikut:

$ diff -u <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 | fold -w2) <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 | fold -w2)
--- /dev/fd/63  2016-02-05 12:55:04.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:55:04.000000000 +0000
@@ -33,7 +33,7 @@
 af
 bf
 a2
-00
+02
 a8
 28
 4b
@@ -53,7 +53,7 @@
 6d
 a0
 d1
-55
+d5
 5d
 83
 60

Contoh tumbukan di atas diambil dari Marc Stevens: Tabrakan satu blok untuk MD5 , 2012; dia menjelaskan metodenya, dengan kode sumber ( tautan alternatif ke kertas ).

Tes lain:

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82  -
cee9a457e790cf20d4bdaa6d69f01e41

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb  -
cee9a457e790cf20d4bdaa6d69f01e41

Jumlah SHA-1 berbeda, hash MD5 yang sama.

Selisihnya dalam satu byte:

$ diff -u <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2) <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2)
--- /dev/fd/63  2016-02-05 12:56:43.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:56:43.000000000 +0000
@@ -19,7 +19,7 @@
 03
 65
 9e
-70
+74
 4f
 85
 34
@@ -41,7 +41,7 @@
 a3
 f4
 15
-5c
+dc
 bb
 86
 07

Contoh di atas diadaptasi dari Tao Xie dan Dengguo Feng: Membangun Tabrakan MD5 Menggunakan Hanya Satu Blok Pesan , 2010.

Terkait:

• Apakah ada dua string yang diketahui memiliki nilai hash MD5 yang sama? di Crypto.SE

Ya, itu mungkin. Ini disebut tabrakan Hash .

Karena itu, algoritma seperti MD5 dirancang untuk meminimalkan kemungkinan tabrakan.

Entri Wikipedia di MD5 menjelaskan beberapa kerentanan di MD5, yang harus Anda waspadai.

Hanya agar lebih informatif. Dari sudut pandang matematika, fungsi Hash tidak bersifat injeksi .
Ini berarti bahwa tidak ada hubungan 1 ke 1 (tapi satu arah) antara himpunan awal dan hasil.

Bijection di wikipedia

EDIT: ada fungsi hash injeksi lengkap: ini disebut hashing sempurna .

Ya itu! Tabrakan akan menjadi kemungkinan (meskipun, risikonya sangat kecil). Jika tidak, Anda akan memiliki metode kompresi yang cukup efektif!

EDIT : Seperti yang dikatakan Konrad Rudolph: Satu set input yang berpotensi tidak terbatas yang diubah menjadi satu set output terbatas (32 karakter hex) akan menghasilkan tabrakan dalam jumlah yang tak terbatas.

Seperti yang dikatakan orang lain, ya, mungkin ada benturan antara dua input yang berbeda. Namun, dalam kasus penggunaan Anda, saya tidak melihat itu menjadi masalah. Saya sangat ragu Anda akan mengalami tabrakan - Saya telah menggunakan MD5 untuk mengambil sidik jari ratusan ribu file gambar dari sejumlah format gambar (JPG, bitmap, PNG, mentah) di pekerjaan sebelumnya dan saya tidak mengalami tabrakan .

Namun, jika Anda mencoba mengambil sidik jari beberapa jenis data, mungkin Anda dapat menggunakan dua algoritme hash - kemungkinan satu masukan menghasilkan keluaran yang sama dari dua algoritme berbeda hampir mustahil.

Saya menyadari ini sudah tua, tetapi saya pikir saya akan menyumbangkan solusi saya. Ada 2 ^ 128 kemungkinan kombinasi hash. Dan dengan demikian kemungkinan 2 ^ 64 dari paradoks ulang tahun. Meskipun solusi di bawah ini tidak akan menghilangkan kemungkinan tabrakan, itu pasti akan mengurangi risiko dalam jumlah yang sangat besar.

2^64 = 18,446,744,073,709,500,000 possible combinations

Apa yang telah saya lakukan adalah saya menggabungkan beberapa hash berdasarkan string input untuk mendapatkan string yang lebih panjang yang Anda anggap hash ...

Jadi pseudo-code saya untuk ini adalah:

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))

Itu adalah ketidakmungkinan praktis tabrakan. Tetapi jika Anda ingin menjadi super paranoid dan tidak dapat mewujudkannya, dan ruang penyimpanan tidak menjadi masalah (juga bukan siklus komputasi) ...

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string)) 
         & Hash(Reverse(SpellOutLengthWithWords(Length(string)))) 
         & Hash(Rotate13(string)) Hash(Hash(string)) & Hash(Reverse(Hash(string)))

Oke, bukan solusi terbersih, tapi ini sekarang membuat Anda lebih banyak bermain dengan seberapa jarang Anda akan mengalami tabrakan. Sampai-sampai saya mungkin menganggap tidak mungkin dalam semua pengertian realistis istilah tersebut.

Demi saya, saya pikir kemungkinan tabrakan cukup jarang sehingga saya akan menganggap ini bukan "pasti" tetapi sangat tidak mungkin terjadi sehingga sesuai dengan kebutuhan.

Sekarang kemungkinan kombinasi naik secara signifikan. Meskipun Anda bisa menghabiskan waktu lama untuk mengetahui berapa banyak kombinasi yang bisa Anda dapatkan, saya akan mengatakan secara teori itu membuat Anda SIGNIFIKAN lebih dari jumlah yang dikutip di atas

2^64 (or 18,446,744,073,709,551,616) 

Mungkin sekitar seratus digit lagi. Maks teoritis yang bisa diberikan ini kepada Anda

Jumlah kemungkinan string yang dihasilkan:

528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336

Saya pikir kita perlu berhati-hati dalam memilih algoritma hashing sesuai kebutuhan kita, karena tabrakan hash tidak jarang seperti yang saya harapkan. Saya baru-baru ini menemukan kasus tabrakan hash yang sangat sederhana dalam proyek saya. Saya menggunakan pembungkus Python xxhash untuk hashing. Tautan: https://github.com/ewencp/pyhashxx

s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266

Ini menyebabkan masalah caching yang sangat rumit dalam sistem, kemudian saya akhirnya menemukan bahwa itu adalah tabrakan hash.