Zasady kryptografii

Choć kryptografia ma historię sięgającą czasów Juliusza Cezara, współczesne techniki kryptograficzne — również te używane w internecie — opierają się na badaniach prowadzonych w ciągu ostatnich 30 lat. Książki The Codebreakers [Kahn 1967] oraz The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography [Singh 1999] oferują fascynujące spojrzenie na długą historię kryptografii. Kompletne studium kryptografii zajęłoby całą książkę [Kaufman 1995; Schneier 1995], więc tutaj zajmiemy się tylko jej najważniejszymi aspektami, szczególnie tymi, które mają związek z internetem. Nadmieńmy też, że choć w tym podrozdziale skupimy się na poufności, to techniki kryptograficzne są również nierozerwalnie splątane z uwierzytelnianiem, integralnością, niezaprzeczalnością i innymi aspektami bezpieczeństwa.

Techniki kryptograficzne pozwalają nadawcy przekształcić dane tak, aby intruz nie mógł uzyskać żadnych informacji z przechwyconej wiadomości. Oczywiście, odbiorca musi mieć możliwość odtworzenia oryginalnych danych. Kilka najważniejszych terminów zilustrowano na rysunku 8.2.

Rysunek 8.2. Komponenty kryptograficzne

Przypuśćmy, że Alicja chce przesłać wiadomość do Bartka. Wiadomość Alicji w pierwotnej postaci (na przykład „Bartku, kocham cię. Alicja”) określa się mianem tekstu jawnego lub zwykłego tekstu. Alicja szyfruje tekst jawny za pomocą algorytmu szyfrowania, uzyskując szyfrogram nieczytelny dla osób postronnych. Co ciekawe, w wielu współczesnych systemach kryptograficznych, również tych używanych w internecie, sama technika szyfrowania jest znana — opublikowana, ustandaryzowana i dostępna dla wszystkich (na przykład [RFC 1321; RFC 3447; RFC 2420; NIST 2001]), również dla potencjalnego intruza! Oczywiście jeśli każdy zna metodę szyfrowania danych, to musi istnieć jakaś tajna informacja, która zapobiegnie odczytaniu danych przez intruza. Tą informacją są klucze.

Na rysunku 8.2 Alicja dostarcza klucz KA — łańcuch liczb lub znaków — na wejście algorytmu szyfrowania. Algorytm przyjmuje klucz oraz tekst jawny m i na ich podstawie tworzy szyfrogram. Notacja KA(m) oznacza szyfrogram tekstu jawnego m uzyskany za pomocą klucza KA. Z kontekstu wiadomo, jaki algorytm korzysta z tego klucza. Podobnie Bartek przekazuje klucz KB algorytmowi deszyfrowania, który przyjmuje ten klucz oraz szyfrogram i na ich podstawie odtwarza tekst jawny; tzn. jeśli Bartek odbierze zaszyfrowaną wiadomość KA(m), odszyfrowuje ją poprzez obliczenie KB(KA(m)) = m. W systemach z kluczem symetrycznym klucze Alicji i Bartka są jednakowe i zachowywane w tajemnicy. W systemach z kluczem publicznym używa się pary kluczy. Jeden z kluczy jest znany zarówno Bartkowi, jak i Alicji (w rzeczywistości całemu światu). Drugi klucz jest znany albo Bartkowi, albo Alicji (ale nie obojgu jednocześnie). W następnych dwóch punktach zbadamy dokładniej systemy z kluczem symetrycznym i kluczem publicznym.

Kryptografia z kluczem symetrycznym

Wszystkie algorytmy kryptograficzne polegają na zastępowaniu jednej rzeczy drugą, na przykład pobieraniu fragmentu tekstu jawnego oraz obliczaniu i podstawianiu odpowiedniego szyfrogramu w celu utworzenia wiadomości zaszyfrowanej. Zanim przestudiujemy współczesny system kryptograficzny oparty na kluczach, zbadajmy bardzo stary, bardzo prosty algorytm szyfrowania przypisywany Juliuszowi Cezarowi i zwany szyfrem Cezara (szyfr to metoda szyfrowania danych).

Szyfr Cezara działa w następujący sposób: bierzemy każdą literę tekstu jawnego i zastępujemy ją literą znajdującą się o k liter dalej w alfabecie (alfabet jest „zawinięty”, tzn. po literze „ż” następuje litera „a”). Jeśli na przykład k = 3, litera „a” w tekście jawnym staje się literą „c” w szyfrogramie; litera „ą” w tekście jawnym staje się literą „ć” w szyfrogramie itd. Wartość k pełni tu funkcję klucza. Na przykład tekst jawny „bartku, kocham cię. alicja” jest przekształcany w szyfrogram „dctymz, mrekco elh. cnlełc”. Choć szyfrogram rzeczywiście wygląda bezsensownie, złamanie kodu byłoby bardzo łatwe, ponieważ istnieje tylko 31 możliwych wartości klucza.

Ulepszeniem szyfru Cezara jest szyfr monoalfabetyczny, który również polega na zamianie liter. Nie używa się jednak regularnego wzorca (na przykład przesunięcia o k liter), ale dowolnych podstawień, z tym zastrzeżeniem, że każda litera musi mieć unikatowy zamiennik. Na rysunku 8.3 pokazano jedną z możliwych metod kodowania tekstu jawnego.

Rysunek 8.3. Szyfr monoalfabetyczny

W tym przypadku tekst jawny „bartku, kocham cię. alicja” jest przekształcany w szyfrogram „cwćytl, tiżźwp żhb. wńhżęa”. Podobnie jak w przypadku szyfru Cezara szyfrogram wygląda bezsensownie. Wydawałoby się też, że szyfr monoalfabetyczny jest znacznie lepszy od szyfru Cezara, ponieważ pozwala połączyć litery w pary na 32! sposobów (liczba rzędu 1035), a nie na skromne 31. Próba złamania kodu i odszyfrowania wiadomości przez wypróbowanie wszystkich 1035 kombinacji zajęłaby tyle czasu, że jest z góry skazana na niepowodzenie. Jednakże analiza statystyczna języka, w którym napisano tekst jawny — na przykład ustalenie, że w typowym polskim tekście najczęściej występują litery „a” oraz „i” (obie z częstością powyżej 7%) i że niektóre dwu- i trzyliterowe sekwencje liter pojawiają się znacznie częściej niż inne (na przykład „ch”, „ci”, „nie” itp.) — pozwala dość łatwo złamać ten kod. Jeśli intruz dysponuje jakąś wiedzą o treści wiadomości, ma jeszcze łatwiejsze zadanie. Przykładowo, jeśli Inga jest żoną Bartka i podejrzewa, że romansuje on z Alicją, to może przypuszczać, że w tekście znajdują się słowa „bartek” lub „alicja”. Gdyby Inga wiedziała na pewno, że te dwa imiona występują w szyfrogramie, mogłaby natychmiast ustalić 10 spośród 32 par liter, zmniejszając o 1014 liczbę możliwości do wypróbowania. Gdyby zresztą Inga podejrzewała Bartka o romans, mogłaby oczekiwać, że znajdzie w wiadomości inne specyficzne słowa.

Kiedy zastanawiamy się, jak łatwo byłoby Indze złamać szyfr używany przez Bartka i Alicję, możemy wyróżnić trzy scenariusze, w zależności od informacji, do jakich intruz ma dostęp:

• Atak ze znanym szyfrogramem. W niektórych przypadkach intruz ma dostęp wyłącznie do szyfrogramu i nie wie nic o zawartości tekstu jawnego. Wyjaśniliśmy już, że w ataku ze znanym szyfrogramem może pomóc analiza statystyczna.
• Atak ze znanym tekstem jawnym. Jak już stwierdziliśmy, gdyby Inga wiedziała, że w szyfrogramie występują słowa „bartek” i „alicja”, mogłaby ustalić pary (tekst jawny, szyfrogram) dla liter b, a, r, t, e, k, l, i, c oraz j. Mogłaby również zarejestrować wszystkie przesyłane szyfrogramy, a później odnaleźć odszyfrowaną wersję któregoś z nich zapisaną przez Bartka na kartce papieru. Kiedy intruz zna niektóre pary (tekst jawny, szyfrogram), mówimy o ataku ze znanym tekstem jawnym. 
• Atak z wybranym tekstem jawnym. W ataku z wybranym tekstem jawnym intruz może wybrać dowolny tekst jawny i uzyskać jego szyfrogram. W przypadku prostych algorytmów, które omawialiśmy do tej pory, Inga mogłaby nakłonić Alicję do wysłania wiadomości „Pchnąć w tę łódź jeża lub ośm skrzyń fig” i całkowicie złamać szyfr. Niebawem pokażemy, że w bardziej zaawansowanych technikach szyfrowania atak z wybranym tekstem jawnym nie zawsze pozwala złamać szyfr. 

Pięćset lat temu wymyślono techniki szyfrowania polialfabetycznego. Polegają one na użyciu wielu szyfrów monoalfabetycznych, przy czym określony szyfr monoalfabetyczny służy do kodowania litery o określonym położeniu w tekście jawnym. Zatem ta sama litera może być kodowana na różne sposoby, w zależności od pozycji, jaką zajmuje w tekście jawnym. Przykład szyfru polialfabetycznego pokazano na rysunku 8.4. Składa się on z dwóch szyfrów Cezara (o parametrach k = 5 i k = 19). Moglibyśmy zdecydować, że będziemy używać tych dwóch szyfrów w powtarzającej się sekwencji C1, C2, C2, C1, C2. Pierwsza litera tekstu jawnego byłaby kodowana za pomocą szyfru C1, druga i trzecia — za pomocą szyfru C2, czwarta — za pomocą szyfru C1, a piąta — za pomocą szyfru C2. Następnie wzór powtarzałby się — szósta litera byłaby kodowana za pomocą szyfru C1, siódma — za pomocą szyfru C2 itd. Tekst jawny „bartku, kocham cię. alicja” zostałby zatem zaszyfrowany do postaci „ęogźak, aefzdc rmu. dąźfnd”. Zauważmy, że pierwsza litera „a” tekstu jawnego jest zakodowana za pomocą szyfru C1, a druga litera „a” — za pomocą C2. W tym przykładzie „kluczem” szyfrowania i deszyfrowania jest znajomość dwóch kluczy Cezara (k = 5, k = 19) oraz wzoru C1, C2, C2, C1, C2.

Rysunek 8.4. Szyfr polialfabetyczny złożony z dwóch szyfrów Cezara  

Szyfry blokowe

Przejdźmy teraz do współczesności i zbadajmy, jak obecnie wygląda szyfrowanie z kluczem symetrycznym. Istnieją dwie ogólne klasy technik szyfrowania z kluczem symetrycznym — szyfry strumieniowe i szyfry blokowe. Szyfry strumieniowe opisujemy pokrótce w podrozdziale 8.7, gdzie badamy zabezpieczenia bezprzewodowych sieci lokalnych. W tym miejscu skoncentrujemy się na szyfrach blokowych, które są stosowane w wielu bezpiecznych protokołach internetowych, w tym w PGP (do zabezpieczenia poczty elektronicznej), SSL (do zabezpieczania połączeń TCP) i IPsec (do zabezpieczania transportu w warstwie sieciowej). 

W szyfrach blokowych szyfrowany komunikat jest przetwarzany w blokach po k bitów. Na przykład jeśli k = 64, komunikat jest dzielony na 64-bitowe bloki, a każdy z nich jest szyfrowany niezależnie. Aby zakodować blok, algorytm szyfrujący stosuje odwzorowanie jeden do jednego i przekształca k-bitowy blok tekstu jawnego na k-bitowe bloki szyfrogramu. Przyjrzyjmy się przykładowi. Załóżmy, że k = 3, więc szyfr blokowy odwzorowuje 3-bitowe dane wejściowe (tekst jawny) na 3-bitowe dane wyjściowe (szyfrogram). Jedno z możliwych odwzorowań przedstawia tabela 8.1. Warto zauważyć, że jest to odwzorowanie jeden do jednego. Oznacza to, że dla każdych danych wejściowych tworzone są inne dane wyjściowe. Ten szyfr blokowy dzieli komunikat na 3-bitowe bloki i szyfruje każdy z nich na podstawie powyższego odwzorowania. Czytelnik powiniensprawdzić, że komunikat 010110001111 zostanie zaszyfrowany do postaci 101000111001.

Tabela 8.1. Określony 3-bitowy szyfr blokowy

Kontynuujmy przykład z 3-bitowymi blokami. Zauważmy, że odwzorowanie z tabeli 8.1 to tylko jedno z wielu możliwych rozwiązań. Ile różnych odwzorowań istnieje? Aby odpowiedzieć na to pytanie, warto zauważyć, że odwzorowanie jest niczym więcej jak permutacją wszystkich możliwych danych wejściowych. Tych danych jest 23, czyli 8 (są one wymienione w kolumnie danych wejściowych). Dla tych ośmiu możliwości istnieje 8! = 40 320 różnych permutacji. Ponieważ każda z nich określa odwzorowanie, tych ostatnich też jest 40 320. Każde odwzorowanie można traktować jako klucz. Jeśli Alicja i Bartek znają odwzorowanie (klucz), mogą szyfrować i odszyfrowywać przesyłane komunikaty.

Atak siłowy (ang. brute force) na ten szyfr polega na próbie odszyfrowania szyfrogramu za pomocą każdego odwzorowania. Przy tylko 40 320 odwzorowaniach (dla k = 3) można to szybko zrobić na komputerze PC. Aby zapobiec atakom siłowym, w szyfrach blokowych zwykle stosuje się dużo większe bloki — z k = 64 lub nawet więcej. Zauważmy, że liczba możliwych odwzorowań dla ogólnego szyfru o bloku o wielkości k wynosi 2k!, co daje bardzo dużą wartość nawet dla umiarkowanych wartości k (na przykład k = 64). Choć szyfry blokowe z kompletną tabelą, takie jak opisany wcześniej, już przy niewielkich wartościach k pozwalają opracować solidne systemy szyfrowania z kluczem symetrycznym, są niestety trudne w stosowaniu. Dla k = 64 i określonego odwzorowania Alicja i Bartek muszą przechowywać tabelę o 264 wartościach wejściowych. Jest to niewykonalne zadanie. Ponadto gdyby Alicja i Bartek mieli wymieniać klucze, musieliby odtwarzać tę tabelę. Dlatego szyfry blokowe z kompletną tabelą, określające wstępnie ustalone odwzorowanie między wszystkimi wartościami wejściowymi i wyjściowymi (jak we wcześniejszym przykładzie), są nieakceptowalne.

Zamiast tego w szyfrach blokowych zwykle wykorzystywane są funkcje symulujące tabele utworzone w wyniku losowej permutacji. Przykład (zaadaptowany z [Kaufman 1995]) takiej funkcji dla k = 64 bity przedstawia rysunek 8.5. Ta funkcja najpierw dzieli 64-bitowy blok na osiem 8-bitowych fragmentów. Każdy z tych fragmentów jest przetwarzany za pomocą możliwej do obsłużenia tabeli o wielkości osiem na osiem bitów. Na przykład do przetwarzania pierwszego fragmentu służy tabela T1. Następnie osiem wyjściowych fragmentów jest łączonych w 64-bitowy blok. System zamienia wtedy pozycje 64 bitów w tym bloku, aby wygenerować 64-bitowe dane wyjściowe. Są one ponownie stosowane jako 64-bitowe dane wejściowe, co zaczyna następny cykl. Po n takich cyklach funkcja zwraca 64-bitowy blok szyfrogramu. Celem stosowania rund jest sprawienie, aby każdy bit wejściowy oddziaływał na większość (jeśli nie wszystkie) z ostatecznie uzyskanych bitów wyjściowych. Gdyby uruchomiono tylko jedną rundę, bit wejściowy wpływałby na tylko osiem z 64 bitów wyjściowych. Kluczem w takim algorytmie szyfrowania blokowego jest osiem tabel permutacji (zakładamy, że funkcja mieszająca bity jest powszechnie znana).

Rysunek 8.5. Przykładowy szyfr blokowy  

Obecnie istnieje wiele popularnych szyfrów blokowych, w tym DES (ang. Data Encryption Standard), 3DES i AES (ang. Advanced Encryption Standard). Każdy z tych standardów wykorzystuje funkcje zamiast wstępnie przygotowanych tabel, jak przedstawia to rysunek 8.5 (choć poszczególne szyfry są bardziej skomplikowane). Każdy z algorytmów używa też łańcucha bitów jako klucza. Na przykład DES wykorzystuje 64-bitowe bloki z 56-bitowym kluczem. AES używa 128-bitowych bloków i może działać z kluczami o długości 128, 192 i 256 bitów. Klucz algorytmu określa konkretne odwzorowania i permutacje w postaci „minitabeli”. Atak siłowy na każdy z tych szyfrów polega na cyklicznym sprawdzaniu wszystkich kluczy i stosowaniu ich w algorytmie deszyfrującym. Zauważmy, że przy kluczu o długości n istnieje 2n możliwych kluczy. W instytucie NIST [NIST 2001] oszacowano, że maszynie, która potrafi złamać 56-bitowy szyfr DES w jedną sekundę (czyli zdoła wypróbować w tym czasie każdy z 256 kluczy), złamanie 128-bitowego klucza AES zajęłoby około 149 trylionów lat.

Wiązanie bloków

W aplikacjach sieciowych zwykle trzeba szyfrować długie komunikaty (lub długie strumienie danych). Jeśli zastosujemy szyfr blokowy przez prosty podział wiadomości na k-bitowe bloki i niezależne zaszyfrowanie każdego z nich, wystąpi subtelny, ale istotny problem. Aby go dostrzec, należy zauważyć, że bloki z tekstem jawnym mogą być identyczne. Na przykład tekst jawny w kilku blokach może brzmieć „HTTP/1.1”. Dla takich identycznych bloków szyfr blokowy utworzy oczywiście takie same szyfrogramy. Napastnik może odgadnąć tekst jawny, jeśli zauważy identyczne bloki w szyfrogramie. Może nawet zdołać odszyfrować całą wiadomość przez zidentyfikowanie takich samych bloków i wykorzystanie wiedzy na temat struktury zastosowanego protokołu [Kaufman 1995].

Aby rozwiązać ten problem, należy wprowadzić w proces losowość, aby identyczne bloki tekstu jawnego prowadziły do utworzenia odmiennych szyfrogramów. W celu wyjaśnienia tego pomysłu przyjmijmy, że m(i) oznacza i-ty blok tekstu jawnego, c(i) to i-ty blok szyfrogramu, a a + b oznacza operację XOR na dwóch łańcuchach bitów (a i b). Przypomnijmy, że 0 + 0 = 1 + 1 = 0 i 0 + 1 = 1 + 0 = 1, a suma XOR dwóch łańcuchów bitów jest obliczana bit po bicie, na przykład 10101010 + 11110000 = 01011010. Ponadto oznaczmy algorytm szyfru blokowego z kluczem S jako KS. Podstawowa reguła wygląda tak — nadawca tworzy losową k-bitową liczbę r(i) dla i-tego bloku i oblicza c(i) = KS(m(i) + r(i)). Zauważmy, że dla każdego bloku wybierana jest nowa k-bitowa liczba. Następnie nadawca wysyła wartości c(1), r(1), c(2), r(2), c(3), r(3) itd. Ponieważ odbiorca otrzymuje c(i) i r(i), może odtworzyć każdy blok tekstu jawnego przez obliczenia m(i) = KS(m(i)) + r(i). Należy zauważyć, że choć wartość r(i) jest przesyłana jako tekst jawny i może zostać zarejestrowana przez Ingę, nie zdoła ona uzyskać tekstu jawnego m(i), ponieważ nie zna klucza KS. Ponadto nawet jeśli dwa bloki tekstu jawnego m(i) i m(j) są identyczne, odpowiadające im bloki szyfrogramu c(i) i c(j) różnią się od siebie (o ile liczby losowe r(i) i r(j) są inne, co jest wysoce prawdopodobne).

Rozważmy na przykład 3-bitowy szyfr blokowy z tabeli 8.1. Załóżmy, że tekst jawny to 010010010. Jeśli Alicja zaszyfruje go bezpośrednio (bez wprowadzania losowo- ści), wynikowy szyfrogram będzie miał wartość 101101101. Jeżeli Inga zarejestruje ten szyfrogram, to ze względu na to, że trzy bloki szyfrogramu są identyczne, będzie mogła słusznie przyjąć, że każdy z trzech bloków tekstu jawnego jest taki sam. Teraz załóżmy, że Alicja wygeneruje losowe bloki r(1) = 001, r(2) = 111 i r(3) = 100 oraz zastosuje opisaną wcześniej technikę do utworzenia szyfrogramu c(1) = 100, c(2) = 010 i c(3) = 000. Zauważmy, że trzy bloki szyfrogramu różnią się od siebie, choć bloki tekstu jawnego są takie same. Alicja wyśle wtedy dane c(1), r(1), c(2) i r(2). Czytelnik powinien sprawdzić, że Bartek zdoła uzyskać pierwotny tekst jawny za pomocą wspólnego klucza KS.

Uważni Czytelnicy zauważą, że wprowadzenie losowości rozwiązuje jeden problem, ale wprowadza inny. Alicja musi teraz przesyłać dwa razy więcej bitów. Dla każdego bitu szyfrogramu musi wysłać także bit losowy, co podwaja potrzebną przepustowość. Aby można było „zjeść ciastko i mieć ciastko”, w szyfrach blokowych zwykle stosuje się technikę wiązania bloków (ang. Cipher Block Chaining — CBC). Podstawowa zasada jej działania polega na wysyłaniu tylko jednej losowej wartości z pierwszym komunikatem, po czym nadawca i odbiorca mogą wykorzystać obliczone zakodowane bloki zamiast kolejnych liczb losowych. Opiszmy dokładniej funkcjonowanie techniki wiązania bloków:

1. Przed zaszyfrowaniem komunikatu (lub strumienia danych) nadawca generuje losowy k-bitowy łańcuch nazywany wektorem inicjującym (ang. Initialization Vector — IV). Oznaczmy ten wektor przez c(0). Nadawca wysyła do odbiorcy wektor IV jako tekst jawny.

2. Dla pierwszego bloku nadawca oblicza wartość m(1)+ c(0), czyli sumę XOR pierwszego bloku tekstu jawnego i wektora IV. Następnie przekazuje wynik do algorytmu szyfru blokowego, aby uzyskać odpowiedni blok szyfrogramu (c(1) = KS(m(1)+ c(0)). Nadawca wysyła zaszyfrowany blok c(1) do odbiorcy.

3. Dla i-tego bloku nadawca generuje i-ty blok szyfrogramu c(i) = KS(m(i) + c(i – 1)). Zbadajmy teraz skutki zastosowania tego podejścia. Po pierwsze, odbiorca nadal może odtworzyć pierwotną wiadomość. Kiedy otrzyma szyfrogram c(i), odszyfruje go za pomocą klucza KS, aby uzyskać s(i) = m(i)? c(i – 1). Ponieważ odbiorca zna również wartość c(i – 1), może otrzymać blok tekstu jawnego na podstawie obliczeń m(i) = s(i)+ c(i – 1). Po drugie, nawet jeśli dwa bloki tekstu jawnego są identyczne, odpowiadające im szyfrogramy prawie zawsze będą różne. Po trzecie, choć nadawca wysyła wektor IV jako tekst jawny, intruz nie będzie mógł odszyfrować bloków szyfrogramu, ponieważ nie zna tajnego klucza S. Wreszcie nadawca wysyła tylko jeden dodatkowy blok (wektor IV), dlatego dla długich komunikatów, składających się z setek bloków, wzrost potrzebnej przepustowości jest pomijalny.

W ramach przykładu obliczmy na podstawie 3-bitowego szyfru blokowego z tabeli 8.1 szyfrogram dla tekstu jawnego 010010010 i wektora IV = c(0) = 001. Nadawca najpierw używa wektora IV do obliczenia c(1) = KS(m(1) ? c(0)) = 100, a następnie oblicza c(2) = KS(m(2)+ c(1)) = KS(010+ 100) = 000 i c(3) = KS(m(3)+ c(2)) = KS(010+ 000) = 101. Czytelnik powinien sprawdzić, że odbiorca — znając wartość wektora IV i klucz KS — zdoła odtworzyć pierwotny tekst jawny.

Wiązanie bloków ma poważny wpływ na projektowanie bezpiecznych protokołów sieciowych. Trzeba w nich udostępnić mechanizm do przekazywania wektora IV od nadawcy do odbiorcy. W dalszej części rozdziału pokażemy, jak odbywa się to w kilku protokołach.

Opracowano na podstawie:

 Sieci komputerowe. Ujęcie całościowe. Wydanie VII, Autorzy: James Kurose, Keith Ross, Wydawnictwo: Helion