Powrót identyfikatora

Po przerwie powrót do tematu poruszanego w poprzednich wpisach. Jednym z warunków zadania była wymagana unikalność identyfikatora na przestrzeni 10 lat. Dodatkowo wiedzieliśmy, że w ciągu sekundy będzie (w przybliżeniu) generowany jeden identyfikator. Oznacza to, że w ciągu 10 lat będzie ponad 315360000. Dla uproszczenia załóżmy, że będzie ich około 316224000 (to wtedy, gdyby każdy rok liczył 366 dni).

Wartość 316224000 jesteśmy w stanie zapisać (z dużym zapasem) na 29 bitach. I tu powinna zapalić się lampka ostrzegawcza – skoro cały identyfikator to 32 bity, to warunek “trudnej enumeracji” chyba nie będzie spełniony. I rzeczywiście – okazuje się, że z po tych 10 latach z wybierając dowolna 32 bitową wartość, trafiamy z prawdopodobieństwem ponad 0.07 w prawidłowy identyfikator. W uproszczeniu można przyjąć, że znalezienie jednego prawidłowego identyfikatora wymaga 14 prób. Mało.

Jaką wartość bylibyśmy w stanie zaakceptować? Załóżmy, że zgadnięcie prawidłowego identyfikatora powinno kosztować atakującego 2\*\*16 prób. Oznacza to, że identyfikator powinien mieć jakieś 54 44 bity długości. Na razie wydłużmy go jednak jeszcze o 10 20 bitów. W jaki sposób generować losowe identyfikatory o takiej długości? Przypominam, że muszą być one unikalne?

Teoretycznie moglibyśmy je po prostu losować. Z dużym prawdopodobieństwem w ciągu 10 lat nie zdarzyłaby się kolizja. Powiedzmy jednak, że jesteśmy strasznie konserwatywni i nawet to niewielkie prawdopodobieństwo kolizji jest dla nas nieakceptowalne. Jak poradzić sobie z tym problemem? Tu warto zapoznać się z pojęciem PRP i PRF. I właśnie PRF może być wykorzystany do generowania naszych identyfikatorów.

Jako PRF wykorzystać można szyfr blokowy o rozmiarze bloku 64 bitów (DES, 3DES). Przeprowadza on w sposób jednoznaczny 64 bity w 64 bity. Dodatkowo wynik działania jest praktycznie nieodróżnialny od losowych danych. Przy zastosowaniu base64 to długość takiego identyfikatora to zaledwie 11 znaków (pomijając padding), a więc coś, co chyba można zaakceptować w dzisiejszych czasach.

Czyli jak można generować identyfikatory spełniające nasze założenia? Prosto:

No dobrze. Ale co, jeśli ktoś uprze się, by identyfikator miał jednak te 54 44 bity? O tym w kolejnym odcinku :)

EDIT: No tak, jednak nie powinienem dzisiaj siadać do pisania. Po dodaniu 16 i 28 wyszło mi 54 zamiast 44. Super :( Pominę już, że w rzeczywistości powinno to być pomiędzy 44 i 45 bitów. 44 bity daje ponad 55000 prób, ale jednak trochę mniej niż wspominane 65535. Ale ta parzysta liczba bitów jest mi potrzebna do dalszych przykładów.

Oryginał tego wpisu dostępny jest pod adresem Powrót identyfikatora

Autor: Paweł Goleń