Algorytm krwawnika - Yarrow algorithm
Algorytm Krwawnik to rodzina kryptograficznych generator liczb pseudolosowych (CPRNG) opracowanych przez Johna Kelsey , Bruce Schneier , a Niels Ferguson i opublikowanych w 1999 roku Yarrow algorytmu jest wyraźnie nieopatentowanej, nieodpłatnej i open source; do korzystania z niego nie jest wymagana licencja. Ulepszony projekt Fergusona i Schneiera, Fortuna , jest opisany w ich książce „ Praktyczna kryptografia”
Yarrow był używany we FreeBSD , ale został zastąpiony przez Fortuna. Yarrow został również włączony do systemów iOS i macOS dla swoich urządzeń /dev/random , ale Apple przeszedł na Fortunę od I kwartału 2020 r.
Nazwa
Nazwa Yarrow nawiązuje do wykorzystania rośliny krwawnika w procesie losowego 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 używają rekurencyjnej arytmetyki modułowej, aby wygenerować dwa bity losowych informacji, które mają niejednorodny rozkład .
Zasady
Główne zasady projektowania Yarrowa to: odporność na ataki, łatwość użycia przez programistów bez znajomości kryptografii oraz możliwość ponownego wykorzystania istniejących elementów konstrukcyjnych. Poprzednie 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
Projekt Yarrowa składa się z czterech głównych elementów: akumulatora entropijnego , mechanizmu zasiewu, mechanizmu generowania i kontroli zasiewu.
Yarrow gromadzi entropię w dwóch pulach: szybkiej puli, która zapewnia częste reseeding klucza, aby czas trwania kompromisów klucza był jak najkrótszy; powolny basen, który zapewnia rzadkie, ale konserwatywne nasiona klucza. Daje to pewność, że nasiona są zabezpieczone, nawet jeśli szacunki entropii są bardzo optymistyczne.
Mechanizm zasiewający łączy akumulator entropijny 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 momentu uruchomienia w celu wygenerowania nowego klucza; reseeding z wolnej puli zachowuje się podobnie, z wyjątkiem tego, że wykorzystuje również skrót wszystkich danych wejściowych do wolnej puli w celu wygenerowania nowego klucza. Oba reseedingi resetują oszacowanie entropii szybkiej puli do zera, ale ostatnie ustawia również oszacowanie wolnej puli na zero. Mechanizm reseedingu stale aktualizuje klucz, dzięki czemu nawet jeśli klucz informacji o puli jest znany atakującemu przed reseedem, po reseed będzie dla atakującego nieznany.
Komponent kontroli reseed wykorzystuje częste ponowne inicjowanie, co jest pożądane, ale może pozwolić na powtarzające się ataki polegające na zgadywaniu , a rzadkim ponownym inicjowaniem, które zagraża większej ilości informacji dla atakującego, który ma klucz. Yarrow używa szybkiej puli do reseedingu, gdy źródło przekracza pewne wartości progowe, i używa wolnej puli do reseedingu, gdy co najmniej dwa z jego źródeł przekraczają inną wartość progową. Konkretne wartości progowe są wymienione w sekcji Yarrow-160 .
Filozofia projektowania
Yarrow zakłada, że można zgromadzić wystarczającą entropię, aby zapewnić, że PRNG jest w nieprzewidywalnym stanie. Projektanci gromadzą entropię w celu zachowania zdolności do odzyskania PRNG nawet po złamaniu klucza. Podobną filozofię projektowania przyjmują RSAREF, DSA i ANSI X9.17 PRNG.
Krwawnik-160
Yarrow używa dwóch ważnych algorytmów: jednokierunkowej funkcji mieszającej i szyfru blokowego . Szczegółowy opis i właściwości są wymienione w poniższej tabeli.
| Algorytmy | Nieruchomości | Co używa Yarrow-160 |
|---|---|---|
| Funkcja skrótu h(x) |
Biorąc pod uwagę M wartości wejściowych, |M| selekcje wartości wyjściowych są równomiernie rozłożone na wartościach m- bitowych. |
Funkcja skrótu SHA-1 |
| Szyfr blokowy E() |
Wysoka wydajność statystyczna danych wyjściowych w przypadku danych wejściowych o wysokim wzorze. |
Trzy klawisze Potrójne DES |
Pokolenie
Yarrow-160 wykorzystuje trzyklawiszowy 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 zlicza bloki wyjściowe, ponieważ gdy klucz zostanie naruszony, wyciek starego wyjścia przed zhakowanym może zostać natychmiast zatrzymany. Po jakiś system bezpieczeństwa parametr P g osiągnięciu algorytm wygeneruje k bitów wyjścia PRNG i używać ich jako nowego klucza. W Yarrow-160 parametr bezpieczeństwa systemu jest ustawiony na 10 , co oznacza P g = 10 . Parametr jest celowo ustawiony jako niski, aby zminimalizować liczbę wyjść, które można cofnąć.
Reseed
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.
Wdrożenie krwawnika-160
Yarrow-160 został zaimplementowany w Javie i we FreeBSD . Przykłady można znaleźć w „Wdrożeniu Yarrow PRNG for FreeBSD” autorstwa Marka RV Murraya.
Plusy i minusy Yarrow
Plusy
- Yarrow ponownie wykorzystuje istniejące cegiełki.
- W porównaniu do poprzednich PRNG, Yarrow jest dość wydajny.
- Yarrow może być używany przez programistów bez znajomości kryptografii w dość bezpieczny sposób. Krwawnik pospolity jest przenośny i precyzyjnie zdefiniowany. Interfejs jest prosty i przejrzysty. Cechy te nieco zmniejszają prawdopodobieństwo błędów implementacji.
- Yarrow został stworzony przy użyciu procesu projektowania ukierunkowanego na atak.
- Entropia oszacowanie z krwawnika jest bardzo konserwatywny, zapobiegając w ten sposób wyczerpujący ataki 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 wysiewu Yarrowa jest stosunkowo kosztowny obliczeniowo, dlatego koszt próby odgadnięcia klucza PRNG jest wyższy.
- Yarrow wykorzystuje funkcje upraszczające zarządzanie plikami nasion, dzięki czemu pliki są stale aktualizowane.
- Aby obsługiwać ataki kryptoanalityczne , Yarrow został zaprojektowany tak, aby opierał się na zabezpieczonym szyfrze blokowym. Poziom bezpieczeństwa mechanizmu generacji zależy od szyfru blokowego.
- Yarrow stara się unikać ścieżek wykonania zależnych od danych. Ma to na celu zapobieganie atakom bocznym, takim jak ataki czasowe i analiza mocy . Jest to ulepszenie w porównaniu do wcześniejszych PRNG, na przykład RSAREF 2.0 PRNG, które całkowicie się rozpadną, gdy dodatkowe informacje o wewnętrznych operacjach nie będą już zabezpieczone.
- Yarrow używa kryptograficznych funkcji skrótu do przetwarzania próbek wejściowych, a następnie używa funkcji 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 wybranymi danymi wejściowymi.
- W przeciwieństwie do ANSI X9.17 PRNG, Yarrow ma możliwość odzyskania sprawności po naruszeniu klucza. Oznacza to, że nawet jeśli klucz zostanie złamany, atakujący nie będzie w stanie w nieskończoność przewidzieć przyszłych danych wyjściowych. Wynika to z mechanizmu ponownego wysiewu krwawnika.
- Yarrow ma pulę próbek entropii oddzieloną od klucza i ponownie umieszcza klucz tylko wtedy, gdy zawartość puli entropii jest całkowicie nieprzewidywalna. Taka konstrukcja zapobiega iteracyjnym atakom polegającym na zgadywaniu, w których atakujący z kluczem odgaduje następną próbkę i sprawdza wynik, obserwując następny wynik.
Cons
- Ponieważ dane wyjściowe Yarrowa są kryptograficzne, systemy korzystające z tych danych wyjściowych mogą być tylko tak bezpieczne, jak sam mechanizm generowania. Oznacza to, że napastnik, który może złamać mechanizm generowania, z łatwością złamie system zależny od wyników Yarrowa. Problemu tego nie da się rozwiązać poprzez zwiększenie akumulacji entropii.
- Krwawnik wymaga estymacji entropii, co jest bardzo dużym wyzwaniem dla wdrożeń. Trudno jest być pewnym, ile entropii zebrać przed użyciem go do ponownego zasiania PRNG. Ten problem rozwiązuje Fortuna (PRNG) , ulepszenie Yarrowa. Fortuna ma 32 pule do zbierania entropii i całkowicie usunęła estymator entropii.
- Siła krwawnika jest ograniczona rozmiarem klucza. Na przykład Yarrow-160 ma efektywny rozmiar klucza 160 bitów. Jeśli zabezpieczenie wymaga 256 bitów, Yarrow-160 nie jest w stanie wykonać tego zadania.
- Yarrow-160 używa SHA-1, który był powszechnie uważany za przestarzały ze względu na jego pierwszą publiczną kolizję.