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).
Powrót identyfikatora
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:
- prowadzimy licznik od 0 do (2**64)-1,
- szyfrujemy (3DES) aktualne wskazanie licznika, w ten sposób otrzymujemy identyfikator,
- zwiększamy licznik o 1,
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.
Z drugiej strony jeśli atakujący ma taki dostęp do systemu, że jest w stanie uzyskać ten klucz, to prawdopodobnie mamy większy problem, niż przewidywalność identyfikatorów
I spara taka, że "Założenie jest takie, że przyznawane identyfikatory nie powinny być sekwencyjne, tak by enumeracja obiektów z użyciem bezpośredniego użycia identyfikatora była nieefektywna". Może nie jest jawna, nie jest widoczna z zewnątrz i w ogóle, ale jak dla mnie, laika, sekwencyjność istnieje.
Inna sprawa jest taka, ze konserwatywność to 'zawsze być przygotowanym na kolizje, bo ona w koncu nastapi', ale widocznie inaczej nas uczono
Ta odwaracalosc procesu nie daje mi spokoju.
Operator może mieć taki poziom dostępu do systemu, że możliwość "odwrócenia" procesu nie będzie istotnym problemem.