Mózg to fascynujące ustrojstwo. Czasami zastanawiam się, czy to ja posiadam mózg, czy mój mózg posiada mnie. Na przykład lubi wybrać sobie temat, nad którym postanowi sobie pracować, kompletnie ignorując przy tym fakt, że pora bardziej odpowiednia do snu, niż do myślenia. Mogę albo usiłować spać (czyli wiercić się przez najbliższą godzinę), albo temat pokonać. Przy okazji temat jest odrobinę związany z poprzednią zagadką, więc będę miał mniejsze wyrzuty sumienia związane z chwilowym brakiem kontynuacji tematu.
Ulf Nitj’sefni
Przejdźmy do sedna. Podczas bardzo interesującej rozmowy (dziękuję) pojawiło się pytanie o długość salta, której bym użył. Cóż, gdybym nie musiał się przejmować oszczędnością miejsca, wykorzystałbym salt o długości 256 bitów. Nie dlatego, by tak duży salt w istotny sposób zwalniał czas obliczeń (aczkolwiek długość hashowanych danych ma pewien wpływ na czas wykonania operacji czego praktyczne wykorzystanie miało miejsce w ostatnim ataku na TLS, patrz: Attack of the week: TLS timing oracles).
To po co taki gigantyczny salt? Salt służy do tego, by atak z użyciem rainbow tables był nieopłacalny (takie ładne słówko infeasible). Chodzi o czas przygotowania tablic i miejsce potrzebne do ich przechowania. I teraz właśnie brain scratcher. A co w przypadku, gdy sobie przygotuję tablice korzystając ze stałego salta 0x999b (16 bitów). Oczywiście zakładam, że hashe haseł również są generowane z użyciem salta o takiej długości. Czy będę miał z takiej tablicy jakiś pożytek?
Odpowiedź brzmi - to zależy. Na przykład od tego, ile hashy haseł mam do złamania.
16 bitów to tylko 65536 możliwych wartości salt. Jeśli weźmiemy pod uwagę, że z LinkedIn wyciekło ponad 6 milionów haseł (zależy, gdzie sprawdzać) to okazuje się, że przy takiej ilości haseł ponad 90 z nich powinno korzystać z mojego wymyślonego salta. Gdyby salt miał tylko 8 bitów, takich haseł/hashy byłoby ponad 20 000. Dla 90 haseł cała zabawa nie ma sensu, dla 20 000 już bardziej.
Druga sprawa - salt ma taki "efekt uboczny", że każde hasło trzeba łamać oddzielnie. W tym sensie, że jeśli dla dwóch różnych hashy chcemy sprawdzić pewną wartość, całą operację hashowania musimy wykonać dwa razy z użyciem salta właściwego hasha. Ale jeśli tak się złoży, że ilość hashy jest większa, niż ilość możliwych wartości salt, znów można sprawdzać kilka hashy jednocześnie (tych z tym samym salt).
Sensowne wydaje mi się następujące podejście:
- ile maksymalnie hashy haseł może znajdować się w bazie?
- podnieś tę wartość do kwadratu, wylicz log2 z tej wartości,
- wyliczona wartość zaokrąglona w górę to długość salt w bitach,
Dlaczego tak? Bo wówczas nawet przy maksymalnej ilości haseł w bazie jest tylko jakieś 50% szans, że dwa różne hashe korzystają z tego samego salt. I tu dochodzimy do mojej odpowiedzi o salt długości 256 bitów. Oznacza to, że dopiero w próbce 2**128 haseł można spodziewać się z 50% prawdopodobieństwem wystąpienia tego samego salta więcej niż raz. Jak paranoja, to pełną gębą. A co!
I by nawiązać do pytania z zagadki. Tam wartość losowa miała długość 8 bitów. Założenia mówiły o generowaniu 60 identyfikatorów w ciągu minuty. Ponieważ cały identyfikator składał się z części opartej o czas i części "losowej", wartość "losowa" powinna być unikalna w obrębie tych 60 losowanych wartości. Problem w tym, że z bardzo dużym prawdopodobieństwem nie była, dowód empiryczny:
In [110]: len(set([os.urandom(1) for i in range(60)])) Out[110]: 53 In [111]: len(set([os.urandom(1) for i in range(60)])) Out[111]: 55 In [112]: len(set([os.urandom(1) for i in range(60)])) Out[112]: 54 In [113]: len(set([os.urandom(1) for i in range(60)])) Out[113]: 53
Na wyjściu podana jest ilość unikalnych wylosowanych wartości. Za każdym razem jest to mniej niż 60, bo losowana jest wielokrotnie ta sama wartość. Wyjaśnienie: Birthday attack. Wydłużenie części losowej do 12 bitów zgodnie z oczekiwaniami poprawia sytuację, ale nie rozwiązuje problemu:
In [144]: len(set([struct.unpack("H", os.urandom(2))[0] & 0xfff for i in range(60)])) Out[144]: 59 In [145]: len(set([struct.unpack("H", os.urandom(2))[0] & 0xfff for i in range(60)])) Out[145]: 59 In [146]: len(set([struct.unpack("H", os.urandom(2))[0] & 0xfff for i in range(60)])) Out[146]: 60 In [147]: len(set([struct.unpack("H", os.urandom(2))[0] & 0xfff for i in range(60)])) Out[147]: 60
Zwłaszcza, że wówczas ilość bitów, na której można zapisać czas, zmniejszyłaby się do 20, więc jej "rozdzielczość" byłaby już gorsza, niż minuta.
Rozwiązaniem nie jest również generowanie identyfikatora poprzez losowanie 32 bitowej wartości, bo kolizji możemy się spodziewać już w próbce 65536 identyfikatorów:
In [153]: len(set([struct.unpack("L", os.urandom(4)) for i in range(2**16)])) Out[153]: 65535 In [154]: len(set([struct.unpack("L", os.urandom(4)) for i in range(2**16)])) Out[154]: 65536
Dla przypomnienia, jeden dzień to 86400 sekund.
P.S. Tytuł tego posta jest rezultatem moich pokręconych skojarzeń, których punktem wyjścia była fraza "brain scratcher".
Winszuję - świetna książka. Właśnie zasiadam do IV. tomu.