MD5

MD5

Опште
Пројектант(и)	Роналд Лин Ривест
Датум објаве	Април 1992.
Серија	MD2, MD4, MD5, MD6
Детаљи
Величина сажимања	128 бита
Структура	Меркл-Дамгард конструкција
Рунде	4
Најбоља јавна криптоанализа
Напад у 2009. години од стране Таоа Ксиа и Денгоа Фенга разбио је MD5 отпорност на колизију за 220.96 време. Напад је трајао неколико секунди на обичном рачунару.

MD5 (енгл. Message-Digest algorithm 5) је криптографски алгоритам који спада у групу хаш алгоритама или алгоритама за сажимање (ови алгоритми се још називају и дигест, иреверизибилни или алгоритми без кључа ) и био је веома је примењен у многим областима заштите података, мада се данас сматра подложним криптографским нападима тако да се ређе примењује у криптографији, али је нашао веома честу примену у провери интегритета већих фајлова због своје брзине. Дужина дигеста (дигест се може превести као сажетак) је 128 бита.

Настанак алгоритма

MD5 алгоритам је развио 1991. године Роналд Ривест. Базиран је на MD4 алгоритму, и иако је нешто спорији од MD4 алгоритма, MD5 је много сигурнији. Величина дигеста, као и број додатних битова додатих изворној поруци су остали исти. Због разлога што је MD4 алгоритам развијен с намером да буде најбржи алгоритам, алгоритам се налазио „на самом рубу“ у погледу ризика успешних криптоаналитичких напада. При развоју MD5 алгоритма, програмери су се одрекли одређеног коефицијента брзине извођења како би остварили већу сигурност.

Разбијање MD5 алгоритма

Дужина дигеста овог алгоритма је 128 бита, чему многи криптоаналитичари замерају овом алгоритму тако да се сматра да је подложан brute force birthday attack. Један такав пројекат под именом MD5CRK је покренут 1. марта 2004. године са намером да докажу да овај алгоритам није сигуран. Не дуго затим 17. августа 2004. објављено је да су Ксиаоун Ванг, Денгуо Фенг, Ксуејиа Лаи и Ксонгбо Ју (Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu) успешно разбили алгоритам односно да су пронашли колизију на алгоритму. За разбијање овог алгоритма било им је потребан само један сат на IBM p690 кластеру.

1. марта 2005. Арјен Ленстра, Ксиаоун Ванг, и Бене де Вегер демонстрирали су креирање два X.509 сертификата са различитим јавним кључевима али истим MD5 дигестом. Неколико дана потом Властимил Клима је креирао унапређени алгоритам који је у стању да на обичном лап топу за неколико сати креира колизију MD5 алгоритма.

Примена

Због пронађених недостатака овог алгоритма, данас се све ређе користи у криптографији за потписивање дигиталних сертификата и складиштење шифри и уместо њега се најчешће користе неки други алгоритми, као на пример SHA-1, WHIRLPOOL, RIPEMD-160. Данас се овај алгоритам најчешће примењује за проверу интегритета фајлова (енгл. checksum, контролни збир).

Опис алгоритма

Слика 3. Једна MD5 операција - MD5 се састоји од 64 ових операција, груписаних у четири корака од 16 операција. F је нелинеарна функција; једна функција се користи за сваки корак. М_i представља 32-битни блок улазне поруке, и К_и представља 32-битну константу, другачију за сваку операцију.

MD5 алгоритам као улаз користи б-битну поруку где је б произвољни ненегативни цели број. Поруку можемо замислити као низ битова:

$m0m1m2...m{b-2}m{b-1}$

Порука се мора надопунити битовима како би њена дужина (у битовима) одговарала броју 448 модуо 512. Другим речима, порука се мора проширити тако да јој недостају 64 бита да њена укупна дужина у битовима буде дељива са 512.

Најчешћи начин проширивања поруке је да се прво поруци дода један „1“ бит, а затим слиједе битови „0“. Тако ће се поруци у најмању руку додати само један бит, а у најгорем случају 512 бита.

Након проширења поруке, поруци је потребно додати 64-битну репрезентацију броја б (б је дужина изворне поруке пре њеног проширења). У случају да се дужина поруке не може приказати помоћу 64 бита, поруци се додају само нижих 64 бита. Битови репрезентације броја б се додају поруци као две 32-битне речи, при чему је реч мање тежине прва придодата.

Након проширења поруке и додавања битова репрезентације дужина поруке мора бити дељива са 512. Односно, порука мора имати дужину дељиву са 16 (32-битних) речи. Сада поруку можемо приказати као:

$M[0,1,...,N-1]$
где је N дељиво са 16.

Након што је порука припремљена за MD5 алгоритам, потребно је иницијализирати 128-битни МД бафер. МД бафер се састоји од четири 32-битних речи А, B, C и D. Као иницијалне вредности речи у хексадецималном систему се користе: A=67452301, B=EFCDAB89, C=98BADCFE и D=10325467.

После иницијализације покреће се MD5 алгоритам који се поново изводи за сваких следећих 512 бита поруке. Само језгро алгоритма представља компресијска функција која се састоји од четири циклуса. Сваки од четири циклуса има сличну структуру, али сваки користи другачију примитивну логичку функцију F, G, H или I. Коначан резултат представљају вредности у регистрима А, B, C и D које се сабирају са њиховим иницијалним вредностима. Сваки од тих четири регистара представља једну четвртину дигеста улазне поруке.

Пример

Пример примене MD5 алгоритма. Реченицу у ASCII формату „The quick brown fox jumps over the lazy dog“ пустићемо кроз MD5 алгоритам и добићемо 128-битни излаз у хексадецималном облику

MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6

Чак и најмања промена тип једног слова у реченици имаће као резултат промену хексадецималног излаза. На пример променићемо d у c:

 MD5("The quick brown fox jumps over the lazy cog") = 1055d3e698d289f2af8663725127bd4b

Излаз MD5 функције у случају празног стринга биће:

 MD5("") = d41d8cd98f00b204e9800998ecf8427e

Упоређење MD5, SHA-1 и RIPEMD-160 алгоритма

32 бита дужи дигест SHA-1 и RIPEMD-160 алгоритама су главне предности тих алгоритама у односу на MD5. Тежина добијања идентичног дигеста за две различите поруке тим алгоритмима са 2⁸⁰ комбинација што изгледа супериорно према тежини MD5 алгоритма која износи 2⁶⁴.

Упоређења SHA-1 алгоритма са MD5 алгоритмом показују да је SHA-1 алгоритам сигурнији од MD5 алгоритма.

	MD5	SHA-1	RIPEMD-160
Дужина дигеста	128 битова	160 битова	160 битова
Дужина блока	512 битова	512 битова	512 битова
Број корака	64 (4 x 16)	80 (4 x 20)	160
Највећа дужина поруке	-	2^64-1 битова	2^64-1 битова
Примитивних логичких функција	4	4	5
Број константи	64	4	9
Запис битова	Little endian	Big endian	Little endian

3