Apakah aman untuk mengabaikan kemungkinan tabrakan SHA dalam praktek?

209

Katakanlah kita memiliki satu miliar gambar unik, masing-masing satu megabita. Kami menghitung hash SHA-256 untuk konten setiap file. Kemungkinan tabrakan tergantung pada:

jumlah file
~~ukuran file tunggal~~

Seberapa jauh kita bisa mengabaikan kemungkinan ini, dengan asumsi itu nol?

hash sha Hristo Hristov
sumber

Itu tergantung pada apa yang Anda gunakan untuk kunci hash. Jika itu semacam identifikasi file, maka sebuah tabrakan mungkin juga berarti file tersebut identik dan dengan demikian Anda perlu membandingkan file juga dalam kasus tabrakan. Saya akan mengatakan itu akan cukup aman untuk hanya membandingkan ukuran file.

mojuba

Ya, dalam hal ini, jika Anda membandingkan ukuran file, kemungkinan menurun secara drastis. Anda juga dapat menggunakan dua algoritma hashing dan menggabungkan hasilnya. Kemudian, kemungkinan tabrakan keduanya sekaligus menurun lebih banyak. Tapi, pertanyaannya adalah, berapa "cukup" aman? Mungkin kita membutuhkan formula dan angka.

Hristo Hristov

@Hristo Hristov: jika kita mengasumsikan bahwa kunci hash adalah angka acak semu (yang secara teoritis benar) maka satu miliar kunci 128-bit memberikan probabilitas tabrakan 2,9 * 10 ^ -30. Anda bahkan tidak dapat menyebutnya "sangat kecil", kurang dari itu;)

mojuba

@mojuba: lebih baik lagi, dia bertanya tentang hash 256-bit.

Michael Borgwardt

FWIW: sistem kontrol versi GIT mengidentifikasi file dengan SHA konten mereka.

snemarch

Jawaban:

385

Jawaban yang biasa berlaku sebagai berikut: berapakah probabilitas asteroid jahat menabrak Bumi dalam detik berikutnya, melenyapkan peradaban-seperti-kita-ketahui-itu, dan membunuh beberapa miliar orang? Dapat dikatakan bahwa setiap peristiwa sial dengan probabilitas lebih rendah dari itu sebenarnya tidak terlalu penting.

Jika kita memiliki fungsi hash "sempurna" dengan output ukuran n , dan kami memiliki p pesan ke hash (panjang pesan individu tidak penting), maka kemungkinan tabrakan adalah tentang p ² /2 ^{n + 1} (ini adalah perkiraan yang berlaku untuk p "kecil" , yaitu jauh lebih kecil dari 2 ^{n / 2} ). Misalnya, dengan SHA-256 ( n = 256 ) dan satu miliar pesan ( p = 10 ⁹ ) maka probabilitasnya sekitar 4,3 * 10 ^-60 .

Batuan ruang-pembunuh massal terjadi rata-rata setiap 30 juta tahun sekali. Hal ini mengarah pada kemungkinan kejadian seperti itu terjadi pada detik berikutnya menjadi sekitar 10 ^-15 . Itu 45 pesanan besarnya lebih mungkin daripada tabrakan SHA-256. Singkatnya, jika Anda menemukan SHA-256 bertabrakan menakutkan maka prioritas Anda salah.

Dalam pengaturan keamanan, di mana penyerang dapat memilih pesan yang akan di-hash, maka penyerang dapat menggunakan secara substansial lebih dari satu miliar pesan; Namun, Anda akan menemukan bahwa probabilitas keberhasilan penyerang masih akan semakin kecil. Itulah inti menggunakan fungsi hash dengan output 256-bit: sehingga risiko tabrakan dapat diabaikan.

Tentu saja, semua hal di atas mengasumsikan bahwa SHA-256 adalah fungsi hash "sempurna", yang masih jauh dari terbukti. Meski begitu, SHA-256 tampaknya cukup kuat.

Thomas Pornin
sumber

Ini jawaban yang sangat bagus, terima kasih! Tetapi, jika terjadi tabrakan, pembangkit listrik tenaga nuklir akan meledak, dan itu tergantung pada Anda, apakah Anda akan mengambil risiko itu? Jika Anda sepenuhnya benar, maka kita dapat mengambil risiko, karena 45 kali lipat lebih besar kemungkinan peradaban untuk dihancurkan. Baik?

Hristo Hristov

@Hristo saya pikir ya, orang akan mengambil risiko itu. Pembangkit listrik tenaga nuklir sudah memiliki peluang yang jauh lebih tinggi untuk meledak karena hal-hal lain, seperti kerusakan mekanis, kesalahan manusia dalam membangunnya atau kesalahan operator saat menjalankannya, dan kami sudah mengambil peluang itu. Jika tabrakan SHA-256 adalah satu-satunya hal yang menyebabkan insiden nuklir, kita hampir pasti memiliki nol di antaranya sejauh ini.

Roman Starkov

foxnews.com/science/2013/02/11/... Saya akan mulai memikirkan SHA512.

Dustin Oprea

Sekarang saya bisa tenang mengetahui bahwa saya kemungkinan akan dihancurkan oleh asteroid jauh sebelum saya hidup untuk mengalami tabrakan SHA-256.

AaronLS

Maaf, Anda melewatkan apa yang disebut "paradoks ulang tahun". Lihat lebih baik pada "tabel bagus", itu tidak bekerja seperti yang Anda pikirkan. Untuk angka yang saya berikan, dalam tabel itu, itu akan menjadi nilai "10 ^ 9" dalam kolom berlabel "4.3 * 10 ^ -60" dan baris "128 bit" (tetapi tabel tidak lebih rendah dari 10 ^ -18 ).

Thomas Pornin

Kemungkinan tabrakan tidak tergantung pada ukuran file, hanya pada jumlah mereka.

Ini adalah contoh dari paradoks ulang tahun . Halaman Wikipedia memberikan perkiraan kemungkinan tabrakan. Jika Anda menjalankan angka, Anda akan melihat bahwa semua hardisk yang pernah diproduksi di Bumi tidak dapat menampung cukup file 1MB untuk mendapatkan kemungkinan tabrakan bahkan 0,01% untuk SHA-256.

Pada dasarnya, Anda bisa mengabaikan kemungkinan itu.

Michael Borgwardt
sumber

Saya tidak bisa setuju dengan kesimpulannya. Ya, tidak ada hardisk yang dapat menyimpan jumlah file itu, tetapi Anda IMO salah menafsirkan situasinya. Hanya membutuhkan dua file untuk menghasilkan tabrakan. Meskipun kemungkinannya sangat rendah itu masih bisa terjadi.

sharptooth

@sharptooth: tidak, saya tidak salah menggambarkan situasinya. Kemungkinan Anda dan semua orang yang Anda kenal meninggal karena kecelakaan di jalan pada hari yang sama sangat rendah, tetapi itu masih bisa terjadi (dan itu jauh lebih tinggi daripada tabrakan SHA-256). Namun Anda mengabaikan kemungkinan itu.

Michael Borgwardt

@sharptooth: Saya berbicara tentang kecelakaan di jalan yang terpisah dan simultan dari beberapa ratus orang tertentu. Anda tidak dapat benar-benar mengambil langkah apa pun untuk membuatnya lebih rendah. Tidak ada gunanya, karena ini sudah sangat rendah. Tetapi masih jauh lebih mungkin daripada tabrakan SHA-256 yang Anda bahkan tidak bisa membayangkan berapa banyak. Argumennya sama dengan yang dibuat Thomas.

Michael Borgwardt

@sharptooth: Tidak, peluangnya tidak tumbuh secara signifikan, karena jumlahnya masih benar-benar dikerdilkan oleh ukuran ruang hash SHA-256. Ini adalah satu hal yang tidak Anda perhitungkan dengan benar - semua faktor harus ditimbang dengan besarnya sebenarnya, tidak sama. Jika Anda menghasilkan satu miliar hash per detik untuk setiap orang di Bumi, dan melakukannya selama seribu tahun, Anda masih memiliki peluang tabrakan kurang dari 1%.

Michael Borgwardt

Jika Anda tidak memeriksa kemungkinan kesalahan yang tidak diperbaiki pada setiap pengambilan dari memori atau membaca dari disk (yang memiliki probabilitas jauh lebih tinggi daripada tabrakan SHA-256), Anda mungkin tidak sepenuhnya memahami probabilitas.

Christophe

Pertama-tama, ini bukan nol, tetapi sangat dekat dengan nol .

Pertanyaan kuncinya adalah apa yang terjadi jika tabrakan benar-benar terjadi ? Jika jawabannya adalah "pembangkit listrik tenaga nuklir akan meledak" maka Anda kemungkinan tidak akan mengabaikan kemungkinan tabrakan. Dalam kebanyakan kasus, konsekuensinya tidak terlalu mengerikan sehingga Anda dapat mengabaikan kemungkinan tabrakan.

Juga jangan lupa bahwa perangkat lunak Anda (atau sebagian kecil dari itu) dapat digunakan dan secara bersamaan digunakan dalam trilyun komputer (beberapa mikrokomputer kecil yang tertanam yang hampir di mana-mana saat ini termasuk). Jika demikian, Anda perlu melipatgandakan estimasi yang Anda dapatkan dengan jumlah salinan sebanyak mungkin.

sharptooth
sumber

... bukan berdasarkan # salinan, tetapi # kumpulan data yang dicerna semua salinan.

Andreas Spindler

Ini salah, jumlah salinan dari perangkat lunak yang berjalan tidak relevan. Satu-satunya hal yang penting adalah jumlah file unik yang diproses dan paradoks ulang tahun adalah matematika untuk perhitungan.

Dirk Bester

Saya mendengar orang lain menyebutkan bahwa kemungkinan kegagalan perangkat keras - yaitu sedikit membalik di suatu tempat karena radiasi, dll - lebih mungkin daripada tabrakan hash, dan karenanya, mengkhawatirkan tabrakan hash konyol. Secara pribadi, saya akan mencoba untuk menutupi kedua kasus, agar aman (semakin aman di pembangkit listrik tenaga nuklir semakin baik), tetapi tabrakan hash mungkin sangat rendah pada daftar bahaya potensial (dengan asumsi ruang hash cukup besar) . Namun, ini semua mengasumsikan bahwa tidak ada beberapa perilaku tersembunyi dalam fungsi hash yang menyebabkan tabrakan lebih sering.

Chris Middleton

'0' memiliki wilayahnya

Green Tree

@ GreenTree Hal yang Anda tautkan adalah tentang sengaja membuat tabrakan.

sharptooth