Algorytm funkcji skrótu md5

hoobert · 31 Maj 2013 11:31

Witam,

na wstępie przepraszam, jeżeli pomyliłem dział. Przeglądając ‘bezpieczeństwo’, stwierdziłem, że ten jednak będzie odpowiedniejszy.

Analizuję funkcję skrótu md5 i przygotowuję algorytm w języku php, lecz to akurat ma najmniejsze znaczenie.

Przeglądałem wiele opisów tej funkcji, głównie w najbardziej chyba wiarygodnym źródle a mianowicie dokumencie RFC1321, jak i m.in. w książce “Podstawy kryptografii” pana Marcina Karbowskiego, natomiast mam problem ze zrozumieniem jednej rzeczy

Czyli zakładając, że mam tekst ‘jakistekst’, jego reprezentacja bitowa wygląda następująco: 1101010110000111010111101001111001111101001100101110101111100111110100

teraz tworzymy tablicę N-elementową, gdzie N to ceil(długość bitowa wiadomości wejściowej / 512) i uzupełniamy po kolei elementy tej tablicy

1. 1101010110000111010111101001111

2. 0011111010011001011101011111001

3. 11110100

dodajemy na końcu bit o wartości ‘1’ a następnie uzupełniamy zerami. Czyli tablica wartości binarnych dla tego tekstu wygląda następująco:

1. 1101010110000111010111101001111

2. 0011111010011001011101011111001

3. 11110100[b]1[/b]0000000000000000000000

4. 0000000000000000000000000000000

5. 0000000000000000000000000000000

6. 0000000000000000000000000000000

7. 0000000000000000000000000000000

8. 0000000000000000000000000000000

9. 0000000000000000000000000000000

10. 0000000000000000000000000000000

11. 0000000000000000000000000000000

12. 0000000000000000000000000000000

13. 0000000000000000000000000000000

14. 0000000000000000000000000000000

15. 0000000000000000000000000000000

16. 0000000000000000000000000000000

Zakładając, że tablica wartości ma wynosić 448 modulo 512 a dopełnienie ostatnich 64 bitów ma być przeznaczone na informację odnośnie długości wiadomości rozumiem to w ten sposób, że jeżeli długość tej wiadomości wynosi 80 bitów (strlen(‘jakistekst’) * 8 bitów) to ta tablica (dla N=1) powinna wyglądać w taki sposób: ?

1. 1101010110000111010111101001111

2. 0011111010011001011101011111001

3. 11110100[b]1[/b]0000000000000000000000

4. 0000000000000000000000000000000

5. 0000000000000000000000000000000

6. 0000000000000000000000000000000

7. 0000000000000000000000000000000

8. 0000000000000000000000000000000

9. 0000000000000000000000000000000

10. 0000000000000000000000000000000

11. 0000000000000000000000000000000

12. 0000000000000000000000000000000

13. 0000000000000000000000000000000

14. 0000000000000000000000000000000

15. 0000000000000000000000000000000

16. 000000000000000000000000[b]1010000[/b]

Czy ta tablica wartości początkowych powinna wyglądać w taki sposób, czy jednak źle zinterpretowałem opis dotyczący tej części algorytmu?

Z góry dziękuję za odpowiedzi.

Pozdrawiam.

Pablo_Wawa · 31 Maj 2013 12:22

Niezupełnie tak, choć Twoje rozumowanie jest w większości poprawne. Błąd masz przy dodawaniu 64-bitów zawierających długość szyfrowanego tekstu - jak możesz przeczytać choćby tutaj http://pl.wikipedia.org/wiki/MD5:

Czyli te bity “1010000” powinny znaleźć się na początku (tuż zaraz za tą dodatkowa “jedynką”) - a potem cała reszta będzie zerami.

WAŻNE: z uwagi na to, że kolejność wszystkich bitów jest od najmłodszego do najstarszego, to tablica bitowa wygląda inaczej. Choćby dla liczby 80 (ta nasza długość tekstu w bitach) powinna w tablicy mieć postać 00001010 , choć binarnie liczba 80 to 01010000, ale ta (ostatnia) postać jest dla bitów od najstarszego do najmłodszego. I pamiętaj, że każdy znak zajmuje 8-bitów (Ty chyba tego nie uwzględniłeś w swoim przykładzie, bo nieznaczące zera pominąłeś, no i nie tą kolejność bitową zastosowałeś). Podobnie (w innej kolejności bitowej niż to zrobiłeś) musisz zapisywać tekst do zakodowania. Ale jeśli znaki tekstu do zakodowania będę zapisywane kolejno jako bajty, to nie musisz się wtedy martwić o właściwą kolejność bitów - ta musi być za to uwzględniana w dalszym algorytmie. A przy uzupełnianiu tekstu “1” i długością tekstu możesz zrobić tak, że długość tekstu mnożysz przez 2 i dodajesz 1 - to odpowiada przesuniąciu bitowego w górę i uzupełnieniu o “1”, w potem taką liczbę traktujesz jako 64-bitową (8-bajtową) i uzupełniasz tablicę - cały czas operujesz na bajtach (uwaga na kolejność - bajty też od najmłodszego do najstarszego), co jest i wygodniejsze, i szybsze.

Przy okazji - pewnie wiesz, że w PHP możesz skorzystać z gotowych funkcji hashujących i szyfrujących (http://php.net/manual/pl/function.md5.php).

hoobert · 1 Czerwiec 2013 07:29

Pablo_Wawa dzięki za odpowiedź.

Racja, pominąłem nieznaczące zera. Czyli mam to rozumieć w ten sposób, że jeżeli mam tekst ‘jakistekst’ i jego reprezentacja bitowa wygląda w ten sposób:

j: 01101010

a: 01100001

k: 01101011

i: 01101001

s: 01110011

t: 01110100

e: 01100101

k: 01101011

s: 01110011

t: 01110100

oraz jego długość bitowa to 80 (1010000) czyli jeżeli zaczynając od najmniej znaczącego bitu wygląda to w sposób następujący: 0000101 to tablica wartości bitowych wygląda w ten sposób: ?

Array

(

    [0] => Array

        (

            [0] => 01010110100001101101011010010110

            [1] => 11001110001011101010011011010110

            [2] => 11001110001011101010110000000000

            [3] => 00000000000000000000000000000000

            [4] => 00000000000000000000000000000000

            [5] => 00000000000000000000000000000000

            [6] => 00000000000000000000000000000000

            [7] => 00000000000000000000000000000000

            [8] => 00000000000000000000000000000000

            [9] => 00000000000000000000000000000000

            [10] => 00000000000000000000000000000000

            [11] => 00000000000000000000000000000000

            [12] => 00000000000000000000000000000000

            [13] => 00000000000000000000000000000000

            [14] => 00000000000000000000000000000000

            [15] => 00000000000000000000000000000000

        )


)

tutaj odwrócone są wartości bitowe dla kolejnych znaków ciągu wejściowego zaczynając od ‘j’ a kończąc na ‘t’.

Czy to rozumienie jest dobre?

I co do długości bitowej. Każdy znak to 8 bitów. Co ze znakami, które nie mieszczą się w zakresie ASCII? Czy wówczas znak może przyjąć więcej jak 8 bitów?

I tak, oczywiście wiem, że w php są wbudowane funkcje skrótów jak i inne funkcje szyfrujące oraz hashujące.

Pozdrawiam.

Pablo_Wawa · 1 Czerwiec 2013 09:28

Teraz jest prawie dobrze - wydaje mi się, że masz błąd w elemencie [2] tablicy, przy trzeciej ósemce bitowej, bo tam stawiasz tylko jedynkę bitową (znacznik końca tekstu) i uzupełniasz do 448 elementu zerami:

[2] => 11001110 00101110 10000000 00000000

No i wartość długości tekstu w bitach zaczynasz wpisywać dopiero na 448 pozycji (patrz opis algorytmu) - czyli dopiero dla elementu [14] Twojej tablicy:

[14] => 00001010 00000000 00000000 00000000

Dla czytelności dodałem spacje.

Algorytm ten (jak i inne) działają na znakach 8-bitowych (czyli bajtach) - jeśli masz znaki spoza tego zakresu (np. Unicode lub UTF-8), to traktujesz je jako ciąg kolejnych bajtów i tak kodujesz. Potem, przy dekodowaniu (nie dla tego algorytmu akurat, bo ten jest jednokierunkowy), robisz analogicznie - składasz z kolejnych bajtów właściwe znaki.

hoobert · 14 Czerwiec 2013 15:34

Musiałem odkopać ten temat bo mam jeszcze jedno pytanie. Powiedzmy, że kilka rzeczy wygląda trochę inaczej a dosyć fajnie przebieg procesu tworzenia skrótu przez algorytm md5 (i nie tylko), obrazuje program CrypTool w wersji 2.

Ale do rzeczy,

Funkcja F, opisana jest wzorem:

F(X,Y,Z) = XY v not(X) Z

Czyli funkcja F dla wartości

B = (dec) 4023233417 = (bin) 11101111110011011010101110001001

C = (dec) 2562383102 = (bin) 10011000101110101101110011111110

D = (dec) 271733878 = (bin) 10000001100100101010001110110

F(B,C,D) = (B AND C) OR (NOT(X) AND Z) = (dec) 271733878 = (bin) 10001000100010001000100010001000

następnie wykonywana jest suma logiczna A + F:

A = 01100111010001010010001100000001 OR

F = 10001000100010001000100010001000

____________________________________

11101111110011011010101110001001

następnie jest wykonywana suma logiczna ze stałą zależną od okresu, w tym wypadku z liczbą (dec) 3614090360 ((bin) 11010111011010101010010001111000), więc:

11101111110011011010101110001001 OR

11010111011010101010010001111000

___________________________________

11111111111011111010111111111001

następnie następuje przesunięcie bitowe tej liczby o 7 pozycji w lewo, czyli

1111011111010111111111001 0000000

i na końcu ta liczba jest sumowana binarnie z wartością rejestru B

11110111110101111111110010000000 OR

11101111110011011010101110001001

___________________________________

11111111110111111111111110001001 (dec) 4292870025

I pytanie co tu mogę robić źle bo nijak wynik nie jest zgodny z tym co zostaje na końcu przypisane do rejestru A, czyli 1439733669.

Czy ktoś mógłby zerknąć i zobaczyć w czym tu jest błąd?

Z góry dzięki.

Pablo_Wawa · 14 Czerwiec 2013 16:11

Cytując opis algorytmu md5 z Wikipedii:

Już pewnie widzisz, na czym polega błąd - Ty przesuwasz te bity w lewo, ale nie cyklicznie, tylko normalnie, uzupełniając je z prawej zerami. Czyli zamiast

11110111110101111111110010000000

powinieneś uzyskać

1111011111010111111111001 1111111

A tak w ogóle to ten CrypTool fajnie to prezentuje.

– Dodane 14.06.2013 (Pt) 18:34 –

Poza tym wydaje mi się, że źle policzyłeś wartość funkcji F - być może powodem tego jest nieuzupełnienie liczby do 32-bitów na początku zerami.

Moje obliczenia (ręczne, więc mogłem się walnąć - sprawdź):

1 2 3 32 bity - pozycja dziesiątek

01234567890123456789012345678901 pozycja jedności

01100111010001010010001100000001 A

11101111110011011010101110001001 B

10011000101110101101110011111110 C

00010000001100100101010001110110 D


11101111110011011010101110001001 B

10011000101110101101110011111110 C

10001000100010001000100010001000 B & C


00010000001100100101010001110110 !B

00010000001100100101010001110110 D

00010000001100100101010001110110 !B & D


10001000100010001000100010001000 B & C

00010000001100100101010001110110 !B & D

10011000101110101101110011111110 F = B & C | !B & D

I “zjadłeś” (pominąłeś) jeden krok - po sumie F + A trzeba teraz dodać wartość pierwszego bloku danych (32-bitowego), tutaj wynoszącego 1633771873 (61 61 61 61 hex), a dopiero potem dodajesz stałą AC (przy dodawaniu nie ma znaczenia ta kolejność - piszę tylko trzymając się algorytmu). I kolejna uwaga: suma bitowa (np. dla F + A) to nie jest OR i nie liczy się jej tak jak przy F! Przykład:

1100 OR 1010 = 1110

1100 + 1010 = (1)0110

hoobert · 14 Czerwiec 2013 19:38

Pablo_Wawa, po raz kolejny dzięki za odpowiedź w tym temacie.

Mam jednak wątpliwości co do tego dodawania, w sumie może to co mówisz jest logiczne, ale dodając 2 liczby 32 bitowe wynik wcale nie musi być 32 bitowy (podobnie jak w przykładzie), a na wyjściu w rejestrze B i w pozostałych trzech jest zawsze liczba 32 bitowa.

I teraz z Twoimi wskazówkami,

F = 10011000101110101101110011111110 ((dec) 2562383102)

A = 01100111010001010010001100000001 ((dec) 1732584193)

B = 11101111110011011010101110001001 ((dec) 4023233417)

C = 10011000101110101101110011111110 ((dec) 2562383102)

D = 00010000001100100101010001110110 ((dec) 271733878)

X[0] = 1100001011000010110000101100001 ((dec) 1633771873)

AC = 11010111011010101010010001111000 ((dec) 3614090360)

1 krok: F + A = 11111111111111111111111111111111 (32 bity)

2 krok: (F+A) + X[0] = 101100001011000010110000101100000 (33 bity)

3 krok: ((F+A) + X[0]) + AC = 1000111000110011000000010111011000 (34 bity)

4 krok: cykliczne przesunięcie o 7 bitów: 000110011000000010111011000 1111111 (34 bity)

5 krok: (((F+A) + X[0]) + AC <<< 7) + B = 101010101110100001001100000001000 ((dec) 5734701064) (33 bity)

I znów ten wynik nie jest taki jak powinien.

Jakieś sugestie?

Pablo_Wawa · 14 Czerwiec 2013 20:17

A czy wiesz co oznacza po polsku stwierdzenie: "“Unsigned integer addition discarding carry bit”?

Dodając liczby 32-bitowe operujemy tutaj tylko w tym zakresie, a nadmiar pomijamy (ignorujemy/opuszczamy bity powyżej 32, czyli te z lewej, bo tutaj wypisujemy liczby 32-bitowe od lewej zaczynając od najstarszego bitu, a najmłodszy jest pierwszym z prawej).

hoobert · 14 Czerwiec 2013 22:15

Masz rację, to dużo wyjaśnia, w sumie wynik jest prawie dobry. Prawie bo mam niewielkie różnice w postaci dziesiętnej.

Po kolei:

F + A = 11111111111111111111111111111111
(1) + X[0] = (1) 01100001011000010110000101100000
(2) + AC = (1) 00111000110011000000010111011000
(3) <<< 7 = 01100110000000101110110001111111
(4) + B = 01010101110100001001100000001000 ((dec) 1439733768)

CrypTool ma w tym rejestrze wartość 1439733669, czyli o 99 mniej.

Wybacz, że tak męczę, ale czy mógłbyś zerknąć co tu jeszcze może być nie tak?

Pablo_Wawa · 15 Czerwiec 2013 09:02

Źle masz w kroku 4. - jak przeniosłeś 7 lewych skrajnych bitów liczby (3) na prawą stronę, że Ci inaczej wyszło niż powinno?

0011100 0110011000000010111011000 => 0110011000000010111011000 0011100

Nie rozumiem skąd u Ciebie się te 1111111 wzięły na końcu z prawej strony?

hoobert · 15 Czerwiec 2013 09:24

Pablo_Wawa, jeszcze raz wielkie dzięki. Już jest wszystko jasne.

Pozdrawiam.