Cześć!

W poprzednim wpisie zajmowaliśmy się szyfrem Cezara, który okazał się być dalekim od ideału zabezpieczeniem poufności informacji. Dzisiaj, tak jak obiecałem, pokażę Wam kolejne i o wiele lepsze podejście do tego problemu😊.

W ramach krótkiego przypomnienia – transformacja stosowana na tekście jawnym musi być odwracalna i bazująca na konkretnym, tajnym kluczu. Takie algorytmy szyfrowania nazywamy symetrycznymi. Szyfr Cezara wykorzystywał podstawienia, zamiast jednej litery wstawiał inną. W jaki sposób możemy dokonać przekształcenia lepiej? Zanim podam Wam rozwiązane tego problemu musimy wrócić do pewnej sprawy podstawowej. Każda informacja jest reprezentowana jako liczba.

Istnieje wiele sposobów jak przedstawić znaki jako liczby i nazywamy je kodowaniem. Najpopularniejszymi są kodowanie ASCII (choć już chyba nieco archaiczne, notabene bazujące na kodach telegraficznych) oraz UTF-8 i UTF-16. Jeśli pójdziemy krok dalej, możemy taką liczbę reprezentować jako ciąg zer i jedynek (bitów, utożsamianych z odpowiednio wysokim i niskim napięciem) z wykorzystaniem systemu dwójkowego. Spójrzcie na przykład poniżej z wykorzystaniem kodowania ASCII:

Znak przed kodowaniem	A		L		A	(spacja)	M	A
Kod ASCII	65		76		65	32	77	65
Zapis binarny	01000001		01001100		01000001	00100000	01001101	01000001
Znak przed kodowaniem		(spacja)		K		O		T	A
Kod ASCII		32		75		79		84	65
Zapis binarny		00100000		01001011		01001111		01010100	01000001

W tym momencie, jak przysłowiowy książę na białym koniu pojawia się nasza nowa metoda transformacji – jest nią bitowa operacja alternatywy rozłącznej, popularnie zwana operacją xor.

Operację tą możemy najprościej przedstawić za pomocą tabelki 2. Litery p i q oznaczają argumenty działania a samą operację oznaczamy znakiem .

0	0	0
0	1	1
1	0	1
1	1	0

Alternatywa rozłączna, jest to operacja bitowa więc możemy ją później wykonywać również na całych bajtach (ciągu ośmiu bitów) xor’ując ze sobą kolejne bity tj. w przykładzie poniżej. Spójrzcie na trzecią kolumnę jak na słupki przy dodawaniu pisemnym.

	Reprezentacja dziesiętna	Reprezentacja binarna
	79	0 1 0 0 1 0 1 1
	254	1 1 1 1 1 1 1 0
	181	1 0 1 1 0 1 0 1

Operacja xor ma co najmniej kilka ciekawych własności i zastosowań (polecam uwadze https://florian.github.io/xor-trick/), jednak dla nas szczególnie istotne są następujące:

• ,
• ,
• , jest to tzw. łączność.

Zatem jeśli , wtedy . Voila! Odzyskaliśmy tekst jawny zatem jesteśmy technicznie w stanie użyć tej operacji do zaszyfrowania danych. Pojawia się w tym momencie pytanie, czym powinien być klucz. Przeanalizujemy teraz kilka opcji.

Rozwiązanie pierwsze:

Wykonujemy xor każdego bajtu tekstu jawnego z pewną stałą wartością liczbową. Proste? Proste! Niestety w realny sposób nie zwiększa to poziomu bezpieczeństwa. Podobnie jak w szyfrze Cezara, ten sam znak będzie miał zawsze przyporządkowywaną tą samą wartość i podobnie jak poprzednik jest podatny na analizę statystyczną. W poprzednim wpisie zajmowaliśmy się tekstem a dzisiaj pokażę Wam ciut bardziej spektakularny przykład wykorzystując obróbkę zdjęć. Spójrzcie na rysunki 1 i 2.

Rysunek 1 Lenna Sjööblom – pierwsza dama internetu wg. czasopisma Wired

Rysunek 2 Rysunek poddany szyfrowaniu poprzez xor z bajtem 0xfe

Rysunek 1 jest to fotografia, którą poddamy szyfrowaniu (łączy się z nią pewna anegdota ale o niej trochę później). Każdy format graficzny w jakiś sposób próbuje zakodować informację o ilości kolorów czerwonego, zielonego oraz niebieskiego dla każdego piksela obrazu. Format bmp, którego użyłem w przykładzie używa 1 bajtna każdy z nich.

Rysunek 2 jest nieco zniekształcony gdyż jest to kryptogram😊. Powstał on poprzez xor’owanie każdego bajtu wszystkich piksli z bajtem 0xFE (to jest zapis w systemie szesnastkowym liczby 254). Zdjęcie wygląda nieco inaczej niż w oryginale ale wciąż rozpoznajemy na nim młodą kobietę z odsłoniętymi ramionami w kapeluszu z futrem. Wniosek jest jeden – pomimo szyfrowania widzimy tutaj całkiem dużo informacji jednak przewrotnie powiem (jest to taki trochę śmiech przez łzy), że mieliśmy i tak sporo szczęścia. Rysunek 3 przedstawia wynik szyfrowania bajtem o wartości 5. Jak widzicie nie różni się on wizualnie wcale od oryginału.

Rysunek 3 Zdjęcie zaszyfrowane bajtem 0x5

W ramach chwili oddechu chciałbym Wam opowiedzieć obiecaną anegdotę. Jeśli będziecie się interesować kiedyś cyfrowym przetwarzaniem obrazu lub ich kompresją to dość często będzie ono Wam towarzyszyć (trochę jak swego czasu memy o Ryszardzie Petru wyskakującym z lodówki).

Po raz pierwszy wykorzystał ją Alexander Sawchuk, profesor Uniwersytetu Południowej Kalifornii, który razem
z kilkoma kolegami usilnie szukał zdjęć do wykorzystania jako przykład w czasie jednej z konferencji. Jak na mój gust wybrali oni dość mało konwencjonalne jak na świat nauki źródła zdjęć. Szukali ich w starych wydaniach Playboy’a, samo zdjęcie pochodzi z roku 1972 roku. Przedstawia ono Lenę Sjööblom, szwedzką modelkę, która o swojej popularności w świecie komputerowych nerdów dowiedziała się dopiero w 1988 roku i aż do 1997 roku nie korzystała z Internetu. Oryginalne zdjęcie możecie znaleźć na poprzez Google’a szukając artykułu pod tytułem Internet Icon with Lenna Sjoeoeblom 😉

W tym momencie przypomina mi się pewien dowcip z bródką:

Dwóch kolegów informatyków zaprasza trzeciego na imprezę. Nie mogą go przekonać i w końcu mówią: „Będą panie!”. Na to trzeci odpowiada – „Ile?”. Dwaj odpowiadają chórem – „Całe 5 giga”.

A teraz wracając do tematu – co możemy zrobić lepiej?

Rozwiązanie 2:

Zamiast xor’ować tekst jawny stale z tą samą wartością możemy użyć jako klucz ciąg losowych wartości i zapisać go aby umożliwić deszyfrację w przyszłości. Ten wariant został zaproponowany w 1917 roku przez Gilberta Vernama jako tzw. szyfr z kodem jednorazowym (ang. one-time pad). Gwarantuje on nam tzw. doskonałą tajność.

Szyfr jest doskonale tajny tylko i wyłącznie gdy dla każdej wiadomości m i dla każdego tekstu tajnego c, prawdopodobieństwo, że otrzymany kryptogram odpowiada wiadomości m jest takie samo jak prawdopodobieństwo nadania wiadomości m. Oznacza to de facto, że szyfrogram:

• nie ujawnia żadnych informacji o tekście jawnym,
• jest bezwarunkowo odporny na atak ze znanym kryptogramem (ang. known-ciphertext attack),
• istnieje więcej kluczy niż wiadomości.

Atak ze znanym szyfrogramem polega na tym, że kryptoanalityk dysponując pewną liczbą zaszyfrowanych tym samym kluczem wiadomości, próbuje odzyskać możliwie wiele oryginalnych wiadomości lub zgadnąć klucz. Nasze zmagania z szyfrem Cezara mogą stanowić przykład takiego ataku – każdą kolejną wiadomość używamy żeby zwiększyć naszą wiedzę o prawdopodobieństwie znaków dopóki nie odzyskamy klucza.

Spójrzcie na rysunek 4. Powstał on przez zaszyfrowanie zdjęcia 1 one-time pad’em i w przeciwieństwie do rysunków 2 i 3 przypomina on raczej biały szum sygnału analogowego w telewizorach przed epoką telewizji cyfrowej.

Rysunek 4 Zdjęcie zaszyfrowane losowym ciągiem bajtów

W przypadku jednokrotnego użycia klucza prawdopodobieństwo zgadnięcia klucza wynosi , czyli jest praktycznie pomijalnie małe. Rozwiązanie na pewno jest bezpieczne, ale czy jest ono tym czego szukamy? Nie do końca… Szukamy zawsze rozwiązania optymalnego, a takie jest kompromisem pomiędzy poziomem bezpieczeństwa (lub paranoi 😊) i wygody. Aktualny pomysł nie jest zbyt wygodny: wymaga wcześniejszej wymiany bardzo długich kodów (albo ustalenia wspólnego źródła bajtów klucza), które na domiar złego muszą być jednorazowe. Mimo to, rozwiązanie było wykorzystywanie na przykład w słynnej gorącej linii pomiędzy Moskwą a Waszyngtonem… a tymczasem pokażę Wam w jaki sposób ten problem ominąć.

Rozwiązanie 3:

Naszym ostatnim krokiem jest wykorzystanie zamiast liczb losowych tzw. generatora liczb pseudolosowych. Samymi generatorami zajmiemy się bardziej w kolejnym artykule ale w telegraficznym skrócie są to komponenty, które inicjujemy tajnym kluczem i zwraca on zawsze ten sam (oczywiście przy tym samym kluczu), nieskończony ciąg liczb, które wyglądają (i zachowują się) jak losowe. Dzięki temu osoba znająca klucz może później zdekodować wiadomość.

Przykładem takiego algorytmu jest szyfr RC4 (lub Arcfour, gdyż nazwa RC4 jest zastrzeżonym znakiem handlowym). W jaki sposób generuje on kolejne liczby? Algorytm składa się z dwóch części:

• procedury inicjowania bufora generatora,
• algorytmu pseudolosowej generacji kolejnych bajtów.

Losowe bajty są tworzone w oparciu o bufor generatora – tablicę 256-elementową wypełnioną kolejnymi liczbami od 0 do 255 włącznie, która jest później mieszana w następujący sposób

Kolejne losowe bajty są uzyskiwane poprzez dalsze mieszanie tablicy i jest ono opisane następującym algorytmem:

Zdjęcie poniżej przedstawia wynik szyfrowania z wykorzystaniem szyfru Arcfour. Jak widzicie nie różni się ono wizualnie od wyników one-time pad’a.

Nazwa strumień jest wykorzystana w pseudokodzie nie bez powodu. Poprzez strumień rozumiemy to, że kolejne losowe bajty mogą być dostarczane na bieżąco, w miarę gdy pojawiają się kolejne bajty tekstu jawnego umożliwiając ciągłe nadawanie ciągłej zaszyfrowanej transmisji. Takie szyfry nazywamy szyframi strumieniowymi.

Tego typu szyfry są użyteczne w szczególności dla urządzeń o małej mocy obliczeniowej lub przy szyfrowanej transmisji dźwięku lub obrazu. Jeśli każdy klucz używamy jednokrotnie to szyfr jest na tyle bezpieczny na ile nieprzewidywalny jest generator.

Już zbliżamy się do końca ale, czy domyślacie się dlaczego w przypadku one-time pad’a oraz Arcfour klucz powinien być jednorazowy? Spójrzcie poniżej, jeśli  oraz  to:

W teorii wciąż nie wiemy jaka jest treść tekstów jawnych, ale czy nie mamy żadnej informacji na ich temat? Zrobimy mały eksperyment, rysunki 5 i 6 zostaną zaszyfrowane szyfrem Arcfour z wykorzystaniem tego samego klucza. Rysunek 7 będzie natomiast przedstawiał wynik xor’owania ze sobą obu szyfrogramów. Myślę, że odpowiedź nasunie się sama.

Rysunek 5 Wariacje na temat logo systemu FreeBSD, przykład do zaszyfrowania

Rysunek 6 Logo systemu FreeBSD, przykład do zaszyfrowania

Rysunek 7 Wynik xor’owania szyfrogramów rysunków 5 i 6

Kończąc, jeśli macie czas i chęci lub po prostu chcecie poeksperymentować z programami, które napisałem do tego wpisu odwiedźcie repozytorium (serdecznie zapraszam) a w następnym artykule zajmiemy się tematem komputerowej losowości, gdyż nie jest to temat taki do końca oczywisty.

Do zobaczenia!