Algorytm krwawnika
Algorytm Yarrow to rodzina kryptograficznych generatorów liczb pseudolosowych (CPRNG) opracowanych przez Johna Kelseya , Bruce'a Schneiera i Nielsa Fergusona i opublikowanych w 1999 roku. Algorytm Yarrow jest jawnie nieopatentowany, wolny od opłat licencyjnych i open source; do korzystania z niego nie jest wymagana żadna licencja. Ulepszony projekt Fergusona i Schneiera, Fortuna , jest opisany w ich książce Practical Cryptography
Yarrow był używany we FreeBSD , ale teraz został zastąpiony przez Fortuna. Yarrow został również włączony do iOS i macOS dla ich urządzeń /dev/random , ale Apple przeszło na Fortuna od pierwszego kwartału 2020 r.
Nazwa
Nazwa Yarrow nawiązuje do użycia rośliny krwawnika w losowym procesie generowania wróżbiarstwa I Ching . Od czasów dynastii Xia (ok. 2070 do ok. 1600 pne) Chińczycy używali łodyg krwawnika do wróżenia. Wróżki dzielą zestaw 50 łodyg krwawnika na stosy i rekurencyjnie wykorzystują arytmetykę modułową , aby wygenerować dwa bity losowych informacji, które mają nierównomierny rozkład .
Zasady
Główne zasady projektowania Yarrow to: odporność na ataki, łatwość użycia przez programistów bez doświadczenia w kryptografii oraz możliwość ponownego wykorzystania istniejących elementów konstrukcyjnych. Dawne szeroko stosowane projekty, takie jak ANSI X9.17 i RSAREF 2.0 PRNG, mają luki, które w pewnych okolicznościach zapewniają możliwości ataku. Niektóre z nich nie zostały zaprojektowane z myślą o atakach w świecie rzeczywistym. Yarrow ma również na celu zapewnienie łatwej integracji, aby umożliwić projektantom systemów z niewielką wiedzą na temat funkcjonalności PRNG.
Projekt
składniki
Konstrukcja Yarrow składa się z czterech głównych elementów: akumulatora entropii , mechanizmu ponownego zasiewania , mechanizmu generowania i kontroli ponownego zasiewania.
Yarrow gromadzi entropię w dwóch pulach: szybkiej puli, która zapewnia częste ponowne umieszczanie klucza, aby czas trwania kluczowych kompromisów był jak najkrótszy; powolna pula, która zapewnia rzadkie, ale konserwatywne reseed klucza. Daje to pewność, że reseed jest zabezpieczony, nawet jeśli szacunki entropii są bardzo optymistyczne.
Mechanizm reseed łączy akumulator entropii z mechanizmem generującym. Ponowne umieszczanie z puli szybkiej używa bieżącego klucza i skrótu wszystkich danych wejściowych do puli szybkiej od uruchomienia w celu wygenerowania nowego klucza; reseed z powolnej puli zachowuje się podobnie, z tą różnicą, że wykorzystuje również skrót wszystkich danych wejściowych do wolnej puli do wygenerowania nowego klucza. Oba ponowne obsadzenia resetują oszacowanie entropii puli szybkiej do zera, ale ostatnie ustawia również oszacowanie wolnej puli na zero. Mechanizm ponownego umieszczania aktualizuje klucz w sposób ciągły, więc nawet jeśli klucz informacji o puli jest znany atakującemu przed ponownym umieszczeniem, będą one nieznane atakującemu po reseed.
Komponent kontroli reseed korzysta z częstych reseedów, co jest pożądane, ale może pozwolić na iteracyjne ataki polegające na zgadywaniu , oraz rzadkich reseedów, które narażają na szwank więcej informacji dla atakującego, który ma klucz. Yarrow używa puli szybkiej do ponownego umieszczania za każdym razem, gdy źródło przekroczy pewne wartości progowe, a powolnej puli do ponownego umieszczania, gdy co najmniej dwa z jego źródeł przekroczą inną wartość progową. Konkretne wartości progowe wymieniono w Yarrow-160 .
Filozofia projektowania
Yarrow zakłada, że można zgromadzić wystarczającą ilość entropii, aby zapewnić nieprzewidywalny stan PRNG. Projektanci gromadzą entropię w celu zachowania możliwości odzyskania PRNG nawet w przypadku złamania klucza. Podobną filozofię projektowania przyjmują RSAREF, DSA i ANSI X9.17 PRNG.
Krwawnik pospolity-160
Yarrow używa dwóch ważnych algorytmów: jednokierunkowej funkcji haszującej i szyfru blokowego . Konkretny opis i właściwości są wymienione w poniższej tabeli.
| Algorytmy | Nieruchomości | Co wykorzystuje Yarrow-160 |
|---|---|---|
| Funkcja skrótu h(x) |
Biorąc pod uwagę wartości wejściowe M , |M| wybory wartości wyjściowych są równomiernie rozłożone na wartości m -bitowe. |
Funkcja skrótu SHA-1 |
| Szyfr blokowy E() |
Wysoka wydajność statystyczna wyników, gdy dane wejściowe są wysoce wzorcowe. |
Potrójny DES z trzema klawiszami |
Pokolenie
Yarrow-160 używa trzech klawiszy Triple DES w trybie licznika do generowania danych wyjściowych. C jest n -bitową wartością licznika; K jest kluczem. Aby wygenerować następny blok wyjściowy, Yarrow postępuje zgodnie z pokazanymi tutaj funkcjami.
Yarrow liczy blok danych wyjściowych, ponieważ po złamaniu klucza wyciek ze starego wyjścia przed uszkodzonym może zostać natychmiast zatrzymany. Po osiągnięciu pewnego parametru bezpieczeństwa systemu P g algorytm wygeneruje k bitów danych wyjściowych PRNG i użyje ich jako nowego klucza. W Yarrow-160 parametr bezpieczeństwa systemu jest ustawiony na 10 , co oznacza P g = 10 . Parametr jest celowo ustawiony na niski, aby zminimalizować liczbę wyjść, które mogą być cofane.
ponownie zasiać
Mechanizm reseed Yarrow-160 wykorzystuje SHA-1 i Triple DES jako funkcję skrótu i szyfr blokowy. Szczegółowe kroki znajdują się w oryginalnym dokumencie.
Implementacja Yarrow-160
Yarrow-160 został zaimplementowany w Javie i FreeBSD . Przykłady można znaleźć w „Animplementation of the Yarrow PRNG for FreeBSD” autorstwa Marka RV Murraya.
Plusy i minusy Yarrow
Zalety
- Yarrow ponownie wykorzystuje istniejące bloki konstrukcyjne.
- W porównaniu z poprzednimi PRNG, Yarrow jest dość wydajny.
- Yarrow może być używany przez programistów bez doświadczenia w kryptografii w dość bezpieczny sposób. Krwawnik pospolity jest przenośny i precyzyjnie zdefiniowany. Interfejs jest prosty i przejrzysty. Te cechy nieco zmniejszają prawdopodobieństwo wystąpienia błędów implementacyjnych.
- Yarrow został stworzony przy użyciu procesu projektowania zorientowanego na ataki.
- Oszacowanie entropii Yarrow jest bardzo konserwatywne, co zapobiega wyczerpującym atakom wyszukiwania . Bardzo często PRNG zawodzą w rzeczywistych zastosowaniach z powodu przeszacowania entropii i możliwych do odgadnięcia punktów początkowych.
- Proces ponownego zasiewania Yarrow jest stosunkowo kosztowny obliczeniowo, dlatego koszt próby odgadnięcia klucza PRNG jest wyższy.
- Yarrow wykorzystuje funkcje upraszczające zarządzanie plikami źródłowymi, dzięki czemu pliki te są stale aktualizowane.
- Aby poradzić sobie z atakami kryptoanalitycznymi , Yarrow został zaprojektowany tak, aby był oparty na zabezpieczonym szyfrze blokowym. Poziom bezpieczeństwa mechanizmu generowania zależy od szyfru blokowego.
- Yarrow stara się unikać ścieżek wykonania zależnych od danych. Ma to na celu zapobieganie atakom typu side-channel, takim jak ataki czasowe i analiza mocy . Jest to ulepszenie w porównaniu z wcześniejszymi PRNG, na przykład RSAREF 2.0 PRNG, które całkowicie się rozpadną, gdy dodatkowe informacje o operacjach wewnętrznych nie będą już zabezpieczane.
- Yarrow używa kryptograficznych funkcji skrótu do przetwarzania próbek wejściowych, a następnie wykorzystuje funkcję bezpiecznej aktualizacji, aby połączyć próbki z istniejącym kluczem. Daje to pewność, że atakujący nie będzie mógł łatwo manipulować próbkami wejściowymi. PRNG, takie jak RSAREF 2.0 PRNG, nie są w stanie oprzeć się tego rodzaju atakom z wybranym wejściem.
- W przeciwieństwie do ANSI X9.17 PRNG, Yarrow ma zdolność odzyskiwania po kluczowym kompromisie. Oznacza to, że nawet jeśli klucz zostanie naruszony, osoba atakująca nie będzie w stanie przewidzieć przyszłych wyników w nieskończoność. Wynika to z mechanizmu ponownego zasiewania krwawnika.
- Yarrow ma pulę próbek entropii oddzieloną od klucza i ponownie umieszcza klucz tylko wtedy, gdy zawartość puli entropii jest całkowicie nieprzewidywalna. Ten projekt zapobiega iteracyjnym atakom zgadywania, w których osoba atakująca z kluczem odgaduje następną próbkę i sprawdza wynik, obserwując następne dane wyjściowe.
Cons
- Yarrow jest zależny od SHA-1, skrótu, który został złamany od czasu publikacji Yarrow i nie jest już bezpieczny.
- Ponieważ dane wyjściowe Yarrow są uzyskiwane kryptograficznie, systemy korzystające z tych danych wyjściowych mogą być tak bezpieczne, jak sam mechanizm generowania. Oznacza to, że osoba atakująca, która może złamać mechanizm generowania, z łatwością złamie system zależny od danych wyjściowych Yarrow. Tego problemu nie można rozwiązać przez zwiększenie akumulacji entropii.
- Yarrow wymaga oszacowania entropii, co jest bardzo dużym wyzwaniem dla wdrożeń. Trudno jest mieć pewność, ile entropii zebrać przed użyciem jej do ponownego zaszczepienia PRNG. Ten problem rozwiązuje Fortuna (PRNG) , ulepszenie Yarrow. Fortuna ma 32 pule do zbierania entropii i całkowicie usunęła estymator entropii.
- Siła Yarrowa jest ograniczona rozmiarem klucza. Na przykład Yarrow-160 ma efektywny rozmiar klucza 160 bitów. Jeśli zabezpieczenia wymagają 256 bitów, Yarrow-160 nie jest w stanie wykonać tego zadania.