Vlákno názorů k článku
Hašovací funkce MD5 a další prolomeny!

Sakra, tohle už je několikátý článek, co jsem o tom přečetl, ale zase jsem se nedozvěděl to hlavní. Umějí nalézt kolizi k pevně danému vstupu, nebo jen dva vstupy se stejným digestem? A pokud rozdíl mezi tím není podstatný, tak proč?

Já zase nechápu, proč je z toho najednou takový problém. Hash má přece omezenou délku a vůči neomezenému počtu dat ze kterých jde spočítat mi připadá logické, že kolize prostě musí existovat u všech funkcí. Jiná věc by byla, kdyby šla data jednoduše upravit tak, aby při stejném hashi obsahovala to co chce útočník. To snad ale (zatím ?) nehrozí?

Kolize samozrejme existuje (je jich dokonce nekonecne mnoho), najit je by ale melo byt co nejobtiznejsi. md5 ma 128 bitu. Kdyz vezmete 2 ruzne soubory, mate pravdepodobnost 1/2^128 ze budou mit stejny md5sum. To je tak mala pravdepodobnost, ze kdyby lidstvo celou dobu sve existence jen hrubou silou generovalo nahodne dokumenty, porat pravdepodobnost ze 2 z nich budou mit stejnou md5ku je strasne mala. Jakmile se ale najde kolize, prinejmensim to signalizuje ze s tou hashovaci funkci neni neco v poradku.

Ano, ale oni nalezli kolizi pri o nekolik radu
mensim poctu pokusu, nez by odpovidalo "hrube sile",
cili vyzkouseni vsech moznosti. Jinak samozrejme v kazde hashovaci funkci existuji dva vstupy ktere davaji stejny digest. Ale kryptograficky bezpecna je, pokud takove dva vstupy neumite najit jinak nez hrubou silou.

-Y.

Uz som si myslel, ze len ja som tie vsetky clanky nepochpil.

K pevne danemu vstupu se kolize zatim u jmenovanych funkci najit neumi. Postacuje vsak najit dve ruzne zpravy, lisici se napriklad v nekolika bitech, majici stejnou has. Tento rozdil, bude-li se jednat napriklad o smlouvu, se muze promitnout napriklad do smluvni ceny. Pri podpisu utocnik predlozi spravnou smlouvu, prodavajici ji podepise a utocnik pak zaplati mene.... Pokud hasovaci funkce neni bezkolizni, ztraci smysl. Kvuli tomu byly konstruovany.

"bezkolizni" v tomto kontextu znamena, ze nikdo nikdy nenalezl zadnou kolizi! Ne ze zadne neexistujou! Kolizi je nekonecne mnoho, najit je by ale melo byt obtizne,

Jak je tedy definovana bezkoliznost ? Ja jsem si myslel, ze jde prave o to, nemit v rozumnem case k dispozici moznost si k dane hashi, resp. dvojici zprava+hash zkonstruovat onu fake zpravu (smlouvu). To, ze existuji ruzne zpravy, ke kterym hash funkce da stejny hash, je prece uplne zrejme. Jde hlavne o ten "reverzne konstrukcni" algoritmus,ze.

ne, napriklad, na kernel.org bude vystavene jadro a bude tam u toho ze ma a4c3da2e685c4e17f2a48077b8ee36ef md5sum. Jadro je velke a tak si nahraju tar.gz od kamarada misto toho abych ho tahal z netu. Spocitam mu md5sum a skontroluju jesli sedi. Ona sedi tak bych si mel byt jist, ze ten tar.gz ten muj kamarad nemodifikoval a ze tam nezanes diry. Kdyby bylo snadne najit kolize, moch by tam udelat backdor a pridat sikovnej komentar kterej sice nebude mit vliv na kod, ale zajisti, ze md5suma bude shodna jako na kernel.org. Je to jasnejsi?

Proc to pises v reakci na muj prispevek ?

sry, nejak sem se rozjel a ted ani nemuzu dohledat k cemu to melo patrit :-)

OK, ale pokud neumějí nalézt kolizi k pevnému vstupu, ale jen generovat kolize, tak tato možnost právě nehrozí, pokud nejde o spiknutí tvého kamaráda *a* kernel.org.

Mozna to nepomuze, pokud jedna zprava je zcela pevna (jako treba neco z kernel.org).

Ale pokud obe zpravy pripravuji ja, tak mam spoustu moznosti, jak si tu kolizi predem pripravit. Treba tak, ze pridavam a ubiram mezery, menim formatovani, slova zamenuji za synonyma atd.

Mimochodem, z tohoto duvodu jiz starsi knihy o bezpecnosti (napr. Schneier) doporucuji, abych ve zprave, kterou mi nekdo dava podepsat, provedl nepodstatnou zmenu formatovani - prave proto, abych vyloucil moznost, ze autor pripravil dve ruzne verze se shodnym hashem.

Ano, v tom je ten rozdíl.

Někdy nastávají situace jako z dalšího diskusního příspěvku (Petr, 25.8.), tj. kdy je někdo tvůrcem programu, dokumentu,... Pak si kolize (metodou Petr, 25.8.) lze připravit, a to pravděpodobně i v případě, že se podepisuje komprimovaný soubor (tj. haš se vytváří z komprimovaného souboru). Neznám formát archivu tar.gz, ale u winzipu by to pravděpodobně šlo - ne vše je zkomprimované, je tam spousta hlaviček s ohromnou manévrovací schopností, které komprimované NEJSOU. Čínský příspěvek [1] právě ukazuje kolidující zprávy, lišící se pouze v několika málo bitech.

Ked je niekto TAK dobry, ze dokaze ucelovo modifikovat zdrojak v komprimovanom subore pri zachovani vysledneho hashu nech sa mi ozve :-)
Odmena ista ;)

To nemyslis vazne, ze ne :-). Clovek disponujici takovou schopnosti se neozve, protoze vyhody jemu z toho plynouci prevazi prakticky cokoli, co mu muzes nabidnout...

Bezkoliznost je překlad anglického collision free. Neznamená to, že kolize nenastanou, ale že je výpočetně nemožné je NALÉZT (viz též správné odpovědi ostatních v diskusi). Protože fakt o EXISTENCI kolizí je zcela triviální, nikdo zasvěcený si při vyslovení pojmu bezkolizní (collision free) nemyslí, že by snad neexistovaly (to je také odpověď na jiný příspěvek do diskuse). Pár definic z kapitoly 12 mojí přednášky na MFF UK (viz lit., k dispozici on-line, prosím nevnucuji, ale když už to je napsané, nechci to opisovat, kromě toho je to v kontextu i s příklady apod.) pro osvěžení (také odpověď na více příspěvků):

Definice: jednosměrná (jednocestná) funkce
Funkci f: X --> Y nazveme jednosměrnou (jednocestnou), jestliže z jakékoli hodnoty x z množiny X je snadné vypočítat y = f(x), ale pro náhodně vybranou hodnotu y z množiny f(X) neumíme (je výpočetně nemožné) najít její vzor x z množiny X tak, aby y = f(x).

Definice: bezkolizní funkce
Funkci f: X --> Y nazveme bezkolizní, jestliže je výpočetně nemožné nalézt různá x, x´ z množiny X tak, že f(x) = f(x´).

Definice: hašovací funkce
Mějme přirozená čísla L, n a nechť X je množina všech binárních řetězců délky 0 až L (prázdný řetězec je platným vstupem a má délku nula). Funkci h: X --> {0,1}^n nazveme hašovací, jestliže je jednosměrná a bezkolizní. Říkáme, že každému binárnímu řetězci z množiny X přiřadí binární hašový kód (hash, haš) délky n.

Z důvodu definice, tedy samé podstaty hašovacích funkcí, je nalezení kolizí pro hašovací funkci smrtelné.

Dále (také odpověď na více příspěvků) nalezení kolize neznamená, že jsem povinen nalézt druhou kolidující zprávu ke zprávě dané, ale libovolné dvě různé zprávy. Tyto dvě situace se také někdy rozlišují jako kolize prvního a druhého řádu. V definici hašovací funkce se požaduje odolnost silnější, tj. nesmí se najít jakékoliv i nesmyslné různé zprávy se stejnou haší.

Proč? Je opatření proti tomu, když útočníkem je sám tvůrce zpráv (už jsem o tom psal v jiné odpovědi). Pokud bude schopen připravit dvě různé zprávy se stejnou haší, může dát jednu podepsat smluvní straně, ale u soudu předložit druhou (pro něj výhodnější) a tvrdit, že protistrana podepsala tu druhou. Pokud by bylo možné nalézat kolize k "dané" zprávě, byla by to katastrofa. Podepsaný kernel by šel zaměnit za vyrobený kolidující (haš je stejná), "JAKÁKOLIV" smlouva (jakýkoliv digitální podpis) by byla zpochybnitelná předložením vyrobené kolidující smlouvy nebo kolidujícího dokumentu nebo by to umožňovalo podvržení vykonstruovaného kolidujícího programu za pravý (podepsaná je pouze haš).

zase se dopouštíte nepřesností. Ne, že bych chtěl být příliš velký pedant, ale přesnost je důležitá.

není vhodnější místo "je výpočetně nemožné" používat spojení "je výpočetně obtížné"? Rozdíl mezi významem slov "nemožné" a "obtížné" pozná i malé dítě.

Dále:
Z důvodu definice, tedy samé podstaty hašovacích funkcí, je nalezení kolizí pro hašovací funkci smrtelné.

Správnější formulace by měla patrně znít:
Z důvodu definice, tedy samé podstaty hashovacích funkcí, je nalezení ALGORITMU pro SNADNÉ nalezení kolizí pro hashovací funkci smrtelné.

Obávám se pane Rohledere, že "výpočetně nemožné" je používaný odborný termín.
Vaši druhou připomínku beru jako poučení, díky. Uděláte mi velkou radost, pokud si přečtete některé mé články a napíšete mi připomínky k terminologii.

z hlediska toho, že česká počítačová terminologie ještě není, třeba na rozdíl od matematiky ustálená, bych se přimlouval za používání takových českých termínů, které lépe vyjadřují podstatu věci. Třeba už to české "výpočetně nemožné" je patrně překladem "computationally unfeasible", což se dá vyjádřit jako výpočetně nemožné nebo také nerealizovatelné, neproveditelné. Nejblíž ke skutečné podstatě je asi to nerealizovatelné.

S tím opravováním článků to asi nepůjde, nejsem až zas takový odborník, ale když na něco narazím, tak Vám určitě napíšu :-)

Skutečně často také používám synonymum "výpočetně neproveditelné".

Jinak s tou terminologií je to opravdu problém, ale spoléhám na přednášky na MFFUK, že ta terminologie se zde zavede. Deset let jsem brojil proti termínům kryptování, zakryptovat, enkrypce, enkryptovat, které pokrývá starý český základ šifr-- a termíny šifrování, šifra, zašifrovat, odšifrovat, šifrátor apod.
Nakonec termín kryptovat vešel do českého jazyka jako tzv. neologizmus a pravděpodobně se stane zanedlouho spisovným.

z toho ovšem třeba namátkou plyne, že libovolně dlouhý vstup jde komprimovat do 128 bitů (třeba), protože existuje jednoznačné zobrazení mezi libovolnou množinou a 128 bity. Super tvrzení.... :-)

K pevne danemu vstupu se kolize zatim u jmenovanych funkci najit neumi.

...jinak nez hrubou silou. Staci ;-)

Jasně že jde libovolný vstup jednoznačně komprimovat do 128 bitů. Akorát že už nepůjde dekomprimovat, protože to zobrazení není jednoznačné _vzájemně_ :-))