Jednorazowa podkładka - One-time pad

Format jednorazowego bloku używanego przez Agencję Bezpieczeństwa Narodowego USA o nazwie kodowej DIANA. Tabela po prawej stronie jest pomocą przy konwersji między tekstem jawnym a tekstem zaszyfrowanym przy użyciu znaków po lewej stronie jako klucza.

W kryptografii The szyfr z kluczem jednorazowym ( OTP ) jest szyfrowanie techniką, która nie może być pęknięty , ale wymaga użycia jednorazowego użytku wstępnie współdzielonego klucza , który jest nie mniejszy niż przesyłanej wiadomości. W tej technice tekst jawny jest łączony z losowym tajnym kluczem (nazywanym również jednorazowym padem ). Następnie każdy bit lub znak tekstu jawnego jest szyfrowany przez połączenie go z odpowiednim bitem lub znakiem z bloku przy użyciu dodawania modularnego .

Otrzymany tekst zaszyfrowany będzie niemożliwy do odszyfrowania lub złamania, jeśli zostaną spełnione następujące cztery warunki:

1. Klucz musi być losowy ( równomiernie rozłożony i niezależny od tekstu jawnego) i pobrany z niealgorytmicznego, chaotycznego źródła, takiego jak sprzętowy generator liczb losowych .
2. Klucz musi być co najmniej tak długi jak tekst jawny.
3. Klucza nie wolno używać ponownie w całości ani w części.
4. Klucz musi być całkowicie tajny przez strony komunikujące się.

Udowodniono również matematycznie, że każdy szyfr mający właściwość doskonałej tajemnicy musi używać kluczy spełniających te same wymagania, co klucze OTP. Cyfrowe wersje jednorazowych szyfrów pad są używane przez kraje do krytycznej komunikacji dyplomatycznej i wojskowej , ale problemy z bezpieczną dystrybucją kluczy sprawiają, że są one niepraktyczne w przypadku większości zastosowań.

Po raz pierwszy opisany przez Franka Millera w 1882 r., jednorazowy pad został ponownie wynaleziony w 1917 r. 22 lipca 1919 r. wydano patent US 1.310.719 na rzecz Gilberta Vernama na operację XOR używaną do szyfrowania jednorazowego padu. Wywodzący się z jego szyfru Vernama , system był szyfrem łączącym wiadomość z kluczem odczytanym z dziurkowanej taśmy . W swojej pierwotnej formie system Vernama był podatny na ataki, ponieważ kluczowa taśma była pętlą, która była ponownie używana za każdym razem, gdy pętla wykonywała pełny cykl. Jednorazowe użycie przyszło później, kiedy Joseph Mauborgne zdał sobie sprawę, że jeśli taśma klucza byłaby całkowicie losowa, kryptoanaliza byłaby niemożliwa.

Część nazwy „podkładka” pochodzi z wczesnych wdrożeń, w których kluczowy materiał był rozprowadzany w postaci bloku papieru, co pozwalało na oderwanie i zniszczenie obecnego górnego arkusza po użyciu. Do ukrycia podkładka była czasami tak mała, że do jej użycia potrzebne było potężne szkło powiększające . KGB używane klocki takiego rozmiaru, że mogą zmieścić się w dłoni lub w orzech powłoki. W celu zwiększenia bezpieczeństwa, bloczki jednorazowe były czasami drukowane na arkuszach z wysoce łatwopalnej nitrocelulozy , aby po użyciu można je było łatwo spalić.

Istnieje pewna niejednoznaczność terminu „szyfr Vernama”, ponieważ niektóre źródła używają zamiennie „szyfru Vernama” i „jednorazowego klucza”, podczas gdy inne odnoszą się do każdego addytywnego szyfru strumieniowego jako „szyfru Vernama”, w tym opartego na bezpiecznym kryptograficznie generator liczb pseudolosowych (CSPRNG).

Historia

Frank Miller w 1882 roku jako pierwszy opisał jednorazowy system nakładek do zabezpieczania telegrafii.

Następny jednorazowy system padów był elektryczny. W 1917 r. Gilbert Vernam (z AT&T Corporation ) wynalazł, a następnie opatentował w 1919 r. ( patent USA 1 310 719 ) szyfr oparty na technologii dalekopisu . Każdy znak w wiadomości był elektrycznie połączony ze znakiem na kluczu z dziurkowanej taśmy papierowej . Joseph Mauborgne (wówczas kapitanem w armii amerykańskiej , a później szef Korpusu Signal ) uznaje się, że sekwencja znaków na taśmie klucz może być zupełnie przypadkowe i że jeśli tak, cryptanalysis byłoby trudniejsze. Razem wynaleźli pierwszy jednorazowy system taśmowy.

Następnym osiągnięciem był system bloczków papierowych. Dyplomaci od dawna używali kodów i szyfrów, aby zachować poufność i zminimalizować koszty telegrafu . W przypadku kodów słowa i frazy zostały zamienione na grupy liczb (zazwyczaj 4 lub 5 cyfr) za pomocą słownika podobnego do książki kodów . W celu zwiększenia bezpieczeństwa, tajne numery można łączyć z (zwykle modułowym dodawaniem) każdą grupą kodów przed transmisją, przy czym tajne numery są okresowo zmieniane (nazywa się to superszyfrowaniem ). Na początku lat dwudziestych trzej niemieccy kryptografowie (Werner Kunze, Rudolf Schauffler i Erich Langlotz), którzy brali udział w łamaniu takich systemów, zdali sobie sprawę, że nigdy nie można ich złamać, jeśli dla każdej grupy kodu zostanie użyta osobna, losowo wybrana liczba dodatkowa. Mieli zduplikowane bloczki z wydrukowanymi liniami grup liczb losowych. Każda strona miała numer seryjny i osiem wierszy. Każda linia miała sześć 5-cyfrowych liczb. Strona byłaby używana jako arkusz roboczy do zakodowania wiadomości, a następnie zniszczona. Numer seryjny strony będą wysyłane z zakodowaną wiadomością. Odbiorca odwróciłby procedurę, a następnie zniszczył swoją kopię strony. Niemieckie Ministerstwo Spraw Zagranicznych wprowadziło ten system w życie do 1923 roku.

Osobnym pojęciem było użycie jednorazowego bloku liter do bezpośredniego kodowania tekstu jawnego, jak w poniższym przykładzie. Leo Marks opisuje wynalezienie takiego systemu dla brytyjskiego Dyrektora Operacji Specjalnych podczas II wojny światowej , choć podejrzewał w tym czasie, że był on już znany w bardzo podzielonym na sekcje świecie kryptografii, jak na przykład w Bletchley Park .

Ostatecznego odkrycia dokonał teoretyk informacji Claude Shannon w latach 40. XX wieku, który rozpoznał i udowodnił teoretyczne znaczenie systemu jednorazowych padów. Shannon przedstawił swoje wyniki w tajnym raporcie w 1945 r. i opublikował je otwarcie w 1949 r. W tym samym czasie sowiecki teoretyk informacji Władimir Kotelnikow niezależnie udowodnił absolutne bezpieczeństwo jednorazowego bloku; jego wyniki zostały dostarczone w 1941 r. w raporcie, który najwyraźniej pozostaje tajny.

Przykład

Załóżmy, że Alicja chce wysłać wiadomość hellodo Boba . Załóżmy, że dwa bloczki papieru zawierające identyczne losowe sekwencje liter zostały w jakiś sposób wcześniej wyprodukowane i bezpiecznie wydane obu. Alicja wybiera z bloczka odpowiednią nieużywaną stronę. Sposób wykonania tego zadania jest zwykle ustalany z wyprzedzeniem, na przykład „użyj 12. arkusza w dniu 1 maja” lub „użyj następnego dostępnego arkusza do następnej wiadomości”.

Materiał na wybranym arkuszu jest kluczem do tej wiadomości. Każda litera z bloczka zostanie połączona w określony sposób z jedną literą wiadomości. (Powszechnie, ale nie jest to wymagane, przypisywanie każdej literze wartości liczbowej , np. ato 0, bto 1 itd.)

W tym przykładzie technika polega na połączeniu klucza i wiadomości za pomocą dodawania modułowego (zasadniczo standardowego szyfru Vigenère'a ). Wartości liczbowe odpowiadającej wiadomości i liter kluczy są sumowane, modulo 26. Tak więc, jeśli materiał klucza zaczyna się od, XMCKLa wiadomość to hello, kodowanie odbywa się w następujący sposób:

      h       e       l       l       o  message
   7 (h)   4 (e)  11 (l)  11 (l)  14 (o) message
+ 23 (X)  12 (M)   2 (C)  10 (K)  11 (L) key
= 30      16      13      21      25     message + key
=  4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) (message + key) mod 26
      E       Q       N       V       Z  → ciphertext

Jeśli liczba jest większa niż 25, to reszta po odjęciu 26 jest brana w arytmetyce modularnej. Oznacza to po prostu, że jeśli obliczenia „przejdą” poza Z, sekwencja zaczyna się ponownie od A.

Zaszyfrowany tekst, który ma zostać wysłany do Boba, to EQNVZ. Bob używa pasującej strony klucza i tego samego procesu, ale w odwrotnej kolejności, aby uzyskać tekst jawny . Tutaj klucz jest odejmowany od zaszyfrowanego tekstu, ponownie używając arytmetyki modularnej:

       E       Q       N       V       Z  ciphertext
    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) ciphertext
−  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) key
= −19       4      11      11      14     ciphertext – key
=   7 (h)   4 (e)  11 (l)  11 (l)  14 (o) ciphertext – key (mod 26)
       h       e       l       l       o  → message

Podobnie jak powyżej, jeśli liczba jest ujemna, to dodawane jest 26, aby liczba wynosiła zero lub była wyższa.

W ten sposób Bob odzyskuje zwykły tekst Alicji, wiadomość hello. Zarówno Alicja, jak i Bob niszczą arkusz klucza natychmiast po użyciu, zapobiegając w ten sposób ponownemu użyciu i atakowi na szyfr. KGB często wydał agentom jednorazowe podkładki drukowane na maleńkich kartkach flash papier chemicznie konwertowane do nitrocelulozy , która spala się niemal natychmiast i nie pozostawia popiołu.

Klasyczny jednorazowy notatnik szpiegowski wykorzystywał rzeczywiste bloczki z malutkiego, łatwego do ukrycia papieru, ostrego ołówka i trochę arytmetyki mentalnej . Metodę można teraz wdrożyć jako program, używając plików danych jako danych wejściowych (tekst jawny), wyjściowych (tekst zaszyfrowany) i materiału klucza (wymagana kolejność losowa). Operacja wyłączności lub (XOR) jest często używana do łączenia tekstu jawnego i kluczowych elementów i jest szczególnie atrakcyjna na komputerach, ponieważ jest to zwykle natywna instrukcja maszynowa i dlatego jest bardzo szybka. Trudno jednak zapewnić, że kluczowy materiał jest w rzeczywistości przypadkowy, użyty tylko raz, nigdy nie zostanie ujawniony opozycji i zostanie całkowicie zniszczony po użyciu. Pomocnicze części implementacji jednorazowej podkładki programowej stanowią prawdziwe wyzwania: bezpieczna obsługa/transmisja tekstu jawnego, naprawdę losowe klucze i jednorazowe użycie klucza.

Próba kryptoanalizy

Kontynuując powyższy przykład, załóżmy, że Ewa przechwytuje zaszyfrowany tekst Alicji: EQNVZ. Gdyby Ewa miała nieskończony czas, odkryłaby, że klucz XMCKLwygeneruje tekst jawny hello, ale odkryje również, że klucz TQURIwygeneruje tekst jawny later, równie prawdopodobną wiadomość:

    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) ciphertext
−  19 (T)  16 (Q)  20 (U)  17 (R)   8 (I) possible key
= −15       0      −7       4      17     ciphertext-key
=  11 (l)   0 (a)  19 (t)   4 (e)  17 (r) ciphertext-key (mod 26)

W rzeczywistości możliwe jest "odszyfrowanie" z zaszyfrowanego tekstu dowolnej wiadomości o takiej samej liczbie znaków, po prostu za pomocą innego klucza, a w zaszyfrowanym tekście nie ma informacji, które pozwoliłyby Ewie wybrać spośród różnych możliwych odczytów. zaszyfrowanego tekstu.

Jeśli klucz nie jest naprawdę losowy, można użyć analizy statystycznej, aby określić, który z prawdopodobnych kluczy jest „najmniej” losowy, a zatem z większym prawdopodobieństwem będzie poprawny. Jeśli klucz zostanie ponownie użyty, będzie zauważalnie jedynym kluczem, który daje sensowne teksty jawne z obu szyfrogramów (szanse, że jakiś losowo niepoprawny klucz również da dwa sensowne teksty jawne, są bardzo małe).

Idealna tajemnica

Jednorazowe nakładki są „ informacyjnie bezpieczne ” w tym sensie, że zaszyfrowana wiadomość (tj. tekst zaszyfrowany ) nie dostarcza kryptoanalitykowi żadnych informacji o oryginalnej wiadomości (poza maksymalną możliwą długością wiadomości). Jest to bardzo silna koncepcja bezpieczeństwa, po raz pierwszy opracowana podczas II wojny światowej przez Claude'a Shannona i okazała się matematycznie prawdziwa dla jednorazowej podkładki Shannona mniej więcej w tym samym czasie. Jego wynik został opublikowany w Bell System Technical Journal w 1949 roku. Właściwie używane, jednorazowe nakładki są w tym sensie bezpieczne nawet przed przeciwnikami o nieskończonej mocy obliczeniowej.

Claude Shannon udowodnił, posługując się teorią informacji , że jednorazowy notatnik ma właściwość, którą nazwał doskonałą tajemnicą ; czyli tekst zaszyfrowany C nie daje absolutnie żadnych dodatkowych informacji o tekście jawnym . Dzieje się tak, ponieważ mając naprawdę losowy klucz, który jest używany tylko raz, tekst zaszyfrowany można przetłumaczyć na dowolny tekst jawny o tej samej długości i wszystkie są jednakowo prawdopodobne. Zatem prawdopodobieństwo a priori wiadomości w postaci tekstu jawnego M jest takie samo, jak prawdopodobieństwo a posteriori wiadomości w postaci tekstu jawnego M przy danym zaszyfrowanym tekście .

Matematycznie jest to wyrażone jako , gdzie jest entropią informacyjną tekstu jawnego i jest entropią warunkową tekstu jawnego dla tekstu zaszyfrowanego C . (Tutaj Η jest wielką grecką literą eta .) Oznacza to, że dla każdej wiadomości M i odpowiadającego jej zaszyfrowanego tekstu C musi istnieć co najmniej jeden klawisz K, który łączy je jako jednorazową blokadę. Matematycznie rzecz biorąc oznacza to , gdzie oznacza wyraźną ilość kluczy, szyfrów i wiadomości. Innymi słowy, jeśli musisz mieć możliwość przejścia z dowolnego zwykłego tekstu w przestrzeni wiadomości M do dowolnego szyfru w przestrzeni szyfrów C (szyfrowanie) oraz z dowolnego szyfru w przestrzeni szyfrowania C do zwykłego tekstu w przestrzeni wiadomości M (deszyfrowanie) , potrzebujesz co najmniej kluczy (wszystkie klucze używane z równym prawdopodobieństwem w celu zapewnienia doskonałej tajemnicy). ${\textstyle \mathrm {H} (M)=\mathrm {H} (M|C)}$${\textstyle \mathrm {H} (M)}$${\textstyle \mathrm {H} (M|C)}$${\textstyle K\geq C\geq M}$${\textstyle K,C,M}$${\displaystyle |M|=|C|}$${\displaystyle 1/|K|}$

Innym sposobem stwierdzające doskonałe utajnienie opiera się na założeniu, że dla wszystkich wiadomości w przestrzeni wiadomość M , a dla wszystkich szyfrów c na szyfr przestrzeni C , mamy , gdzie reprezentuje prawdopodobieństwo, przejęte wybór w przestrzeni kluczy ciągu rzutów monet z algorytmem probabilistycznym , . Doskonała tajemnica jest silnym pojęciem trudności kryptoanalitycznej. ${\displaystyle m_{1},m_{2}}$${\ Displaystyle {\ underset {k \ Leftarrow \ operatorname {K} {\ operatorname {Pr}}} [E_ {k} (m_ {1}) = c] = {\ underset {k \ Left Arrow \ operatorname {K } }{\nazwa operatora {Pr} }}[E_{k}(m_{2})=c]}$${\textstyle \operatorname {Pr} }$${\displaystyle k}$${\ Displaystyle \ operatorname {K}}$${\ Displaystyle E}$

Konwencjonalne algorytmy szyfrowania symetrycznego wykorzystują złożone wzorce podstawienia i transpozycji . Jeśli chodzi o najlepsze z obecnie używanych, nie wiadomo, czy istnieje procedura kryptoanalityczna, która może odwrócić (lub częściowo odwrócić ) te przekształcenia bez znajomości klucza używanego podczas szyfrowania. Algorytmy szyfrowania asymetrycznego opierają się na problemach matematycznych, które uważa się za trudne do rozwiązania, takich jak faktoryzacja liczb całkowitych i logarytmy dyskretne . Nie ma jednak dowodu na to, że problemy te są trudne, a matematyczny przełom może sprawić, że istniejące systemy będą podatne na ataki.

Dzięki doskonałej tajności, w przeciwieństwie do konwencjonalnego szyfrowania symetrycznego, OTP jest odporne nawet na ataki brute-force. Próba wszystkich kluczy daje po prostu wszystkie teksty jawne, wszystkie z równym prawdopodobieństwem będą rzeczywistym tekstem jawnym. Nawet przy znanym tekście jawnym, takim jak część wiadomości, nie można użyć ataków brute-force, ponieważ atakujący nie jest w stanie uzyskać żadnych informacji o częściach klucza potrzebnych do odszyfrowania reszty wiadomości. Części, które są znane, ujawnią tylko odpowiadające im części klucza i odpowiadają one ściśle jeden do jednego ; żadna część klucza nie jest zależna od żadnej innej części.

Peter Shor i inni wykazali, że komputery kwantowe są znacznie szybsze w rozwiązywaniu niektórych trudnych problemów, które zapewniają pewne bezpieczeństwo asymetrycznemu szyfrowaniu. Jeśli komputery kwantowe zostaną zbudowane z wystarczającą ilością kubitów i pokonają pewne ograniczenia w zakresie korekcji błędów, niektóre algorytmy kryptografii klucza publicznego staną się przestarzałe. Jednorazowe wkładki pozostaną jednak bezpieczne. Zobacz kryptografię kwantową i kryptografię post-kwantową, aby uzyskać dalsze omówienie wpływu komputerów kwantowych na bezpieczeństwo informacji.

Problemy

Pomimo dowodu Shannona na jego bezpieczeństwo, jednorazowa podkładka ma w praktyce poważne wady, ponieważ wymaga:

• Naprawdę losowe, w przeciwieństwie do pseudolosowych , jednorazowe wartości wypełnienia, co jest nietrywialnym wymogiem. Zobacz generator liczb pseudolosowych i generowanie liczb losowych .
  • Prawdziwe generatory liczb losowych istnieją, ale zazwyczaj są wolniejsze i bardziej wyspecjalizowane.
• Bezpieczne generowanie i wymiana jednorazowych wartości padów, które muszą być co najmniej tak długie jak wiadomość.
  • Bezpieczeństwo jednorazowego padu jest tylko tak bezpieczne, jak bezpieczeństwo jednorazowej wymiany padu, ponieważ jeśli atakujący jest w stanie przechwycić jednorazową wartość padu i wie, że jest to jednorazowy pad, może odszyfrować wiadomość jednorazowego padu.
• Staranne traktowanie, aby upewnić się, że jednorazowe wartości padów nadal pozostają tajne i są prawidłowo usuwane, zapobiegając ponownemu użyciu w całości lub w części – stąd „jednorazowe”. Zobacz remanencję danych, aby omówić trudności z całkowitym wymazaniem nośników komputerowych.

Jednorazowe pady rozwiązują kilka aktualnych praktycznych problemów w kryptografii. Szyfry wysokiej jakości są powszechnie dostępne, a ich bezpieczeństwo nie jest obecnie uważane za poważny problem. Takie szyfry są prawie zawsze łatwiejsze w użyciu niż jednorazowe podkładki; ilość materiału klucza, który musi być prawidłowo i bezpiecznie generowany, bezpiecznie dystrybuowany i bezpiecznie przechowywany, jest znacznie mniejsza, a kryptografia klucza publicznego rozwiązuje ten problem.

Prawdziwa losowość

Liczby losowe wysokiej jakości są trudne do wygenerowania. Funkcje generowania liczb losowych w większości bibliotek języka programowania nie nadają się do użytku kryptograficznego. Nawet te generatory, które nadają się do normalnego użytku kryptograficznego, w tym /dev/random i wiele sprzętowych generatorów liczb losowych , mogą w pewnym stopniu korzystać z funkcji kryptograficznych, których bezpieczeństwo nie zostało udowodnione. Przykładem tego, jak można osiągnąć prawdziwą losowość, jest pomiar emisji radioaktywnych .

W szczególności bezwzględnie konieczne jest jednorazowe użycie. Jeśli jednorazowa podkładka zostanie użyta tylko dwa razy, proste operacje matematyczne mogą zredukować ją do działającego szyfru klawiszowego . Na przykład, jeśli i reprezentują dwie różne wiadomości w postaci zwykłego tekstu i każda z nich jest zaszyfrowana wspólnym kluczem , to odpowiednie szyfrogramy są podawane przez: ${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle k}$

${\displaystyle c_{1}=p_{1}\oplus k}$

${\displaystyle c_{2}=p_{2}\oplus k}$

gdzie oznacza XOR . Jeśli atakujący byli mieć zarówno szyfrogramów i , po prostu biorąc XOR z i daje XOR dwóch plaintexts . (Dzieje się tak, ponieważ wzięcie XOR wspólnego klucza z samym sobą daje stały strumień bitów zer) . ${\ Displaystyle \ oplus}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle p_{1}\oplus p_{2}}$${\displaystyle k}$${\displaystyle p_{1}\oplus p_{2}}$

Jeśli oba teksty jawne są w języku naturalnym (np. angielskim lub rosyjskim), to mimo że oba są tajne, każdy z nich ma bardzo dużą szansę na odzyskanie przez kryptoanalizę heurystyczną , z możliwymi kilkoma niejasnościami. Oczywiście dłuższą wiadomość można przerwać tylko dla części, która nakłada się na krótszą wiadomość, a także może trochę więcej, uzupełniając słowo lub frazę. Najsłynniejszy exploit wykorzystujący tę lukę miał miejsce w projekcie Venona .

Dystrybucja kluczy

Ponieważ pad, podobnie jak wszystkie wspólne sekrety , musi być przekazywany i przechowywany w bezpiecznym miejscu, a pad musi być co najmniej tak długi, jak wiadomość, często nie ma sensu używać jednorazowego dopełnienia, ponieważ można po prostu wysłać zwykły tekst zamiast podkładki (ponieważ oba mogą mieć ten sam rozmiar i muszą być bezpiecznie wysłane). Jednak po bezpiecznym wysłaniu bardzo długiej nakładki (np. dysku komputera pełnego losowych danych), można jej użyć do wielu przyszłych wiadomości, dopóki suma ich rozmiarów nie zrówna się z rozmiarem nakładki. Dystrybucja kluczy kwantowych również proponuje rozwiązanie tego problemu, przy założeniu, że komputery kwantowe są odporne na awarie .

Dystrybucja bardzo długich, jednorazowych kluczy do padów jest niewygodna i zwykle stanowi poważne zagrożenie bezpieczeństwa. Pad jest zasadniczo kluczem szyfrującym, ale w przeciwieństwie do kluczy do nowoczesnych szyfrów, musi być bardzo długi i jest zbyt trudny do zapamiętania dla ludzi. Nośniki pamięci, takie jak pendrive , DVD-R lub osobiste cyfrowe odtwarzacze audio, mogą być używane do przenoszenia bardzo dużego jednorazowego pada z miejsca na miejsce w sposób nie budzący podejrzeń, ale mimo to konieczność fizycznego transportu pada jest obciążenie w porównaniu z protokołami negocjacji klucza nowoczesnego kryptosystemu z kluczem publicznym, a takie nośniki nie mogą być bezpiecznie usunięte w żaden sposób, poza fizycznym zniszczeniem (np. spaleniem). 4,7 PL DVD-R pełen danych jednorazowej pieluchy, jeśli rozdrabnia się cząstek 1 mm ² (0,0016 cali kwadratowych) w wielkości, pozostawia w ciągu 4 megabitów na (wprawdzie trudne do odzyskania, a nie niemożliwie SO) danych na każdej cząstce . Ponadto ryzyko popełnienia kompromitacji podczas transportu (na przykład przeciągnięcia przez kieszonkowca , skopiowania i wymiany bloczka) jest w praktyce znacznie większe niż prawdopodobieństwo popełnienia kompromitacji w przypadku szyfru takiego jak AES . Wreszcie, wysiłek potrzebny do zarządzania jednorazowymi kluczami masowymi bardzo źle w przypadku dużych sieci komunikatorów — liczba wymaganych nakładek rośnie wraz z kwadratem liczby użytkowników swobodnie wymieniających wiadomości. W przypadku komunikacji między dwiema osobami lub topologii sieci gwiazdowej jest to mniejszy problem.

Materiał klucza należy bezpiecznie usunąć po użyciu, aby zapewnić, że materiał klucza nigdy nie zostanie ponownie wykorzystany i aby chronić wysyłane wiadomości. Ponieważ materiał klucza musi być transportowany z jednego punktu końcowego do drugiego i trwać do momentu wysłania lub odebrania wiadomości, może być bardziej podatny na odzyskiwanie śledcze niż przejściowy tekst jawny, który chroni (patrz remanencja danych ).

Uwierzytelnianie

Zgodnie z tradycją, jednorazowe pady nie zapewniają uwierzytelniania wiadomości , którego brak może stanowić zagrożenie bezpieczeństwa w systemach w świecie rzeczywistym. Na przykład osoba atakująca, która wie, że wiadomość zawiera „spotkajmy się z Jane i ze mną jutro o piętnastej trzydzieści” może wyprowadzić odpowiednie kody pada bezpośrednio z dwóch znanych elementów (zaszyfrowanego tekstu i znanego tekstu jawnego). Atakujący może następnie zastąpić ten tekst dowolnym innym tekstem o dokładnie tej samej długości, na przykład „trzy trzydzieści spotkanie zostało odwołane, zostań w domu”. Wiedza osoby atakującej o jednorazowej wkładce jest ograniczona do tej długości bajtów, którą należy zachować, aby jakakolwiek inna zawartość wiadomości pozostała ważna. Różni się to nieco od plastyczności, w której niekoniecznie przyjmuje się, że znany jest tekst jawny. Zobacz także atak szyfrem strumieniowym .

Aby zapobiec takim atakom, można zastosować standardowe techniki, takie jak użycie kodu uwierzytelniania wiadomości, wraz z systemem jednorazowych padów, podobnie jak metody klasyczne, takie jak dopełnienie o zmiennej długości i kopulacja rosyjska , ale wszystkie nie mają idealnego bezpieczeństwo, jakie ma samo OTP. Uniwersalne mieszanie zapewnia sposób uwierzytelniania wiadomości aż do arbitralnego ograniczenia bezpieczeństwa (tj. dla dowolnego p > 0 , wystarczająco duży skrót zapewnia, że ​​nawet nieograniczony obliczeniowo prawdopodobieństwo udanego fałszerstwa jest mniejsze niż p ), ale to wykorzystuje dodatkowe dane losowe z podkładki i usuwa możliwość realizacji systemu bez komputera.

Częste błędy w implementacji

Ze względu na względną prostotę implementacji i obietnicę doskonałej poufności, jednorazowy pad cieszy się dużą popularnością wśród studentów uczących się kryptografii, zwłaszcza że jest to często pierwszy algorytm prezentowany i implementowany podczas kursu. Niestety implementacje często łamią wymagania dotyczące teoretycznego bezpieczeństwa informacji na jeden lub więcej sposobów:

• Pad jest generowany przez pewien algorytm, który rozszerza jedną lub więcej małych wartości do dłuższego „jednorazowego padu”. Dotyczy to w równym stopniu wszystkich algorytmów, od całkowicie niezabezpieczonych podstawowych operacji matematycznych, takich jak rozwinięcia dziesiętne pierwiastka kwadratowego, po złożone, kryptograficznie bezpieczne generatory liczb losowych (CSPRNG). Żadna z tych implementacji nie jest jednorazowymi nakładkami, ale z definicji szyframi strumieniowymi . Wszystkie jednorazowe pady muszą być generowane w procesie niealgorytmicznym, np. przez sprzętowy generator liczb losowych .

• Wymiana wkładki odbywa się w sposób nieinformacyjny teoretycznie bezpieczny. Jeśli jednorazowy pad jest zaszyfrowany teoretycznie bezpiecznym algorytmem nie zawierającym informacji, bezpieczeństwo kryptosystemu jest tak bezpieczne, jak najsłabsze ogniwo kryptosystemu. Typowym mechanizmem nieprawidłowego dostarczania dla jednorazowej podkładki jest standardowy hybrydowy system kryptograficzny, który opiera się na kryptografii klucza symetrycznego do szyfrowania podkładki i kryptografii asymetrycznej do dostarczania klucza symetrycznego. Prawidłowe metody jednorazowej dostawy padów to przede wszystkim dystrybucja kluczy Quantum , usługa Sneakernet lub Courier lub Dead drop .

• Implementacja nie zawiera bezwarunkowo bezpiecznego mechanizmu uwierzytelniania, takiego jak jednorazowy MAC .

• Podkładka jest ponownie używana (patrz projekt Venona )

• Podkładka nie ulega zniszczeniu natychmiast po użyciu.

Zastosowania

Zastosowanie

Pomimo swoich problemów jednorazowy pad zachowuje pewne praktyczne zainteresowanie. W niektórych hipotetycznych sytuacjach szpiegowskich jednorazowy notatnik może być przydatny, ponieważ można go obliczyć ręcznie, używając tylko ołówka i papieru. Rzeczywiście, prawie wszystkie inne szyfry wysokiej jakości są całkowicie niepraktyczne bez komputerów. Jednak we współczesnym świecie komputery (takie jak te wbudowane w osobiste urządzenia elektroniczne, takie jak telefony komórkowe ) są tak wszechobecne, że posiadanie komputera odpowiedniego do wykonywania konwencjonalnego szyfrowania (na przykład telefonu, na którym można uruchomić ukryte oprogramowanie kryptograficzne) zwykle nie wzbudzić podejrzenia.

• Jednorazowy pad to optymalny kryptosystem z teoretycznie idealną tajemnicą.
• Jednorazowa klawiatura jest jedną z najbardziej praktycznych metod szyfrowania, w której jedna lub obie strony muszą wykonywać wszystkie czynności ręcznie, bez pomocy komputera. To sprawiło, że stało się to ważne w erze przed komputerami i prawdopodobnie nadal może być przydatne w sytuacjach, w których posiadanie komputera jest nielegalne lub obciążające lub gdy godne zaufania komputery nie są dostępne.
• Jednorazowe pady są praktyczne w sytuacjach, gdy dwie strony w bezpiecznym środowisku muszą być w stanie odejść od siebie i komunikować się z dwóch oddzielnych bezpiecznych środowisk z zachowaniem doskonałej tajemnicy.
• Jednorazowy pad może być używany w superszyfrowaniu .
• Algorytm najczęściej kojarzony z dystrybucją klucza kwantowego to jednorazowa podkładka.
• Jednorazowy pad jest naśladowany przez szyfry strumieniowe .
• Jednorazowy pad może być częścią wprowadzenia do kryptografii.

zastosowania historyczne

Jednorazowe ochraniacze były używane w szczególnych okolicznościach od początku XX wieku. W 1923 r. został zatrudniony do komunikacji dyplomatycznej przez niemiecki establishment dyplomatyczny. Republika Weimarska Służby Dyplomatycznej zaczął się metodą około 1920. łamaniu słabej Radzieckiego kryptografii przez Brytyjczyków , z wiadomości upublicznione ze względów politycznych w obu przypadkach w 1920 roku ( case ARCOS ), wydaje się, że indukowane Związek Radziecki do przyjęcia jednorazowe podkładki do niektórych celów około 1930 r. Wiadomo również, że szpiedzy KGB ostatnio używali jednorazowych podkładek ołówkowych i papierowych. Przykładami są pułkownik Rudolf Abel , który został aresztowany i skazany w Nowym Jorku w latach pięćdziesiątych, oraz „Krogers” (tj. Morris i Lona Cohen ), których aresztowano i skazano za szpiegostwo w Wielkiej Brytanii na początku lat sześćdziesiątych. Obaj znaleziono z fizycznymi jednorazowymi podkładkami w ich posiadaniu.

Wiele krajów korzystało z jednorazowych systemów padów do obsługi wrażliwego ruchu. Leo Marks donosi, że brytyjski Special Operations Executive używał jednorazowych padów podczas II wojny światowej do kodowania ruchu między swoimi biurami. Jednorazowe podpaski do użytku z zagranicznymi agentami zostały wprowadzone pod koniec wojny. Kilka brytyjskich jednorazowych maszyn szyfrujących taśmę to Rockex i Noreen . Niemiecka maszyna Stasi Sprach była również w stanie wykorzystać jednorazową taśmę, z której korzystały Niemcy Wschodnie, Rosja, a nawet Kuba do wysyłania zaszyfrowanych wiadomości do swoich agentów.

II wojny światowej głos skrambler SIGSALY był również formą systemu jednorazowej. Dodawał szum do sygnału na jednym końcu i usuwał go z drugiego końca. Szum był rozprowadzany na końcach kanałów w postaci dużych płyt szelakowych, które zostały wyprodukowane w unikalnych parach. Pojawiły się zarówno problemy z początkową synchronizacją, jak i długoterminowymi problemami dryfu fazowego, które pojawiły się i zostały rozwiązane, zanim system mógł być używany.

Hotline między Moskwie i Waszyngtonie , założona w 1963 roku po 1962 kryzysu kubańskiego , używane dalekopisy chronione przez komercyjnego systemu taśmowego jednorazowej. Każdy kraj przygotował taśmy-klucze używane do zakodowania swoich wiadomości i dostarczył je za pośrednictwem swojej ambasady w drugim kraju. Unikalną zaletą OTP w tym przypadku było to, że żaden kraj nie musiał ujawniać drugiemu bardziej wrażliwych metod szyfrowania.

US Army Special Forces używało jednorazowych ochraniaczy w Wietnamie. Używając kodu Morse'a z jednorazowymi padami i ciągłej transmisji radiowej (nośnik kodu Morse'a), osiągnęli zarówno tajność, jak i niezawodną komunikację.

Podczas inwazji Grenady w 1983 r. siły amerykańskie znalazły w kubańskim magazynie parę jednorazowych zeszytów.

Począwszy od 1988 roku, Afrykański Kongres Narodowy (ANC) używał jednorazowych podkładek dyskowych jako części bezpiecznego systemu komunikacji między przywódcami ANC spoza Republiki Południowej Afryki a krajowymi agentami w ramach operacji Vula, udanej próby zbudowania ruchu oporu sieć w Republice Południowej Afryki. Losowe liczby na dysku zostały wymazane po użyciu. Stewardessa belgijskiej linii lotniczej działała jako kurier przynosząc dyskietki. Potrzebne było regularne uzupełnianie nowych dysków, ponieważ dość szybko się zużywały. Jednym z problemów z systemem było to, że nie można go było używać do bezpiecznego przechowywania danych. Później Vula dodał szyfr strumieniowy kluczowany kodami książkowymi, aby rozwiązać ten problem.

Pokrewnym pojęciem jest kod jednorazowy — sygnał użyty tylko raz; np. „Alfa” dla „misja zakończona”, „Bravo” dla „misji nieudane” lub nawet „Pochodnia” dla „ alianckiej inwazji na francuską Afrykę Północną ” nie mogą być „odszyfrowane” w żadnym sensownym znaczeniu tego słowa. Zrozumienie komunikatu będzie wymagało dodatkowych informacji, często „głębokości” powtórek lub analizy ruchu . Jednak takie strategie (choć często używane przez prawdziwych agentów i trenerów baseballu ) nie są jednorazowym podkładem kryptograficznym w żadnym znaczącym sensie.

NSA

Przynajmniej do lat 70. Amerykańska Agencja Bezpieczeństwa Narodowego (NSA) wyprodukowała różne ręczne jednorazowe podkładki, zarówno ogólnego przeznaczenia, jak i specjalistyczne, z 86 000 jednorazowych podkładek wyprodukowanych w roku podatkowym 1972. Specjalne podkładki zostały wyprodukowane dla tego, co NSA zwane systemami „pro forma”, gdzie „podstawowe ramy, forma lub format każdego tekstu wiadomości są identyczne lub prawie takie same; ten sam rodzaj informacji, wiadomość po wiadomości, ma być prezentowana w tej samej kolejności, a tylko określone wartości, takie jak liczby, zmieniają się z każdą wiadomością.” Przykłady obejmowały wiadomości o wystrzeleniu nuklearnym i raporty dotyczące radionawigacji (COMUS).

Bloki ogólnego przeznaczenia produkowane były w kilku formatach, prosta lista losowych liter (DIANA) lub samych cyfr (CALYPSO), malutkie podkładki dla tajnych agentów (MYSZKA MIKI) oraz bloki przeznaczone do szybszego kodowania krótkich wiadomości, kosztem mniejsza gęstość. Jeden przykład, ORION, miał po jednej stronie 50 rzędów alfabetów tekstu jawnego, a po drugiej odpowiadające im litery tekstu zaszyfrowanego. Umieszczając arkusz na kawałku kalki z kalką do góry, można zakreślić jedną literę w każdym rzędzie z jednej strony, a odpowiadającą literę z drugiej strony zakreślić kalką. W ten sposób jeden arkusz ORION mógł szybko zakodować lub zdekodować wiadomość o długości do 50 znaków. Produkcja bloków ORION wymagała drukowania obu stron z dokładnym pasowaniem, co było trudnym procesem, dlatego NSA przeszła na inny format bloku, MEDEA, z 25 rzędami sparowanych alfabetów i przypadkowych znaków. ( Patrz Commons:Category:NSA jednorazowe klocki dla ilustracji.)

NSA zbudowała również zautomatyzowane systemy dla „scentralizowanej siedziby jednostek CIA i sił specjalnych, tak aby mogły efektywnie przetwarzać wiele oddzielnych, jednorazowych komunikatów padów do i od poszczególnych posiadaczy padów w terenie”.

Podczas II wojny światowej i do lat 50. Stany Zjednoczone intensywnie korzystały z jednorazowych systemów taśmowych. Oprócz zapewnienia poufności, obwody zabezpieczone jednorazową taśmą działały nieprzerwanie, nawet gdy nie było ruchu, chroniąc w ten sposób przed analizą ruchu . W 1955 r. NSA wyprodukowała około 1 660 000 rolek jednorazowej taśmy. Każda rolka miała średnicę 8 cali, zawierała 100 000 znaków, trwała 166 minut i kosztowała 4,55 USD. Do 1972 roku wyprodukowano zaledwie 55 000 rolek, ponieważ jednorazowe taśmy zostały zastąpione maszynami wirnikowymi, takimi jak SIGTOT, a później urządzeniami elektronicznymi opartymi na rejestrach przesuwnych . NSA opisuje jednorazowe systemy taśmowe, takie jak 5-UCO i SIGTOT, jako używane do ruchu wywiadowczego do czasu wprowadzenia elektronicznego szyfru KW-26 w 1957 roku.

Exploity

Podczas gdy jednorazowe pady zapewniają idealną tajemnicę, jeśli są odpowiednio generowane i używane, małe błędy mogą prowadzić do udanej kryptoanalizy:

• W latach 1944-1945 The US Army „s Signals Intelligence Obsługa była w stanie rozwiązać system szyfr z kluczem jednorazowym używany przez niemieckiego MSZ dla jego ruchu na wysokim poziomie, o nazwie kodowej GEE. GEE było niepewne, ponieważ pady nie były wystarczająco losowe — maszyna używana do generowania padów dawała przewidywalny wynik.
• W 1945 roku Stany Zjednoczone odkryły, że wiadomości Canberra – Moskwa były szyfrowane najpierw za pomocą książki kodów, a następnie za pomocą jednorazowego pada. Jednak używany jednorazowo pad był tym samym, którego używa Moskwa do wiadomości Waszyngton, DC – Moskwa. W połączeniu z faktem, że niektóre wiadomości Canberra–Moskwa zawierały znane dokumenty rządu brytyjskiego, pozwoliło to na złamanie niektórych zaszyfrowanych wiadomości.
• Jednorazowe podkładki były wykorzystywane przez sowieckie agencje szpiegowskie do tajnej komunikacji z agentami i kontrolerami agentów. Analiza wykazała, że ​​bloki te zostały wygenerowane przez maszynistki przy użyciu rzeczywistych maszyn do pisania. Ta metoda nie jest oczywiście naprawdę losowa, ponieważ sprawia, że ​​pewne dogodne sekwencje klawiszy są bardziej prawdopodobne niż inne, jednak okazała się ogólnie skuteczna, ponieważ chociaż dana osoba nie tworzy naprawdę losowych sekwencji, w równym stopniu nie przestrzega tego samego rodzaju ustrukturyzowanych reguł matematycznych że maszyna też by to zrobiła, a każda osoba generuje szyfry w inny sposób, co utrudnia atakowanie każdej wiadomości. Bez kopii użytego materiału klucza tylko niektóre defekty w metodzie generowania lub ponownego użycia kluczy dawały dużą nadzieję na kryptoanalizę. Począwszy od późnych lat 40. amerykańskie i brytyjskie agencje wywiadowcze były w stanie przerwać część sowieckiego jednorazowego ruchu padów do Moskwy podczas II wojny światowej w wyniku błędów popełnionych w generowaniu i dystrybucji kluczowego materiału. Jedną z sugestii jest to, że personel Centrum Moskiewskiego był nieco pospieszony obecnością wojsk niemieckich tuż pod Moskwą pod koniec 1941 i na początku 1942 roku i w tym okresie wyprodukowali więcej niż jedną kopię tego samego kluczowego materiału. Ten trwający od dziesięcioleci wysiłek został ostatecznie nazwany kryptonimem VENONA (BRIDE to wcześniejsza nazwa); przyniosła znaczną ilość informacji. Mimo to tylko niewielki procent przechwyconych wiadomości został całkowicie lub częściowo odszyfrowany (kilka tysięcy z kilkuset tysięcy).
• Systemy taśm jednorazowych używane w USA wykorzystywały miksery elektromechaniczne do łączenia fragmentów wiadomości i taśmy jednorazowej. Miksery te emitowały znaczną energię elektromagnetyczną, którą przeciwnik mógł odebrać w pewnej odległości od sprzętu szyfrującego. Ten efekt, po raz pierwszy zauważony przez Bell Labs podczas II wojny światowej, może umożliwić przechwytywanie i odzyskiwanie tekstu jawnego przesyłanych wiadomości, lukę o nazwie kodowej Tempest .

Zobacz też

Uwagi

Bibliografia

Dalsza lektura

Zewnętrzne linki

• Szczegółowy opis i historia One-Time Pad z przykładami i obrazami na temat maszyn szyfrujących i kryptologii
• W FreeS / WAN słowniczek wpis z omówieniem słabości OTP