Paweł Goleń, blog

Coś z niezupełnie innej beczki...

Może najpierw odeślę do opisu algorytmu RC4, oraz do artykułu o atakach na szyfry strumieniowe. Dlaczego? Dlatego, że RC4 intensywnie wykorzystuje XOR.

Big fat warning!

Tutaj przy okazji chciałem powiedzieć, że fakt, iż często odsyłam do Wikipedii nie oznacza, iż jest to dobre (dogłębne) źródło wiedzy. Materiały tam zawarte często są niekompletne, czasami nawet błędne (do tych nie odsyłam). Traktuję to raczej jak wskazanie kierunku poszukiwań. To tak w temacie tego postu Michała, z którym się zgadzam.

...wracając do właściwego tematu...

Wracając do tematu. Microsoft ma na swoim koncie wiele wpadek z wykorzystaniem algorytmu RC4. Nie tylko Microsoft, ale zwykle o nim jest głośno. Nie zmienia to faktu, że takie same błędy są wciąż popełniane "w naturze". Na przykład hasła zabezpieczane są za pomocą algorytmu XOR. Podejście takie jest stosowane przez część programów, które przechowują hasła w postaci odwracalnej. W zasadzie jest to tylko "ukrywanie" hasła, bo o zabezpieczeniu ciężko tutaj mówić. Zresztą zaszycie klucza w programie i ewentualne jego wykorzystywanie w mocniejszych algorytmach, niewiele zmienia sytuację, ale to temat już na inną opowieść.

Dlaczego tak łatwo zrobić sobie krzywdę XOR?

Dlaczego tak łatwo sobie strzelić z łuku w kolano korzystając z XOR? Cóż, jedną z własności XOR jest to, że:

(M1 xor K) xor (M2 xor K) = M1 xor M2

Czyli jeśli mamy dwa komunikaty zaszyfrowane XOR przy pomocy tego samego klucza, to po wykonaniu operacji XOR na nich, zdejmowany jest klucz K i rezultatem tej operacji jest wynik M1 xor M2. Co to daje? W końcu dalej nie mamy tekstu jawnego, jak mamy ustalić jaka jest wiadomość M1 a jaka M2? Jeśli długość M1 jest równa M2, to jaka jest różnica między M1 xor K a M1 xor M2? Taka, że K jest (powinno) być losowe, a M2 już takie nie jest. Wówczas wkracza statystyka. Jeśli M1 i M2 są jakimiś tekstami, to na podstawie częstotliwości występowania liter można stosunkowo łatwo określić jak wygląda M1 i M2.

Zrób to sam - hasła "zabezpieczone" XOR

Co w przypadku haseł, zwłaszcza tych generowanych losowo? Przecież w takim przypadku haseł generowanych na przykład przy pomocy APG ciężko oczekiwać o jakiejś charakterystyki występowania poszczególnych liter. I co z tego? Znana jest natomiast polityka haseł, wiadomo, że hasło powinno zawierać określony zbiór znaków. W takim przypadku wystarczy wykonywać operację XOR jednego wybranego hasła z pozostałymi zabezpieczonymi w ten sposób hasłami. Rezultatem tej operacji będzie H1 xor Hn. Następnie należy sprawdzać jakie znaki mogą występować w H1 i Hn, które dają określoną wartość operacji XOR (oczywiście każdy znak hasła należy rozpatrywać osobno). Za pierwszym razem dostaniemy grupę znaków, która mogła wystąpić w wyróżnionym haśle H1 na danej pozycji. Później z każdym kolejnym sprawdzanym "zaszyfrowanym" hasłem, zbiór dopuszczalnych znaków będzie się zmniejszał, aż do czasu, gdy na każdej pozycji będzie tylko jeden dopuszczalny znak, czyli w zasadzie do czasu poznania formy jawnej wyróżnionego hasła H1. Wówczas rezultat ten wystarczy poddać operacji XOR z H1 by otrzymać klucz, a następnie wykorzystać poznany klucz do poznania pozostałych haseł.

Eksperyment...

Przeprowadziłem eksperyment. Wygenerowałem 512 haseł APG, podzieliłem to na paczki 8, 16, 32, 64, 128, 256 i 512 haseł, które "zaszyfrowałem" przy pomocy XOR, klucza nawet nie znałem. Następnie na poszczególne próbki "napuszczałem" skrypt, który wykonywał opisany wcześniej algorytm. Wystarczająca była próbka 128 haseł. Czy to dużo? I tak, i nie. Oznacza to tylko tyle, że w tym konkretnym przypadku potrzebne było 128 próbek, co wcale nie znaczy, że w innym przypadku, tych próbek nie wystarczy 16, lub 8. W zasadzie powinienem test ten powtórzyć większą ilość razy i na podstawie zebranych danych wyliczyć choćby wartość oczekiwaną. Tylko po co? Jasne jest, że przy wystarczającej ilości próbek "zabezpieczone" w ten sposób hasła, da się odzyskać. Tak samo, jak przy wystarczającej ilości IVS da się złamać WEP.