2. MD5

MD5

Ronald Rivest navrhl v roce 1991 zcela nový algoritmus. Jedná se o hashovací systém MD5 (Message Digest Algorithm 5). Algoritmus v sobě implementuje hashovací funkci a probíhá v 64 rundách, na jejichž konci je 128 bitový výstupní blok dat.

Jeho zjednodušený princip můžete vidět na schématu.

do algoritmu nám vstupuje blok dat Mi, který je dlouhý 512 bitů
z tohoto bloku dat získáme šestnáct 32 bitových slov (označených M0...M15)
posloupnost těchto šestnácti bloků je opakována čtyřikrát za sebou (blok1 .. blok4), pokaždé s jinou permutací
Vzpomenete si ještě, co je to permutace?
permutace mění pozice prvků dané množiny za jiné prvky množiny bez opakování prvku
jak jsme si říkali, prvky si zahrají škatulata

Ale zpět k postupu:

blok je rozdělen na čtyři části (bloky A, B, C, D) a v kompresní funkci se kombinuje logickou funkcíXOR vždy s jedním 32 bitovým slovem Mi, výsledek poté provede XOR s konstantou K_i (K_i pro každou rundu mění); důležité je, že funkce F, se po šestnácti rundách střídá a nahrazuje ji jiná funkce
po operaci je blok dat cyklicky posunut o x bitů vlevo
následuje poslední použití XOR při kombinaci výsledku s částí bloku
runda končí výstupními bloky A, B, C, D
tyto operace proběhnou 64x za sebou a po průběhu poslední šedesáté čtvrté rundy se k bloku dat přičte původní otevřený text
a máme výstupní text, který tvoří 128 bitů (128bitová hash)

Za předpokladu, že tento blok dat je jediný, který nám do algoritmu vstupuje, pak jsme se dobrali ke zdárnému konci. Pokud bychom měli ještě několik dalších bloků, pokračovali bychom stejným způsobem a na konci by na nás opět čekala 128 bitová hash.

Útoky na MD5

Zde je nutné říci, že hledáme klíč, díky němuž získáme správný hash. Hash, který máme k dispozici je zašifrován veřejným klíčem, který známe. Hash, který hledáme, je zašifrován soukromým klíčem autora a kolizi, která by mohla ukázat totožnost těchto dvou hashí právě hledáme.Budou zde zmíněny jen některé pokusy o prolomení.

v roce 1994 by navržen stroj na vyhledávání kolizí za cenu 10 milionů dolarů; dokázal najít kolizi během 24 dnů
v letech 1993 a 1996 byly uveřejněny kolize a pseudokolize (pseudokolizí rozumíme takovou kolizi, která je definována určitou množinou - můžeme si to představit jako náhodné a pseudonáhodné generování klíče)
v srpnu 2004 byly prezentovány další možné kolize
asi nejzajímavější je přínos Číňanů v kryptoanalýze MD5, kdy přišli s metodou, která dokáže nalézt kolize dvou různých 1024 bitových textů; princip je vlastně jednoduchý a je založený na tom, že se nejprve naleznou dvě různé 512 bitové „půlzprávy“(což časově trvá několik hodin); poté se k nim najdou ještě jedny dvě 512 bitové půlzprávy (to trvá už jen sekundy) složené zprávy (první z prvního hledání s první z druhého hledání a obdobně druhá z prvního hledání s druhou z druhého hledání) pak mají stejnou hash.

Co nám to přináší?Neumíme k podepsanému dokumentu, souboru, či mailu, nalézt jiný, se stejnou hash funkcí, aledokážeme najít dva různé dokumenty, soubory, či maily, opatřené stejnou hash.Pro ilustraci si to můžeme představit tak, že jako skladník necháme řediteli podepsat žádost o dovolenou, se kterou úplně náhodou koliduje návrh na zvýšení platu.Nástupcem MD5 bývá označen algoritmus SHA a jeho novější modifikace, pojďme se nyní společně na ně podívat zblízka...

Shrnutí

Hashovací algoritmy nám vytvářejí hashe. Podívali jsme se tedy blíže na princip jednoho z nich a to algoritmu MD5.

Zdroje

JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.