Apa perbedaan antara serangan preimage kedua dan serangan collision?

Wikipedia mendefinisikan serangan preimage kedua sebagai:

diberi pesan tetap m1, cari pesan berbeda m2 sedemikian sehingga hash (m2) = hash (m1).

Wikipedia mendefinisikan serangan tabrakan sebagai:

temukan dua pesan berbeda sembarang m1 dan m2 sedemikian sehingga hash (m1) = hash (m2).

Satu-satunya perbedaan yang bisa saya lihat adalah bahwa dalam serangan preimage kedua, m1 sudah ada dan dikenal oleh penyerang. Namun, itu tidak menurut saya signifikan - tujuan akhirnya masih menemukan dua pesan yang menghasilkan hash yang sama.

Apa perbedaan penting dalam bagaimana serangan preimage kedua dan serangan tabrakan dilakukan? Apa perbedaan hasil?

(Selain itu, saya tidak dapat menandai pertanyaan ini dengan benar. Saya mencoba menerapkan tag "kriptografi keamanan pra-gambar tabrakan" tetapi saya tidak memiliki reputasi yang cukup. Dapatkah seseorang menerapkan tanda yang sesuai?)

Saya dapat memotivasi perbedaan untuk Anda dengan skenario serangan.

Dalam serangan preimage pertama , kami meminta lawan, hanya diberikan , untuk menemukan atau sehingga = . Misalkan sebuah situs web menyimpan dalam basis datanya alih-alih . Situs web masih dapat memverifikasi keaslian pengguna dengan menerima kata sandi mereka dan membandingkan (dengan probabilitas untuk beberapa besar untuk positif palsu). Sekarang anggaplah basis data ini bocor atau dikompromikan. Sebuah serangan preimage pertamam m ′ H ( m ′ ) H ( m ) { u s e r n a m e , H ( p a s s w o r d ) } { u s e r n a m e , p a s s w o r d } H ( i $H(m)$$m$$m'$$H(m')$$H(m)$$\{username, H(password)\}$$\{username, password\}$1 / 2 n$H(input) =? H(password)$$1/2^n$$n$adalah situasi di mana musuh hanya memiliki akses ke pesan intisari dan sedang berusaha menghasilkan pesan yang hash untuk nilai ini.

Dalam serangan preimage kedua , kami mengizinkan lawan informasi lebih lanjut. Secara khusus, kita tidak hanya memberinya tetapi juga memberinya . Pertimbangkan fungsi hash mana dan adalah bilangan prima besar dan adalah konstanta publik. Jelas untuk serangan preimage pertama ini menjadi masalah RSA dan diyakini sulit. Namun, dalam kasus serangan preimage kedua menemukan tabrakan menjadi mudah. Jika seseorang menetapkan ,m H ( m ) = m $H(m)$$m$p q d m ′ = m p q + m H ( m p q + m ) = ( m p q + m ) $H(m) = m^d \mod{pq}$$p$$q$$d$$m' = mpq + m$$H(mpq + m) = (mpq + m)^d \mod{pq} = m^d \mod{pq}$. Dan musuh telah menemukan tabrakan dengan sedikit atau tanpa perhitungan.

Kami ingin fungsi hash satu arah agar tahan terhadap serangan preimage kedua karena skema tanda tangan digital, dalam hal ini dianggap informasi publik dan diteruskan (melalui tingkat tipuan) dengan setiap salinan dokumen. Di sini penyerang memiliki akses ke dan . Jika penyerang dapat membuat variasi pada dokumen asli (atau pesan yang sama sekali baru) sedemikian rupa sehingga ia dapat menerbitkan dokumennya seolah-olah ia adalah penandatangan asli.d o c u m e n t H ( d o c u m e n t ) d ′ H ( d ′ ) = H ( d o c u m e n t $H(document)$$document$$H(document)$$d'$$H(d') = H(document)$

Sebuah serangan tabrakan memungkinkan musuh bahkan lebih banyak kesempatan. Dalam skema ini, kami meminta lawan (dapatkah saya memanggilnya Bob?) Untuk menemukan dua pesan dan sedemikian rupa sehingga . Karena prinsip pigeonhole dan paradoks ulang tahun, bahkan fungsi hash 'sempurna' secara quadratically lebih lemah untuk serangan tabrakan daripada serangan preimage. Dengan kata lain, diberikan fungsi intisari pesan yang tidak dapat diprediksi dan tidak dapat diubah, yang membutuhkan waktu untuk memaksa, tabrakan dapat selalu ditemukan dalam waktu yang diharapkan .m $m_1$$m_2$f ( { 0 , 1 } ∗ ) = { 0 , 1 } n O ( 2 n ) O ( s q r t ( 2 n ) ) = O ( 2 n / 2$H(m_1) = H(m_2)$$f(\{0,1\}^*) = \{0,1\}^n$$O(2^n)$$O(sqrt(2^n)) = O(2^{n/2})$

Bob dapat menggunakan serangan tabrakan untuk keuntungannya dalam banyak hal. Berikut adalah salah satu yang paling sederhana: Bob menemukan tabrakan antara dua binari dan ( ) sehingga b adalah patch keamanan Microsoft Windows yang valid dan adalah malware. (Bob bekerja untuk Windows). Bob mengirimkan patch keamanannya ke atas rantai komando, di mana di belakang lemari besi mereka menandatangani kode dan mengirimkan biner ke pengguna Windows di seluruh dunia untuk memperbaiki kesalahan. Bob sekarang dapat menghubungi dan menginfeksi semua komputer Windows di seluruh dunia dengan dan tanda tangan yang dikomputasi oleh Microsoft untukb ′ H ( b ) = H ( b ′ ) b ′ b ′$b$$b'$$H(b) = H(b')$$b'$$b'$$b$. Di luar skenario serangan seperti ini, jika fungsi hash diyakini tahan benturan, fungsi hash itu juga lebih cenderung tahan terhadap preimage.

Serangan tabrakan mungkin jauh lebih mudah, tetapi jika berhasil, jauh lebih bermanfaat.

Masalah yang Ross sebutkan sebagai masalah log diskrit dalam kenyataannya adalah masalah yang sama sekali berbeda, masalah RSA, yang jauh lebih terkait dengan komputasi akar daripada log diskrit.