Paweł Goleń, blog

Odrobina o koncepcji...

Koncepcja, która chodziła mi po głowie zakładała przekształcenie identyfikatora w ciąg danych, który:

• zawiera dane pozwalające zweryfikować "integralność" otrzymanych przez aplikację parametrów,
• nie jest zbyt długi (co jest oczywiście parametrem dość rozmytym),
• ustalenie rzeczywistej wartości identyfikatora nie powinno być proste,

W rezultacie radosnej burzy mózgu powiązanej z równie radosnym kodowaniem, wymyśliłem coś takiego:

• dla każdej sesji generowany jest losowy klucz (wykorzystywany w operacji HMAC),
• na wartości identyfikatora wykonywana jest operacja HMAC,
• rezultat funkcji HMAC jest przekształcany w krótszy ciąg znaków (taki "skrót skrótu"),
• na podstawie "skrótu skrótu" generowany jest klucz szyfrowania,
• wartość identyfikatora jest "szyfrowana" (z wykorzystaniem XOR),
• na stronie wypisywana jest wartość złożona ze "skrótu skrótu" HMAC oraz "zaszyfrowanego" identyfikatora,

Oczywiście po otrzymaniu takiego identyfikatora wykonywana jest operacja odwrotna:

• na podstawie pierwszej części danych generowany jest klucz szyfrowania,
• druga część danych (zawierająca identyfikator) jest poddawana operacji XOR (czyli przekształcana do formy jawnej),
• odszyfrowany identyfikator poddawany jest operacji HMAC,
• wyliczany jest "skrót skrótu" i porównywany z oryginalnym, zawartym w pierwszej części identyfikatora,

Kilka dodatkowych informacji:

Przy generowaniu skrótu skrótu losowana jest wartość z zakresu 0 do 0xFF i w zależności od niej na podstawie rezultatu wcześniejszej operacji HMAC tworzona jest skrócona wartość. Tak więc dla jednego identyfikatora możliwych jest 256 wartości, dzięki czemu ten sam identyfikator w tej samej sesji może wyglądać na różny sposób. Wykorzystanie HMAC i wygenerowanie oddzielnego klucza dla każdej sesji powoduje, że identyfikator prawidłowy w jednej sesji, nie będzie prawdopodobnie już prawidłowy w drugiej. Prawdopodobnie, bo jednak skracam dość istotnie rezultat HMAC, więc istnieje spore prawdopodobieństwo "kolizji", ale o tym później.

Wykorzystanie XOR w tym wypadku nie jest strasznie złe. Wykorzystywany klucz jest dość unikalny i dla każdej wartości identyfikatora ma 256 możliwych wartości. Jest on również dość długi, po prostu jest wyliczany jako sha512 ze skrótu skrótu. Dodatkowo długość takiego skrótu jest istotnie większa, niż długość "szyfrowanych danych". A poza tym, to skuteczne zaszyfrowanie wartości nie jest moim celem, a tylko jej "zaciemnienie". Oczywistą słabością jest tu fakt, że całe "szyfrowanie" traci swój efekt, gdy atakujący wie, w jaki sposób generowany jest klucz szyfrowania, choć można temu zaradzić zastępując prosty sha512 choćby (ponownie) HMAC, wówczas do wygenerowania klucza potrzebny będzie nie tylko "skrót skrótu", ale i klucz wykorzystany przy HMAC, który dodatkowo może być różny od tego już wykorzystywanego.

...i co z tego wyszło

Na razie sprawdziłem empirycznie to, co można w zasadzie wyliczyć - czyli ile różnych wartości identyfikatora generuje tą samą wartość "uwierzytelniającą". W trakcie tych testów wartość ta składała się z 6 znaków, 2 znaki na losową wartość od 0x00 do 0xFF i cztery znaki wybrane z rezultatu funkcji HMAC. Prawdopodobieństwo wystąpienia konkretnego układu tych czterech znaków to 1/16^4 (bo każdy z tych czterech znaków ma 16 dopuszczalnych wartości). Na tej podstawie i na podstawie mocy zbioru identyfikatorów (tych "surowych") można estymować ile różnych identyfikatorów będzie miało tą samą wartość. Dla przykładu jeśli identyfikatory są ciągle i mają zakres od 1 do 1000000 to można się spodziewać, że istnieje w okolicach 16 różnych elementów, które mają taką samą wartość. Czyli dla konkretnej wartości pierwszej części identyfikatora istnieje około 16 różnych, prawidłowych wartości drugiej części "zaszyfrowanego" identyfikatora, ale, co ważne, wartości te nie są dowolne. Przykład prostej symulacji dla 1000000 elementów:

Auth: dc12c0 
Wartości: 
29629 
91023 
119923 
129775 
148199 
161504 
512037 
617944 
742919 
785080 
790468 
795534 
962448 
962636
Prawdopodobieństwo: 0.001400% 
Ilość "kolizji": 14

Bardziej jednak istotną informacją będzie ile prób musi wykonać atakujący, by przekazać do systemu określoną wartość. Teoretycznie będzie to 16^6, jednak mając na uwadze rolę dwóch pierwszych znaków, to efektywna maksymalna ilość prób będzie wynosiła jedynie 16^4, co daje 65536. Oczywiście sytuacja ulegnie poprawie, jeśli zamiast 4 znaków z hasha, będzie brana ich większa ilość. Zwiększenie liczby "istotnych" znaków do 6 daje już wynik (pesymistyczny, lub optymistyczny - zależny od punktu widzenia) na poziomie 16 777 216 prób. Jeśli uwzględni się fakt, że całość będzie odbywała się przez sieć, zadanie nie jest trywialne.

Zastanawiam się, czy dodatkowej złożoności nie wprowadziłoby generowanie klucza szyfrowania w inny sposób. Obecnie, przypominam, jest to sha512 z pierwszej części "zakodowanego" identyfikatora, więc klucz atakujący może wyliczyć dość trywialnie (o czym wspominałem). Na podstawie klucza generuje on następnie odpowiednią "wartość zaszyfrowaną" dla pożądanej przez niego wartości identyfikatora. Jeśli klucz będzie generowany w bardziej złożony sposób, atakujący będzie miał prawdopodobnie większą przestrzeń do przeszukania, ponieważ klucza nie będzie mógł wyliczyć. Będzie tak naprawdę musiał wykonać dwa zadania:

• znaleźć wartość "skrót skrótu" prawidłową dla określonej wartości (rzeczywistego) identyfikatora,
• znaleźć wartość "zaszyfrowaną", która po rozszyfrowaniu nieznanym kluczem, daje odpowiednią wartość,

Jeśli identyfikator potraktujemy jako string i przed szyfrowaniem zamienimy go na ciąg hex, to ilość możliwych wartości części zaszyfrowanej można przedstawić jako 16^i gdzie i jest 2*długość_identyfikatora, a przynajmniej tak mi się wydaje.

Zastanawiam się również, czy atakujący będzie mógł w jakiś sposób stworzyć "lokalny test", który pozwoli mu weryfikować poprawność "fałszywych" identyfikatorów, bez kontaktu z serwerem. Wydaje mi się to mało prawdopodobne, bo sprowadzałoby się to do zadania "obserwując wyjście HMAC odgadnij użyty klucz".

Na dziś wystarczy, prawdopodobnie jeszcze poeksperymentuje z tym pomysłem, na koniec może pokażę PoC.