Anarchriz - CRC32 i jak go odwrócić

Wprowadzenie

Ten esej składa się z przewodnika po CRC i opisu sposobu na jego odwrócenie. Wielu reverserów nie zna dokładnych zasad, na jakich funkcjonuje CRC a prawie nikt nie wie jak go odwrócić, choć wiedza ta może być bardzo użyteczna. Najpierw przewodnik nauczy cię jak ogólnie obliczyć CRC, możesz użyć go do ochrony danych. Potem, część traktująca o odwracaniu nauczy cię (głównie) jak odwracać CRC-32 - możesz tego użyć do złamania zabezpieczeń CRC niektórych programów (np. antywirusów). Wydaje się, że istnieją programy, które mogą "poprawić" CRC za ciebie, ale wątpię, czy tłumaczą co robią.
Chciałbym cię ostrzec, że w eseju tym znajduje się dużo matematyki. Nie zrobi to nikomu krzywdy, a przeciętny koder/Reverser zrozumie to bardzo dobrze. Dlaczego? Cóż. Jeżeli nie wiesz dlaczego używa się matematyki w CRC, proponuję kliknąć przycisk z X w prawym górnym rogu tego ekranu. Zakładam więc, że czytelnik zna arytmetykę binarną.

Część 1: Przewodnik po CRC, co to jest i jak to obliczyć

Cyclic Redundancy Code lub CRC

Wszyscy znamy CRC. Nawet jeżeli sobie nie przypominasz, przypomnisz sobie gdy pomyślisz o tych wkurzających komunikatach, które wyświetlają RAR, ZIP i inne kompresory kiedy plik jest uszkodzony z powodu wadliwego połączenia lub tych !@#$% dyskietek. CRC to wartość obliczona z kawałka danych, na przykład dla każdego pliku w czasie kompresji. Kiedy archiwizer rozpakowuje ów plik, odczytuje CRC i sprawdza go z nowo obliczonym CRC rozpakowanego pliku. Kiedy oba CRC pokrywają się, istnieje duża szansa, że pliki są identyczne. Przy CRC-32 szansa na to, że nie zostanie wykryta zmiana w danych wynosi 1/2 ^ 32.

Wielu ludzi sądzi, że CRC to po prostu skrót od Cyclic Redundancy Check (cykliczne sprawdzenie nadmiaru). Jeżeli CRC to rzeczywiście skrót tego terminu, wielu ludzi używa go niewłaściwie. Jeżeli by tak było, nie można by powiedzieć "CRC tego programu to 12345678". Ludzie mówią też zawsze, że jakiś program ma test CRC, nie Cyclic Redundancy Check check (sprawdzenie cyklicznego sprawdzenia nadmiaru). Wniosek: CRC znaczy Cyclic Redundancy Code (cykliczny kod nadmiaru a NIE Cyclic  Redundancy Check (cykliczne sprawdzenie nadmiaru).

Jak dokonuje się tego obliczenia? Cóż, punktem wyjścia jest uznanie pliku za jeden duży łańcuch bitów podzielonych przez jakąś liczbę, dzielenie przez którą da resztę, mianowicie CRC! Działanie to zawsze daje resztę (może nią być zero), która jest najwyżej o jeden bit mniejsza niż dzielna (inaczej wciąż znajduje się w niej dzielnik). (9/3=3 reszta=0; (9+2)/3=3 reszta=2)

Tylko że tutaj, dzielenie przez bity wykonywane jest nieco inaczej. Dzielenie to powtarzane odejmowanie (x razy) liczby (dzielnika) od liczby, którą chcemy podzielić, co prowadzi do otrzymania reszty. Jeżeli chcemy otrzymać liczbę wyjściową, mnożymy przez dzielnik lub dodajemy dzielnik x razy do siebie a potem do wyniku dodajemy resztę.
Obliczenie CRC używa specjalnego sposobu na odejmowanie i dodawanie, tj. nowej "arytmetyki". Podczas obliczeń, dla obliczenia każdego bitu carry jest "zapominane". Przyjrzyjmy się dwóm przykładom, numer 1 to zwykłe odejmowanie, numery dwa i trzy są specjalne.


     -+

(1) 1101  (2) 1010  1010  (3) 0+0=0  0-0=0

    1010-     1111+ 1111-     0+1=1 *0-1=1

    ----      ----  ----      1+0=1  1-0=1

    0011      0101  0101     *1+1=0  1-1=0


W przykładzie pierwszym(1), drugą kolumnę od prawej można by rozwinąć do 0-1=-1, a więc bit jest "pożyczany" z sąsiadującego bitu, co daje następujące odejmowanie  (10+0)-1=1. (sposób podobny do odejmowania na papierze, odejmowania decymalnego)

Przykłady specjalne (2 i 3)

1+1 normalnie dałoby wynik 10, gdzie "1" jest carry, który "transportuje" wartość do obliczeń do następnego bitu. Ta wartość zostaje zapomniana.
Przypadek specjalny 0-1 normalnie miałby wartość "-1", co miałoby wpływ na sąsiadujący bit (patrz przykład 1). Ta wartość także zostaje zapomniana. Jeżeli wiesz coś o programowaniu, to wygląda, lub nawet lepiej powiedzieć, to jest operacja XOR.

Teraz przyjrzyjmy się przykładowi dzielenia:


To normalna arytmetyka:

1001/11110001101 13            9/12013

     1001    -                    09  -|

     ----                         --   |

      1100                         30  |

      1001    -                    27  -

      ----                         --

       0110                         3 -> reszta

       0000    -

       ----

        1100

        1001    -

        ----

         011 -> 3, reszta



W arytmetyce CRC:

1001/11110001110               9/12014 reszta 6

     1001    -

     ----

      1100

      1001    -

      ----

       1010

       1001    -

       ----

        0110

        0000    -

        ----

         110 -> reszta

(przykład 3)


Wynik dzielenia nie jest ważny, i nie warto go pamiętać, ponieważ wynosi on tylko kilka bitów mniej niż łańcuch bitów, z którego chciałeś obliczyć CRC. Ważna jest reszta! To ona mówi coś ważnego o oryginalnym pliku. To jest w zasadzie CRC!

Przejście do prawdziwych obliczeń CRC

By wykonać obliczenie CRC musimy wybrać dzielnik, od teraz będziemy go nazywać poly. Szerokość W poly to pozycja najwyższego bitu, a więc szerokość poly 1001 to 3, a nie 4. Zauważ, że najwyższym bitem jest zawsze jedynka, kiedy wybierasz więc szerokość poly musisz wybrać wartość tylko dla niższych bitów szerokości(W).

Jeżeli chcemy obliczyć CRC dla łańcucha bitów, musimy mieć pewność, że wszystkie bity zostaną przetworzone. Dlatego też musimy dodać do W bitów 0 do końca łańcucha. W przypadku przykładu 3, moglibyśmy powiedzieć, że łańcuch bitów to 1111. Przyjrzyjmy się nieco większemu przykładowi:

Poly                = 10011, szerokość W=4
Łańcuch bitów + W zer = 110101101 + 0000


10011/1101011010000110000101 (nieważny jest dla nas wynik)

      10011|||||||| -

      -----||||||||

       10011|||||||

       10011|||||||  -

       -----|||||||

        00001||||||

        00000||||||   -

        -----||||||

         00010|||||

         00000|||||    -

         -----|||||

          00101||||

          00000||||     -

          -----||||

           01010|||

           00000|||      -

           -----|||

            10100||

            10011||       -

            -----||

             01110|

             00000|        -

             -----|

              11100

              10011         -

              -----

               1111 -> reszta -> CRC!

(przykład 4)

Trzeba tu podkreślić dwie ważne rzeczy:
1. Tylko gdy najwyższy bit łańcucha ma wartość 1 wykonujemy na nim operację XOR w połączeniu z poly, w innym wypadku jedynie "przesuwamy" łańcuch bitów o jeden bit w lewo.
2. Efektem operacji XOR jest to, co zostało zXORowane z niższymi bitami szerokości W, ponieważ najwyższy bit zawsze będzie wynosił 0.

Przejście do algorytmu bazującego na tablicach

Wszyscy powinniście zrozumieć, że algorytm bazujący na obliczeniach binarnych będzie bardzo wolny i nieefektywny. Dużo bardziej wydajnie byłoby liczyć na bajtach. Ale wtedy możemy przyjąć poly tylko o szerokości wielokrotności 8 bitów (8 bitów to bajt). Przedstawmy to na przykładowym poly o szerokości 32 (W=32):


          3   2   1   0    bajt

        +---+---+---+---+

Pop! <--|   |   |   |   |<-- łańcuch bitów z dodanym W bitów, w tym wypadku 32

        +---+---+---+---+

       1<--- 32 bits ---> to jest poly, 4*8 bitów


(element 1)

To jest rejestr, którego używasz do chwilowego przechowywania CRC, nazywam go od tej chwili rejestrem CRC lub po prostu rejestrem. Przesuwasz bity do łańcucha bitów na prawo, a z łańcucha na lewo. Kiedy bit został usunięty z łańcucha a strona lewa jest równa 1, cały rejestr zostaje poddany operacji XOR przez niższe W bitów poly (w tym wypadku 32). Tak naprawdę jest to dokładnie taka sama operacja jak przedstawione wyżej dzielenie.
A co gdybyśmy (jak już mówiłem) przesunęli całą grupę bitów jednocześnie. Spójrz na przykład 8 bitowego CRC, gdzie przesunięto 4 bity za jednym razem:

Rejestr tuż przed przesunięciem: 10110100

Potem 4 bity (z góry) zostają usunięte z łańcucha z lewej strony, podczas gdy 4 nowe bity zostają dodane do łańcucha na prawą stronę. W tym wypadku 1011 zostaje usunięte a 1101 (nowe) zostaje dodane.

Potem sytuacja wygląda następująco:
8 bitowy rejestr CRC: 01001101
4 górne bity właśnie usunięte: 1011
używamy tego poly: 101011100, szerokość W=8

Teraz liczymy normalnie nową wartość rejestru.

Góra Rejestr
---- --------
1011 01001101  górne bity i rejestr
1010 11100   + (*1) Poly jest poddawane operacji XOR na pozycji 3 górnych bitów (bo tam znajduje się jedynka)

-------------
0001 10101101 wynik operacji XOR

Teraz wciąż mamy jedynkę w bicie na pozycji zero bitów górnych:

0001 10101101  poprzedni rezultat
1 01011100+ (*2) Poly jest poddawane operacji XOR na pozycji 0 górnych bitów (bo tam znajduje się jedynka)

-------------
0000 11110001 wynik drugiej operacji XOR
^^^^

Teraz górne bity to same zera, więc nie trzeba znów wykonywać operacji XOR na poly dla tej sekwencji górnych bitów.

Taką samą wartość rejestru otrzymuje się najpierw poddawszy operacji XOR (*1) z (*2) a wynik z rejestrem. Wynika to ze standardowej własności XOR:


(a XOR b) XOR c = a XOR (b XOR c)



1010 11100     poly na pozycji 3 górnych bitów

   1 01011100+ poly poddane operacji XOR na pozycji 0 górnych bitów

-------------

1011 10111100  (*3) rezultat operacji XOR

Rezultat (*3) jest poddawany operacji XOR z rejestrem
1011 10111100
1011 01001101+ górne bity i rejestr
-------------
0000 11110001
Widzisz? Wynik jest taki sam! Teraz (*3) jest ważny, ponieważ z górnymi bitami 1010, w podanych warunkach, zawsze powiązana jest wartość (*3)=10111100 (tylko niższe W=8 bitów). Dzięki temu możesz obliczyć wartości XOR dla każdej kombinacji bitów górnych zanim zaczniesz dalsze obliczenia. Zauważ, że górne bity zawsze otrzymują zero po jednym powtórzeniu, dzieje się tak dlatego, że prowadzi do tego kombinacja operacji XOR.

Teraz wracamy do elementu 1. Dla każdej wartości górnego bajtu (8 bitów), który właśnie został przesunięty, możemy wcześniej obliczyć wartość. W tym wypadku byłaby to tablica składająca się z 256(2^8) elementów dwuwyrazowych (32 bity). (tablica CRC32 znajduje się w załączniku)

W pseudo-języku nasz algorytm wygląda tak:

While (łańcuch bajtów nie jest wyczerpany)
Begin
Top = górny bajt rejestru
Register = rejestr przesunięty o 8 bitów w lewo i poddany operacji XOR nowym bajtem z łańcucha
Register = rejestr poddany operacji XOR wartością Top z wcześniej obliczonej tablicy wyników
End

Bezpośredni algorytm tablicowy

Algorytm zaproponowany powyżej może zostać zoptymalizowany. Bajty z łańcucha bajtów nie muszą podróżować przez cały rejestr nim zostaną użyte. Za pomocą tego algorytmu możemy bezpośrednio poddać operacji XOR bajt z łańcucha bajtów z bajtem przesuniętym z rejestru. Wynik wskazuje na wartość z tabeli wartości, która zostanie poddana operacji XOR z rejestrem.
Nie wiem dokładnie dlaczego operacje te dają ten sam rezultat (ma to coś wspólnego z własnością XOR), ale ma to jedną wielką zaletę - nie musisz dodawać bajtów/bitów 0 do łańcucha bajtów. (jeżeli ktoś wie dlaczego, proszę powiedzcie mi :)

Spróbujmy zobrazować ten algorytm:


  +----< łańcuch bajtów (lub plik)

  |

  v       3   2   1   0    bajt

  |     +---+---+---+---+

XOR---<|   |   |   |   |  rejestr

  |     +---+---+---+---+

  |             |

  |            XOR

  |             ^

  v     +---+---|---+---+

  |     |   |   |   |   |  tabela wyników

  |     +---+---+---+---+

  +--->-:   :   :   :   :

        +---+---+---+---+

        |   |   |   |   |

        +---+---+---+---+

(element 2)

"Odbity" bezpośredni algorytm tablicowy

By jeszcze skomplikować sprawę istnieje "odbita" wersja tego algorytmu. W "odbitym" rejestrze/wartości bity są zamieniane miejscami względem centrum. Na przykład 0111011001 jest odbiciem 1001101110.

Wymyślono to z powodu UART (chip wykonujący seryjne IO), który wysyła każdy bajt z najmniej istotnym bitem (bit 0) jako pierwsze a najbardziej istotny bit (bit 7) ostatni, co jest odwróceniem normalnej sytuacji.

Zamiast więc odwracać każdy bajt przed jego obróbką, każdy inny jest odwracany. Zaletą takiej operacji jest to, iż daje to kod o zmniejszonej objętości w implementacji. A więc, w tablicy obliczeniowej, bity zostają przesunięte w prawo a poly zostaje odwrócone. Podczas obliczania CRC rejestr zostaje przesunięty w prawo i (oczywiście) wykorzystuje się odwróconą tabelę.


łańcuch bajtów (lub plik) -->---+

                              |    1. Każdy element tablicy zostaje odwrócony

    bajt  3   2   1   0       V    2. Wyjściowy rejestr zostaje odwrócony

        +---+---+---+---+     |    3. Bajty z łańcucha bajtów nie zostają odwrócone,

        |   |   |   |   |>---XOR       ponieważ wszystko inne zostało.

        +---+---+---+---+     |

                |             |

               XOR            V

                ^             |

        +---+---|---+---+     |

        |   |   |   |   |     |   Tabela wyników

        +---+---+---+---+     |

        :   :   :   :   : <---+

        +---+---+---+---+

        |   |   |   |   |

        +---+---+---+---+

(element 3)


Nasz algortym:
1. Przesunąć rejestr on jeden bajt w prawo
2. Poddać operacji XOR górny bajt który został właśnie usunięty z nowym bajtem z łańcucha bajtów by otrzymać index do tablicy ([0,255])
3. Za pomocą operacji XOR wprowadzić wartość z tablicy do rejestru
4. Jeżeli zostało więcej bajtów do przetworzenia: patrz punkt 1

Kilka implementacji w assemblerze

Oto standard CRC-32:
Nazwa                 : "CRC-32"
Szerokość              : 32
Poly                : 04C11DB7
Wartość początkowa       : FFFFFFFF
Odwrócony           : Tak
XOR out with        : FFFFFFFF

Jako bonus dla ciekawskich, standard CRC-16: :)
Nazwa                : "CRC-16"
Szerokość               : 16
Poly                : 8005
Wartość początkowa       : 0000
Odwrócony           : Tak
XOR out with        : 0000

"XOR out with"  to wartość którą poddaje się operacji XOR z ostateczną wartością rejestru przed otrzymaniem (jako wynik) ostatecznego CRC.
Istnieją także odwrócone poly dla CRC ale są on nieistotne dla tego przewodnika. Spójrz na moje odniesienia jeżeli chcesz dowiedzieć się więcej.

Dla implementacji assemblerowej używam 32 bitowego kodu w 16 bitowym trybie DOSowym... a więc zobaczysz nieco pomieszanego 32 i 16 bitowego kodu... łatwo to przekonwertować w pełny 32 bitowy kod. Zauważ że implementacja assemblerowa została przetestowana i działa, natomiast kod Java i języka C są wnioskami płynącymi z poprzedniego kodu.
Ok. Oto implementacja w assemblerze obliczająca wartości tabeli CRC-32:

xor     ebx, ebx   ;ebx=0, ponieważ zostanie on użyty jako wskaźnik
InitTableLoop:
xor     eax, eax   ;eax=0, ponieważ na początku musi równać się 0
mov     al, bl     ;8 niższych bitów ebx zostaje skopiowane do 8 niższych bitów eax

;generate entry
xor     cx, cx
entryLoop:
test    eax, 1
jz     no_topbit
shr     eax, 1
xor     eax, poly
jmp    entrygoon
no_topbit:
shr     eax, 1
entrygoon:
inc     cx
test    cx, 8
jz     entryLoop

mov     dword ptr[ebx*4 + crctable], eax
inc     bx
test    bx, 256
jz     InitTableLoop

Notes:  - crctable to tablica 256 wartości dwuwyrazowych
- eax zostaje przesunięty w prawo, ponieważ CRC-32 używa odwróconego algorytmu
- dlatego też najniższe 8 bitów jest przetwarzanych...

To samo w Javie lub C (int ma 32 bity):

for (int bx=0; bx<256; bx++){
int eax=0;
eax=eax&0xFFFFFF00+bx&0xFF;      // the "mov al,bl" instruction
for (int cx=0; cx<8; cx++){
if (eax&&0x1) {
eax>>=1;
eax^=poly;
}
else eax>>=1;
}
crctable[bx]=eax;
}

Implementacja dla obliczeń CRC-32 z użyciem tabeli:

computeLoop:
xor     ebx, ebx
xor     al, [si]
mov     bl, al
shr     eax, 8
xor     eax, dword ptr[4*ebx+crctable]
inc     si
loop   computeLoop

xor     eax, 0FFFFFFFFh

Notes:  - ds:si wskazuje na bufor gdzie znajdują się bajty do przetworzenia
- cx zawiera ilość bajtów do przetworzenia
- eax zawiera obecny CRC
- crctable to tabela obliczona za pomocą powyższego kodu
- wyjściowa wartość CRC jest taka sama jak w przypadku CRC-32: FFFFFFFF
- po końcowych wyliczeniach CRC poddawany jest operacji XOR z: FFFFFFFF
co oznacza to samo co NOTacja.

W Javie lub języku C wygląda to tak:

for (int cx=0; cx>=8;) {
eax^=crcTable[ebx];
}
eax^=0xFFFFFFFF;

A więc wylądowaliśmy na końcu pierwszej części: przewodnika po CRC. Jeżeli chcesz lepiej poznać tajniki CRC sugeruję, byś przeczytał napisany przeze mnie dokument, do którego adres znajdziesz na końcu tego dokumentu.
Ok. A teraz przejdźmy do najbardziej interesującej części tego dokumentu: odwracania CRC

Częśc 2: Odwracanie CRC

Kiedy myślałem nad sposobem by odwrócić CRC ... kilkakrotnie utknąłem. Próbowałem "dezaktywować" CRC poprzez taką sekwencję bajtów, żeby potem nie miało już  znaczenia jakie bajty umieściłbyś po nim. Nie potrafiłem tego zrobić... Potem zdałem sobie sprawę z tego, że to nigdy nie mogło działać w ten sposób, ponieważ algorytm CRC jest zbudowany w taki sposób, że nieważne, który bit zostanie zmieniony, kompletny CRC zawsze (cóż...prawie zawsze) zmienia się drastycznie. Spróbuj sam (z pomocą jakiegoś prostego programu CRC)... :)

Zdałem sobie sprawę z tego, że mogę tylko poprawić CRC po bajtach które chciałem zmienić. A więc mogłem stworzyć taką sekwencję bajtów, która przekształciłaby CRC w cokolwiek bym chciał.
Zobrazujmy ten pomysł:

Zlepek bajtów: 01234567890123456789012345678901234567890123456789012
Chcesz zmienić od        ^ tego bajtu do  ^ tego bajtu
To pozycje od 9 do 26
Potrzebujemy także 4 dodatkowych bajtów (do pozycji 30 ^) dla sekwencji bajtów, która przywróci CRC do jego oryginalnej wartości po zmienionych bajtach.

Gdy liczysz CRC-32 wszystko idzie gładko aż do bajtu na pozycji 9, w zlepku zmienianych bajtów CRC zmienia się radyklanie od tej pozycji. Nawet po przekroczeniu pozycji 26, gdzie bajty nie zostają już zmienione, nigdy nie odzyskasz oryginalnego CRC. NIE! Kiedy przeczytasz resztę tego eseju będziesz wiedział jak to zrobić.
W skrócie musisz postąpić tak gdy zmieniasz zlepek bajtów zatrzymując oryginalny CRC:

1. Obliczyć CRC do pozycji 9 i zapisać tą wartość.
2. Liczyć dalej aż do pozycji 27 i dla dalszych 4 dodatkowych bajtów i zapisać wynik.
3. Użyć wartości z punktu 1 do obliczenia CRC nowych bajtów i 4 dodatkowych bajtów (powinno być 27-9+4=22 bajty) i zapisać wynik.
4. Teraz mamy nową wartość CRC, ale chcemy by CRC było starym CRC. Używamy odwróconego algorytmu do obliczenia dodatkowych 4 bajtów.

Potrafimy wykonać obliczenia z punktów 1-3, teraz nauczymy się tych z punktu 4.

Odwracanie CRC-16

Pomyślałem, że żeby ułatwić wam sprawę, najpierw pokażę jak obliczyć odwrotność CRC-16. Ok. Jesteśmy w pewnym punkcie po zmianie kodu, kiedy chcemy przywrócić CRC jego oryginalną wartość. Znamy oryginalny CRC (obliczony przed zmienieniem danych) i obecny rejestr CRC. Chcemy obliczyć 2bajtowy łańcuch który zmienia obecny rejestr CRC na oryginalny CRC. Wpierw obliczamy "normalnie" CRC nieznanych 2 bajtów nadając im nazwę X i Y, a za wartość rejestru przyjmujemy a1 a0, jedynym elementem, który nie jest zmienną jest zero (00). :) Spójrzmy na nasz najnowszy algorytm CRC (element 3), by lepiej zrozumieć o czym mowa.
Ok., zaczynamy:

Weźmy 2bajtowy łańcuch "X Y". Bajty przetwarzane są od lewej strony.
Za rejestr przyjmijmy a1 a0.
Zamiast "operacja XOR" pisać będziemy "+" (tak jak w przewodniku).

Przetwarzamy pierwszy bajt, X:
a0+X            to jest obliczony górny bajt (1)
b1 b0           sekwencja tabeli na którą wskazuje górny bajt
00 a1           rejestr przesunięty w prawo
00+b1 a1+b0     poprzednie 2 wiersze poddane operacji XOR ze sobą

Teraz wartość rejestru to: (b1) (a1+b0)

Przetwarzamy drugi bajt, Y:
(a1+b0)+Y       to jest obliczony górny bajt (2)
c1 c0           sekwencja tabeli na którą wskazuje górny bajt
00 b1           rejestr przesunięty w prawo
00+c1 b1+c0     poprzednie 2 wiersze poddane operacji XOR ze sobą

Teraz wartość rejestru to: (c1) (b1+c0)

Pokażę to w trochę inny sposób:

a0 + X      =(1)  wskazuje na b1 b0 w tabeli
a1 + b0 + Y =(2)  wskazuje na c1 c0 w tabeli
b1 + c0=d0  nowy niski bajt rejestru
c1=d1  nowy górny bajt rejestru
(1)  (2)

Wow! Niech ta informacja popracuje nad tobą przez chwilę... :)
Nie bój się - zaraz omówimy przykład na konkretnej wartości

A co gdybyś chciał żeby rejestr był jakimś d1 d0 (oryginalny CRC) I znałbyś wartość rejestru przed transformacją (a więc a1 a0)... jakie 2 bajty lub jakie X i Y musiałbyś przepuścić przez obliczenia CRC?
Ok. Zaczniemy pracę od końca i cofniemy się do początku. d0 musi być równe b1+c0 a d1 musi być równe c1... Ale już słyszę jak mówisz: "Skąd do cholery wziąć wartość bajtów b1 i c0???" Czy muszę przypominać ci o tabeli? Możesz po prostu sprawdzić wartość wyrażeń c0 c1 w tabeli ponieważ znasz c1. Dlatego bardzo ważne jest, by wyrobić sobie nawyk patrzenia w tabelę. Jeżeli znalazłeś wartość, zapamiętaj index do tej wartości, ponieważ w ten sposób znajdziesz nieznane górne bajty np. (1)&(2)!
A więc teraz gdy znalazłeś c1 c0, skąd wziąć b1 b0? Jeżeli b1+c0=d0 to b1=d0+c0! Teraz spójrz w tabelę by otrzymać wartość b1 b0. Teraz znamy wszystko co potrzebne do obliczenia X & Y! Fajnie, nie?
a1+b0+Y=(2) więc Y=a1+b0+(2)
a0+X=(1)    więc X=a0+(1)

Konkretny przykład dla CRC-16

Przyjrzyjmy się przykładowi z konkretnymi wartościami:
-rejestr przed: (a1=)DE (a0=)AD
-poszukiwany rejestr: (d1=)12 (d0=)34
Odnajdź w tabeli pozycję zaczynającą się od 12 w tabeli CRC-16 w załaczniku.

- Chodzi o pozycję 38h mającą wartość 12c0. Spróbuj znaleźć inną pozycję zaczynającą się od 12. Nie możesz znaleźć innej bo obliczyliśmy każdą pozycję dla każdej możliwej wartości górnego bajtu a to daje 256 warości, zapamiętaj!
Teraz wiemy że (2)=38, c1=12 a c0=c0, a więc b1=c0+34=F4, teraz odnajdź w tabeli pozycję B1 zaczynającą się od F4.

-To pozycja 4Fh zaczynająca się od wartości F441.

Teraz wiemy, że (1)=4F, b1=F4 a b0=41. Teraz znamy wszystkie potrzebne wartości by móc obliczyć X i Y a więc bierzemy się do tego:

Y=a1+b0+(2)=DE+41+38=A7
X=a0+(1)   =AD+4F   =E2

Wniosek: by zmienić rejestr CRC-16 z DEAD na 1234 potrzebujemy bajtów E2 i A7 (w tej kolejności).

Widzisz, by odwrócić CRC musisz sobie "obliczyć drogę powrotną" i zapamiętywać otrzymywane po drodze wyniki. Kiedy programujesz tabelę w asemblerze, pamiętaj że intel zapisuje wartości od końca w formacie Little-Endian. Teraz pewnie rozumiesz jak odwrócić CRC-16 ... teraz CRC-32.

Odwracanie CRC-32

Omówiliśmy już CRC-16, CRC-32 jest tak samo łatwy do odwrócenia (lub tak samo trudny). Teraz pracujemy z 4 zamiast 2 bajtów. Podczas czytania zerkaj i porównuj to z wersją dla 16bit.

Weźmy 4bajtowy łańcuch X Y Z W, bajty bierzemy z lewej strony.
Za rejestr przyjmijmy a3 a2 a1 a0
Zauważ, że a3 jest najważniejszym bajtem a a0 najmniej ważnym.

Przetwarzamy pierwszy bajt, X:
a0+X                    to jest obliczony górny bajt (1)
b3    b2    b1    b0    sekwencja tabeli na którą wskazuje górny bajt
00    a3    a2    a1    rejestr przesunięty w prawo
00+b3 a3+b2 a2+b1 a1+b0 poprzednie 2 wiersze poddane operacji XOR ze sobą

Teraz rejestr to: (b3) (a3+b2) (a2+b1) (a1+b0)

Przetwarzamy drugi bajt, Y:
(a1+b0)+Y                       to jest obliczony górny bajt (2)
c3    c2    c1       c0         sekwencja tabeli na którą wskazuje górny bajt
00    b3    a3+b2    a2+b1      rejestr przesunięty w prawo
00+c3 b3+c2 a3+b2+c1 a2+b1+c0   poprzednie 2 wiersze poddane operacji XOR ze sobą

Teraz rejestr to: (c3) (b3+c2) (a3+b2+c1) (a2+b1+c0)

Przetwarzamy trzeci bajt, Z:
(a2+b1+c0)+Z                    to jest obliczony górny bajt (3)
d3    d2    d1       d0         sekwencja tabeli na którą wskazuje górny bajt
00    c3    b3+c2    a3+b2+c1    rejestr przesunięty w prawo
00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 poprzednie 2 wiersze poddane operacji XOR ze sobą

Teraz rejestr to:: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0)

Przetwarzamy czwarty bajt, W:
(a3+b2+c1+d0)+W                 to jest obliczony górny bajt (4)
e3    e2    e1       e0         sekwencja tabeli na którą wskazuje górny bajt
00    d3    c3+d2    b3+c2+d1    rejestr przesunięty w prawo
00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 poprzednie 2 wiersze poddane operacji XOR ze sobą

Teraz rejestr to: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0)


Pokażę to na trochę inny sposób:

a0 + X                  =(1)  wskazuje na b3 b2 b1 b0  z tabeli

a1 + b0 + Y             =(2)  wskazuje na  c3 c2 c1 c0  z tabeli

a2 + b1 + c0 + Z        =(3)  wskazuje na  d3 d2 d1 d0  z tabeli

a3 + b2 + c1 + d0 + W   =(4)  wskazuje na  e4 e3 e2 e1  z tabeli

     b3 + c2 + d1 + e0  =f0

          c3 + d2 + e1  =f1

               d3 + e2  =f2

                    e3  =f3

    (1)  (2)  (3)  (4)

(element 4)


Kod ten został odwrócony w taki sam spobób jak jego 16bitowa wersja. Podam teraz przykład z prawdziwymi wartościami. Jako tablicy wartości użyj tablicy CRC-32 z załącznika.
Za rejestr CRC przed -  a3 a2 a1 a0 -przyjmij odpowiednio AB CD EF 66
Za rejestr CRC po - f3 f2 f1 f0 -przyjmij odpowiednio 56 33 14 78 (szukana wartość)

Zaczynamy:

Pierwszy bajt wpisu:             wpis     wartość
e3=f3                     =56 -> 35h=(4) 56B3C423 dla e3 e2 e1 e0
d3=f2+e2      =33+B3      =E6 -> 4Fh=(3) E6635C01 dla d3 d2 d1 d0
c3=f1+e1+d2   =14+C4+63   =B3 -> F8h=(2) B3667A2E dla c3 c2 c1 c0
b3=f0+e0+d1+c2=78+23+5C+66=61 -> DEh=(1) 616BFFD3 dla b3 b2 b1 b0

Teraz mamy wszystkie potrzebne wartości, a więc
X=(1)+         a0=         DE+66=B8
Y=(2)+      b0+a1=      F8+D3+EF=C4
Z=(3)+   c0+b1+a2=   4F+2E+FF+CD=53
W=(4)+d0+c1+b2+a3=35+01+7A+6B+AB=8E
(ostateczne obliczenie)

Wniosek: by zmienić rejestr CRC-32 z ABCDEF66 na 56331478 potrzebujemy takiej sekwencji bajtów B8 C4 53 8E

Odwrócony algorytm dla CRC-32

Jeżeli spojrzysz na ręczne obliczenia sekwencji bajtów potrzebnych do zmiany rejestru CRC z a3 a2 a1 a0  na  f3 f2 f1 f0  zobaczysz, że trudno przekształcić je w miły algorytm o małej objętości.


Spójrzmy na rozszerzoną wersję ostatecznego obliczenia:

                            Pozycja

X =(1) +                a0     0

Y =(2) +           b0 + a1     1

Z =(3) +      c0 + b1 + a2     2

W =(4) + d0 + c1 + b2 + a3     3

f0= e0 + d1 + c2 + b3          4

f1= e1 + d2 + c3               5

f2= e2 + d3                    6

f3= e3                         7

(element 5)

To tak jak w elemencie 4, tylko niektóre wartości/bajty zostały zamienione. Ten punkt widzenia pomoże nam w wypracowaniu kompaktowego algorytmu. Co jeśli weźmiemy bufor o rozmiarach 8 bajtów, gdzie dla każdej linii którą widzisz w elemencie 5 zarezerwowany jest jeden bajt. Bajty od 0 do 3 są wypełnione a0 do a3, bajty 4 do 7 od f0 do f3. Jak wcześniej bierzemy ostatni bajt e3, który jest równy f3, i sprawdzamy jego kompletną wartość w tabeli CRC.Potem na pozycji 4 (tak jak w elemencie 5) poddajemy tą wartość (e3 e2 e1 e0) operacji XOR. Automatycznie znamy wartość d3, ponieważ poddaliśmy już operacji XOR f3 f2 f1 f0 z e3 e2 e1 e0, a f2+e2=d3. Ponieważ znamy już wartość (4) (cyfra elementarna), możemy bezpośrednio poddać ją operacji XOR na pozycję 3. Gdy znamy już wartość d3 możemy jej użyć by z tabeli odczytać wartość d3 d2 d1 d0 i poddać ją operacji XOR na poprzedniej pozycji, tj. pozycji 3. Teraz poddajemy znaleziony numer wejścia (3) operacji XOR z tym z pozycji 2. Znamy wartość c3 ponieważ znamy wartość f1+e1+d2=c3 na pozycji 5.

Robimy tak aż poddamy operacji XOR b3 b2 b1 b0 na pozycji 1. I voila! Bajty 0 do 3 z bufora teraz zawierają potrzebne nam bajty X do W!

Oto podsumowanie algorytmu:
1. W 8 bajtowym buforze, pozycje od 0 do 3 wypełnij wartościami od a0 do a3 (wartość początkowa rejestru CRC), a pozycje 4 do 7 wartościami f0 do f3 (żądana końcowa wartość rejestru CRC).
2.Weź bajt z pozycji 7 i użyj go by odczytać z tabeli pełną wartość.
3. Poddaj tą wartość (dwuwyraz) operacji XOR na pozycji 4
4. Poddaj operacji XOR numer wejścia (bajt) na pozycji 3
5. Powtórz krok 2 I 3 jeszcze 3 razy za każdym razem zmniejszając pozycję o jeden.

Implementacja odwróconego algorytmu.

Teraz czas na trochę kodu. Poniżej znajduje się implementacja odwróconego algorytmu dla CRC-32 w Asemblerze (nie jest trudno zrobić to samo dla innych języków i/lub standardów CRC). Pamiętaj, że w asemblerze (na PC"tach) dwuwyrazy są zapisywane i czytane z pamięci w odwrotnej kolejności.

Wyjściowe CRC (crcBefore)       dd (?)
Żądane CRC (wantedCrc)       dd (?)
Bufor (buffer)          db 8 dup (?)

mov     eax, dword ptr[crcBefore] ;/*
mov     dword ptr[buffer], eax
mov     eax, dword ptr[wantedCrc] ; Step 1
mov     dword ptr[buffer+4], eax  ;*/

mov     di, 4
computeReverseLoop:
mov     al, byte ptr[buffer+di+3] ;/*
call   GetTableEntry              ; Step 2 */
xor     dword ptr[buffer+di], eax ; Step 3
xor     byte ptr[buffer+di-1], bl ; Step 4
dec     di                        ;/*
jnz    computeReverseLoop         ; Step 5 */

Notes:
-Używa się rejestrów eax, di bx

Implementacja GetTableEntry

crctable        dd 256 dup (?)      ;powina zostać gdzieś zdefiniowana globalnie;amp; oczywiście zainicjalizowana

mov     bx, offset crctable-1
getTableEntryLoop:
add     bx, 4                ;points to (crctable-1)+k*4 (k:1..256)
cmp     [bx], al             ;must always find the value somewhere
jne     getTableEntryLoop

sub     bx, 3
mov     eax, [bx]
sub     bx, offset crctable
shr     bx, 2

ret

NA wyjściu eax zawiera pozycję z tabeli, bx numer pozycji z tabeli.

Outtro

Cóż...dotarłeś do końca tego eseju. Jeżeli teraz myślisz: wow, wszystkie te programy chronione przez CRC mogą się teraż pożegnać... nic z tego. Bardzo łatwo napisać anty-anty CRC. By udało się odwrócić CRC musisz wiedzieć dokładnie od której części kodu obliczane jest CRC i jaki algorytm CRC jest do tego wykorzystywany. Powszechnym zabezpieczeniem jest używanie dwóch algorytmów CRC albo kombinacji z innym algorytmem ochrony danych.
Mam nadzieję, że to wszystko było interesujące I że tyle samo radości czerpałeś z czytania tego jak ja z pisania.

Podziękowania dla beta-testerów Douby/DREAD and Knotty Dread za komentarze odnośnie mojej pracy, które uczyniły ją jeszcze lepszą!

By zdobyć demonstracyjny program poprawiający CRC-32 odwiedź moje strony:
http://surf.to/anarchriz  -> Programming -> Projects
(to wciąż wersja próbna, ale da ci dowód na prawdziwość mojego pomysłu)

Po więcej informacji od DREAD odwiedź http://dread99.cjb.net

Jeżeli wciąż masz jakieś pytania możesz do mnie napisać e-mail: anarchriz@hotmail.com lub spróbować kanałów IRC #DreaD, #Win32asm, #C.I.A i #Cracking4Newbies (w tej kolejności) na Efnet.

CYA ALL! - Anarchriz

"The system makes its morons, then despises them for their ineptitude, and
rewards its "gifted few" for their rarity." - Colin Ward

Załącznik


Tabela CRC-16



  00h   0000 C0C1 C181 0140 C301 03C0 0280 C241

  08h   C601 06C0 0780 C741 0500 C5C1 C481 0440

  10h   CC01 0CC0 0D80 CD41 0F00 CFC1 CE81 0E40

  18h   0A00 CAC1 CB81 0B40 C901 09C0 0880 C841



  20h   D801 18C0 1980 D941 1B00 DBC1 DA81 1A40

  28h   1E00 DEC1 DF81 1F40 DD01 1DC0 1C80 DC41

  30h   1400 D4C1 D581 1540 D701 17C0 1680 D641

  38h   D201 12C0 1380 D341 1100 D1C1 D081 1040



  40h   F001 30C0 3180 F141 3300 F3C1 F281 3240

  48h   3600 F6C1 F781 3740 F501 35C0 3480 F441

  50h   3C00 FCC1 FD81 3D40 FF01 3FC0 3E80 FE41

  58h   FA01 3AC0 3B80 FB41 3900 F9C1 F881 3840



  60h   2800 E8C1 E981 2940 EB01 2BC0 2A80 EA41

  68h   EE01 2EC0 2F80 EF41 2D00 EDC1 EC81 2C40

  70h   E401 24C0 2580 E541 2700 E7C1 E681 2640

  78h   2200 E2C1 E381 2340 E101 21C0 2080 E041



  80h   A001 60C0 6180 A141 6300 A3C1 A281 6240

  88h   6600 A6C1 A781 6740 A501 65C0 6480 A441

  90h   6C00 ACC1 AD81 6D40 AF01 6FC0 6E80 AE41

  98h   AA01 6AC0 6B80 AB41 6900 A9C1 A881 6840



  A0h   7800 B8C1 B981 7940 BB01 7BC0 7A80 BA41

  A8h   BE01 7EC0 7F80 BF41 7D00 BDC1 BC81 7C40

  B0h   B401 74C0 7580 B541 7700 B7C1 B681 7640

  B8h   7200 B2C1 B381 7340 B101 71C0 7080 B041



  C0h   5000 90C1 9181 5140 9301 53C0 5280 9241

  C8h   9601 56C0 5780 9741 5500 95C1 9481 5440

  D0h   9C01 5CC0 5D80 9D41 5F00 9FC1 9E81 5E40

  D8h   5A00 9AC1 9B81 5B40 9901 59C0 5880 9841



  E0h   8801 48C0 4980 8941 4B00 8BC1 8A81 4A40

  E8h   4E00 8EC1 8F81 4F40 8D01 4DC0 4C80 8C41

  F0h   4400 84C1 8581 4540 8701 47C0 4680 8641

  F8h   8201 42C0 4380 8341 4100 81C1 8081 4040





Tabela CRC-32



  00h   00000000 77073096 EE0E612C 990951BA

  04h   076DC419 706AF48F E963A535 9E6495A3

  08h   0EDB8832 79DCB8A4 E0D5E91E 97D2D988

  0Ch   09B64C2B 7EB17CBD E7B82D07 90BF1D91



  10h   1DB71064 6AB020F2 F3B97148 84BE41DE

  14h   1ADAD47D 6DDDE4EB F4D4B551 83D385C7

  18h   136C9856 646BA8C0 FD62F97A 8A65C9EC

  1Ch   14015C4F 63066CD9 FA0F3D63 8D080DF5



  20h   3B6E20C8 4C69105E D56041E4 A2677172

  24h   3C03E4D1 4B04D447 D20D85FD A50AB56B

  28h   35B5A8FA 42B2986C DBBBC9D6 ACBCF940

  2Ch   32D86CE3 45DF5C75 DCD60DCF ABD13D59



  30h   26D930AC 51DE003A C8D75180 BFD06116

  34h   21B4F4B5 56B3C423 CFBA9599 B8BDA50F

  38h   2802B89E 5F058808 C60CD9B2 B10BE924

  3Ch   2F6F7C87 58684C11 C1611DAB B6662D3D



  40h   76DC4190 01DB7106 98D220BC EFD5102A

  44h   71B18589 06B6B51F 9FBFE4A5 E8B8D433

  48h   7807C9A2 0F00F934 9609A88E E10E9818

  4Ch   7F6A0DBB 086D3D2D 91646C97 E6635C01



  50h   6B6B51F4 1C6C6162 856530D8 F262004E

  54h   6C0695ED 1B01A57B 8208F4C1 F50FC457

  58h   65B0D9C6 12B7E950 8BBEB8EA FCB9887C

  5Ch   62DD1DDF 15DA2D49 8CD37CF3 FBD44C65



  60h   4DB26158 3AB551CE A3BC0074 D4BB30E2

  64h   4ADFA541 3DD895D7 A4D1C46D D3D6F4FB

  68h   4369E96A 346ED9FC AD678846 DA60B8D0

  6Ch   44042D73 33031DE5 AA0A4C5F DD0D7CC9



  70h   5005713C 270241AA BE0B1010 C90C2086

  74h   5768B525 206F85B3 B966D409 CE61E49F

  78h   5EDEF90E 29D9C998 B0D09822 C7D7A8B4

  7Ch   59B33D17 2EB40D81 B7BD5C3B C0BA6CAD



  80h   EDB88320 9ABFB3B6 03B6E20C 74B1D29A

  84h   EAD54739 9DD277AF 04DB2615 73DC1683

  88h   E3630B12 94643B84 0D6D6A3E 7A6A5AA8

  8Ch   E40ECF0B 9309FF9D 0A00AE27 7D079EB1



  90h   F00F9344 8708A3D2 1E01F268 6906C2FE

  94h   F762575D 806567CB 196C3671 6E6B06E7

  98h   FED41B76 89D32BE0 10DA7A5A 67DD4ACC

  9Ch   F9B9DF6F 8EBEEFF9 17B7BE43 60B08ED5



  A0h   D6D6A3E8 A1D1937E 38D8C2C4 4FDFF252

  A4h   D1BB67F1 A6BC5767 3FB506DD 48B2364B

  A8h   D80D2BDA AF0A1B4C 36034AF6 41047A60

  ACh   DF60EFC3 A867DF55 316E8EEF 4669BE79



  B0h   CB61B38C BC66831A 256FD2A0 5268E236

  B4h   CC0C7795 BB0B4703 220216B9 5505262F

  B8h   C5BA3BBE B2BD0B28 2BB45A92 5CB36A04

  BCh   C2D7FFA7 B5D0CF31 2CD99E8B 5BDEAE1D



  C0h   9B64C2B0 EC63F226 756AA39C 026D930A

  C4h   9C0906A9 EB0E363F 72076785 05005713

  C8h   95BF4A82 E2B87A14 7BB12BAE 0CB61B38

  CCh   92D28E9B E5D5BE0D 7CDCEFB7 0BDBDF21



  D0h   86D3D2D4 F1D4E242 68DDB3F8 1FDA836E

  D4h   81BE16CD F6B9265B 6FB077E1 18B74777

  D8h   88085AE6 FF0F6A70 66063BCA 11010B5C

  DCh   8F659EFF F862AE69 616BFFD3 166CCF45



  E0h   A00AE278 D70DD2EE 4E048354 3903B3C2

  E4h   A7672661 D06016F7 4969474D 3E6E77DB

  E8h   AED16A4A D9D65ADC 40DF0B66 37D83BF0

  ECh   A9BCAE53 DEBB9EC5 47B2CF7F 30B5FFE9



  F0h   BDBDF21C CABAC28A 53B39330 24B4A3A6

  F4h   BAD03605 CDD70693 54DE5729 23D967BF

  F8h   B3667A2E C4614AB8 5D681B02 2A6F2B94

  FCh   B40BBE37 C30C8EA1 5A05DF1B 2D02EF8D

Odniesienia:

> Bezbolesny przewodnik po algorytmie wykrywania błędów CRC:
url: ftp://ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
(Założę się, że ten "bezbolesny przewodnik" jest bardziej bolesny niż mój "krótki";)

> Użyłem też losowego źródła algorytmu CRC-32 by lepiej zrozumieć ten algorytm.

> Link do programów obliczających CRC... hmmm poszukaj "CRC.ZIP" lub "CRC.EXE" lub czegoś podobnego w wyszukiwarce ftp na http://ftpsearch.lycos.com?form=advanced

Copyright (c) 1998,1999 by Anarchriz
(to już NAPRAWDĘ ostatnia linijka:)

Copyright (c) 2002 for the polish translation by Michał "Evangelion" Skoczyński

Comments

Comment viewing options

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
Select your preferred way to display the comments and click "Save settings" to activate your changes.

To zależy od przewidywanej ilości rekordów:

http://www.datamgmt.com/index.php?module=article&view=42

Niezależnie od realnej możliwości kolizji to trzeba też wziąć pod uwagę reakcję CRC-32 na drobne różnice pomiędzy tekstami wejściowymi takie jak np. przestawienie liter, zmiana wielkości liter tzn czy w takichp rzypadkach nie wystąpią kolizje. Najlepiej sprawdzić to na żywo na rzeczywistych danych. Mała złożoność obliczeniowa jest tutaj jedynym, ale dość istotnym argumentem za CRC-32 i przeciwko kryptograficznym funkcjom skrótu.

Jaka jest szansa na powtórzenie crc32 dla dwóch różnych ciągów?
Chciałem użyć crc32 jako klucza głównego w tabeli mysql... dobry pomysł?