Kupodivu nalezeni kolize v tomto pripade je jednodussi nez se na prvni pohled zda a neni o moc slozitejsi nez u jedne hasovaci funkce. Dokonce plati obecne pro ruzne velmi komplikovane zesloziteni zpravy nez je obraceni znaku. Paradoxem je, ze cim vice bude zeslozitena zprava pro druhe hasovani, tim lepe se bude kolize hledat (nevzniknou zavislosti, ktere by mohly teoreticky komplikovat nasledujici postup). Uplne nejlepsi by bylo vzit si pevny klic a zpravu M nikoli obratit, ale zasifrovat pomoci AES! Tak jak na to. Dejme tomu, ze puvodni funkci oznacime H a aplikaci na M jako H(M). Necht ma n bitovy hasovy kod. Potom oznacme G tu hasovaci funkci, ktera vznikne aplikaci H na (jak je libo) upravenou zpravu M , tj. G(M) = H(M obracene nebo M jinak zasmodrchana). Ted nalezneme tzv. multikolizi u hasovaci funkce H. Bylo ukazano (Joux, Crypto 2004), ze nalezeni 2^(n/2) kolizi u H trva radove n*2^(n/2), tedy mame 2^(n/2) zprav M, ktere davaji stejnou hash H. Mezi temito zpravami M se najde podle narozeninoveho paradoxu jedna, ktera dava kolizi pro hasovaci funkci G, tj. mame soucasne kolizi na H i G, tj. stejne (H(M),G(M)).
Pozn.: Pouzijeme-li jeste navic Kelsey-Schneierovo vylepseni hledani multikolizi, dobereme se k velmi mnoha takovym zpravam M.
Pokud se podivate na moji stranku ,venovanou kolizim hasovacich funkci, mel byste tam najit prezentaci na MFFUK, kde je v zaveru literatura i hlavni vysledky zminene posledni prace.
Zkuste na to jit jinak.
