Vlákno názorů k článku Hašovací funkce MD5 a další prolomeny! od Yeti - Sakra, tohle už je několikátý článek, co jsem...

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 ?

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.

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

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é.

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ě_ :-))