Czy ta prosta, szyfrowana komunikacja XOR jest absolutnie bezpieczna?

23

Powiedzmy, że Alice i Peter mają 4 GB pamięci flash USB. Spotykają i zapisują na obu patykach dwa pliki o nazwach alice_to_peter.key(2 GB) i peter_to_alice.key(2 GB), które zawierają losowo wygenerowane bity. Nigdy więcej się nie spotykają, ale komunikują się elektronicznie. Alice utrzymuje również wywoływaną zmienną, alice_pointera Peter utrzymuje wywoływaną zmienną peter_pointer, które początkowo są zerowane.

Kiedy Alice musi wysłać wiadomość do Piotra, robi to (gdzie njest n-ty bajt wiadomości):

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)

~~(i dla maksymalnego bezpieczeństwa, wykorzystaną część klucza można usunąć)~~

Piotr odbiera encrypted_payload_to_peter, czyta alice_pointerzapisane na początku wiadomości i wykonuje:

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

~~Aby zapewnić maksymalne bezpieczeństwo, po przeczytaniu wiadomości usuń również zużytą część klucza.~~ - EDYCJA: W rzeczywistości ten krok z tym prostym algorytmem (bez sprawdzania integralności i uwierzytelniania) zmniejsza bezpieczeństwo, patrz post Paŭlo Ebermann poniżej.

Kiedy Peter musi wysłać wiadomość do Alicji, robią to odwrotnie, tym razem z peter_to_alice.keyi peter_pointer.

Za pomocą tego trywialnego schematu mogą przesyłać codziennie przez kolejne 50 lat 2 GB / (50 * 365) = ~ 115 kB zaszyfrowanych danych w obu kierunkach. Jeśli potrzebują więcej danych do wysłania, mogą użyć większych kluczy, na przykład w dzisiejszych dyskach HD o pojemności 2 TB (klucze 1 TB) możliwa byłaby wymiana 60 MB dziennie przez następne 50 lat! To dużo danych w praktyce; na przykład użycie kompresji to ponad godzina wysokiej jakości komunikacji głosowej.

Wydaje mi się, że atakujący nie ma możliwości odczytania zaszyfrowanych wiadomości bez kluczy, ponieważ nawet jeśli mają nieskończenie szybki komputer, z brutalną siłą mogą uzyskać każdą możliwą wiadomość poniżej limitu, ale jest to liczba astronomiczna wiadomości, a atakujący nie wie, która z nich jest faktyczną wiadomością.

Czy mam rację? Czy ten schemat komunikacji jest naprawdę absolutnie bezpieczny? A jeśli jest bezpieczny, to czy ma własną nazwę? Szyfrowanie XOR jest dobrze znane, ale szukam nazwy tej konkretnej praktycznej aplikacji wykorzystującej duże klucze po obu stronach? Pokornie oczekuję, że ta aplikacja została wymyślona przez kogoś przede mną. :-)

Uwaga: jeśli jest absolutnie bezpieczny, to jest niesamowity, ponieważ przy dzisiejszych tanich i dużych urządzeniach pamięci masowej bezpieczniejsza komunikacja byłaby znacznie tańsza niż przy drogiej kryptografii kwantowej, a to ma równoważne bezpieczeństwo!

EDYCJA: Myślę, że będzie to bardziej praktyczne w przyszłości, gdy koszty przechowywania spadną.~~Może na zawsze rozwiązać bezpieczną komunikację.~~Dziś nie masz pewności, czy ktoś z powodzeniem zaatakuje istniejące szyfry nawet rok później i sprawi, że jego często drogie implementacje będą niebezpieczne. W wielu przypadkach przed komunikacją, kiedy obie strony spotykają się osobiście, nadszedł czas na wygenerowanie kluczy. Myślę, że jest idealny do komunikacji wojskowej, na przykład między okrętami podwodnymi, które mogą mieć dyski twarde z dużymi kluczami, a centrala wojskowa może mieć dyski twarde dla każdej łodzi podwodnej. Może być również praktyczny w życiu codziennym, na przykład do kontrolowania konta bankowego, ponieważ podczas tworzenia konta spotykasz się z bankiem itp.

communication encryption

— użytkownik3123061
źródło

4

Oprócz określonego schematu koordynowania, której części klucza użyć, jest to tylko jednorazowa podkładka . Ale przy bliższej kontroli okazuje się, że w rzeczywistości nie jest przydatny w 99% przypadków użycia.

10

Ponieważ pytanie dotyczy siły określonego algorytmu kryptograficznego, może być bardziej odpowiednie dla crypto.stackexchange.com . Aby przenieść tam swoje pytanie, możesz oflagować uwagę moderatora i poprosić o migrację.

— Bart van Ingen Schenau

12

OTP zostały wynalezione ponad sto lat temu i były używane jako rzeczywiste fizyczne podkładki papieru w obu wojnach światowych. ( en.wikipedia.org/wiki/One-time_pad ) Problemem w kryptografii jest, jak teraz, wymiana kluczy.

— Gort the Robot

6

Należy pamiętać, że nadal pozwala to rozwiązać problem generowania wystarczającej liczby unikatowych kluczy dla wszystkich oczekiwanych danych, dopóki obie strony nie spotkają się ponownie, oraz że klucze muszą zostać wygenerowane w RZECZOWO losowym procesie - generatory liczb pseudolosowych są narażone na analizę, w coraz większym stopniu w miarę udostępniania większej liczby próbek przy użyciu tego samego PRNG.

— keshlam

1

@keshlam. Generowanie prawdziwych liczb losowo-kwantowych staje się bardzo tanie. Ciekawy artykuł na arXiv: Quantum generowania liczb losowych z telefonu komórkowego: arxiv.org/abs/1405.0435

— user3123061

50

Tak, to jednorazowa podkładka . Jeśli kluczowy materiał nigdy nie zostanie ponownie użyty, jest teoretycznie bezpieczny.

Wadą jest to, że potrzebujesz jednego klucza na parę komunikujących się zleceniodawców i potrzebujesz bezpiecznego sposobu wymiany klucza przed komunikacją.

— Vatine
źródło

52

Myślę, że warto podkreślić, że „teoretycznie bezpieczny” oznacza, że matematycznie udowodniono, że jest niezniszczalny , pod warunkiem, że klucze są naprawdę losowe i nie są ponownie używane. To prawie najsilniejsza gwarancja, jaką można uzyskać w dowolnym miejscu w kryptografii.

— Michael Borgwardt

1

@MichaelBorgwardt ogromny punkt tam. W tym przypadku „teoretycznie bezpieczny” faktycznie jest lepszy niż „praktycznie bezpieczny”.

— Mark

2

przypadek: mam losowy klucz 2 GB, który ma 16 kolejnych bajtów równych 0.

— Michael

@Michael Szanse na to są około 1 na 10 ^ 27.

— to

1

@Floris Moje „obliczenie”: bajt ma 256 możliwych wartości. To jest jeden na 256, że wszystko będzie zero. 256 ^ 16, aby uzyskać szansę na 16 bajtów. A następnie podziel tę liczbę bajtów na 2 GB. Wydaje mi się, że przegapiłem podział przez 16, w każdym razie tutaj (1024 * 1024 * 1024 * 1024 * 2 * (1/16)) / (256 ^ 16) Twój ostatni punkt sprawia, że te obliczenia i tak nie mają znaczenia.

— tego

32

Jak wskazuje odpowiedź Vatine , twój algorytm jest w zasadzie jednorazowy.

Aby jednak skomentować jedną z twoich notatek:

Uwaga: jeśli jest absolutnie bezpieczny, to jest niesamowity, ponieważ przy dzisiejszych tanich pamięciach jest praktycznie o wiele tańszy sposób bezpiecznej komunikacji niż kosztowna kryptografia kwantowa i równoważne bezpieczeństwo!

Moja odpowiedź brzmi: nie, to nie jest niesamowite. Diabeł zawsze tkwi w szczegółach, a diabeł tutaj polega na wymianie kluczy. Twoja metoda zależy od bezbłędnej wymiany kluczy twarzą w twarz. Nie mogę sobie pozwolić na wysyłanie Jamesa Bonda z dyskiem flash 4 GB dla mnie do każdego sprzedawcy w Internecie za każdym razem, gdy chcę coś kupić lub mieć inne bezpieczne połączenia.

Wreszcie aspekt XOR algorytmu nie jest ważny. Prosty szyfr zastępczy jest w porządku z OTP. Siłą OTP jest to, że klucz nigdy nie jest ponownie używany, i zakłada, że James Bond bezbłędnie wymienia klucze dla obu stron (tj. Wcześniejsza bezpieczna wymiana kluczy)

— Jaka jest nazwa?
źródło

13

Inną cechą OTP jest to, że klucz jest (przynajmniej) tak długi, jak wiadomość do zaszyfrowania, i potrzebuje źródła liczb losowych o bardzo wysokiej jakości.

— Donal Fellows

Wiele algorytmów szyfrowania działa poprzez konwersję klucza w strumień danych, który jest nie do odróżnienia od danych losowych, a następnie wykorzystanie tych danych jako jednorazowej podkładki. Z punktu widzenia atakującego nie ma różnicy między danymi, które są naprawdę przypadkowe, a danymi, których nie można odróżnić od danych losowych (z definicji; jeśli znalazłeś różnicę, nie było nie do odróżnienia), więc teoretycznie jest to tak samo bezpieczne jak OTP . Oczywiście, gdy mówimy, że danych nie można odróżnić od prawdziwych danych losowych, zwykle istnieje szereg zastrzeżeń. To wyjaśnienie jest oczywiście rażącym nadmiernym uproszczeniem.

— Brian

21

Chociaż jednorazowa podkładka ma bezwarunkową (matematycznie udowodnioną) gwarancję prywatności przeciwko atakującemu, który może tylko czytać wiadomości, ma pewne słabości.

Przechwytujący atakujący, który poprawnie zgaduje zwykły tekst, może manipulować tekstem zaszyfrowanym do dowolnego celu (o tej samej długości).
Jeśli atakujący wstawi lub usunie jakąś wiadomość (lub jej część), wskaźniki Alicji i Boba nie są zsynchronizowane i każda kolejna komunikacja jest przerywana.

Aktualizacja: Założono, że obie strony śledzą oba wskaźniki. Jeśli wyślesz bieżącą wartość wskaźnika, jesteś podatny na ataki z użyciem dwóch bloków czasowych (jeśli zezwolisz na użycie tego samego zakresu klucza więcej niż jeden raz) lub ataki DOS (jeśli nie zezwolisz na ten sam zakres klucza do wykorzystania więcej niż jeden raz, np. poprzez ich usunięcie).

Oba te problemy są spowodowane brakującą ochroną integralności i uwierzytelnienia - masz doskonały szyfr, ale nie masz MAC.

Dodaj MAC do protokołu jednorazowego pada, aby rzeczywiście był bezpieczny. Każda wiadomość powinna otrzymać „sumę kontrolną”, która gwarantuje, że faktycznie została wysłana przez domniemanego nadawcę i nie została zmodyfikowana pomiędzy. Powinieneś również wysłać jakiś numer sekwencyjny, aby odbiorca wiedział, której części klucza użyć, gdy poprzednia wiadomość zaginęła (lub odrzucić wiadomość, jeśli jest zduplikowana) - uwzględnij to w obliczeniu sumy kontrolnej.

Zrobiłby to zwykły algorytm MAC, ale przypuszczam, że możesz chcieć użyć jakiegoś jednorazowego wielomianowego MAC, aby mieć zabezpieczenia dopasowane do twojego jednorazowego pada. (Wyjmij klucz MAC z bitów przed lub po kluczu szyfrującym, tj. Nie używaj ponownie jednego klucza do obu celów.)

— Paŭlo Ebermann
źródło

Jeśli atakujący wstawi lub usunie jakąś wiadomość (lub jej część), wskaźniki Alicji i Boba nie są zsynchronizowane i każda kolejna komunikacja jest przerywana. Wskaźniki są niezależne i nie muszą być zsynchronizowane, więc żadna przyszła komunikacja nie zostanie przerwana, jeśli wiadomość zostanie utracona (faktyczne przesunięcie klucza używanego do szyfrowania wiadomości jest wysyłane z tą wiadomością). Ale masz częściowo rację: po synchronizacji używana jest część klucza po stronie odbierającej, która nie jest usuwana, ponieważ usunięta wiadomość nie została odebrana (zużyta część zostanie usunięta z następną otrzymaną wiadomością).

— user3123061

Ale masz rację. Przedstawiono prosty brak integralności i uwierzytelnienia algorytmu. Praktyczne wdrożenie będzie musiało być bardziej niezawodne.

— user3123061

@ user3123061 Gdybym był tobą, nie zlekceważyłbym integralności i uwierzytelnienia. Technika adaptacyjnego ataku wybranego tekstu zaszyfrowanego wykorzystuje brak ochrony integralności do złamania poufności . Chciałbym posunąć się nawet do stwierdzenia, że klasyczna jednorazowa podkładka (którą właśnie wymyśliłeś na nowo) jest całkowicie niepewna , pomimo swojej matematycznej solidności, tylko z powodu tego ataku.

— zwolnienie

2

Adaptacyjny wybór ataku zaszyfrowanego tekstu jest dość słabym wyborem ataku na OTP sprawdzony przez człowieka. OOS zostanie zauważony, a twój atakujący zostanie dość szybko zlikwidowany. Tylko jeśli odbiornik jest przetwarzany maszynowo i daje odpowiedź, atak ten jest w ogóle dobry.

— Joshua

@Zack Istnieje wiele problemów z OTP, ale żaden nie zagraża poufności. Zauważ, że nawet jeśli doskonale odgadniesz klucz tekstowy + klucz poprzedniej wiadomości, następna wiadomość jest szyfrowana za pomocą zupełnie nowego, niezależnego klucza (również o znacznych rozmiarach). Po wielu interakcjach nie trzeba się dostosowywać.

4

W rzeczywistości nie jest to całkowicie bezpieczne. Wyciekiem protokołu jest DŁUGOŚĆ przekazywanej wiadomości.

Na przykład, jeśli szpieg wie, że odpowiesz „tak” lub „nie” i zobaczy długość = 2, może wydedukować to „nie”.

To naprawdę niesamowite, ile można wydedukować tylko ze znanych długości, jeśli można odgadnąć kontekst.

— w.pasman
źródło

3

Jest to dość łatwe do naprawienia, z rozsądnym poziomem bezpieczeństwa, ponieważ można wypełnić wiadomość losowymi śmieciami, więc długość wiadomości jest wielokrotnością o stałym rozmiarze bloku - powiedzmy 256 znaków. Pokonałoby to prostą analizę typu „tak” i „nie”, kosztem szybszego zużycia OTP.

— Peter Bagnall

Rzeczywiście - skoro można wysłać ~ 115kB codziennie przez następne 50 lat, można oczekiwać, że każdy blok będzie wynosić co najmniej 20kb, co oznacza długość nie jest tak ważne.

— apnorton