Mengapa mengenkripsi dengan pad satu waktu yang sama tidak baik?

20

Untuk mengenkripsi pesan $m_1$ dengan kunci satu kali $k$ Anda lakukan $Enc(m_1,k) = m_1 \oplus k$ .

Jika Anda menggunakan sama $k$ untuk mengenkripsi pesan yang berbeda $m_2$ Anda mendapatkan $Enc(m_2,k) = m_2 \oplus k$ , dan jika Anda melakukan Xor dari dua ciphertext yang Anda dapatkan

(m_{1} \oplus k) \oplus (m_{2} \oplus k) = m_{1} \oplus m_{2}

$( m_1 \oplus k) \oplus ( m_2 \oplus k) = m_1 \oplus m_2$

jadi, OK, ada beberapa kebocoran informasi karena kamu belajar , tetapi mengapa itu tidak aman? Saya tidak punya cara untuk belajar (katakanlah) kecuali saya tahu . Jadi mengapa salah menggunakan dua kali ?? $m_1 \oplus m_2$ $m_1$ $m_2$ $k$

cryptography information-theory encryption Ran G.
sumber

ya, ini penyemaian. Terutama, menyemai perdebatan tentang batas antara crypto.se dan cs.se.

Ran G.

Silakan lihat di sini untuk diskusi tentang tag yang digunakan.

Raphael

Saya ingat saya melihat visualisasi yang membuatnya sangat jelas, tetapi saya tidak dapat menemukannya sekarang. Adakah yang tahu apa yang saya bicarakan? (Saya harap saya tidak bingung dengan gambar crypto lain seperti ECB linux-pinguin, dll.)

Ran G.

1

@RANG. : benar - pertanyaan crypto.se yang sesuai ada di Mengambil keuntungan dari penggunaan kembali kunci pad sekali pakai?

David Cary

Proyek Venona

sdcvvc

14

Saya tidak punya cara untuk belajar (katakanlah) kecuali saya tahu . $m_1$ $m_2$

Itulah masalahnya - jika Anda menggunakan kembali kunci yang sama, dan seseorang memiliki akses ke satu pesan yang Anda enkripsi dalam bentuk plaintext dan terenkripsi, mereka dapat menggunakannya untuk menemukan kunci Anda:

(m_{2} \oplus k) \oplus m_{2} = k

$(m_2 \oplus k) \oplus m_2 = k$

Sebagai skenario alternatif, jika Anda menggunakan kunci yang sama berulang-ulang, penyerang mungkin dapat menebak hanya beberapa bagian dari pesan terenkripsi, dan setiap tebakan yang berhasil mengungkapkan bagian dari kunci , sehingga seiring waktu semakin banyak kunci terungkap. $k$

Strategi umum ini untuk memecahkan cryptosystem dikenal sebagai serangan plaintext yang dikenal . Banyak sistem, seperti AES dan RSA, diyakini aman terhadap serangan ini. Tetapi pad sekali pakai menjadi benar-benar tidak aman terhadap mereka kecuali pad baru digunakan untuk setiap enkripsi, itulah sebabnya mereka disebut "bantalan sekali pakai".

Carl Mummert
sumber

11

Tidak aman justru karena alasan yang Anda sebutkan - ada beberapa informasi yang bocor.

Pada dasarnya, jika Anda memiliki asumsi tentang plaintext (teks bahasa Inggris, file dengan struktur yang diketahui, dll), itu mengarah pada analisis statistik yang mudah. Mungkin menggunakannya dua kali tidak mengubah kepraktisan serangan secara signifikan, tetapi menggunakannya berkali-kali dengan plaintext non-acak, akhirnya mengungkapkan informasi yang cukup untuk memulihkan kunci.

Akhirnya, jika Anda memiliki kemampuan untuk menggunakannya hanya dua kali , Anda juga memiliki kemampuan untuk menggunakannya hanya sekali - batasannya adalah bahwa bantalan sekali pakai ini tidak boleh digunakan yang berpotensi tidak diketahui dan seiring waktu, merusak beberapa kali.

$m_1$ $m_2$

Serangan teks biasa dikenal cukup umum, itu cukup mudah untuk memaksa mekanisme enkripsi untuk mengenkripsi sesuatu yang Anda tahu a-priori. Jika tidak, Anda biasanya dapat membuat asumsi statistik yang masuk akal.

qdot
sumber

Selain itu, satu kali bantalan memiliki properti yang jika Anda tahu teks cyphertext dan bahkan bagian dari teks, Anda dapat segera memulihkan bagian yang sesuai dari kunci, yang berarti bagian dari semua pesan di masa depan yang dienkripsi dengan bantalan yang sama secara efektif dikirim dalam clear (membuatnya lebih mudah untuk menebak beberapa plaintext, mengungkapkan lebih banyak kunci, dll). Jika Anda mengenkripsi banyak hal seperti email atau permintaan HTTP, maka penyerang hampir selalu dapat mengetahui bagian dari teks biasa hanya karena struktur protokol ini.

Ben

6

$(m_1 \oplus k) \oplus (m_2 \oplus k) = m_1 \oplus m_2$

$\log_2 26 = 4.7$

Jika Anda ingin menggunakan kertas satu kali dua kali, Anda harus mengompres pesan Anda terlebih dahulu. Dan bahkan kemudian, jika Anda tidak menggunakan algoritma kompresi yang hampir sempurna, dan Anda menggunakan pad satu kali beberapa kali, akan ada cukup entropi yang tersisa untuk memulihkan pesan secara teoritis. Saya tidak tahu betapa sulitnya dalam praktek.

Peter Shor
sumber

4

$m_1$ $m_2$ $m_1 \oplus m_2$

Sebenarnya, untuk banyak kasus, ini sangat sederhana. Berikut visualisasi sederhana.

Ran G.
sumber

2

Inilah cara intuitif untuk mewakili pendekatan tanpa bantuan matematika. Katakanlah Anda memiliki dua pesan terenkripsi yang telah dienkripsi dengan satu panel waktu yang sama.

Buat tebakan pada kata atau frasa yang mungkin terkandung dalam salah satu pesan. Katakanlah frasa "Laporan cuaca"
Dimulai dengan pesan 1, asumsikan "Laporan Cuaca" muncul di posisi huruf pertama.
Hitung kembali 14 karakter pertama dari bantalan satu kali.
Dekripsi 14 karakter pertama dari pesan 2 menggunakan OTP yang dihitung kembali.
Jika plaintext terlihat seperti gobble-di-gook, maka kembali ke langkah 2 dan ulangi pada posisi huruf 2. Namun, jika Anda mendapatkan teks yang bermakna (misalnya "Selamat Pagi I" lalu selamat, Anda telah mengerjakan 14 karakter pertama dari OTP (dan 14 karakter pertama dari setiap huruf)
Jika Anda sampai di akhir pesan 1 tanpa memuntahkan apa pun selain huruf acak, maka Anda dapat menyimpulkan bahwa frasa "Laporan Cuaca" tidak muncul dalam pesan 1. Kembali ke langkah 1 dengan frasa yang berbeda seperti "Kolonel yang Terhormat" "

Johnno
sumber

Mengapa mengenkripsi dengan pad satu waktu yang sama tidak baik?

Jawaban: