Szyfry współczesne

Szyfry współczesne

Współcześnie możemy podzielić metody szyfrowania na 3 grupy:

  1. szyfry asymetryczne

  2. symetryczne szyfry blokowe

  3. symetryczne szyfry strumieniowe

a) Szyfry asymetryczne

W szyfrowaniu asymetrycznym występują 2 klucze – klucz publiczny służący do szyfrowania, oraz klucz prywatny służący do deszyfrowania. Ponieważ nie ma potrzeby rozpowszechniania klucza prywatnego, bardzo małe są szanse, że wpadnie on w niepowołane ręce. Szyfry asymetryczne opierają się na istnieniu pewnych trudnych do odwrócenia problemów. Np. o wiele łatwiej jest pomnożyć przez siebie 2 duże liczby, niż rozłożyć dużą liczbę na czynniki (opiera się na tym system RSA). Drugim popularnym systemem jest ElGamal1, opierający się na trudności logarytmu dyskretnego. Typowe rozmiary kluczy są rzędu 1024-2048 bitów. W przypadku RSA złamane zostały klucze rozmiarów do ok. 500 bitów.

b) Szyfry blokowe

Szyfry blokowe to procedury, które szyfrują niewielkie bloki danych (znacznie mniejsze od typowej wiadomości), współcześnie jest to najczęściej 128 bitów (AES), choć do niedawna przeważały 64-bitowe bloki (DES, 3DES, Blowfish, IDEA). Klucze są znacznie mniejsze, mają zwykle od 128 do 256 bitów, przy czym wartości mniejsze od 80 (DES – 56) są uważane za niewystarczające. Typowy szyfr blokowy składa się
z kilkunastu dość prostych rund przekształcających blok. Operacje używane w tych szyfrach są zwykle proste, ale pochodzą z „różnych światów”, np. używa się dodawania, użycia funkcji XOR, przesunięć cyklicznych, mnożenia modulo liczb pierwszych itd. Już kilka rund takich operacji zupełnie zaburza jakikolwiek porządek i jest bardzo trudne do analizowania.

Ponieważ szyfr blokowy szyfruje jedynie niewielką ilość informacji, używane są różne tryby szyfrowania, które umożliwiają szyfrowanie większych wiadomości.

Główne tryby to:

W kryptografii CBC – Cipher Block Chaining to tryb kodowania wiadomości za pomocą szyfru blokowego, w którym przed zaszyfrowaniem każdy z bloków wiadomości jest przekształcany funkcją XOR z szyfrogramem uzyskanym
z szyfrowania poprzedniego bloku wiadomości. Pierwszy blok wiadomości jest szyfrowany za pomocą wylosowanego ciągu bitów (IV, initial vector) dołączanego
do wiadomości.

Wzory na kodowanie:

C0 = IV

Wzory na dekodowanie:

CFB – Cipher Feedback Tryb użycia szyfru blokowego pozwalający na użycie go do kodowania strumieni danych. Szyfr blokowy jest używany do wygenerowania pseudolosowego ciągu danych, który następnie pełni rolę strumienia szyfrującego mieszanego z danymi za pomocą funkcji XOR.

Opis algorytmu:

  • Wybieramy losowy, jawny blok danych, zwany wektorem inicjującym. Jego długość jest zależna od wybranego szyfru i jest równa długości bloku, na którym operuje szyfr.

  • Szyfrujemy go za pomocą tajnego klucza.

  • Poddajemy wynik z wiadomością funkcji XOR i uzyskujemy fragment szyfrogramu.

  • Uzyskany fragment szyfrogramu po zaszyfrowaniu z użyciem tego samego klucza szyfrującego stanowi kolejny fragment strumienia szyfrującego.

CTR – Counter Tryb użycia szyfru blokowego pozwalający na użycie go
do kodowania strumieni danych. Szyfr blokowy jest używany do wygenerowania pseudolosowego ciągu danych, który następnie pełni role strumienia szyfrującego mieszanego z danymi za pomocą funkcji XOR.

Opis algorytmu:

  • Wybieramy jawną funkcję, która na podstawie pozycji bloku danych względem początku strumienia generuje ciąg danych o długości równej długości bloku szyfru blokowego, wymagane jest by funkcja ta zwracała wartości pseudolosowe.

  • Wynik funkcji szyfrujemy szyfrem blokowym.

  • Poddajemy wynik z wiadomością funkcji XOR i uzyskujemy fragment szyfrogramu.

Jest to najpopularniejszy tryb pracy szyfrów blokowych. W przeciwieństwie
do CFB i OFB pozwala odszyfrować dowolny fragment danych, bez konieczności odszyfrowywania wszystkich poprzedzających.

OFB – Output Feedback Tryb użycia szyfru blokowego pozwalający na użycie go do kodowania strumieni danych. Szyfr blokowy jest używany do wygenerowania pseudolosowego ciągu danych, który następnie pełni role strumienia szyfrującego mieszanego z danymi za pomocą funkcji XOR.

Opis algorytmu:

  • Wybieramy losowy, jawny blok danych, zwany wektorem inicjującym. Jego długość jest zależna od wybranego szyfru i jest równa długości bloku, na którym operuje szyfr.

  • Szyfrujemy go za pomocą tajnego klucza.

  • Uzyskany ciąg danych stanowi:

    • Początek strumienia szyfrującego dla funkcji XOR.

    • Tekst jawny, którego zaszyfrowanie dostarczy nam kolejny fragment strumienia szyfrującego.

Niektóre szyfry blokowe to:

Rijndael/AES

Szyfr AES może operować na bloku o zmiennej długości, używając kluczy zmiennej długości. Oficjalna specyfikacja dopuszcza użycie bloków 128-, 192- lub 256-cio bitowych, szyfrowanych kluczami 128-, 192- lub 256-cio bitowymi. Dopuszczalne są wszystkie z 9 kombinacji.

Rijndael jest „iterowanym szyfrem blokowym”, co oznacza, że blok wejściowy oraz klucz przechodzą wielokrotne RUNDY transformacji, zanim wyprodukują wynik. Po każdej rundzie, powstaje szyfr pośredni, zwany STANEM (State).2

Serpent

Serpent (ang. „wąż”) był kolejnym finalistą konkursu AES3. Jego konstrukcja przypomina czołg. Jest to propozycja najbardziej zachowawcza spośród wszystkich przesłanych do AES, pod wielo­ma względami odmienna od ostatecznie wybranego laureata. O ile AES największy nacisk kładzie na elegancję i wydajność, Serpent został zaprojektowany wyłącznie z myślą o bezpieczeństwie. Naj­lepszy znany atak obejmuje jedynie 10 z 32 istniejących tur . Wadą algorytmu Serpent jest jego szybkość: jest on trzykrotnie wolniejszy od AES.

Pod pewnymi względami Serpent przypomina AES. Składa się on z 32 tur. Każda tura obej­muje przekształcenie przez XOR względem 128-bitowego klucza tury, użycie 128-bitowej liniowej funkcji mieszającej i równoległe zastosowanie 32 czterobitowych S-boksów. Wszystkie 32 S-boksy są identyczne dla wszystkich tur, ale do dyspozycji jest osiem różnych S-boksów, których używa się po kolei w następujących turach.

Algorytm Serpent wykorzystuje pewne szczególnie pomysłowe rozwiązanie programowe. Zwykła implementacja byłaby bardzo powolna, gdyż w każdej z 32 tur konieczne jest przejrzenie 32 S-boksów. Łącznie oznaczałoby to konieczność przejrzenia 1024 S-boksów, co może trwać bardzo długo. Sztuczka polega na zastąpieniu S-boksów wyrażeniami logicznymi (boolowskie). Każdy z czterech bitów wynikowych jest wyrażany w postaci funkcji boolowskiej czterech bitów wej­ściowych. Procesor bezpośrednio oblicza wartość funkcji korzystając z operacji AND, OR i XOR. Najważniejszy jest fakt, że w 32-bitowych procesorach można równolegle obliczać transformację przez wszystkie 32 S-boksy, gdyż każdy bit wynikowy opisany jest tą samą funkcją, choć działającą na różnych danych wejściowych. Tego rodzaju implementację nazywamy implementacją plasterkową (ang. bitslice). Serpent został zaprojektowany specjalnie z myślą o takiej implementacji. Prze­prowadzenie fazy mieszania jest w niej względnie proste.4

Gdyby Serpent był tak szybki jak Rijndael (obecnie AES), prawie na pewno zostałby wybra­ny jako algorytm AES, a to z uwagi na jego konserwatywną konstrukcję. Jednak szybkość jest pojęciem względnym. Jeśli mierzymy ją względem liczby szyfrowanych bajtów, Serpent jest pra­wie tak szybki jak DES i znacznie szybszy od 3DES. Serpent jest powolny jedynie w porównaniu z pozostałymi finalistami konkursu AES.

Skipjack

Algorytm Skipjack to tajny algorytm opracowywany w latach 1987-1993 przez NSA5 jako narzędzie do zapewniania bezpiecznej komunikacji głosowej oraz do wymiany danych z jednoczesnym umożliwieniem kontroli i podsłuchu przez uprawnione agencje rządu USA. Urządzenia działające w systemie SKIPJACK
(np. telefony) mają zainstalowany odporny na ingerencje układ scalony. Dystrybucja kluczy odbywa się ręcznie.

SKIPJACK szyfruje 64-bitowe bloki w 32 etapach za pomocą 80-bitowego klucza. Zakładając, że dysponuje się hipotetyczną maszyną złożoną z 1, 2 miliarda jednodolarowych układów scalonych z zegarem 1 GHz i szyfrowaniem potokowym
w jednym cyklu zegara zakres kluczy SKIPJACK wyczerpałby się po upływie roku.

3DES

3DES to algorytm polegający na zakodowaniu wiadomości DESem trzy razy:

  1. kodujemy pierwszym kluczem

  2. dekodujemy drugim kluczem

  3. kodujemy trzecim kluczem

c = E3(D2(E1(m)))

Użycie dekodowania jako drugiej fazy nie wpływa na siłę algorytmu (dekodowanie w DESie jest identyczne jak kodowanie, tylko ma odwróconą kolejność rund), ale umożliwia używania 3DESa w trybie kompatybilności z DESem – za klucz pierwszy i drugi, lub drugi i trzeci przyjmujemy dowolny taki sam klucz, a za ostatni zwykły klucz DESowski:

c = E3(D1(E1(m))) = E3(m)

c = E3(D3(E1(m))) = E1(m) 6

3DES używa takich samych rozmiarów bloków oraz trybów jak zwykły DES. Siła 3DESa jest tylko dwukrotnie, nie trzykrotnie większa od siły zwykłego DESa.

Blowfish

Blowfish to szyfr blokowy stworzony przez Bruce’a Schneier’a w 1993 roku jako szybka i bezpłatna alternatywa dla istniejących ówcześnie algorytmów.

Algorytm operuje na 64-bitowych blokach i używa kluczy od 32 do 448 bitów.

Algorytm ma postać szyfru Feistela z 16 rundami z SBOXami zależnymi od klucza. Każda zmiana klucza wymaga dość sporej ilości wstępnych obliczeń, żeby ustalić SBOXy. Z tego powodu atak brute-force trwa znacznie dłużej niż można by się spodziewać.

W typowych algorytmach jeśli długość klucza to k, a koszt zakodowania bloku to B, koszt ataku brute-force wynosi 2kB. W przypadku Blowfisha trzeba dla każdego klucza obliczyć SBOXy, co zajmuje tyle co zakodowanie ok. 29 bloków, a więc czas ataku brute-force wynosi około 2k + 9B (a zatem atak na 64-bitowy Blowfish zajmuje mniej więcej tyle czasu co na 73-bitowy bardziej tradycyjny szyfr). Wadą tego rozwiązania są dość duże wymagania pamięciowe – potrzebne są ponad 4kB pamięci, co nie jest problemem dla nawet słabych komputerów, ale jest już dla np. kart chipowych.7

Nie istnieją (2004) znane ataki na Blowfisha o ilości rund większej niż 4.
Są znane dość duże jak na symetryczny szyfr blokowy grupy słabych kluczy, czyli takich, dla których Blowfish jest słabszy niż dla typowych kluczy (większość szyfrów posiada takowe, jednak szansa na wylosowanie takiego klucza jest bardzo niska).

Twofish

Twofish był następnym finalistą AES. Można go traktować jako kompromis między AES a Serpent. Jest on niemal tak szybki jak AES, ale zapewnia wyższy poziom bezpieczeństwa. Co ważniejsze, nie ma on znanej prostej reprezentacji algebraicznej. Najlepszy znany atak obejmuje 8 z 16 tur. Największą wadą Twofish jest to, że zmiana klucza szyfrującego może być kosztowna, gdyż najlepsza implementacja tego algorytmu wymaga wielu obliczeń wstępnych.

Algorytm Twofish wykorzystuje te same struktury Feistela, co DES. Podczas szyfrowania Twofish 128-bitowy tekst otwarty dzieli się na cztery wartości 32-bitowe, na których wykonywana jest później większość operacji. Funkcja tury składa się
z dwóch wywołań funkcji g, funkcji o nazwie PHT oraz dodawania klucza. Wynik funkcji jest poddawany operacji XOR z pozostałą częścią danych (dwie pionowe kreski na prawo od bloku funkcji).

Każda funkcja g składa się z czterech S-boksów8 i z mieszającej funkcji liniowej bardzo po­dobnej do funkcji mieszającej AES. S-boksy są już nieco inne.
W przeciwieństwie do wszystkich innych omawianych wcześniej szyfrów, tym razem S-boksy nie są stałe: ich zawartość zależy od klu­cza. Specjalny algorytm wylicza tablice S-boksów na podstawie klucza. Uzasadnieniem takiego rozwiązania jest utrudnienie analizy S-boksów potencjalnym włamywaczom. Dlatego właśnie w wielu implementacjach Twofish niezbędne są dodatkowe obliczenia wstępne dla każdego nowego klucza. W ich trakcie wyznacza się nowe S-boksy, które następnie są przechowywane w pamięci.9

Funkcja PHT miesza dwa wyniki funkcji g korzystając z 32-bitowych operacji dodawania.

W algorytmie Twofish zastosowano dodatkowe przetwarzanie wstępne
i końcowe. Polega ono na dodawaniu pewnych informacji z klucza do danych. W ten sposób szyfr trudniej poddaje się większości ataków, zaś wzrost kosztu jest niewielki.

Tak jak w przypadku innych szyfrów, Twofish ma schemat przetwarzania klucza, pozwalający uzyskać klucze tur oraz dwa dodatkowe klucze: początkowy
i końcowy.

DES

DES (ang. Data Encryption Standard – Standard Szyfrowania Danych) – szeroko używany algorytm kryptograficzny. Stworzony przez IBM na podstawie szyfru Lucifer, został zmodyfikowany przez amerykańską NSA. Zaakceptowany jako amerykański standard w roku 1977.10

Algorytm jest następujący:

  • Wykonujemy wejściową permutację danych (IP)

  • Powtarzamy 16 razy następującą operację

    • Przestawiamy bity danych (umieszczenie tej operacji miało na celu preferowanie rozwiązań sprzętowych w których wykonanie tego przekształcenia sprowadza się do odpowiedniego przeprowadzenia połączeń.

    • Dane które dostaliśmy na wejściu rundy dzielimy na dwie 32-bitowe części – lewą Li i prawą Ri

    • Rozszerzamy przez powielanie bitów prawą część do 48 bitów uzyskując E(Ri)

    • Poddajemy funkcji XOR E(Ri) z podkluczem dla aktualnej rundy

    • Rozbijamy na 8 fragmentów po 6 bitów

    • Każdy z tych fragmentów jest argumentem jednej z 8 funkcji, tzw.
      S-BOX-ów.

    • Łączymy wyniki S-BOXów w

    • Permutujemy uzyskany wynik

    • Jako lewą stronę wyjścia przekazujemy prawą stronę wejścia:
      Li + 1 = Ri

    • Jako prawą stronę wyjścia przekazujemy lewą stronę wejścia poddaną funkcji XOR z : 11

  • Wykonujemy odwróconą permutację wejściową danych (IP – 1)

Schemat ten to tzw. sieć Feistela.

Deszyfrowanie polega na zastosowaniu tych samych operacji w odwrotnej kolejności (różni się od szyfrowania tylko wyborem podkluczy, który teraz odbywa się od końca).

Z powodu słabości klucza (56 bitów) został w dużej mierze zastąpiony przez inne szyfry: modyfikacje DESa takie jak 3DES czy DESX, a ostatnio przez nowsze
i bezpieczniejsze algorytmy jak AES, IDEA, Twofish itd.

DES ma 4 słabe i 12 półsłabych kluczy. Szansa na wylosowanie takiego wynosi

, czyli nie wpływa w istotny sposób na siłę szyfru.

DESX

DESX to prosta modyfikacja DESa:

  • blok danych poddajemy funkcji XOR z pierwszym kluczem (64 bitowym)

  • blok szyfrujemy za pomocą DES-a drugim kluczem (56 bitowym)

  • blok danych poddajemy funkcji XOR z trzecim kluczem (64 bitowym)

Klucz ma nietypowy rozmiar 184 bitów (64+56+64).

DESX jest co najmniej tak samo bezpieczny jak DES na wszystkie możliwe ataki, a na niektóre wydaje się być znacznie bardziej odporny. W szczególności klucz jest już na tyle duży, że sprawdzenie wszystkich kluczy jest niepraktyczne.

DESX jest też bardzo szybki (potrzeba tylko dwóch 64-bitowych XORów na blok), w przeciwieństwie do innych modyfikacji DESa takich jak 3DES (który potraja czas wykonywania).12

IDEA

IDEA (International Data Encryption Algorithm) to symetryczny szyfr blokowy operujący na 64-bitowych blokach wiadomości i mający 128-bitowy klucz.

IDEA używa operacji z 3 światów na 16-bitowych liczbach:

  • XOR

  • Dodawanie modulo 216

  • Mnożenie modulo 216 + 1 (które jest liczbą pierwszą), przy czym liczba 0 jest traktowana jako 216.

IDEA była używana we wczesnych wersjach PGP.

IDEA jest objęta patentem w USA, i jest dostępna do darmowego użytku tylko w celach niekomercyjnych.

Ze względów patentowych oraz ze względu na powstanie lepszych algorytmów (AES) i postępy w kryptoanalizie IDEA znacznie straciła na popularności, choć nie została nigdy złamana.

c. Szyfry strumieniowe

Szyfry strumieniowe szyfrują każdy znak tekstu jawnego osobno, generując znak strumienia szyfrującego i przekształcając go na przykład z użyciem funkcji XOR go ze znakiem danych, w związku z czym nie jest konieczne oczekiwanie na cały blok danych, jak w przypadku szyfrów blokowych. Najpopularniejszym współczesnym szyfrem strumieniowym jest RC4, którego stosowanie jest ograniczone ze względu na
warunki licencyjne. Inne popularne szyfry strumieniowe to A5/1 i A5/2 stosowane
w telefonii komórkowej. Do szyfrów strumieniowych należą też historyczne szyfry polialfabetyczne i monoalfabetyczne.

Niektóre z trybów szyfrów blokowych – CFB, OFB, CTR – działają jako szyfry strumieniowe, generując strumień szyfrujący i przekształcając dane za pomocą funkcji XOR.

Szyfr strumieniowy (stream cipher) to szyfr symetryczny, który koduje generując potencjalnie nieskończony strumień szyfrujący (keystream), i XOR-ując go
z wiadomością:

Odszyfrowywanie zakodowanej wiadomości odbywa się w identyczny sposób – generujemy strumień szyfrujący, i XOR-ujemy go z szyfrogramem:

13

Przypis:

Istnieją szyfry strumieniowe oparte na generatorach liczb pseudolosowych – jeśli generator jest kryptograficznie silny, to jądro generatora może służyć jako klucz,
a generowany strumień pseudolosowych liczb jako strumień szyfrujący. Blum Blum Shub14 jest przykładem generatora, dla którego (co rzadkie w kryptografii) istnieje dowód, że złamanie go jest co najmniej równie trudne jak rozbicie liczby stanowiącej klucz na czynniki.

Szyframi strumieniowymi są też tryby CFB, OFB i CTR szyfrów blokowych. Generują one z samego klucza i z wektora inicjalizującego (nie korzystając z danych) strumień szyfrujący, po czym używają funkcji XOR do połączenia go z danymi.

1 ElGamal– jeden z dwóch najważniejszych systemów kryptografii asymetrycznej (drugim jest RSA). System jest oparty na trudności problemu logarytmu dyskretnego w ciele liczb całkowitych modulo duża liczba pierwsza.

2 http://e-handel.mm.com.pl/crypto/aes.htm

3 AES-ang. Advanced Encryption Standard- zaawansowany standard szyfrowania, symetryczny algorytm szyfrujący Rijndael, który w 2000r. został zwycięzcą ogłoszonego przez NIST konkursu, algorytm ma docelowo zastąpić mało bezpieczny już DES.

4 N. Ferguson, B. Schneider: Kryptografia w praktyce, Wydawnictwo Helion, Gliwice 2004, s. 57

5 NSA (National Security Agency) Agencja Bezpieczeństwa Narodowego – głęboko utajniona amerykańska agencja wywiadowcza, koordynująca całość operacji SIGINT, powstała w kwietniu 1952 roku.

6 http://pl.wikipedia.org/wiki/3DES

7 http://ochrona.bajo.pl/szyfrprog.php

8 S-Box (Substitution Box) – podstawowy element wielu współczasnych szyfrów (np. DES). Istota jego działania polega na podstawieniu ciągu bitów innym, w zależności od bitów: poprzedzającego
i następujacego.

9 N. Ferguson, B. Schneider: Kryptografia w praktyce, Wydawnictwo Helion, Gliwice 2004, s. 58

10 http://pl.freeglossary.com/DES

11 http://pl.wikipedia.org/wiki/DES

12 http://ochrona.bajo.pl/szyfrprog.php

13 http://pl.wikipedia.org/wiki/szyfr_strumieniowy

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *