Dlaczego funkcje skrótu są bezpieczne?

Wielu ludzi zastanawia się, dlaczego funkcje skrótu są bezpieczne. W jaki sposób możemy utworzyć jednokierunkową funkcję? W tym tłumaczeniu postaram się pokazać, w jaki sposób próbowałem atakować funkcję skrótu SHA-1, a także, co to oznacza w kontekście innych funkcji skrótu.

Pierwszą rzeczą, od której powinniśmy zacząć, jest tworzenie wiadomości. Wyobraź sobie ciąg zer i jedynek, na przykład "10111010000". Mamy tutaj 11 bitów, więc całość nie jest wyrównana względem ośmiobitowych bajtów. Brak tego wyrównania nie ma znaczenia w kontekście funkcji skrótu, gdyż każda z nich jest w stanie świetnie sobie z tym poradzić. Aby utworzyć wiadomość, której skrót będziemy liczyć, należy dołożyć jedynkę na końcu, a następnie wstawić odpowiednią liczbę zer w celu wyrównania (dokładna liczba zer zależy od rozmiaru wiadomości). Ostatecznie, rozmiar naszej wiadomości może wahać się od zera do 2^64-1. Zatem mamy: rozmiar(wiadomości)+rozmiar(jedynki)+rozmiar(zerWyrównujących)+rozmiar(rozmiaruWiadomości). Taka suma powinna być zawsze podzielna przez 512, bez żadnej reszty z dzielenia. Zatem, aby wszystko do siebie pasowało, musimy jedynie dopasować rozmiar zer wyrównujących.

Aby uprościć sytuację, przyjmuję założenie, że istnieje tylko jeden 512-bitowy blok. W rzeczywistości, zwykle będzie ich wiele i zależy to od rozmiaru wiadomości. Ale tutaj, jeden blok wystarcza do tego, aby pokazać wszystko, czego potrzebuję.

Na początku, zaczynamy od sztywno ustawionego wektora inicjalizacyjnego, który w przypadku SHA-1 wynosi:

Code:

67452301 efcdab89 98badcfe 10325476 c3d2e1f0

Jak łatwo zauważyć, taka wartość nie jest wyciągnięta niczym królik z kapelusza, zatem możemy założyć, że nie została wybrana w szczególny sposób i że twórca funkcji skrótu nie chce jej celowo osłabić, poprzez dobranie "magicznych liczb".

Następnie, rozdzielamy nasz 512-bitowy blok na 32-bitowe fragmenty. W swoim kodzie używam prostej tablicy zmiennych typu uint32. Używam następującego formatu do wyświetlania tych wartości:

Code:

w[ 0] w[ 1] w[ 2] w[ 3]
w[ 4] w[ 5] w[ 6] w[ 7]
w[ 8] w[ 9] w[10] w[11]
w[12] w[13] w[14] w[15]

To oznacza, że przy pustej wiadomości, uzyskujemy następujący blok:

Code:

80000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

Jak łatwo zauważyć, mamy tutaj pustą wiadomość, pojedynczy bit o wartości "1", zera wyrównujące, a także rozmiar wiadomości (w bitach) na ostatnich 64 bitach (równy zero). Ostatecznie mamy zatem 0x80000000, a następnie ciąg 0x00000000. SHA-1 tego wszystkiego wynosi:

Code:

da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

Jeśli mamy do czynienia z łańcuchem bitów wspomnianym wcześniej, czyli "10111010000", uzyskujemy następujący wynik:

Code:

ba100000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 0000000b

SHA-1 tego bloku wynosi:

Code:

be5abcb4 16303cb7 3459305d e9ef9055 16be628d

Rzadko spotyka się skrót jakiegoś ciągu bitów, który nie jest wyrównany do ośmiobitowych bajtów, jednak jak możemy zobaczyć na tym przykładzie, taka operacja jest świetnie zdefiniowana w funkcjach skrótu pokroju SHA-1. Oprócz tego, możemy zauważyć, że cała zabawa polega na obliczaniu skrótu jakiegoś pojedynczego 512-bitowego bloku. Jeśli mamy ich więcej, możemy łatwo dojść do wniosku, że ostatni z nich ma najwięcej ograniczeń, gdyż musi zawierać ostatni kawałek wiadomości (jeśli taki istnieje), pojedynczy bit równy jeden, garść zer wyrównujących, a także rozmiar całej wiadomości.

Zatem, cały "rdzeń" funkcji skrótu, może być zawarty w obliczaniu skrótu pojedynczego fragmentu. Możemy myśleć o liczeniu skrótów w następujący sposób:

Code:

wektor inicjalizacyjny: 67452301 efcdab89 98badcfe 10325476 c3d2e1f0
             wiadomość: 80000000 00000000 00000000 00000000
                        00000000 00000000 00000000 00000000
                        00000000 00000000 00000000 00000000
                        00000000 00000000 00000000 00000000
         skrót końcowy: da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

Wtedy cała funkcja skrótu sprowadza się do przetwarzania jakiegoś wektora inicjalizacyjnego do jakiegoś skrótu końcowego. Musimy o tym pamiętać, żeby zrozumieć, w jaki sposób można utworzyć atak rozszerzający wiadomość, poprzez wzięcie wszystkich poprzednich bloków i potraktowanie ich jako część wiadomości, a następnie dołożenie bitu "1", zer wyrównujących, a także nowego rozmiaru wiadomości. Możemy także łatwo zauważyć, że aby rozszerzyć dowolną wiadomość, nie musimy nawet znać jej treści! Ale może wróćmy teraz do naszego pojedynczego bloku.

Pierwszym krokiem jest rozszerzenie wiadomości. Mamy 16 wartości, każda 32-bitowa, ale mamy też 80 rund SHA-1. To oznacza, że musimy rozszerzyć naszą wiadomość. Pierwsze 16 zmiennych zostawiamy bez zmian, ale następne generujemy poprzez prostą pętlę, używając obrotów oraz xorowania:

Code:

w[i]=rol(w[i-16]^w[i-14]^w[i-8]^w[i-3])

To oznacza, że używamy zmiennych od w[0] do w[15] jako podstawy do utworzenia wartości od w[16] do w[79]. Na przykład:

Code:

w[16]=rol(w[ 0]^w[ 2]^w[ 8]^w[13])
w[17]=rol(w[ 1]^w[ 3]^w[ 9]^w[14])
w[18]=rol(w[ 2]^w[ 4]^w[10]^w[15])
...
w[77]=rol(w[61]^w[63]^w[69]^w[74])
w[78]=rol(w[62]^w[64]^w[70]^w[75])
w[79]=rol(w[63]^w[65]^w[71]^w[76])

Zatem, aby uzyskać nasze wartości "w", musimy po prostu zXORować parę innych wartości "w", a następnie obrócić wynik końcowy. Ostateczny wynik zależy od naszej wiadomości, na przykład:

Code:

ba100000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 0000000b
74200001 00000000 00000016 e8400002
00000000 0000002c d0800005 00000016
e840005a a100000b 00000000 000000b0
42000017 0000004e 49400169 84000014
38c00007 000002c0 08000005 a1000133
250005a5 100000e2 a100000b 00000b58
8100017f 000004e0 94001694 40000164
5c800076 00002c58 21000003 b10013f5
63805a4b 00000e21 10000182 2500b5fd
b10017f3 00004cc0 48016914 0000177c
ed0002c0 1002c562 b1000039 10013403
b905a5c9 0000e6a8 35000ebe 100b5ec2
3d017f43 0004e000 00169114 100164fa
8000765c 002c5800 00000321 0013f501
c25a4b74 000e2480 100183ca 84b5fa4b
1817f356 004cc740 1969112f 1017712a

Jak łatwo zauważyć, nawet przy tak prostej wiadomości, uzyskujemy kompletny chaos. Możemy pominąć obrót w lewo, wtedy uzyskamy SHA-0 i poprzez samo spojrzenie na wyniki, możemy łatwo stwierdzić, dlaczego taki obrót został dodany.

Kolejnym krokiem jest przetworzenie początkowej funkcji skrótu, runda po rundzie, kawałek po kawałku. Zatem, zaczynamy od wektora inicjalizacyjnego i dodajemy każdy kawałek do każdej rundy, dopóki nie uzyskamy ostatecznego skrótu. Jeśli wypiszemy sobie to wszystko w konsoli, zobaczymy coś takiego:

Code:

 i       a[i]     b[i]     c[i]     d[i]     e[i]
-------------------------------------------------
 0   67452301 efcdab89 98badcfe 10325476 c3d2e1f0
 1   1fb498b3 67452301 7bf36ae2 98badcfe 10325476
 2   5d43e370 1fb498b3 59d148c0 7bf36ae2 98badcfe
 3   158d2f62 5d43e370 c7ed262c 59d148c0 7bf36ae2
 4   cdecfb5d 158d2f62 1750f8dc c7ed262c 59d148c0
 5   4953565e cdecfb5d 85634bd8 1750f8dc c7ed262c
 6   e44ab766 4953565e 737b3ed7 85634bd8 1750f8dc
 7   c09d7f27 e44ab766 9254d597 737b3ed7 85634bd8
 8   87074800 c09d7f27 b912add9 9254d597 737b3ed7
 9   41376611 87074800 f0275fc9 b912add9 9254d597
10   cbdbff31 41376611 21c1d200 f0275fc9 b912add9
11   40166973 cbdbff31 504dd984 21c1d200 f0275fc9
12   adc0e0ca 40166973 72f6ffcc 504dd984 21c1d200
13   84c05eb2 adc0e0ca d0059a5c 72f6ffcc 504dd984
14   1512c8b9 84c05eb2 ab703832 d0059a5c 72f6ffcc
15   40182905 1512c8b9 a13017ac ab703832 d0059a5c
16   d8fd6547 40182905 4544b22e a13017ac ab703832
17   06bf9173 d8fd6547 50060a41 4544b22e a13017ac
18   28a9520e 06bf9173 f63f5951 50060a41 4544b22e
19   0b3088dd 28a9520e c1afe45c f63f5951 50060a41
20   e758e8da 0b3088dd 8a2a5483 c1afe45c f63f5951
21   90eb9850 e758e8da 42cc2237 8a2a5483 c1afe45c
22   7dbb787d 90eb9850 b9d63a36 42cc2237 8a2a5483
23   1c64d028 7dbb787d 243ae614 b9d63a36 42cc2237
24   1e97b73a 1c64d028 5f6ede1f 243ae614 b9d63a36
25   62d7f53f 1e97b73a 0719340a 5f6ede1f 243ae614
26   34f3d6d8 62d7f53f 87a5edce 0719340a 5f6ede1f
27   4f2ed1c1 34f3d6d8 d8b5fd4f 87a5edce 0719340a
28   c7b11e2d 4f2ed1c1 0d3cf5b6 d8b5fd4f 87a5edce
29   874b786f c7b11e2d 53cbb470 0d3cf5b6 d8b5fd4f
30   ca4556cb 874b786f 71ec478b 53cbb470 0d3cf5b6
31   6a2e466e ca4556cb e1d2de1b 71ec478b 53cbb470
32   62ea3d59 6a2e466e f29155b2 e1d2de1b 71ec478b
33   b77bac25 62ea3d59 9a8b919b f29155b2 e1d2de1b
34   4b1347e2 b77bac25 58ba8f56 9a8b919b f29155b2
35   391ef0c4 4b1347e2 6ddeeb09 58ba8f56 9a8b919b
36   abbab988 391ef0c4 92c4d1f8 6ddeeb09 58ba8f56
37   04f07669 abbab988 0e47bc31 92c4d1f8 6ddeeb09
38   b201788b 04f07669 2aeeae62 0e47bc31 92c4d1f8
39   62273351 b201788b 413c1d9a 2aeeae62 0e47bc31
40   9bdbdd71 62273351 ec805e22 413c1d9a 2aeeae62
41   95aa398b 9bdbdd71 5889ccd4 ec805e22 413c1d9a
42   5e28e858 95aa398b 66f6f75c 5889ccd4 ec805e22
43   95642485 5e28e858 e56a8e62 66f6f75c 5889ccd4
44   fa950aba 95642485 178a3a16 e56a8e62 66f6f75c
45   de1e3a01 fa950aba 65590921 178a3a16 e56a8e62
46   afe695ab de1e3a01 bea542ae 65590921 178a3a16
47   a195ba90 afe695ab 77878e80 bea542ae 65590921
48   e6d39f43 a195ba90 ebf9a56a 77878e80 bea542ae
49   0bca9922 e6d39f43 28656ea4 ebf9a56a 77878e80
50   6ae826ff 0bca9922 f9b4e7d0 28656ea4 ebf9a56a
51   01ff3253 6ae826ff 82f2a648 f9b4e7d0 28656ea4
52   e2581ce0 01ff3253 daba09bf 82f2a648 f9b4e7d0
53   56ce73ab e2581ce0 c07fcc94 daba09bf 82f2a648
54   ae56e542 56ce73ab 38960738 c07fcc94 daba09bf
55   8590c0e8 ae56e542 d5b39cea 38960738 c07fcc94
56   be4a4bea 8590c0e8 ab95b950 d5b39cea 38960738
57   168ce0bb be4a4bea 2164303a ab95b950 d5b39cea
58   e1afab22 168ce0bb af9292fa 2164303a ab95b950
59   982bcbca e1afab22 c5a3382e af9292fa 2164303a
60   9b9d2913 982bcbca b86beac8 c5a3382e af9292fa
61   d37db937 9b9d2913 a60af2f2 b86beac8 c5a3382e
62   85b9d227 d37db937 e6e74a44 a60af2f2 b86beac8
63   cd98fbb7 85b9d227 f4df6e4d e6e74a44 a60af2f2
64   bb0f226f cd98fbb7 e16e7489 f4df6e4d e6e74a44
65   eb59446c bb0f226f f3663eed e16e7489 f4df6e4d
66   d37225cb eb59446c eec3c89b f3663eed e16e7489
67   111341f3 d37225cb 3ad6511b eec3c89b f3663eed
68   e79afbf0 111341f3 f4dc8972 3ad6511b eec3c89b
69   8ba00627 e79afbf0 c444d07c f4dc8972 3ad6511b
70   503c7ae0 8ba00627 39e6befc c444d07c f4dc8972
71   3cd517f9 503c7ae0 e2e80189 39e6befc c444d07c
72   b47ddf0e 3cd517f9 140f1eb8 e2e80189 39e6befc
73   5e3a0780 b47ddf0e 4f3545fe 140f1eb8 e2e80189
74   63db37b2 5e3a0780 ad1f77c3 4f3545fe 140f1eb8
75   15e98d17 63db37b2 178e81e0 ad1f77c3 4f3545fe
76   b0149467 15e98d17 98f6cdec 178e81e0 ad1f77c3
77   14b7106a b0149467 c57a6345 98f6cdec 178e81e0
78   666b8bc6 14b7106a ec052519 c57a6345 98f6cdec
79   6e9d9f84 666b8bc6 852dc41a ec052519 c57a6345
80   72f480ed 6e9d9f84 999ae2f1 852dc41a ec052519
81   da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

Runda 81 to tylko mój wymysł, ponieważ tak naprawdę mamy jedynie 80 rund. Jednakże, w ostatnim kroku, wektor inicjalizacyjny musi zostać dodany do skrótu z ostatniej rundy, a ten krok również chciałbym śledzić w jakiś sposób. W praktyce, gdy mamy więcej niż jeden 512-bitowy blok, wynik tejże "81. rundy" jest przekazywany dalej, jako kolejny wektor inicjalizacyjny, do kolejnego 512-bitowego bloku.

Złamanie wszystkich 80 rund jest trudne. Ale żeby pokazać, dlaczego tak jest, musimy zagłębić się w szczegóły dotyczące obliczania poszczególnych rund. Aby uprościć sprawę, zaczynamy od złamania pierwszych szesnastu rund. Aby to zrobić, możemy zacząć od zrozumienia, jak jest obliczana pierwsza runda.

Code:

 0   67452301 efcdab89 98badcfe 10325476 c3d2e1f0
 1   1fb498b3 67452301 7bf36ae2 98badcfe 10325476

Jak łatwo zauważyć, wiele wartości się powtarza. Głównym powodem jest to, że wartość "a" jest połączeniem wszystkich poprzednich wartości, wartość "c" stanowi po prostu wartość "b", przekręconą o 30 bitów w lewo (albo o 2 bity w prawo, żeby uprościć sytuację, używam wyłącznie obrotów w lewo), zaś wszystkie pozostałe wartości są po prostu przekazywane dalej. Wczytując się dokładniej w wartość "a", możemy zobaczyć coś takiego:

Code:

a[i+1]=rol5(a[i])+f[i]+e[i]+k[i]+w[i]

Jak dotąd, znamy a[i], możemy obrócić taką wartość o pięć bitów, znamy także e[i] oraz w[i]. Nasza wartość "f" jest zwykłą funkcją, przyjmującą krotkę (b,c,d) i zwracającą jakiś wynik. Istnieją trzy funkcje "f": f1, f2, a także f3. W funkcji skrótu SHA-1, nasze funkcje "f" są ściśle związane z wartościami "k". Zmieniamy je co 20 rund:

Code:

  runda   k[i]       f[i]
------------------------------------------------------------------
 0...19   5a827999      f1(b=b[i],c=c[i],d=d[i])=(b&c)|((~b)&d)
20...39   6ed9eba1      f2(b=b[i],c=c[i],d=d[i])=b^c^d
40...59   8f1bbcdc      f3(b=b[i],c=c[i],d=d[i])=(b&c)|(b&d)|(c&d)
60...79   ca62c1d6   f4=f2(b=b[i],c=c[i],d=d[i])=b^c^d

Używanie dokładnie tych wartości "k" jest bardzo ważne. To pierwiastki kwadratowe pewnych małych liczb, możemy sobie policzyć na przykład (5a827998^2,5a827999^2,5a82799a^2) i zobaczyć, co się stanie. Tego typu stałe są konieczne, ponieważ bez nich, jeśli wektor inicjalizacyjny wynosi zero, zaś wiadomość składa się z samych zer, to wynik końcowy również wynosi zero (a taki stan rzeczy znacząco osłabiłby naszą funkcję skrótu). Zatem, skoro teraz już wiemy, jak nasza wartość "a" jest obliczana, możemy spróbować policzyć ją dla pierwszej rundy, być może dostrzeżemy coś ciekawego.

Code:

a[i+1]=rol5(a[i])+f[i]+e[i]+k[i]+w[i]
a[1]=rol5(a[0])+f[0]+e[0]+k[0]+w[0]
a[0]=67452301
f[0]=f1(b[0],c[0],d[0])
f[0]=f1(efcdab89,98badcfe,10325476)
f[0]=98badcfe
e[0]=c3d2e1f0
k[0]=5a827999
a[1]=rol5(67452301)+98badcfe+c3d2e1f0+5a827999+w[0]
rol5(67452301)=e8a4602c
a[1]=9fb498b3+w[0]

Jak łatwo zauważyć, nasza wartość a[1] może być łatwo wyrażona jako stała, dodawana do w[0]. Ale, takie wyniki dostaniemy tylko przy pierwszej rundzie. Możemy spróbować utworzyć podobne równania przy pozostałych rundach i wtedy szybko zauważymy, że wartość a[15] zależy od wszystkich wartości od w[0] do w[15] i nie będziemy mogli tego łatwo uprościć.

Jednak, mimo tego, złamanie pierwszych szesnastu rund jest proste, ponieważ jeśli możemy dowolnie ustawić nasze zmienne (co jest możliwe, jeśli nie mamy do czynienia z ostatnim blokiem i jego ograniczeniami), to możemy również ustawić naszą wiadomość tak, jak chcemy. Zatem, spróbujmy uzyskać same zera, poprzez wstawienie odpowiednich liczb w odpowiednich miejscach:

Code:

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667

Sprawdźmy pierwsze 17 rund:

Code:

 0   67452301 efcdab89 98badcfe 10325476 c3d2e1f0
 1   00000000 67452301 7bf36ae2 98badcfe 10325476
 2   00000000 00000000 59d148c0 7bf36ae2 98badcfe
 3   00000000 00000000 00000000 59d148c0 7bf36ae2
 4   00000000 00000000 00000000 00000000 59d148c0
 5   00000000 00000000 00000000 00000000 00000000
 6   00000000 00000000 00000000 00000000 00000000
 7   00000000 00000000 00000000 00000000 00000000
 8   00000000 00000000 00000000 00000000 00000000
 9   00000000 00000000 00000000 00000000 00000000
10   00000000 00000000 00000000 00000000 00000000
11   00000000 00000000 00000000 00000000 00000000
12   00000000 00000000 00000000 00000000 00000000
13   00000000 00000000 00000000 00000000 00000000
14   00000000 00000000 00000000 00000000 00000000
15   00000000 00000000 00000000 00000000 00000000
16   00000000 00000000 00000000 00000000 00000000
17   3b8b2d2e 00000000 00000000 00000000 00000000

Ładny wynik, nieprawdaż? Z tego powodu, jeśli uprościmy naszą funkcję skrótu do pierwszych 16 rund, możemy wykonać wiele ataków i uzyskać takie skróty, jakich sobie zażyczymy. Może nam się to przydać, jeśli zastanawiamy się "co się stanie, gdy jakaś funkcja skrótu przestanie być odporna na atak preimage". Możemy po prostu zmienić nasz kod źródłowy i zastąpić jakąś bezpieczną funkcję skrótu czymś takim, jak wyżej. Zmniejszona liczba rund znacząco ją osłabi i wtedy możemy atakować tak, jak nam się żywnie podoba i łatwo odpowiadać na pytanie "co by było, gdyby".

Jeśli chodzi o łamanie kolejnych rund, to całość robi się coraz trudniejsza. Aby złamać 17. rundę, należy ustawić wartość w[16] tak, jak chcemy. Ale: nie możemy bezpośrednio zmieniać w[16]. Mamy wartości od w[0] do w[15], zaś cała reszta jest obliczana na podstawie tego, co tam wstawimy. Zatem, należy przyjrzeć się dokładniej, jak jest liczone w[16]:

Code:

w[16]=rol(w[0]^w[2]^w[8]^w[13])

Świetnie, mamy tylko cztery zależności. Zatem, wykonanie ataku "break17" nie jest takie trudne do zmajstrowania. Na przykład, spróbujmy zmienić w[13] na coś innego:

Code:

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667
a57d8667 a57d8668 a57d8667 a57d8667

Wtedy uzyskamy to:

Code:

13   00000000 00000000 00000000 00000000 00000000
14   00000001 00000000 00000000 00000000 00000000
15   00000020 00000001 00000000 00000000 00000000
16   00000400 00000020 40000000 00000000 00000000
17   3b8bad24 00000400 00000008 40000000 00000000

Teraz możemy zobaczyć, jak rzeczy są ze sobą połączone. Na szczęście, możemy łatwo to naprawić, poprzez odpowiednią zmianę przy w[14] oraz w[15]:

Code:

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667
a57d8667 a57d8668 a57d8647 a57d8667

Jest lepiej, ale pojawia się inny problem:

Code:

13   00000000 00000000 00000000 00000000 00000000
14   00000001 00000000 00000000 00000000 00000000
15   00000000 00000001 00000000 00000000 00000000
16   00000000 00000000 40000000 00000000 00000000
17   3b8b2d24 00000000 00000000 40000000 00000000

Jak łatwo zauważyć, nasz skrót po 16 rundach jest prawie dobry. Prawie, ponieważ nasz atak na w[13] zmienił także c[16] na 0x40000000, zamiast 0x00000000. Możemy to naprawić, jeśli zmienimy w[12]:

Code:

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 a57d8667
a57d8668 a57d8647 a57d8667 a57d8667

Jest lepiej, ale to jeszcze nie to:

Code:

12   00000000 00000000 00000000 00000000 00000000
13   00000001 00000000 00000000 00000000 00000000
14   00000000 00000001 00000000 00000000 00000000
15   00000000 00000000 40000000 00000000 00000000
16   00000000 00000000 00000000 40000000 00000000
17   7b8b2d6e 00000000 00000000 00000000 40000000

Zatem, obecnie przenieśliśmy 0x40000000 do d[16]. Może dałoby się przenieść to dalej, poza e[16], jeśli zaatakujemy wcześniejszą wartość? Spróbujmy zmienić w[10]:

Code:

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8668 a57d8647
a57d8667 a57d8667 657d8667 657d8667

Mamy to!

Code:

10   00000000 00000000 00000000 00000000 00000000
11   00000001 00000000 00000000 00000000 00000000
12   00000000 00000001 00000000 00000000 00000000
13   00000000 00000000 40000000 00000000 00000000
14   00000000 00000000 00000000 40000000 00000000
15   00000000 00000000 00000000 00000000 40000000
16   00000000 00000000 00000000 00000000 00000000
17   3b8b2d2e 00000000 00000000 00000000 00000000

Jak łatwo zauważyć, mamy kolizję w szesnastej rundzie. Skrót wynoszący zero osiągnięty! Istotną sprawą jest to, że nasza siedemnasta runda pozostaje nienaruszona, niezależnie od tego, jaką wartość umieścimy na przekątnej.

Code:

10   00000000 00000000 00000000 00000000 00000000
11   ........ 00000000 00000000 00000000 00000000
12   00000000 ........ 00000000 00000000 00000000
13   00000000 00000000 ........ 00000000 00000000
14   00000000 00000000 00000000 ........ 00000000
15   00000000 00000000 00000000 00000000 ........
16   00000000 00000000 00000000 00000000 00000000
17   3b8b2d2e 00000000 00000000 00000000 00000000

To oznacza, że uzyskaliśmy kolizje w rundzie 17., zaś atak preimage w rundzie 16. Takie właściwości mogą nam się później przydać, ale na razie spróbujmy wykonać "break17" poprzez edycję e[16]. Zatem, nasz atak preimage będzie wyglądał tak:

Code:

11   00000000 00000000 00000000 00000000 00000000
12   ........ 00000000 00000000 00000000 00000000
13   00000000 ........ 00000000 00000000 00000000
14   00000000 00000000 ........ 00000000 00000000
15   00000000 00000000 00000000 ........ 00000000
16   00000000 00000000 00000000 00000000 ........
17   00000000 00000000 00000000 00000000 00000000

Na początku, zaczynamy od w[16], ponieważ nie możemy bezpośrednio tego ruszać, mamy tylko wartości od w[0] do w[15] w naszej wiadomości:

Code:

w[16]=rol(w[0]^w[2]^w[8]^w[13])
w[0]=604b674d
w[2]=90cf3e87
w[8]=a57d8667
w[13]=a57d8667
w[16]=e108b395

Możemy zauważyć, że:

Code:

a[17]=rol5(a[16])+f[16]+e[16]+k[16]+w[16]
a[17]=00000000
a[16]=00000000
f[16]=00000000
k[16]=5a827999
w[16]=e108b395
00000000=00000000+00000000+e[16]+5a827999+e108b395
e[16]=c474d2d2

Prawie skończyliśmy, ponieważ teraz możemy użyć obrotu "rol2" i wtedy uzyskamy wszystkie wartości:

Code:

a[12]=rol2(c474d2d2)=11d34b4b
b[13]=rol2(c474d2d2)=11d34b4b
c[14]=c474d2d2
d[15]=c474d2d2
e[16]=c474d2d2

Zatem, nasze rundy powinny wyglądać następująco:

Code:

11   00000000 00000000 00000000 00000000 00000000
12   11d34b4b 00000000 00000000 00000000 00000000
13   00000000 11d34b4b 00000000 00000000 00000000
14   00000000 00000000 c474d2d2 00000000 00000000
15   00000000 00000000 00000000 c474d2d2 00000000
16   00000000 00000000 00000000 00000000 c474d2d2
17   00000000 00000000 00000000 00000000 00000000

Natępnie, możemy wyciągnąć z tego nasze wartości "w":

Code:

604b674d 994f32f3 90cf3e87 cfb8d2c5
4bac3da7 a57d8667 a57d8667 a57d8667
a57d8667 a57d8667 a57d8667 b750d1b2
6b141d05 a57d8667 a57d8667 e108b395

Sprawdźmy pierwsze 18 rund:

Code:

 0   67452301 efcdab89 98badcfe 10325476 c3d2e1f0
 1   00000000 67452301 7bf36ae2 98badcfe 10325476
 2   00000000 00000000 59d148c0 7bf36ae2 98badcfe
 3   00000000 00000000 00000000 59d148c0 7bf36ae2
 4   00000000 00000000 00000000 00000000 59d148c0
 5   00000000 00000000 00000000 00000000 00000000
 6   00000000 00000000 00000000 00000000 00000000
 7   00000000 00000000 00000000 00000000 00000000
 8   00000000 00000000 00000000 00000000 00000000
 9   00000000 00000000 00000000 00000000 00000000
10   00000000 00000000 00000000 00000000 00000000
11   00000000 00000000 00000000 00000000 00000000
12   11d34b4b 00000000 00000000 00000000 00000000
13   00000000 11d34b4b 00000000 00000000 00000000
14   00000000 00000000 c474d2d2 00000000 00000000
15   00000000 00000000 00000000 c474d2d2 00000000
16   00000000 00000000 00000000 00000000 c474d2d2
17   00000000 00000000 00000000 00000000 00000000
18   08723a05 00000000 00000000 00000000 00000000

Jesteśmy w domu. Ale idąc dalej, zrobienie "break18", "break19", i tak dalej, jest coraz trudniejsze, ponieważ mamy coraz więcej zależności. Co więcej, jeśli chcemy sprawdzić niektóre właściwości, możemy spróbować zmniejszyć liczbę bitów. Jeśli popatrzymy na SHA-256 oraz SHA-512, to zauważymy, że te funkcje skrótu są do siebie podobne. Na tej samej zasadzie, budowa SHA-256 przypomina miejscami SHA-1, jeśli chodzi o ataki opisane wyżej.

Jeśli chodzi o upraszczanie funkcji skrótu, możemy na przykład uprościć SHA-1 ze 160 do 80 bitów, jeśli po prostu przejdziemy na 16-bitowe zmienne wewnętrzne. Jeśli użyjemy 8-bitowych zmiennych, staje się to dość wygodne, ponieważ wtedy mamy 40-bitową funkcję skrótu i możemy ją dalej poznawać. Wtedy, możemy sprawdzić wszystkie możliwe wartości i zauważyć, że przy niektórych rundach, nie będziemy mieli żadnych udanych ataków preimage. Jeśli chodzi o podwójne obliczanie funkcji skrótu, możemy łatwo dowiedzieć się, jak to działa, oraz że żadna 40-bitowa wartość, wymieszana ponownie, nie daje nam tego, czego chcemy, jeśli chodzi o niektóre rundy.

Topic: Dlaczego funkcje skrótu są bezpieczne? (Read 53 times)