Kryptoanaliza - Cryptanalysis

Zbliżenie wirników w maszynie szyfrującej Fialka

Kryptoanaliza (od greckiego kryptós , „ukryte” i analýein , „analizować”) odnosi się do procesu analizy systemów informatycznych w celu zrozumienia ukrytych aspektów systemów. Kryptoanaliza służy do naruszania kryptograficznych systemów bezpieczeństwa i uzyskiwania dostępu do zawartości zaszyfrowanych wiadomości, nawet jeśli klucz kryptograficzny jest nieznany.

Oprócz analizy matematycznej algorytmów kryptograficznych, kryptoanaliza obejmuje badanie ataków kanałem bocznym , które nie są ukierunkowane na słabości samych algorytmów kryptograficznych, ale wykorzystują słabości w ich implementacji.

Chociaż cel był ten sam, metody i techniki kryptoanalizy zmieniły się drastycznie w historii kryptografii, dostosowując się do rosnącej złożoności kryptograficznej, począwszy od metod pióra i papieru z przeszłości, poprzez maszyny takie jak brytyjskie bomby i Komputery Colossus w Bletchley Park w czasie II wojny światowej , do matematycznie zaawansowanych skomputeryzowanych schematów współczesności. Metody łamania współczesnych kryptosystemów często obejmują rozwiązywanie starannie skonstruowanych problemów w czystej matematyce , z których najbardziej znanym jest faktoryzacja liczb całkowitych .

Przegląd

Biorąc pod uwagę niektóre zaszyfrowanych danych ( zaszyfrowany ), przy czym celem kryptoanalityk jest zdobycie jak najwięcej informacji, jak to możliwe o oryginale, dane niekodowane ( zwykłego tekstu ). Ataki kryptograficzne można scharakteryzować na kilka sposobów:

Ilość informacji dostępnych dla atakującego

Ataki mogą być klasyfikowane na podstawie rodzaju informacji dostępnych dla atakującego. Jako podstawowy punkt wyjścia przyjmuje się zwykle, że do celów analizy znany jest ogólny algorytm ; to maksyma Shannona „wróg zna system” — z kolei odpowiednik zasady Kerckhoffsa . W praktyce jest to rozsądne założenie — na przestrzeni dziejów istnieją niezliczone przykłady tajnych algorytmów wchodzących w szerszą wiedzę, na różne sposoby poprzez szpiegostwo , zdradę i inżynierię wsteczną . (Czasami szyfry zostały złamane przez czystą dedukcję; na przykład niemiecki szyfr Lorenza i japoński kod Purple oraz różne klasyczne schematy):

Wymagane zasoby obliczeniowe

Ataki mogą również charakteryzować się wymaganymi zasobami. Zasoby te obejmują:

  • Czas — liczba kroków obliczeniowych (np. szyfrowanie testowe), które należy wykonać.
  • Pamięć — ilość pamięci wymagana do wykonania ataku.
  • Dane — ilość i rodzaj tekstów jawnych i tekstów zaszyfrowanych wymaganych dla określonego podejścia.

Czasami trudno jest dokładnie przewidzieć te ilości, zwłaszcza gdy atak nie jest praktyczny do faktycznego zaimplementowania do testowania. Ale kryptoanalitycy akademiccy mają tendencję do podawania przynajmniej szacowanego rzędu wielkości trudności swoich ataków, mówiąc na przykład: „Kolizje SHA-1 są teraz 2 52 ”.

Bruce Schneier zauważa, że ​​nawet niepraktyczne obliczeniowo ataki można uznać za złamane: „Złamanie szyfru oznacza po prostu znalezienie w nim słabości, którą można wykorzystać w sposób mniej skomplikowany niż brutalna siła. Nieważne, że brutalna siła może wymagać 2 128 szyfrowań; atak wymagający 2 110 szyfrowań zostałby uznany za złamanie… po prostu złamanie może być po prostu słabością certyfikacji: dowodem na to, że szyfr nie działa zgodnie z reklamą”.

Częściowe przerwy

Wyniki kryptoanalizy mogą również różnić się użytecznością. Na przykład kryptograf Lars Knudsen (1998) sklasyfikował różne rodzaje ataków na szyfry blokowe według ilości i jakości odkrytych tajnych informacji:

  • Całkowite złamanie — atakujący wyprowadza tajny klucz .
  • Dedukcja globalna — atakujący odkrywa funkcjonalnie równoważny algorytm szyfrowania i deszyfrowania, ale bez uczenia się klucza.
  • Dedukcja instancji (lokalna) — atakujący odkrywa dodatkowe teksty jawne (lub szyfrogramy), które wcześniej nie były znane.
  • Dedukcja informacji — atakujący uzyskuje informacje Shannona o nieznanych wcześniej tekstach jawnych (lub szyfrogramach).
  • Algorytm odróżniający — atakujący może odróżnić szyfr od przypadkowej permutacji .

Ataki akademickie są często skierowane przeciwko osłabionym wersjom kryptosystemu, takim jak szyfr blokowy lub funkcja skrótu z usuniętymi niektórymi rundami. Wiele, ale nie wszystkie ataki stają się wykładniczo trudniejsze do wykonania, gdy rundy są dodawane do kryptosystemu, więc możliwe jest, że pełny kryptosystem będzie silny, nawet jeśli warianty o ograniczonej rundzie są słabe. Niemniej jednak częściowe przerwy, które zbliżają się do złamania oryginalnego kryptosystemu, mogą oznaczać, że nastąpi pełne złamanie; udane ataki na DES , MD5 i SHA-1 zostały poprzedzone atakami na osłabione wersje.

W kryptografii akademickiej słabość lub przerwa w schemacie jest zwykle definiowana dość konserwatywnie: może wymagać niepraktycznej ilości czasu, pamięci lub znanych tekstów jawnych. Może to również wymagać, aby atakujący był w stanie zrobić rzeczy, których wielu atakujących w świecie rzeczywistym nie jest w stanie: na przykład atakujący może potrzebować wybrać określone teksty jawne do zaszyfrowania lub nawet poprosić o zaszyfrowanie tekstu jawnego za pomocą kilku kluczy powiązanych z sekretem klucz. Co więcej, może ujawnić tylko niewielką ilość informacji, wystarczającą do udowodnienia niedoskonałości kryptosystemu, ale zbyt małą, aby była użyteczna dla atakujących w świecie rzeczywistym. Wreszcie, atak może dotyczyć tylko osłabionej wersji narzędzi kryptograficznych, takich jak szyfr ze skróconym blokiem, jako krok w kierunku złamania całego systemu.

Historia

Kryptoanaliza ewoluowała razem z kryptografią, a konkurs można prześledzić w historii kryptografii — nowe szyfry są projektowane w celu zastąpienia starych uszkodzonych projektów i nowe techniki kryptoanalityczne wymyślone w celu złamania ulepszonych schematów. W praktyce są one postrzegane jako dwie strony tego samego medalu: bezpieczna kryptografia wymaga zaprojektowania przed ewentualną kryptoanalizą.

Szyfry klasyczne

Pierwsza strona IX-wiecznego rękopisu Al-Kindiego o rozszyfrowywaniu wiadomości kryptograficznych

Chociaż samo słowo „ kryptoanaliza ” jest stosunkowo nowe (wymyślone przez Williama Friedmana w 1920 r.), metody łamania kodów i szyfrów są znacznie starsze. David Kahn zauważa w The Codebreakers, że arabscy ​​uczeni byli pierwszymi ludźmi, którzy systematycznie dokumentowali metody kryptoanalityczne.

Pierwsze znane nagrane wyjaśnienie kryptoanalizy zostało podane przez Al-Kindi (ok. 801–873, znanego również jako „Alkindus” w Europie), IX-wiecznego arabskiego politologa , w Risalah fi Istikhraj al-Mu'amma ( Rękopis na Odszyfrowywanie wiadomości kryptograficznych ). Niniejszy traktat zawiera pierwszy opis metody analizy częstotliwości . Al-Kindi jest zatem uważany za pierwszego łamacza kodów w historii. Na jego przełomową pracę wpłynął Al-Khalil (717–786), który napisał Księgę wiadomości kryptograficznych , w której po raz pierwszy zastosowano permutacje i kombinacje, aby wymienić wszystkie możliwe słowa arabskie z samogłoskami i bez.

Analiza częstotliwościowa jest podstawowym narzędziem do łamania większości klasycznych szyfrów . W językach naturalnych niektóre litery alfabetu pojawiają się częściej niż inne; w języku angielskimE ” jest prawdopodobnie najczęstszą literą w dowolnej próbce tekstu jawnego . Podobnie dwuznak „TH” jest najbardziej prawdopodobną parą liter w języku angielskim i tak dalej. Analiza częstotliwości polega na tym, że szyfr nie potrafi ukryć tych statystyk . Na przykład, w prostym szyfrze podstawieniowym (gdzie każda litera jest po prostu zastępowana inną), najczęstsza litera w szyfrogramie byłaby prawdopodobną kandydatką na „E”. Analiza częstotliwości takiego szyfru jest zatem stosunkowo łatwa, pod warunkiem, że zaszyfrowany tekst jest wystarczająco długi, aby dać dość reprezentatywną liczbę zawartych w nim liter alfabetu.

Wynalezienie przez Al-Kindi techniki analizy częstotliwości do łamania monoalfabetycznych szyfrów podstawienia było największym postępem w kryptoanalityce przed II wojną światową. Risalah fi Istikhraj al-Mu'amma Al-Kindi opisał pierwsze techniki kryptoanalityczne, w tym niektóre dla szyfrów polialfabetycznych , klasyfikacji szyfrów, arabskiej fonetyki i składni, a co najważniejsze, przedstawił pierwsze opisy dotyczące analizy częstotliwości. Zajmował się również metodami szyfrowania, kryptoanalizą niektórych szyfrów oraz analizą statystyczną liter i kombinacji liter w języku arabskim. Ważny wkład Ibn Adlana (1187-1268) dotyczył wielkości próby do wykorzystania analizy częstotliwości.

W Europie włoski uczony Giambattista della Porta (1535-1615) był autorem przełomowego dzieła o kryptoanalizie, De Furtivis Literarum Notis .

Udana kryptoanaliza niewątpliwie wpłynęła na historię; umiejętność odczytywania rzekomo tajnych myśli i planów innych może być decydującą zaletą. Na przykład w Anglii w 1587 roku, Maria I Stuart został osądzony i stracony za zdradę w związku z jej zaangażowaniem w trzech działek zamachu Elżbieta I Tudor . Plany wyszły na jaw po tym, jak Thomas Phelippes rozszyfrował jej zaszyfrowaną korespondencję z innymi spiskowcami .

W Europie w XV i XVI wieku ideę polialfabetycznego szyfru podstawieniowego rozwinął m.in. francuski dyplomata Blaise de Vigenère (1523–96). Przez około trzy stulecia szyfr Vigenère'a , który używa powtarzalnego klucza do wyboru różnych alfabetów szyfrujących naprzemiennie , był uważany za całkowicie bezpieczny ( le chiffre indéchiffrable — „szyfr nieczytelny”). Niemniej jednak Charles Babbage (1791–1871), a później, niezależnie, Friedrich Kasiski (1805–81), zdołali złamać ten szyfr. Podczas I wojny światowej , wynalazcy w kilku krajach opracowano wirnika maszyny szyfr , takich jak Artur Scherbius ' Enigma , w celu zminimalizowania powtarzania, które zostały wykorzystane do złamania systemu Vigenère.

Szyfry z I i II wojny światowej

Odszyfrowany telegram Zimmermanna .

W czasie I wojny światowej złamanie Telegramu Zimmermanna odegrało kluczową rolę we wciągnięciu Stanów Zjednoczonych do wojny. W II wojnie światowej , gdy alianci skorzystała ogromnie ze wspólnego sukcesu kryptoanalizy szyfrów niemieckich - w tym Enigmy i szyfru Lorenz - i japońskich szyfrów, szczególnie „Purple” i JN-25 . „Ultra” inteligencję przypisuje się wszystkim od skrócenia końca europejskiej wojny nawet o dwa lata do ostatecznego wyniku. Wojnie na Pacyfiku w podobny sposób pomogła „Magiczna” inteligencja.

Kryptoanaliza wiadomości wroga odegrała znaczącą rolę w zwycięstwie aliantów w II wojnie światowej. FW Winterbotham , cytując zachodniego Naczelnego Dowódcę alianckich, Dwighta D. Eisenhowera , pod koniec wojny opisał ultrainteligentną inteligencję jako „decydującą” o zwycięstwie aliantów. Sir Harry Hinsley , oficjalny historyk brytyjskiego wywiadu w czasie II wojny światowej, dokonał podobnej oceny o Ultra, mówiąc, że skróciło to wojnę „o nie mniej niż dwa lata, a prawdopodobnie o cztery lata”; ponadto powiedział, że w przypadku braku Ultra nie jest pewne, jak zakończyłaby się wojna.

W praktyce analiza częstotliwości opiera się w równym stopniu na wiedzy lingwistycznej , co na statystyce, ale gdy szyfry stały się bardziej złożone, matematyka zyskała na znaczeniu w kryptoanalizie. Zmiana ta była szczególnie widoczna przed i podczas II wojny światowej , kiedy próby złamania szyfrów Osi wymagały nowych poziomów matematycznego wyrafinowania. Ponadto, automatyzacja został po raz pierwszy zastosowany do kryptoanalizy w tamtych czasach z Polski Bomba urządzenia, brytyjska bomba , stosowanie karta dziurkowana wyposażenia, a także w komputerach Colossus - pierwsze elektroniczne komputery cyfrowe być kontrolowane przez program.

Wskaźnik

Dzięki wzajemnym szyfrom maszynowym, takim jak szyfr Lorenza i maszyna Enigma, używanych przez nazistowskie Niemcy podczas II wojny światowej , każda wiadomość miała swój własny klucz. Zwykle operator nadawczy informował operatora odbierającego o tym kluczu wiadomości, przesyłając pewien tekst jawny i/lub tekst zaszyfrowany przed zaszyfrowaną wiadomością. Nazywa się to wskaźnikiem , ponieważ wskazuje operatorowi odbierającemu, jak ustawić jego maszynę do odszyfrowania wiadomości.

Źle zaprojektowane i zaimplementowane systemy wskaźników pozwoliły najpierw polskim kryptografom, a następnie brytyjskim kryptografom z Bletchley Park złamać system szyfrów Enigma. Podobne słabe systemy wskaźników pozwoliły Brytyjczykom zidentyfikować głębokości, które doprowadziły do ​​diagnozy systemu szyfrującego Lorenz SZ40/42 i kompleksowego łamania jego wiadomości bez zauważenia przez kryptoanalityków maszyny szyfrującej.

Głębokość

Wysyłanie dwóch lub więcej wiadomości z tym samym kluczem jest procesem niepewnym. Kryptoanalitykowi mówi się wtedy, że wiadomości są „dogłębne”. Może to zostać wykryte przez wiadomości mające ten sam wskaźnik, za pomocą którego operator wysyłający informuje operatora odbierającego o początkowych ustawieniach generatora kluczy dla wiadomości.

Ogólnie rzecz biorąc, kryptoanalityk może skorzystać na umieszczeniu identycznych operacji szyfrowania w zestawie wiadomości. Na przykład szyfr Vernama szyfruje bit po bicie, łącząc tekst jawny z długim kluczem za pomocą operatora „ exclusivelubdodawania modulo-2 ” (symbolizowanego przez ⊕ ):

Zwykły tekst ⊕ Klawisz = Zaszyfrowany tekst

Deszyfrowanie łączy te same bity klucza z tekstem zaszyfrowanym, aby zrekonstruować tekst jawny:

Zaszyfrowany tekst ⊕ Klawisz = zwykły tekst

(W arytmetyce modulo-2 dodawanie jest tym samym co odejmowanie.) Gdy dwa takie szyfrogramy są wyrównane dogłębnie, połączenie ich eliminuje wspólny klucz, pozostawiając tylko kombinację dwóch tekstów jawnych:

Zaszyfrowany tekst1 ⊕ Zaszyfrowany tekst2 = Zwykły tekst1 ⊕Zwykły tekst2

Poszczególne teksty jawne można następnie opracować językowo, próbując w różnych miejscach prawdopodobnych słów (lub fraz), znanych również jako „szopki” ; prawidłowe odgadnięcie, w połączeniu ze scalonym strumieniem zwykłego tekstu, daje zrozumiały tekst z innego komponentu zwykłego tekstu:

(Zwykły tekst1 ⊕ Zwykły tekst2) ⊕ Zwykły tekst1 = Zwykły tekst2

Odzyskany fragment drugiego tekstu jawnego często można rozszerzyć w jednym lub obu kierunkach, a dodatkowe znaki można połączyć ze scalonym strumieniem tekstu jawnego w celu rozszerzenia pierwszego tekstu jawnego. Pracując tam iz powrotem między dwoma tekstami jawnymi, używając kryterium zrozumiałości do sprawdzenia domysłów, analityk może odzyskać większość lub wszystkie oryginalne teksty jawne. (Mając tylko dwa teksty jawne dogłębnie, analityk może nie wiedzieć, który odpowiada któremu zaszyfrowanemu tekstowi, ale w praktyce nie jest to duży problem). Kiedy odzyskany tekst jawny jest następnie łączony z jego zaszyfrowanym tekstem, ujawnia się klucz:

Zwykły tekst1 ⊕ Zaszyfrowany tekst1 = Klucz

Znajomość klucza umożliwia następnie analitykowi odczytywanie innych wiadomości zaszyfrowanych tym samym kluczem, a znajomość zestawu powiązanych kluczy może pozwolić kryptoanalitykom na zdiagnozowanie systemu użytego do ich budowy.

Rozwój nowoczesnej kryptografii

Rządy od dawna dostrzegają potencjalne korzyści płynące z kryptoanalizy dla wywiadu , zarówno wojskowego, jak i dyplomatycznego, i ustanowiły dedykowane organizacje zajmujące się łamaniem kodów i szyfrów innych narodów, na przykład GCHQ i NSA , organizacji, które są nadal bardzo aktywne.

Bombe replikowane działanie kilku maszyn Enigma przewodowych razem. Każdy z szybko obracających się bębnów, przedstawionych powyżej w makiecie muzeum Bletchley Park , symulował działanie wirnika Enigmy.

Mimo że obliczenia zostały wykorzystane z wielkim efektem w kryptoanalizie szyfru Lorenza i innych systemów podczas II wojny światowej, umożliwiły również nowe metody kryptografii o rzędy wielkości bardziej złożone niż kiedykolwiek wcześniej. Jako całość, współczesna kryptografia stała się znacznie bardziej odporna na kryptoanalizę niż systemy pióra i papieru z przeszłości, a teraz wydaje się mieć przewagę nad czystą kryptoanalizą. Historyk David Kahn zauważa:

Wiele z kryptosystemów oferowanych obecnie przez setki komercyjnych dostawców nie może zostać złamanych żadną znaną metodą kryptoanalizy. Rzeczywiście, w takich systemach nawet atak z wybranym tekstem jawnym , w którym wybrany tekst jawny jest dopasowywany do jego zaszyfrowanego tekstu, nie może dostarczyć klucza odblokowującego inne wiadomości. W pewnym sensie więc kryptoanaliza jest martwa. Ale to nie koniec historii. Kryptoanaliza może być martwa, ale jest – mieszając moje metafory – więcej niż jeden sposób na oskórowanie kota.

Kahn wspomina o zwiększonych możliwościach przechwytywania, podsłuchu , ataków z kanału bocznego i komputerów kwantowych jako zamienników tradycyjnych metod kryptoanalizy. W 2010 roku były dyrektor techniczny NSA, Brian Snow, powiedział, że zarówno kryptografowie akademiccy, jak i rządowi „posuwają się bardzo powoli do przodu w dojrzałej dziedzinie”.

Jednak każda sekcja zwłok do kryptoanalizy może być przedwczesna. Chociaż skuteczność metod kryptoanalitycznych stosowanych przez agencje wywiadowcze pozostaje nieznana, we współczesnej erze kryptografii komputerowej opublikowano wiele poważnych ataków zarówno na akademickie, jak i praktyczne prymitywy kryptograficzne:

Tak więc, podczas gdy najlepsze współczesne szyfry mogą być znacznie bardziej odporne na kryptoanalizę niż Enigma , kryptoanaliza i szersza dziedzina bezpieczeństwa informacji pozostają dość aktywne.

Szyfry symetryczne

Szyfry asymetryczne

Kryptografia asymetryczna (lub kryptografia klucza publicznego ) to kryptografia, która opiera się na użyciu dwóch (matematycznie powiązanych) kluczy; jeden prywatny i jeden publiczny. Takie szyfry niezmiennie opierają się na „twardych” problemach matematycznych jako podstawie ich bezpieczeństwa, więc oczywistym punktem ataku jest opracowanie metod rozwiązania problemu. Bezpieczeństwo kryptografii dwukluczowej zależy od pytań matematycznych, w przeciwieństwie do kryptografii jednokluczowej, i odwrotnie, w nowy sposób łączy kryptoanalizę z szerszymi badaniami matematycznymi.

Schematy asymetryczne są zaprojektowane wokół (domniemanej) trudności w rozwiązywaniu różnych problemów matematycznych. Jeśli uda się znaleźć ulepszony algorytm, który rozwiąże problem, system jest osłabiony. Na przykład bezpieczeństwo schematu wymiany kluczy Diffie-Hellman zależy od trudności obliczenia logarytmu dyskretnego . W 1983 r. Don Coppersmith znalazł szybszy sposób znajdowania dyskretnych logarytmów (w pewnych grupach), a tym samym wymagał od kryptografów używania większych grup (lub różnych typów grup). Bezpieczeństwo RSA zależy (częściowo) od trudności faktoryzacji liczb całkowitych — przełom w faktoringu wpłynąłby na bezpieczeństwo RSA.

W 1980 r. można było rozłożyć trudną 50-cyfrową liczbę kosztem 10 12 podstawowych operacji komputerowych. Do 1984 r. stan techniki w algorytmach faktoringowych osiągnął punkt, w którym 75-cyfrową liczbę można było uwzględnić w 10 12 operacjach. Postępy w technologii obliczeniowej oznaczały również, że operacje można było również wykonywać znacznie szybciej. Prawo Moore'a przewiduje, że prędkość komputerów będzie nadal rosła. Techniki faktoringowe mogą nadal to robić, ale najprawdopodobniej będą zależeć od wglądu matematycznego i kreatywności, z których żadna nigdy nie była przewidywalna. Rozłożono na czynniki 150-cyfrowe liczby, takie jak kiedyś używane w RSA. Wysiłek był większy niż powyżej, ale nie był nierozsądny na szybkich nowoczesnych komputerach. Na początku XXI wieku 150-cyfrowe liczby nie były już uważane za wystarczająco duży rozmiar klucza dla RSA. Liczby składające się z kilkuset cyfr nadal uważano za zbyt trudne do uwzględnienia w 2005 r., chociaż metody prawdopodobnie będą z czasem ulegać poprawie, wymagając rozmiaru klucza, aby nadążać za tempem, lub innych metod, takich jak kryptografia krzywych eliptycznych .

Inną wyróżniającą cechą schematów asymetrycznych jest to, że w przeciwieństwie do ataków na symetryczne kryptosystemy, każda kryptoanaliza ma możliwość wykorzystania wiedzy uzyskanej z klucza publicznego .

Atakowanie kryptograficznych systemów haszujących

Ataki side-channel

Aplikacje obliczeń kwantowych do kryptoanalizy

Komputery kwantowe , które wciąż znajdują się we wczesnej fazie badań, mają potencjalne zastosowanie w kryptoanalizie. Na przykład algorytm Shora może rozkładać duże liczby w czasie wielomianowym , w efekcie łamiąc niektóre powszechnie stosowane formy szyfrowania z kluczem publicznym.

Korzystając z algorytmu Grovera na komputerze kwantowym, wyszukiwanie kluczy metodą brute-force można przyspieszyć kwadratowo. Można temu jednak przeciwdziałać, podwajając długość klucza.

Zobacz też

Historyczni kryptoanalitycy

Bibliografia

Cytaty

Źródła

Dalsza lektura

Zewnętrzne linki