Dlaczego szyfrowanie za pomocą tego samego jednorazowego pada nie jest dobre?

20

Aby zaszyfrować wiadomość za pomocą klawisza jednorazowego k wykonaj E n c ( m 1 , k ) = m 1k .m1kEnc(m1,k)=m1k

Jeśli użyjesz tego samego do zaszyfrowania innej wiadomości m 2 , otrzymasz E n c ( m 2 , k ) = m 2k , a jeśli wykonasz Xor obu tekstów zaszyfrowanych, otrzymasz ( m 1k ) ( m 2k ) = m 1m 2km2Enc(m2,k)=m2k

(m1k)(m2k)=m1m2

więc OK, istnieje pewien wyciek informacji, ponieważ uczysz się , ale dlaczego to nie jest bezpieczne? Nie mam możliwości nauki (powiedzmy) m 1, chyba że znam m 2 . Dlaczego więc źle jest używać k dwa razy?m1m2m1m2k

Ran G.
źródło
tak, to jest siew. Przede wszystkim debata na temat granicy między crypto.se i cs.se.
Ran G.
Proszę zobaczyć tutaj do dyskusji tagów używanych.
Raphael
Pamiętam, że widziałem wizualizację, która czyni ją naprawdę jasną, ale nie mogę jej teraz znaleźć. Czy ktoś wie o czym mówię? (Mam nadzieję, że nie pomylę tego z innym obrazem kryptograficznym, takim jak EBC Linux Pinguin itp.)
Ran G.
1
@RanG. : prawda - odpowiadające pytanie o crypto.se brzmi: Wykorzystanie jednorazowego ponownego użycia klucza?
David Cary

Odpowiedzi:

14

Nie mam możliwości nauki (powiedzmy) chyba że znam m 2 .m1m2

(m2k)m2=k

k

Ta ogólna strategia łamania kryptosystemu jest znana jako znany atak jawnego tekstu . Uważa się, że wiele systemów, takich jak AES i RSA, jest zabezpieczonych przed tymi atakami. Ale jednorazowa podkładka staje się wobec nich całkowicie niepewna, chyba że do każdego szyfrowania używana jest nowa podkładka, dlatego nazywane są „jednorazowymi podkładkami”.

Carl Mummert
źródło
11

Nie jest to bezpieczne dokładnie ze względu na podany powód - istnieje pewien wyciek informacji.

Zasadniczo, jeśli masz jakieś założenia dotyczące tekstów jawnych (tekst angielski, pliki o znanej strukturze itp.), Prowadzi to do łatwej analizy statystycznej. Prawdopodobnie użycie go dwa razy nie zmienia znacząco praktyczności ataku, ale użycie go wiele razy z nieprzypadkowym tekstem jawnym ostatecznie ujawnia wystarczającą ilość informacji, aby odzyskać klucz.

Wreszcie, jeśli masz możliwość użycia go tylko dwa razy , masz również możliwość użycia go tylko raz - ograniczenie polega na tym, że tych jednorazowych padów nie należy używać potencjalnie nieznanych i z czasem niszczących wiele razy.

m1m2

Znane ataki zwykłego tekstu są dość powszechne, względnie łatwo jest zmusić mechanizm szyfrowania do szyfrowania czegoś, co znasz a priori. Jeśli nie, zwykle możesz przyjąć rozsądne założenia statystyczne.

qdot
źródło
Ponadto jednorazowe pady mają właściwość polegającą na tym, że jeśli znasz szyfrację, a nawet część tekstu jawnego, możesz natychmiast odzyskać odpowiednią część klucza, co oznacza, że ​​część wszystkich przyszłych wiadomości zaszyfrowanych za pomocą tego samego pada jest skutecznie wysyłana do jasne (co ułatwia odgadnięcie większej ilości tekstu jawnego, ujawnienie większej ilości klucza itp.). Jeśli szyfrujesz wiele rzeczy, takich jak żądania e-mail lub HTTP, atakujący może prawie zawsze znać część tekstu jawnego po prostu ze względu na strukturę tych protokołów.
Ben
6

(m1k)(m2k)=m1m2

log226=4.7

Jeśli chcesz użyć jednorazowego pada dwa razy, musisz najpierw skompresować wiadomość. I nawet wtedy, jeśli nie użyjesz prawie idealnego algorytmu kompresji i użyjesz jednorazowego pada wiele razy, pozostanie wystarczająca ilość entropii, aby teoretycznie odzyskać wiadomości. Nie wiem, jak ciężko byłoby w praktyce.

Peter Shor
źródło
4

m1m2m1m2

W rzeczywistości w wielu przypadkach jest to bardzo proste. Oto prosta wizualizacja.

Ran G.
źródło
2

Oto intuicyjny sposób przedstawienia podejścia bez odwoływania się do matematyki. Załóżmy, że masz dwie zaszyfrowane wiadomości, które zostały zaszyfrowane za pomocą tego samego klawisza jednorazowego.

  1. Odgadnij słowo lub frazę, które mogą znajdować się w jednej z wiadomości. Powiedzmy frazę „Raport pogodowy”
  2. Począwszy od komunikatu 1, załóż, że „Raport pogodowy” występuje na pierwszej pozycji litery.
  3. Przelicz z powrotem pierwsze 14 znaków jednorazowego padu.
  4. Odszyfruj pierwsze 14 znaków wiadomości 2 przy użyciu obliczonego z góry OTP.
  5. Jeśli tekst jawny wygląda jak gobble-di-gook, wróć do kroku 2 i powtórz w pozycji 2 litery. Jeśli jednak otrzymasz sensowny tekst (na przykład „Dzień dobry I”, a następnie gratulacje), opracowałeś pierwsze 14 znaków OTP (i pierwsze 14 znaków każdej litery)
  6. Jeśli dojdziesz do końca wiadomości 1, nie wyrzucając niczego poza przypadkowymi literami, możesz dojść do wniosku, że wyrażenie „Raport pogodowy” nie występuje w wiadomości 1. Wróć do kroku 1 z inną frazą, na przykład „Drogi pułkowniku. „
Johnno
źródło