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


202

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


14
Po zaszczepieniu wyjście z java.util.Random jest deterministyczną sekwencją liczb. Możesz tego nie chcieć.
Peter Štibraný

1
Czy kod inicjuje Randomjeden raz przy starcie, czy też inicjuje nowy dla każdego tokena? Mam nadzieję, że to głupie pytanie, ale pomyślałem, że sprawdzę.
Tom Anderson

8
Losowe ma tylko stan wewnętrzny 48-bitową i będzie powtórzyć po 2 ^ 48 połączeń do nextLong (), co oznacza, że nie przyniesie to możliwe longlub doublewartości.
Peter Lawrey,

3
Jest jeszcze jeden poważny problem. 64 bity oznaczają 1,84 * 10 ^ 19 możliwych kombinacji, co jest zbyt mało, aby wytrzymać wyrafinowany atak. Istnieją maszyny, które złamały 56-bitowy kod DES (współczynnik 256 mniej) z 90 * 10 ^ 9 kluczami na sekundę w ciągu 60 godzin. Użyj 128 bitów lub dwóch długości!
Thorsten S.

Odpowiedzi:


232

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 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 ...


4
Bardzo pomocne, być może możesz również wyjaśnić, jak działa SecureRandom (tak jak wyjaśniasz, jak działa Random) ..
gresdiplitude

4
To pokonuje cel bezpiecznego losowego
Azulflame

Wiem, nauczyłem się tej lekcji na własnej skórze. Ale twardy szyfr i trudno dostępne źródło działa dobrze. Notch mógł się czegoś o tym dowiedzieć (koduje hasło użytkownika w pliku .lastlogin, kodowanym za pomocą podstawowego szyfrowania przy użyciu „pliku haseł” jako klucza)
Azulflame

1
Prawdziwe pytanie tutaj: jeśli java może wygenerować bezpieczniejszy prng z podobnym API, dlaczego nie zastąpili uszkodzonego?
Joel Coehoorn

11
@JoelCoehoorn Nie jest tak, że Randomjest zepsuty - powinien być po prostu używany w różnych scenariuszach. Oczywiście zawsze możesz skorzystać z SecureRandom. Ale ogólnie SecureRandomjest zauważalnie wolniejszy niż czysty Random. Są przypadki, w których interesują Cię tylko dobre właściwości statystyczne i doskonała wydajność, ale tak naprawdę nie zależy ci na bezpieczeństwie: symulacje Monte-Carlo są dobrym przykładem. Skomentowałem to w podobnej odpowiedzi , być może okażą się przydatne.
wytłoczono

72

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.


Wymaga znacznie mniej niż 2 ^ 48, aby przewidzieć a Random, OP nie powinien w ogóle używać Random.
wytłoczono

@emboss: Mówię o brutalizacji.
Ashwin

1
Ostrożnie z Linuksem: może osiągnąć wyczerpanie entropii (więcej w VM niż w sprzęcie)! Spójrz na /proc/sys/kernel/random/entropy_availniektóre zrzuty wątków i sprawdź, czy nie trzeba długo czekać na czytanie/dev/random
Yves Martin

2
Zauważ, że Oracle JRE (przynajmniej 1.7) domyślnie współpracuje z / dev / urandom, a nie / dev / random, więc sufiks twojej odpowiedzi nie jest już poprawny. w celu sprawdzenia sprawdź $ JAVA_HOME / lib / security / java.security dla właściwości securerandom.source
Boaz

1
Nasz plik java.security miał securerandom.source = file: / dev / urandom zamiast file: /// dev / urandom (dwa ukośniki za dwukropkiem dla protokołu plików, a następnie jeden ukośnik dla katalogu głównego systemu plików), co powoduje jego cofnięcie na / dev / random, co spowodowało problemy z wyczerpaniem puli entropii. Nie można go edytować, więc musiałem ustawić właściwość systemową java.security.egd na właściwą podczas uruchamiania aplikacji.
maxpolk

11

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ć.


11
Jeśli weźmiesz dwa wystąpienia dowolnego PRNG i zapełnisz go tą samą wartością, zawsze otrzymasz te same losowe liczby, nawet użycie SecureRandom tego nie zmieni. Wszystkie PRNG są deterministyczne, a zatem przewidywalne, jeśli znasz ziarno.
Robert

1
Istnieją różne implementacje SecureRandom, niektóre są PRNG, inne nie. Z drugiej strony java.util.Random jest zawsze PRNG (zgodnie z definicją w Javadoc).
Peter Štibraný

3

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.


Nie sądzę, by pierwotne pytanie zawierało informację, że java.util.Randomimplementacja została użyta SecureRandomwewnętrznie, a także, że ich kod używa SecureRandomdo uruchomienia Random. Mimo to zgadzam się z obydwoma dotychczasowymi odpowiedziami; najlepiej użyć, SecureRandomaby uniknąć jednoznacznie deterministycznego rozwiązania.
Palpatim

2

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źć.


Poprawny. Zobacz, jak szybko złamać java.util.random na jazzy.id.au/default/2010/09/20/... !
ingyhere

2

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.


0

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ć.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.