Dotychczas zajmowałem się realizacją usług integralności oraz uwierzytelnienia przesłanych danych. Najwyższy czas zająć się tajnością, czyli takim ich zabezpieczeniem, aby nie były możliwe do odczytania przez osoby do tego nieuprawnione. Jest to cel usługi zwanej poufnością, a algorytmy które ją realizują nazywane są szyframi (ang. cipher). W poniższym wpisie przedstawię jeden z ich typów. Będą to symetryczne szyfry blokowe.
Szyfrowanie i deszyfrowanie
Proces szyfrowania (ang. encryption) przekształca wiadomość zwaną tekstem jawnym lub otwartym (ang. plaintext, cleartext) w tekst zaszyfrowany określany również kryptogramem (ang. encrypted text, ciphertext). Operacją odwrotną jest deszyfrowanie (ang. decryption). Parametrem obu funkcji jest klucz (ang. key), który zapewnia utajnienie przekazywanej informacji. Procesy te pokazane są na poniższym rysunku. Zamiast oznaczenia $$E^{-1}_K$$ stosowane jest również $$D_K$$.
Poufność nie jest usługą, która pojawiła się dopiero wraz z nowoczesnymi komputerami. Jednym z klasycznych szyfrów jest szyfr Cezara. Polega on na podstawieniu za każdą literę szyfrowanej wiadomości litery odległej od niej o trzy znaki w alfabecie. Zatem wiadomość ABC po zaszyfrowaniu uzyska postać DEF. Szyfr ten można uogólnić ustalając klucz K na liczbę przesunięć. Dla alfabetu angielskiego uzyskamy wtedy szyfr przesuwający z 26 możliwymi kluczami. Jest to szczególny przypadek szyfru monoalfabetycznego, w którym kluczem jest określona permutacja alfabetu, czyli przyporządkowanie liter do innych liter. Takie przyporządkowanie stosujemy dla każdego znaku szyfrowanej wiadomości. Jeśli przygotowalibyśmy kilka takich przekształceń i stosowali je cyklicznie dla kolejnych znaków to otrzymamy szyfr polialfabetyczny. Wszystkie te szyfry tworzą grupę szyfrów podstawieniowych. Dla porządku muszę jeszcze wspomnieć o szyfrach przestawieniowych, w których szyfrowanie polega na zmianie kolejności (pozycji) znaków w tekście jawnym a nie ich wartości.
Szyfr Cezara używa jednego klucza i nazywany jest szyfrem z powodów historycznych. Poprawnie należałoby mówić w tym przypadku o kodowaniu a nie szyfrowaniu. Kodowanie jest zmianą formy zapisu według określonego i znanego algorytmu, w której nie występuje klucz potrzebny do odczytania wiadomości. Jedna z odmian szyfru przesuwającego, używająca przesunięcia 13, czyli połówki alfabetu angielskiego (dzięki temu ten sam algorytm służy do szyfrowania i deszyfrowania) znana jest jako ROT13 i niekiedy używana na przykład na grupach dyskusyjnych w celu zaciemnienia treści lub jako przedmiot różnych żartów. Algorytm ten wbudowany jest w wiele aplikacji pocztowych i edytorów tekstowych. W edytorze Vim przekształcenie można wykonać używając skrótu g?.
Kiedy szyfr jest szyfrem
Nie każda funkcja przekształcająca wiadomość jest szyfrem. W szczególności aby być tak zwanym szyfrem blokowym musi spełniać co najmniej następujące warunki:
- każde dane o określonej wielkości (np. n bitów) musi zamieniać na blok o takiej samej długości (stąd nazwa szyfry blokowe, liczbę n nazywamy długością bloku),
- szyfr działa używając kluczy o długości k bitów, długość ta może być inna niż długość bloku,
- musi zachodzić $$E^{-1}_K(E_K(M))=M$$, czyli to co zaszyfrujemy powinno być możliwe do rozszyfrowania tym samym kluczem.
Wymienione własności nie wyczerpują wszystkich cech dobrego szyfru. Musi on być trudny do złamania, co oznacza, że osoba nie posiadająca klucza nie powinna mieć możliwości uzyskania tekstu jawnego z kryptogramu. Wymagania dla szyfrów są jeszcze silniejsze: osoba posiadająca tekst jawny i kryptogram nie powinna mieć możliwości odzyskania klucza, który umożliwi jej zdeszyfrowanie innych przechwyconych kryptogramów. Wszystkie te zasady zakładają również jawność algorytmu szyfrującego.
Wyobraźmy sobie następujący eksperyment. Siedzimy przed czarną skrzynką, do której wprowadzamy pewne dane, a ona odpowiada nam danymi o tej samej długości. Innymi słowy wprowadzamy blok danych do przekształcenia i w odpowiedzi również otrzymujemy blok danych. Może być tam szyfrator szyfrujący z pewnym, nieznanym nam, kluczem K lub generator liczb losowych. Nie wiemy co jest w skrzynce, a nasze zadanie polega na odgadnięciu czy mamy do czynienia z generatorem liczb losowych czy z szyfratorem. Jeżeli znajdziemy metodę by na podstawie otrzymywanych wyników rozpoznawać co robi urządzenie, to szyfr poddany temu testowi nie znajdzie zastosowań w kryptografii. Oczywiście nie możemy dwukrotnie podawać do czarnego pudełka tego samego bloku - wtedy zadanie byłoby łatwe do rozwiązania. Z opisanego eksperymentu wynika jeszcze jeden ważny wniosek. Odpowiednio użyty szyfr może mieć zastosowanie jako generator liczb losowych.
Dobre szyfry powinny zapewniać konfuzję i dyfuzję. Twórcą tych koncepcji jest Claude Elwood Shannon, który zajmował się teorią informacji. Konfuzja ma na celu ukrycie związku pomiędzy wiadomością jawną, szyfrogramem i kluczem. Dyfuzja mówi o rozproszeniu bitów klucza i wiadomości jawnej w całym kryptogramie.
Z powyższych powodów wymienione wcześniej szyfry klasyczne z punktu widzenia kryptografii są obecnie ciekawostką i nie powinny być używane w systemach, które mają zapewnić poufność.
Kluczy o długości k bitów może być $$2^k$$. Zbiór wszystkich kluczy nazywamy przestrzenią kluczy. Ponieważ jest ich skończona liczba to zawsze możemy przeprowadzić atak brutalny (ang. brute force attack), który polega na sprawdzeniu kolejnych kluczy. Z tego powodu przestrzeń kluczy powinna być tak duża, aby taki atak uniemożliwić w praktyce. Wtedy czas lub zaangażowane zasoby do znalezienia klucza będą nieopłacalne, żeby przeprowadzić taki atak. Załóżmy, że klucz ma długość 56 bitów i w ciągu sekundy możemy sprawdzić 100 milionów kluczy. Aby przeszukać całą przestrzeń kluczy potrzeba prawie 23 lat. Jeśli wydłużymy klucz tylko o 1 bit czas wzrośnie dwukrotnie, do prawie 46 lat.
Szyfry symetryczne
Kiedy operacja szyfrowania i deszyfrowania wykonywana jest z tym samym kluczem mówimy o szyfrowaniu symetrycznym (ang. symmetric encryption), a klucz taki nazywamy kluczem tajnym (ang. secret key). Diagram bezpiecznej komunikacji za pomocą takiego szyfru przedstawiony jest na poniższym rysunku.
Niezbędnym warunkiem do prawidłowej realizacji usługi poufności jest bezpieczne przekazanie klucza tajnego. Jak można to zrobić? Oczywiście realizując usługę poufności, czyli przekazać klucz zaszyfrowany... innym kluczem. Realizując taką procedurę wpadniemy w rekurencję, którą w końcu trzeba przerwać. Niezbędna jest wymiana pierwszego klucza w zaufanym kanale, czyli w takim, który nie jest narażony na skuteczne ataki przez kryptoanalityka. O takich technikach napiszę wkrótce.
Jak już wspomniałem blokowe szyfry symetryczne szyfrują całe n-bitowe bloki. Jeśli blok jaki chcemy zaszyfrować jest za krótki niezbędne jest zastosowanie dopełnienia (ang. padding). Wiadomość można uzupełnić na przykład zerami. W tym przypadku druga strona może mieć kłopot z określeniem co jest wiadomością a co jest dopełnieniem ponieważ w samej wiadomości mogą być zera. Innym rodzajem dopełnienia, które będzie jednoznaczne dla odbiorcy, jest uzupełnienie wiadomości bajtami o wartości liczby dopełnianych bajtów. W każdym przypadku odbiorca musi wiedzieć jaką technikę stosowaliśmy, aby zastosować analogiczny algorytm i oddzielić wiadomość od jej dopełnienia.
Kilka algorytmów
Jednym z pierwszych współczesnych algorytmów kryptograficznych jest algorytm DES (Data Encryption Standard) nazywany również DEA (Data Encryption Algorithm). Został opracowany w połowie lat siedemdziesiątych przez IBM na zlecenie USA. Działa na blokach o długości 64 bitów. Klucz algorytmu DES jest takiej samej długości, jednak w samym algorytmie najmłodsze bity każdego bajtu klucza są pomijane co prowadzi do efektywnego klucza o długości 56 bitów. Algorytm DES nigdy nie został złamany, ale ma zbyt krótki klucz i z tego powodu nie powinien być obecnie stosowany. Metodą wydłużenia klucza w algorytmie DES jest jego zastosowanie trzy razy z różnymi kluczami. Potrójny DES polega na zaszyfrowaniu wiadomości z kluczem K1, następnie zdeszyfrowaniu wyniku z kluczem K2 i ponownym jego zaszyfrowaniu z kluczem K3. Można zapisać to jako $$3DES_{K1 | K2 | K3}(M)=DES_{K3}(DES^{-1}{K2}(DES{K1}(M)))$$. Pozwala to wydłużyć klucz do 192 bitów (efektywnie 168 bitów). 3DES używa się często z zestawem kluczy w których pierwszy i trzeci klucz mają tę samą wartość. W takim przypadku klucz będzie miał długość 128 bitów (efektywnie 112 bitów). DES i 3DES przedstawione zostały w standardzie FIPS 46-3.
W roku 1997 NIST ogłosił konkurs na algorytm, który miał stać się nowym standardem szyfrowania i zastąpić algorytm DES. W finale znalazły się szyfry Rijndael, MARS, RC6, Serpent i Twofish. Miano AES (Advanced Encryption Standard) uzyskał pierwszy z nich. AES szyfruje 128-bitowe bloki używając klucza o długości 128, 192 lub 256 bitów. Początkowa specyfikacja Rijndaela dopuszczała również bloki 192- i 256-bitowe, ale zostały one usunięte z AES. Działanie tego algorytmu można obejrzeć na tej animacji, formalna specyfikacja przedstawiona jest w dokumencie FIPS 197. Obecnie AES jest zalecanym przez NIST sposobem szyfrowania danych.
Algorytmem o którym warto wspomnieć jest Blowfish i to nie tylko z powodu jego wdzięcznej nazwy w języku polskim, która wskazuje na rybę rozdymkę. Jest on dość popularny w oprogramowaniu typu open source, którego twórcy z różnych powodów nie chcą używać rozwiązań zalecanych przez organizacje rządowe. Blowfish szyfruje 64-bitowe bloki używając klucza o długości od 32 do 448 bitów. Bruce Schneier, autor algorytmu, zaleca obecnie używanie jego następcy, czyli algorytmu Twofish.
Szyfrowanie i deszyfrowanie w Javie można zrealizować za pomoc ą fabryki Cipher. Nazwa wybranego algorytmu szyfrującego, typ dopełnienia oraz tak zwany tryb szyfrowania (omówię je w kolejnym wpisie) przekazywany jest jako ciąg znaków. Podobnie jak inne algorytmy znajdziemy je w dokumencie Standard Algorithm Name Documentation lub w dokumentacji używanego dostawcy usług kryptograficznych.
Wynikiem działania poniższego programu będzie wyliczenie kryptogramu dla pojedynczego bloku (szyfrowanie) oraz przekształcenie go w początkową wiadomość (deszyfrowanie) za pomocą algorytmu AES, bez dopełnienia (szyfrujemy cały blok, więc jest niepotrzebne), w trybie elektronicznej książki kodowej (na ten moment można przyjąć, że tryb ten to szyfrowanie każdego z bloków niezależnie od siebie).
1import javax.crypto.Cipher; 2import javax.crypto.spec.SecretKeySpec; 3 4public class CipherTest { 5 public static void main(String[] args) throws Exception { 6 byte[] plain = "abcdefghijklmnop".getBytes(); 7 byte[] key = "klucz--128-bitow".getBytes(); 8 9 SecretKeySpec secretKey = new SecretKeySpec(key, "AES"); 10 Cipher cipher = Cipher.getInstance("AES/ECB/NoPadding"); 11 12 // szyfrowanie 13 cipher.init(Cipher.ENCRYPT_MODE, secretKey); 14 byte encrypted[] = cipher.doFinal(plain); 15 16 // deszyfrowanie 17 cipher.init(Cipher.DECRYPT_MODE, secretKey); 18 byte decrypted[] = cipher.doFinal(encrypted); 19 } 20}
Interesujący efekt działania programu zaobserwujemy wydłużając klucz do 256 bitów. U użytkowników maszyny wirtualnej HotSpot najczęściej pojawi się wyjątek java.security.InvalidKeyException Illegal key size or default parameters. Nie jest to wina klucza, dla algorytmu AES klucz o tej długości jest prawidłowy. Ograniczenie na siłę algorytmów kryptograficznych jest wymaganiem w niektórych krajach i z tego powodu domyślnie instalowane jest z dystrybucją maszyny wirtualnej. Po pobraniu i zainstalowaniu pakietu Java Cryptography Extension (JCE) Unlimited Strength Jurisdiction Policy Files dla odpowiedniej wersji Java ograniczenie to będzie zniesione i program zacznie działać.
Zachęcam do samodzielnych eksperymentów z innymi szyframi oraz dopełnieniami bloków. Zwracam uwagę, że tajny klucz przechowujemy w kodzie źródłowym aplikacji, co nie jest najlepszym pomysłem. Pojawiają się przy tym kolejne problemy. Jeśli użytkownik miałby pamiętać 128-bitowy klucz i używać go jak hasła to w rzeczywistym rozwiązaniu jest to niepraktyczne. Rozwiązaniem będzie przekształcanie haseł użytkowników w klucze kryptograficzne.
Podsumowanie
Algorytmy szyfrujące umożliwiają realizację usługi poufności. Co się stanie jeśli atakujący przechwyci i zakłóci przesyłany kryptogram? Nie uda mu się poznać przesyłanej wiadomości (oczywiście jeśli użyty zostanie bezpieczny szyfr), ale odbiorca zdeszyfruje zakłócony kryptogram. To co otrzyma nie będzie oryginalną wiadomością. Jednak skąd odbiorca ma to wiedzieć? Z punktu widzenia kryptoanalizy taki atak doprowadzi do zaakceptowania przed odbiorcę fałszywego komunikatu. Dlaczego udało się go przeprowadzić? Cbavrjnż avr mncrjavbab vagrtenyabśpv. Qb ernyvmnpwv grtb pryh zbżan jlxbemlfgnć zrpunavmzl, xgóer whż cemrqfgnjvłrz. N j xbyrwalz jcvfvr bzójvę gelol fmlsebjnavn qyn fmlseój oybxbjlpu.
