Ponieważ Garbage Collection jest niedeterministyczny, dlaczego nie jest wykorzystywany do bezpiecznego generowania liczb losowych?

13

Rozumiem, że / dev / random jest dobrym źródłem entropii i jest to zwykle używane. Tak jak czytam na GC, przynajmniej w Javie, wydaje się akceptowane, że demon odśmiecania działa w sposób niedeterministyczny . Jeśli to prawda, to dlaczego nie używamy czasu wyrzucania elementów bezużytecznych jako źródła entropii zamiast zmiennej / dev / random?

trzecia
źródło
7
spójrz na niektóre dokumenty dotyczące funkcji rand () w standardowej bibliotece C. W szczególności wzywają, że chociaż podają ci liczby, które wydają się losowe, nie mogą być używane dla bezpieczeństwa. Twój typowy śmieciarz prawdopodobnie należałby do tej samej kategorii. Jeśli zamierzasz użyć jednego ze względów bezpieczeństwa, musisz upewnić się, że używasz bezpiecznego kryptograficznie modułu do usuwania śmieci.
DXM,
15
coś niedeterministycznego może być nadal wysoce przewidywalne
maniak zapadkowy
7
W tym przypadku „niedeterministyczny” jest złym opisem. Garbage collector jest systemem całkowicie deterministycznym i jeśli masz pełną wiedzę o jego stanie i stanie programu, który go używa, możesz deterministycznie przewidzieć wyniki.
Gort the Robot
4
@DXM czy znasz dobrą implementację kryptograficznie bezpiecznego modułu do usuwania śmieci? ;)
AJMansfield
7
„Każdy, kto rozważa arytmetyczne metody tworzenia losowych cyfr, jest oczywiście w stanie grzechu”. - John von Neumann
Mark Adler,

Odpowiedzi:

58

„Nieokreślony” i „losowy” to dwa zupełnie różne pojęcia.

Dokładne działanie śmieciarza nie jest określone i zależy od śmieciarza (zwykle implementowane przez pewnego rodzaju maszynę wirtualną, ale niekoniecznie).

Dlatego nie masz określonego (tj. Deterministycznego) czasu, w którym śmieci będą zbierane.

Jednak każda implementacja będzie podlegać pewnym regułom i istnieje duża szansa, że ​​dwa kolejne uruchomienia tego samego programu będą miały bardzo podobne wzorce wyrzucania elementów bezużytecznych.

Dlatego rzeczywista entropia dostarczona przez moduł wyrzucania elementów bezużytecznych byłaby bardzo niska (i ustalenie, które części można faktycznie użyć jako entropii, będzie trudne).

Dla porównania: A HashMapw Javie nie gwarantuje żadnej kolejności pobierania dla swoich członków (w zasadzie dlatego, że zagwarantowanie, że doda koszty ogólne, które w większości przypadków nie są warte zapłaty). Jednak dla danej implementacji i danego zestawu wstawień / usunięć można zdecydowanie obliczyć wynikową kolejność. To, że nie ma gwarancji na dane zamówienie, nie oznacza, że ​​zamówienie jest losowe.

Joachim Sauer
źródło
20
Myślę, że byłoby słuszne stwierdzenie, że jeśli komputer kiedykolwiek robi coś, co w rzeczywistości nie jest deterministyczne, to komputer jest zepsuty.
Schilcote
Niedeterministyczny może również oznaczać, że opiera się on na jakimś stanie zewnętrznym dla danego programu, który sam może być deterministyczny, ale będzie całkowicie niezwiązany z samym programem, a więc może być różny przy każdym uruchomieniu programu.
asmeurer
@asmeurer Nie sądzę, żebym słyszał te warunki w takim kontekście. W rzeczywistości nie jestem nawet pewien, co masz na myśli: każdy program, który pobiera dane zewnętrzne (czyli najbardziej przydatne programy) „opiera się na jakimś stanie zewnętrznym”, ale to nie czyni go niedeterministycznym.
us2012
2
@Schilcote: Niektóre nowoczesne procesory mają niedeterministyczne (prawdziwe) RNG zaimplementowane sprzętowo. Są to naprawdę niedeterministyczne fizyki aż do poziomu kwantowego.
MSalters
2
@Schilcote Nawet bez wyspecjalizowanych instrukcji RNG (RDRAND Intela i RDSEED) komputer nie jest całkowicie deterministyczny. Niektóre czasy nie są całkowicie określone i mogą zależeć od czynników zewnętrznych, takich jak temperatura.
CodesInChaos
8

Po pierwsze, musimy uważać, aby nie wpaść w pułapkę rozumowania poprzez manipulację zwykłymi słowami. Na przykład moglibyśmy zapytać, skoro NFA jest „niedeterministycznym automatem skończonym”, dlaczego nie wykorzystamy go do uzyskania liczb losowych? W takim przypadku byłoby tak, ponieważ nie to oznacza „niedeterministyczny” w NFA; w rzeczywistości, gdy symulujemy NFA, na danych wejściowych zachowanie symulacji jest całkowicie deterministyczne.

„Deterministyczny” jest załadowaną frazą. Dla programisty lub informatyka zachowanie niedeterministyczne oznacza po prostu „określenie dokładnego zachowania, o którym trudno pomyśleć”, i zależy od zbyt wielu czynników, w tym wkładu programu.

Nie oznacza to jednak, że nie jest deterministyczne dla osoby zmotywowanej do ataku na kryptosystem. Czasami czynniki środowiskowe i dane wejściowe mogą zostać określone, a powtarzalne wzorce wyłaniają się z zachowania „niedeterministycznego”.

Kaz
źródło