Przewidywanie wyników rand () PHP

21

Czytałem w wielu źródłach, że dane wyjściowe PHP rand () są przewidywalne jako PRNG, i w większości akceptuję to jako fakt, ponieważ widziałem to w tak wielu miejscach.

Interesuje mnie proof-of-concept: jak mógłbym zająć się przewidywaniem wyników rand ()? Po przeczytaniu tego artykułu rozumiem, że liczba losowa jest liczbą zwracaną z listy rozpoczynającej się od wskaźnika (nasienia) - ale nie wyobrażam sobie, jak można to przewidzieć.

Czy ktoś mógłby rozsądnie dowiedzieć się, jakie losowe # zostało wygenerowane za pomocą rand () w danym momencie w ciągu kilku tysięcy zgadnięć? a nawet 10.000 domysłów? W jaki sposób?

To się zbliża, ponieważ widziałem bibliotekę auth, która używa rand () do generowania tokena dla użytkowników, którzy stracili hasła, i założyłem, że to potencjalna dziura w zabezpieczeniach. Od tego czasu zastąpiłem tę metodę haszowaniem mieszanki openssl_random_pseudo_bytes(), hashującego hasła i mikrotimu. Po zrobieniu tego zdałem sobie sprawę, że gdybym patrzył na zewnątrz, nie miałbym pojęcia, jak zgadnąć token, nawet wiedząc, że to md5 rand ().

Erik
źródło
„ale nie mogę sobie wyobrazić, jak to jest przewidywalne”? Najpierw musisz przeczytać na „ en.wikipedia.org/wiki/Linear_congruential_generator , abyś mógł zacząć wyobrażać sobie, jak to jest przewidywalne. Następnie możesz zrewidować swoje pytanie, aby wyeliminować zdziwienie i przejść do bardziej praktycznych kwestii inżynierii odwrotnej PHP źródło funkcji rand, aby zobaczyć, jak to działa
S.Lott
„Zakładałem, że to potencjalna dziura w zabezpieczeniach”? Tylko jeśli Evil Hacker może uzyskać losowe hasło użytkownika, użyj tabeli tęczy, aby cofnąć skrót MD5, aby odzyskać pierwotną wartość (przed haszowaniem), a następnie zagwarantować, że wykonali następne żądanie hasła. Teoretycznie możliwe, jak sądzę. Ale tylko jeśli mieli działający tęczowy stół dla przypadkowej liczby.
S.Lott
@ S.Lott - to nie jest kwestia hasła. System pozwala zresetować hasło i przesłać Ci e-mailem token używany w adresie URL. Token jest generowany przez MD5 (rand ()). Jeśli potrafisz przewidzieć wyjście rand (), możesz zmienić hasło każdego użytkownika, bez posiadania skrótu dla oryginału lub znajomości oryginału.
Erik
@Erik. Dobrze. Jeśli to pomoże, zamień „losowe hasło” na „losowy token”. Token może zostać wykorzystany tylko wtedy, gdy ktoś może rozwinąć skrót MD5 w celu odzyskania losowej liczby ORAZ upewnić się, że otrzyma następną losową liczbę. Przewidywanie następnego randa to tylko jedna mała część. Cofnięcie MD5 jest trudną częścią.
S.Lott
1
Zauważ, że MD5 (rand ()) ma tylko takie same zabezpieczenia jak rand (). Praktyczne jest zbudowanie tabeli przeglądowej MD5 (rand ()) -> rand () dla bardzo ograniczonego zestawu liczb. Z ograniczoną domeną rand () możesz wypróbować prostą brutalną siłę, chyba że istnieje mechanizm zapobiegający powtórnym próbom.
MZB

Odpowiedzi:

28

Możliwość odgadnięcia kolejnej wartości randwiąże się z możliwością ustalenia, z czym srandzostała wywołana. W szczególności wysiew srandz ustaloną liczbą daje przewidywalną wydajność ! Z interaktywnego monitu PHP:

[charles@charles-workstation ~]$ php -a
Interactive shell

php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > 

To nie tylko fuks. Większość wersji PHP * na większości platform ** generuje sekwencję 97, 97, 39, 77, 93, gdy srandjest z 1024.

Żeby było jasne, nie jest to problem z PHP, to jest problem z randsamą implementacją . Ten sam problem występuje w innych językach, które używają tej samej (lub podobnej) implementacji, w tym Perl.

Sztuczka polega na tym, że każda rozsądna wersja PHP będzie zawierała wstępnie srand„nieznaną” wartość. Och, ale tak naprawdę nie jest to nieznane. Od ext/standard/php_rand.h:

#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

Jest to więc matematyka z time()PID i wynikiem php_combined_lcg, który jest zdefiniowany w ext/standard/lcg.c. Nie zamierzam tu c & p, bo oczy mi się błyszczą i postanowiłem przestać polować.

Trochę Googling pokazuje, że inne obszary PHP nie mają najlepszych właściwości generowania losowości i wzywa do php_combined_lcgwyróżnienia się tutaj, szczególnie ten fragment analizy:

Ta funkcja ( gettimeofday) nie tylko przekazuje nam dokładny znacznik czasu serwera na srebrnym talerzu, ale także dodaje dane wyjściowe LCG, jeśli poprosimy o „więcej entropii” (z PHP uniqid).

Tak żeuniqid . Wydaje się, że wartość php_combined_lcgjest tym, co widzimy, gdy patrzymy na wynikowe cyfry szesnastkowe po wywołaniu uniqidz drugim argumentem ustawionym na wartość prawdziwą.

Gdzie teraz byliśmy?

O tak. srand.

Tak więc, jeśli kod, z którego próbujesz przewidzieć losowe wartości , nie wywołuje srand, musisz określić wartość podaną przez php_combined_lcg, którą możesz (pośrednio?) Uzyskać poprzez wywołanie uniqid. Mając tę ​​wartość w ręku, możliwe jest brutalne wymuszenie reszty wartości - time()PID i pewnej matematyki. Powiązany problem bezpieczeństwa dotyczy przerywania sesji, ale ta sama technika działałaby tutaj. Ponownie z artykułu:

Oto podsumowanie kroków ataku opisanych powyżej:
  • poczekaj, aż serwer się zrestartuje
  • pobierz wartość uniqid
  • brutalna siła nasion RNG z tego
  • odpytuje status online, aby poczekać na pojawienie się celu
  • przeplataj ankiety stanu z ankietami uniqid, aby śledzić aktualny czas serwera i wartość RNG
  • identyfikator sesji brute force przeciwko serwerowi przy użyciu czasu i przedziału wartości RNG ustalonego podczas odpytywania

Wystarczy wymienić ostatni krok zgodnie z wymaganiami.

(Ten problem bezpieczeństwa został zgłoszony we wcześniejszej wersji PHP (5.3.2) niż obecnie (5.3.6), więc możliwe jest, że zachowanie uniqidi / lub php_combined_lcguległo zmianie, więc ta konkretna technika może już nie być wykonalna. YMMV.)

Z drugiej strony, jeśli kod, który próbujesz wytworzyć, wywołuje srandręcznie , to chyba że używają czegoś wielokrotnie lepszego niż wynik php_combined_lcg, prawdopodobnie łatwiej będzie ci odgadnąć wartość i zainicjować lokalne generator z odpowiednią liczbą. Większość osób, które dzwoniłyby ręcznie, srandrównież nie zdawały sobie sprawy z tego, jak okropny jest to pomysł, a zatem prawdopodobnie nie zastosują lepszych wartości.

Warto zauważyć, że mt_randten sam problem dotyczy również tego samego problemu. Wysiew mt_srando znanej wartości da również przewidywalne wyniki. Oparcie się na entropii openssl_random_pseudo_bytesjest prawdopodobnie bezpieczniejszym zakładem.

tl; dr: Aby uzyskać najlepsze wyniki, nie uruchamiaj generatora liczb losowych PHP, a na miłość boską, nie narażaj uniqidużytkowników. Wykonanie jednego lub obu z nich może sprawić, że twoje losowe liczby będą bardziej zgadywalne.


Aktualizacja dla PHP 7:

PHP 7.0 wprowadza random_bytesi random_intjako podstawowe funkcje. Korzystają z implementacji CSPRNG systemu bazowego, dzięki czemu są wolni od problemów, jakie ma zalążkowy generator liczb losowych. Są skutecznie podobne openssl_random_pseudo_bytes, ale nie wymagają instalowania rozszerzenia. Polifill jest dostępny dla PHP5 .


*: Poprawka bezpieczeństwa Suhosin zmienia zachowanie randi powoduje mt_rand, że zawsze są one ponownie uruchamiane przy każdym wywołaniu. Suhosin jest dostarczany przez stronę trzecią. Niektóre dystrybucje Linuksa domyślnie włączają go do swoich oficjalnych pakietów PHP, podczas gdy inne udostępniają go jako opcję, a inne całkowicie go ignorują.

**: W zależności od platformy i używanych wywołań biblioteki, zostaną wygenerowane inne sekwencje niż tutaj udokumentowane, ale wyniki powinny być powtarzalne, chyba że zostanie użyta łatka Suhosin.

Charles
źródło
Dzięki Charles - między twoją odpowiedzią a przeczytaniem linku na generatorze liniowej zgodności z Tangurena czuję, że lepiej ją rozumiem. Już „wiedziałem”, że użycie rand () w ten sposób było złym pomysłem, ale wiem, dlaczego .
Erik
Wow, rekwizyty za dokładną, dobrze zapisaną odpowiedź, dzięki!
David Hobs,
10

Aby zilustrować wizualnie, jak nieprzypadkowa jest ta rand()funkcja, oto obraz, na którym wszystkie piksele składają się z „losowych” wartości czerwonych, zielonych i niebieskich:

Losowe wartości RGB

Zwykle na obrazach nie powinno być żadnych wzorów.

Próbowałem wywoływać srand()z różnymi wartościami, nie zmienia to przewidywalności tej funkcji.

Zauważ, że oba nie są kryptograficznie bezpieczne i dają przewidywalne wyniki.

minifif
źródło
7

dane wyjściowe PHP rand () są przewidywalne jako PRNG

Jest to liniowy generator zgodności . Oznacza to, że masz funkcję, która jest skutecznie: NEW_NUMBER = (A * OLD_NUMBER + B) MOD C. Jeśli sporządzisz wykres NEW_NUMBER vs OLD_NUMBER, zaczniesz widzieć ukośne linie. Niektóre uwagi na temat dokumentacji RAND PHP podają przykłady tego, jak to zrobić.

To się zbliża, ponieważ widziałem bibliotekę auth, która używa rand () do generowania tokena dla użytkowników, którzy stracili hasła, i założyłem, że to potencjalna dziura w zabezpieczeniach.

Na komputerze z systemem Windows maksymalna wartość RAND wynosi 2 ^ 15. Daje to atakującemu tylko 32 768 możliwości sprawdzenia.

Czy ktoś mógłby rozsądnie dowiedzieć się, jakie losowe # zostało wygenerowane za pomocą rand () w danym momencie w ciągu kilku tysięcy zgadnięć? a nawet 10.000 domysłów? W jaki sposób?

Chociaż ten artykuł nie jest dokładnie tym, którego szukasz, pokazuje, jak niektórzy badacze wzięli istniejącą implementację generatora liczb losowych i wykorzystali go do zarobienia pieniędzy na Texas Holdem. Jest 52! możliwe tasowane talie, ale implementacja wykorzystała 32-bitowy generator liczb losowych (który jest maksymalną liczbą z mt_getrandmax na komputerze z systemem Windows) i zaszczepił go czasem w milisekundach od północy. Zmniejszyło to liczbę możliwych potasowanych talii z około 2 ^ 226 do około 2 ^ 27, umożliwiając wyszukiwanie w czasie rzeczywistym i sprawdzenie, jaka talia została rozdana.

Po zrobieniu tego zdałem sobie sprawę, że gdybym patrzył na zewnątrz, nie miałbym pojęcia, jak odgadnąć token, nawet wiedząc, że jest to md5 rand ().

Polecam użycie czegoś w rodzinie SHA-2, ponieważ federalni uważają, że md5 jest zepsuty. Niektórzy ludzie używają google do odszyfrowywania skrótów md5, ponieważ są one tak powszechne. Wystarczy haszować, a następnie wrzucić hash do wyszukiwarki google - w zasadzie google stało się wielkim tęczowym stołem .

Tangurena
źródło
1

Naprawdę dokładniej jest powiedzieć, że biorąc pod uwagę losowo wygenerowaną liczbę, następna jest względnie przewidywalna. Jest tylko tyle liczb, ile może być. Ale to nie znaczy, że możesz to odgadnąć, a bardziej, że możesz napisać program, który robi to dość szybko.

pdr
źródło
1
Myślę, że następny numer jest całkowicie deterministyczny. Nie „względnie”, ale absolutnie. Problem z pseudolosowymi generatorami liczb polega na tym, że sekwencja przejdzie testy statystyczne. Dwie sąsiednie liczby, choć całkowicie deterministyczne, mogą mieć właściwości statystyczne wspólne z faktycznymi liczbami losowymi.
S.Lott
1
Kolejna liczba jest całkowicie deterministyczna. To właśnie oznacza „pseudo” w generatorze liczb pseudolosowych. Z drugiej strony informacje potrzebne do ustalenia, że ​​kolejny numer jest prawie niemożliwy do uzyskania w praktyce.
Rein Henrichs
@ S.Lott - Miałem wrażenie, że liczba może pojawić się wiele razy w 2 ^ 32 możliwych wynikach i że za każdym razem, gdy się pojawi, może następować inna liczba. Ale biorąc pod uwagę ziarno X, zwracając wynik Y, następny wynik zawsze będzie taki sam. Tak więc w praktyce może występować kilka liczb następujących po Y. Mogę się jednak mylić; dawno nie patrzyłem na PRNG.
pdr