Kryptografia – szyfry strumieniowe

Dzisiaj chcemy Wam opowiedzieć o tym jak działają szyfry strumieniowe, czym są rejestry LSFR i gdzie takich szyfrów strumieniowych używamy. Jeśli jesteście zainteresowani niskopoziomowym działaniem algorytmów szyfrujących i innych konceptów bliskich kryptografii to zapraszamy!

Wstęp

Aby dobrze zrozumieć jak działają poszczególne algorytmy szyfrowania, trzeba uświadomić sobie, że szyfry symetryczne – czyli takie, które używają tego samego klucza do szyfrowania i deszyfrowania wiadomości – dzielą się na szyfry blokowe i szyfry strumieniowe. Szyfry blokowe są stosowane głównie w Internecie, natomiast strumieniowe tam, gdzie jest mało zasobów np. w systemach wbudowanych, czy bluetooth, choć znajdą się wyjątki od tej reguły. Oba te podejścia mają swoje wady i zalety oraz wiele podtypów posiadających specyficzne cechy. Szyfry blokowe łączą fragmenty bitów tekstu jawnego z bitami kluczy, aby utworzyć szyfrogram o tym samym rozmiarze. Szyfry strumieniowe nie łączą natomiast bezpośrednio tekstu jawnego z bitami kluczy, a generują pseudolosowe bity z użyciem klucza, na którym następnie wykonują działanie XOR.

Rysunek 1 – Przykład szyfru stumieniowego RC4, źródło wentzwu.com

Rysunek 2  – Podstawowy koncept szyfru blokowego, źródło thesslstore.com

Szyfry strumieniowe – podstawy

Szyfry strumieniowe, zgodnie z tym co powiedzieliśmy i pokazaliśmy na powyższym rysunku 1, szyfrują bit po bicie. Są one podobne do DRNG (ang. Deterministic Random Bit Generator), które deterministyczne (to znaczy dla takiego samego wejścia zawsze jest takie same wyjście) produkują sekwencję bitów z wartości początkowej nazywanej seedem. Szyfry strumieniowe natomiast przyjmują dwie wartości: klucz oraz wartość jednorazową, gdzie klucz powinien być wartością tajną, a wartość jednorazowa powinna być unikalna. Oznacza to, że istnieją pewne ograniczenia wynikające z wielkości wartości jednorazowej. Jeśli dana wartość jest 8-bitowa, to mamy 2^8 możliwych wiadomości zanim będziemy musieli zmienić klucz. Jeśli tego nie zrobimy, to pojawia się pewne prawdopodobieństwo, że jeśli pojawią się dwie te same wiadomości będą posiadały ten sam szyfrogram, a cała idea szyfrowania zakłada, że potencjalny atakujący nie powinien wysnuć żadnych wniosków na temat wiadomości bez posiadania klucza.

Rysunek 3 – Działanie szyfru strumieniowego, źródło: javatpoint.com

Po wygenerowaniu pseudolosowych znaków algorytm strumieniowy wykonuje operację XOR na tekście jawnym. Przyjrzyjmy się przez chwilę tabeli prawdy dla tej operacji i jakie szczególne właściwości posiada.

XOR posiada interesującą właściwość pozwalającą na odwrócenie wyniku tzn. jeśli c = p ⊕ k , to c ⊕ k = p ⊕ (k ⊕ k) =  p ⊕ 0 = p

Można to nawet zobaczyć w tabeli prawdy. Wyobraźmy sobie, że X jest bitem tekstu jawnego, a Y bitem wygenerowanego, pseudolosowego ciągu szyfrującego – X ⊕ Y jest więc szyfrogramem. Jeśli X = 0, a Y=1 to X ⊕ Y = 1. Teraz jeśli chcemy przeprowadzić tę operację w drugą stronę, to biorąc  Y=1 to X ⊕ Y = 1 z tabeli prawdy wynika, że jest to 0. Operacja jest więc odwrócona.

Taka właściwość sprawia między innymi, że dla algorytmów strumieniowych nie trzeba posiadać osobnych funkcji szyfrujących i deszyfrujących, ponieważ jest to ta sama operacja XOR, która jest odwracalna.

Rodzaje szyfrów strumieniowych

Istnieje kilka rodzajów szyfrów strumieniowych i można je dzielić na wiele sposobów. Podstawowy podział obejmuje dwie kategorie:

• szyfry strumieniowe stanowe (ang. stateful stream ciphers) – strumień posiada wewnętrzny stan, który zmienia się podczas generowania strumienia np. RC4, Salsa20

Rysunek 4 – Szyfr strumieniowy stanowy, źródło: Aumasson, Serious Cryptography

• szyfry strumieniowe oparte na liczniku (ang. counter-based stream ciphers) – strumień nie posiada wewnętrznego stanu, który zastąpiony jest licznikiem zwiększanym z każdym kolejnym krokiem. N – to tzw. nonce. która powinna być unikalna dla każdego stosowanego klucza (istotne w przypadku rotacji kluczy)

Rysunek 5 – Szyfr strumieniowy oparty na liczniku, źródło: Aumasson, Serious Cryptography

LSFR

Z pojęciem szyfru strumieniowego bardzo mocno powiązana jest koncepcja LSFR (ang. linear feedback shift register). Jest to rejestr przesuwający, którego bit wejściowy jest funkcją liniową jego poprzedniego stanu, który służy do generowania losowych wartości do szyfrów strumieniowych (keystream). Prawidłowe użycie takiego generatora ma bardzo dobre właściwości statystyczne, co jednak nie oznacza, że taki rejestr ma odpowiednie właściwości kryptograficzne.

Rysunek 6 – Budowa rejestru przesuwnego LSFR, źródło: minutesheep

Rejestry przesuwne tego typu z operacją XOR’ującą niektóre bity sprawiają, że reprezentacje bitowe liczb generowane przez ten rejestr są zapętlone. Przykładowo dany rejestr 4-bitowy jest zapętlony w cyklu 16 możliwości (co jest wartością optymalną, bo maksymalną) i generuje liczby binarne od 0000 do 1111. W praktyce oczywiście tego typu rejestry są dłuższe i są zapisywane w postaci wielomianów, gdzie liczba bitów jest największą potęgą danego wielomianu.

Takie rejestry zaprezentowane w postaci wielomianów można następnie dzięki przekształceniom matematycznym optymalizować i sprawiać, że cykle są maksymalnie długie. Robi się tak dlatego, że różne połączenie XOR różnych bitów daje różne efekty tzn. możliwy jest np. rejestr przesuwny 128 bitowy połączony w taki sposób, aby generował jedynie wartości liczbowe od 0-15 na 4 ostatnich bitach, co jest nieoptymalne, bo oznacza to, że nasz generowany keystream będzie miał długość 4 bitów, co jest bardzo słabe i równoważne z wzięciem rejestru o długości 4. Optymalny wielomian tzn. o maksymalnym cyklu musi spełniać pewne właściwości matematyczne jak między innymi bycie wielomianem prymitywnym (odsyłamy do źródeł poniżej). Wielomiany sklasyfikowane jako prymitywne można znaleźć w gotowych tabelach w Internecie.

Bezpieczeństwo LSFR

Pomimo tego, że sam algorytm pozyskiwania losowych bitów ma dobre właściwości statystyczne, to kryptograficznie jest on nienajlepszy. W rejestrach LSFR bitwy wyjściowe i stanu są powiązane przez “m” równań liniowych, które z użyciem sprytnych matematyczno-komputerowych sztuczek można rozwiązać. W praktyce w kryptografii używamy dodatkowych mechanizmów kryptograficznych, aby kryptograficznie ulepszyć koncepcję LSFR. Stosowane są choćby filtrowane rejestry LSFR lub nieliniowe rejestry FSR (NFSR). Wprowadzają one dodatkowe przekształcenia, które sprawiają, że wyżej wymienione liniowe równania potrzebne do złamania szyfru stają się nieliniowe i tym samym niemożliwe lub trudne do rozwiązania.

Gdzie wykorzystywane są szyfry strumieniowe? 

Istnieje wiele miejsc, gdzie korzystamy z szyfrów strumieniowych i są to między innymi:

• stare wersje bluetooth (do 3.0 używano szyfru E0 uznawanego obecnie za niebezpieczny)
• stare wersje zabezpieczeń Wi-Fi (WEP używało szyfru RC4, również jest to obecnie uznawane za niebezpieczne)
• TLS (różne algorytmy strumieniowe (RC4, ChaCha20  – część uznawana za bezpieczne a część nie, polecamy zajrzeć do dokumentacji RFC)
• telefonia komórkowa GSM (algorytm A5, obecnie uznawany za niebezpieczny)

Rysunek 7 – Możliwe mechanizmy bezpieczeństwa dla TLS 1.3 – są zarówno szyfry blokowe jak i chacha20 czyli szyfr strumieniowy.

Czy szyfry strumieniowe są szybsze i bardziej efektywne?

Odpowiedź brzmi: to zależy! Teoretycznie szyfry strumieniowe powinny być szybsze ze względu na mniejszą liczbę i mniejszy poziom skomplikowania operacji. Zależy to jednak od wielu czynników np. implementacji, długości klucza czy długości danych wejściowych. Jednak dzisiejsze, zoptymalizowane implementacje np. AES poprzez choćby dedykowane instrukcje na procesorze i dedykowane układy hardware’owe są zdolne do osiągania takich samych prędkości lub większych zakładając wybranie odpowiedniego trybu blokowego. 

Jeśli chodzi o efektywność szyfrowania to odnosi się ona do ilości zasobów, takich jak pamięć, przepustowość czy energia, wykorzystywanych podczas procesu szyfrowania. Efektywność ma znaczenie w sytuacjach, gdzie zasoby są ograniczone, jak w przypadku systemów wbudowanych, sieci bezprzewodowych czy urządzeń mobilnych. Szyfry strumieniowe wykazują wyższą efektywność w porównaniu do szyfrów blokowych, ponieważ posiadają generalnie mniej kodu, używają mniej pamięci i generują mniejszy narzut komunikacyjny. Co za tym idzie, szyfry strumieniowe powodują mniejsze zużycie energii dzięki mniejszej liczbie obliczeń i generowaniu mniejszej ilości ciepła. Szyfry blokowe wymagają większej alokacji zasobów – zarówno podczas implementacji, jak i działania. 

Podsumowanie

Jak widzicie tematy niskopoziomowe związane z szyfrowaniem wcale nie są łatwe. Za tydzień odejdziemy na chwilę od tematu kryptografii i zajmiemy się innymi aspektami informatyki. Do usłyszenia!

Źródła:

• https://wentzwu.com/2020/07/26/cissp-practice-questions-20200727/ 
• https://www.thesslstore.com/blog/block-cipher-vs-stream-cipher/ 
• https://datatracker.ietf.org/doc/html/rfc8446#page-133 
• https://www.secureideas.com/blog/2020/10/boolean-math-xor-logic-cissp-domain-3.html 
• https://youtu.be/sKUhFpVxNWc
• https://minutesheep.github.io/2020/11/26/stream-cipher/
• https://en.wikipedia.org/wiki/Primitive_polynomial_(field_theory)