Przewidywanie wyników rand () PHP

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

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.

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:

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.

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 .

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.