odkryte niedawno przez chińskich naukowców słabości w algorytmie MD5.pdf

Zagrożenia związane

ze stosowaniem algorytmu MD5

Philipp Schwaha, Rene Heinzl

Artykuł opublikowany w numerze 1/2005 magazynu hakin9

Wszelkie prawa zastrzeżone. Bezpłatne kopiowanie i rozpowszechnianie artykułu dozwolone

pod warunkiem zachowania jego obecnej formy i treści.

Magazyn hakin9 , Wydawnictwo Software, ul. Lewartowskiego 6, 00-190 Warszawa, hakin9@hakin9.org

Zagrożenia związane ze

stosowaniem algorytmu MD5

Philipp Schwaha, Rene Heinzl

MD5 jest zapewne

najpopularniejszą obecnie

funkcją skrótu – jej zastosowania

sięgają od prostych sum

kontrolnych plików do DRM

(Digital Rights Management).

Choć odkrycie poważnej

luki w bezpieczeństwie MD5

wydawało się nierealne, została

ona znaleziona przez chińskich

naukowców.

chińskich naukowców: Xiaoyun Wang,

Dengguo Feng, Xueija Lai i Hongbo Yu.

Wyniki swoich analiz zaprezentowali na konfe-

rencji CRYPTO we wrześniu 2004 r. Ich wywód

wyglądał niewiarygodnie, więc z początku nikt

nie potraktował go poważnie. Jednak później

kilku innych autorów zaprezentowało własne

dokonania – potwierdziły one rewelacje zawar-

te w publikacji Chińczyków.

lną MD5, możemy je zamienić – w ten sposób

robimy świetny interes (pomijając aspekt mo-

ralny przedsięwzięcia – oczywiście szczerze

odradzamy takie postępowanie). Kupiec mu-

si zapłacić 100,000 euro, potwierdził przecież

umowę własnym podpisem cyfrowym.

Oto inny przykład – pracujemy w wielkiej ir-

mie informatycznej (na przykład jak ta z Red-

mond, USA), w dziale programistycznym. Uwa-

żamy, że pracodawca płaci nam zbyt mało,

chcemy więc dokonać krwawej cyfrowej ze-

msty. Tworzymy plik z programem, nad którym

właśnie pracujemy (nazwijmy to archiwum da-

taG.ile ). Następnie tworzymy jeszcze jeden plik

(o nazwie dataD.ile ), tym razem z niebezpiecz-

nymi danymi w rodzaju trojana lub backdoora.

Wysyłamy niewinny plik dataG.ile do działu zaj-

Scenariusze ataków

Wyobraźmy sobie, że chcemy sprzedać w In-

ternecie coś bardzo cennego. Cena tego przed-

miotu będzie wysoka, chcemy więc zawrzeć

umowę kupna-sprzedaży. Znajdujemy kupca,

uzgadniamy cenę i przygotowujemy kontrakt

(plik PDF z umową opiewającą na 1,000 euro).

Jeśli bylibyśmy w stanie stworzyć dwa pliki z ta-

ką samą sumą kontrolną MD5 i różną zawarto-

ścią (na przykład z ceną w wysokości 100,000

euro), możemy oszukać kupującego.

Wysyłamy więc kontrakt na kwotę 1,000 eu-

ro kupcowi – ten akceptuje go, potwierdza swo-

im podpisem elektronicznym (na przykład przy

użyciu gpg ) i odsyła z powrotem. Dzięki temu,

że mamy dwie umowy z tą samą sumą kontro-

Z artykułu dowiesz się...

• jak działa jednokierunkowa funkcja skrótu MD5,

• jak można przeprowadzić ataki na funkcję

MD5.

Powinieneś wiedzieć...

• powinieneś znać język programowania C++.

www.hakin9.org

hakin9 Nr 1/2005

B adania nad MD5 prowadziło czterech

Zagrożenia związane z MD5

Jak działa MD5

Hash (skrót), zwany też message digest (ang. streszczenie wiadomości), to liczba ge-

nerowana z danych wejściowych (na przykład tekstu). Hash jest krótszy niż dane wej-

ściowe i powinien być generowany w taki sposób, by istniało jak najmniejsze prawdo-

podobieństwo, że dwie różne wiadomości będą miały taką samą wartość hash . Jeśli

dwie różne wiadomości dają taki sam message digest , mówi się, że nastąpiła kolizja .

Oczywiście należy unikać takich sytuacji – sprawiają, że stosowanie funkcji skrótu (ha-

szujących) staje się bezużyteczne. Funkcja haszująca uniemożliwiająca odzyskanie

oryginalnych danych z hasha zwana jest jednokierunkową funkcją skrótu.

Taką właśnie funkcją jest MD5, stworzona na uniwersytecie MIT ( Massachusetts

Institute of Technology ) przez Ronalda Rivesta. Generuje ona skrót wiadomości o dłu-

gości 128 bitów i jest powszechnie używana do sprawdzania integralności danych. Spe-

cyikacja funkcji MD5 znajduje się w dokumencie RFC 1321 (patrz Ramka W Sieci ).

mującego się kontrolą binariów, który

sprawdzi program i dane oraz stwo-

rzy dla nich sumy kontrolne i sygna-

tury MD5. Program zostaje umiesz-

czony na serwerze FTP. Teraz mo-

żemy zastąpić plik dataG.ile szkodli-

wym plikiem dataD.ile – sumy kontro-

lne MD5 będą identyczne. Jeśli nawet

ktoś w przyszłości zwróci uwagę na

złośliwą zawartość, winny będzie wy-

łącznie dział kontroli plików.

Kolejny scenariusz: piszemy pro-

stą lecz wciągającą grę lub poży-

teczny program. Umieszczamy na-

sze dzieło (umownie dataG.ile ) i kil-

ka innych plików na stronie WWW.

Następnie ktoś, kto pobierze nasz

program rozpakowuje archiwum i in-

staluje binaria. Ponieważ jednak jest

przytomnym użytkownikiem kompu-

tera, tworzy sumy kontrolne tych pli-

ków (przy użyciu Tripwire lub innego

narzędzia korzystającego z MD5). Ale

jeśli uzyskamy (niezależnie od meto-

dy) dostęp do jego maszyny, możemy

zamienić dataG.ile na nasz spreparo-

wany plik dataD.ile . System wykry-

wania zmian nie zarejestruje modyi-

kacji – pliki mają taką samą sumę kon-

trolną, a my mamy idealny backdoor

ukryty w komputerze oiary.

Brzmi to niewiarygodnie? Przy-

najmniej obecnie takie ataki są niere-

alne – chińscy badacze pod kierun-

kiem Wanga nie opublikowali dotąd

kompletnego algorytmu umożliwiają-

cego odnalezienie collision key (klu-

cza kolizji) dla dowolnej wiadomości.

Musimy więc ograniczyć nasze roz-

ważania do stosunkowo prostych

przykładów; możemy jednak poka-

zać, jak można tę wiedzę wykorzy-

stać obecnie i co będzie można osią-

gnąć, jeśli mechanizm generowania

kolidujących bloków z dowolnych

wiadomości zostanie opublikowany.

Nasze ograniczenia wynikają z fak-

tu, że nie jesteśmy w stanie stworzyć

par collision key w rozsądnym cza-

sie. Skorzystamy więc z gotowych

1024-bitowych wiadomości zapre-

zentowanych w tekście Wanga.

Krok pierwszy: przygotowanie danych (padding)

MD5 zawsze używa danych o całkowitej długości równej wielokrotności 512 bitów.

W celu uzyskania tekstu o wymaganej długości, przygotowuje się go w następujący

sposób:

• do wiadomości dodawany jest pojedynczy bit o wartości 1 poprzedzony zerami

– tak, by jej długość była o 64 bity krótsza od wielokrotności 512 bitów,

• brakujące 64 bity są wykorzystywane do przechowywania długości oryginalnej

wiadomości – gdyby wiadomość miała nieprawdopodobną długość 2^64 bitów

(czyli 2097152 terabajtów), dodawane są tylko ostatnie 64 bity.

Kroki te wykonywane są zawsze, nawet gdy wiadomość ma już wymaganą długość

(wielokrotność 512 bitów).

Krok drugi: kalkulacja

Następnie tworzony jest hash , uzyskiwany przez wielokrotną modyikację 128-bitowej

wartości opisującej stan. Aby ułatwić zrozumienie tego procesu, na Rysunku 1 przed-

stawiono schemat algorytmu.

Dla celów obliczeniowych 128-bitowy stan jest dzielony na cztery 32-bitowe frag-

menty (bloki) – nazwijmy je A, B, C i D. Na początku działania algorytmu wartości wy-

noszą:

• A = 0x67452301,

• B = 0xefcdab89,

• C = 0x98badcfe,

• D = 0x10325476.

Początkowy stan jest następnie modyikowany poprzez przetworzenie każdego bloku

danych wejściowych w odpowiedniej kolejności.

Przetwarzanie każdego z wejściowych bloków danych dokonywane jest w czte-

rech fazach. Każda faza, zwana też rundą , składa się z 16 operacji, co daje 64 opera-

cje dla każdego bloku danych. 512-bitowy blok wejściowy jest dzielony na 16 ciągów

danych o długości 32 bitów. Istotą każdej z rund jest jedna z poniższych funkcji:

• F(X,Y,Z) = (X AND Y) OR (NOT(X) AND Z) ,

• G(X,Y,Z) = (X AND Z) OR (Y AND NOT(Z)) ,

• H(X,Y,Z) = X XOR Y XOR Z ,

• I(X,Y,Z) = Y XOR (X OR NOT(Z)) .

Każda z nich pobiera trzy 32-bitowe porcje danych i przetwarza je w pojedynczą 32-bi-

tową wartość. W każdej rundzie, przy użyciu tych funkcji, obliczane są nowe tymczaso-

we zmienne stanu (A, B, C i D). Poza początkowymi danymi wejściowymi, do obliczenia

wartości hash używane są dane z tablicy zawierającej całkowite części 4294967296 *

abs(sin(i)) . Wyniki każdej fazy są używane w fazie następnej przez dodanie, na końcu

danego bloku wejściowego, do poprzednich wartości A, B, C i D reprezentujących stan.

Po powtórzeniu operacji na wszystkich blokach wejściowych otrzymujemy hash

w postaci 128-bitowej wartości opisującej stan.

Atak na cyfrowy

podpis

Rozpocznijmy od przykładu z dwo-

ma różnymi kontraktami (przykład

hakin9 Nr 1/2005

www.hakin9.org

��

oparty na tekście Ondreja Mikle

z Uniwersytetu w Pradze).

Potrzebne będą następujące pliki

(zamieszczone na hakin9.live ):

�

• plik wykonywalny create-package ,

• plik wykonywalny self-extract ,

• dwa różne pliki zawierające kon-

trakty w PDF ( contract1.pdf , con-

tract2.pdf ).

��

�

Pliki z archiwum na hakin9.live mogą

być skompilowane przy użyciu dołą-

czonego Makeile (platformy unikso-

we). Użytkownicy platformy Micro-

soft Windows mogą skorzystać z go-

towych binariów.

Plik wykonywalny create-packa-

ge (patrz Listing 1) tworzy z dwóch

zadanych plików ( contract1.pdf , con-

tract2.pdf ) dwa nowe pliki z dodatko-

wymi informacjami – każdy z nich za-

wiera oba podane pliki. Składnia po-

lecenia jest następująca:

��

�

��

�

��

�

��

$ ./create-package contract.pdf \

contract1.pdf contract2.pdf

��

Program ten umieści pliki contrac-

t1.pdf i contract2.pdf w odpowied-

nich archiwach: data1.pak i da-

ta2.pak . Z każdego z nich, za pomo-

cą programu self-extract , uzyskamy

plik o nazwie contract.pdf.

Rysunek 2 pokazuje rozmiesz-

czenie danych w plikach data1.pak

i data2.pak .

Bloki w specjalnej wiadomości

( special message ) oznaczone kolora-

mi zielonym i czerwonym to tak zwa-

ne colliding blocks (kolidujące bloki)

– są różne w każdym z plików ( da-

ta1.pak i data2.pak ). Specjalne wia-

domości to binarne ciągi dołączone

do dokumentów chińskich naukow-

ców. Pozostałe dane w plikach da-

ta1.pak i data2.pak są zawsze iden-

tyczne. Podczas obliczania sum kon-

trolnych MD5 tych plików zaznaczo-

ne kolidujące bloki sprawiają, że ha-

she są identyczne. Ponieważ reszta

danych jest zawsze taka sama, w re-

zultacie hash jest zawsze taki sam

– niezależnie od dodatkowej zawar-

tości plików .pak .

W naszym przykładzie stworzy-

my dwa różne katalogi ( contract1Dir

�

��

�

��

�

��

�

��

�

Rysunek 1. Schemat działania algorytmu MD5

www.hakin9.org

hakin9 Nr 1/2005

Zagrożenia związane z MD5

��

Rysunek 2. Rozmieszczenie danych w plikach data.pak

i contract2Dir ). Następnie umieścimy

plik data1.pak w katalogu contrac-

t1Dir , zaś plik data2.pak – w katalogu

contract2Dir . Kolejnym krokiem bę-

dzie zmiana nazw obu plików na da-

ta.pak . Należy też do obu katalogów

skopiować plik self-extract .

Zawartość katalogów powinna

wyglądać następująco:

pliku data.pak . Odczytuje bit decyzyjny

( decision-bit ) z pozycji zdeiniowanej

przez MD5 _ COLLISION _ OFFSET i maskuje

go przy użyciu maski MD5 _ COLLISION _

BITMASK . Następnie odczytuje długość

nazwy pliku do rozpakowania (w na-

szym przypadku: 0x0C -> 12d ). Wresz-

cie odczytuje nazwę pliku ( contract.pdf )

oraz długość pierwszego i drugiego

pliku. Te informacje wystarczą do ob-

liczenia absolutnej pozycji danych do

wypakowania w pliku data.pak – de-

cyzja jest oparta o bit decyzyjny. Dane

z określonej pozycji są wypakowywane

do pliku o nazwie określonej wcześniej.

Jak widać na Rysunku 4, zaczyna-

my od stworzenia plików data.pak za-

wierających różne kontrakty ( contrac-

t1.pdf i contract2.pdf ). Kupujący otrzy-

ma archiwum data.pak i plik wykony-

walny self-extract . Wypakuje plik con-

tract.pdf (pierwotnie contract1.pdf ) z

• contractDir1 : self-extract i data.pak ,

• contractDir2 : self-extract i da-

ta.pak .

Listing 1. Kod źródłowy programu create-package

Po uruchomieniu self-extract w każ-

dym z katalogów program – na

podstawie jednego ze znajdują-

cych się w kolidujących blokach

bitów – sam zdecyduje, który plik

z data.pak rozpakować. Ten bit jest

zdeiniowany w kodzie źródłowym

następująco:

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <fstream>

#include <stdint.h>

#include <netinet/in.h>

//dwa kolidujace 1024-bitowe bloki

# include "collision.h"

#deine COLLISION_BLOCK_SIZE (1024/8)

#deine TABLE_SIZE (sizeof(FileSizes))

using namespace std ;

uint32_t FileSizes [ 2 ] , FileSizesNetFormat [ 2 ];

uint32_t getilesize ( ifstream & inile ) {

uint32_t fsize ;

inile . seekg ( 0 , ios :: end );

fsize = inile . tellg ();

inile . seekg ( 0 , ios :: beg );

return fsize ;

}

int main ( int argc , char * argv [] {

if ( argc < 3 ) {

cout << "Usage: create-package outile inile1 inile2" << endl ;

exit ( 1 );

}

/* Offset kolidujacego bitu */

/* w pliku z danymi */

#deine MD5_COLLISION_OFFSET 19

/* Maska bitowa kolidujacego bitu */

#deine MD5_COLLISION_BITMASK 0x80

Sposób użycia tych plików wyjaśni-

my za chwilę. Zajmijmy się najpierw

wypakowaniem plików z danymi z ar-

chiwum data.pak (Rysunek 3).

Program self-extract (patrz Listing 2)

rozpoczyna działanie od otworzenia

hakin9 Nr 1/2005

www.hakin9.org

��

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: