MD5

Из пројекта Википедија

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

[уреди] Настанак алгоритма

MD5 је креирао Роналд Ривест (један од проналазача RSA алгоритма) 1991. године

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 клaстеру.

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

[уреди] Примена

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

[уреди] Опис алгоритма

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

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

m0m1m2...mb − 2mb − 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 алгоритма.