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, [e-mail]
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.
adania nad MD5 prowadziło czterech lną MD5, możemy je zamienić  w ten sposób
chińskich naukowców: Xiaoyun Wang, robimy świetny interes (pomijając aspekt mo-
BDengguo Feng, Xueija Lai i Hongbo Yu. ralny przedsięwzięcia  oczywiście szczerze
Wyniki swoich analiz zaprezentowali na konfe- odradzamy takie postępowanie). Kupiec mu-
rencji CRYPTO we wrześniu 2004 r. Ich wywód si zapłacić 100,000 euro, potwierdził przecież
wyglądał niewiarygodnie, więc z początku nikt umowę własnym podpisem cyfrowym.
nie potraktował go poważnie. Jednak póz
niej Oto inny przykład  pracujemy w wielkiej fir-
kilku innych autorów zaprezentowało własne mie informatycznej (na przykład jak ta z Red-
dokonania  potwierdziły one rewelacje zawar- mond, USA), w dziale programistycznym. Uwa-
te w publikacji Chińczyków. żamy, że pracodawca płaci nam zbyt mało,
chcemy więc dokonać krwawej cyfrowej ze-
Scenariusze ataków msty. Tworzymy plik z programem, nad którym
Wyobraz
my sobie, że chcemy sprzedać w In- właśnie pracujemy (nazwijmy to archiwum da-
ternecie coś bardzo cennego. Cena tego przed- taG.file). Następnie tworzymy jeszcze jeden plik
miotu będzie wysoka, chcemy więc zawrzeć (o nazwie dataD.file), tym razem z niebezpiecz-
umowę kupna-sprzedaży. Znajdujemy kupca, nymi danymi w rodzaju trojana lub backdoora.
uzgadniamy cenę i przygotowujemy kontrakt Wysyłamy niewinny plik dataG.file do działu zaj-
(plik PDF z umową opiewającą na 1,000 euro).
Jeśli bylibyśmy w stanie stworzyć dwa pliki z ta-
Z artykułu dowiesz się...
ką samą sumą kontrolną MD5 i różną zawarto-
ścią (na przykład z ceną w wysokości 100,000
" jak działa jednokierunkowa funkcja skrótu MD5,
euro), możemy oszukać kupującego.
" jak można przeprowadzić ataki na funkcję
Wysyłamy więc kontrakt na kwotę 1,000 eu-
MD5.
ro kupcowi  ten akceptuje go, potwierdza swo-
Powinieneś wiedzieć...
im podpisem elektronicznym (na przykład przy
użyciu gpg) i odsyła z powrotem. Dzięki temu, " powinieneś znać język programowania C++.
że mamy dwie umowy z tą samą sumą kontro-
2 www.hakin9.org hakin9 Nr 1/2005
Atak
Zagrożenia związane z MD5
mującego się kontrolą binariów, który
sprawdzi program i dane oraz stwo-
Jak działa MD5
rzy dla nich sumy kontrolne i sygna-
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- tury MD5. Program zostaje umiesz-
ściowe i powinien być generowany w taki sposób, by istniało jak najmniejsze prawdo- czony na serwerze FTP. Teraz mo-
podobieństwo, że dwie różne wiadomości będą miały taką samą wartość hash. Jeśli
żemy zastąpić plik dataG.file szkodli-
dwie różne wiadomości dają taki sam message digest, mówi się, że nastąpiła kolizja.
wym plikiem dataD.file  sumy kontro-
Oczywiście należy unikać takich sytuacji  sprawiają, że stosowanie funkcji skrótu (ha-
lne MD5 będą identyczne. Jeśli nawet
szujących) staje się bezużyteczne. Funkcja haszująca uniemożliwiająca odzyskanie
ktoś w przyszłości zwróci uwagę na
oryginalnych danych z hasha zwana jest jednokierunkową funkcją skrótu.
złośliwą zawartość, winny będzie wy-
Taką właśnie funkcją jest MD5, stworzona na uniwersytecie MIT (Massachusetts
łącznie dział kontroli plików.
Institute of Technology) przez Ronalda Rivesta. Generuje ona skrót wiadomości o dłu-
Kolejny scenariusz: piszemy pro-
gości 128 bitów i jest powszechnie używana do sprawdzania integralności danych. Spe-
stą lecz wciągającą grę lub poży-
cyfikacja funkcji MD5 znajduje się w dokumencie RFC 1321 (patrz Ramka W Sieci).
teczny program. Umieszczamy na-
Krok pierwszy: przygotowanie danych (padding)
sze dzieło (umownie dataG.file) i kil-
MD5 zawsze używa danych o całkowitej długości równej wielokrotności 512 bitów.
ka innych plików na stronie WWW.
W celu uzyskania tekstu o wymaganej długości, przygotowuje się go w następujący
Następnie ktoś, kto pobierze nasz
sposób:
program rozpakowuje archiwum i in-
staluje binaria. Ponieważ jednak jest
" 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, przytomnym użytkownikiem kompu-
" brakujące 64 bity są wykorzystywane do przechowywania długości oryginalnej
tera, tworzy sumy kontrolne tych pli-
wiadomości  gdyby wiadomość miała nieprawdopodobną długość 2^64 bitów
ków (przy użyciu Tripwire lub innego
(czyli 2097152 terabajtów), dodawane są tylko ostatnie 64 bity.
narzędzia korzystającego z MD5). Ale
jeśli uzyskamy (niezależnie od meto-
Kroki te wykonywane są zawsze, nawet gdy wiadomość ma już wymaganą długość
dy) dostęp do jego maszyny, możemy
(wielokrotność 512 bitów).
zamienić dataG.file na nasz spreparo-
Krok drugi: kalkulacja
wany plik dataD.file. System wykry-
Następnie tworzony jest hash, uzyskiwany przez wielokrotną modyfikację 128-bitowej
wania zmian nie zarejestruje modyfi-
wartości opisującej stan. Aby ułatwić zrozumienie tego procesu, na Rysunku 1 przed-
kacji  pliki mają taką samą sumę kon-
stawiono schemat algorytmu.
trolną, a my mamy idealny backdoor
Dla celów obliczeniowych 128-bitowy stan jest dzielony na cztery 32-bitowe frag-
ukryty w komputerze ofiary.
menty (bloki)  nazwijmy je A, B, C i D. Na początku działania algorytmu wartości wy-
Brzmi to niewiarygodnie? Przy-
noszą:
najmniej obecnie takie ataki są niere-
" A = 0x67452301, alne  chińscy badacze pod kierun-
" B = 0xefcdab89,
kiem Wanga nie opublikowali dotąd
" C = 0x98badcfe,
kompletnego algorytmu umożliwiają-
" D = 0x10325476.
cego odnalezienie collision key (klu-
cza kolizji) dla dowolnej wiadomości.
Początkowy stan jest następnie modyfikowany poprzez przetworzenie każdego bloku
Musimy więc ograniczyć nasze roz-
danych wejściowych w odpowiedniej kolejności.
ważania do stosunkowo prostych
Przetwarzanie każdego z wejściowych bloków danych dokonywane jest w czte-
przykładów; możemy jednak poka-
rech fazach. Każda faza, zwana też rundą, składa się z 16 operacji, co daje 64 opera-
zać, jak można tę wiedzę wykorzy-
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: stać obecnie i co będzie można osią-
gnąć, jeśli mechanizm generowania
" F(X,Y,Z) = (X AND Y) OR (NOT(X) AND Z),
kolidujących bloków z dowolnych
" G(X,Y,Z) = (X AND Z) OR (Y AND NOT(Z)),
wiadomości zostanie opublikowany.
" H(X,Y,Z) = X XOR Y XOR Z,
Nasze ograniczenia wynikają z fak-
" I(X,Y,Z) = Y XOR (X OR NOT(Z)).
tu, że nie jesteśmy w stanie stworzyć
Każda z nich pobiera trzy 32-bitowe porcje danych i przetwarza je w pojedynczą 32-bi- par collision key w rozsądnym cza-
tową wartość. W każdej rundzie, przy użyciu tych funkcji, obliczane są nowe tymczaso- sie. Skorzystamy więc z gotowych
we zmienne stanu (A, B, C i D). Poza początkowymi danymi wejściowymi, do obliczenia
1024-bitowych wiadomości zapre-
wartości hash używane są dane z tablicy zawierającej całkowite części 4294967296 *
zentowanych w tekście Wanga.
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.
Atak na cyfrowy
Po powtórzeniu operacji na wszystkich blokach wejściowych otrzymujemy hash
podpis
w postaci 128-bitowej wartości opisującej stan.
Rozpocznijmy od przykładu z dwo-
ma różnymi kontraktami (przykład
hakin9 Nr 1/2005 www.hakin9.org
3
oparty na tekście Ondreja Mikle
z Uniwersytetu w Pradze).
podział 512-bitowej
dane
Potrzebne będą następujące pliki
porcji danych na 16
wejściowe
32-bitowych ci gów
(zamieszczone na hakin9.live):
" plik wykonywalny create-package,
" plik wykonywalny self-extract,
A B C D
" dwa różne pliki zawierające kon-
trakty w PDF (contract1.pdf, con-
inicjalizacja tymczasowych tract2.pdf).
stanów dla każdej porcji danych
Pliki z archiwum na hakin9.live mogą
być skompilowane przy użyciu dołą-
czonego Makefile (platformy unikso-
a b c d
we). Użytkownicy platformy Micro-
soft Windows mogą skorzystać z go-
+
towych binariów.
ci g z danymi +
Plik wykonywalny create-packa-
(X AND Y) OR
(NOT(X) AND Z)
+ ge (patrz Listing 1) tworzy z dwóch
dane z tablicy
zadanych plików (contract1.pdf, con-
rotate left
tract2.pdf) dwa nowe pliki z dodatko-
+
wymi informacjami  każdy z nich za-
wiera oba podane pliki. Składnia po-
a b c d
lecenia jest następująca:
+
$ ./create-package contract.pdf \
ci g z danymi +
(X AND Z) OR
contract1.pdf contract2.pdf
(Y AND NOT (Z))
+
dane z tablicy
rotate left 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-
a b c d
cą programu self-extract, uzyskamy
plik o nazwie contract.pdf.
+
Rysunek 2 pokazuje rozmiesz-
ci g z danymi +
X XOR Y XOR Z czenie danych w plikach data1.pak
+
dane z tablicy
i data2.pak.
rotate left
Bloki w specjalnej wiadomości
+ (special message) oznaczone kolora-
mi zielonym i czerwonym to tak zwa-
a b c d
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
ci g z danymi +
Y XOR
do dokumentów chińskich naukow-
(X OR NOT (Z))
+
dane z tablicy
ców. Pozostałe dane w plikach da-
rotate left
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
A B C D
 niezależnie od dodatkowej zawar-
tości plików .pak.
W naszym przykładzie stworzy-
Rysunek 1. Schemat działania algorytmu MD5
my dwa różne katalogi (contract1Dir
4 www.hakin9.org hakin9 Nr 1/2005
Atak
Zagrożenia związane z MD5
poprawne archiwum poprawne archiwum
rozmiar dane
data1.pak z plikiem contract1.pdf data2.pak z plikiem contract2.pdf
w bajtach


128 bajtów: specjalna wiadomość







1 bajt: długość nazwy pliku


X bajtów: nazwa pliku do
rozpakowania

4 bajty: rozmiar pliku 1
rozmiar pliku 2
4 bajty:

rozmiar pliku 1 dane z pliku 1

rozmiar pliku 2
dane z pliku 2
Rysunek 2. Rozmieszczenie danych w plikach data.pak
i contract2Dir). Następnie umieścimy pliku data.pak. Odczytuje bit decyzyjny wypakowania w pliku data.pak  de-
plik data1.pak w katalogu contrac- (decision-bit) z pozycji zdefiniowanej cyzja jest oparta o bit decyzyjny. Dane
t1Dir, zaś plik data2.pak  w katalogu przez MD5 _ COLLISION _ OFFSET i maskuje z określonej pozycji są wypakowywane
contract2Dir. Kolejnym krokiem bę- go przy użyciu maski MD5 _ COLLISION _ do pliku o nazwie określonej wcześniej.
dzie zmiana nazw obu plików na da- BITMASK. Następnie odczytuje długość Jak widać na Rysunku 4, zaczyna-
ta.pak. Należy też do obu katalogów nazwy pliku do rozpakowania (w na- my od stworzenia plików data.pak za-
skopiować plik self-extract. szym przypadku: 0x0C -> 12d). Wresz- wierających różne kontrakty (contrac-
Zawartość katalogów powinna cie odczytuje nazwę pliku (contract.pdf) t1.pdf i contract2.pdf). Kupujący otrzy-
wyglądać następująco: oraz długość pierwszego i drugiego ma archiwum data.pak i plik wykony-
pliku. Te informacje wystarczą do ob- walny self-extract. Wypakuje plik con-
" contractDir1: self-extract i data.pak, liczenia absolutnej pozycji danych do tract.pdf (pierwotnie contract1.pdf) z
" contractDir2: self-extract i da-
ta.pak.
Listing 1. Kod z
ródłowy programu create-package
#include
Po uruchomieniu self-extract w każ-
#include
dym z katalogów program  na
#include
podstawie jednego ze znajdują-
#include
cych się w kolidujących blokach
#include
bitów  sam zdecyduje, który plik #include
//dwa kolidujace 1024-bitowe bloki
z data.pak rozpakować. Ten bit jest
#include "collision.h"
zdefiniowany w kodzie z
ródłowym
#define COLLISION_BLOCK_SIZE (1024/8)
następująco:
#define TABLE_SIZE (sizeof(FileSizes))
using namespace std;
/* Offset kolidujacego bitu */ uint32_t FileSizes[2], FileSizesNetFormat[2];
uint32_t getfilesize(ifstream &infile) {
/* w pliku z danymi */
uint32_t fsize;
#define MD5_COLLISION_OFFSET 19
infile.seekg(0, ios::end);
/* Maska bitowa kolidujacego bitu */
fsize = infile.tellg();
#define MD5_COLLISION_BITMASK 0x80
infile.seekg(0, ios::beg);
return fsize;
}
Sposób użycia tych plików wyjaśni-
int main(int argc, char *argv[] {
my za chwilę. Zajmijmy się najpierw
if (argc < 3) {
wypakowaniem plików z danymi z ar-
cout << "Usage: create-package outfile infile1 infile2" << endl;
chiwum data.pak (Rysunek 3).
exit(1);
Program self-extract (patrz Listing 2) }
rozpoczyna działanie od otworzenia
hakin9 Nr 1/2005 www.hakin9.org
5
" 1 (ważny jeden dzień),
Listing 1. Kod z
ródłowy programu create-package cd.
" prawdziwe nazwisko (rene
heinzl),
ifstream infile1(argv[2], ios::binary);
" adres e-mail ([e-mail]),
ifstream infile2(argv[3], ios::binary);
ofstream outfile1("data1.pak", ios::binary); " komentarz (Used for hakin9
ofstream outfile2("data2.pak", ios::binary);
demonstration of reduced
FileSizes[0] = getfilesize(infile1);
applicability of MD5).
FileSizes[1] = getfilesize(infile2);
//stworz dane do przechowania w pamieci i odczytaj oba pliki
Teraz podpisuje swoim kluczem
uint32_t datasize = FileSizes[0] + FileSizes[1];
char *data = new char [datasize]; pliki data.pak i self-extract. Robi
infile1.read(data, FileSizes[0]);
to za pomocą następujących po-
infile2.read(data+FileSizes[0], FileSizes[1]);
leceń:
//zapisz nazwe pliku do pakietu
uint8_t fnamelen = strlen(argv[1]);
$ gpg -u USERID \
//konwertuj tablice z rozmiarami plikow do formatu network-endian
FileSizesNetFormat[0] = htonl(FileSizes[0]);  -digest-algo md5 \
FileSizesNetFormat[1] = htonl(FileSizes[1]);
-ab -s data.pak
//utworz data1.pak
$ gpg -u USERID \
outfile1.write((char *)collision[0], COLLISION_BLOCK_SIZE);
- digest-algo md5 \
outfile1.write((char *)&fnamelen, 1);
-ab -s self-extract
outfile1.write(argv[1], fnamelen);
outfile1.write((char *)FileSizesNetFormat, TABLE_SIZE);
outfile1.write(data, datasize);
W efekcie w swoim katalogu otrzy-
outfile1.close();
ma takie pliki:
//utworz data2.pak
outfile2.write((char *)collision[1], COLLISION_BLOCK_SIZE);
$ ls -l
outfile2.write((char *)&fnamelen, 1);
outfile2.write(argv[1], fnamelen); -rw-r--r-- 1 test
outfile2.write((char *)FileSizesNetFormat, TABLE_SIZE);
users 3266
outfile2.write(data, datasize);
2004-12-01 00:59
outfile2.close();
data.pak
cout << "Custom colliding files created." << endl;
-rw-r----- 1 test
cout << "Files are named data1.pak and data2.pak" << endl;
cout << "Put each of them in contr1 and contr2 directory," << endl; users 392
cout << "rename each to data.pak and run self-extract
2004-12-29 14:59
to see result" << endl;
data.pak.asc
cout << endl << "Press Enter to continue" << endl;
-rwxr-x--- 1 test
char somebuffer[8];
users 6408
cin.getline(somebuffer, 8);
} 2004-12-18 19:00
self-extract
-rw-r----- 1 test
pliku data.pak i, po przeczytaniu umo- $ ls -l users 392
wy, podpisze pobrane pliki (data.pak i -rw-r--r-- 1 test 2004-12-29 15:01
self-extractor) swoim kluczem. users 3266 self-extract.asc
Gdy te pliki wrócą do nas, 2004-12-01 00:59
możemy zamienić pliki data.pak data.pak Jak widzimy, ofiara stworzyła osob-
(czyli w rzeczywistości contrac- -rwxr-x--- 1 test ne sygnatury dla każdego z plików.
t1.pdf i contract2.pdf). Ponieważ users 6408 Teraz prześle nam te pliki razem
kupujący podpisał je własnym klu- 2004-12-18 19:00 z podpisami. To odpowiedni moment
czem i mamy podpisany kontrakt na self-extract dla naszego ataku:
absurdalnie wysoką kwotę (100,000
euro), możemy przystąpić do złośli- Po wypakowaniu i przeczytaniu kon- $ gpg -v --verify \
wych działań. traktu kupujący tworzy klucz gpg data.pak.asc data.pak
W praktyce skorzystamy z linuk- (testforhakin9):
sowego gpg (GnuPG 1.2.2) Wynik będzie następujący:
i naszych plików (contract1.pdf, $ gpg  -gen-key
contract2.pdf, self-extract). Jak gpg: armor header:
pamiętamy, przesłaliśmy kupują- Wybiera następujące opcje: Version: GnuPG v1.2.2
cemu stworzone pliki (data.pak (GNU/Linux)
i self-extract), więc otrzymał on na- " 5 (RSA, tylko podpis), gpg: Signature made
stępujące binaria: " 1024  minimalna długość klucza, Wed 29 Dec 2004
6 www.hakin9.org hakin9 Nr 1/2005
Atak
Zagrożenia związane z MD5
Version: GnuPG v1.2.2
(GNU/Linux)
gpg: Signature made
otwórz plik data.pak
Wed 29 Dec 2004
02:59:46 PM CET
using RSA key ID 4621CB9C
odczytaj bit z pozycji
gpg: Good signature from
"rene heinzl (Used for hakin9
demonstration of
maskuj bit mask

"reduced applicability of MD5")
"
gpg: binary signature,
odczytaj długość pliku
odczytaj plik
digest algorithm MD5
Możemy teraz wypakować plik con-
odczytaj długość pliku 1
odczytaj długość pliku 2
tract.pdf (contract2.pdf) z pliku data.pak
 okaże się, że jest zupełnie inny niż
oblicz pozycję danych 1
oblicz pozycję danych 2
ten, który został podpisany przez kupu-
jącego. Wadą zaprezentowanej metody
jest konieczność użycia dwóch plików

indeks <- bit decyzyjny






i fakt, że ofiara musi podpisać oba pliki,








a nie sam kontrakt. Nie zmniejsza to



jednak zagrożenia, jakie niesie ze sobą



zaprezentowana metoda.



W branży kontroli cyfrowych tre-



+ pozycja danych 1 + pozycja danych 2
ści (Digital Rights Management,
DRM) zawsze stosowana jest któraś
z funkcji haszujących, nawet jeśli nie
zapisz contract.pdf
służy bezpośrednio do uzyskiwania
message digest plików. Komercyjni
producenci używają zwykle trzech
najważniejszych algorytmów  RSA,
Rysunek 3. Dekompresja jednego pliku z archiwum data.pak
DSA i ElGamal (są to asymetryczne
02:59:46 PM CET Jeśli zastąpimy odebrany plik data.pak metody szyfrowania). Ponieważ jed-
using RSA key ID 4621CB9C (contract1.pdf) naszą własną, sprepa- nak techniki te są powolne, w świecie
gpg: Good signature from rowaną wersją data.pak (contract2.pdf) DRM używa się ich raczej do podpi-
"rene heinzl (Used for hakin9 i spróbujemy zweryfikować dane, wynik sywania sum hash, nie zaś samych
demonstration of będzie identyczny z poprzednim: plików. W związku z tym użycie za-
"reduced applicability of MD5") prezentowanej metody do nadużyć
" $ gpg -v --verify \ (preparowanie podpisów dla plików,
gpg: binary signature, data.pak.asc data.pak niezależnie od ich wielkości)  bio-
digest algorithm MD5 gpg: armor header: rąc pod uwagę dużą wydajność MD5
 jest całkiem realne.
Wspomniana technika jest uży-
Listing 2. Kod z
ródłowy programu self-extract
wana na codzień przez Microsoft
#include
Authenticode, choćby w przeglą-
#include
darce Internet Explorer. Jej zada-
#include
niem jest ograniczenie wykonywal-
#include
#include nej zawartości stron internetowych
#include
tylko do podpisanych cyfrowo bina-
using namespace std;
riów. Wobec faktu, że technika Mi-
#define MD5_COLLISION_OFFSET 19
crosoftu wykorzystuje (a przynajm-
#define MD5_COLLISION_BITMASK 0x80
niej umożliwia wykorzystanie) MD5,
#define SUBHEADER_START (1024/8)
#define TABLE_SIZE (sizeof(FileSizes)) zastosowanie opisanej metody ata-
uint32_t FileSizes[2];
ku do podmiany niewinnej zawarto-
uint32_t FilePos[2];
ści na szkodliwą byłoby wręcz try-
wialne.
hakin9 Nr 1/2005 www.hakin9.org
7
wartość archiwów może być zupeł-
Listing 2. Kod z
ródłowy programu self-extract, cd.
nie różna.
Przyjrzyjmy się szczegółom. Przy-
int main(int argc, char *argv[]) {
gotowaliśmy do potrzeb symulacji dwa
ifstream packedfile("data.pak", ios::binary);
uint8_t colliding_byte, fnamelen; proste narzędzia (runprog, make-da-
//znajdz i odczytaj bajt, w ktorym nastepuje kolizja MD5
ta-packages). Najpierw, przy użyciu
packedfile.seekg(MD5_COLLISION_OFFSET, ios::beg);
make-data-packages (patrz Listing 3),
packedfile.read((char *)&colliding_byte, 1);
stworzymy nasze dwa odmienne ar-
//zaladuj nazwe pliku
chiwa (dataG.file to skrót od data-Ge-
packedfile.seekg(SUBHEADER_START, ios::beg);
packedfile.read((char *)&fnamelen, 1); neral-file, a dataD.file jest skrótem od
char *filename = new char[fnamelen+1];
data-Dangerous-file):
packedfile.read(filename, fnamelen);
filename[fnamelen] = 0; //zakonczenie ciagu
$ ./make-data-packages
//zaladuj tablice plikow
packedfile.read((char *)FileSizes, TABLE_SIZE);
//konwertuj tablice z formatu sieciowego do formatu hosta Jeśli nie podamy nazw plików, do-
//zadziala na platformach little-endian i big-endian
myślnie program użyje nazw da-
for (int i=0; i<2; i++) FileSizes[i] = ntohl(FileSizes[i]);
taG.file i dataD.file. Plik data.G.file
//aktualizacja pozycji plikow w archiwum
zostanie razem z programem run-
FilePos[0] = SUBHEADER_START + 1 + fnamelen + TABLE_SIZE;
prog (patrz Listing 4) umieszczony
FilePos[1] = FilePos[0] + FileSizes[0];
unsigned int fileindex = (colliding_byte & MD5_COLLISION_BITMASK) ? 1 : 0; na serwerze WWW. Jeśli ktoś ścią-
//odczytaj i wypakuj plik
gnie te dwa pliki, wszystko będzie
uint32_t extrsize = FileSizes[fileindex];
wyglądać niewinnie.
uint32_t extrpos = FilePos[fileindex];
Pamiętajmy, że kod użyty w tym
char *extractbuf = new char[extrsize];
przykładzie po deasemblacji będzie
packedfile.seekg(extrpos, ios::beg);
packedfile.read(extractbuf, extrsize); wyglądał podejrzanie  jego złośliwe
packedfile.close();
działanie jest jednoznaczne i łatwe
ofstream outfile(filename, ios::binary);
do zauważenia; można sobie wy-
outfile.write(extractbuf, extrsize);
obrazić konsekwencje naszych dzia-
outfile.close();
łań, jeśli zostaniemy rozszyfrowani.
cout << "File " << filename << " extracted. Press Enter to continue."
<< endl; Ale celem tego artykułu nie jest opis
char somebuffer[8];
ukrywania tylnych furtek w systemie
cin.getline(somebuffer, 8);
(patrz poprzednie numery hakin9u),
return(0);
lecz przedstawienie efektów słabo-
}
ści algorytmu MD5.
Tak wygląda zawartość katalo-
rzędziem typu Tripwire, ale dostoso- gu użytkownika po pobraniu plików
Atak na integralność
wanie tego scenariusza do kompro- z serwera:
danych
mitacji plików na serwerze WWW
Jak mogliśmy się przekonać, wy- czy FTP jest prawie banalne. $ ls -la
korzystując kolizje możemy stwo- Jak dokonamy symulacji ataku? -rw-r----- 1 test
rzyć dwa zupełnie różne kontrak- Użyjemy pliku wykonywalnego i, po- users 128
ty i bez ryzyka podsunąć jeden dobnie jak poprzednio, dwóch róż- 2004-12-29 14:05
z nich ofierze. Przyjrzyjmy się te- nych archiwów data.pak (dataG.fi- dataG.file
raz wykorzystaniu ataku na MD5 le, dataD.file)  zawartość tych pli- -rwxr-x--- 1 test
do kompromitacji systemów siecio- ków to jedynie dane z dokumentów users 11888
wych służących do publikacji opro- chińskich naukowców, więc ich su- 2004-12-29 14:04
gramowania zabezpieczonego ha- my kontrolne MD5 będą identycz- runprog
shami MD5 oraz tych chronionych ne. Następnie umieścimy plik wy-
przez narzędzia sprawdzające inte- konywalny i niewinne dataG.file na Oto efekt działania programu run-
gralność plików. Do takich narzędzi serwerze. Jeśli użytkownik pobie- prog na pliku dataG.file:
należy na przykład Tripwire, tworzą- rze i rozpakuje te pliki, wszystko bę-
cy sumy kontrolne wszystkich waż- dzie wyglądało zwyczajnie. Ale gdy- $./runprog dataG.file
nych plików i wykrywający ich zmia- by udało nam się zdobyć dostęp do way one
ny (patrz Artykuł Tripwire  wykry- jego komputera i zastąpić dataG.file here the program is
wacz odmieńców, hakin9 3/2004). plikiem dataD.file, program Tripwi- currently okay.. no
Dla lepszego zrozumienia omówimy re ciągle nie odnotuje różnic  su- malicious routines
jedynie atak na system chroniony na- my MD5 będą takie same, choć za- will be started
8 www.hakin9.org hakin9 Nr 1/2005
Atak
Zagrożenia związane z MD5
a4c0d35c95a63a80ż
utwórz archiwa data.pak
5915367dcfe6b751
z plikami contract1.pdf i contract2.pdf
dataG.file
poprawny data.pak
56fa8b2c22ab43f0ż
poprawny data.pak
z plikiem contract1.pdf
z plikiem contract1.pdf c9c937b0911329b6
runprog
poprawny data.pak poprawny data.pak
z plikiem z plikiem
MD5 = MD5
W rzeczywistości jednak oba pliki
contract1.pdf contract1.pdf
się różnią:
poprawny data.pak $ diff -q dataD.file dataG.file
z plikiem
Files dataD.file
contract1.pdf
and dataG.file differ
podpis
A teraz zastąpmy dataG.file plikiem
odesłanie
dataD.file:
$ mv dataD.file dataG.file
poprawny data.pak
poprawny data.pak
z plikiem
MD5 = MD5
z plikiem
contract1.pdf
Sprawdz
my sumy MD5:
contract1.pdf
podpis
zamiana plików PDF
$ for i in `ls`; \
do md5sum $i; done
plik data.pak z plikiem a4c0d35c95a63a80ż
plik rozpakowuj cy
contract2.pdf podpisany
archiwum
5915367dcfe6b751
podpis dataG.file
56fa8b2c22ab43f0ż
c9c937b0911329b6
Rysunek 4. Atak na podpis cyfrowy
runprog
Sumy MD5: $ ls -l
-rw-r----- 1 test i uruchommy runprog:
$ for i in `ls`; \ users 128
do md5sum $i; done 2004-12-29 14:09 $ ./runprog dataG.file
a4c0d35c95a63a80ż dataD.file way two
5915367dcfe6b751 -rw-r----- 1 test here the program
dataG.file users 128 is in the bad branch..
56fa8b2c22ab43f0ż 2004-12-29 14:09 malicious routines
c9c937b0911329b6 dataG.file will be started
runprog -rwxr-x--- 1 test
users 11888 Sumy MD5 się nie zmieniły, więc
Teraz, jeśli zdobędziemy dostęp do 2004-12-29 14:04 sprawdzanie (na przykład narzę-
systemu użytkownika, możemy za- runprog dziem Tripwire) integralności nie
mienić plik dataG.file szkodliwym $ for i in `ls`; \ wykryje modyfikacji  nasz pro-
plikiem dataD.file (trzeba pamiętać do md5sum $i; done gram może więc zrobić kilka na-
o zmianie nazwy). a4c0d35c95a63a80ż prawdę szkodliwych rzeczy. Może
Oto zawartość katalogu i sumy 5915367dcfe6b751 na przykład otworzyć jeden z por-
MD5 plików po zamianie plików: dataD.file tów i wysłać przez niego klucz pry-
watny użytkownika lub plik passwd
do innego komputera.
W Sieci
Gdybyśmy mieli dostęp do peł-
nego algorytmu obliczania par ko-
" http://cryptography.hyperlink.cz/2004/collisions.html  witryna Ondreja Mikle
lizji MD5, wszystkie fragmenty ko-
o kolizjach
du mogłyby się znalez
ć w jednym
" http://www.gnupg.org/  Gnu Privacy Guard,
pliku. Cała procedura ataku była-
" http://www.faqs.org/rfcs/rfc1321.html  Ronald L. Rivest, MD5 RFC,
" http://eprint.iacr.org/2004/199  kolizje funkcji haszujących MD4, MD5, HAVAL- by wtedy o wiele mniej podejrzana
128 and RIPEMD. niż metoda korzystająca z dwóch
plików.
hakin9 Nr 1/2005 www.hakin9.org
9
Atak brute force
Listing 3. Kod z
ródłowy programu make-data-packages
Atak typu brute force na algoryt-
my haszujące (MD5, SHA-1 i inne)
#include
polega po prostu na wyszukiwa-
#include
niu wszystkich możliwych kombina-
//dwa kolidujace bloki 1024-bitowe, plik autorstwa Ondreja Mikle
cji par danych wejściowych w celu
#include "collision.h"
uzyskania identycznej message di-
#define COLLISION_BLOCK_SIZE (1024/8)
gest. Generalnie algorytm haszujący
using namespace std;
jest uznawany za bezpieczny wtedy,
int main(int argc, char *argv[]) {
gdy nie ma innego poza brute force string filename1("dataG.file"), filename2("dataD.file");
if (argc < 3) {
sposobu stworzenia danych wejścio-
cout << "Using default names for data files" << endl;
wych o żądanej wartości hash.
cout << "filename1: " << filename1 << endl;
Atak brute force na MD5 jest skraj-
cout << "filename2: " << filename2 << endl;
nie niewydajny. Uzyskanie dwóch
} else {
wiadomości o tej samej wartości filename1 = argv[1];
filename2 = argv[2];
hash wymaga przeprowadzenia 2^64
cout << "Creating the files with the following filenames:" << endl;
(=1.844674407e+19) operacji haszo-
cout << "filename1: " << filename1 << endl;
wania. Dostępny obecnie przeciętny
cout << "filename2: " << filename2 << endl;
komputer dokonałby tego w pół wieku,
}
więc ciężko to uznać za realistyczny ofstream outfile1(filename1.c_str(), ios::binary);
ofstream outfile2(filename2.c_str(), ios::binary);
scenariusz. Jednak ostatnio opubli-
// stworz plik o nazwie filename1
kowane dokumenty udowadniają, że
outfile1.write((char *)collision[0], COLLISION_BLOCK_SIZE);
za pomocą zaawansowanych ope-
outfile1.close();
racji matematycznych możliwe jest
// stworz plik o nazwie filename2
zmniejszenie tego wysiłku do około outfile2.write((char *)collision[1], COLLISION_BLOCK_SIZE);
outfile2.close();
2^42 (=4.398046511e+12) operacji
}
haszowania. To zmniejszenie wyma-
ganych działań skraca czas obliczeń
do niecałej doby.
Stworzenie wiadomości o za-
Listing 4. Kod z
ródłowy programu runprog
danym hashu wymaga 2^128
#include
(=3.402823669e+38) operacji i jest
#include
niewykonalne nawet w ciągu miliar-
#include
dów lat. Jak dotąd nie odkryto żad-
using namespace std;
nego sposobu skrócenia tego cza-
/* Offset kolidujacego bajtu w pliku z danymi*/
su  zaprezentowane techniki wyko- #define MD5_COLLISION_OFFSET 19
/* Maska kolidujacego bitu*/
rzystywania słabości MD5 nie doty-
#define MD5_COLLISION_BITMASK 0x80
czą więc tego rodzaju ataków na al-
int main(int argc, char *argv[]) {
gorytm MD5.
if (argc < 2) {
cout << "Please specifiy the used filename .. " << endl;
Ufać znaczy
return(-1);
}
kontrolować
ifstream packedfile(argv[1], ios::binary);
Opublikowane przykłady kolizji nie sta-
uint8_t colliding_byte;
nowią dużego zagrożenia, ale wskazu-
//znajdz i odczytaj bajt, w ktorym nastepuje kolizja MD5
ją na pewne słabości algorytmu MD5.
packedfile.seekg(MD5_COLLISION_OFFSET, ios::beg);
Należy pamiętać, że w przeszłości packedfile.read((char *)&colliding_byte, 1);
if ( colliding_byte & MD5_COLLISION_BITMASK) {
podobne odkrycia prowadziły do
cout << "way one " << endl;
ujawnienia bardzo poważnych dziur.
cout << "here the program is currently okay..
W wielu zastosowaniach należy
no malicious routines will be started " << endl;
rozważyć migrację do innych funkcji
} else {
haszujących  zaprezentowane sła- cout << "way two " << endl;
cout << "here the program is in the bad branch..
bości już przecież otwierają drogę
malicious routines will be started " << endl;
do nadużyć i podważają zaufanie
}
do MD5. Zaś w cyfrowym świecie,
return(0);
gdzie praktycznie brakuje gwarancji
}
bezpieczeństwa danych, zaufanie jest
najważniejsze. n
10 www.hakin9.org hakin9 Nr 1/2005
Atak