Na przestrzeni lat powstało wiele algorytmów i technik kryptograficznych. Ich rozwój ma na celu coraz lepszą ochronę szyfrowanych danych.
Przegląd algorytmów kryptograficznych rozpoczniemy od algorytmów symetrycznych.
DES
DES, czyli Data Encryption Standard, to jeden z najbardziej rozpowszechnionych algorytmów kryptograficznych. Jest bardzo stary - ma ponad dwadzieścia lat i do niedawna w miarę skutecznie opierał się różnym atakom. Twórcą tego algorytmu była firma IBM, choć część zasługi należy przypisać NSA. To właśnie National Security Agency przeprojektowała S-Boxy (zwane czasem s-skrzynkami), które są sercem DES.
DES jest szyfrem blokowym. Dzieli informację na fragmenty o długości 64 bitów, a później jeszcze na lewą i prawą połowę (każda o długości 32 bitów). Standardowa długość klucza wynosi 56 bitów. Jednak wraz z postępem kryptografii zaczęto uważać, że taki klucz jest zbyt krótki. Zaowocowało to stworzeniem mutacji DES-a zwanej 3DES lub Triple DES. W przypadku 3DES-a informacja jest szyfrowana trzy razy. Oznacza to, że długość klucza została powiększona do 168 bitów. Jednak niektóre implementacje stosują tylko dwa klucze 56-bitowe.
Mutacje DES-a
3DES nie jest jedyną modyfikacją Data Encryption Standard. Na przykład firma RSA opracowała algorytm DESX, który jest częścią pakietu BSAFE. Ta wersja algorytmu ma dodatkowy 64-bitowy klucz, za pomocą którego przeprowadzana jest operacja XOR na tekście jawnym przed pierwszą rundą szyfrowania (DES standardowo ma ich 16). Dzięki temu DESX jest bardziej odporny na atak brutalny oraz lepiej opiera się krypto-analizie różnicowej i liniowej.
CRYPT(3) to wersja DES-a używana w systemach Unix. Jej wzmocnienie polega na uniemożliwieniu opracowania urządzenia do łamania haseł.
Tego typu modyfikacji jest najwięcej. Niektóre S-Boxy są tak zaprojektowane, by lepiej bronić się przed kryptoanalizą różnicową, inne zaś wzmacniają algorytm przed atakami ze strony kryptoanalizy liniowej. Generalnie jednak nie udało się stworzyć S-boxów lepszych od zaprojektowanych przez NSA. Wyjątkiem może być s3DES z odwróconymi S-Boxami nr 1 i 2. Dzięki temu są one odporne na ataki za pomocą kryptoanalizy różnicowej i liniowej. Istnieje również wersja DES-a, w której S-Boxy są zależne od klucza szyfrującego.
| Kryptoanaliza różnicowa i liniowa |
Kryptoanaliza różnicowa to typ ataku, jaki można przeprowadzić tylko na pewnej, stosunkowo dużej rodzinie algorytmów blokowych. Należą do niej m.in. DES czy FEAL-4 - pierwszy algorytm, na którym przeprowadzono tego typu atak. Oczywiście nie ograniczono się tylko do jednego algorytmu. Wkrótce za pomocą kryptoanalizy różnicowej zaczęto atakować inne algorytmy - z bardzo różnymi wynikami. Nowe algorytmy były projektowane tak, aby oprzeć się kryptoanalizie różnicowej.
W przypadku DES-a projektowanego w połowie lat 70, gdy kryptoanaliza różnicowa nie była powszechnie znana, technika ta okazała się mało skuteczna. NSA, która przeprojektowała S-Boxy DES-a, twierdzi, że sposób ten znany był im już w latach 70. i został wzięty pod uwagę podczas konstruowania założeń dotyczących algorytmu. Kryptoanaliza różnicowa jest rodzajem ataku typu: wybrany tekst jawny (ang. Chosen-plaintext attack).
Kryptoanaliza liniowa służy do opisu zachowania algorytmów blokowych. Jej twórcami byli Matsui i Yamagishi, którzy wykorzystali tę metodę do analizy algorytmu FEAL. Istnieje również atak oparty na połączeniu kryptoanalizy różnicowej i liniowej (ang. Differential-linear cryptoanalysis). Metoda ta została opracowana przez Langforda i Hellmana.
Kryptoanaliza liniowa to rodzaj ataku typu: znany tekst jawny (ang. Known-plaintext attack). Przy założeniu, że mamy wystarczająco dużą liczbę tekstów jawnych i zaszyfrowanych, można odkryć przynajmniej część bitów klucza szyfrującego. Można to zrobić w następujący sposób:
1) przeprowadzić operację XOR na wszystkich bitach tekstu jawnego,
2) przeprowadzić operację XOR na wszystkich bitach tekstu zaszyfrowanego,
3) przeprowadzić operację XOR na wynikach obu operacji; efektem będą bity klucza. |
Bezpieczeństwo DES-a
Dzisiaj 56-bitowy klucz nie jest już żadną rewelacją. Wszystko zależy od wagi samej informacji i czasu jej życia. W połowie lipca tego roku Electronic Frontier Foundation (
www.eff.com/descracker.html) ogłosiła skonstruowanie maszyny łamiącej DES-a. Koszt wyprodukowania takiego sprzętu nie przekroczyłby 250 tys. dolarów. Widać więc, że łamanie informacji zaszyfrowanych za pomocą DES-a jest już w zasięgu średniej wielkości firmy. Natomiast 3DES jest rozwiązaniem nadal bezpiecznym. Podkreślam jednak, że wszystko zależy od czasu życia informacji - jeżeli nie przekracza 24 godzin, to DES jest nadal bezpieczny.
| Techniki ataków |
Atak brutalny
W zasadzie każdy szyfr można złamać za pomocą brutalnej siły (ang. brute force). Atak ten zwany jest czasami atakiem wyczerpującym i jest najłatwiejszy w implementacji. Polega on na sprawdzeniu wszystkich możliwych kombinacji, aż do momentu odnalezienia właściwego klucza, który pozwala sprowadzić informację do postaci jawnej.
Skoro zasada działania tego ataku jest taka prosta, to dlaczego uważa się szyfry za bezpieczne - przecież każdy może taką próbę podjąć. Problemem jest jednak czas i wymagana moc obliczeniowa. Szyfr, który uznaje się za bezpieczny, daje odpowiednio dużą liczbę kombinacji, aby atak brutalną siłą był czasowo nieopłacalny. Podczas prób deszyfrowania informacji trzeba brać pod uwagę czas jej życia, który określa, jak długo informacja ma znaczenie - bardzo mało informacji "żyje" dłużej niż rok. Tylko systemy komputerowe w dużych instytucjach (lub całe sieci komputerowe) mają szansę na udaną deszyfrację w rozsądnym czasie. Statystycznie trzeba sprawdzić tylko połowę kluczy.
Kryptoanaliza
Ponieważ atak brutalny jest czasowo nieekonomiczny, kryptolodzy cały czas poszukują technik umożliwiających szybkie deszyfrowanie lub analizę zaszyfrowanej informacji. Często analiza zaszyfrowanej informacji może ujawnić słabości danego rozwiązania, które później mogą pomóc w deszyfrowaniu. Osiągnięciami kryptoanalizy są: kryptoanaliza liniowa i różnicowa.
Istnieją cztery podstawowe rodzaje ataków (przy założeniu, że znany jest algorytm szyfrujący):
- Atak typu: tylko tekst zaszyfrowany (ang. chiper-only attack) - kryptolog ma do dyspozycji tylko informację w postaci zaszyfrowanej (najczęściej ma ich przynajmniej kilka). Wszystkie informacje zostały zaszyfrowane za pomocą tego samego algorytmu. Zadanie kryptologa polega na odnalezieniu maksymalnie wielu postaci jawnych informacji. Pełny sukces nastąpi w przypadku odkrycia oryginalnego klucza (lub kluczy).
- Atak typu: znany tekst jawny (ang. Known-plaintext attack) - w tym przypadku osoba próbująca złamać szyfr ma dostęp do tej samej informacji w postaci jawnej i zaszyfrowanej; musi odnaleźć odpowiedni klucz.
- Atak typu: wybrany tekst jawny (ang. Chosen-plaintext attack) - kryptolog nie tylko zna jawną postać informacji, ale również wybiera informację, która zostanie zaszyfrowana. Metoda ta jest dużo bardziej skuteczna od poprzedniej.
- Atak typu: adaptive-chosen-plaintext - jest to wariacja poprzedniej techniki z tą tylko różnicą, że kryptolog może zmieniać treść i rozmiar informacji, która ma zostać zaszyfrowana.
Nie są to wszystkie sztuczki, jakimi posługują się kryptolodzy. W literaturze można znaleźć jeszcze przynajmniej 3 inne ataki, które są skomplikowanymi wariacjami podstawowych metod. |
IDEA
Jest to algorytm konkurencyjny w stosunku do DES-a, choć dużo młodszy (pierwsze wersje pojawiły się w 1990 roku pod nazwą PES). IDEA operuje na 64-bitowych blokach (podobnie jak DES), ale długość klucza równa jest 128 bitom. Blok 64-bitowy jest dzielony na cztery 16-bitowe podbloki, które stają się danymi wejściowymi dla pierwszej rundy algorytmu. IDEA wykorzystuje osiem rund do szyfrowania informacji. Ciekawą własnością tego algorytmu jest szybkość - w przypadku rozwiązań programowych IDEA jest prawie dwukrotnie szybsza od DES-a.
Zdaniem wielu kryptografów na całym świecie, również i moim, IDEA jest bezpieczniejsza od DES-a. NSA nie miała wpływu na wygląd i siłę tego algorytmu, ponieważ powstał on w Szwajcarii. Gdyby przeprowadzić atak brutalny na ten algorytm, to do sprawdzenia byłoby 1038 zaszyfrowanych tekstów. Możliwy jest atak inną metodą, lecz IDEA jest zbyt młoda, aby można było znać jakiś skuteczny sposób. Dodatkowo IDEA była projektowana tak, aby oprzeć się kryptoanalizie różnicowej.
| One-time pad |
Poprawnie stosowany algorytm One-time pad jest niemożliwy do złamania. W tej metodzie każdy bajt treści jawnej zostaje zastąpiony innym (losowym) bajtem. Oznacza to, że długość klucza równa jest długości informacji. Przyjmijmy, że wiadomość, którą szyfrujemy brzmi:
P C k u r i e r
2 & * d Q / [ d
Normalnie operacja podstawienia jest zastępowana operacją XOR, nie zmienia to jednak zasady działania. Warto zwrócić uwagę, że w przykładzie bajt o wartości "d" wystąpił dwa razy, ale za każdym razem oznacza inny bajt tekstu jawnego. Widać więc, że kryptolog nie znajduje w zaszyfrowanym tekście żadnego punktu zaczepienia - nawet statystyka występowania liter w języku jest zatarta. Kryptolog może jedynie próbować stwierdzić, czy informacja jest w postaci skompresowanej. Atak brutalny też nic nie da, bo zaszyfrowany tekst jest nieznany i kryptolog nie wie, czy tekst "PCkurier" jest oryginalną informacją.
One-time pad zwany jest też szyfrem Vernama. W oryginalnej implementacji klucz był zapisany na długiej, obracającej się taśmie papierowej. Taki szyfr jest bardzo łatwo złamać, gdyż wystarczy odszyfrować tylko jedną informację, aby móc wydedukować klucz szyfrujący. Jeśli jednak klucz szyfrujący będzie całkowicie losowy i nigdy się nie powtórzy, to złamanie szyfru jest niemożliwe. |
Algorytmy asymetryczne - RSA
Pierwszy i do tej pory jedyny powszechnie akceptowany algorytm z kluczem jawnym jest dziełem Rona Rivesta, Adi Shamira i Lena Adlemana. Powstał w 1977 roku i rok później został po raz pierwszy opublikowany. RSA jest najbardziej znanym algorytmem asymetrycznym. Pomysł opiera się na wykorzystaniu bardzo dużych liczb pierwszych. Algorytm może być stosowany z kluczami o różnej długości (na przykład 512 lub 1024 bity). Sama RSA zaleca używanie kluczy o długości 2048 bitów do szyfrowania najważniejszych informacji. Zdaniem ekspertów z tej firmy, klucz 768-bitowy powinien być bezpieczny do roku 2004.
RSA jest algorytmem bezpiecznym - przy założeniu, że nie zostanie w nim znaleziona jakaś dziura lub błąd. Najbardziej skuteczną metodą ataku na algorytm RSA byłoby opracowanie metody szybkiego rozkładu na czynniki pierwsze (faktoryzacja). Istnieją co prawda inne metody ataku na RSA, ale w wielu przypadkach dotyczą konkretnej implementacji, pozostałe zaś wymagają pełnego zrozumienia działania algorytmu.
* * *
Aleksander Czarnowski
Adres autora:
alekc@avet.com.pl
|
