Nowoczesna kryptografia. Praktyczne wprowadzenie do szyfrowania - ebook

SŁOWO WSTĘPNE

Każdy, kto przeczytał jedną lub dwie książki o bezpieczeństwie komputerowym, mógł spotkać się z powszechnym poglądem na temat kryptografii. Mówi się że „kryptografia to najsilniejsze ogniwo w łańcuchu”. To stanowcze sformułowanie, ale nieco lekceważące. Jeśli rzeczywiście kryptografia to najsilniejsza część naszego systemu, to po co inwestować swój czas w jej poprawę, jeśli jest tyle innych obszarów systemu, które mogą więcej skorzystać na poświęceniu im naszej uwagi?

Jeśli jest coś, co należy wynieść z tej książki, to jest to świadomość, że ten pogląd na kryptografię jest wyidealizowany. To w dużej części mit. Kryptografia jest mocna w teorii, ale w praktyce jest tak samo podatna na błędy, jak każdy inny element systemu bezpieczeństwa. Sprawdza się to w szczególności, gdy implementacje kryptograficzne są tworzone przez osoby niebędące ekspertami, bez wystarczającej dbałości lub doświadczenia, jak się to zdarza w wielu wdrażanych dziś systemach kryptograficznych. I sytuacja się pogarsza – gdy już implementacje kryptograficzne zawodzą, często zawodzą w niezwykle spektakularny sposób.

Czemu się tym przejmować i po co jest ta książka?

Gdy niemal dwadzieścia lat temu zacząłem pracować w dziedzinie stosowanej kryptografii, informacje, które mieli twórcy oprogramowania, były często fragmentaryczne i nieaktualne. Kryptografowie tworzyli algorytmy i protokoły, a inżynierowie zajmujący się kryptografią wdrażali je, aby tworzyć nieprzejrzyste, słabo udokumentowane biblioteki kryptograficzne zaprojektowane przede wszystkim z myślą o innych ekspertach. Istniał wtedy duży podział między tymi, którzy znali i rozumieli algorytmy kryptograficzne, i tymi, którzy ich używali (lub ignorowali je na swoją zgubę). Nie ma na rynku wielu porządnych podręczników, a jeszcze mniej jest takich, które dają praktykom użyteczne narzędzia.

Wyniki tego nie były piękne. Mówię o naruszeniach podstawowych algorytmów „CVE” (Common Vulnerabilities and Exposures) i „Severity:High” (Bardzo poważne) oraz kilku alarmujących przypadkach, atakach na prezentacje oznaczone jako „ŚCIŚLE TAJNE”. Możecie znać niektóre słynne przykłady choćby dlatego, że uderzyły one w systemy, na których polegacie. Wiele z tych problemów wystąpiło, gdyż kryptografia jest subtelna i elegancka matematycznie, a eksperci z tej dziedziny nie podzielili się swoją wiedzą z inżynierami, którzy pisali oprogramowanie.

Na szczęście zaczęło się to zmieniać i ta książka jest symptomem tych zmian.

Nowoczesna kryptografia została napisana przez jednego z najlepszych ekspertów stosowanej kryptografii, ale nie jest skierowana do ekspertów. Nie znaczy to, że jej celem jest powierzchowny przegląd całej dziedziny. Przeciwnie, zawiera ona pełne i aktualne omówienie inżynierii kryptograficznej, przygotowane jako pomoc dla praktyków, którzy planują lepsze działanie w tej dziedzinie. Z tej książki dowiecie się, nie tylko jak działają algorytmy kryptograficzne, ale jak z nich korzystać w prawdziwych systemach.

Książka zaczyna się od analizy wielu podstawowych pojęć z zakresu kryptografii, w tym podstawowych algorytmów jako szyfry blokowe, systemy szyfrowania publicznego, funkcje skrótu i generatory liczb losowych. Każdy rozdział podaje praktyczne przykłady pracy algorytmów i co należy, a czego nie należy robić. Końcowe rozdziały poruszają zaawansowane tematy, jak TLS, a także przyszłość kryptografii – co robić po nadejściu komputerów kwantowych, które skomplikują nam życie.

Choć ta jedna książka nie jest w stanie rozwiązać wszystkich naszych problemów, to nieco wiedzy może zaprowadzić nas daleko. A ta książka zawiera dużo wiedzy. Zapewne dosyć, aby rzeczywista, wdrażana kryptografia spełniła oczekiwania, jakie wielu z nas z nią wiąże.

Przyjemnego czytania!

Matthew D. Green Profesor

Information Security Institute Johns Hopkins UniversityWPROWADZENIE

Książkę tę napisałem, gdyż takiej mi brakowało, gdy zaczynałem się uczyć kryptografii. W roku 2005 byłem na studiach magisterskich w pobliżu Paryża i bardzo chciałem zapisać się na kurs kryptografii w kolejnym semestrze. Niestety, zajęcia zostały odwołane z powodu zbyt małej liczby zapisanych na nie studentów. „Kryptografia jest za trudna” mówili studenci i zamiast tego masowo zapisywali się na kursy grafiki komputerowej i baz danych.

Tekst „kryptografia jest trudna” słyszałem od tego czasu wiele razy. Ale czy ona naprawdę jest aż tak trudna? Aby grać na instrumencie, opanować dobrze język programowania lub zrealizować w praktyce zastosowania w jakiejkolwiek dziedzinie, trzeba nauczyć się nieco pojęć i symboli, ale nie wymaga to doktoratu. Wydaje mi się, że to samo dotyczy nabycia kompetencji z zakresu kryptografii. Uważam także, że kryptografia postrzegana jest jako trudna, gdyż kryptografowie nie uczą jej dobrze.

Innym powodem, dla którego uważałem, że ta książka jest potrzebna, jest fakt, że nie chodzi tylko o kryptografię – rozwinęła się ona w dziedzinę wielodyscyplinarną. Aby zrobić coś potrzebnego i znaczącego w kryptografii, trzeba rozumieć związane z nią pojęcia: jak działają sieci i komputery, czego potrzebują użytkownicy oraz systemy i jak napastnicy mogą zaatakować algorytmy i ich implementacje. Innymi słowy, trzeba być w kontakcie z rzeczywistością.

Stosowane podejście

Początkowo tytuł tej książki brzmiał Crypto for Real (Prawdziwa kryptografia), co miało podkreślić, że przyjęte podejście jest skupione na kwestiach praktycznych, na rzeczywistych zastosowaniach. Nie chciałem sprawić, aby kryptografia stała się przystępna przez jej uproszczenie, ale wolałem powiązać ją z rzeczywistymi zastosowaniami. Podaję kod źródłowy i przykłady, opisując prawdziwe błędy i historie jak z horroru.

Obok nawiązania do nowoczesności atutami tej książki są prostota i nowoczesne podejście Skupiłem się na prostej formie: przedstawiam wiele nietrywialnych pojęć, bez nudnego formalizmu matematycznego. Próbuję wprowadzić zrozumienie najważniejszych pojęć kryptografii, które są ważniejsze od zapamiętywania wielu równań. Aby zapewnić nowoczesność książki, omawiam najnowsze dokonania i zastosowania kryptografii, jak TLS 1.3 oraz kryptografię postkwantową. Nie omawiam szczegółów starych lub mało bezpiecznych algorytmów, jak DES lub MD5. Wyjątek stanowi RC4, ale jest on tu uwzględniony, abym mógł wyjaśnić jak bardzo jest słaby, i aby pokazać, jak działa szyfr strumieniowy tego rodzaju.

Nowoczesna kryptografia nie jest przewodnikiem po oprogramowaniu kryptograficznym ani kompendium specyfikacji technicznych – takie rzeczy można łatwo znaleźć w sieci. Podstawowym celem tej książki jest zaciekawienie was kryptografią, a przy okazji nauczenie podstawowych pojęć z nią związanych.

Dla kogo jest ta książka

Pisząc tę książkę, często wyobrażałem sobie czytelnika jako dewelopera, który spotkał się z szyframi, ale czuł się zagubiony i sfrustrowany po próbach przeczytania niezrozumiałych podręczników i artykułów naukowych. Deweloperzy często potrzebują – i chcą – lepszego zrozumienia szyfrów, aby uniknąć złych wyborów projektowych. Mam nadzieję, że książka ta im w tym pomoże.

Ale jeśli nie piszecie programów, nie martwcie się! Ta książka nie wymaga umiejętności programowania i jest dostępna dla każdego, kto rozumie podstawy informatyki i zna matematykę na poziomie szkoły średniej (pojęcia prawdopodobieństwa, arytmetyki modulo itd.).

Książka ta może jednak onieśmielać i pomimo swej względnej dostępności wymaga nieco wysiłku, aby z niej naprawdę skorzystać. Lubię porównania wspinaczkowe – autor układa ścieżkę, zapewniając nam liny i czekany, aby ułatwić pracę, ale sami musimy wejść na szczyt. Nauka pojęć z tej książki będzie wymagała wysiłku. Ale na końcu czeka nas nagroda.

Układ książki

Książka ma 14 rozdziałów podzielonych na cztery części. Rozdziały są w zasadzie od siebie niezależne, poza rozdziałem 9, który daje podstawy dla trzech kolejnych rozdziałów. Zalecam też przeczytanie trzech pierwszych rozdziałów, przed przejściem do kolejnych.

Podstawy

• Rozdział 1: Szyfrowanie wprowadza pojęcie bezpiecznego szyfrowania, od słabych szyfrów papierowych do silnego szyfrowania probabilistycznego.

• Rozdział 2: Losowość opisuje, jak działa generator pseudolosowy i jakie warunki trzeba spełnić, aby był on bezpieczny, a także jak używać generatorów w sposób bezpieczny.

• Rozdział 3: Bezpieczeństwo kryptograficzne omawia teoretyczne i praktyczne pojęcia bezpieczeństwa i porównuje systemy z dowodami bezpieczeństwa do tych prawdopodobnie bezpiecznych.

Szyfry symetryczne

• Rozdział 4: Szyfry blokowe dotyczy szyfrów, które przetwarzają komunikaty blok po bloku, skupiając się na najbardziej znanym z nich, AES (Advanced Encryption Standard).

• Rozdział 5: Szyfry strumieniowe prezentuje szyfry, które tworzą strumień losowo wyglądających bitów szyfrowanych za pomocą XOR-owania z bitami komunikatów do zaszyfrowania.

• Rozdział 6: Funkcje skrótu dotyczą jedynego algorytmu, który nie działa z tajnym kluczem, a okazuje się blokiem kryptograficznym o najbardziej wszechstronnej budowie.

• Rozdział 7: Funkcje skrótu z kluczem tłumaczy, co się dzieje, gdy połączymy funkcję skrótu z tajnym kluczem, i jak pomaga to w uwierzytelnianiu komunikatów.

• Rozdział 8: Uwierzytelniane szyfrowanie pokazuje, jak niektóre algorytmy mogą zarówno szyfrować, jak i uwierzytelniać komunikaty, na przykładach takich jak AES-GCM.

Szyfry asymetryczne

• Rozdział 9: Trudne problemy wykłada podstawowe pojęcia leżące u podstaw kryptografii klucza publicznego, wykorzystując pojęcia złożoności obliczeniowej.

• Rozdział 10: RSA wykorzystuje problem rozkładu na czynniki w celu zbudowania bezpiecznego szyfrowania i systemów podpisu za pomocą prostych działań arytmetycznych.

• Rozdział 11: Diffie–Hellman rozszerza kryptografię asymetryczną na pojęcia uzgadniania kluczy, gdzie dwie strony uzgadniają tajną wartość, wykorzystując wartości, które nie są tajne.

• Rozdział 12: Krzywe eliptyczne podaje łagodne wprowadzenie do kryptografii krzywych eliptycznych, która jest najszybszym rodzajem kryptografii asymetrycznej.

Zastosowania

• Rozdział 13: TLS skupia się na protokole TLS (Transport Layer Security), który jest uważany za najważniejszy protokół w bezpieczeństwie sieciowym.

• Rozdział 14: Kryptografia kwantowa i postkwantowa kończy książkę nutą science fiction, opisując pojęcia komputerów kwantowych i nowy rodzaj kryptografii.

PODZIĘKOWANIA

Chciałbym podziękować Jan, Annie i pozostałym członkom zespołu No Starch, którzy mają swój wkład w tę książkę, a zwłaszcza Billowi, który wierzył w ten projekt od początku, za jego cierpliwość w przetrawieniu trudnych tematów i przekształcaniu moich niezdarnych prób w nadające się do czytania strony. Jestem też wdzięczny Laurel za to, że książka ta wygląda tak ładnie i za wprowadzenie wielu moich poprawek.

Od strony technicznej książka zawierałaby wiele błędów i niedokładności bez pomocy wymienionych tu osób: Jon Callas, Bill Cox, Niels Ferguson, Philipp Jovanovic, Samuel Neves, David Reid, Phillip Rogaway, Erik Tews, a także wszystkich czytelników wczesnych wersji, którzy zgłosili błędy. Wreszcie dziękuję Mattowi Greenowi za napisanie słowa wstępnego.

Chciałbym też podziękować mojemu pracodawcy, firmie Kudelski Security, za czas, który mogłem przeznaczyć na tę książkę. Wreszcie przekazuję najgłębsze podziękowania Aleksandrze i Melinie za ich wsparcie i cierpliwość.

Lozanna, 17.05.2017 (trzy liczby pierwsze)SKRÓTY

-------- -----------------------------------------------------------------------------------------------------------------------------------------------------------------------
AE authenticated encryption, szyfrowanie uwierzytelnione
AEAD authentication encryption with associated data, szyfrowanie uwierzytelnione z powiązanymi danymi
AES Advanced Encryption Standard, zaawansowany standard szyfrowania
AES-NI instrukcje natywne AES
AKA authenticated key agreement, uwierzytelnione uzgadnianie kluczy
API application program interface, interfejs programistyczny aplikacji
ARX add-rotate-XOR, dodawanie–rotacja–XOR
ASIC application-specific integrated circuit, układ scalony do konkretnych zastosowań
CA certificate authority, urząd certyfikacyjny, jednostka certyfikująca
CAESAR Competition for Authenticated Encryption: Security, Applicability, and Robustness, konkurs w szyfrowaniu uwierzytelnionym: bezpieczeństwo, zastosowalność i odporność
CBC cipher block chaining, wiązanie bloków zaszyfrowanych
CCA chosen-ciphertext attackers, atak z wybranym szyfrogramem
CDH computational Diffie–Hellman, obliczeniowy problem Diffiego–Hellmana
CMAC cipher-based MAC, MAC oparty na szyfrowaniu
COA ciphertext-only attack, atak z samym szyfrogramem
CPA chosen-plaintext attack, atak z wybranym tekstem jawnym
CRT Chinese remainder theorem, chińskie twierdzenie o resztach
CTR counter mode, tryb licznika
CVP closest vector problem, problem najbliższego wektora
DDH decisional Diffie–Hellman, decyzyjny problem Diffiego–Hellmana
DES Data Encryption Standard, standard szyfrowania danych
DH Diffie–Hellman
DLP discrete logarithm problem, problem logarytmu dyskretnego
DRBG deterministic random bit generator, deterministyczny generator bitów losowych
ECB electronic codebook, elektroniczna książka kodowa
ECC elliptic curve cryptography, kryptografia krzywych eliptycznych
ECDH elliptic curve Diffie–Hellman, protokół Diffiego–Hellmana na krzywej eliptycznej
ECDLP elliptic-curve discrete logarithm problem, problem logarytmu dyskretnego na krzywej eliptycznej
ECDSA elliptic-curve digital signature algorithm, algorytm podpisu cyfrowego na krzywych eliptycznych
FDH Full Domain Hash, skrót pełnodomenowy
FHE fully homomorphic encryption, szyfrowanie w pełni homomorficzne
FIPS Federal Information Processing Standards, Federalny Standard Przetwarzania Informacji
FPE format-preserving encryption, szyfrowanie zachowujące format
FPGA field-programmable gate array, bezpośrednio programowane macierze bramek
FSR feedback shift register, rejestr przesuwny ze sprzężeniem zwrotnym
GCD greatest common divisor, największy wspólny dzielnik (NWD)
GCM Galois Counter Mode, tryb licznika Galois
GNFS general number field sieve, ogólne sito ciała liczbowego
HKDF HMAC-based key derivation function, funkcja wyprowadzania klucza na bazie HMAC
HMAC hash-based message authentication code, kod uwierzytelniania wiadomości na podstawie skrótu
HTTPS HTTP Secure, bezpieczny protokół HTTP
IND indistinguishablity, nierozpoznawalność
IP Internet Protocol, protokół internetowy
IV initial value, wartość początkowa
KDF key derivation function, funkcja wyprowadzania klucza
KPA known-plaintext attack, atak ze znanym tekstem jawnym
LFSR linear feedback shift register, rejestr przesuwny z liniowym sprzężeniem zwrotnym
LSB least significant bit, bit najmniej znaczący
LWE learning with errors, uczenie się z błędami
MAC message authentication code, kod uwierzytelniania wiadomości
MD message digest, skrót wiadomości
MitM meet-in-the-middle
MQ multivariate quadratics, równanie kwadratowe wielu zmiennych
MQV Menezes–Qu–Vanstone
MSB most significant bit, bit najbardziej znaczący
MT Mersenne Twister
NFSR nonlinear feedback shift register, rejestr przesuwny z nieliniowym sprzężeniem zwrotnym
NIST National Institute of Standards and Technology, Narodowy Instytut Standaryzacji i Technologii
NM non-malleability, niedeformowalność
OAEP Optimal Asymmetric Encryption Padding, optymalne dopełnienie w szyfrowaniu asymetrycznym
OCB offset codebook, książka kodowa z przesunięciem
P polynomial time, czas wielomianowy
PLD programmable logic device, programowane urządzenie logiczne
PRF pseudorandom function, funkcja pseudolosowa
PRNG pseudorandom number generator, generator liczb pseudolosowych
PRP pseudorandom permutation, permutacja pseudolosowa
PSK pre-shared key, wstępnie współdzielony klucz
PSS Probabilistic Signature Scheme, schemat podpisu probabilistycznego
QR quarter-round, ćwierć-runda
QRNG quantum random number generator, kwantowy generator liczb losowych
RFC request for comments, prośba o komentarze
RNG random number generator, generator liczb losowych
RSA Rivest–Shamir–Adleman
SHA Secure Hash Algorithm, bezpieczny algorytm skrótu
SIS short integer solution, problem krótkiego rozwiązania w liczbach całkowitych
SIV Synthetic IV
SPN substitution–permutation network, sieć podstawieniowo-permutacyjna
SSH Secure Shell, bezpieczna powłoka
SSL Secure Socket Layer, bezpieczna warstwa gniazd
TE tweakable encryption, szyfrowanie dostrajalne
TLS Transport Layer Security, bezpieczeństwo warstwy transportowej
TMTO time-memory trade-off, kompromis między czasem a pamięcią
UDP User Datagram Protocol, protokół pakietów użytkownika
UH universal hash, uniwersalna funkcja skrótu
WEP Wired Equivalent Privacy, protokół szyfrowania w sieciach bezprzewodowych
WOTS Winternitz one-time signature, jednorazowy podpis Winternitza
XOR exclusive OR, alternatywa wykluczająca
-------- -----------------------------------------------------------------------------------------------------------------------------------------------------------------------2 LOSOWOŚĆ

Losowość w kryptografii można odnaleźć wszędzie: w tworzeniu tajnych kluczy, w systemach szyfrowania, a nawet w atakach na systemy kryptograficzne. Bez losowości kryptografia byłaby niemożliwa, ponieważ wszystkie działania stałyby się przewidywalne, a zatem nie byłyby bezpieczne.

Ten rozdział jest wprowadzeniem do pojęcia losowości w kontekście kryptografii i jej zastosowań. Omawiamy generatory liczb pseudolosowych oraz sposób, w jaki systemy operacyjne mogą tworzyć wiarygodną losowość, a na koniec przedstawiamy rzeczywiste przykłady pokazujące, jak błędna losowość może wpływać na bezpieczeństwo.

Losowy czy nie losowy?

Słyszeliście już zapewne zwrot „losowe bity”, lecz dokładnie rzecz biorąc, nie ma takiej rzeczy jak ciąg bitów losowych. To, co jest losowe, jest tak naprawdę algorytmem lub procesem, który tworzy ciąg bitów losowych; dlatego, gdy mówimy „bity losowe”, mamy na myśli bity generowane w sposób losowy.

Jak wyglądają bity losowe? Na przykład dla większości osób 8-bitowy ciąg 11010110 jest bardziej losowy niż 00000000, mimo że prawdopodobieństwo utworzenia obu z nich jest jednakowe (dokładnie to 1/256). Wartość 11010110 wydaje się bardziej losowa od 00000000, ponieważ ma znaki typowe dla wartości wygenerowanej w sposób losowy. Czyli 11010110 nie ma oczywistego wzorca.

Gdy patrzymy na ciąg 11010110, nasz mózg rejestruje, że ma on mniej więcej tyle zer (trzy), ile jedynek (pięć), tak jak 55 innych ciągów 8-bitowych (11111000, 11110100, 11110010, itp.), lecz tylko jeden ciąg 8-bitowy ma osiem zer. Ponieważ wzór z trzema zerami i pięcioma jedynkami jest bardziej prawdopodobny od wzoru z ośmioma zerami, uznajemy 11010110 za losowy, a 00000000 za nielosowy, a jeśli program tworzy bity 11010110, możemy uważać, że jest losowy, nawet gdy tak nie jest. I przeciwnie, jeśli losowy program tworzy 00000000, jego losowość zapewne zostanie poddana w wątpliwość.

Ten przykład ilustruje dwa rodzaje błędów często popełniane przez ludzi przy rozpoznawaniu losowości:

Mylne przyjmowanie braku losowości za losowość – myślenie, że obiekt został wygenerowany losowo tylko dlatego, że wygląda na losowy.

Mylne przyjmowanie losowości za nielosowość – myślenie, że wzory pojawiające się przypadkowo są tam z jakiegoś innego powodu.

Odróżnienie obiektu wyglądającego na losowy od obiektu naprawdę losowego jest niezwykle ważne. W istocie w kryptografii nielosowość jest często synonimem braku bezpieczeństwa.

Losowość jako rozkład prawdopodobieństwa

Każdy proces losowy charakteryzuje się rozkładem prawdopodobieństwa, które podaje wszystko, co można wiedzieć o losowości procesu. Rozkład prawdopodobieństwa, lub po prostu rozkład, podaje rezultaty procesu losowego, z których każdy ma przypisane prawdopodobieństwo.

Prawdopodobieństwo mierzy możliwość nastąpienia danego zdarzenia. Jest wyrażane jako liczba rzeczywista między 0 a 1, gdzie prawdopodobieństwo 0 oznacza zdarzenie niemożliwe, a prawdopodobieństwo 1 oznacza zdarzenie pewne. Na przykład, gdy rzucamy dwustronną monetą, prawdopodobieństwo, że moneta upadnie reszką do góry, to 1/2 i zwykle zakładamy, że wylądowanie monety na krawędzi ma zerowe prawdopodobieństwo.

Rozkład prawdopodobieństwa musi obejmować wszystkie możliwe wyniki, aby suma wszystkich prawdopodobieństw była równa 1. W szczególności jeśli możliwych jest N zdarzeń, istnieje N prawdopodobieństw p₁, p₂, . . . , p_(N), gdzie p₁ + p₂ + . . . + p_(N) = 1. W przypadku rzutu monetą rozkład to 1/2 dla reszki i 1/2 dla orła. Suma obu prawdopodobieństw jest równa 1/2 + 1/2 = 1, ponieważ moneta upadnie na jedną z dwóch swoich stron.

Rozkład jednorodny to rozkład, w którym wszystkie prawdopodobieństwa są równe, czyli wszystkie wyniki są równie prawdopodobne. Jeśli zdarzeń jest N, każde zdarzenie ma prawdopodobieństwo 1/N. Na przykład przy losowym wyborze 128-bitowego klucza – zgodnie z rozkładem jednorodnym – każdy z 2¹²⁸ możliwych kluczy powinien mieć prawdopodobieństwo 1/2¹²⁸.

Natomiast gdy rozkład jest niejednorodny, prawdopodobieństwa nie są równe. Rzut monetą o niejednorodnym rozkładzie jest określany jako obciążony i może dawać na przykład reszkę z prawdopodobieństwem 1/4, a orła z prawdopodobieństwem 3/4.

Entropia – miara niepewności

Entropia jest miarą niepewności lub nieuporządkowania systemu. Entropię można traktować jako ilość niepewności co do wyników procesu losowego – im większa entropia, tym mniejsza pewność wyników.

Możemy obliczyć entropię rozkładu prawdopodobieństwa. Jeśli nasz rozkład składa się z prawdopodobieństw p₁, p₂, . . . , p_(N), wtedy jego entropia jest ujemną sumą prawdopodobieństw pomnożoną przez ich logarytmy, jak pokazano w tym wyrażeniu:

– p₁ × log₂ (p₁) – p₂ × log₂ (p₂) – … p_(N) × log₂ (p_(N))

Tutaj funkcja log jest logarytmem binarnym, czyli logarytmem o podstawie dwa. Inaczej niż w logarytmie naturalnym, logarytm binarny wyraża informacje w bitach i daje wartości całkowite, gdy prawdopodobieństwa są potęgami liczby dwa. Na przykład log₂(1/2) = –1, log₂ (1/4) = –2, a ogólniej log₂ (1/2^(n)) = –n. (Dlatego liczymy ujemną sumę, aby w rezultacie otrzymać liczbę dodatnią). Losowe klucze 128-bitowe utworzone przy jednorodnym rozkładzie mają zatem następującą entropię:

2¹²⁸ × (–2^(–128) × log₂(2^(–128))) = –log₂ (2^(–128)) = 128 bitów

Jeśli 128 zastąpimy liczbą całkowitą n, okaże się, że entropią łańcucha n-bitowego o rozkładzie jednorodnym jest n bitów.

Entropia jest maksymalna, gdy rozkład jest jednorodny, ponieważ przy takim rozkładzie niepewność jest największa – żaden wynik nie jest bardziej prawdopodobny od innych. Dlatego wartości n-bitowe nie mogą mieć więcej niż n bitów entropii.

Z tego samego powodu, gdy rozkład nie jest jednorodny, entropia jest niższa. Rozważmy przykład z rzutem monetą. Entropia uczciwego rzutu monetą jest następująca:

–(1/2) × log₂ (1/2) – (1/2) × log₂(1/2) = 1/2 + 1/2 = 1 bit

Co będzie, jeśli prawdopodobieństwo wylądowania monety na jednej ze stron jest większe niż dla drugiej? Powiedzmy, że prawdopodobieństwo dla reszki wynosi 1/4, dla orła 3/4 (trzeba pamiętać, że suma wszystkich prawdopodobieństw powinna wynosić 1).

Entropia takiego obciążonego rzutu jest następująca:

–(3/4) × log₂ (3/4) – (1/4) × log₂ (1/4) ≈ – (3/4) × (–0,415) – (1/4) × (–2) ≈ 0,81 bitów

Fakt, że 0,81 to mniej niż 1-bitowa entropia dla uczciwego rzutu, mówi nam, że im bardziej moneta jest niesymetryczna (wynik jest obciążony), tym mniej równomierny jest rozkład i mniejsza entropia. Biorąc następny przykład, jeśli wyrzucenie reszki ma prawdopodobieństwo 1/10, entropia jest równa 0,469; jeśli prawdopodobieństwo spadnie do 1/100, entropia zmaleje do 0,081.

UWAGA
Entropię można także postrzegać jako miarę informacji. Na przykład wynik rzutu monetą daje nam dokładnie jeden bit informacji – reszkę lub orła – i nie możemy przewidzieć wyniku rzutu. W przypadku nieuczciwego rzutu monetą wiemy wcześniej, która strona jest bardziej prawdopodobna, więc zwykle możemy przewidzieć wynik. Wynik rzutu monetą daje nam informacje potrzebne do przewidzenia tego wyniku w sposób pewny.

Generatory liczb losowych (RNG) i generatory liczb pseudolosowych (PRNG)

Aby systemy kryptograficzne były bezpieczne, wymagają one losowości, dlatego potrzebny jest komponent będący źródłem tej losowości. Zadaniem tego komponentu jest zwracanie na żądanie losowych bitów. Jak dokonuje się to losowe generowanie? Potrzebne są dwie rzeczy:

• źródło niepewności lub źródło entropii, zapewniane przez generatory liczb losowych (RNG);

• algorytm kryptograficzny, który generuje bity losowe o dużej jakości ze źródła entropii; można go znaleźć w generatorach liczb pseudolosowych (PRNG).

Wykorzystanie generatorów RNG i PRNG jest kluczem do praktycznej i bezpiecznej kryptografii. Zanim zaczniemy głębszą analizę generatorów PRNG, popatrzmy, jak działają generatory RNG.

Źródłem losowości jest środowisko analogowe, chaotyczne, niepewne, a więc nieprzewidywalne. Losowość nie może być wytworzona przez same algorytmy oparte na komputerach. W kryptografii losowość zazwyczaj pochodzi z generatorów liczb losowych (random number generators, RNG), które są składnikami oprogramowania lub sprzętu, wykorzystującymi entropię występującą w świecie analogowym do wytwarzania nieprzewidywalnych bitów w systemie cyfrowym. Na przykład RNG może bezpośrednio próbkować bity z pomiarów temperatury, szumu akustycznego, turbulencji powietrza lub elektryczności statycznej. Niestety, takie analogowe źródła entropii nie zawsze są dostępne, a ich entropia jest często trudna do oszacowania.

Generatory RNG mogą także zbierać entropię w działającym systemie operacyjnym, czerpiąc ją z przyłączonych czujników, urządzeń we/wy, aktywności sieci lub dysku, dzienników systemu, uruchomionych procesów i działań użytkownika, takich jak naciskanie klawisza czy ruch myszą. Takie działania generowane przez system i człowieka mogą być dobrym źródłem entropii, lecz mogą być wrażliwe i manipulowane przez napastnika. Są one również powolne w uzyskiwaniu losowych bitów.

Kwantowe generatory liczb losowych (quantum random number generators, QRNG) to rodzaj RNG, które opierają się na losowości powstającej ze zjawisk mechaniki kwantowej, takich jak rozpad radioaktywny, fluktuacje próżni oraz obserwacja polaryzacji fotonów. Dostarczają one prawdziwą losowość, a nie tylko coś, co wygląda na losowe. Jednak w praktyce generatory QRNG mogą być obciążone i nie tworzyć szybko bitów; wymienione wcześniej źródła entropii wymagają dodatkowego komponentu, aby szybko wytworzyć wiarygodny wynik.

Generatory liczb pseudolosowych (pseudorandom number generators, PRNG) rozwiązują problemy, które napotykamy w generowaniu losowości poprzez niezawodne wytwarzanie wielu sztucznych bitów losowych z kilku naprawdę losowych bitów. Na przykład RNG, który przekłada ruchy myszy na losowe bity, przestaje działać, gdy przestaniemy ruszać myszą, natomiast PRNG na żądanie zawsze podaje bity pseudolosowe.

Generatory PRNG są oparte na generatorach RNG, lecz działają inaczej: RNG tworzą prawdziwe bity losowe dość wolno i ze źródeł analogowych, w sposób niedeterministyczny i bez gwarancji wysokiej entropii. W przeciwieństwie do nich generatory PRNG tworzą ze źródeł cyfrowych bity wyglądające na losowe, w sposób deterministyczny, z maksymalną entropią. W istocie generatory PRNG przekształcają kilka niepewnych bitów losowych na długi strumień wiarygodnych bitów pseudolosowych odpowiednich dla aplikacji szyfrowania, jak to pokazano na rysunku 2.1.

Rysunek 2.1. Generatory RNG tworzą kilka niepewnych bitów ze źródeł analogowych, podczas gdy generatory PRNG rozszerzają te bity na długi strumień wiarygodnych bitów

Jak działa generator PRNG

Generator PRNG otrzymuje w regularnych odstępach losowe bity z RNG i wykorzystuje je, aby zaktualizować zawartość dużego bufora pamięci, nazywanego pulą entropii. Pula entropii to źródło entropii generatora PRNG, tak jak fizyczne środowisko dla RNG. Gdy PRNG aktualizuje pulę entropii, razem miesza ze sobą bity puli, co ma pomóc w usunięciu wszelkich obciążeń statystycznych.

Aby generować bity pseudolosowe, PRNG uruchamia deterministyczny algorytm generatora bitów losowych (DRBG), który rozciąga bity z puli entropii w dużo dłuższe sekwencje. Jak wskazuje jego nazwa, DRBG jest deterministyczny, a nie losowy: przy danym wejściu zawsze dostajemy takie samo wyjście. PRNG sprawia, że DRBG nigdy nie otrzyma dwukrotnie takich samych wartości na wejściu, aby generować niepowtarzalne sekwencje pseudolosowe.

W toku swojej pracy PRNG wykonuje trzy następujące działania:

init() – inicjalizuje pulę entropii i wewnętrzny stan PRNG;

refresh(R) – aktualizuje pulę entropii za pomocą pewnej danej, R, zwykle uzyskanej z RNG;

next(N) – zwraca N pseudolosowe bity i aktualizuje pulę entropii.

Działanie init przywraca PRNG do początkowego stanu, ponownie inicjalizuje pulę entropii na pewną wartość domyślną i inicjalizuje wszystkie zmienne, czyli bufory pamięci używane przez PRNG, aby wykonać działania refresh i next.

Działanie refresh jest często nazywane wprowadzeniem nowego ziarna, a jego argument R jest nazywany ziarnem. Gdy nie ma żadnego dostępnego RNG, ziarna mogą być niepowtarzalnymi wartościami zakodowanymi trwale w systemie. Działanie refresh jest zwykle wywoływane przez system operacyjny, podczas gdy next jest zwykle wywoływane, czyli żądane przez aplikację. Działanie next uruchamia DRBG i zmienia pulę entropii, aby sprawić, że następne wywołanie dostarczy inne bity pseudolosowe.

Kwestie bezpieczeństwa

Omówmy w skrócie sposób, w jaki PRNG rozwiązuje niektóre kwestie bezpieczeństwa wysokiego poziomu. W szczególności generatory PRNG powinny gwarantować odporność na analizę wsteczną i odporność na przewidywanie. Odporność na analizę wsteczną (nazywane także poufnością w przód, forward secrecy) oznacza, że wcześniej wygenerowanych bitów nie można odtworzyć, natomiast odporność na przewidywanie (poufność wstecz, backward secrecy) oznacza, że przewidzenie przyszłych bitów musi być niemożliwe.

Aby osiągnąć odporność na analizę wsteczną, PRNG powinien sprawić, że przekształcenia wykonywane przy aktualizacji stanu działania refresh i next będą nieodwracalne, więc jeśli napastnik złamie system i uzyska wartość puli entropii, nie będzie mógł ustalić wcześniejszych wartości puli ani wcześniej wygenerowanych bitów. Aby uzyskać odporność na przewidywanie, PRNG powinien regularnie wywoływać refresh z wartościami R, które nie są znane napastnikowi i są trudne do odgadnięcia, co uniemożliwia mu ustalenie przyszłych wartości puli entropii, nawet po poznaniu puli. (Nawet po poznaniu listy używanych wartości R trzeba znać kolejność wykonywania wywołań refresh i next, aby ponownie zbudować pulę).

Fortuna PRNG

Fortuna to struktura PRNG wykorzystywana w systemie Windows, zaprojektowana w 2003 roku przez Nielsa Fergusona i Bruce’a Schneiera. Fortuna zastąpiła Yarrow, projekt Kelseya i Schneiera z 1998 r., używany teraz w systemach operacyjnych macOS i iOS. Nie podamy tutaj charakterystyki Fortuny ani nie pokażamy jej implementacji, lecz spróbujemy wyjaśnić, jak działa. Pełny opis Fortuny można znaleźć w rozdziale 9 książki Cryptography Engineering, autorstwa Fergusona, Schneiera i Kohno (Wiley, 2010).

Pamięć wewnętrzna Fortuny zawiera:

• 32 pule entropii P₁, P₂, . . . , P₃₂, takie, że P_(i) jest używana przy każdym nowym 2^(i) ziarnie;

• klucz K i licznik C (oba 16-bajtowe), które tworzą stan wewnętrzny w DRBG Fortuny.

Mówiąc najprościej, Fortuna działa tak:

• init() ustawia K i C na zero i opróżnia 32 pule entropii P_(i), gdzie i = 1 . . . 32;

• refresh(R) dołącza dane R do jednej z pul entropii; system wybiera generatory RNG używane do tworzenia wartości R i powinien regularnie wywoływać refresh;

• next(N) aktualizuje K przy użyciu danych z jednej lub większej liczby pul entropii, przy czym wybór pul entropii zależy głównie od tego, jak wiele aktualizacji K już zostało wykonanych – N żądanych bitów jest wtedy tworzonych poprzez szyfrowanie C za pomocą klucza K; jeśli szyfrowanie C nie wystarczy, Fortuna szyfruje C + 1, potem C + 2 itd., aby otrzymać wystarczającą liczbę bitów.

Mimo że działania Fortuny wyglądają na dość proste, ich prawidłowa implementacja jest trudna. Po pierwsze, trzeba poznać wszystkie szczegóły algorytmu, a mianowicie, jak są wybierane pule entropii, typ szyfru używany w next, co zrobić, gdy nie otrzyma się żadnej entropii itd. Choć specyfikacja definiuje większość szczegółów, nie obejmują one całościowego zestawu testów sprawdzających prawidłowość implementacji, więc trudno zapewnić, by nasza implementacja Fortuny działała zgodnie z oczekiwaniem.

Nawet jeśli Fortuna jest prawidłowo zaimplementowana, mogą pojawić się błędy bezpieczeństwa z innych powodów niż zastosowanie niewłaściwych algorytmów. Na przykład Fortuna może nie zauważyć, że generator RNG nie generuje wystarczająco losowych bitów i w rezultacie Fortuna będzie wytwarzać bity pseudolosowe o niższej jakości lub może całkiem przestać dostarczać bity pseudolosowe.