Paweł Goleń, blog

Najpierw o XOR

Najpierw bardzo szybkie i raczej oczywiste w swojej treści wprowadzenie do tego, co to jest xor i jak działa. Co to jest XOR? To operacja, którą najlepiej w języku potocznym opisać jako albo to, albo to. W przypadku operowania na bitach wygląda to tak:

A   B   A xor B
---------------
1   1   0
1   0   1
0   1   1
0   0   0

Ponadto operacja XOR:

• jest przemienna: A xor B == B xor A
• jest łączna: (A xor B) xor C == A xor (B xor C)
• istnieje element neutralny: A xor 0 == A
• istnieje element odwrotny: A xor A == 0

Załóżmy teraz, że wykorzystujemy operację XOR do szyfrowania (np. one-time pad), to z tych własności wynika między innymi to, że:

• jeśli znamy wiadomość i mamy jej postać zaszyfrowaną, możemy odzyskać klucz,
• możemy modyfikować zaszyfrowaną wiadomość lub jej fragment,
• jeśli ten sam klucz zostanie wykorzystany do zaszyfrowania wielu wiadomości, jesteśmy w stanie go odtworzyć,

W zasadzie wszystkie stwierdzenia powinny być oczywiste. Ale na wszelki wypadek popatrzmy z czego to wynika. W pierwszym przypadku mamy następującą sytuację:

m xor k = c
m xor k = c | xor m
(m xor k) xor m = c xor m
(m xor m) xor k = c xor m
0 xor k = c xor m
k = c xor m

Jest to oczywiste, ale na wszelki wypadek wyjaśniam. Dysponujemy na wejściu m oraz c, naszym celem jest odzyskanie klucza k. Wartość c uzyskuje się poprzez operację m xor k. Jeśli obie strony poddamy operacji xor m, otrzymamy k.

Drugą sytuację można przedstawić w sposób następujący:

m1 xor k = c1
c2 = c1 xor m2
c2 xor k = (c1 xor m2) xor k = ((m1 xor k) xor m2) xor k = k xor k xor m1 xor m2 = 0 xor m1 xor m2 = m1 xor m2

Przekładając to na język bardziej zrozumiały, mamy następującą sytuację: jeśli na zaszyfrowanej przy pomocy XOR wiadomości (tu c1 wykonamy operację XOR z pewną wiadomością m2 i w ten sposób uzyskamy c2, to c2 po rozszyfrowaniu będzie miało wartość m1 xor m2.

Operując na liczbach załóżmy, że:

m1 = 4
k = 9
c = m1 xor k = 4 xor 9 = 13

Co zrobić, by uzyskać wartość c1 taką, by po wykonaniu operacji xor k uzyskać m2 o wartości 6. Zakładamy oczywiście, że nie znamy wartości k i nie chcemy jej wyliczać (choć możemy to zrobić w trywialny sposób, skoro znamy wartości m1 oraz c).

Można to zrobić w sposób następujący:

m2 = 6
m3 = m2 xor m1
c1 = c xor m3
c1 = c xor m3 = m1 xor k xor m3 = m1 xor m1 xor m2 xor k = 0 xor m2 xor k = m2 xor k
c1 xor k = m2 xor k xor k = m2

Czyli wystarczy najpierw wykonać operację XOR między m1 i m2, czyli między aktualnie "zaszyfrowaną" wiadomością i wiadomością, którą chcemy uzyskać po rozszyfrowaniu, a następnie wykonać operację xor między zaszyfrowanym tekstem c.

Na potwierdzenie:

In [41]: (13 ^ (4 ^ 6)) ^ 9
Out[41]: 6

Co z ostatnią sytuacją, czyli możliwością ustalenia klucza który został wykorzystany do zaszyfrowania wielu wiadomości? Nie znamy żadnej z tych wiadomości, ale możemy zakładać, że mają one określoną strukturę, w szczególności, że np. mogą zawierać tylko określony zakres znaków. Jak możemy odzyskać klucz?

Posłużmy się tutaj następującym przykładem. Załóżmy, że dysponujemy następującymi wartościami:

[2, 1, 0, 7, 6, 5, 4, 11, 10]

Wiemy o nich tyle, że powstały one w wyniku operacji i xor k i to, że i należy do przedziału [1;9]. W takim przypadku nie pozostaje nic innego, jak sprawdzić, jakie są możliwe wartości k, które przeprowadzą kolejne elementy powyższego zbioru do tego przedziału. Ponieważ nic nie wiemy na temat k, poszukajmy go w następujący sposób:

c = i xor k
k = c xor i

Czyli znając wartość c przechodzimy przez wszystkie dopuszczalne wartości i (prawidłowe wartości po rozszyfrowaniu) i znajdujemy klucze, które do takich wartości prowadzą:

In [48]: [2^i for i in range(1,10)]
Out[48]: [3, 0, 1, 6, 7, 4, 5, 10, 11]

In [49]: [1^i for i in range(1,10)]
Out[49]: [0, 3, 2, 5, 4, 7, 6, 9, 8]

In [50]: [7^i for i in range(1,10)]
Out[50]: [6, 5, 4, 3, 2, 1, 0, 15, 14]

In [57]: [6^i for i in range(1,10)]
Out[57]: [7, 4, 5, 2, 3, 0, 1, 14, 15]

(...)

Jak widać na tych przykładach ilość dopuszczalnych wartości k jest ograniczona. Ponieważ wszystkie wartości zostały "zaszyfrowane" z użyciem jednego klucza (k), musi on występować we wszystkich przypadkach. Tu na przykładach warunek ten spełniają tylko następujące wartości:

[0, 3, 4, 5]

Po sprawdzeniu pozostałych wartości z "przechwyconego" zbioru (w tym przykładzie sprawdziłem tylko 2, 1, 7 i 6), ten zbiór zostałby zawężony prawdopodobnie do tylko jednego elementu.

I co z tego wynika

A teraz trochę odnośnie tego co z powyższych własności XOR może wynikać. Trochę jako ciekawostka, a trochę jako przykład odnośnie tego, dlaczego nie należy używać samego szyfrowania.

Można przypuszczać, że jeśli atakujący zobaczy zaszyfrowaną wiadomość c, nie będzie w stanie wygenerować wiadomości c1, która po rozszyfrowaniu będzie różniła się od D(c) w oczekiwany przez niego sposób. To rzeczywiści jest prawdą w niektórych przypadkach. Tu pokażę dla przykładu dwa przypadki, w których prawdą to nie jest. Konkretnie pokaże takie sytuacje, w których atakujący, który zna m i c = E(k, m) będzie w stanie wygenerować c1 takie, że m1 = D(k, m1) będzie różniło się od m w oczekiwany przez atakującego sposób.

Jeśli ktoś będzie twierdził, że takie przypadki nie występują w naturze, spieszę donieść, że jak najbardziej - występują. Coraz częściej szyfrowanie jest wykorzystywane w celu zapewnienia integralności danych i w wielu przypadkach takie rozwiązanie kompletnie nie sprawdza się w takim zastosowaniu.

Modyfikacja pierwszego bloku w trybie CBC

Jednym z trybów pracy szyfrów blokowych jest tryb Cipher-block chaining (CBC).

W tym przypadku pierwszy blok jest szyfrowany z użyciem wektora IV. Każdy kolejny blok w roli wektora IV wykorzystuje zaszyfrowaną postać poprzedniego bloku. Wektor IV jest wysyłany razem z wiadomością.

Samo szyfrowanie wygląda w ten sposób, że każdy blok m wiadomości jest najpierw poddawany operacji XOR z postacią zaszyfrowaną poprzedniego bloku (lub z IV w przypadku pierwszego bloku), a następnie szyfrowany. W przypadku rozszyfrowania jest odwrotnie. Najpierw blok jest odszyfrowywany, a następnie wykonywana jest operacja XOR. W wyniku otrzymywana jest postać jawna zaszyfrowanego tekstu.

Problem z tym podejściem jest taki, że atakujący może zmodyfikować w trywialny sposób pierwszy blok tekstu jawnego nie wpływając przy tym w żaden sposób na rezultat deszyfrowania kolejnych bloków. Jak może to zrobić? Wystarczy, że zmodyfikuje wektor IV w taki sam sposób, jak pokazywałem to dla zwykłego OTP.

Przykład (z wykorzystaniem PyCrypto):

In [63]: key = os.urandom(16)

In [64]: iv = os.urandom(16)

In [67]: aes = AES.new(key, AES.MODE_CBC, iv)

In [68]: m = "0000000000000000"

In [69]: c = aes.encrypt(m)

In [70]: iv.encode('hex')
Out[70]: '91457e3364034d7eb2648ee720cccd5b'

In [71]: c.encode('hex')
Out[71]: 'f0cf50bf2f748996e6f047313643c660'

W ramach ćwiczenia zmieńmy w takim razie IV w taki sposób, by wiadomość c po rozszyfrowaniu zaczynała się od słów TEST, a pozostała część niech pozostanie bez zmian.

XOR między początkiem wiadomości m i tą wartością, którą chcemy uzyskać, jest następujący:

In [78]: [ord(i)^ord(j) for i,j in zip("0000","TEST")]
Out[78]: [100, 117, 99, 100]

Wygenerujmy nowy IV:

In [92]: x = [100, 117, 99, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
In [93]: iv = '91457e3364034d7eb2648ee720cccd5b'.decode('hex')

In [94]: "".join([chr(i^ord(j)) for i,j in zip(x,iv)]).encode('hex')
Out[94]: 'f5301d5764034d7eb2648ee720cccd5b'

I teraz sprawdźmy, czy poszło dobrze:

In [118]: aes = AES.new(key, AES.MODE_CBC, 'f5301d5764034d7eb2648ee720cccd5b'.decode('hex'))

In [119]: aes.decrypt('f0cf50bf2f748996e6f047313643c660'.decode('hex'))
Out[119]: 'TEST000000000000'

Jak widać po rozszyfrowaniu otrzymany został tekst zmodyfikowany, zgodnie z moimi oczekiwaniami. To po raz kolejny dowód na to, że szyfrowanie nie zapewnia integralności danych, chyba, że użyta została Authenticated Encryption.

Tryb CTR

Jeśli ktoś chciałby zamiast trybu CBC wykorzystać tryb CTR, musi przygotować się na jeszcze większą niespodziankę. W tym przypadku musi być świadomy tego, że:

• atakujący może dowolnie zmodyfikować treść zaszyfrowanej wiadomości,
• może odszyfrować wiadomości, jeśli nonce jest wykorzystany wielokrotnie,

Dlaczego jest to możliwe? Wynika to z trybu pracy tego szyfru. Działa on w oparciu o klucz, nonce oraz licznik. Szyfrowanie wygląda w ten sposób, że dla kolejnych bloków tekstu jawnego liczony jest keystream jako E(klucz, nonce || licznik), a następnie jest wykonywana operacja XOR z tekstem jawnym. Rozszyfrowanie wygląda w dokładnie ten sam sposób.

Mamy więc tak naprawdę sytuację, w której szyfrowanie wygląda tak:

ks xor m

Gdzie ks jest generowany przez szyfr blokowy, a m jest wiadomością. Czyli praktycznie dokładnie to samo, co w przypadku omawianego na samym początku przypadku z XOR.

By taki tryb był bezpieczny nonce musi być unikalny dla każdej wiadomości. Wtedy generowany ks jest również unikalny dla wiadomości i w związku z tym odszyfrowanie wiadomości po zebraniu ich większej ilości nie będzie możliwe. Możliwa będzie natomiast wciąż modyfikacja tekstu tajnego w taki sposób, by po rozszyfrowaniu różnił się od oryginalnego tekstu w sposób oczekiwany przez atakującego. Kolejny przykład/dowód na to, że samo szyfrowanie nie wystarcza do zagwarantowania integralności danych.