Mengapa nilai hash MD5 tidak dapat dibalik?

Satu konsep yang selalu saya pertanyakan adalah penggunaan fungsi dan nilai hash kriptografi. Saya memahami bahwa fungsi-fungsi ini dapat menghasilkan nilai hash yang unik dan hampir tidak mungkin untuk dibalik, tetapi inilah yang selalu saya pikirkan:

Jika di server saya, di PHP saya menghasilkan:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Saat Anda menjalankan string yang sama melalui fungsi MD5, Anda mendapatkan hasil yang sama pada instalasi PHP Anda. Suatu proses digunakan untuk menghasilkan beberapa nilai, dari beberapa nilai awal.

Bukankah ini berarti ada cara untuk mendekonstruksi apa yang terjadi dan membalikkan nilai hash?

Ada apa dengan fungsi-fungsi ini yang membuat string yang dihasilkan tidak mungkin dilacak kembali?

Bahan masukan bisa panjang tak terbatas, di mana keluaran selalu 128 bit panjang. Ini berarti bahwa jumlah string masukan yang tak terbatas akan menghasilkan keluaran yang sama.

Jika Anda memilih nomor acak dan membaginya dengan 2 tetapi hanya menuliskan sisanya, Anda akan mendapatkan 0 atau 1 - genap atau ganjil. Apakah mungkin mengambil 0 atau 1 dan mendapatkan nomor aslinya?

Jika fungsi hash seperti MD5 dapat dibalik maka itu akan menjadi peristiwa penting dalam sejarah algoritma kompresi data! Sangat mudah untuk melihat bahwa jika MD5 dapat dibalik maka potongan data sewenang-wenang dengan ukuran sewenang-wenang dapat diwakili oleh hanya 128 bit tanpa kehilangan informasi. Dengan demikian Anda akan dapat merekonstruksi pesan asli dari nomor 128 bit terlepas dari ukuran pesan aslinya.

Bertentangan dengan apa yang ditekankan oleh jawaban yang paling disukai di sini, non-injeksi (yaitu ada beberapa string yang memiliki nilai yang sama) dari fungsi hash kriptografi yang disebabkan oleh perbedaan antara ukuran masukan yang besar (kemungkinan tidak terbatas) dan ukuran keluaran tetap tidak poin penting - sebenarnya, kami lebih suka fungsi hash di mana tabrakan itu jarang terjadi.

Pertimbangkan fungsi ini (dalam notasi PHP, sebagai pertanyaannya):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

Ini menambahkan beberapa spasi, jika string terlalu pendek, lalu mengambil 16 byte pertama dari string tersebut, lalu mengkodekannya sebagai heksadesimal. Ini memiliki ukuran keluaran yang sama dengan hash MD5 (32 karakter heksadesimal, atau 16 byte jika kita menghilangkan bagian bin2hex).

print simple_hash("stackoverflow.com");

Ini akan menghasilkan:

737461636b6f766572666c6f772e636f6d

Fungsi ini juga memiliki properti non-injeksi yang sama seperti yang disorot oleh jawaban Cody untuk MD5: Kita dapat mengirimkan string dengan ukuran berapa pun (asalkan sesuai dengan komputer kita), dan hanya akan menghasilkan 32 digit hex. Tentu saja tidak bisa injeksi.

Tetapi dalam kasus ini, sangat mudah untuk menemukan string yang memetakan ke hash yang sama (cukup terapkan hex2binpada hash Anda, dan Anda memilikinya). Jika string asli Anda memiliki panjang 16 (seperti contoh kami), Anda bahkan akan mendapatkan string asli ini. Hal semacam ini seharusnya tidak mungkin dilakukan untuk MD5, bahkan jika Anda mengetahui panjang masukan cukup pendek (selain dengan mencoba semua masukan yang mungkin sampai kami menemukan salah satu yang cocok, misalnya serangan brute-force).

Asumsi penting untuk fungsi hash kriptografi adalah:

• Sulit untuk menemukan string apa pun yang menghasilkan hash tertentu (resistansi preimage)
• Sulit untuk menemukan string berbeda yang menghasilkan hash yang sama dengan string yang diberikan (resistansi preimage kedua)
• sulit untuk menemukan pasangan string dengan hash yang sama (ketahanan benturan)

Jelas simple_hashfungsi saya memenuhi tidak satu pun dari kondisi ini. (Sebenarnya, jika kita membatasi ruang input ke "string 16-byte", maka fungsi saya menjadi injektif, dan dengan demikian bahkan dapat dibuktikan tahan gambar sebelumnya dan tahan benturan.)

Sekarang ada serangan tabrakan terhadap MD5 (misalnya dimungkinkan untuk menghasilkan sepasang string, bahkan dengan awalan yang sama, yang memiliki hash yang sama, dengan cukup banyak pekerjaan, tetapi bukan tidak mungkin banyak pekerjaan), jadi Anda tidak boleh menggunakan MD5 untuk segala hal yang penting. Belum ada serangan preimage, tapi serangan akan menjadi lebih baik.

Untuk menjawab pertanyaan sebenarnya:

Ada apa dengan fungsi-fungsi ini yang membuat string yang dihasilkan tidak mungkin dilacak kembali?

Apa yang MD5 (dan fungsi hash lainnya dibangun di atas konstruksi Merkle-Damgard) secara efektif lakukan adalah menerapkan algoritma enkripsi dengan pesan sebagai kuncinya dan beberapa nilai tetap sebagai "teks biasa", menggunakan ciphertext yang dihasilkan sebagai hash. (Sebelumnya, input diisi dan dipisahkan dalam blok, masing-masing blok ini digunakan untuk mengenkripsi output dari blok sebelumnya, XOR dengan inputnya untuk mencegah penghitungan terbalik.)

Algoritme enkripsi modern (termasuk yang digunakan dalam fungsi hash) dibuat sedemikian rupa sehingga sulit untuk memulihkan kunci, bahkan diberikan plaintext dan ciphertext (atau bahkan saat musuh memilih salah satunya). Mereka melakukan ini secara umum dengan melakukan banyak operasi bit-shuffle sedemikian rupa sehingga setiap bit keluaran ditentukan oleh setiap bit kunci (beberapa kali) dan juga setiap bit masukan. Dengan cara itu Anda hanya dapat dengan mudah menelusuri kembali apa yang terjadi di dalam jika Anda mengetahui kunci lengkap dan input atau output.

Untuk fungsi hash seperti MD5 dan serangan preimage (dengan string hash blok tunggal, untuk mempermudah), Anda hanya memiliki input dan output dari fungsi enkripsi Anda, tetapi bukan kuncinya (inilah yang Anda cari).

Jawaban Cody Brocious benar. Sebenarnya, Anda tidak dapat "membalikkan" fungsi hash karena banyak string yang dipetakan ke hash yang sama. Perhatikan, bagaimanapun, bahwa menemukan satu string yang dipetakan ke hash tertentu, atau menemukan dua string yang dipetakan ke hash yang sama (yaitu tabrakan ), akan menjadi terobosan besar bagi seorang cryptanalyst. Kesulitan besar dari kedua masalah ini adalah alasan mengapa fungsi hash yang baik berguna dalam kriptografi.

MD5 tidak membuat nilai hash unik; tujuan MD5 adalah dengan cepat menghasilkan nilai yang berubah secara signifikan berdasarkan perubahan kecil pada sumbernya.

Misalnya,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Jelas itu bukan enkripsi MD5 yang sebenarnya)

Sebagian besar hash (jika tidak semua) juga tidak unik; sebaliknya, mereka cukup unik , jadi tabrakan sangat tidak mungkin, tetapi masih mungkin.

Cara yang baik untuk memikirkan algoritma hash adalah dengan memikirkan mengubah ukuran gambar di Photoshop ... katakanlah Anda memiliki gambar yang berukuran 5000x5000 piksel dan kemudian Anda mengubah ukurannya menjadi hanya 32x32. Apa yang Anda miliki masih merupakan representasi dari gambar asli tetapi jauh lebih kecil dan secara efektif telah "membuang" bagian tertentu dari data gambar agar sesuai dengan ukuran yang lebih kecil. Jadi jika Anda mengubah ukuran gambar 32x32 itu kembali menjadi 5000x5000, yang Anda dapatkan hanyalah kekacauan yang kabur. Namun, karena gambar 32x32 tidak terlalu besar, secara teoritis dapat dibayangkan bahwa gambar lain dapat diperkecil untuk menghasilkan piksel yang sama persis!

Itu hanya analogi tetapi membantu memahami apa yang dilakukan hash.

Tabrakan hash jauh lebih mungkin daripada yang Anda kira. Lihatlah paradoks ulang tahun untuk mendapatkan pemahaman yang lebih baik tentang mengapa demikian.

Karena jumlah file masukan yang mungkin lebih besar dari jumlah keluaran 128-bit, tidak mungkin untuk menetapkan hash MD5 secara unik untuk setiap kemungkinan.

Fungsi hash kriptografi digunakan untuk memeriksa integritas data atau tanda tangan digital (hash sedang ditandatangani untuk efisiensi). Karena itu, mengubah dokumen asli berarti hash asli tidak cocok dengan dokumen yang diubah.

Kriteria ini terkadang digunakan:

1. Preimage resistance: untuk fungsi hash yang diberikan dan hash yang diberikan, akan sulit untuk menemukan input yang memiliki hash yang diberikan untuk fungsi tersebut.
2. Resistensi preimage kedua: untuk fungsi dan input hash yang diberikan, akan sulit untuk menemukan input kedua yang berbeda dengan hash yang sama.
3. Resistensi benturan: untuk fungsi yang diberikan, akan sulit untuk menemukan dua input berbeda dengan hash yang sama.

Kriteria ini dipilih untuk menyulitkan menemukan dokumen yang cocok dengan hash yang diberikan, jika tidak maka akan mungkin untuk memalsukan dokumen dengan mengganti aslinya dengan yang cocok dengan hash. (Sekalipun penggantinya omong kosong, penggantian yang asli saja dapat menyebabkan gangguan.)

Angka 3 menyiratkan angka 2.

Khususnya untuk MD5, telah terbukti cacatnya: Cara memecah MD5 dan fungsi hash lainnya .

Tapi di sinilah tabel pelangi ikut bermain. Pada dasarnya ini hanyalah sejumlah besar nilai yang di-hash secara terpisah dan kemudian hasilnya disimpan ke disk. Kemudian bit pembalikannya adalah "hanya" untuk melakukan pencarian di tabel yang sangat besar.

Jelas ini hanya layak untuk subset dari semua nilai masukan yang mungkin tetapi jika Anda mengetahui batas-batas nilai masukan, mungkin untuk menghitungnya.

Ilmuwan Cina telah menemukan cara yang disebut "tabrakan awalan-terpilih" untuk membuat konflik antara dua string berbeda.

Berikut ini contohnya: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
Kode sumber: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0. 5_source.zip

Cara terbaik untuk memahami arti dari semua jawaban yang paling banyak dipilih adalah dengan mencoba mengembalikan algoritme MD5. Saya ingat saya mencoba mengembalikan algoritme MD5crypt beberapa tahun yang lalu, bukan untuk memulihkan pesan asli karena jelas tidak mungkin, tetapi hanya untuk menghasilkan pesan yang akan menghasilkan hash yang sama dengan hash asli. Ini, setidaknya secara teoritis, akan memberi saya cara untuk masuk ke perangkat Linux yang menyimpan pengguna: kata sandi di file / etc / passwd menggunakan pesan (kata sandi) yang dihasilkan daripada menggunakan yang asli. Karena kedua pesan akan memiliki hasil hash yang sama, sistem akan mengenali kata sandi saya (yang dihasilkan dari hash asli) sebagai valid. Itu tidak berhasil sama sekali. Setelah beberapa minggu, jika saya ingat dengan benar, penggunaan garamdi pesan awal membunuhku. Saya harus menghasilkan tidak hanya pesan awal yang valid, tetapi pesan awal yang valid, yang tidak pernah dapat saya lakukan. Tapi pengetahuan yang saya dapat dari percobaan ini bagus.

Seperti yang telah dikatakan sebagian besar, MD5 dirancang untuk aliran data dengan panjang variabel yang akan di-hash ke potongan data yang panjangnya tetap, sehingga satu hash digunakan bersama oleh banyak aliran data masukan.

Namun jika Anda memang perlu mencari data asli dari checksum, misalnya jika Anda memiliki hash kata sandi dan perlu mengetahui kata sandi asli, seringkali lebih cepat hanya menggunakan google (atau pencari apa pun yang Anda inginkan) hash untuk jawabannya daripada memaksa itu. Saya telah berhasil menemukan beberapa kata sandi menggunakan metode ini.

menurut definisi fungsi Hash (Hash kriptografik): tidak boleh dibalik; tidak boleh bertabrakan (paling tidak mungkin).

regd pertanyaan Anda: ini adalah salah satu cara hash. input (terlepas dari panjangnya) akan menghasilkan output ukuran tetap. (itu akan diisi berdasarkan algo (batas 512 bit untuk MD5)). Informasi dikompresi (hilang) dan secara praktis tidak mungkin dihasilkan dari transformasi terbalik.

info tambahan tentang MD5: rentan terhadap tabrakan. membaca artikel ini baru-baru ini, http://www.win.tue.nl/hashclash/Nostradamus/

membuka kode sumber untuk implementasi hash crypto (MD5 dan SHA) dapat ditemukan di kode Mozilla. (perpustakaan freebl).

Sekarang hash MD5 hari atau hash lainnya dalam hal ini dihitung sebelumnya untuk semua kemungkinan string dan disimpan untuk memudahkan akses. Meskipun dalam teori MD5 tidak dapat dibalik tetapi menggunakan database seperti itu, Anda dapat mengetahui teks mana yang menghasilkan nilai hash tertentu.

Misalnya coba kode hash berikut di http://gdataonline.com/seekhash.php untuk mengetahui teks apa yang saya gunakan untuk menghitung hash

aea23489ce3aa9b6406ebb28e0cda430

f (x) = 1 tidak dapat diubah. Fungsi hash tidak dapat diubah.

Ini sebenarnya diperlukan bagi mereka untuk memenuhi fungsi mereka dalam menentukan apakah seseorang memiliki salinan data hash yang tidak rusak. Hal ini membawa kerentanan terhadap serangan brute force, yang cukup kuat akhir-akhir ini, terutama terhadap MD5.

Ada juga kebingungan di sini dan di tempat lain di antara orang-orang yang memiliki pengetahuan matematika tetapi sedikit pengetahuan yang memecahkan sandi. Beberapa cipher hanya melakukan XOR data dengan keystream, sehingga Anda dapat mengatakan bahwa ciphertext sesuai dengan semua plaintext sepanjang itu karena Anda dapat menggunakan keystream apa pun.

Namun, ini mengabaikan bahwa teks biasa yang masuk akal yang dihasilkan dari benih passwordjauh lebih mungkin daripada yang lain yang dihasilkan oleh benih Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6osejauh siapa pun yang mengklaim bahwa yang kedua adalah kemungkinan akan ditertawakan.

Dengan cara yang sama, jika Anda mencoba untuk memutuskan antara dua kata sandi potensial passworddan Wsg5Nm^bkI4EgxUO, itu tidak sesulit yang Anda yakini oleh beberapa ahli matematika.

Saya menyukai semua argumen yang berbeda. Jelas nilai sebenarnya dari nilai hash hanyalah untuk menyediakan placeholder yang tidak dapat dibaca manusia untuk string seperti kata sandi. Ini tidak memiliki manfaat keamanan khusus yang ditingkatkan. Dengan asumsi penyerang mendapatkan akses ke tabel dengan kata sandi berciri, dia dapat:

• Hash kata sandi pilihannya sendiri dan tempatkan hasilnya di dalam tabel kata sandi jika dia memiliki hak menulis / mengedit ke tabel.
• Hasilkan nilai hash dari kata sandi umum dan uji keberadaan nilai hash serupa di tabel kata sandi.

Dalam hal ini kata sandi yang lemah tidak dapat dilindungi hanya dengan fakta bahwa kata sandi itu di-hash.