Apakah komunikasi terenkripsi XOR sederhana ini benar-benar aman?

23

Say Alice dan Peter masing-masing memiliki memory stick flash USB 4GB. Mereka bertemu dan menyimpan di kedua stik dua file bernama alice_to_peter.key(2GB) dan peter_to_alice.key(2GB) yang berisi bit yang dihasilkan secara acak. Mereka tidak pernah bertemu lagi, tetapi berkomunikasi secara elektronik. Alice juga memelihara variabel yang dipanggil alice_pointerdan Peter mempertahankan variabel yang dipanggil peter_pointer, yang keduanya awalnya diatur ke nol.

Ketika Alice perlu mengirim pesan kepada Peter, ia mengirim pesan ke ( nbyte byte pesan):

encrypted_message_to_peter[n] = message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]
encrypted_payload_to_peter = alice_pointer + encrypted_message_to_peter
alice_pointer += length(encrypted_message_to_peter)

(dan untuk keamanan maksimum, bagian yang digunakan dari kunci dapat dihapus)

Peter menerima encrypted_payload_to_peter, membaca alice_pointerdisimpan di awal pesan dan tidak:

message_to_peter[n] = encrypted_message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]

Dan untuk keamanan maksimum, setelah membaca pesan juga menghapus bagian kunci yang digunakan. - EDIT: Sebenarnya langkah ini dengan algoritma sederhana ini (tanpa pemeriksaan integritas dan otentikasi) mengurangi keamanan, lihat Paŭlo Ebermann posting di bawah ini.

Ketika Peter perlu mengirim pesan ke Alice mereka melakukan sebaliknya, kali ini dengan peter_to_alice.keydan peter_pointer.

Dengan skema sepele ini, mereka dapat mengirim setiap hari selama 50 tahun ke depan 2GB / (50 * 365) = ~ 115kB data terenkripsi di kedua arah. Jika mereka membutuhkan lebih banyak data untuk dikirim, mereka dapat menggunakan kunci yang lebih besar, misalnya dengan HD 2TB hari ini (tombol 1TB) akan mungkin untuk bertukar 60MB / hari selama 50 tahun ke depan! Itu banyak data dalam praktiknya; misalnya, menggunakan kompresi itu lebih dari satu jam komunikasi suara berkualitas tinggi.

Sepertinya saya bahwa tidak ada cara bagi penyerang untuk membaca pesan terenkripsi tanpa kunci, karena bahkan jika mereka memiliki komputer yang sangat cepat, dengan kekerasan mereka bisa mendapatkan setiap pesan yang mungkin di bawah batas, tetapi ini adalah angka astronomi pesan dan penyerang tidak tahu yang mana dari mereka adalah pesan yang sebenarnya.

Apakah saya benar? Apakah skema komunikasi ini benar-benar aman? Dan jika aman, apakah ia memiliki namanya sendiri? Enkripsi XOR sudah terkenal, tapi saya mencari nama aplikasi praktis konkret ini menggunakan tombol besar di kedua sisi? Saya dengan rendah hati berharap bahwa aplikasi ini telah menemukan seseorang sebelum saya. :-)

Catatan: Jika benar-benar aman maka itu luar biasa, karena dengan perangkat penyimpanan besar berbiaya rendah saat ini, akan jauh lebih murah untuk melakukan komunikasi yang aman daripada dengan kriptografi kuantum yang mahal, dan ini memiliki keamanan yang setara!

EDIT: Saya pikir ini akan lebih praktis di masa depan karena biaya penyimpanan berkurang.Itu dapat memecahkan komunikasi yang aman selamanya.Hari ini Anda tidak memiliki kepastian apakah seseorang berhasil menyerang cipher yang ada bahkan setahun kemudian dan membuat implementasinya yang sering mahal menjadi tidak aman. Dalam banyak kasus sebelum komunikasi terjadi, ketika kedua belah pihak bertemu secara pribadi, itulah saatnya untuk menghasilkan kunci. Saya pikir itu sempurna untuk komunikasi militer, misalnya antara kapal selam yang dapat memiliki HD dengan kunci besar, dan pusat militer dapat memiliki HD untuk setiap kapal selam. Bisa juga praktis dalam kehidupan sehari-hari, misalnya untuk mengontrol rekening bank Anda, karena ketika Anda membuat akun Anda bertemu dengan bank dll.

communication encryption pengguna3123061
sumber
4
Selain skema khusus untuk mengoordinasikan bagian mana dari kunci yang digunakan, ini hanya pad sekali pakai . Tetapi di bawah pemeriksaan lebih dekat ternyata tidak benar-benar berguna untuk 99% kasus penggunaan.
10
Karena pertanyaan ini adalah tentang kekuatan algoritma kripto tertentu, mungkin lebih cocok untuk crypto.stackexchange.com . Untuk memindahkan pertanyaan Anda di sana, Anda dapat menandai perhatian moderator dan meminta migrasi.
Bart van Ingen Schenau
12
OTP diciptakan lebih dari seabad yang lalu, dan digunakan, sebagai kertas fisik yang sebenarnya, di kedua Perang Dunia. ( en.wikipedia.org/wiki/One-time_pad ) Masalah dalam kriptografi maka seperti sekarang adalah pertukaran kunci.
Gort the Robot
6
Perhatikan bahwa ini masih membuat Anda menyelesaikan masalah menghasilkan kunci unik yang cukup untuk semua data yang diharapkan sampai kedua pihak bertemu lagi, dan bahwa kunci tersebut harus dihasilkan melalui proses acak GENUINELY - generator nomor pseudorandom rentan untuk dianalisis, semakin karena semakin banyak sampel menggunakan PRNG yang sama tersedia.
keshlam
1
@keshlam. Menghasilkan angka acak-kuantum yang benar menjadi sangat murah. Artikel menarik di arxiv: Pembuatan angka acak kuantum di ponsel: arxiv.org/abs/1405.0435
user3123061

Jawaban:

50

Ya, ini adalah kertas sekali pakai . Jika material utama tidak pernah digunakan kembali, secara teoritis aman.

Kelemahannya adalah bahwa Anda akan membutuhkan satu kunci per pasangan kepala sekolah yang berkomunikasi dan Anda akan membutuhkan cara yang aman untuk bertukar bahan kunci sebelum berkomunikasi.

Vatine
sumber
52
Saya pikir perlu ditekankan bahwa "aman secara teoritis" berarti secara matematis terbukti tidak bisa dipecahkan , asalkan kunci benar-benar acak dan tidak digunakan kembali. Itu adalah jaminan terkuat yang bisa Anda dapatkan di mana saja dalam kriptografi.
Michael Borgwardt
1
@MichaelBorgwardt titik besar di sana. Dalam hal ini "aman secara teoritis" sebenarnya lebih baik daripada "praktis aman".
Markus
2
contoh kasus: saya punya kunci acak 2GB yang kebetulan memiliki 16 byte berurutan dari 0.
Michael
@Michael Kemungkinan itu terjadi sekitar 1 dalam 10 ^ 27.
ini
1
@ Floris "Kalkulasi" Saya: Satu byte memiliki 256 nilai yang memungkinkan. Itu adalah satu dari 256 yang semuanya akan menjadi nol. 256 ^ 16 untuk mendapatkan kesempatan selama 16 byte. Dan kemudian membagi jumlah byte dalam 2GB secara kebetulan. Saya pikir saya ketinggalan sebuah divisi dengan 16, tetap di sini (1024 * 1024 * 1024 * 1024 * 2 * (1/16)) / (256 ^ 16) Poin terakhir Anda membuat perhitungan ini tidak relevan lagi.
ini
32

Seperti yang ditunjukkan oleh jawaban Vatine , algoritma Anda pada dasarnya adalah one-time-pad.

Namun, untuk mengomentari salah satu catatan Anda:

Catatan: Jika ini benar-benar aman maka itu luar biasa karena dengan kenangan besar berbiaya rendah saat ini praktis cara komunikasi yang lebih nyaman daripada kriptografi kuantum mahal dan dengan keamanan setara!

Tanggapan saya adalah tidak, itu tidak luar biasa. Iblis selalu dalam perincian, dan iblis di sini adalah dalam pertukaran kunci. Metode Anda bergantung pada pertukaran kunci tanpa cacat dan langsung. Saya tidak mampu mengirim James Bond membawa flash disk 4GB untuk saya ke setiap pedagang di internet setiap kali saya ingin membeli sesuatu atau memiliki koneksi aman lainnya.

Dan terakhir, aspek XOR dari algoritma Anda tidak penting. Cipher substitusi sederhana baik-baik saja dengan OTP. Kekuatan OTP adalah bahwa kuncinya tidak pernah digunakan kembali, dan mengasumsikan James Bond dengan sempurna bertukar kunci untuk kedua belah pihak (yaitu pertukaran kunci aman sebelumnya)

Apa namanya
sumber
13
Hal lain tentang OTP adalah kuncinya adalah (setidaknya) selama pesan untuk dienkripsi, dan membutuhkan sumber nomor acak berkualitas sangat tinggi.
Donal Fellows
Banyak algoritma enkripsi bekerja dengan entah bagaimana mengubah kunci menjadi aliran data yang tidak dapat dibedakan dari data acak, kemudian menggunakan data itu sebagai bantalan satu kali. Dari perspektif penyerang, tidak ada perbedaan antara data yang benar-benar acak dan data yang tidak dapat dibedakan dari data acak (menurut definisi; jika Anda menemukan perbedaan, itu tidak bisa dibedakan), jadi secara teori ini sama amannya dengan OTP . Tentu saja, ketika kita mengatakan data tidak dapat dibedakan dari data acak yang sebenarnya, biasanya ada banyak peringatan. Penjelasan ini tentu saja merupakan penyederhanaan berlebihan.
Brian
21

Sementara one-time-pad memiliki jaminan privasi tanpa syarat (terbukti secara matematis) terhadap penyerang yang hanya dapat membaca pesan, ia memiliki beberapa kelemahan.

  • Seorang penyerang mencegat yang menebak dengan benar teks biasa dapat memanipulasi teks sandi untuk apa pun yang diinginkannya (dengan panjang yang sama).

  • Jika penyerang memasukkan atau menghapus beberapa pesan (atau sebagian darinya), petunjuk Alice dan Bob menjadi tidak sinkron dan setiap komunikasi di masa depan terputus.

    Pembaruan: Ini diasumsikan bahwa kedua belah pihak melacak kedua petunjuk. Jika Anda mengirim nilai pointer saat ini, Anda rentan terhadap serangan dua-waktu-pad (jika Anda membiarkan rentang kunci yang sama digunakan lebih dari sekali) atau serangan-DOS (jika Anda tidak mengizinkan rentang kunci yang sama untuk digunakan lebih dari sekali, misalnya dengan menghapusnya).

Kedua masalah tersebut disebabkan oleh hilangnya integritas dan perlindungan otentikasi - Anda memiliki sandi yang sempurna, tetapi tidak memiliki MAC.

Tambahkan MAC ke protokol sekali pakai Anda untuk membuatnya benar-benar aman. Setiap pesan harus mendapatkan "checksum" yang memastikan bahwa itu sebenarnya dikirim oleh pengirim yang seharusnya, dan tidak dimodifikasi di antaranya. Anda juga harus mengirim beberapa nomor urut sehingga penerima tahu bagian mana dari kunci yang digunakan ketika pesan sebelumnya hilang (atau untuk menolak pesan jika digandakan) - termasuk dalam perhitungan checksum.

Algoritma MAC biasa akan dilakukan di sini, tetapi saya kira Anda mungkin ingin menggunakan beberapa polinomial MAC untuk mendapatkan keamanan yang cocok dengan pad satu kali Anda. (Ambil kunci MAC dari bit sebelum atau setelah kunci enkripsi Anda, yaitu jangan menggunakan kembali satu kunci untuk kedua tujuan.)

Paŭlo Ebermann
sumber
Jika penyerang memasukkan atau menghapus beberapa pesan (atau sebagian darinya), petunjuk Alice dan Bob menjadi tidak sinkron dan setiap komunikasi di masa depan terputus. Pointer independen dan tidak perlu disinkronkan sehingga tidak ada komunikasi di masa depan yang rusak jika pesan hilang (offset kunci yang sebenarnya digunakan untuk mengenkripsi pesan dikirim dengan pesan itu). Tapi Anda sebagian benar: Tidak sinkron digunakan bagian dari kunci di sisi penerima yang tidak dihapus karena pesan yang dihapus tidak diterima (bagian yang digunakan akan dihapus dengan pesan yang diterima berikutnya).
user3123061
Tapi kamu benar. Algoritme sederhana yang disajikan kehilangan integritas dan otentikasi. Implementasi praktis perlu lebih kuat.
user3123061
@ user3123061 Saya tidak akan mengabaikan integritas dan otentikasi jika saya adalah Anda. Teknik serangan ciphertext terpilih yang adaptif mengeksploitasi ketiadaan perlindungan integritas untuk memecah kerahasiaan . Saya akan mengatakan bahwa pad sekali pakai klasik (yang telah Anda temukan kembali) benar-benar tidak aman , terlepas dari soliditas matematisnya yang nyata, hanya karena serangan ini.
zwol
2
Serangan cipertext terpilih yang adaptif adalah pilihan serangan yang sangat buruk terhadap OTP yang diperiksa manusia. OOS akan diperhatikan dan penyerang Anda akan dikerjai cukup cepat. Hanya jika penerima diproses dengan mesin dan menghasilkan respons maka serangan ini ada gunanya sama sekali.
Joshua
@Zack Ada banyak masalah dengan OTP, tetapi tidak ada yang mengancam kerahasiaan. Perhatikan bahwa bahkan jika Anda menebak dengan sempurna kunci plantext + pesan sebelumnya, pesan berikutnya dienkripsi dengan kunci independen yang sama sekali baru (dengan ukuran yang cukup besar). Tidak ada yang dapat beradaptasi dengan lebih dari beberapa interaksi.
4

Sebenarnya itu tidak sepenuhnya aman. Apa kebocoran protokol Anda adalah LENGTH dari pesan yang dikomunikasikan.

Misalnya, jika mata-mata tahu Anda akan membalas dengan "ya" atau "tidak" dan melihat panjang = 2 ia dapat menyimpulkan itu "tidak".

Sungguh menakjubkan betapa banyak yang dapat disimpulkan hanya dari panjang yang diketahui jika seseorang dapat menebak konteksnya.

w.pasman
sumber
3
Itu cukup mudah untuk diperbaiki, ke tingkat keamanan yang masuk akal, karena Anda dapat mengisi pesan dengan sampah acak, sehingga panjang pesan adalah kelipatan dari ukuran blok tetap - katakanlah 256 karakter. Itu akan mengalahkan analisis ya v tidak sederhana, dengan biaya menggunakan OTP lebih cepat.
Peter Bagnall
Memang - karena Anda dapat mengirim ~ 115kB setiap hari selama 50 tahun ke depan, Anda mungkin berharap bahwa setiap blok setidaknya 20kb, yang berarti panjangnya tidak begitu penting.
apnorton