Názory k článku
Hašovací funkce MD5 a další prolomeny!

To jako že "pišme správně česky"? Odkdy je ke spočtení hashe potřeba haš? To snad leda kdybych to chěl počítat z hlavy...:-)

hash i haš je spravny cesky termin, je to v mnoha ceskych normach, namatkou CSN ISO/IEC 10118-1 (hasovaci funkce vseobecne)

Aby mohli takovi magori jako ty na forum neco prispet, vole! Nemas to jedno, vsichni vime o co kraci, jenomze holt, nejakej rypal se vzdycky musi najit. Modlim se, aby jednou nastal den, kdy si prectu diskusi se vsemi prispevkami "k veci".

kdidek kamo ;-)
bud nad veci a uzivej letosni sklizne...

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

Nebo je přístupný pouze vládám a korporacím?

Bohužel ten algoritmus si jeho autoři nechávají pro sebe. Pravděpodobně ho pilují, nevěřím tomu, že by na ně byl kladen vnější tlak. Jednak se o ničem takovém nehovořilo a jednak jeden z autorů žije delší dobu ve Švýcarsku, takže by asi takový vládní nátlak nepřipustil. Některé triky, které Číňani použili, by určitě ráda znala některá kryptoanalytická oddělení. Zatím je pravděpodobné, že část toho zná NSA, neboť záhy po uveřejnění SHA-0 ji změnila na SHA-1. SHA-1 útoku odolává...
Vše podstatné, co je k algoritmu známo, je v literatuře [1] plného textu.

Ze o tom vubec pochybujes. W a Microsoft to maj plne pod kontrolou ;)

Nevíte, jak je na tom Tiger hash? ( http://www.cs.technion.ac.il/~biham/Reports/Tiger/ )

Jestli je pan Klíma tím naším slavným kryptologem, tak si tímto článkem opravdu vybral slabší chvilku.

Každá hashovací funkce je přece už ze své podstaty kolizní. Pokud se podíváme třeba do Schneiera, tak ten na jednosměrné hashovací funkce klade následují požadavky:

1. při dané zprávě M je jednoduché spočítat h=H(M)
2. při daném hashi h je těžké spočítat M takové, že H(M)=h
3. při dané zprávě M je těžké nalézt jinou zprávu M' takovou, že H(M)=H(M')

Takže pokud se něco stalo, tak jedině to, že kryptologové našli algoritmus, který pro jisté hashovací funkce láme podmínku 2 a 3 (tj. není těžké spočítat ...).

Koliznost nějaké hashovací funkce ji ještě nediskvalifikuje z funkcí v digitálním podpisu, protože tímto způsobem by byly diskvalifikovány všechny hashovací funkce. Co takovou hashovací funkci diskvalifikuje je právě nesplnění podmínek 2. a 3.

Dobre, tak

s/bezkolizni/odolna kolizim (collision resistant)/g

trošku rozdíl.

Ja si ale myslim, ze "collision resistant" se u nas preklada prave jako "bezkolizni", s tim ze se to nesmi brat doslova (ona ta funkce neni ani doslova "jednosmerna", protoze po urcite dobe se doberu vysledku i opacny smerem, jenom je ta doba ponekud exponencialni). Ale bez zaruky.

pokud někdo překládá collision resistant jako bezkolizní, tak se jedná o významový posun jako prase. Kde jinde bychom měli používat přesné termíny, než v matematice.

%s/bezkolizni/odolna kolizim (collision resistant)/g
;)

Teď jsem se podíval do poznámek z přednášky o šifrování:

To, co jsi popsal, je "one-way hash function".

Collision-resistant hash function je funkce, která splňuje požadavek one-way hash function a navíc ještě splňuje, že je obtížné najít dvě zprávy, které mají stejnou hodnotu funkce.

Pro některá použití stačí one-way hash function (třeba kódování hesel v /etc/shadow), pro jiná použití (jako třeba digitální podpis) je potřeba collision-resistant hash function.

souhlasím s tím, že podmínku odolnosti proti kolizím jsem tam už nenapsal, to ovšem nic nemění na faktu, že ten odstavec o kolizích a nepoužitelnosti hashovacích funkcí je nesmyslný. Kolize prostě nastávají u všech hashovacích funkcí už z principu.

Zdá se, že problém EXISTENCE a problém NALEZENÍ kolizí se již v diskusi vyjasnil. Také se vyjasnilo, že podstata Vašeho nazvání článku blábolem je v tom, že považujete za nesmyslné, že bezkolizní funkcí nazývám něco, co kolize musí mít. Není to ovšem špek ode mne, ale dlouho zavedený termín. Doufám, že teď už s tím nebudete mít problém.

P.S. používají se synonyma collision free / collision resistant = bezkolizní / odolné proti kolizi, už to tu také správně zaznělo

Podival jsem se na prvni uvadeny zdroj a podstata sdeleni je dle meho laickeho usudku takova, ze umeji docela rychle nachazet pary zprav se stejnou hodnotou hashe. Takze (alespon doufam :) snad nejde o primou moznost podvrzeni zpravy, ale asi o zjednoduseni (nevim ale jak podstatne) utoku hrubou silou. Pane Klimo, pokud to ctete: co je to initial value of MD5 ? Bezkoliznost tedy znamena, ze neumim (nemam algoritmus) nachazet pary zprav se stejnou hodnotou hashe ? Dekuji

I nalezení dvou kolizních zpráv je problém při podpisu. Představ si, že uděláš nějakou zprávu, která nemá žádný význam (třeba text A: "následující byty nemají smysl: " a druhou, která význam má (třeba text B: "dlužím panu X 50000Kč a následující byty nemají smysl: ". Pak vezmeš inicializační vektor po projití první zprávy hashovací funkcí, inicializační vektor po projití druhé zprávy hashovací funkcí a na základě algoritmu najdeš kolizi. Pak vezmeš text A připlácneš za jeho konec nalezenou kolizi a dáš to někomu podepsat (ten to podepíše, neboť je to neškodné tvrzení). Pak vezmeš text B a připlácneš za něj druhou část nalezené kolize, a máš podepsanou zprávu, kterou původce podepsat vůbec nechtěl, ve které tvrdí, že ti dluží 50000Kč.

OTOH toho, že když zkontroluji MD5 digest tarballu jádra s tím, co mám, a sedí, že je přesto podvrřený, se tedy [zatím] bát nemusím -- protože vytvořit modifikovaný tarball se stejným digestem zatím neumějí, a pokud nevěřím Linusovým umýslům, nebudu od něj předně používat žádné jádro...

Ne, ale můžeš jakýkoli kód poslat Linusovi s tím, že je to firmware k nějaké nové verzi nějaké karty, a s trochou sociálního inženýrství se ti ho do oficiálního jádra podaří dostat.

Problém by byl v tom, že jádro se mění velmi rychle a nevíš, co za další patche Linus do nové verze dá, takže by předem vypočtená kolize na to stejně nefungovala. Ale u méně-se měnících projektů, kde autor vydá verzi i s touhle jedinou změnou, je to problém.

Jelikoz tar.(gz|bz2) byva dost casto zarovnan na velikost bloku (implicitne 10240), byva na konci
souboru spousta nul. Ty by se daly vyuzit k dorovnani hashe u jiz zkomprimovaneho archivu.

Díky moc, to se bude časem hodit!!!! Ta cesta tam tedy asi povede.
S tím manuálem je to sakra pravda.

nechce se mi nad tim premyslet, ale vazne to takhle funguje?

Jasně, problém je v tom, že pokud můžeš do podesané zprávy podstrčit nějakou část ty sám, tak pak (s prolomenou hashovací funkcí) můžeš získat podpis jakékoli zprávy s nějakými náhodnými byty.

Získat podpis libovolné zprávy s tím nejde. Ale už tohle prolomení podpisu může být celkem podstatný problém.

Není žádný problém tu kolizi rozšířit na libovolně dlouhé zprávy. Podstatné jsou první dva bloky, už tam nastane kolize v kontextu (průběžná haš), zprávu (obě dvě) od tohoto místa lze doplnit čímkoliv a kolize zůstává.

Obojí jste pochopil správně.
V prvním případě opravdu nejde o možnost podvržení zprávy (k nějaké předem dané), ale nalezení libovolných kolizí jinak než hrubou silou (narozeninovým paradoxem). Ukazují, že to lze udělat velice efektivně.
V druhém případě jste bezkoliznost pochopil zcela správně, viz též odpovědi výše.
Initial value of MD5 je konstanta, pevně definovaná pro MD5. Je to počáteční obsah kontextu, s nímž se začíná hašovat jakákoliv zpráva. Lapidárně řečeno se vezme tento kontext a pomocí kompresní funkce se smíchá s první částí zprávy, vznikne nový kontext, k němu se přimíchá další část zprávy atd. Je to princip iterativních hašovacích funkcí, který je použit u všech moderních hašovacích funkcí (viz též přednáška na MFF v literatuře). Čínský útok [1] dokonce ukazuje, že jsou schopni kolize nalézat pro jakékoliv hodnoty IV, nejen pro ty, definované standardem. Toho využívají při konstrukci kolidujících zpráv. Dělí je na dvě části - první částí si jakoby vytvoří svoje IV a druhou částí dotlačí kontext ke kolizi. Je to ale hodně vágní vysvětlení.

[16:35:28]alfa[~]$ md5sum 1 2
87608a1174a5b2a990b929e4a52dc683 1
189490f3dc4b30262d17cd4054110436 2

v 1 a 2 su spravy z clanku
podla clanku uvedene hashe by mali byt rovnake... nie ? medzery som odstranil...

nielenze mi nevysla hash z clanku ale ani niesu rovnake, co robim zle ?

V tech souborech 1 a 2 jsou ascii stringy nebo primo data s uvadenou ascii reprezentaci ?

Vzhledem k tomu, že tam jsou jenom znaky [0-9a-f], tak to budou asi HEX kódy znaků.

Jo, a ještě se ty dvouslova musí brát obráceně, jako v little-endian pořadí. Takže když je v tomto článku napsáno 1234ABCD 5678EF09, tak se místo toho veme CDAB341209EF7856 --- četl jsem to v původním článku, ale nezkoušel jsem to.

No nejako tak to vyslo aj mne. Tiez sa cudujem preco mi vysli 2 rozdielne MD5 a este k tomu ani jedna z nich nezodpoveda popisu v clanku. Skusal som pre istotu aj PHP funkciu md5() a tam som napodiv dostal zase ine hashe : f6e44db01f60a35bf2794cee6fee575a (a) 54607d90638616b2283638049e936aa5. Takze teraz uz mam 4 rozdielne :-) (resp. ak ratam aj clanok tak 5)

Zkoušel jsem to na linuxu pomocí "md5sum" a vyšel mi stejný hash jako vám a rozhodně se neshoduje s článkem.

Vlepte každý z kousků hexu do jiného souboru a přečtěte je pomocí

perl -ne 's/\s+//g; print pack('H2', $1) while (s/^(..)//)' vstup > vystup

Pak to funguje.

Trošku vydařenější pokus je na:
http://www.md5crk.com/sha0col/
Zkoušel jsem a funguje

Tohle mě opravdu děsí. Koukněte na www.md5crk.com a podívejte se jak lze toto zneužít při zabezpečené komunikaci. Např. moje banka používá md5 (https://www.servis24.cz). Docela by mě zajímalo, jak moc je to reálně zneužitelné?!

Zneužitelnost je o něco menší, než jen pouhé nalezení kolize. Třeba u zmíněného kernelu je potřeba najít dva rozdílné soubory dat, které půjdou rozbalit, budou stejně dlouhé a navíc bude ten druhý dávat smysl (tj. obsahovat požadovanou (dis)funkci) - tedy aby to mělo alespoň minimální naději na úspěch. To je už netriviální (resp. méně jednoduché, než pouhé nalezení kolize). Stejně tak teoretická možnost, že se mi podaří nechat si u Verisignu podepsat můj veřejný klíč se smysuplnými hodnotami zvolenými díky kolizi tak, že budu následně schopen vyměnit moje údaje za (slovní) identifikaci eBanky (tj. nalezená kolize neohrozí funkčnost veřejného klíče), pak jim unést DNS a nebo pomocí trojského koně spáchat man-in-the-middle attack. Tj. že uživatel bude komunikovat s mojim serverem a bude si myslet, že komunikuje s eBankou (kontrola popisu certifikátu, MD5 a tudíž i zřetězené kontroly uvnitř prohlížeče bude OK) a já (jako man-in-the-middle) budu eBance předávat pozměněné příkazy k úhradě. Poučení pro publikum - vidíte-li použití MD5 jako ověření identity, pak ověřujte i SHA1. Objevení současné kolize dvou rozdílných algoritmů snižuje pravděpodobnost na násobek obou obtížností. BTW: životnost hashovacích funkcí je omezená časově právě kvůli zvyšování výpočetní kapacity a tím reálnosti (snadného) nalezení kolize. Současné nalezení významného ulehčení je vlastně urychlení procesu stárnutí algoritmu.

Asi jsem úplný blbec, ale zkoušel jsem jednu jasnou věc, z které vyšel nečekaný výsledek.
Mám binární soubory file1.bin a file2.bin
>diff file1.bin file2.bin
Soubory jsou různé.
>openssl sha file1.bin
>openssl sha file2.bin
Vyjde stejný hash.
Následně jsem hashe šifroval:
>openssl sha file1.bin | openssl des -e -out file1.bin.des
>openssl sha file2.bin | openssl des -e -out file2.bin.des
Čekal jsem, že výsledné šifrované soubory budou při použití stejného hesla identické. Ale jsou různé!
Asi je to nějaká blbost, ale může mi to někdo objasnit???

Díky

Jakub Kocourek

Je to proto, že ten příkaz openssh sha soubor vypíše na stdout i jméno souboru. Zkus místo toho

cat soubor|openssl sha

A dnesni cenu za zbytecne vyvolani prikazu cat ziskava....:-)

Clanek mne zaujal, skoda, ze nektere terminy se vysvetlily az v diskuzi. Mozna mohly byt jiz v clanku... Autor ma clanky v CHIPU ctivejsi ... Bud to podle mne trochu odbyl nebo to vznikalo ve spechu... Nicmene diky. Pomohl mne se trochu v tom hash BOOMu zorientovat.

Díky za kritiku, beru ji. Článek nevznikal ve spěchu, ale spíše se zavřenýma očima, takže semtam jsem něco napsal tím, že mi upadla hlava na klávesnici :-). S editací mi pak ráno pomohla jedna sympatická "rooťanka", jinak by článek nevznikl. (Nejen z toho důvodu jsem odmítl honorář.)

Jsem ale rád, že to něčemu pomohlo. Chtěl bych ještě upozornit na věc, která zapadla - aby se aplikace psaly tak, že kryptografické nástroje půjdou jednoduše vyměnit třeba konfigurací nebo přihráním modulu, ale bez významného zásahu do ostatního SW/HW (samozřejmě, že to zakládá možnost útoků, ale tomu se nevyhneme nikdy).

Vývoj kryptografie ukázal, že se nemůžeme spoléhat na jeden nástroj, ale brát každý kryptografický nástroj jako dočasné řešení s vědomím, že "tenhle nástroj je teď bezpečný, protože jeho brejknutí teď je příliš složité/výpočetně náročné/nemáme k tomu teorii apod., ALE zítra tomu tak být nemusí". Je to přesně případ MD5. Půda na její nahrazení není příliš připravena.

O drtivé většině POUŽITELNÝCH a používaných moderních kryptografických nástrojích (v IS/IT) bohužel od roku 1949 víme s jistotou jen jediné - že nikdy nemohou být tak bezpečné, jak bychom chtěli, tj., že jednoho dne mohou být s klidem brejknuty. Proto je potřeba přijmout onu modularitu a vyměnit ji za důvěru a bezstarostnost. V tomhle světle je možná dobré vidět i problém ověřování pravosti kernelu.

Nasli jsme teda kolizi. Jak, je uz celkem jedno. Ted problem. V roce 2002 jsem podepsal nejaky dokument (smlouvu). V roce 2008 byla algoritmus tvorici HASH zpochybnen a nasledne se prestal pouzivat. Jak asi dopadne soudni spor v roce 2012 o pravosti smlouvy?
Ptam se v dusledku zavadeni e-govermentu apod.

Bude záležet na předložení technických i netechnických důkazů. Daný problém zanechá spoustu důkazů počítačových, věcných, budou tam svědectví lidí apod. Takže pouze finta s haší by zřejmě neprošla. Soudy věří spíše faxu než elektronickému podpisu. Problém nalezení klizí a jeho zneužití je spíše problémem "sítě" a "automatů" (zkontrolují haš, vykonají daný kód atd.).

Prave v dokazovani vidim problem. Ty pocitace z roku xy uz nebudou, ... Svedci (casto tvrzeni proti tvrzeni), ale uznavam, ze HASH v tom bude mozna nevine.
Takze je spise problem na strane ruznych automaticky generovanych rejstriku (zivnostensky, obchodni, vypis z katastru, z rejstriku trestu,...)?
Nebo jen pouze nejakych protokolu (nizsi vrstva)?

Dovolim si vstoupit do diskuze - a reagovat na otazku, jak to bude se "statnimi urednimi elektronicky podpesanymi dokumenty - rejstriky atd.)" a upozornit na jeden fakt.
Pokud jde o podpisove schema zalozena na MD5, pak neni v CR pro prostredky pro bezpecne vytvareni a overovani zaruceneho elektronickeho podpisu povoleno (viz priloha č.2 k vyhlasce c.366/2001 Sb.). Obdobne je to v cele EU - nebot se zde vychazi z doporuceni EESSI (Algorithms and Parameters for Secure Electronic Signatures). V tomto doporuceni jiz MD5 neni. Algoritmy zde uvedene budou pouzivany do roku 2005 pro podpis a 2006 pro overovani podpisu. Pote bude provedena revize dopruceni a vznikne soupis novych doporucenych podpisovych schemat. Dokument o kterem pisi najdete napr zde : http://crypto-world.info/normy/index.htm

problémů je spousta, hašovací funkce jsou prolezlé všude možně (což je také dobře, je to výborný nástroj, jedna z klíčových myšlenke moderní kryptogrfie, tak ať nám pěkně slouží),
nejvíce pochopitelně v protokolech, internetu, sítích, bankovních aplikacích,...

nicméně praktické soudní spory na bázi kolize haše opravdu neočekávám

i když svého času nějaká stará paní vyhrála v Německu spor o neoprávněný výběr kartou z jejího konta díky tomu, že ta její banka používala DES v době, kdy byl na světě DES-Cracker

to bych považoval za výjimku, potvrzující pravidlo

Dekuji za pekny clanek i za ucast v diskuzi!

Je dulezite problemy popisovat, zverejnovat a hledat reseni.

Je to doplnění velmi dobré úvahy Milana Keršlágera. Jaká je teda složitost vytvoření dvou různých kernelů se stejnou kontrolou? (Problém vytvoření kolidujícího kernelu k již existujícímu "cizímu" kernelu je mnohařádově složitější úloha) Berme kernel jako libovolný SW, jehož pravost je ověřena otiskem MD5. Číňani ukázali, že s největší pravděpodobností (všichni tomu věří) mohou hledat kolize při libovolném IV. Napíšu dva kernely, vše podstatné je balík SW "na začátku zdrojáku". Liší se jen na konci - jeden třeba končí nějakým komentářem (označme REM), kdežto druhý tam má soft - zadní vrátka. Při hašování u obou kernelů dojdeme až k hranici REM, kde jsou zatím oba kontexty (mezivýsledky hašování) stejné. Tenhle mezivýsledek je vlastně nový IV pro čínskou metodu. Teď teprve budeme hledat vhodný obsah REM a škodlivého kódu v druhém kernelu, které kolidují při tomto IV. Máte pravdu, že je tam mezikrok komprimování, čili úloha je o tento krok složitější. To hlavní - balík softu před rozdílem, má ale stejný komprimovaný začátek i startovní bod pro hledání kolize. Ještě bych se snažil přinutit komprimační program tak, aby něco nekomprimoval. Neznám tar.gz, ale třeba u winzipu to jsou služební hlavičky souborů. Tím lze vytvořit prostor pro variabilní vatu, potřebnou k nalezení kolize. Neříkám, že je to jednoduché, ale takhle bych na to šel.

> Neznám tar.gz

Taru se to netýká, ten jen balí více souborů do jednoho a pro jeho kompresi si za běhu volá gzip, bzip2, compress nebo něco jiného. Gzip umí ukládat data bez komprese, a snad to i přepíná automaticky (řádek *file_method = STORED; v trees.c).

Každopádně díky tomu, že se volba způsobu komprese týká celého archívu a ne jednotlivých souborů jako u .zip, tak by nárůst délky archivu (pokud by nebyl komprimovaný) byl nápadný.

Tohle je komplikované kompresí. Ale jak je to třeba u Wordového dokumentu?
1) Firma vytvoří smlouvu.
2) Zákazník elektronicky podepíše (podepisuje hash dokumentu, je to tak???)
3) Firma změní dokument a na konec souboru přidá pro Word nečitelné nesmysly, které upravují hash na hodnotu v době podpisu.
Je toto možné udělat jednoduše v řádu hodin??? Objevili Číňani jen metodu jak vytvořit dva nesmysly se stejným md5sum, nebo jak dopočítat k existujícímu dokumentu druhý změněný, tak aby hashe kolidovaly???

Dál k internetovému bankovnictví:
Je možné, aby byl tedy po cestě mezi serverem a klientem změněn např. příkaz k úhradě, dopočítán md5sum a paket znovu šifrován veřejným klíčem banky a odeslán serveru??? Na to neni ani porřeba obstarat stejný certifikát jako má banka ne? Zpět už přece komunikuje banka a ta je důvěryhodná?! Prostě se jen po cestě vytvoří jiný příkaz se stejným md5, jako měl u klienta? Šlo by to???

Poslední věc:
Jestli tomu rozumím, tak prolomení sha-1 by bylo možné dosáhnout také, jen na to zatím nikdo nenašel vhodný algoritmus???
Je možné tedy v případě nalezení JEDNÉ kolize (třeba čistě náhodné), vytvořit právě tento algoritmu fungující obecně???

Díky za odpověď

Jakub Kocourek

>Ale jak je to třeba u Wordového dokumentu?
> 1) Firma vytvoří smlouvu.
> 2) Zákazník elektronicky podepíše (podepisuje hash dokumentu, je to tak???)
> 3) Firma změní dokument a na konec souboru přidá pro Word nečitelné nesmysly,které
> upravují hash na hodnotu v době podpisu.
> Je toto možné udělat jednoduše v řádu hodin??? Objevili Číňani jen metodu jak vytvořit dva nesmysly se stejným md5sum, nebo jak dopočítat k existujícímu dokumentu druhý změněný, tak aby hashe kolidovaly???

V současné době je pouze popsáno to, jak vytvořit dva binární nesmysly se stejnou haší. Je to jednoduché a v řádu hodin.
V tento okamžik ale nelze s jistotou říci, že lze udělat body 1,2,3, protože tu metodu neznáme, nezveřejnili ji. Z bočních informací lze však usuzovat, že po jejím zveřejnění toto s určitou pravděpodobností možné bude. Pak by to také bylo jednoduché a v řádu hodin.

>Dál k internetovému bankovnictví:
Je možné, aby byl tedy po cestě mezi serverem a klientem změněn např. příkaz k úhradě, dopočítán md5sum a paket znovu šifrován veřejným klíčem banky a odeslán serveru???

Tohle je podobný problém jako s tím wordovským dokumentem, zkomplikovaný navíc šifrováním toho příkazu/dokumentu. Podstatné je, že tvůrcem příkazu je oprávněný uživatel a současně útočník. Může tedy poměrně dlouho bádat nad tím, jaký příkaz má vytvořit a současně aby byl schopen vytvořit smysluplný (stejně dlouhý) druhý příkaz se stejnou haší md5. V současné době funguje útok tak, že obě kolidující zprávy se liší jen v několika bitech. Pokud bude to spojení šifrováno proudovou šifrou (bývá tomu tak, RC4), stačí onu bitovou změnu provést na paketu se šifrovým textem (myslím, že nad tím už není kontrola integrity, ale kdyžtak mě opravte). Místo původního příkazu, zabezpečeného haší MD5 tak do banky putuje jiná zpráva (po odšifrování lišící se o pár bitů), se stejnou haší, tedy bude uznána jako autenticky odeslaná klientem. Proč by to ale klient dělal? Mohl takovou zprávu poslat rovnou. Takový útok by měl smysl, pokud by původní příkaz nebyl jeho, ale někoho jiného. Pak ale útočník nemá možnost kolidující zprávy vyrábět, musel by hledat kolidující zprávu ke zprávě jemu dané (vytvořené jiným klientem). To je jiná a v současné době neřešitelná úloha, jak bylo výše v diskusi už vyjasněno (hledání kolidující zprávy ke zprávě již dané).

>Jestli tomu rozumím, tak prolomení sha-1 by bylo možné dosáhnout také, jen na to zatím >nikdo nenašel vhodný algoritmus???

Prolomení hrubou silou možné je, ale nikoho nezajímá, protože je drahé a trvá příliš dlouho, rychlejší algoritmus nebyl nalezen a zatím nejsou signály, že by něco z publikovaných výsledků mělo přímý vliv na bezpečnost SHA-1.

>Je možné tedy v případě nalezení JEDNÉ kolize (třeba čistě náhodné), vytvořit právě >tento algoritmu fungující obecně???
Zatím rozhodně ne.

Pane Klimo, muzete se vyjadrit k nasledujicimu tvrzeni p. Patocky:
-------------------
Představ si, že uděláš nějakou zprávu, která nemá žádný význam (třeba text A: "následující byty nemají smysl: " a druhou, která význam má (třeba text B: "dlužím panu X 50000Kč a následující byty nemají smysl: ". Pak vezmeš inicializační vektor po projití první zprávy hashovací funkcí, inicializační vektor po projití druhé zprávy hashovací funkcí a na základě algoritmu najdeš kolizi. Pak vezmeš text A připlácneš za jeho konec nalezenou kolizi a dáš to někomu podepsat (ten to podepíše, neboť je to neškodné tvrzení). Pak vezmeš text B a připlácneš za něj druhou část nalezené kolize, a máš podepsanou zprávu, kterou původce podepsat vůbec nechtěl, ve které tvrdí, že ti dluží 50000Kč.
-------------------
Pokud je to realne, tak sebeslabsi algoritmus na nalezeni kolize ma fatalni dopady (pro MD5)
Dekuji

V současné době je pouze popsáno to, jak vytvořit dva binární nesmysly se stejnou haší. Je to jednoduché a v řádu hodin.
Až Číňani zveřejní postup, myslím, že půjde udělat právě to, co říkáte.

Text se podepisuje tak, že se podepíše ohraničená textová část, tj. hash se počítá z použitých znaků (písmen) a ten hash se pak zašifruje, převede do čitelné podoby (ASCII) a přidá za text. Celé se to pak dá zkopírovat na kopírce beze ztráty podpisu. Problémem (při přepisu zpět do elektronické podoby a ověření) jsou neviditelné znaky (mezery, entery, tabelátory). Tohle najdete třeba v textové elektronické poště. Když podepíšete soubor, tj. přidáte k danému souboru (třeba Word.doc) další soubor s digitálním podpisem (signaturou), počítá se do hashe i neviditelný "plevel" (tj. třeba informace o formátování). Do těch by se kolize dala doplnit snadněji. Ale je z toho snadné východisko - stačí podepsat dvakrát s užitím různých hashů nebo třeba dvěma osobami, podruhé včetně prvního podpisu. Obtížnost nalezení kolize bude násobkem jednotlivých obtížností a pokud NEpoužijete jasně profláknutý hash, tak se dostanete za hranici zneužitelnosti v rozumném časovém horizontu.

BTW: stejně se mi jako útok na digitální podpis zdá jednodušší krádež privátního klíče a heslové fráze. Ve Windows je to s trojským koněm triviální. Už se těším na první soudní spory ohledně zneužití kradeného klíče :-), protože trojan není (profláknutý) vir a antivir (jako metoda "spolehlivé ochrany") ho tak nenalezne.

Co se tyce klasickych algoritmu je jen otazkou casu kdy bude vytvorena univerzalni metoda prolomeni jakkoliv silneho algoritmu (kvantove pocitace a spol.).

Skutecnym resenim aspon prozatim je kvantova kryptografie, ktera uz je vic realitou nez by si vetsina lidi myslela, viz. www.magiqtech.com

Jestli je to ta vec, o ktere jsem slysel i ja, tak mi unika, jak se tim da podepisovat.

velmi pěkná otázka

s nastupem teto technologie elektronicky podpis ztraci svuj vyznam, zjednodusene receno data se daji prenest jen k brane ktere patri, ale samozrejme vzhledem k cenam techto technologii (v nejakem souvisejicim pdf jsem zahlidl 38.000 $) je a jeste nejakou (pravdepodobne dlouhou) dobu bude tahle technologie dostupna nejvetsim firmam, bankam atd.

Takže narovinu: Až Číňani zveřejní svůj algoritmus, bude md5sum úplně nanic, protože změnit soubor s takovým hashem bude stejně jednoduché jak Caesarova šifra :) Je to tak?
To se týká lokálních souborů. Ale co tedy internet? Vidíte vážnější problémy v komunikaci se servery bank pomocí md5sum + šifrování des. Nejsem v tomhle žádný profesionál - můžete mi vysvětlit co vlastně probíhá při takovéhle komunikaci s bankou (md5 + des)?
Jak dlouho podle vás může vydržet sha-1 jako "bezkolizní" (tím myslím bez nalezení algoritmu pro získání kolize na libovolném dokumentu)?
Nejprve to vypadalo docela nevinně, ale ten drobný rozdíl ve dvou .bin souborech a stejný md5sum je děsivý! Vždycky jsem si myslel, že kolize může nastat jen u zcela rozdílných dat, ale tady jde o změnu v jednotkách bajtů.

Až Číňani zveřejní postup, myslím, že nastane teprve pěkná mela v interpretaci, co s tím lze udělat a) pro již napadené haše, b) pro opory typu SHA-1,256,384,512,224, na něž se spoléhá.

Třeba to, co pustili, je jen odvar z toho, co mají, a chtěli na konferenci Crypto 2004 ukázat, na čem pracují, aby jim doma přihráli ještě nějaké peníze na pokračování výzkumu.

Děsivé je to, že se jedná dokonce o změny několika bitů, že je to rychlé a že to nebude konec jejich výzkumu.

Proto znovu opakuji: nevěřte kryptologům. Stavějte systémy tak, jakoby kryptografické mechanismy platily jen omezeně a mohly se snadno vyměňovat.

Pro posouzení problému šifrování s md5+des je nutno mít konkrétní případ, takhle to nejde říci. Lze jen říci, že oba dva mechanismy nejsou považovány za bezpečné. Lze s nimi vystavět leccos, ale bude z toho vždycky koukat nějaký průšvih.

Na SHA-1 ještě nějakou dobu sázím. Dávám jí tak šest let.

Konkretnim pripadem muze byt https://www.servis24.cz Spravoval by jste ucet u teto banky po internetu? :) Je to zaludna otazka, ale ja ani nevim jak takovyhle prenos funguje, takze to tezko posoudim. Proste to pouziva md5 + des a ja bych rad vedel, jestli prave prekonany md5 muze narusit (realne) bezpecnost prenosu.

Je to záludná otázka. Vy nevíte jak takový přenos funguje a já to také nevím. Já si ale dokonce myslím, že to neví ani moje banka (neříkám, která to je). Já ten problém řeším tím, že při každé platbě k tomu musí ještě být použit autentizační token (kalkulátor). Přesto, že to považuji za riziko (tady vidíte paranoiu), jsou pro mě výhody větší, než nevýhody.

V bance (a nejen mojí) tyhle problémy řeší tiskoví mluvčí a vzhledem k problémům a rizikům banky je tohle pro management naprostá prkotina, kterou je potřeba jenom shodit ze stolu (řeší hlavně problém, jak vydělávat peníze). Když jsme ukázali prolomitelnost SSL, tisková mluvčí jedné velké banky řekla cca toto: útok na SSL nám nehrozí, protože my máme naše komunikace chráněné pomocí bezpečného certifikátu firmy Verisign (překlad ... pomocí SSL).
Bankovní systémy jsou tak složité, že je zázrak, že to drží pohromadě. Také bych nerad někde z boku vyndaval berličku a měnil jí za jinou. Mohlo by to pak spadnout celé. Neříkám, že nevěřím internetovému bankovnictví, nevěřím jenom tiskovým mluvčím.
Dál je potřeba to nestavět jenom technicky - prolomením DESu elektronické bankovnictví také neskončilo a neskončí ani prolomením RSA, jen se to bude muset řešit, až to nastane. Dalším faktorem je to, že příslušný útok musí někdo provést, a to zcela konkrétně, k tomu je potřeba hodně znalostí a věcí a nakonec ten nepříjemný okamžik, kdy si jdete vybrat z konta peníze a oni Vám k tomu dají navíc ještě náramky. Proto snad to elektronické bankovnictví přežijeme.

Zpět ke kombinaci md5+des. Pokud to bude md5+RC4, vidím tady určitou možnost, kterou jsem popsal výše v jiné odpovědi, u des a tripledes (a obecně blokových šifer) by to bylo nešlo tak jednoduše, jak je to popsáno.

Je to záludná otázka. Vy nevíte jak takový přenos funguje a já to také nevím. Já si ale dokonce myslím, že to neví ani moje banka (neříkám, která to je). Já ten problém řeším tím, že při každé platbě k tomu musí ještě být použit autentizační token (kalkulátor). Přesto, že to považuji za riziko (tady vidíte paranoiu), jsou pro mě výhody větší, než nevýhody.

V bance (a nejen mojí) tyhle problémy řeší tiskoví mluvčí a vzhledem k problémům a rizikům banky je tohle pro management naprostá prkotina, kterou je potřeba jenom shodit ze stolu (řeší hlavně problém, jak vydělávat peníze). Když jsme ukázali prolomitelnost SSL, tisková mluvčí jedné velké banky řekla cca toto: útok na SSL nám nehrozí, protože my máme naše komunikace chráněné pomocí bezpečného certifikátu firmy Verisign (překlad ... pomocí SSL).
Bankovní systémy jsou tak složité, že je zázrak, že to drží pohromadě. Také bych nerad někde z boku vyndaval berličku a měnil jí za jinou. Mohlo by to pak spadnout celé. Neříkám, že nevěřím internetovému bankovnictví, nevěřím jenom tiskovým mluvčím.
Dál je potřeba to nestavět jenom technicky - prolomením DESu elektronické bankovnictví také neskončilo a neskončí ani prolomením RSA, jen se to bude muset řešit, až to nastane. Dalším faktorem je to, že příslušný útok musí někdo provést, a to zcela konkrétně, k tomu je potřeba hodně znalostí a věcí a nakonec ten nepříjemný okamžik, kdy si jdete vybrat z konta peníze a oni Vám k tomu dají navíc ještě náramky. Proto snad to elektronické bankovnictví přežijeme.

Zpět ke kombinaci md5+des. Pokud to bude md5+RC4, vidím tady určitou možnost, kterou jsem popsal výše v jiné odpovědi, u des a tripledes (a obecně blokových šifer) by to bylo nešlo tak jednoduše, jak je to popsáno.

Po přečtení článku a diskuze bych se rád pozeptal: Došlo k prolomení MD5, ale vzhledem k tomu, že se jedná spíše o teoretický problém a tím, že praktická kryptologie není na úrovni teoretické(na mnoha místech) znamená (nezveřejní-li se něco nového), že problém je stanoven do blízké budoucnosti a musí se s tím počítat, ale v současném stavu není očekáváno nějaké citelné narušení/prolomení kombinací prostředků používajících výše zmíněné algoritmy pro příliž velkou složitost ?

První část není tak. Pro digitální podpisy (upravené legislativou) je MD5 nevyhovující a musí být ze schémat digitálních podpisů vyloučena - tady ten přínos není pouze teoretický.

Druhá část - tady máte pravdu. Nemohu ale vyloučit, že někde jsou ty systémy tak špatně postavené, že by to tam nešlo využít (asi víte jak to chodí v praxi, že ...).

Je to tam nejake rozhazene. Jak to ma byt doopravdy?

Dávám pro jistotu kus z kontrolního programu na tu mojí stránku o kolizích http://cryptography.hyperlink.cz/2004/kolize_hash.htm.
Jsou tam datové struktury z C.

link nefunguje, protoze jsem tam zapomnel tecku na konci, takze bez tecky:

http://cryptography.hyperlink.cz/2004/kolize_hash.htm

a primo link na ta data je

http://cryptography.hyperlink.cz/2004/kontrolni_data_md5.htm

Jsem rad ze diskuze prinesla daleko vice informaci nez clanek (neberte to jako kritiku, od toho tu diskuze jsou :-) ) Myslim ze to hlavni jsem pochopil. Jen jeste jedna doplnujici otazka:
Budu-li mit bezne pouzivany certifikat (treba od ICA nebo Versign, to je fuk od koho), napisu mail (napriklad v outlooku ale to je asi taky jedno v cem) a "standardne" ho podepisu tim certifikatem, co se v ten okamzik pouzije za algoritmus (popr algoritmy)? Udela se ze zparvy MD5? nebo nektere SHA? nebo je to uplne jinac?
Diky za odpoved...

Ty algoritmy je většinou možné nastavit v příslušných softech, ale někdy to ovlivnit nejde. Lidi kolem certifikačních autorit a mailových klientů vám určitě poradí k vašemu konkrétnímu softu. Jisté je, že jakmile máte nainstalovaný certifikát, tak se vás to už na nic neptá, vypočte haš nastaveným algoritmem a podepíše privátním podpisovým klíčem. Takže prozkoumejte vaše nastavení nebo u odeslaného mailu si dejte zobrazit podpis/certifikát, tam je to uvedeno.

VK z Dekrosu, kterého jsem tak často vídával na stránkách CHIPu, když jsem ho ještě četl...

...tehdy mě dost štvalo, že CHIP věnuje tolik prostoru takovým nezáživným (rozumněj odborným) věcem...

K věci... hashovací algoritmus přece ve své definici připouští kolize, tak proč se všichni ohání nějakým "prolomením"?

ááááá to už tady bylo na začátku diskuse...
zkuste tam zabrousit

P.S.: Chipu jsem vděčný za prostor, který mi poskytoval neuvěřitelných deset let.
Když jsem přinesl první článek tehdejšímu čerstvému šéfredaktorovi Milanu Louckému, myslel jsem, že napíšu tak tři články. Pak to vyšlo přes sto, ale nikdy jsem to nepočítal. I když tam byla výborná parta, neměl jsem žádnou protekci a bylo to vždycky v rovině tady je článek, jestli chcete, berte nebo ne. Nechávat někoho publikovat deset let není obvyklé. Nikdy předtím jsem nic nepsal (byl jsem ve státní správě), a tak jsem byl taky překvapen, že moje články se po několik let držely na 1-2-3. místě ve čtenosti podle anket Chipu. Postupem času (poslední roky) tak bylo možné přejít ke složitějším věcem, které nebyly jednoduchým čtením do tramvaje. No a na tom to taky skončilo, což je logické.
Jsem moc rád, že články v Chipu přivedly ke kryptologii nové lidi v době, kdy tady nebyl žádný jiný zdroj. Teď už je to snazší, neb se kryptologie začíná vyučovat na MFF UK a informací je na internetu kolik chcete.

Všem v Chipu, kteří se mnou spolupracovali, tímto děkuji a držím jim i časopisu palce. Milanu Louckému díky za to, že mě naučil, jak lze článek zkrátit na polovinu při zachování informační hodnoty a ještě vylepšit jeho čitelnost, Miloši Helclovi díky za precizní redaktorskou práci a novinářskou profesionalitu.

Kolize se sice připouští, ale ty jako uživatel bys neměl jakýmkoliv způsobem efektivnějším než brutální silou najít dva různé texty, které mají stejný hash. V okamžiku, kdy jsi schopen toto provést, ztrácí funkce své opodstatnění a stává se nedůvěryhodnou.

Bohužel(dík) byl očividně tento způsob nalezen a časová náročnost je více než extrémně krátká. Proto jsou tyto funkce nyní určené do skript a na propadliště dějin.

(Doufám, že jsem nic nepřevrátil)

Tak pani, neviem kde je problem a ci to vobec niekto testoval, ale mne osobne to nesedi.

Zobral som program MD5SUM, funkciu md5() v PHP, dokonca som si vykopiloval md5.c podla zdrojakov v prislusnom RFC (http://www.networksorcery.com/enp/rfc/rfc1321.txt), stale dostavam nasledujuce vysledky:

Prvy hash: f6e44db01f60a35bf2794cee6fee575a
Druhy hash: 54607d90638616b2283638049e936aa5

A teda nie spolocny hash: a4c0d35c95a63a805915367dcfe6b751

Kde je problem?

Aha, tak uz viem kde je problem, uz to funguje. Vyraz retazec nebol v clanku pouzity prave najstastnejsie.

Pre ostatnych, ktori by si to chceli vyskusat:

http://cryptography.hyperlink.cz/2004/kontrolni_data_md5.htm

Odpověď nautiluZ-ovi na dotaz z 28.8:
Důvěrnost je jenom jedna z kryptografických služeb. Nestačí pokrýt všechny současné požadavky. Například je potřeba také integrita dat, autentizace dat a entit, nepopiratelnost.

(Když už jsem to jednou vypotil, tak viz přednáška Symetrická kryptografie I, MFFUK, kap.3, na http://adela.karlin.mff.cuni.cz/~tuma/nciphers.html.).

Kontrolní otázka:
Předpokládejme, že kvantová kryptografie už není tak drahá. Jak prakticky pomocí ní zajistíte, abychom si byli jisti, že program, který chceme nainstalovat, pochází ze zdroje, kterému důvěřujeme?
Dnes to zajistí digitální podpis a certifikáty.

Americký standardizační úřad NIST vydal prohlášení k současným výsledkům v oblasti kryptoanalýzy hašovacích funkcí. Jeho plné znění naleznete na http://csrc.ncsl.nist.gov/hash_standards_comments.pdf i na hlavní stránce, věnované kolizím http://cryptography.hyperlink.cz/2004/kolize_hash.htm .

Výtah:
- SHA-1 zůstává bezpečná.
- Doporučuje se používat třídu funkcí SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512).
- Do roku 2010 se předpokládá opuštění i SHA-1 a přechod na SHA-2.
- Do roku 2010 se předpokládá opuštění kryptografických technik, majících složitost max. 2^80 operací, to znamená mj. také Skipjacku s 80 bitovým klíčem (určen k ochraně dat do stupně Tajné včetně).
- Úřad blahopřeje kryptoanalytikům a podporuje takové výsledky, zejména by rád, aby se pozornost soustředila na SHA-256 a SHA-512.

Mimo záznam: Doufejme, že Číňani nedosáhnou příliš vysokého stupně soustředění, aby nám to tak nějak nepropálili celé :-)

Oni uz to cele propalili pred 5 lety, jen to ted po kapkach uvolnuji aby z toho meli taky propagandisticky efekt :)

Jak reagovat na uvedená zjištění? Co konkrétně nějak jednoduše řečeno s tím dělat?

Jednoduše řečeno:
- přestat používat MD5, SHA-0, RIPEMD a HAVAL-128 tam, kde to můžete ovlivnit
- tam, kde to nemůžete ovlivnit, alespoň upozornit (pokud je to možné), že používají brejknuté nástroje
- ve vlastních aplikacích se nezdržovat s přechodem MD5 na SHA-1, ale rovnou přejít na SHA-256 nebo SHA-512 (linky na popisy a zdroje SHA-256/512 viz hlavní stránka o haších http://cryptography.hyperlink.cz/2004/kolize_hash.htm )
- pamatovat si, že MD5 by se už neměla používat zejména v aplikacích digitálního podpisu

- s nadsázkou: modlit se, aby Biham, Joux a Číňani neposlali i SHA-256/512 na smetiště dějin a aby NIST vypsal nové výběrové řízení na hašovací funkci "nového typu" (SHA-x jsou založeny na podobných principech nebo podobné "třídě funkcí" jako MD-y, i když jsou složitější), ani jedno, ani druhé ale asi nepřichází v úvahu

Protože dotaz zapadl v diskusi, odpovídám takto na konci.
Není známo nic, co by nasvědčovalo, že se nalezené kolize týkají také Tigeru. Domovská stránka Tigeru je na http://www.cs.technion.ac.il/~biham/Reports/Tiger/
a pokud se něco Tigeru týká, mělo by to tam být. Tak to slibují autoři Tigeru, uznávaní kryptologové a univerzitní profesoři Anderson a Biham.

Myslite, ze Tiger je dostatocna nahrada (z hladiska bezpecnosti, nie rychlosti) za MD5? Ja verim, ze ano, ale zaujima ma Vas nazor. Dakujem.

Tiger je dostatečnou náhradou za MD5, ale má to také své nevýhody. U Tigeru si můžete zvolit až do 192 bitů hašového kódu, protože má 192 bitů výstupu. Tento výstup se dá krátit na 128 (pak lze v aplikacích zaměnit za MD5) nebo 160 (jako SHA-1) nebo nejlépe plných 192bitů . Složitost nalezení kolizí narozeninovým paradoxem je při použití 192bitové haše 2^(192/2) = 2^96, což je DNES dostatečné. Tiger je robustní a stojí za ním skvělí kryptologové.

ALE:
Při použití 128bitového Tigeru je ale složitost nalezení kolizí narozeninovým paradoxem (tedy zde hrubou silou) pouze 2^64, což není považováno dnes za bezpečné.

Proto je vhodné použít Tiger-192, což není v aplikacích z hlediska délky haše kompatibilní s MD5. Když už budeme nahrazovat nekompatibilně, přimlouval bych se za delší haš. Časem bude 192 bitů málo z hlediska složitosti útoku narozeninovým paradoxem. Proto je dobré se zamyslet se nad třídou SHA-2 s délkou kódu minimálně 256 bitů. Moje volba by byla SHA-512 a použít potřebnou délku hašovacího kódu (n bitů) podle bezpečnosti, kterou chci docílit (2^(n/2)), byť by to bylo 256 bitů nebo dokonce oněch krátkých 128 bitů tam, kde je NUTNO nahradit MD5.

Opakuji myšlenku z hlavního článku, že v případě brejknutí jakéhokoliv algoritmu (nejen haše) musí být systémy začít stavěny tak, aby šly jednoduše překonfigurovat na jiné. Proto je také dobré začít používat například SHA-512 s tím, že parametrem aplikace bude délka haše, která se z jejího výstupu 512 bitů použije. Tím se připravíte jednak na výměnu hašovacích funkcí a jednak na možnost mít až 512 bitový výstup.

V cisle 9 e-zinu Crypto-world (viz http://www.crypto-world.info, registrace zdarma) vysla chybna interpretace utoku na hasovaci funkce. Pokusil jsem se ji strucne vysvetlit v newsech na http://crypto-world.info/news/index.php?prispevek=639, v cisle 10 e-zinu se k tomu vratim podrobneji.

Jako laik bych udělal dva hasche

1. jeden normálně
2. druhý pro text psaný pozpátku

ahoj
md5: jdshgkfjksdfhgksh

joha
md5.!r: kshufghkjghruihgi

Najít kolizi pro dva hashe by už problém byl, né?
:)

Napište mi podněty.. rád se přiučím.

A co tak pouzivat lepsi standard pre elektronicky podpis? Napriklad:

Dokument sa skomprimuje vhodnym algoritmom (vsetky bity vystupu musia mat vplyv na obsah a vstup nesmie byt rozdelovany na nezavisle komprimovane bloky). Potom sa vezme dlzka dekomprimovanej spravy v bajtoch, dlzka komprimovanej spravy v bitoch (nie bajtoch ale BITOCH), hash dekomprimovanej a hash komprimovanej spravy a pouzije sa to ako obsah zasifrovaneho bloku pre digitalny podpis.

Pri overovani podpisu sa vezme spominany skomprimovany blok. Overi sa jeho hash, ak nesedi - "verification failed". Potom sa verifikator pokusi blok rozbalit, ak najde v komprimovanych datach chyby alebo sa pouzilo nespravne mnozstvo dat - "verification failed". Potom sa overi hash dekomprimovanej spravy a dlzky, ak nieco z toho nesedi - "verification failed". Inak "verification ok".

V pripade dokumentov typu zmluva by sa k poziadavkam pridalo aj to, ze dany subor musi byt textovy subor s ludsky citatelnym obsahom v UTF-8 kodovani (ziadne MS Word Document a podobne binarne kraviny so spustou ignorovanych bajtov vyuzitelnych na dotlacenie hashe ku kolizii) s tym, ze kazdy znak dokumentu musi byt zakodovany najkratsim moznym kodom. Pripadny pokus o manipulacie hashe bude odhaleny po prve preto, ze ho utocnik nema kam schovat a po druhe celkom urcite porusi UTF-8 kodovanie (v takom pripade kontrola podpisu prehlasi "verification failed").

Pouzitie takehoto standardu elektronickeho podpisu by mohlo umoznit predlzik klinicku smrt hashovacich funkcii o nejaky ten rok. Je totiz velky problem k danemu dokumentu vygenerovat iny dokument s tym istym podpisom, ktory by uvedenym "vyberavym" validatorom podpisov presiel bez uhony.

V podstate ide o to, ze k informacii v elektronickom podpise sa pridaju dalsie doplnkove data ktore verifikacnemu systemu umoznia sofistikovanejsiu kontrolu integrity dat.

Jako laik bych udělal dva hasche

1. jeden normálně
2. druhý pro text psaný pozpátku

ahoj
md5: jdshgkfjksdfhgksh

joha
md5.!r: kshufghkjghruihgi

Najít kolizi pro dva hashe by už problém byl, né?
:)

Napište mi podněty.. rád se přiučím.

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.

Coze?