Różnica między java.util.Random i java.security.SecureRandom

Mój zespół otrzymał kod po stronie serwera (w Javie), który generuje losowe tokeny, i mam pytanie dotyczące tego samego -

Cel tych tokenów jest dość wrażliwy - służy do identyfikatora sesji, linków do resetowania hasła itp. Dlatego muszą one być kryptograficznie losowe, aby ktoś ich nie zgadł lub nie zastosował brutalnej siły. Token jest „długi”, więc ma 64 bity.

Kod obecnie używa java.util.Randomklasy do generowania tych tokenów. Dokumentacja dla java.util.Randomjasno stwierdza co następuje:

Instancje java.util.Random nie są bezpieczne kryptograficznie. Zamiast tego rozważ użycie SecureRandom, aby uzyskać kryptograficznie bezpieczny generator liczb pseudolosowych do użytku przez aplikacje wrażliwe na bezpieczeństwo.

Jednak sposób, w jaki obecnie używa kod, jest java.util.Randomtaki - tworzy instancję java.security.SecureRandomklasy, a następnie używa SecureRandom.nextLong()metody do uzyskania zarodka, który jest używany do tworzenia instancji java.util.Randomklasy. Następnie używa java.util.Random.nextLong()metody do wygenerowania tokena.

Tak więc moje pytanie - czy nadal jest niepewne, biorąc pod uwagę, że java.util.Randomjest ono zaszczepiane java.security.SecureRandom? Czy muszę zmodyfikować kod, aby używał java.security.SecureRandomwyłącznie do generowania tokenów?

Obecnie ziarno kodu jest Randomjednorazowe przy starcie

Standardowa implementacja Oracle JDK 7 używa tak zwanego liniowego generatora zbieżnego do generowania losowych wartości java.util.Random.

Zaczerpnięty z java.util.Randomkodu źródłowego (JDK 7u2), z komentarza do metody protected int next(int bits), która generuje losowe wartości:

Jest to liniowy kongruencjalny generator liczb pseudolosowych, zdefiniowany przez DH Lehmera i opisany przez Donalda E. Knutha w The Art of Computer Programming, Tom 3: Seminumerical Algorytmy , sekcja 3.2.1.

Przewidywalność liniowych generatorów zbieżnych

Hugo Krawczyk napisał całkiem niezły artykuł o tym, jak można przewidzieć te LCG („Jak przewidzieć generatory kongruencjalne”). Jeśli masz szczęście i jesteś zainteresowany, nadal możesz znaleźć bezpłatną wersję do pobrania w Internecie. Istnieje wiele innych badań, które wyraźnie pokazują, że nigdy nie należy używać LCG do celów krytycznych dla bezpieczeństwa. Oznacza to również, że Twoje losowe liczby są teraz przewidywalne, czego nie potrzebujesz w przypadku identyfikatorów sesji i tym podobnych.

Jak zepsuć liniowy generator zbieżny

Założenie, że atakujący będzie musiał czekać na powtórzenie LCG po pełnym cyklu, jest błędne. Nawet przy optymalnym cyklu (moduł m w jego relacji powtarzalności) bardzo łatwo jest przewidzieć przyszłe wartości w znacznie krótszym czasie niż pełny cykl. W końcu to tylko garść modułowych równań, które należy rozwiązać, co staje się łatwe, gdy tylko zaobserwujesz wystarczającą wartość wyjściową LCG.

Bezpieczeństwo nie poprawia się dzięki „lepszemu” ziarnu. Po prostu nie ma znaczenia, czy zaszczepisz losową wartością wygenerowaną przez, SecureRandomczy nawet wygenerujesz wartość, rzucając kostką kilka razy.

Atakujący po prostu obliczy ziarno na podstawie zaobserwowanych wartości wyjściowych. To zajmuje znacznie mniej czasu niż 2 ^ 48 w przypadku java.util.Random. Niewierzący mogą wypróbować ten eksperyment , w którym wykazano, że można przewidzieć przyszłe Randomwyniki, obserwując tylko dwie (!) Wartości wyjściowe w czasie około 2 ^ 16. Na nowoczesnym komputerze nawet w sekundę można przewidzieć wynik liczb losowych.

Wniosek

Zastąp swój obecny kod. Używaj SecureRandomwyłącznie. Przynajmniej będziesz miał małą gwarancję, że wynik będzie trudny do przewidzenia. Jeśli chcesz właściwości kryptograficznie bezpiecznego PRNG (w twoim przypadku tego właśnie chcesz), musisz wybrać SecureRandomtylko. Sprytne podejście do zmiany sposobu, w jaki powinien być używany, prawie zawsze skutkuje czymś mniej bezpiecznym ...

Losowy ma tylko 48 bitów, przy czym jako SecureRandom może mieć do 128 bitów. Tak więc szanse na powtórzenie w bezpiecznym losie są bardzo małe.

Losowo używa system clockjako nasiona / lub do wygenerowania nasion. Można je więc łatwo odtworzyć, jeśli atakujący zna czas, w którym ziarno zostało wygenerowane. Ale SecureRandom bierze Random Dataod ciebie os(mogą to być odstępy między naciśnięciami klawiszy itp. - większość systemów operacyjnych zbiera te dane i przechowuje je w plikach /dev/random and /dev/urandom in case of linux/solaris)) i używa tego jako źródła.
Więc jeśli mały rozmiar tokena jest w porządku (w przypadku Random), możesz dalej używać swojego kodu bez żadnych zmian, ponieważ używasz SecureRandom do wygenerowania ziarna. Ale jeśli chcesz większych tokenów (które nie mogą podlegać brute force attacks), skorzystaj z SecureRandom -
W przypadku losowych 2^48wymaganych są tylko próby, przy dzisiejszych zaawansowanych procesorach możliwe jest złamanie go w praktycznym czasie. Jednak w przypadku bezpiecznych, losowych 2^128prób będą wymagane lata, które przekroczą nawet dzisiejsze zaawansowane maszyny.

Zobacz ten link, aby uzyskać więcej informacji.
EDYCJA
Po przeczytaniu linków dostarczonych przez @emboss, jasne jest, że ziarno, jakkolwiek losowe, nie powinno być używane z java.util.Random. Bardzo łatwo obliczyć ziarno, obserwując wydajność.

Przejdź do SecureRandom - użyj natywnego PRNG (jak podano w linku powyżej), ponieważ pobiera losowe wartości z /dev/randompliku dla każdego wywołanianextBytes(). W ten sposób atakujący obserwujący dane wyjściowe nie będzie w stanie niczego zrozumieć, chyba że kontroluje zawartość /dev/randompliku (co jest bardzo mało prawdopodobne)
. Algorytm sha1 prng oblicza ziarno tylko raz i jeśli maszyna wirtualna działa przez wiele miesięcy przy użyciu tego samego seed, może zostać złamany przez atakującego, który biernie obserwuje dane wyjściowe.

UWAGA - Jeśli dzwonisz nextBytes()szybciej, niż Twój system operacyjny jest w stanie zapisać losowe bajty (entropię) do /dev/random, możesz wpaść w kłopoty podczas korzystania z NATIVE PRNG . W takim przypadku użyj wystąpienia SHA1 PRNG SecureRandom i co kilka minut (lub jakiś interwał), zapisz to wystąpienie wartościąnextBytes()wystąpienia NATIVE PRNG SecureRandom. Uruchomienie tych dwóch równolegle zapewni regularne zapełnianie prawdziwych losowych wartości, a jednocześnie nie wyczerpuje entropii uzyskanej przez system operacyjny.

Jeśli uruchomisz dwa razy java.util.Random.nextLong()z tym samym ziarnem, wygeneruje ten sam numer. Ze względów bezpieczeństwa chcesz się trzymać, java.security.SecureRandomponieważ jest to o wiele mniej przewidywalne.

Do 2 Ćwiczenia są podobne, myślę, że po prostu trzeba zmienić Random, aby SecureRandomza pomocą narzędzia refactoring i większość istniejącego kodu będzie działać.

Jeśli zmiana istniejącego kodu jest niedrogim zadaniem, sugeruję użycie klasy SecureRandom zgodnie z sugestią Javadoc.

Nawet jeśli okaże się, że implementacja klasy Random używa klasy SecureRandom wewnętrznie. nie należy przyjmować za pewnik, że:

1. Inne implementacje maszyn wirtualnych robią to samo.
2. Implementacja klasy Random w przyszłych wersjach JDK nadal korzysta z klasy SecureRandom

Dlatego lepszym wyborem jest skorzystanie z sugestii dokumentacji i skorzystanie bezpośrednio z SecureRandom.

Obecna implementacja referencyjna java.util.Random.nextLong()wykonuje dwa wywołania metody, next(int)która bezpośrednio eksponuje 32-bitowy bieżący seed:

protected int next(int bits) {
    long nextseed;
    // calculate next seed: ...
    // and store it in the private "seed" field.
    return (int)(nextseed >>> (48 - bits));
}

public long nextLong() {
    // it's okay that the bottom word remains signed.
    return ((long)(next(32)) << 32) + next(32);
}

Górne 32 bity wyniku nextLong()to bity nasion w tym czasie. Ponieważ szerokość zarodka wynosi 48 bitów (mówi javadoc), wystarczy *, aby przejść do pozostałych 16 bitów (to tylko 65 536 prób), aby określić ziarno, które wygenerowało drugi 32 bit.

Gdy ziarno jest znane, można łatwo obliczyć wszystkie następujące tokeny.

Wykorzystując dane wyjściowe nextLong(), częściowo tajemnicę PNG, do tego stopnia, że ​​cały sekret można obliczyć z niewielkim wysiłkiem. Niebezpieczny!

* Potrzebny jest pewien wysiłek, jeśli drugi 32-bit jest ujemny, ale można to znaleźć.

Ziarno jest bez znaczenia. Dobry generator losowy różni się wybranym numerem pierwotnym. Każdy generator losowy zaczyna się od liczby i przechodzi przez „pierścień”. Co oznacza, że ​​przechodzisz od jednej liczby do drugiej ze starą wartością wewnętrzną. Ale po chwili osiągasz początek i zaczynasz wszystko od nowa. Więc biegasz cyklami. (wartość zwracana z generatora losowego nie jest wartością wewnętrzną)

Jeśli użyjesz liczby pierwszej do utworzenia pierścienia, wszystkie liczby w tym pierścieniu zostaną wybrane przed zakończeniem pełnego cyklu przez wszystkie możliwe liczby. Jeśli weźmiesz liczby inne niż pierwotne, nie wszystkie liczby zostaną wybrane i otrzymasz krótsze cykle.

Wyższe liczby pierwsze oznaczają dłuższe cykle, zanim ponownie powrócisz do pierwszego elementu. Bezpieczny generator losowy po prostu ma dłuższy cykl, zanim ponownie osiągnie początek, dlatego jest bezpieczniejszy. Nie można przewidzieć generowania liczb tak łatwo, jak przy krótszych cyklach.

Innymi słowy: musisz wymienić wszystko.

Spróbuję użyć bardzo podstawowych słów, abyś mógł łatwo zrozumieć różnicę między Random a secureRandom i ważnością SecureRandom Class.

Czy zastanawiałeś się kiedyś, jak generowane jest hasło jednorazowe? Aby wygenerować OTP, również używamy klas Random i SecureRandom. Teraz, aby wzmocnić OTP, SecureRandom jest lepszy, ponieważ wymagało 2 ^ 128 próby złamania OTP, co jest prawie niemożliwe na obecnej maszynie, ale jeśli użyjesz Random Class, twój OTP może zostać złamany przez kogoś, kto może zaszkodzić twoim danych, ponieważ zabrał tylko 2 ^ 48 spróbuj złamać.