Umí p?edpov?d?t vít?ze VyVolených, BigBrother i co se stane v roce 2006
25.08.2005John Kelsey, Tadayoshi Kohno: Herding Hash Functions and the Nostradamus Attack–DRAFT, IACR Cryptology ePrint Archive, Report 2005/281, 22 Aug 2005
Obsah
Auto?i ukazují, že ty hašovací funkce, u nichž je možné konstruovat kolize v reálném ?ase (nap?íklad MD4, MD5), mohou být náchylné na tzv. Nostradam?v útok. Útok má dv? fáze. V první fázi si úto?ník p?ipraví tzv. diamantovou strukturu, kterou vytvo?í pomocí schopnosti nacházet kolize a vypo?te hodnotu hašovacího kódu H, kterou zve?ejní. Potom k libovolnému prefixu P (který obdrží zven?í, je vytvo?en bez jeho vlivu) v druhé fázi vytvo?í suffix S tak, že h(P || S) = H. Tímto suffixem jaksi "dožene" (herd) libovoln? zadaný za?átek zprávy P do p?edem publikované hašovací hodnoty H. Publikováním P || S vytvá?í dojem d?kazu, že ?et?zec P znal p?ed publikací hodnoty haše H. Je z?ejmé, že hašovací funkce by m?ly být odolné proti tomuto typu útoku. Ty, které odolné jsou, se nazývají "odolné proti donucování" - Chosen Target Forced Prefix (CTFP) preimage resistance. Je z?ejmé, že hašovací funkce, které nejsou odolné proti donucování (tj. ty, u nichž lze hledat kolize), by nem?ly být používány k d?kazu znalosti.
P?íklad. B?hem roku 2005 bude publikováno prohlášení typu: Já Nostradamus, zde uve?ej?uji MD5 haš od mé p?edpov?di cen akcií SP500 v poslední den roku 2005 a další p?edpov?di na budoucí léta. Ceny akcií tvo?í prefix P. Suffix S vytvo?í úto?ník poté, co bude znát P. Na po?átku roku 2006 pak zve?ejní ceny akcií i další p?edpov?? (S z?et?zeno s P). Tím vytvá?í dojem, že ceny akcií v poslední den roku znal p?ed tímto datem, a tudíž i ostatní p?edpov?di jsou hodnov?rné. Ve skute?nosti však ceny akcií neznal.
Auto?i proto varují, že hašovací funkce (zejména MD4 a MD5), u nichž lze hledat kolize, by nem?ly být používány v protokolech, kde se pomocí nich prokazuje znalost n?jaké tajné hodnoty. Takových použití je v protokolech celá ?ada.
Dobrá zpráva je, že "donucovací útok" je pom?rn? složitý. Pro MD5 to znamená ud?lat 2^69 až 2^87 operací podle délky suffixu.
Špatná zpráva je, že útoky se vždy pouze zlepšují, nikdy nezhoršují.
Zdroj: http://eprint.iacr.org/2005/281/Autor: VK
Heuristické vyhledání souvisejících článků v archívu NEWS
Pozor - není zdaleka přesné a výsledek je bez záruky...
Chcete-li článek obsahující konkrétní termín - pou·ijte funkci
vyhledávání !
