W poprzednim wpisie poruszyłem problem kiepskiego algorytmu generowania liczb pseudolosowych w PHP. Jednak to nie koniec problemów z wartościami losowymi. Programiści powinni sobie zdać sprawę z powtarzalności wyników losowania, a więc i tzw. paradoksu urodzinowego.
Zbierzmy w pokoju pewną liczbę osób. Każdą z nich spytajmy o datę urodzin. Ile musi być tych osób w pokoju, by prawdopodobieństwo tego, że 2 osoby obchodzą urodziny w tym samym dniu było większe niż 50%? Zastanów się dobrze. Czas na odpowiedź masz do końca następnego akapitu.
Prawdopodobieństwo nie jest do końca intuicyjne. Szansa, że w rzucie monetą trafimy orła jest równa 50%. Szansa, że w dwóch kolejnych rzutach trafimy dwa orły jest równa 25% – dwa razy mniej. W związku z tym, intuicyjnie, szansa na trafienie pod rząd 10 razy orła powinna być dziesięć razy mniejsza – 5%. Nieprawda. W grę wchodzą bowiem nie zależności liniowe, a wykładnicze. Owe 25% (czyli 0,25) wyliczamy podnosząc 0,5 (szansę na orła w jednym rzucie) do potęgi 2 (ilość rzutów). 0,5^2 = 0,25. Przy dziesięciu rzutach to prawdopodobieństwo wynosi 0.5^10 = 0,001.
Jak widać powyżej, prawdopodobieństwo ciężko brać intuicyjnie. W pokazanym wyżej pokoju, by spełnić nasz warunek, wystarczą 23 osoby! To zaskakująco mało. Należy o tym pamiętać za każdym razem, gdy liczba pseudolosowa lub hash służy do zabezpieczeń. Średnia ilość prób potrzebna do złamania metodą brute force w oparciu o prawdopodobieństwo (tzw. atak urodzinowy) to nie dzielenie ilości kombinacji przez 2, a tym bardziej nie wolno zakładać maksymalnej ilości kombinacji (bez dzielenia). Ta ilość prób wg ogólnego wzoru (wyprowadzenie tutaj w załączniku B) to tylko ok. 1,18 * sqrt(N) gdzie N oznacza ilość wszystkich możliwych kombinacji. Pamiętajmy o tym, gdy planujemy zabezpieczenia aplikacji.
Dodaj komentarz