MD5

Шаблон:Инфокутија метода шифровања -{MD5}- (Шаблон:Јез-ен) је криптографски алгоритам који спада у групу хаш алгоритама или алгоритама за сажимање (ови алгоритми се још називају и дигест, иреверизибилни или алгоритми без кључа ) и био је веома је примењен у многим областима заштите података, мада се данас сматра подложним криптографским нападима тако да се ређе примењује у криптографији, али је нашао веома честу примену у провери интегритета већих фајлова због своје брзине. Дужина дигеста (дигест се може превести као сажетак) је 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}-. Данас се овај алгоритам најчешће примењује за проверу интегритета фајлова (Шаблон:Јез-ен, контролни збир).

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

Слика 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}- алгоритма.

Шаблон:Мд5сха2рипемд160упоређење3