Zagrajmy w pokera komputerowego, tylko ty, ja i serwer, któremu obaj ufamy. Serwer używa generatora liczb pseudolosowych, który jest inicjowany 32-bitowym ziarnem tuż przed rozpoczęciem gry. Istnieje więc około czterech miliardów możliwych talii.
Mam w ręce pięć kart - najwyraźniej nie gramy w Texas Hold 'Em. Załóżmy, że karty są rozdawane jedna dla mnie, jedna dla ciebie, jedna dla mnie, jedna dla ciebie i tak dalej. Mam więc pierwszą, trzecią, piątą, siódmą i dziewiątą kartę w talii.
Wcześniej uruchomiłem pseudolosowy generator liczb cztery miliardy razy, raz z każdym ziarnem i zapisałem pierwszą wygenerowaną kartę dla każdego z nich w bazie danych. Załóżmy, że moją pierwszą kartą jest królowa pik. To pokazuje tylko jedną jako pierwszą kartę w jednej na 52 możliwych talii, więc zmniejszyliśmy możliwe talie z czterech miliardów do około 80 milionów.
Załóżmy, że moją drugą kartą jest trójka kier. Teraz uruchamiam moje RNG 80 milionów razy więcej, używając 80 milionów nasion, które produkują królową pik jako pierwszą liczbę. Zajmuje mi to kilka sekund. Zapisuję wszystkie talie, które wytwarzają trójkę, jako trzecią kartę - drugą kartę w mojej ręce. To znowu tylko około 2% talii, więc teraz mamy do 2 milionów talii.
Załóżmy, że trzecia karta w mojej ręce to 7 trefl. Mam bazę danych 2 milionów nasion, które rozdają moje dwie karty; Uruchomiłem mój RNG kolejne 2 miliony razy, aby znaleźć 2% talii, które produkują 7 trefl jako trzecią kartę, a my mamy tylko 40 tysięcy talii.
Widzisz jak to idzie. Uruchomiłem mój RNG 40000 razy więcej, aby znaleźć wszystkie nasiona, które produkują moją czwartą kartę, i to prowadzi nas do 800 talii, a następnie uruchamiam go 800 razy więcej, aby uzyskać ~ 20 nasion, które produkują moją piątą kartę, a teraz po prostu wygeneruj te dwadzieścia talii kart i wiem, że masz jedną z dwudziestu możliwych rąk. Co więcej, mam bardzo dobry pomysł na to, co narysuję.
Czy rozumiesz teraz, dlaczego prawdziwa losowość jest ważna? Sposób, w jaki go opisujesz, wydaje ci się, że dystrybucja jest ważna, ale dystrybucja nie jest tym, co czyni proces losowym. Nieprzewidywalność sprawia, że proces jest losowy.
AKTUALIZACJA
Na podstawie komentarzy (obecnie usuniętych ze względu na ich niekonstruktywny charakter) co najmniej 0,3% osób, które to przeczytały, jest zdezorientowanych co do mojego punktu widzenia. Kiedy ludzie spierają się z punktami, których nie uczyniłem, lub gorzej, argumentują za punktami, które zrobiłem przy założeniu, że ich nie uczyniłem, wtedy wiem, że muszę wyjaśnić jaśniej i dokładniej.
Wydaje się, że istnieje szczególny zamęt w dystrybucji słów, dlatego chcę ostrożnie przywoływać wyrażenia .
Dostępne pytania to:
- Czym różnią się liczby pseudolosowe i liczby prawdziwie losowe?
- Dlaczego różnica jest ważna?
- Czy różnice mają coś wspólnego z rozkładem produkcji PRNG?
Zacznijmy od rozważenia idealnego sposobu na wygenerowanie losowej talii kart do gry w pokera. Następnie zobaczymy, jak inne techniki generowania talii są różne i czy można skorzystać z tej różnicy.
Zacznijmy od założenia, że mamy oznakowane magiczne pudełko TRNG
. Jako jego dane wejściowe podajemy mu liczbę całkowitą n większą lub równą jeden, a jako wynik daje nam prawdziwie losową liczbę od jednego do n włącznie. Dane wyjściowe pola są całkowicie nieprzewidywalne (jeśli podano liczbę inną niż jeden), a dowolna liczba między jednym i n jest równie prawdopodobna jak inna; to znaczy, że rozkład jest jednolity . (Istnieją inne bardziej zaawansowane statystyczne kontrole losowości, które moglibyśmy przeprowadzić; ignoruję ten punkt, ponieważ nie ma to związku z moim argumentem. TRNG jest z założenia statystycznie losowy).
Zaczynamy od tasowanej talii kart. Prosimy o podanie numeru od jednego do 52 - to znaczy TRNG(52)
,. Bez względu na liczbę, którą oddaje, odliczamy tyle kart z naszej posortowanej talii i usuwamy tę kartę. Staje się pierwszą kartą w tasowanej talii. Następnie pytamy TRNG(51)
i robimy to samo, aby wybrać drugą kartę i tak dalej.
Innym sposobem na to jest: jest ich 52! = 52 x 51 x 50 ... x 2 x 1 możliwe talie, czyli około 2226 . Jeden z nich wybraliśmy przypadkowo.
Teraz rozdajemy karty. Kiedy patrzę na moje karty, nie mam pojęcia, jakie masz karty. (Poza oczywistym faktem, że nie masz żadnej z moich kart). Mogą to być dowolne karty, z jednakowym prawdopodobieństwem.
Pozwólcie więc, że wyjaśnię to jasno. Mamy jednolity rozkład każdej indywidualnej produkcji TRNG(n)
; każdy wybiera liczbę od 1 do n z prawdopodobieństwem 1 / n. Rezultatem tego procesu jest to, że wybraliśmy jedną z 52! możliwe talie z prawdopodobieństwem 1/52 !, więc rozkład w zestawie możliwych talii jest również jednolity.
W porządku.
Załóżmy teraz, że mamy mniej magiczne pudełko, oznaczone PRNG
. Zanim będzie można go użyć, musi zostać zaszczepiony 32-bitową liczbą bez znaku.
NA BOK: Dlaczego 32 ? Czy nie można go obsadzić liczbą 64-, 256- lub 10000-bitową? Pewnie. Ale (1) w praktyce większość gotowych PRNG jest obsadzonych liczbą 32-bitową, i (2) jeśli masz 10000 bitów losowości, aby zrobić ziarno, to dlaczego w ogóle używasz PRNG? Masz już źródło 10000 bitów losowości!
W każdym razie wróć do tego, jak działa PRNG: po jego zaszczepieniu możesz go używać w taki sam sposób, jak używasz TRNG
. Oznacza to, że przekazujesz mu liczbę n, a ona zwraca liczbę od 1 do n włącznie. Ponadto rozkład tej produkcji jest mniej więcej równomierny . Oznacza to, że kiedy poprosimy PRNG
o liczbę od 1 do 6, otrzymamy 1, 2, 3, 4, 5 lub 6, każdy mniej więcej jedną szóstą czasu, bez względu na to, jakie było ziarno.
Chciałbym podkreślić tę kwestię kilka razy, ponieważ wydaje się, że to ona dezorientuje niektórych komentujących. Dystrybucja PRNG jest jednolita na co najmniej dwa sposoby. Po pierwsze, załóżmy, że wybieramy jakieś konkretne nasienie. Spodziewalibyśmy się, że sekwencja PRNG(6), PRNG(6), PRNG(6)...
milion razy dałaby jednolity rozkład liczb między 1 a 6. Po drugie, gdybyśmy wybrali milion różnych nasion i wzywali PRNG(6)
jeden raz dla każdego ziarenka, znowu oczekiwalibyśmy jednolitego rozkładu liczb od 1 do 6. Jednorodność PRNG we wszystkich tych operacjach nie ma związku z atakiem, który opisuję .
Mówi się, że proces ten jest pseudolosowy, ponieważ zachowanie pudełka jest w pełni deterministyczne; wybiera jedno z 2 32 możliwych zachowań w oparciu o ziarno. Oznacza to, że po zaszczepieniu PRNG(6), PRNG(6), PRNG(6), ...
tworzy sekwencję liczb o jednolitym rozkładzie, ale ta sekwencja jest całkowicie determinowana przez ziarno. Dla danej sekwencji wywołań, powiedzmy PRNG (52), PRNG (51) ... i tak dalej, istnieją tylko 2 32 możliwe sekwencje. Ziarno zasadniczo wybiera, które otrzymamy.
Aby wygenerować talię, serwer generuje teraz ziarno. (Jak? Będziemy wracać do tego punktu). Następnie nazywają PRNG(52)
, PRNG(51)
i tak dalej, aby wygenerować talię, podobnie jak przedtem.
Ten system jest podatny na opisany przeze mnie atak. Aby zaatakować serwer, najpierw z góry zapełniamy własną kopię pudełka wartością 0 oraz pytamy o to PRNG(52)
i zapisujemy. Następnie ponownie inicjujemy z 1, pytamy PRNG(52)
i zapisujemy to, aż do 2 32 -1.
Teraz serwer pokera, który używa PRNG do generowania talii, musi jakoś wygenerować ziarno. Nie ma znaczenia, jak to robią. Mogą zadzwonić, TRNG(2^32)
aby uzyskać naprawdę losowe ziarno. Lub mogą potraktować ten czas jako zalążek, który wcale nie jest przypadkowy; Wiem, która godzina to tyle co ty. Chodzi mi o to, że to nie ma znaczenia, bo mam swoją bazę danych . Kiedy widzę swoją pierwszą kartę, mogę wyeliminować 98% możliwych nasion. Kiedy widzę moją drugą kartę, mogę wyeliminować 98% więcej i tak dalej, aż w końcu mogę przejść do garści możliwych nasion i z dużym prawdopodobieństwem wiedzieć, co masz na ręce.
Teraz jeszcze raz chcę podkreślić, że założenie tutaj jest takie, że gdybyśmy zadzwonili PRNG(6)
milion razy, otrzymalibyśmy każdą liczbę mniej więcej jedną szóstą czasu . Ten rozkład jest (mniej więcej) jednolity , a jeśli jednolitość tego rozkładu jest wszystkim, na czym ci zależy , to dobrze. Chodziło o to, czy istnieją inne rzeczy niż to, na PRNG(6)
czym nam zależy? a odpowiedź brzmi tak . Dbamy również o nieprzewidywalność .
Innym sposobem spojrzenia na problem jest to, że chociaż dystrybucja miliona połączeń PRNG(6)
może być w porządku, ponieważ PRNG wybiera tylko 2 32 możliwe zachowania, nie może wygenerować każdej możliwej talii. Może wygenerować tylko 2 32 z 2 226 możliwych talii; mały ułamek. Więc rozkład w zestawie wszystkich talii jest bardzo zły. Ale znowu, podstawowy atak tutaj polega na tym, że jesteśmy w stanie z powodzeniem przewidzieć przeszłe i przyszłe zachowanie na PRNG
podstawie niewielkiej próbki jego wyników.
Powiem to po raz trzeci lub cztery, aby upewnić się, że to się zatopi. Istnieją tutaj trzy dystrybucje. Po pierwsze, rozkład procesu, który generuje losowe 32-bitowe ziarno. Może to być całkowicie losowe, nieprzewidywalne i jednolite, a atak nadal będzie działał . Po drugie, dystrybucja miliona połączeń do PRNG(6)
. To może być idealnie jednolite, a atak nadal będzie działał. Po trzecie, rozkład talii wybrany przez pseudolosowy proces, który opisałem. Ten rozkład jest wyjątkowo słaby; tylko niewielka część możliwych talii IRL może być wybrana. Atak zależy od przewidywalności zachowania PRNG na podstawie częściowej wiedzy o jego wyniku .
POMOC: Ten atak wymaga, aby osoba atakująca wiedziała lub była w stanie odgadnąć, jaki jest dokładny algorytm używany przez PRNG. Czy jest to realistyczne, czy nie, pytanie jest otwarte. Jednak projektując system bezpieczeństwa, musisz zaprojektować go tak, aby był zabezpieczony przed atakami, nawet jeśli osoba atakująca zna wszystkie algorytmy w programie . Mówiąc inaczej: część systemu bezpieczeństwa, która musi pozostać tajna, aby system był bezpieczny, nazywa się „kluczem”. Jeśli twój system zależy od bezpieczeństwa od algorytmów, których używasz, będąc tajemnicą, twój klucz zawiera te algorytmy . To jest wyjątkowo słaba pozycja!
Iść dalej.
Załóżmy teraz, że mamy oznaczone trzecie magiczne pudełko CPRNG
. Jest to wersja krypto-siły PRNG
. Zajmuje 256-bitowe ziarno, a nie 32-bitowe ziarno. Dzieli się z PRNG
właściwością, którą ziarno wybiera z jednego z 2 256 możliwych zachowań. I podobnie jak nasze inne maszyny, ma tę właściwość, że duża liczba wywołań CPRNG(n)
zapewnia jednolity rozkład wyników między 1 in: każde zdarza się 1 / n czasu. Czy możemy skierować przeciwko temu nasz atak?
Nasz oryginalny atak wymaga od nas przechowywania 2 32 mapowań od nasion do PRNG(52)
. Ale 2 256 to znacznie większa liczba; uruchamianie CPRNG(52)
tak wiele razy i zapisywanie wyników jest całkowicie niemożliwe .
Ale przypuśćmy, że istnieje inny sposób, aby wziąć wartość CPRNG(52)
i na tej podstawie wydedukować fakt o nasieniu? Do tej pory byliśmy dość głupi, po prostu brutalnie zmuszając wszystkie możliwe kombinacje. Czy możemy zajrzeć do magicznego pudełka, dowiedzieć się, jak to działa i wydedukować fakty na temat nasion na podstawie wyników?
Nie. Szczegóły są zbyt skomplikowane, aby je wyjaśnić, ale CPRNG są sprytnie zaprojektowane, dlatego nie można wydedukować żadnego przydatnego faktu na temat nasion z pierwszego wyjścia CPRNG(52)
lub z dowolnego podzbioru wyjścia, bez względu na to, jak duże .
OK, więc załóżmy teraz, że serwer używa CPRNG
do generowania talii. Potrzebuje 256-bitowego ziarna. Jak wybiera to ziarno? Jeśli wybierze jakąkolwiek wartość, którą atakujący może przewidzieć, nagle atak znów stanie się realny . Jeśli uda nam się ustalić, że z 2 256 możliwych nasion, tylko cztery miliardy z nich zostaną wybrane przez serwer, to wrócimy do pracy . Możemy ponownie przeprowadzić ten atak, zwracając uwagę tylko na niewielką liczbę nasion, które mogą zostać wygenerowane.
Serwer powinien zatem działać, aby zapewnić równomierną dystrybucję liczby 256-bitowej - to znaczy, że każdy możliwy seed jest wybierany z prawdopodobieństwem 1/2 256 . Zasadniczo serwer powinien dzwonić, TRNG(2^256)-1
aby wygenerować ziarno CPRNG
.
Co jeśli mogę zhakować serwer i zajrzeć do niego, aby zobaczyć, który materiał źródłowy został wybrany? W takim przypadku osoba atakująca zna całą przeszłość i przyszłość CPRNG . Autor serwera musi się wystrzegać przed tym atakiem! (Oczywiście, że jeśli uda mi się przeprowadzić ten atak, prawdopodobnie będę mógł po prostu przelać pieniądze bezpośrednio na moje konto bankowe, więc może to nie jest takie interesujące. Chodzi o to, że ziarno musi być trudnym do odgadnięcia sekretem i naprawdę losowa liczba 256-bitowa jest cholernie trudna do odgadnięcia.)
Wracając do mojego wcześniejszego punktu dotyczącego dogłębnej obrony: 256-bitowe ziarno jest kluczem do tego systemu bezpieczeństwa. Idea CPRNG polega na tym, że system jest bezpieczny, dopóki klucz jest bezpieczny ; nawet jeśli każdy inny fakt na temat algorytmu jest znany, tak długo, jak możesz zachować klucz w tajemnicy, karty przeciwnika są nieprzewidywalne.
OK, więc ziarno powinno być zarówno tajne, jak i równomiernie rozmieszczone, ponieważ jeśli nie, możemy przeprowadzić atak. Zakładamy, że rozkład produkcji CPRNG(n)
jest jednolity. Co z rozkładem w zestawie wszystkich możliwych talii?
Można powiedzieć: CPRNG ma do dyspozycji 2 256 możliwych sekwencji, ale są tylko 2 226 możliwych talii. Dlatego jest więcej możliwych sekwencji niż talie, więc nic nam nie jest; każda możliwa talia IRL jest teraz (z dużym prawdopodobieństwem) możliwa w tym systemie. To dobry argument, z wyjątkiem ...
2 226 to tylko przybliżenie 52 !. Podziel to. 2 256/52 ! nie może być liczbą całkowitą, ponieważ z jednej strony 52! jest podzielny przez 3, ale nie ma potęgi dwóch! Ponieważ nie jest to teraz liczba całkowita, mamy sytuację, w której wszystkie talie są możliwe , ale niektóre talie są bardziej prawdopodobne niż inne .
Jeśli nie jest to jasne, rozważ sytuację z mniejszymi liczbami. Załóżmy, że mamy trzy karty, A, B i C. Załóżmy, że używamy PRNG z 8-bitowym ziarnem, więc istnieje 256 możliwych nasion. Istnieje 256 możliwych wyników PRNG(3)
zależnych od nasion; nie ma możliwości, aby jedna trzecia z nich była A, jedna trzecia z nich była B, a jedna trzecia z nich była C, ponieważ 256 nie jest równomiernie podzielne przez 3. Musi być niewielki błąd względem jednego z nich.
Podobnie 52 nie dzieli się równomiernie na 2 256 , więc niektóre karty muszą mieć pewne odchylenie jako pierwsza wybrana karta, a odchylenie od innych.
W naszym oryginalnym systemie z 32-bitowym ziarnem nastąpiło ogromne odchylenie i ogromna większość możliwych talii nigdy nie została wyprodukowana. W tym systemie można wyprodukować wszystkie talie, ale ich rozkład jest nadal wadliwy . Niektóre pokłady są bardzo nieznacznie bardziej prawdopodobne niż inne.
Teraz pytanie brzmi: czy mamy atak oparty na tej usterce? a odpowiedź jest w praktyce, prawdopodobnie nie . CPRNG są zaprojektowane w taki sposób, że jeśli ziarno jest naprawdę losowe, wówczas obliczenie różnicy między CPRNG
i jest niewykonalne obliczeniowo TRNG
.
OK, podsumujmy.
Czym różnią się liczby pseudolosowe i liczby prawdziwie losowe?
Różnią się poziomem przewidywalności, którą wykazują.
- Prawdziwie losowe liczby nie są przewidywalne.
- Wszystkie liczby pseudolosowe są przewidywalne, jeśli ziarno można określić lub zgadnąć.
Dlaczego różnica jest ważna?
Ponieważ istnieją aplikacje, w których bezpieczeństwo systemu zależy od nieprzewidywalności .
- Jeśli do wybrania każdej karty zostanie użyty TRNG, wówczas system będzie niedostępny.
- Jeśli do wybrania każdej karty zostanie użyty CPRNG, system jest bezpieczny, jeśli ziarno jest zarówno nieprzewidywalne, jak i nieznane.
- Jeśli używany jest zwykły PRNG z małą przestrzenią początkową, wówczas system nie jest bezpieczny, niezależnie od tego, czy ziarno jest nieprzewidywalne czy nieznane; wystarczająco mała przestrzeń nasienna jest podatna na ataki typu brute force opisanego przeze mnie.
Czy różnica ma coś wspólnego z rozkładem produkcji PRNG?
Jednorodność dystrybucji lub jej brak dla poszczególnych połączeń do RNG(n)
nie ma związku z atakami, które opisałem.
Jak widzieliśmy, zarówno a, jak PRNG
i CPRNG
produkują słabe rozkłady prawdopodobieństwa wyboru dowolnej indywidualnej talii ze wszystkich możliwych talii. PRNG
Jest znacznie gorzej, ale obie mają problemy.
Jeszcze jedno pytanie:
Jeśli TRNG jest o wiele lepszy niż CPRNG, co z kolei jest o wiele lepsze niż PRNG, dlaczego ktoś używa CPRNG lub PRNG?
Dwa powody.
Po pierwsze: wydatek. TRNG jest drogi . Generowanie naprawdę losowych liczb jest trudne. CPRNG dają dobre wyniki dla dowolnie wielu połączeń z tylko jednym połączeniem do TRNG dla materiału siewnego. Wadą jest oczywiście to , że musisz zachować to ziarno w tajemnicy .
Po drugie: czasami chcemy przewidywalności i zależy nam tylko na dobrej dystrybucji. Jeśli generujesz „losowe” dane jako dane wejściowe programu dla zestawu testowego, a to pokazuje błąd, fajnie byłoby, gdyby ponowne uruchomienie zestawu testowego spowodowało błąd!
Mam nadzieję, że jest to teraz o wiele bardziej jasne.
Wreszcie, jeśli ci się podobało, możesz cieszyć się dalszą lekturą na temat losowości i permutacji: