Cześć!

W poprzednim wpisie wspominałem Wam, że jeśli używamy klucza tylko i wyłącznie jednorazowo to szyfr jest na tyle bezpieczny na ile nieprzewidywalne są liczby losowe użyte do szyfrowania. Może Was to nieco dziwić… Każdy z nas, od wczesnego dzieciństwa przyzwyczajony jest do losowych wyników poprzez rzut kością w grach planszowych czy przypadkowej kolejności kart w potasowanej talii (notabene do tematu gier karcianych wrócę nieco później) więc losowość do pewnego stopnia jest dla nas naturalna.

Niestety (albo stety) nie jest tak dla komputera, który ze swej natury jest deterministyczny. Podczas gdy my, rzucając kością wyzwalamy zdarzenia losowe, ponieważ nie jesteśmy w stanie rzucić kością zawsze dokładnie tak samo (chyba, że kość jest kantowana) to komputer nie ma takiej możliwości. Prawdziwa losowość może bazować na szumie sensorów albo zjawiskach fizycznych – może to być np. rozpad promieniotwórczy nie mówiąc już o innych zjawiskach elektromagnetycznych lub kwantowych.

Sensory jako źródło entropii

Spójrzcie na nagranie poniżej – prezentuje ono zapis odczytów akcelerometru, który jak widzicie tkwi w bezruchu… A odczyty szaleją!

Odczyty akcelerometru

Szum w odczytach czujników jest sporym problemem dla robotyków, którzy radzą sobie z nimi wykorzystując różnego rodzaju filtry, takie jak np. filtr Kalmana dla nas ma on jednak wielkie znaczenie. Pokazuje, że czujniki mogą stanowić źródło losowości (albo używając mądrzejszych słów entropii) dla komputera. Jeśli się zastanowimy, to upakowana jest w nim cała masa różnych komponentów elektronicznych, które często potrzebują ze względów bezpieczeństwa np. informację o temperaturze komponentu… System operacyjny zbiera te odczyty generując entropię dla generatorów liczb losowych.

Wykres poniżej przedstawia obciążenie procesora w czasie pracy komputera. Niektóre programy tj. na przykład VeraCrypt (służący do szyfrowania danych) wykorzystują w tym celu chaotyczne trajektorie ruchów myszy użytkownika w czasie instalacj oprogramowania.

Rysunek 1 Obciążenie procesora przy włączonym Wordzie i Netflix’ie

To podejście ma jednak drobną wadę – jest powolne. Dlatego informatycy wymyślili generatory liczb pseudolosowych. Algorytmy, które zainicjowane ziarnem, podają na wyjściu liczby, sprawiające wrażenie losowych.

Generatory liczb pseudolosowych

Jednym z przykładów takich algorytmów jest liniowy generator kongruentny (ang. linear congruential pseudorandom generator, LCRNG). Wiem, nazwa brzmi mądrze, gdyż wzięła się stąd, że wykorzystuje on reszty z dzielenia (stąd kongruentny). Działa on w następujący sposób:

1. Użytkownik inicjuje generator ziarnem, które oznaczamy jako X₀
2. Kolejne liczby są generowane wg. Następującej formuły

Zapis ten oznacza, że  ma wartość reszty z dzielenia  przez m, gdzie a, c oraz m są stałymi w czasie działania algorytmu.

Zróbmy drobny test, wykorzystajmy tę formułę w wyznaczenia przybliżonej wartości liczby π metodą Monte Carlo (tak na marginesie, została ona opisana i po raz pierwszy wykorzystana przez polskiego matematyka ze Lwowa, Stanisława Ulama). Działa ona w następujący sposób:

Losujemy punkty o współrzędnych z przedziału od -1 do 1 i zliczamy liczbę punktów, które znajdują się w kole o środku w punkcie (0, 0) i promieniu 1 – pole takiego koła wynosi… Niespodzianka, właśnie liczba π 😊. Punkty te należą do koła, jeśli spełniają nierówność .

Liczba π ma wtedy wartość  .

Rysunek 2 Rysunek poglądowy przygotowany z wykorzystaniem programu Wolfram Mathematica

Program montecarlo https://gitlab.com/sisiphus-on-code/cryptography/-/tree/main/random_number_generator/montecarlo zawiera implementację algorytmu LCRNG i wykorzystuje go do wyznaczenia wartości liczby Pi. Możecie sprawdzić, że im więcej punktów losujemy, tym bliżej otrzymana wartość bliska jest liczbie 3,14 zatem algorytm z dużym prawdopodobieństwem generuje liczby losowe. Pozostaje tylko pytanie, czy jest jakiś haczyk, tym bardziej, że jest on wykorzystywany w bibliotekach standardowych wielu różnych języków programowania – w tym glibc języka C, która jest swego rodzaju lingua franca świata komputerów. Tak na marginesie, z niej właśnie wziąłem parametry do generatora użytego w metodzie Monte Carlo.

Niestety, jak się za chwilę dowiecie algorytm ten w pewnych okolicznościach może być przewidywalny o czym boleśnie przekonały się swego czasu kasyna Las Vegas.

Historia o automatach do gry w pokera

Kilka lat temu czytałem książkę Kevina Mitnicka „Sztuka infiltracji”, obecnie szanowanego konsultanta do spraw bezpieczeństwa komputerowego, a kiedyś hakera znanego pod pseudonimem Condor (było to nawiązanie do filmu z „Trzy dni kondora” z roku 1975, w którym główną rolę grał Robert Redford).

Otóż Mitnick, przytoczył w niej historię grupki znajomych, którzy mieli przeprowadzić konsultacje w Nevadzie i pod wpływem ich piękniejszych, drugich połówek zdecydowali się by przy okazji znaleźć sposób na rozbicie puli w kasynach Vegas. Czego nie zrobią mężczyźni, gdy kobiety im wejdą na ambicje!

Grupa analizowała przede wszystkim dwie możliwości w jaki sposób można potencjalnie zaatakować kasyno albo mówiąc bardziej profesjonalnym językiem, wyznaczyli następujące wektory ataku:

1. Fizyczne włamanie do maszyn i “podmiana firmware’u”
   
   Umieszczenie własnego chipu, aby zastąpić oryginalne oprogramowanie wersją zapewniającą bardziej atrakcyjne wypłaty. Rozwiązanie to jest o tyle problematyczne, że wymaga współpracy z technikiem opiekującym się automatami – można byłoby je porównać z walnięciem staruszki po głowie i odebraniem jej torebki,
   
   
2. Atak zaczerpnięty z książki The Eudaemonic Pie Thomasa Bassa (Penguin, 1992).
   
   Grupa komputerowców i fizyków rozpracowywali w latach 80 system ruletki w kasynach. Opracowali komputerek, któremu jeden członek grupy podawał prędkość koła ruletki
   oraz obrotów kulki i próbował przewidzieć wynik gry. Nie wygrali tym sposobem tony złota, gdyż ich metoda była skażona tym, że dużą rolę odgrywało w niej zachowanie i stosunki międzyludzkie – nie mogli się wydać podejrzani innym uczestnikom gry.

Podejście, które zastosowała grupa bazowała na ataku 2, ale wybrali grę, która ograniczała stosunki między ludzkie do minimum – czyli automaty do gry w pokera.

Prace nad problemem rozpoczeli or pragmatycznego założenia związanego względami proceduralnymi. Maszyny zanim zostaną dopuszczone do użytku muszą przejść testy wymagane przez Komisję Gier Hazardowych Las Vegas. Testy te nie dość, że zabierają bardzo dużo czasu to do tego są jeszcze niezwykle kosztowne. Ich celem jest sprawdzenie czy z jednej strony automat zapewnia dostateczną losowość, z drugiej czy nie zapewnia nieuczciwej przewagi kasynu. Do pewnego stopnia musi być przewidywalne, jak często pada zwycięskie rozdanie, aby kontrolować maksymalną wartość puli. W związku z tym kasyna decydowały się dłużej eksploatować przestarzałe maszyny niż to było wskazane. Bezpieczeństwo poprzez wycinkę drzew i generowanie tony dokumentów jest elementem charakterystycznym dla branży automotive. Za pewne pożalę się na to w którymś z kolejnych artykułów.

Panowie koledzy pojechali więc do sąsiedniego stanu i.… zakupili w nieoficjalnym obiegu jedną ze starszych maszyn do pokera, gdyż założyli (jak się później okazało słusznie), że podobne są używane w Vegas. Stwierdzili też, że skoro planują atakować automaty o niskich wypłatach to za pewne generator nie jest zbyt silny i może być wadliwie zaimplementowany 😊. Maszyny po przewiezieniu do wynajętych przez nich apartamentów, zostały rozebrane na części pierwsze po czym zrzucili zawartość pamięci Flash z programem.

Stosując narzędzia inżynierii wstecznej (czyli odzyskiwaniu informacji jak on działa na podstawie analizy istniejącego produktu), odkryli, w jaki sposób generowane są wartości kart oraz to,
że losowość zapewniana jest przez znany nam już algorytm LCG. Dało im to zdolność do przewidzenia, za ile rozdań pojawi się zwycięskie rozdanie. W jaki sposób możemy przewidzieć kolejne liczby generatora?

Hakowanie glibc’a?

Spójrzcie na zamieszczony poniżej fragment linuksowego manual’a dotyczącego funkcji random().

Rysunek 3 Fragment linuksowego manuala dotyczącego funkcji random()

Kluczowe jest pierwsze zdanie: “The random() function uses a nonlinear additive feedback random number generator”, które jest nie do końca prawdziwe. Dlaczego?

Jeśli zerkniecie https://github.com/lattera/glibc/blob/master/stdlib/random_r.c znajdziecie tam kod, który na pierwszy rzut oka (i nawet na drugi 😉) wydaje się całkiem skomplikowany jednak Peter Selinger z Uniwersytetu Dalhousie na stronie https://www.mathstat.dal.ca/~selinger/random/ zaprezentował algorytm, który produkuje dokładnie te same wartości co funkcja random() (oczywiście dla tego samego ziarna).

Na stronie mojego repozytorium https://gitlab.com/sisiphus-on-code/cryptography/-/tree/main/random_number_generator/glibc_randomness znajdziecie trzy programy:

• GlibcGenerator – oczekuje podania ziarna generatora, informację ile liczb losowych ominąć i ile liczb wydrukować na ekranie. Liczby są wygenerowane używając funkcji random().
• AlternativeGenerator – oczekuje na podobne parametry wejściowe jak program powyżej jednak liczby generowane są z wykorzystaniem algorytmu Selingera, który nieco zrefaktoryzowałem,
• GlibcNextPredictor – oczekuje na 31 liczb podanych poprzez standardowe wejście i na ich podstawie generuje jaka będzie następna liczba dostarczona poprzez generator glibc’a.

Zajmiemy się teraz przez moment analizą programu AlternativeGenerator. Co możemy zaobserwować przy pierwszym czytaniu kodu

1. W funkcji main nie ma żadnego bezpośredniego odwołania do struktury state (typu randomness_state).

Struktura ta jest wewnętrznym stanem generatora, gdyby wyciągnąć funkcje init_randomness() oraz get_random() do osobnego pliku, programista nie miałby do niej w ogóle dostępu.

• Przed użyciem funkcji get_random() wywołujemy funkcję init_randomness() zatem sekwencja jest podobna do użycia funkcji srand() i random().
• Algorytm LCG jest używany TYLKO I WYŁĄCZNIE na początku inicjowania tablicy stanów, później używane są już proste sumy lub podstawienia.
• Funkcja random() nie zwraca nam dokładnej wartości przechowywanej w wewnętrznym stanie tylko obciętą o najmniej znaczący bit.

Kluczowe dla nas będą obserwacje 3 i 4. Możemy zauważyć, że jeśli dostaliśmy 31 liczb z generatora to kolejna jest sumą liczb o indeksach 0 oraz 28. Jednak musimy sobie przypomnieć, że liczby które widzieliśmy na ekranie są obcięte o jeden bit względem wewnętrznego stanu generatora zatem kolejna liczba może być mieć jedną z następujących wartości:

• 2 * buffer[0] + 2 * buffer[28] – brakującym bitem obu liczb jest zero
• 2 * buffer[0] + 2 * buffer[28] + 1 – brakującym bitem jednej z liczb jest 1 (najbardziej prawdopodobna).
• 2 * buffer[0] + 2 * buffer[28] + 2 – brakującym bitem obu liczb jest jeden

Jak widzicie udało nam się z pewnym prawdopodobieństwem określić jakie będzie kolejna liczba pochodząca z generatora.

Na ile dobry jest los?

Skoro już wiemy, że generator generatorowi nie jest równy, warto zastanowić się nad tym czy da się to w jakiś sposób sprawdzić.

Możemy tego dokonać z wykorzystaniem narzędzi takich jak:

• Dieharder,
• TestU01.

Próbują one znaleźć korelację pomiędzy kolejnymi liczbami losowymi implementując różne testy statystyczne (np. bazujące na paradoksie urodzinowym). Przykładowo, mogą one zliczać długość sekwencji rosnących i malejących wygenerowanych liczb i sprawdzać ich rozkład (żeby potencjalny adwersarz nie mógł określić prawdopodobieństwa czy kolejna liczba będzie większa czy mniejsza).
Do zastosowań kryptograficznych ważne jest aby rozkład generowanych liczb był jednostajny.
W rozkładzie jednostajnym, każdy bajt jest tak samo prawdopodobny, podczas gdy w rozkładzie normalnym wartości środkowe występują znacznie częściej niż skrajne.

Rysunek 4 Przykładowy rozkład zbliżony do normalnego

Rysunek 5 Przykładowy rozkład zbliżony do jednostajnego

Swego czasu, zdarzyło mi się eksperymentować ze sprzętowym generatorem liczb losowych dostępnego na płytce Nucleo L552ZE-Q. Test dieharder jest to aplikacja, która przyjmuje testowane liczby na standardowe wejście (tj. wejście na konsolę terminala) lub z pliku tekstowego. TestU01 jest natomiast dostarczany jako biblioteka, gdzie bateriom testowym przekazujemy funkcję generującą (czy w moim przypadku dostarczającą pobrane poprzez UART) liczby losowe. Wykonałem te testy na generatorze RC4, linuksowym pseudourządzeniu /dev/urandom (w systemach uniksowych każde urządzenie konceptualnie jest reprezentowane jako plik, generator liczb pseudolosowych nie jest prawdziwym urządzeniem, a sztucznie utworzonym przez jądro systemu, stąd prefiks pseudo) oraz sprzętowym z mikrokontrolera. Jakie były wyniki? Pierwsze dwa generatory okazały się bezpieczne podczas gdy STM’owy okazał się być wadliwy – prawie żaden nie przechodził. Wydało mi się to dziwne, gdyż znalazłem informację, że przechodzą na nim testy sugerowane przez NIST (bardzo ważną organizację wytyczających normy cyberbezpieczeństwa dla firm prywatnych). Myślałbym, że to wina sprzętu, jednak testy dostarczone przez producenta przechodzą właściwie (a niespodziewałbym się, że firma taka jak STMicro kłamie), stąd podejrzewam raczej, że źródło problemów znajdowało się między klawiaturą a krzesłem 😉. Później pojawiły mi się pilniejsze rzeczy do zrobienia więc nie inwestygowałem tego dalej.

Kończąc, sprzedam Wam anegdotkę, że pisząc ten test dość boleśnie przekonałem jak wiele daje buforowanie. Wczytując po jednej linii z UART’u duża bateria testowa TestU01 wykonywała się 3h i końca nie było widać podczas gdy zaimplementowałem wczytywanie bufora po 256 znaków czas skrócił się do… o ile mnie pamięć nie myli pół godziny. W tym momencie przypomniałem sobie cytat twórcy jądra systemu Linux, Linusa Torvaldsa, który słynie z dość „obrazowego” języka:

„Chciałbym również zasugerować, że należałoby wstecznie zaabortować każdego geniusza, który pomyślał, że czytanie danych przy pomocy JEDNEGO J*BANEGO BAJTU NA RAZ przez wywołania systemowe to dobry pomysł. Kto, do cholery, robi tak debilne rzeczy? Jak to się stało, że nie umarł jako dziecko – mając na uwadze, że prawdopodobnie był za głupi na znalezienie cycka, którego miał ssać.”

Całe szczęście on tego nie widział i to było tylko na chwilę 😉! Tymczasem chciałbym się z Wami pożegnać, a w kolejnym artykule pokażę Wam małe matematyczne czary mary – zajmiemy się tak zwanymi dowodami o wiedzy zerowej.

Pozdrawiam,
Paweł

UWAGA KOŃCOWA 1 – Jak tutaj się prezentuje algorytm RC4? Pewne sekwencje bajtów pojawiają się nieco częściej niż inne co zostało wykorzystane w ataku Fluhrera-Mantina-Shamira. Analizując dużą liczbę wiadomości zaszyfrowanych tym samym kluczem, można odzyskać klucz co pozwoliło złamać standard szyfrowania WiFi WEP (co przyśpieszyło rozwój standardu WPA). Istnieje jednak możliwość obrony przed tym atakiem – należy odrzucić początkową (co najmniej pierwsze 1024 bajty) porcję danych ze strumienia szyfrującego.

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!

Cześć!

W tym artykule chciałbym przedstawić Wam świat, w którym wszyscy żyjemy w nieco innym świetle. Kryptografia, jest to pojęcie o którym wiele osób słyszało, jednak nie dostrzega go na co dzień. Mam nadzieję to zmienić i pokazać Wam jej podstawowe narzędzia.

Zazwyczaj pierwsze skojarzenia odnośnie kryptografii dotyczą świata militariów – często myślimy o wojnie, enigmie i szpiegach przesyłających tajne depesze. Prawda jest jednak zupełnie inna. Obecnie, w dobie Internetu, w świecie cywilnym ma ona o wiele szerszą liczbę zastosowań niż było to we wcześniejszych wiekach. Zanim podam Wam ich przykłady musimy ustalić jakie są jej podstawowe cele.

Często w kręgu osób zainteresowanych bezpieczeństwem w tym miejscu mówi się o modelu zwanym triadą CIA. Wiem o czym myślicie ale nie, nie ma ona nic wspólnego ze słynną amerykańską agencją wywiadowczą a z oczekiwanymi własnościami informacji:

• Confidentiality – poufność, tylko określone osoby są w stanie zrozumieć informację,
• Integrity – integralność, wszelkie manipulacje informacją muszą zostać wykryte przez odbiorcę,
• Availability – dostępność, dostęp do informacji musi być uwierzytelniony.

Triada CIA opisuje cele, które uzyskujemy dzięki kryptografii. Najpowszechniejszym miejscem, w którym stykamy się z kryptografią jest Internet.

Gdzie jest kryptografia w naszym życiu?

Kilka lat temu, tuż po tym, gdy zapłaciłem za wizytę dentystyczną, mój lekarz zadał jedno pytanie – „Przepraszam, czy nie jest Pan przypadkiem informatykiem?”. Zapaliła mi się z tyłu głowy obawa przed syndromem darmowego informatyka (który zawsze i wszędzie udziela bezpłatnej pomocy) ale jednak chęć pomocy zwyciężyła, zwłaszcza, że chwilę wcześniej uratował mnie od wielkiego bólu zęba, więc odpowiedziałem zgodnie z prawdą.

Dzień wcześniej otworzył bowiem załącznik, który miał być fakturą a okazał się wirusem. Lekarz zaobserwował jeden objaw. Próba odwiedzenia poczty Google’a oraz kalendarza kończyła się komunikatem „Twoje połączenie nie jest prywatne”. Historię zwieńczyło pytanie, czy da się ominąć komunikat i przejść do usług Google’a pomimo braku szyfrowania. Niestety odpowiedź powinna brzmieć, tak ale nie należy z niej korzystać. Prawda jest taka, że większość usług, z których korzystamy w Internecie jest szyfrowana. Poniżej możecie porównać w jaki sposób wyglądają informacje wysyłane przez naszą przeglądarkę do strony internetowej z szyfrowaniem i bez.

Zrzut ekranu zawiera przykładowy zapis transmisji poprzez Wi-Fi gdzie komunikacja jest szyfrowana. Możecie zauważyć drobną wzmiankę, że wykorzystywany jest protokół HTTP2, który jest ukryty poprzez TLS’a. Nie szyfrowana komunikacja wygląda natomiast tak:

Sekcja Hypertext Transfer Protocol zawiera niezaszyfrowany ładunek informacji.

Kolejnym przykład kryptografii w naszych domach stanowią routery. Komunikacja pomiędzy urządzeniami w sieciach Wi-Fi nie zawsze przebiega bez zakłóceń. Dzięki niej jesteśmy np. w stanie wykryć przynajmniej część przekłamań w transmisji. Protokół TCP (schemat komunikacji wykorzystywany do łączności z Internetem) wymaga stosowanie dodatkowych kodów aby zapewnić integralność transmisji.

Sumy kontrolne (zakreślone żółtym podkreślaczem pole Checksum) pozwalają wykryć nieprawidłowe pakiety w sieci – może do tego dojść z wielu różnych powodów jak np. zbyt słabego sygnału czy przeszkody fizyczne takie jak ściany.

W jaki sposób zaszyfrować wiadomość?

Teraz, kiedy mamy pewne wyobrażenia dotyczące kryptografii w życiu codziennym chciałbym dać Wam pewien przedsmak tego czym będziemy zajmować się w kolejnych artykułach. Zaczniemy więc od problemu szyfrowania na przykładzie szyfru Cezara – miał być on używany przez niego do poufnej komunikacji ze swoimi przyjaciółmi. Ciekawe, czy również z Brutusem…

Opowiem Wam zaraz pewną bajkę. Musicie wiedzieć, że bajki kryptograficzne mają pewien element wspólny z komediami romantycznymi. W obu gatunkach mamy dwóch głównych bohaterów, w życiu których pojawia się trzecia, która odkąd się pojawiła to miesza
w zaistniałej wcześniej sytuacji. Bohaterowie naszej bajki nazywają się Juliusza Cezar, Marek Krassus oraz Gnejusz Pompejusz. Istnieli jak pewnie wiecie naprawdę, ale historia ta została całkowicie zmyślona.

Dawno, dawno temu, za siedmioma lasami, za siedmioma górami… No dobrze, w starożytnym Rzymie , istniał sojusz trzech wielkich mężów – wymienionego wcześniej Juliusza, Gnejusza i Marka. Trudno mówić w ich przypadku o wielkiej miłości (całe szczęście) a nawet przyjaźni. Najbliżej tej relacji do czegoś w rodzaju małżeństwa z rozsądku. Otóż Marek wybierał się na wojnę z Partami i zastanawiał się w jaki sposób informować Cezara o postępach kampanii tak żeby ani Gnejusz, ani Asteriks i Obeliks z odległej Galii przechwyciwszy wiadomość nie potrafili jej zrozumieć.

Juliusz-kryptograł pomyślał sobie: „Kurcze, przecież musi dać się jakoś tak zmodyfikować tekst żeby nie dało się go zrozumieć a później odwrócić ten proces…”. Myślał nad tym problemem kilka dni aż w końcu wymyślił! Czemu by nie przesuwać liter alfabetu o 3, tj. zamieniać litery A na D, B na E, C na F, itd ….? Przecież ten proces da się odwrócić! Jak pomyślał tak zrobił.

Tabela przekształceń

Przed przekształceniem

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

W

V

X

Y

Z

Po przekształceniu

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

W

V

X

Y

Z

A

B

C

Przykład:
Tekst jawny: ALA MA KOTA
Tekst poufny: DOD PD NRVD

Wiadomość, po przesunięciu liter o 3 podobna sama do siebie za bardzo nie była, natomiast po odwróceniu procesu na uzyskanej wiadomości uzyskał oryginalną. Voila! Problem rozwiązany.

Dzisiaj proces pierwszy nazywamy szyfrowaniem, gdyż służy on transformacji tekstu jawnego (plaintext) w tzw. szyfrogram (ciphertext, tekst poufny) z wykorzystaniem pewnego klucza (w przypadku szyfru Cezara jest nim wielkość przesunięcia). Proces odwrotny tj. transformacja szyfrogramu w tekst oryginalny nazywamy natomiast deszyfracją. W kolejnych artykułach przekonacie się, że klucz szyfrowania i deszyfrowania nie muszą być koniecznie takie same. Matematyk powiedział by, że szyfrowanie i deszyfrowanie są to takie funkcje Encrypt i Decrypt, że:

Wszystko ładnie i pięknie, Cezar z Krassusem czuli się w pełni komfortowo i bezpiecznie, do tego stopnia, że poruszali nawet bardziej intymne tematy. Czy słusznie?

Tutaj pojawia się trzeci bohater, gnuśny (a przynajmniej na potrzeby tej opowieści) Gnejusz, który przechwycił wiadomość. Spojrzał i na pierwszy rzut oka nic nie rozumie… Trochę tak,
jak w piosence  Voulez-vous coucher avec moi zespołu Aquarium:

Trzymam w mym ręku list, ale widzę tylko litery
Nie pamiętam nawet, jak złożyć z nich słowa.

Boris GrebensHchikov – Voulez-Vous coucher avec moi

Mimo wszystko Gnejusz okazał się być szczwanym lisem, pomyślał: „Alfabet łaciński nie jest taki długi, to tylko 26 liter…”, poza tym podsłuchał kiedyś gdy dwaj „przyjaciele” rozmawiali o jakimś przesunięciu… Wziął wszystkich swoich 25 greckich niewolników, którzy uczyli jego dzieci matematyki i kazał każdemu z nich postąpić tak: pierwszy niewolnik zamieniał B na A, drugi C na A itd…. Odkrył, że ten podstawiający z przesunięciem o 3 stworzył sensowny tekst. Sekrety Juliusza Cezara oraz Marka Krassusa nie były już dłużej bezpieczne.

W XIX wieku holenderski kryptograf Auguste Kerckhoffs ukuł kilka zasad, które można streścić w zdaniu bezpieczeństwo systemu kryptograficznego powinno być oparte na tajności klucza a nie procedur. Poza tym przestrzeń kluczy powinna być na tyle duża by nie można było ich efektywnie sprawdzić poprzez przegląd wszystkich możliwości jak to zrobił nasz Gnejusz.

Pojawia się w tym momencie kolejne pytanie, czy gdybyśmy zamiast przesunięć stworzyli losową tablicę podmian znaków byłoby to trudniejsze do złamania? W końcu takich tablic jest 26! (26 * 25 * … * 1) czyli 403 291 461 126 605 635 584 000 000, czyli chyba więcej niż dzisiaj jest mieszkańców globu. Na ówczesne czasy chyba tak, na dzisiejsze już nieco mniej.

Dla każdego języka charakterystyczną cechą jest prawdopodobieństwo z jakim występują różne litery – nazywamy to po angielsku footprint’em. Jeśli przeanalizujemy nawet takie losowe przyporządkowanie to dla stosownych znaków, proporcje zostaną zachowane i łatwo możemy odzyskać tabelę przekształceń.

Sen nocy letniej	Hamlet	Tytus Andronikus	Juliusz Cezar
e – 0.125070 t – 0.089611 o – 0.082563 a – 0.073165 i – 0.067040 n – 0.064873 r – 0.063607 s – 0.062375 h – 0.060174 l – 0.042804 d – 0.037934 u – 0.034204 m – 0.030064 y – 0.025354 w – 0.023495 c – 0.022468 f – 0.019651 g – 0.018613 p – 0.018237 b – 0.015545 v – 0.009261 k – 0.008850 j – 0.001688 q – 0.001437 x – 0.001380 z – 0.000160	e – 0.119177 t – 0.094475 o – 0.090922 a – 0.072433 i – 0.070513 n – 0.066361 s – 0.061381 r – 0.061328 h – 0.058782 l – 0.041492 d – 0.035600 u – 0.031561 m – 0.028901 c – 0.025002 f – 0.024669 y – 0.021922 w – 0.020429 g – 0.019023 p – 0.018363 b – 0.013724 v – 0.009891 k – 0.008652 x – 0.001613 q – 0.001586 j – 0.001520 z – 0.000387	e – 0.116557 t – 0.091163 o – 0.079234 a – 0.076153 s – 0.070158 r – 0.066631 i – 0.066056 n – 0.063976 h – 0.062430 l – 0.042079 d – 0.040791 u – 0.039810 m – 0.031577 y – 0.023036 w – 0.022481 c – 0.022115 f – 0.018478 b – 0.016279 p – 0.015238 g – 0.015040 v – 0.010047 k – 0.006777 x – 0.001496 j – 0.001120 q – 0.000941 z – 0.000337	e – 0.111776 t – 0.090989 o – 0.079855 a – 0.078732 s – 0.074840 i – 0.069186 r – 0.064229 n – 0.062292 h – 0.054276 u – 0.043762 l – 0.039957 d – 0.037449 c – 0.029907 m – 0.026944 y – 0.023323 w – 0.021900 f – 0.019925 b – 0.018240 g – 0.016004 p – 0.015713 v – 0.009188 k – 0.007784 j – 0.001249 x – 0.001046 z – 0.001026 q – 0.000397

Otello	Król Lear	Makbet	Romeo i Julia
e – 0.118021 o – 0.093300 t – 0.089555 a – 0.075691 i – 0.072920 s – 0.064400 n – 0.062901 h – 0.059833 r – 0.056231 l – 0.044050 d – 0.040107 u – 0.031610 m – 0.029905 c – 0.023494 y – 0.023396 w – 0.021660 f – 0.020160 g – 0.020030 p – 0.015265 b – 0.014678 v – 0.010811 k – 0.008557 j – 0.001355 x – 0.001226 q – 0.000624 z – 0.000206	e – 0.123370 t – 0.091010 o – 0.082386 a – 0.074466 r – 0.066092 n – 0.064729 i – 0.061943 s – 0.061511 h – 0.059232 l – 0.045270 d – 0.040576 u – 0.033572 m – 0.028211 c – 0.024047 y – 0.023805 w – 0.023063 g – 0.021867 f – 0.021526 p – 0.015605 b – 0.014197 k – 0.010820 v – 0.009252 j – 0.001355 x – 0.001287 q – 0.000606 z – 0.000197	e – 0.136079 t – 0.091050 o – 0.078711 a – 0.075283 n – 0.063903 s – 0.063343 h – 0.062361 i – 0.060133 r – 0.058979 l – 0.042537 d – 0.039887 u – 0.035202 m – 0.029912 c – 0.026279 w – 0.023548 y – 0.022760 f – 0.020612 g – 0.018212 b – 0.017812 p – 0.014785 k – 0.009038 v – 0.004879 x – 0.002342 q – 0.001497 j – 0.000514 z – 0.000343	e – 0.119085 t – 0.092119 o – 0.082889 a – 0.076255 i – 0.065469 r – 0.064054 n – 0.062439 h – 0.061715 s – 0.061532 l – 0.044045 d – 0.037029 u – 0.034058 m – 0.031761 y – 0.024470 w – 0.023845 c – 0.022922 f – 0.020649 g – 0.018860 b – 0.016862 p – 0.016563 v – 0.009755 k – 0.008240 j – 0.003129 x – 0.001332 q – 0.000633 z – 0.000291

Jako próbkę danych wykorzystałem oryginalne teksty różnych sztuk Szekspira ze strony projektu Guttenberg. Możecie zauważyć, że statystyki wyglądają dość podobnie. Im dłuższy tekst próbujecie zdeszyfrować, tym dokładniej będzie działać odtworzona tablica. Na stronie repozytorium https://gitlab.com/sisiphus-on-code/cryptography, w katalogu caesar-cipher znajdziecie źródła do programów wykorzystanych do statystyk, testowe pliki oraz eksperyment z deszyfrowaniem bazując na statystykach występowania znaków.

Możecie zauważyć w tym miejscu, dwa typy problemów:

• W jaki sposób zabezpieczyć poufność komunikacji?
• W jaki sposób możemy przeanalizować przechwycone informacje aby odzyskać lub podmienić chociaż część danych nie znając klucza?

Na pierwsze pytanie odpowiada kryptografia a na drugie kryptoanaliza a oba zagadnienia  są przedmiotem nauki o nazwie kryptologia.

Jakie narzędzia zapewnia nam kryptografia

Teraz kiedy zobaczyliście przykład w jaki sposób możemy (chociaż może nieco nieudolnie,
w kolejnych artykułach przedstawię Wam lepsze sposoby) zapewniać poufność korespondencji, pewnie jesteście ciekawi co jeszcze będzie elementem naszego narzędziowego przybornika.

Poniżej znajdziecie krótkie zastawienie narzędzi, które zobaczycie w kolejnych wpisach:

Narzędzie	Opis i zastosowanie
Algorytmy szyfrowania	Algorytmy, które umożliwiają odwracalne zmodyfikowanie zawartości wiadomości aby uniemożliwić jej odczytanie.
Podpisy cyfrowe	Protokoły wykorzystujące algorytmy szyfrowania asymetrycznego (tj. klucz szyfrowania jest inny od klucza deszyfrowania) aby umożliwić potwierdzenie np. kto jest nadawcą wiadomości.
Funkcje hashujące (skrótu)	Przypisanie większemu pakietowi informacji charakterystycznej wartości liczbowej o stałym rozmiarze w sposób nieodwracalny.
Kody korekcyjne	Dodatkowa informacja dodawana do wiadomości dzięki której gdy pojawiły się przekłamania transmisji wiadomość można próbować odzyskać.
(H)MAC – kody uwierzytelnienia wiadomości	Algorytmy zapewniające integralność wiadomości (nie muszą zapewniać pewności, kto nadał daną wiadomość).

Wszystkie te narzędzia są łączone w większą całość – bardziej skomplikowane protokoły
i kryptosystemy. U ich podstaw natomiast leżą pewne zagadnienia związane z matematyką tj. liczby losowe, problemy teorio-liczbowe (np. problem dyskretnego logarytmu albo rozkładu liczb na czynniki pierwsze), kombinatoryka i rachunek prawdopodobieństwa.

W kolejnych wpisach postaram się przybliżyć Wam szczegóły w jaki sposób działają powyższe narzędzia a tymczasem najwyższy czas kończyć na dziś!

Do zobaczenia 😊