Wchodzę do środka i porozmawiam trochę o entropii i prawdopodobieństwie i mam nadzieję, że pomoże ci to zrozumieć.
Po pierwsze, czym jest prawdopodobieństwo? W rzeczywistości jest to otwarte pytanie wśród statystyków, ale oto definicja częstości: mówimy, że jeśli uczciwa moneta zostanie rzucona, to z prawdopodobieństwem 0,5 wypadnie reszka. Jeśli jednak rzucisz monetą, możesz zauważyć, że pierwsze pięć wyników to wszystkie orły, co nie wygląda dobrze. Tak więc, osoba często używająca tego nurtu mówi, że gdybyś rzucił monetą „wystarczająco” razy, w końcu okaże się, że jeden na dwa rzuty monetą to orzeł.
Kluczem jest to prawdopodobieństwo nie mówi nic o tym, co się faktycznie stanie . Hasło o dużej entropii można było odgadnąć przy pierwszej próbie przez zwykłe szczęście, niezależnie od możliwych wyników itd.
A teraz czym jest entropia? Jeśli zacząłeś mówić „no cóż, to liczba możliwych wyników…”, możesz mieć rację w kontekście generowania pewnych losowych danych, ale jest to doskonały przykład tego, gdzie naprawdę musisz zrozumieć, co się dzieje pod spodem.
Po pierwsze, porozmawiajmy o informacji o sobie. Jest to zmienna losowa (co oznacza, że istnieje wiele możliwych wyników), która zmienia się w zależności od prawdopodobieństwa każdego wyniku (a następnie bierzemy -log2 (P (X)), aby zakodować ją w „bity” informacji). Musimy więc przypisać każdemu wynikowi prawdopodobieństwo.
Jak zauważyli inni, niektóre warianty wyboru kodu PIN są bardziej prawdopodobne. Wszystkie te same liczby (1111, 2222, 3333, ...), urodziny (20XX, 19XX) i tak dalej. Powinieneś przypisać większe prawdopodobieństwo tym liczbom, ponieważ po prostu ludzie są bardziej skłonni do ich wybierania i na pewno nie wybiorą losowej sekwencji. To, jak przypiszesz prawdopodobieństwo innym liczbom, zależy wyłącznie od Ciebie i naprawdę zależy od tego, ile wiesz o procesie wybierania pinezki.
Otóż, entropia, lub aby uszczęśliwić @codesinchaos, szczególnie entropia Shannona, jest średnią dystrybucji informacji o sobie. Jest to „najbardziej prawdopodobna” wartość informacji o sobie, biorąc pod uwagę prawdopodobieństwo każdego wyboru. Co to znaczy? Jak mówi obecna, najczęściej wybierana odpowiedź, jest to miara procesu wyboru i jego dobra, a nie sama szpilka.
Co się dzieje, gdy wybierasz opcje o wysokim prawdopodobieństwie, takie jak 1111, 2222, 3333 ? Te wyniki dają bardzo niską informację o sobie (-log (P (X)) jest małe dla dużych prawdopodobieństw, ponieważ spodziewamy się ich wystąpienia), więc ich usunięcie przesuwa rozkład w prawo, tj. Przesuwa lokalizację rozkładu w kierunku Centrum. To zwiększy jego średnią. Zatem usunięcie wyborów, które większość ludzi w przeciwnym razie dokonałaby z dużym prawdopodobieństwem faktycznie zwiększa entropię .
Spójrzmy na entropię w inny sposób: jeśli zamierzasz odgadnąć PINy, w jakiej kolejności czy spróbowałbyś ich (zakładając brak blokady)? Zacząłbyś od najbardziej prawdopodobnych PIN-ów na pewno. Entropia mówi, że jeśli powtórzysz ten eksperyment dostatecznie dużo razy (np. Spróbujesz odgadnąć PIN dużej liczby kart, których PINy zostały wybrane zgodnie z tą samą logiką), wtedy wybór niższej entropii da tobie, atakującemu, większy sukces szybko.
Ponownie, pozostaje kwestią tego, co może się wydarzyć w teoretycznym przypadku wielu kart, a nie co może się wydarzyć, ponieważ atakującemu ma szczęście .
Oto twoje podsumowanie wykonawcze:
- To, czym entropia się stanie, zależy od tego, jak przypiszesz prawdopodobieństwa do przestrzeni wyników.
- Bez wątpienia, jeśli pozostawisz ludziom wybór PIN-ów, wybiorą one określone wartości z dużo większym prawdopodobieństwem niż inne.
- Oznacza to, że nie możesz założyć, że podstawowy rozkład jest jednolity i powiedzieć „entropia == liczba wyników”.
- Jeśli usuniesz opcje złego wyboru o największym prawdopodobieństwie, entropia rośnie.
- Entropia, podobnie jak prawdopodobieństwo prawidłowego odgadnięcia, nie mówi absolutnie nic o tym, czy atakujący będzie miał szczęście i poprawnie odgadnie Twój kod PIN. Mówi po prostu, że w teorii lepsza entropia utrudnia napastnikowi.
Aby zakończyć moją odpowiedź, przyjrzyjmy się praktycznym aspektom. Jeśli mamy zamiar porównać do haseł, opcji wyjściowych funkcji skrótu lub losowych danych, kody PIN są do niczego. Jeśli dasz atakującemu i obrońcy wolny wybór zgadywanego kodu PIN i żadnych innych informacji, liczba trafnych przypuszczeń w 50% przypadków (paradoks urodzin) jest absurdalnie niska. Kody PIN byłyby kiepskimi funkcjami skrótu.
Jednak ludzie nie mogą bardzo dobrze zapamiętać 128-bitowych danych, zwłaszcza gdy są pijani i próbują zapłacić za kebab za pomocą chip-and-pin. Kody PIN są zatem pragmatycznym kompromisem i przy trzech domysłach jako ograniczeniu, oprócz tego, że atakujący ma dużo szczęścia, powinieneś być bezpieczny.
TL; DR Usunięcie wyboru bardziej prawdopodobnego Kody PIN z możliwych wyborów zwiększają Twoje szanse w obliczu napastnika, który nie będzie zgadywał przypadkowo (tj. Większość napastników).
Edytuj: Myślę, że ta dyskusja uzasadnia teraz trochę matematyki. Oto, co zamierzam założyć w moich obliczeniach:
- Używamy 4-cyfrowych PIN-ów
-
Dane z linku Raesene są poprawne, tj .:
# 1 1234 10,713% # 2 1111 6,016% # 3 0000 1,881% # 4 1212 1,197% # 5 7777 0,745% # 6 1004 0,616% # 7 2000 0,613% # 8 4444 0,526% # 9 2222 0,516% # 10 6969 0,512% # 11 9999 0,451% # 12 3333 0,419% # 13 5555 0,395% # 14 6666 0,391% # 15 1122 0,366% # 16 1313 0,304% # 17 8888 0,303% # 18 4321 0,293% # 19 2001 0,290% # 20 1010 0,285%
- Zakładam również, że jakikolwiek PIN niewymieniony na tej liście ma równe szanse na wybranie z pozostałych „nieprzydzielonych” prawdopodobieństw (1-całkowite prawdopodobieństwo wykorzystane powyżej). Jest to prawie na pewno niepoprawne, ale mamy tylko tyle danych.
Aby to obliczyć, użyłem następującego kodu:
def shannon_entropy (prawdopodobieństwa ): składki = [p * (-1 * log (p, 2)) dla p prawdopodobieństw] zwracana suma (składki)
Oblicza rzeczywistą entropię Shannona dla danego zbioru prawdopodobieństw .
import itertoolstotal_outcome = 10,0 ^ 4probability_random_outcome = 1 / total_outcomeprobability_random_outcomemaximum_entropy = -log (probability_random_outcome, 2) maximum_entropymaximum_entropy_probability_list = list (itertopopy_entrale_problem. maximum_entropy) print (maximum_entropy_calculated)
Pokazuje, że moja funkcja dokładnie oblicza maksymalną entropię, biorąc listę 10 ^ 4 prawdopodobieństw, każde o wartości 1/10 ^ 4.
Następnie
probability_list_one = [10,713 / 100, 6,016 / 100, 1,881 / 100, 1,197 / 100, 0,745 / 100, 0,616 / 100, 0,613 / 100, 0,526 / 100, 0,516 / 100, 0,512 / 100, 0,451 / 100, 0,419 / 100, 0,395 / 100, 0,391 / 100, 0,366 / 100, 0,304 / 100, 0,303 / 100,0,293 / 100,0,290 / 100,0,285 / 100] result_count_one = 10 ^ 4 - len (probability_list_one) print ("Outcome count 1:", result_count_one) probability_consumed_one = sum (probability_list_one) print ("Prawdopodobieństwo wykorzystane według listy: ", probability_consumed_one) probability_ro_one = (1-probability_consumed_one) / result_count_oneentropy_probability_list_one = probability_list_one + list (itertools.repeat (probability_ro_one, wynik_count_one)) entropy_one = shannonon_entrcode>
Tutaj, jak powiedziałem powyżej, biorę te 20 prawdopodobieństw i zakładam, że pozostałe prawdopodobieństwa są równomiernie rozłożone między pozostałe wyniki, poprzez równomierne rozszerzenie listy o każdy zestaw prawdopodobieństw. Obliczenia są wykonywane.
probability_list_two = [6,016 / 100, 1,881 / 100, 1,197 / 100, 0,745 / 100, 0,616 / 100, 0,613 / 100, 0,526 / 100,0,516 / 100, 0,512 / 100, 0,451 / 100, 0,419 / 100, 0,395 / 100, 0,391 / 100, 0,366 / 100, 0,304 / 100, 0,303 / 100, 0,293 / 100, 0,290 / 100, 0,285 / 100] liczba_wyników = 10 ^ 4 - len (probability_list_two) -1print ("Licznik wyników 2:", result_count_two) probability_consumed_two = sum (probability_list_two) print ("Prawdopodobieństwo zużyte przez listę:", probability_consumed_two) probability_ro_two = (1-probability_consumed_two) / result_count_two .repeat (probability_ro_two, result_count_two))) entropy_two = shannon_entropy (entropy_probability_list_two) entropy_two
W tym przypadku usuwam najbardziej prawdopodobny PIN 1111 i ponownie obliczam entropię.
Na podstawie tych wyników można zobaczyć, że losowe wybranie kodu PIN ma 13,2877 bitów entropii. Powtórzenie tego eksperymentu z usuniętym jednym kodem PIN daje nam 13,2876 bitów.
Wybierając PIN, biorąc pod uwagę te prawdopodobieństwa wyboru dla tych 20 PIN-ów, w przeciwnym razie, wybór losowy oznacza wybór 11,40 bitów entropii z 13,2877 bitów. Z tej bazy blokowanie PIN 1111 iw inny sposób dopuszczanie pozostałych 19 oczywistych PIN-ów i wszystkich innych PIN-ów wybranych z równym prawdopodobieństwem ma entropię 12,33 bitów z możliwych 13,2876 bitów.
Mam nadzieję, że to wyjaśnia, dlaczego wiele odpowiedzi mówi, że entropia spada, a nie rośnie. Rozważają maksymalną możliwą entropię, a nie średnią entropię (entropię Shannona) systemu, biorąc pod uwagę możliwość wyboru. Lepszą miarą jest entropia Shannona, ponieważ bierze pod uwagę ogólne prawdopodobieństwo każdego wyboru, a więc sposób, w jaki atakujący prawdopodobnie będzie postępował w ataku.
Jak widać , blokując ten PIN 1111, znacząco zwiększa entropię Shannona, przy niewielkim koszcie ogólnej możliwej entropii. Jeśli chcesz pokłócić się o entropię, zasadniczo usunięcie PIN 1111 bardzo pomaga.
Dla odniesienia ten komiks XKCD oblicza entropię słabych haseł na około 28 bitach i entropię dobrych wyższa, przy 44 bitach. Znowu zależy to od tego, jakie założenia są poczynione co do prawdopodobieństwa pewnych wyborów , ale powinno to również pokazać, że PINy są do dupy pod względem entropii, a limit N-prób dla małego N jest jedynym rozsądnym sposobem kontynuuj.
Arkusz mędrca publicznego