MD5

Վիքիփեդիայից՝ ազատ հանրագիտարանից

MD5-ը գաղտնագրությունում հաճախ օգտագործվող, մասնակի անապահով, 128բիթ երկարությամբ հեշ արժեք ունեցող հեշ ֆունկցիա է: Որպես ինտերնետ ստանդարտ RFC 1321-ի մաս, այն օգտագործվում է բազմազան սպահովագրման գործողություններում և ֆայլերի ամբողջականությունը ստուգելու համար: MD5 հեշը հաճախ ներկայացվում է որպես 32 նիշանոց տասվեցական թիվ:

MD5ը նախագծվել է Ռոն Ռիվեստի կողմից 1991-ին իր նախորդող MD4-ին փոխարինելու համար: 1996-ին հայտնաբերվել է առաջին թերությունը: Չնայած որ թերությունը ճակատագրական չէր, գաղտնագրողները սկսեցին խորհուրդ տալ օգտագործել այն հեշ ֆունկցիաներ, օրինակ SHA-1(չնայած վերջինս նունյպես ունի բազում խոցելիություններ): 2004-ին ավելի վտանգավոր խոցելիություններ հայտնաբերվեցին, որոնք MD5-ի օգտագործումը հարցականի տակ էին դնում: Իսկ 2006-ին մի խումբ հետազոտողներ նկարագրեցին մի ալգորիթմ, որը թույլ եր տալիս ստեղծել 2 ֆայլ նույն MD5 checksum-ով:

[խմբագրել] Պատմություն

Message Digset-ը դա ալգորիթմների խումբ է որոնք նկարագրվել են պրոֆեսոր Ռոնալդ Ռիվեստի կողմից: MD5-ը ստեղծվեց որպես MD4-ի փոխարինող, երբ դեռ վերջինիս խոցելիությունները հայտնի չէին, սակայն նրանք շուտով երևան եկան: 1993ին հայտնաբերվեցին MD5-ի թերություններ ունենալու առաջին պսեվդո-նշանները: Դեն Բոեռը ներկայացրեց 2 սկզբնարժքեավորման վեկտորներ որոնք տալիս էին նույն հեշ արդյունքը: 1996ին Դոբերտինը հայտարարեց MD5ի համեմատման ֆունկցիաի ընդհարման մասին: Սա ամբողջական հարձակում չէր MD5ի վրա, բայց սա բերեց այլ հեշ ֆունկցիաների օգտագործմանը անցնելու մասին մեծ խոսակցությունների:

128 բիթը բավականին փոքր է ծննդյան հարձակում(birthday attack) գործելու համար: 2004ին թողարկվեց MD5CRK կոչված մի նախագիծ որը նպատակ էր դրել ապացուցել MD5ում ընդհարումների գոյությունը, սակայն այն ավարտվեց այն բանից հետո, երբ 2004-ի օգոստոսի 17ին Ժիայոյուն Վանգը հայտարարեց MD5ում գոյություն ունեցող լրիվ ընդհարումների մասին: Նրանց անալիտիկ հարձակումը տևում էր 1 ժամ IBM p690 cluster-ի վրա:

2005-ի մարտի 1-ին Արյեն Լեսնտրան Ժիայոյուն Վանգի հետ միասին ցուցադրեցին 2 X.509 սերտիֆիկատներ տարբեր հասարակական բանալիներով (public key) և նույն MD5 հեշ կոդով, ինչով ապացուցեցին ընդհարումների հնարավորությունը պրակտիկայում: Մի քանի օր անց Վլաստիմիլ Կլիման ներկայացրեց ալգորիթմ որը իվիճակի էր կառուցել MD5 ընդհարում մի քանի ժամերի ընթացքում, 1 ծնկադիր համակարգչի վրա: 2006-ի մարտի 18-ին նույն Կլիման ներկայացրեց նոր ալգորիթմ, որը նա անվանեց թունելավորման ալգորիթմ: Վերջինս գտնում էր ընդհարում 1 նոթբուքի վրա, ընդհամենը 1 ժամում:

[խմբագրել] Կիրառությունները

MD5-ը լայն կիրառություն է գտել կիրառական ծրագրերի լայն բնագավառում, որտեղ պետք է տալ որոշակի երաշխիք որ փոխադրված տվյալները բարեհաջող տեղ են հասել: Օրինակ շատ սերվերներ տրամադրում են նախորոք հաշվարկված MD5 checksum-ներ, որպեսզի օգտագործողը կարողանա ֆայլը ստանալուց հետո հաշվարկել ստացված ֆայլի MD5 checksum-ը և համեմատի ստացվածի հետ: Սակայն հաշվի առնելով, որ այժմ շատ հեշտ է ստանալ MD5 ընդհարում` 2 ֆայլ նույն MD5 հեշ արժեքով, չի կարելի վստահել ֆայլերի ամբողջականությունը ստուգելու այս եղանակին:

UNIX-անման օպերացիոն համակարգերը ներառում են MD5-ի հաշվարկման ծրագրեր ինենց ստանդարտ փաթեթում, մինչդեռ Windows համակարգում օգտագործվում են երրորդ կողմերի ծրագրերը:

[խմբագրել] Ալգորիթմ

Մեկ MD5 գործողություն։ MD5 բաղկացած է 64 այսպիսի գործողություններից, միավորված 16 գործողությունների 4 անցման մեջ։ F-ը ոչ գծային ֆունկցիա է. ամեն անցման ժամանակ օգտագործվում է մեկ ֆունկիցա։ M_i-ը 32-բիտանոց փոխանցվող հաղորդման (input meesage) բլոկն է, իսկ K_i -ով նշանակված են 32-բիտանոց հաստատուները, որոնք տարբեր են ամեն գործողության համար

MD5-ը վերածում է փոփոխական երկարության հաղորդագրությունը 128 բիթանոց ելքային տողի: Ներմուծված տողը մասնատվում է 512-բիթանոց բլոկերի` 16 հատ 32-բիթանոց ամբողջ թվերի: Հաղորդագրության երկարությունը ավելացվում է այնպես, որ այն բաժանելի լինի 512ի: Ավելացումը իրականացվում է հետևյալ կերպ` սկզբից 1 բիթ` 1 է ավելացվում հաղորդագրությանը, ինչից հետո հաջորդում են այնքան 0-ներ, որ հաշեղդագրության երկարությանը պակասի 64 բիթ 512-ի բաժանելի լինելու համար: Վերջին 64 բիթերը լրացվում են հաղորդագրության իրական երկարությունը բիթերով ներկայացնող անբողջ թվով:

Հիմնական MD5 ալգորիթմը աշխատում է 128 բիթանոց վիճակներով, բաժանված 4 հատ 32 բիթանոց բառերի, որոնք համապատասխանաբար կկոչվեն A, B, С և D: Վերջիններս սկզբնարժեքավորվում են հանտնի հաստատուններով: MD5 ալգորիթմը հաջորդաբար գործողություններ է կատարոմ ամեն բլոկի հետ, ինչի արդյունքում փոփորվում են վիճակի փոփոխականները: Հաղորդագրության բլոկի մշակումը բաղկացած է 4 համանման փուլերից, որոնք անվանվում են շրջաններ` rounds: Ամեն շրջանը բաղկացած է 16 ոչ գծային ֆունկցիաների (մոդուլ 2-ով գումարում, ձախ պտույտ) վրա հիմնված օպերացինաերից: Կան հնարավոր 4 ֆունկցիաներ, որոնցից ամեն շրջանում օգտագործվում է մեկը:

$F(X,Y,Z) = (X\wedge{Y}) \vee (\neg{X} \wedge{Z})$