Názory k článku
Nalézání kolizí MD5 - hračka pro notebook

Skvela prace...
...radsi si to ale rychle patentujte :D

Popis zatim nedavam k dispozici. Pokusim se nejdriv algoritmus urychlit.

No,rekl bych, ze udelat kryptoanalyzu hodne rozsirenyho a dulezityho hash algoritmu a najit v nem kolizi postupem, ktery muze doma reprodukovat kazdy, to je docela dost skvela prace. Tobe to mozna nic nerika, ale budes se chlapce divit, az ti nekdo rekne "tohle jste udelal vy, mame vas certifikat, MD5 souhlasi", to pak budes cumet a budes rad, kdyz budes moct rict, "ale tenhle clovek uz tehdy dokazal, ze MD5 neni spolehlivy, takze mate smulu, ale na zaklade MD5 mi nic nemuzete". Ja osobne smekam, protoze dokazat najit kolizi na nejakym silenym clusteru, to umi kazdej, ale dokazat to generovat na obyc domacim PCcku, to uz chce fakt hlavu na vymysleni postupu.

Akorat by me take zajimalo, jestli autori publikuji postup verejne, nebo ho budou schovavat jako cinani.

"proste sem si precet ten clanek, pak jeste jednou to pdfko a napsal sem sem co si o tom clanku a o autorovi myslim"

No právě. Představ si, že vlezeš na konferenci chirurgů o pooperační péči, zběžně prolistuješ bulletin, přistoupíš k mikrofonu a řekneš, že ty bys na tu ránu jako správný šaman plivnul a posypal ji hlínou. Je to tvůj názor, máš na něj právo, ale poženou tě ze sálu poklusem :-)))

Tak se nam predstav a ukaz co si publikoval, odborniku.

Pote, jak jsi tady sil do Vlastika Klimy, aniz bys projevil porozumeni problematice a trochu pokory pred uspechy jinych, Te mohu ujistit, ze kryptograficky clanek na Roota opravdu zadny nenapises bez ohledu na design.

Tak hele, Johanko, to byla naprosto konsturktivni kritika. Napis mi prosimte kde sem napsal co nepravdiveho nebo lziveho nebo kde sem nekoho urazel. Md5ka byla prolomena uz davno a program ktery nasel kolizi existuje uz dlouho. Tedy, rozhodne bylo z ceho cerpat. Tudiz si dost dobre nedokazu predstavit, z toho clanku, co vlastne za tu vanocni dovolenou vymysleli a co uz bylo vymysleno. Ale myslim ze by to mohl pan Klima rozlousknout ne?

A to ze "kryptograficky clanek na Roota opravdu zadny nenapises bez ohledu na design." to mam chapat jako jak? Pan Klima uz tu reagoval a nijak urazene se "netvaril". To jako myslis ze moje clanky sou neqalitni? To jako myslis ze by muj clanek o kryptografii nebyl pro roota dost dobry? Ja chapu ze ste s panem Klimou kamaradi, ale to sem nemoch vedet. Proc do toho xakru tahas osobni vztahy? Ses redaktorka a mas brat clanky pokud sou qalitni od kazdyho a ne jen od tech co sou ti simpaticky.

Ale abych nebyl tak zly, vis, ja se dneska rano probudil, a strasne se mi chtelo nekde rozpoutat nejakej flame a nekomu to poradne natrit a nekomu ukazat jak sem strasne "chytrej". Mozna se to nekoho dotklo, ale ja uz sem proste takovej. A dokonce nekdy dokazu rozjet tak urputou vymenu nazoru, ze az reknu jaxe menuju a to je potom mazec. Omlouvam se, prehnal sem to. Do smrti dobry?

člověče, chováš se jak děcko, co se za každou cenu musí vztekat. Obouváš se do lidí, kteří maj určitě lepší věci na práci, než se hádat o pitomostech. Co myslíš? A když tě pak plesknou přes ruku, tak se hned dáš do breku a z fleku rozbíjíš hračky. Má to význam?
Určitě tohle tvoje chování všichni ocení :-(

hele, uznavam ze predtim to byly zabomysi spory, ok, sem decko a sem ochoten se za to omluvit. Ok?

Ale johanka mi ted napsala, ze moje clanky nejsou hodny toho aby byly zverejnovany na rootu. Kurva ja sem sem napsal 7 clanku, stravil sem na nich spoustu hodin, kazdej den sem kontroloval kolik lidi uz si je cetlo a ona mi ted tohle napise? Beru si to velmi osobne!

Vsechno prekrucujes.

Ja nerekla nic o Tvych predchozich clancich, rekla jsem neco o urovni Tveho soucasneho diskusniho projevu. O Tvych predchozich clancich nikdo nediskutuje, jiste byly dobre.

Ale kdyz z nekoho vyroste prudic, nechceme od nej zadne *dalsi* clanky, stejne jako Ty jsi odmitl psat pro bilyho Roota - Root se zmenil, proto pro nej nechces psat, Ty ses taky zmenil, proto zase my nechceme, abys pro nas psal.
Driv jsi nemel reci a my byly cerny, tudiz Tobe nic nevadilo ani nam nic nevadilo.

Uz jsi to pochopil?
Tak dobrou noc, followupy nebudou, protoze rano ucim, a prosim ostatni, aby tuto diskusi oznacili za nekvalitni :)

Najdi pro svuj pozadavek oporu v autorskem zakone a rado Ti bude vyhoveno.

Kdyz napises clanek do papiroveho casopisu, tak ho snad muzes dodatecne vymazat?

Ja si treba o nejmenovanem papirovem (existuje jeste?) platku taky myslim ledacos, ale to, ze jsem tam neco napsala, byla proste moje chyba, se kterou ted uz nic neudelam, pouze to, ze ji nebudu opakovat. Proste autor napise clanek, platek da honorar, a tim to hasne, zbytek se ridi prislusnymi pravnimi predpisy.

Johanko a 1984 jsi necetla? Zalozte si na Rootu Ministerstvo pravdy a mas to. :-)

K tomu, co Smrtak pise, se vyjadrovat nebudu. Ale jak muzes zakazovat psat clanky na Roota nekomu, o kom vlastne vubec nevis, kdo je? Muzu take napsat neco jako neregistrovana Johanka Dolezalova (nic proti Tobe) a kazdy si bude myslet, ze se vedeni Roota zblaznilo :)

Protoze mam vzhledem k dalsim zkusenostem (nedavna flame v emailove konferenci autoru apod.) dostatek duvodu predpokladat, ze prispevky pise skutecne ten, za koho se jejich autor prohlasuje (resp. uz tehdy jsme meli dostatek duvodu ho v dalsim psani pro Roota nepodporovat a dnes se to jen potvrdilo).

No a tomu, aby nekdo nekomu zkazil povest, se da snadno predejit prave registraci :), kazdy bude vedet, ze neregistrovana johanka nejsem ja, pripadne jim to registrovana johanka vysvetli :)

kurna johanko, ja uz se s tebou nechci hadat. to ze semnapsal do konference autoru bylo proto, ze mne zajimalo co na to rikaji autori. A to ze vam kazim reputaci, tak tu si kazite predevsim sami. Kdyby se ostatnim novej root libil, myslis ze by to tu zustalo bez reakce? A kazdopadne si znovu precti:

http://www.root.cz/clanky/novy-root/

A mas pravdu, s tim psanim, je to pro vase dobro, uz pro vas psat nebudu design/nedesign.

Ale jinak se mi kazdopadne libis. Vcera vecer mi to pripominalo takovy ty sceny v americkejch filmech, jak se ty dva brutalne dohadaji a v tom nejvetsim vypeti se na sebe vrhnou a zacnou se zurive libat. Trochu sem se toho obaval, tak sem projistotu zamknul dvere :-)

Ovsem smrtak psal neregistrovany a tak, z pravniho hlediska, nemaji jeho prizpevky zadnou prukazni hodnotu, nechces-li se poustet do vysetrovani pres odesilatelovy ip adresu. To, ze uvedl link na sve clanky, nic neznamena. Priste mohu treba ja rozpoutat jine flame, vsechny nasrat az na pudu a pak se pochlubit cizim perim (linkem na neci clanky). Pokud mi to redakce zbasti, bude se opravdovy autor divit. :-)

Prosba
Moc bych vas chtel pozadat, abyste se pokusil neurazet Johanku. Nedela to tady za trest. Abyste ji presvedcil, zkuste neco napsat, a pod jinou identitou propasovat na root :-)

Program na generovani kolizi.
Kdybyste venoval tolik energie, co na tuhle diskusi, na precteni puvodniho clanku, mozna byste nenapsal, ze program, ktery nasel kolizi uz existuje dlouho. Existuje, ale je v cinskem suplicku. A vo tom to prave cele bylo. Ani ted neexistuje nikde verejne nic, co umi kolizi vygenerovat v rozumnem case. K cemu by byl pak byl projekt MD5CRACK?

Vanocni vyzkum
Nebyl to vanocni vyzkum, o vanocich to zacalo a trvalo dva a pul mesice. V patek 25.2. jsem rozeslal kolegum prvni programy. Pres vikend to jelo, v pondeli 28. byly kolize na svete. Mam z toho radost, protoze po letech jsem si skutecne udelal volno na neco, co zaujalo me, a ne zamestnavatele nebo klienta. A povedlo se to posledni den, co jsem na to mel cas, bylo to skutecne neuveritelna shoda nahod. V utery 1.3. jsem mel nastoupit do prace, a to jsem si pak mohl o nejakem vyzkumu jenom nechat zdat. Mozna pod dojmem tohoto vyvoje jsem tam napsal jak dlouho to trvalo. Nebylo to nutne. Lze to povazovat za vytahovani, uznavam.

ok, omlouvam se jesli sem se trochu moc rozohnil. Kazdopadne sem se nechtel pohadat s johankou, ale spis s Vami. Dost dobre nechapu proc do toho zasahovala.

Jakou hovadinu mas na mysli? Zkus byt trochu konkretnejsi. Kde sem napsal cokoli nepravdive? A s tim urazenim, z ceho tak soudis?

Dobry den,
jsem rad, ze odpovidate Vy a ne Johanka. Prvne bych se chtel zastavit nad parafrazi vyroku "At mas jak chces kvalitni clanek, stejne nevyjde". Neni to nahodou na skodu ctenaru Roota? Chapu, ze sefredaktor je jisty diktator, ale stejne si myslim, ze na tuto cenzuru mel nekdo reagovat...

K samotnemu clanku. Musim se zastat Ondry v urcitem smeru, tento clanek neni clanek v klasickem smyslu, nicmene spise jen takova anotace na odkazy pod clankem (vcetne stranky projektu). Roota ctou i lide, kteri o techto udalostech tolik nevedi a podle me by tam mohlo byt o pet odstavcu vic a clanek vic samostatny (to je muj osobni nazor).

A jeste jedna poznamka, ktera by mozna mohla byt take zajimava. To, ze program existuje jen v cinskem suplicku a ve vasem notebooku muze byt trosku dusledek neexistence patentu v tomto smeru. V nekterych oblastech jsou patenty primo skodlive (europatenty...), ale v nekterych oblastech zase pomahaji. Jakmile zverejnite algoritmus, mate smulu a kazdy ho muze pouzit, takze ho mozna radsi udrzite pod poklickou (v suplicku) a prodate hezky potaji a za velke prachy.

P.S.: Omlouvam se za stylistiku cestiny, ale dlouho jsem nic cesky nepsal.
P.P.S.:Takovy vyzkum udelat za dva a pul mesice, smekam.

Nic ve zlem, ale k cemu by takovy patent byl? To jako ze honem vsichni zacnou psat komercni aplikace na lamani md5 a prodavat je uzivatelum, kteri se ale vbrzku z nejakych nepochopitelnych duvodu od md5 odkloni, jen co nekdo navrhne neco lepsiho?

Dobry den,
jsem rad, ze odpovidate Vy a ne Johanka. Prvne bych se chtel zastavit nad parafrazi vyroku "At mas jak chces kvalitni clanek, stejne nevyjde". Neni to nahodou na skodu ctenaru Roota? Chapu, ze sefredaktor je jisty diktator, ale stejne si myslim, ze na tuto cenzuru mel nekdo reagovat...

K samotnemu clanku. Musim se zastat Ondry v urcitem smeru, tento clanek neni clanek v klasickem smyslu, nicmene spise jen takova anotace na odkazy pod clankem (vcetne stranky projektu). Roota ctou i lide, kteri o techto udalostech tolik nevedi a podle me by tam mohlo byt o pet odstavcu vic a clanek vic samostatny (to je muj osobni nazor).

A jeste jedna poznamka, ktera by mozna mohla byt take zajimava. To, ze program existuje jen v cinskem suplicku a ve vasem notebooku muze byt trosku dusledek neexistence patentu v tomto smeru. V nekterych oblastech jsou patenty primo skodlive (europatenty...), ale v nekterych oblastech zase pomahaji. Jakmile zverejnite algoritmus, mate smulu a kazdy ho muze pouzit, takze ho mozna radsi udrzite pod poklickou (v suplicku) a prodate hezky potaji a za velke prachy.

P.S.: Omlouvam se za stylistiku cestiny, ale dlouho jsem nic cesky nepsal.
P.P.S.:Takovy vyzkum udelat za dva a pul mesice, smekam.

A ja, mily Peto, znovu opakuji, ze nejde o blokaci "jakkoli dobreho clanku", nybrz o to, ze mam jistou predstavu o kvalite kryptoclanku autora, ktery zde projevil neznalost problematiky. A co se obecne tyce blokovani autoru, se kterymi se neda vyjit, treba s takovymi bratry Kulhavymi se taky neda vyjit, a prestoze jsou chytri a schopni, radi jejich clanky ozelime (byt o ne pripravime ctenare), protoze proste jeden dobry clanek za nekolik hodin hadek nestoji, opravdu ne, musi se zachovat nejaky pomer cena/vykon, abych mela cas i na neco jineho nez dohadovat se s konfliktnimi autory (treba na samotnou pripravu vydani). Nemluve o tom, ze casto se stane, ze vydame byt i kvalitni clanek od cloveka, ktery je znam jako prudic, a ctenari nam nadavaji (to je treba pripad Cijomla). Tam je proste (pravu kvuli Tebou zminovanemu blahu ctenaru a povesti serveru mezi nimi) nutne prihlizet i k osobni povesti autora a ne jen ke kvalite clanku.

Co se tyce smyslu clanku pana Klimy, ja samozrejme uznavam, ze to neni typicky rootovsky clanek, na druhou stranu tohle jsou veci, ktere se opravdu neodmitaji, a ja si skutecne velmi vazim toho, ze pro nas pise (ani nevim, cim jsme si to zaslouzili :)). A za ucelem nahledu do problematiky jsou u clanku uvedeny linky na clanky souvisejici.

Ze zasahuju do diskuse, to je moje prace, nebot bych rada autora odstinila od toho, co nevzniklo jeho vinou (napr. nastvani ctenaru nad bilym designem, ktere implikuje prudeni naprosto vsude), aby mel cas (a chut) reagovat na konstruktivni prispevky.

Johanko, ja te miluju a chapu te. Chces odstinila debatu od zmrsenyho roota aby vypadalo ze je vlastne vsechno v poratku. A ja ti zehnam, HALELUJA!

Sakra, preju vam hodne volneho casu a doufam, ze z toho zase neco psinezniho vypadne.

Hééééééézkýýýýýýý
To je lepší než kdyby to tu kdokoliv-jakkoliv obodoval
:-))

Posledni dobou nepisu casto do diskuzi, ale zde udelam vyjimku:

1. narozdil od http://eprint.iacr.org/2002/076, povazuji tohle za velmi zajimavy vysledek. Myslim, ze i pro pana Klimu to bude jeden z nejzajimavejsich radku v jeho zivotopise. Nezbyva mi nez pogratulovat. Pokud se nekdy objevi nejaky presnejsi popis algoritmu a celeho postupu reseni, rad si z nej prectu vse, na co budu se svou matematikou stacit.

2. pan Holecek je blb. Jeho chovani by mohlo omluvit, kdyby mu bylo mene nez 15 let. V opacnem pripade necht zvazi moznost ukoncit svuj zbytecny zivot.

ad1) Mate pravdu, pro sebe to povazuji za jeden ze "zaseku". Jsem sice v nalezani kolizi 3-6x rychlejsi nez Cinane, ale nejvic me tesi, ze jsem to udelal "na kolene", coz je typicka ceska vlastnost.

Prof. Wangova studuje kolize od roku 1996. Navzdory tomuhle memu lepsimu vysledku toho Wangova se svym tymem udelala radove vice nez ja, to bych chtel zduraznit.

A to i presto, ze hodlam metodu urychlit jeste o jeden rad. Doufam, ze uz brzo. Nejaky napad mam.

Rozumis kryptoanalyze nebo samanskym postupum, jako osetrovani ran slinami a hlinou?

md5 vznikol v roku 1991 vid. http://www.rsasecurity.com/rsalabs/node.asp?id=2253 takze tych 20 rokov je prehnane:-)

20 se zabyva kryptografii, ne MD5. Lidi vy fakt musite rypat do vseho :(
Zavist je v Ceskem lidu hodne zakorenena a uznat neci zasluhu? Blaznite?

Opravdu me pristup techto lidi hodne mrzi

Bože co je toto za kokota? To snad není ani možné?! - Ondřej Holeček - Měl by se léčit, nebo spíše ukončit svůj zbytečný život, jak už tady někdo psal...

Pokusim se tech 8 hodin jeste stlacit radove na minuty, pak bych to publikoval.

ta zpravicka uz tu vysla, i s odkazem na to PDFko :-)

Takhle se pry pisou odborne clanky. A autor asi odborne publikuje uz dost dlouho, aby byl dostatecne deformovan.

Psal jsem takhle prispevek na konferenci stylem, aby to pochopilo i moje devce a ona to fakt pochopila. Jenze vedouci mi to zkritizoval, ze takhle se pisou pohadky a ze to mam cele preformulovat do odborneho jazyka.

Dyslexie je porucha čtení. Dysgrafie je porucha psaní. Pro poruchu správného psaní se také někdy používá pojem dysortografie. No zkusím to po sobě párkrát přečíst, ale jelikož jsem taky postižený, stejně tam něco zůstane :-)

to koho tu vydieras tym ze si postihnuty? to je ciste tvoj problem!

Teda tady musim smeknout, uz par tvych prispevku (vlastne mozna vsechny) jednoduse nejsem schopnej pochopit. Hledam neco o zabezpeceni o kryptografii apod. Potom si ctu tuhle diskuzi. Docetl jsem ji az sem. Musis byt asi genius, protoze ti fakt vubec nerozumim. A rikam si, ze mozna tuhle diskuzi ctou spis normalni lidi nez geniove. Strasne me proto mrzi, ze se nevenujes (nebo to aspon nedavas najevo) necemu uzitecnejsimu napr. kryptografii nebo kombinatorice apod. Jses naprosto genialni v tvorbe diskusi o nicem. A tak si te mozna zapamatuji i ostatni, kteri cetli tuhle diskuzi. Skoda, ze nemas vyssi cile.

Stranka projektu.
Stranka projektu skutecne zela prazdnotou, protoze jsem na ni nemel cas. Ted uz jsem tam dal alespon Ondruv clanek a brzy pribudou dalsi linky.

Psani odbornych clanku.
Pokud se tyka psani odbornych clanku, i kdyz je autor jeden, pise vse jakoby by byl cisar, tj. MY. Pokud to neudela, bude vypadat jako saman na sjezdu chirurgu, jak to tady nekdo trefne poznamenal. Je povoleno par vyjimek. Kdyz hovorite s manzelkou o aute, neni vhodne rikat "nevis, kde jsem zaparkoval svoje auto?", ale v pripade, ze hledate kalhoty, je hloupe se ptat "nevis, kde mame nase kalhoty?". Pripad notebooku je typ "nase kalhoty", takze tam je povolena vyjimka. Dokonce by se dalo v tomto pripade napsat i "na mem notebooku" misto "na autorove notebooku", ale mirnejsi je to druhe. To ma za cil potlacit prvni osobu, nikoli ji zvyraznit, jak se mylne domnivate. Jsou to nepsana pravidla, ktera jsem za tech 20 let nikdy nevidel porusit (plati to v akademickych konferencich a textech).

Superpocitac.
Trochu se ale divim, ze mi tady nikdo neomyje hlavu za to, ze jsem tam napsal "superpocitac" (IBM P690). Byl jsem jednim novinarem upozornen, ze je to jen zaklad superpocitacu. Protoze tomu nerozumim, srazim paty a zeptam se. Budu rad, kdyz mi to nekdo objasnite.

Pane Klima,
p690 su high-end UNIXove pocitace od IBM. Viac vam povie link:
http://www.ibm.com/news/cz/2004/02/p690.html

O kolko krat je to IBM-ko rychlejsie ako Vas notebook ?

cituji z ceskeho clanku:...
Vykony notebooku a superpocitace lze tezko srovnavat z duvodu ruznych architektur,ale kdyz uvazujeme, ze uvedeny superpocitac je 25 - 50 krat rychlejsi nez notebook (odhad
poskytl Ondrej Mikle na zaklade pomeru bogomips), ...

viz http://cryptography.hyperlink.cz/MD5_collisions.html

V odbornych pracich a publikacich je zvykem, ze autor nepise ja jsem tohle, ja jsem tamto, ale pise o „autorovi“.

Taky vam u prikladu se zvolenou inicializacni hodnotou IV nesouhlasi hash u prvni zpravy? Postup delam pro vsechny zpravy stejne, u prvnich dvou zprav mam hash stejnou jako ma byt, u treti zpravy mi hash vychazi 9180a371b0f5e9e3961e49b638349cb3 a u ctvrte zpravy je v poradku 2c8c2ca7077d24eb769727d53e15d58c.

No, ja jsem si vzal md5.c z http://theory.lcs.mit.edu/~rivest/md5.c a pote co jsem mu vysvetlil, ze long int nema na mem pocitaci 32-bitu, tak uz mi to vychazi spravne (tedy stejne hashe). Ale u tech druhych dvou zprav je spolecny hash ef2eae54e034707ca26eb09b45c7e487, ne 2c8c2ca7077d24eb769727d53e15d58c. Autor ma v clanku chybu.

9180a371b0f5e9e3961e49b638349cb3, resp. 2c8c2ca7077d24eb769727d53e15d58c vyjde pro treti a ctvrtou zpravu, kdyz zapomenete nastavit ten inicialni vektor na hodnoty ktere se tam pisou a nechate ty defaultni z md5.c.

Jan "Yenya" Kasprzak

no, tak takovej guru zase nejsem:) ja to zkousel obycejnym md5sum:) fascinuje me, ze ty md5 vychazeji na ty tri zpravy a jen na tu jednu ne:)

Klobouk dolu, diky, je to tak, opravu jsem poslal, mela by se promitnout i se zminkou o Vasem autorstvi jak zde, tak na webu IACR http://eprint.iacr.org/2005/075/, pokud tam uvidite verzi 2, je to Vase zasluha :-)
Nez se Americani probudi a opravi to, bude to ale chvilku trvat.

Jake hashovaci funkce mame pouzivat, kdyz MD5 ne?
Byly uz nalezeny kolize pro SHA-1?
Znamena nalezeni kolizi v MD5 to, ze se nemuzu spolehnout na bezpecnost spojeni pres IPSec (FreeS/WAN), ktere pouziva MD5 pro autentizaci?

ntw

No, SHA-1 myslim timhle postupem prolomena nebyla, jinak pisou ze MD4, a nejaky ty dalsi. Takze zrejme SHA-1 zustava OK.

Jinak pokud jsem to dobre pochopil, tak problem s MD5 hrozi v pripade, kdyz nekomu muzes podstrcit jiny data, ktery ale vygenerujes tak, ze maji stejnou MD5 jako data originalni, cili:

a) posles sefovi k podepsani souhlas se zaplacenim faktury, sefovo mail klient udela MD5 a zasifruje svym privatnim klicem, cili kazdy muze overit, ze ti podepsal souhlas zaplatit fakturu. No a pak k tej zprave souhlasu vygenerujes jinou zpravu, ktera bude mit stejnou MD5, ale obsah bude rikat, ze se ti zvysuje mzda:) MD5 souhlasi, mas vyssi plat. dalsi priklady viz fantazie (no a kdyz tohle dokazes udelat na obyc PC, tak je fakt MD5 k tomuhle ucelu nepouzitelna).

b) na webu je SW balik a jeho MD5. Hacker udela backdoor do toho SW a pripravi ten balik tak, aby mel stejnou MD5. Pak uz jen staci, kdyz ten svuj balik rozdistribuuje.

Mam dojem, ze pokud nekdo ziska MD5, tak stale nemuze ziskat originalni zpravu, coz je tvoje plus a tudiz myslim, ze na autentizaci v IPsec to nema vliv. Problem se tyka pouze toho, ze najdes kolizi se stejnou MD5, ne ze najdes k MD5 originalni zpravu (pak by to byl jeste vetsi pruser:)) Ovsem pokud se nepletu.

>Problem se tyka pouze toho, ze najdes kolizi se stejnou MD5, ne ze najdes k MD5 originalni >zpravu (pak by to byl jeste vetsi pruser:)) Ovsem pokud se nepletu.
Myslim si ze nepletete, puvodni zpravu urcite lze jednoduse najit, stejne jako tech (2^mesage_size/2^hash size) dalsich vyhovujicich a to pocitam jen stejne dlouhe zpravy :)

Ad IPsec: Nejsem si jist jestli by nebylo mozne zfalsovat AH vrstvu (podpisy paketu) a pro ESP udelat man in the midle.

Naštěstí se zatím zdá, že ten man in the middle by byl hardwarově neúnosný, aspoň u přenosů v reálném čase. Jenže Mooreův zákon ...

Neviem ci Ti rozumiem, ale ked viem MD5 spravy tak v zasade nikdy nebudem vediet ziskat tu spravu (ak je dlha aspon cca 512 bitov)... uz len preto lebo MD5 hash ma len 128bitov.

a) posles sefovi k podepsani souhlas se zaplacenim faktury, sefovo mail klient udela MD5 a zasifruje svym privatnim klicem, cili kazdy muze overit, ze ti podepsal souhlas zaplatit fakturu. No a pak k tej zprave souhlasu vygenerujes jinou zpravu, ktera bude mit stejnou MD5, ale obsah bude rikat, ze se ti zvysuje mzda:) MD5 souhlasi, mas vyssi plat. dalsi priklady viz fantazie (no a kdyz tohle dokazes udelat na obyc PC, tak je fakt MD5 k tomuhle ucelu nepouzitelna). To je nesmysl, jiná zpráva bude mít jinou MD5. Můžete ale najít jinou zprávu se stejnou MD5, která bude ale obsahovat s největší pravděpodobností jenom chaos. b) na webu je SW balik a jeho MD5. Hacker udela backdoor do toho SW a pripravi ten balik tak, aby mel stejnou MD5. Pak uz jen staci, kdyz ten svuj balik rozdistribuuje. To je taky nesmysl, cracker bude umět zase jenom generovat jiný balík (s nesmyslným obsahem), který bude mít stejnou MD5. Problém je zase v tom, že balík bude jenom kopec nesmyslů. Kolize jsou problémem třeba u hesel. Když systém ukládá heslo (zjednodušeně!), tak se zapisuje do /etc/shadow něco jako md5(to_co_uživatel_zadal). Kontrola hesla je pak test md5(to_co_uživatel_zadal)==md5_ze_shadow. Teoreticky je teda možné najít jiné heslo se stejnou MD5 a tím autentizovat útočníka, při znalosti /etc/shadow samozřejmě. (Výše uvedené vyjadřuje pouze jak jsem to pochopil, nikoli 100% pravdu. :)

no, jeste nez byla zverejnena tahle rychla varianta hledani kolizi, tak uz byly na svete postupy, jak prave provadet a) i b). Proste v pripade zpravy se pouzije text + nejaky bordel, napr. v DOC je tohle docela v pohode, ale myslim, ze by to slo i txt. stejne tak v nejakym zipu nebo bzipu (bzip tusim dokaze ignorovat mess).

najit nejakou zpravu ke znamymu MD5 souctu jeste nejde v kloudnem case, aspon mam dojem, ze to tak je. takze nutny predpoklad je, ze mas originalni data a pripravis k nim falesna data se stejnou MD5.

Mozna bych doporucil k precteni http://www.root.cz/clanky/hasovaci-funkce-md5-a-dalsi-prolomeny/ , ze ktereho vyplava:

1) SHA-1 je bezpecna
2) byla nalezena kolize ve smyslu "je mozne najit dve ruzne zpravy, jejich MD5 jsou stejne"
3) "bezkoliznost je dulezita u digitalnich podpisu" - priklad a) a b)

SHA-1 byla udajne tez prolomena viz http://www.abclinuxu.cz/news/show/77022

SHA-1 byla udajne tez prolomena
Sakra, to jsem nejak minul:(

No IMHO je to tak, že máme zprávu A a MD5 hash H. Prolomení v tomto prezentovaném smyslu znamená, že umíme efektivně zkonstruovat zprávu B, která má taky hash H. Efektivně znamená, že na to nejdeme úplně hrubou silou. Ani jeden algoritmus ale není zveřejněný, takže nevíme, jak pracuje a co přesně dělá.

Co je dále úspěch, tak kolizi lze efektivně hledat i pro předem danou zprávu A (jak zase plyne z textu). Komplementem této situace by byl stav, kdy bychom byli efektivně schopni nalézt dvě zprávy (A a B) se stejným hashem H, aniž bychom předem znali A nebo B. (Toto už by bylo z bezpečnostního hlediska skoro úplně na nic.)

Nikde se ale nepíše o formátu zprávy B. Tzn. jak to chápu já, tak zpráva B vzniká naprosto nahodile a agoritmus funguje jako B=md5_find_collision(H). Nikde se nepíše, že lze dopředu deklarovat \"máme A s hasem H, B začíná řetězcem X\". Pokud by to šlo a fungovalo by to takto (tzn. B=md5_find_collision(H, zacatek_noveho_B)), pak máte samozřejmě pravdu. Ale to by bylo prolomení MD5 na naprosto jiné úrovni a autoři by se s tím určitě rádi pochválili. Pak by šla MD5 fakticky zahodit.

Zase jsou to jenom moje doměnky, mohl jsem někde něco přehlédnout. Dále se samozřejmě rád nechám poučit od lidí, kteří ví víc než já. :)

...no tak po krátkém dalším prozkoumání přiložených materiálů musím konstatovat, že nemám pravdu a funguje to fakt tím "horším" způsobem, tzn. lze celkem jednoduše vytvořit funkci B=md5_find_collision(H, zacatek_noveho_B). Tím bych se chtěl omluvit, jak jsem tady mystifikoval.

Mozna dobrej zdroj s detailama je http://cryptography.hyperlink.cz/2004/cinsky_utok_a_hashe.pdf (a dalsi http://cryptography.hyperlink.cz/2004/kolize_hash.htm)

"" b) na webu je SW balik a jeho MD5. Hacker udela backdoor do toho SW a pripravi ten balik tak, aby mel stejnou MD5. Pak uz jen staci, kdyz ten svuj balik rozdistribuuje. To je taky nesmysl, cracker bude umět zase jenom generovat jiný balík (s nesmyslným obsahem), který bude mít stejnou MD5. Problém je zase v tom, že balík bude jenom kopec nesmyslů. ""

No, asi jste si spatne precetl odkazy, na ktere se da peoklikat z puvodniho clanku. Cituji: "Later, we found out ways to apply this attack to various other formats used in software distribution (zip, tar.bz2, tar.gz, rpm, ...)": http://cryptography.hyperlink.cz/2004/otherformats.html.

Jo, četl jsem špatně, kousek dál už jsem se omluvil za mystifikaci. Mate pravdu.

Kolize pro SHA-1 zatim nalezeny nebyly, ale byla nalezena metoda, jak snizit slozitost jejich nalezeni na 2^69. Tim z kryptografickeho hlediska SHA-1 skoncila. Z hlediska praktickeho muzete klidne pouzivat co chcete, treba MD4, MD5 nebo SHA-1, ale musite zvazit jake podstupujete riziko. V nekterych aplikacich nevadi, ze u hasovaci funkce byla kolize nalezena, ale je to tanecek na palube Titaniku. Kdo vi, kde ma ta funkce dalsi diru, kdyz uz o jedne poradne trhline vime.

NIST doporucuje SHS-256/384/512.

K autorizaci baliku doporucuji pouzivat vice sifer najednou (takovy pristup ma treba OpenBSD), kdy balik validujes pomoci MD5, SHA-1 a RMD160 najednou - pak se ti tezko stane, ze se nekomu povede narusit vsechny tri sifry najednou a certifikat pri tom porad nemel 3GiB

Připojuji se ke gratulantům. Skvělá práce. Kdybych na to přišel já, tak bych se chlubil, že jsem pro naši civilizaci udělal něco extra užitečného.

Myslím, že by bylo pěkné, kdyby se našel sponzor, který by vás nechal sestavit tým a vybrat vybavení k dalšímu výzkumu. Na vládu se v tomhle bohužel nedá moc spoléhat.

Zdravím,
přes tento bezpečnostní problém má podle mě MD5 stále své místo v mnoha aplikacích. Třeba klasická session ID, která se používá na webu a je tvořena např.

md5('432fdsfsd' + client_ip + 'fsd42rgf')

je naprosto v pohodě, zde nalezení shody nepomůže. Anebo se pletu? Ptám se proto, až se klienti či šéf začnou ptát, jestli nepoužíváme tu nebezpečnou MD5...

Jak jsem psal, mam dojem, ze kdyz ti nekdo vezme jen MD5, tak si s ni moc nepomuze. Kdyz ti ukradne originalni data, tak je schopny k ni vytvorit jina data se stejnou MD5 (ale musi ti ty data predat). Takze kdyz by mel originalni retezec, tak si k nemu muze vytvorit jiny se stejnou MD5. Ve tvym pripade by musel tedy vygenerovat nejakou prvni a posledni cast, k tomu pridat svoje IPcko a pak by mozna mohl dostat stejnou MD5. Jenze tu zdrojovou zpravu generujes ty na zaklade IP adresy, takze utocnik by to mohl ovlivnit jenom tou IP adresou a s tim by asi moc nezmohl.

A proč na tohle chcete používat MD5? Nebyl by lepší náhodný řetězec?

To je prave kvuli te kontrole IP adresy, aby nemohl session nekdo ukrast. Proto se v aplikaci pocita MD5 z ip adresy (obalene nejakym balastem) a porovna se to s tim, co prislo od klienta.

To chápu, ale IP adresa se přece může kontrolovat vedle, nemusí být součástí Session ID.

A kde chces sehnat nahodny retezec ? md5 je jako generator pseudonahodnych cisel mnohem lepsi nez rand() ... pravda, md5("owejiowe".client_ip."werwer".rand()) by byla nahodna jeste lepe.

Panove, jako problemek je to zajimave, ale z tehle kusych informaci nejsem schopen vam nic kloudneho rici. Bud to chce popsat tady, ale asi v jinem vlaknu, nebo si to vyridit mailama mimo a pak sem dat vysledek. V kazdem pripade je potreba tu situaci trochu vic popsat a formulovat problem. Vetsinou se vyresi tim, kdyz clovek sepisuje, oc vlastne jde...

Mohl by mi prosím někdo stručně vysvětlit co to je ve smyslu prolomení md5 kolize? Nejsem odborník a nevím o co jde, co se vlastně autorovi povedlo. Děkuji.

Kolize je srážka - srazí se ti dvě různé zprávy tak, že obě mají stejný hash (kontrolní podpis generovaný na základě obsahu zprávy). Tím, se pak onen podpis stává bezcenným, ptž můžeš jednu zprávu (pravou) nahradit zprávou jinou (falešnou, padělanou) a podpis zůstane stejný.

Nejsem si jistej, jestli je to zcela presny vysvetleni. Uz z principu hashovani vyplyva, ze zpravy se stejnym hashem existujou a je jich velka spousta, a to uz kazdy hashovaci metody.
To, co se autorovi povedlo, je nalezt zpusob, jak rychle hledat takovy kolize k dany zprave (rychle ve smyslu \"rychleji nez systemem hruba sila\").

Mně je to jasné :). Tazatel se ptal, co je to kolize a chtěl to stručně. Jemnosti jsem tudíž nechal stranou ;).

Zdravim, kde je ke stazeni ten program na hledani kolizi?

Proc je prvni a druha zpava v ukazce stejna? Pak samozrejme MD5 vyjde take stejne (: Nebo jsem neco prehlid?

Jinak je to zajimavy poznatek, teorie dobra na napsani clanku a ziskani carky za vedu, ale v realu dost stezi vyuzitelne. Ostatne kolize jsou u kazde hashe (uz z principu ze ;) akorat je odhalit jinak nez brute force...

nojo lisi se to... (:o

Ostatne kolize jsou u kazde hashe (uz z principu ze ;) akorat je odhalit jinak nez brute force..
Ano a to je presne ono. Sila hashovaci funkce se prave meri tim, jak dlouha doba je nutna pro nalezeni kolize (dvou ruznych zprav se stejnou hashi). Pokud je doba relativne kratka (napr. 8 hodin na obyc. PC), pak je hash funkce spatna a neda se pouzivat. Pokud je doba dlouha, je hash silna (i presto, ze prakticky musi existovat dve zpravy se stejnou hashi pro vybranou hash funkci).

jasne 100% souhlas. Otazka je jestli se to da zneuzit (realne). To by me zajimalo vic nez ze se relativne rychle da najit nejaky chumel cisel co nahodou ma stejny hash.

viz [4] Ondrej Mikle: Practical Attacks on Digital Signatures Using MD5 Message Digest, Cryptology ePrint Archive, Report 2004/356, 2nd December 2004. Prakticky priklad je na 2.strance obrazek 1 http://eprint.iacr.org/2004/356.pdf. Staci?

to jsem hledal, dik :)

Diky za odpoved. V listopadu jsme mohli jen rikat, "kdybychom byli schopni nalezat kolize pro libovolny inicializacni vektor jako Cinani...". Proto Ondra naprogramoval ukazku, ktera vyuziva jen jedne ze dvou konkretnich kolizi, ktere jsme meli od Cinanu k dispozici.

Ted jsme v situaci, kdy si muzeme kolize vyrabet sami a to pro libovolny inicializacni vektor.

Pak mame schema mnohem zajimavejsi:

1) P = zvolte libovolnych X*512 bitu (treba doc, xls... dokument, smlouva, apod.)

2) vypocteme mezivysledek hase pri hasovani P (neuzavirame), rekneme, ze tento mezivysledek je inicializacni hodnota MD5

3) programem vygenerujeme dve ruzne nesmyslne 1024bitove zpravy (M1, M2) se stejnou hasi (pro nami uvedenou inicializacni hodnotu).

4) zvolime libovolny smysluplny nebo nesmysluplny text, binar apod. Y (nasobek 512 bitu)

Plati:

MD5(P, M1) = MD5(P, M2)
MD5(P, M1, Y) = MD5(P, M2, Y)

cili z dane kolize lze vyrabet libovolne dlouhe kolidujici zpravy

postup je i s obrazky v prednasce na BIS, http://cryptography.hyperlink.cz/2004/kolize_hash.htm

stranku jsem dnes predelal, aby byly pohromade nektere veci

A kdyz uz jsme u te prednasky na BIS, budes nekde (na miste pristupnem beznym smrtelnikum) povidat i o techhle novych vecech (az ten algoritmus doladis a zverejnis)? Zaslechla jsem cosi o CryptoFestu, ta zimni prednaska z matfyziho seminare by si mozna take zaslouzila letni (trochu akcnejsi) followup :)

prednasku na BIS samozrejme predelam na zaklade zkusenosti z minula a pridam novinky
ta prvni byla otukavaci, nevedel jsem, co osazenstvo vi a co ocekava
tesim se, doufam, ze ucastniky zase poňouknu k nějaké akci

zdravim,

zajimalo by me jake tohle ma prakticke dopady. Trebas u FW, ktere pouzivaji MD5 jako otisky programu, ktere pousti na porty. Slo by teda realne vyrobit hash stejny jako ma trebas IE , trillian, dc proste cokoliv k nejakemu trojanu , ktery by potom FW poustel ven v domeni , ze je to "povoleny" program ?

jo ...

Dobra prace pane Klima...

MD5 je jednou z možností ve vyhlášce 366/2001 Sb. a direktivě 1999/93/EC pro vytváření elektronického podpisu. Je otázka, jestli algoritmus nalézání kolizí dokáže nalézt kolizní zprávu pro libovolnou zvolenou zprávu nebo dokonce dokáže nalézt kolizní zprávu obsahující zvolený text.

Současný algoritmus nedokáže ke zvolené zprávě nalézt druhou se stejnou haší. Je zaběhlá představa, že to se musí umět, aby kolize byly nebezpečné. V praxi to ale na různé podvrhy vůbec není potřeba.
Se současnou znalostí lze totiž
- padělat certifikát, viz http://crypto-world.info/news/index.php?prispevek=1232.
- vzít dva libovolné soubory a docílit toho, že je uživatel přesvědčen, že jsou totožné po kontrole haše a digitálního podpisu, viz článek Ondreje Mikle na http://cryptography.hyperlink.cz/MD5_collisions.html

Jen si dovolím upřesnit:
a) ve zminěné direktivě ani jejích 4 přílohách, žadné algoritmy uvedeny nejsou a tedy není pravda, ze by tu byla MD5 uvedena resp. doporučena.
Zajemci o preklad direktivy ji najdou napr. v knize Elektronicky podpis, kterou jsem po dohode s nakladatelstvim uvolnil k volnemu stazeni v pdf formatu - http://www.crypto-world.info/kniha/
b) ve vyhlasce 366/2001 Sb. je sice MD5 uvedena, ale v priloze cislo jedna, zatimco v priloze cislo 2 : "Kryptografické algoritmy a jejich parametry pro vytváření párových dat poskytovatele a pro prostředky pro bezpečné vytváření a ověřování zaručeného elektronického podpisu" jiz uvedena a tedy povolena neni.
Takze : pro vytvareni/overovani zaruceneho elektronickeho podpisu pomoci bezpecnych podpisovych/overovacich prostredku ve smyslu Zakona c.227/2000 Sb. neni v podpisovych schematech v ČR MD5 povolena.
c) V EU řeší otázku doporučených algoritmu pro podpisové schéma standard nazývaný ALGO - celá citace : Cryptography algorithms and parameters used are in compliance with Algorithms and Parameters for Secure Electronic Signatures (ETSI Special Report SR 002 176, March 2003). V tomto dokumentu (z jehož straší verze a to 1.44/EESSI se vychazelo pri priprave vyhlasky) take MD5 uvedena neni.

Uvadim to zde jen pro to, aby zde nevznikla neplodná diskuze nakolik prislusny vysledek podlomi duveru ve vyuziti elektronickeho podpisu v agendach, ktere se ridi prislusnym Zakonem o elektronickem podpisu ....

Myslím, že nemusím být kryptoanalytik, abych mohl nadnést svůj pohled, který by měl racionální jádro.
Pan Klíma zřejmě patří k nejlepším odborníkům v tomto oboru v Čechách. Pamatuji si na články, které vydával v časopisu CHIP a které jsem občas se zájmem přečetl, ale kterým jsem mnohdy já a předpokládám i většina dalších čtenářů nerozuměli :-)
Pak jsem jeho jméno zaslechl v souvislosti s údajným "rozlousknutím" šifrování(? RSA,IDEA ?), které používá PGP. To by byl skutečně zásadní objev světového významu, ale jak se později ukázalo, byla to zbytečně nafouknutá bublina a humbuk, protože nebyla objevena nedostatečnost v algoritmu šifrování, ale pouze v jeho _implementaci_ v tomto konkrétním programu.
Před téměř rokem oznámila čínská skupina kryptoanalytiků, že našla chybu(nedostatečnost) v hashovacím algoritmu MD5, která se dá využít k významě rychlejšímu hledání kolizí a toto se stalo světovou událostí min. loňského roku. Přestože nezveřejnili přímo kód, uvedli dostatek indicií na to, aby mnoho talentovaných lidí napsalo vlatní vyhledávač a na Internetu se jich válí desítky. Objevil nyní p. Klíma jinou a doposud nedokumentovanou zranitelnost algoritmu MD5 nebo jen vylepšil implementaci už objeveného ? Tak nevím ...
S odstupem času se snad ukáže, nakolik bylo nadšení na místě. Každopádně přeji autorovi do budoucna mnoho úspěchů a dobrých nápadů a aby už konečně "prolomil ledy" ;-)

PGP - bulvar
Z kauzy PGP udelali bublinu novinari, spustili to Lidovky a pak se to uz vezlo. Medialni stroj pracuje nezavisle na vas a nezavisle na faktech. Je to uzasna vec. Vali se to jako vlna a vy muzete jen neme zirat, kam to s vami "flakne".

Odborne
Nezlobte se, ale smysl naseho tehdejsiho clanku nebyla "chyba v implementaci algoritmu sifrovani v konkretnim programu". V te vete jsou dve chyby. Za prve to byla sada programu, za druhe to byla chyba ve standardu RFC2440, proto se to tykalo sady programu jak starych, soucasnych, tak budoucich, protoze vsechny kvuli kompatibilite zakladnich sifrovacich struktur by ten standard mely dodrzet. Ze to nebyla zbytecne nafouknuta bublina (z odborneho hlediska) snad dokazuje to, ze na http://www.pgpi.org/ je tato nase vec stale vedena mezi hlavnimi udalostmi od roku 2001 - a neni jich tam mnoho. Pak se nejednalo se o sifrovani, ale o podepisovani. Neco jako hodinky a holinky. Konkretne o ziskani privatniho podepisovaciho klice. Vite, kdyz nekdo v kryptologii umi ziskat klic, je to vzdycky o necem. Proto jsme dostali blahoprani k tomuto vysledku od prednich kryptologu.

Cinsky vysledek
Vase interpretace tohoto vysledku je opravdu zabavna. Kdybyste si precetl alespon diskusi na rootu, nemusel jste takovou hloupost napsat. Nekdy se to hodi, tahle anonymita...

Jen jsem zvedav, jestli se take omluvite.

chlapiku, dej si bacha, tohle uz by se dalo povazovat za "Siti do pana Klimi" a taky be te za to mohla treba johanka zdrbnout!

Pokud si se smrtaku zase spatne vyspal, muzes se zase vratit zpatky do hrobu. Slusne jsem te poprosil, abys Johanku nechal na pokoji. Muzes sit do me, ale na to zda se nemas vitaminy. Tema je hasovaci funkce. Jenze tady neumis ani precist clanek v cestine. Zato kecy, rejpani a urazky ti jdou dobre. Navrhl jsem ti, abys neco stvoril a anonymne to do rootu poslal, kdyz jsi takovy dobry. Misto toho se probudis, sednes k pocitaci a jdes rejpat do lidi.

A vite proc ten konflikt zacal? Zacal proto, ze sem byl obvinen, ze do Vas siju a quli tomu uz nesmim psat na roota. A ze nazivam jeho design za spraseny? A neni? Tak sem chtel kolegu upozornit, ze by mohl dopadnout stejne. Nic vic. Co Vam pripada na vete "chlapiku, dej si bacha, tohle uz by se dalo povazovat za 'Siti do pana Klimi' a taky by te za to mohla treba johanka zdrbnout!" urazliveho? Jak sem to mel formulovat? A vubec, ukazte mi tu prispevek kde sem tu nekoho urazel?

Ja podal Johance smirci ruku. Ona ji prijala a druhej den se zase do mne obouva. Nezlobte se, ale kdyz ona rejpe, tak ja budu rejpat taky. A clanek? Vy byste posilal anonymne clanke do casopisu, jehoz design se vam hnusi.... ok pominu design, kde Vam za projeveveny nazoru sefredaktorka napise ze za to, ze "do nekoho sijete uz sem nesmite psat"? Schvalne se podivejte jak ten flame zacal. Myslite si, ze kdybych tu podobnym zpusobem sil do napriklad autora minuleho clanku o SDL, ze by to dopadlo stejne? ANI NAHODOU! Proste, nekteri jsou si rovni, jini jsou si rovnejsi.

Johanka je bezesporu fajn holka a ja proti ni mam jenom to ze nedokaze od sebe oddelovat profeionalni a osobni zalezitosti. Na ruznych mistech na rootu na ruznych diskuzich by se o tom naslo zajiste dost prikladu typu... pokouseni se zakazovat diskutovat o urcitem tematu. Kdyz nekdo sije do neceho co je v poradku a do ceho se proto ani vlastne sit neda (to bude asi Vas pripad), tak si stupi jehlu. Ale Johanka je (nezlobte se za to prirovnani) jak jehelnicek. Ale slibuju ze uz toho fakt necham.

Otazka zni treba, kdyz sem napisu ten clanek a podepisu se pod nej, kdo mi zaruci ze bude-li qalitni, ze bude zverejnen? Ja sem proste anonymne psat nebudu. A co vy? Potencionalne, dejme tomu, ze sem napisu uplne bezvadny clanek. Dokazal byste mne, bez ohledu na to, ze sem se tu hadal s johankou (vy tvrdite ze sem ji urazel, ja tvrdim ze ne), na zaklade toho clanku prijmout jako zamestnance k Vam do prace (nemate-li zrovna plny stav)? ;-) Ja verim ze ano.

Podobna otazka na johanku, fakt te tak moc urazim? Dokazala by ses treba nechat odemne vzit do hospody a nechat si zaplatit pifo (ciste pratelsky, zadne baleni)? Tomu neverim. Kdybys byla profesor a delala ustni zkousky, nechtel bych ji u tebe delat, myslim ze bych nemel sanci - byt by nebyla z kryptografie :-)

Ty ses fakt asi vul.

Ad Johanka smirci a obouvajici se: ja Ti poprala dobrou noc a doufala, ze uz budes drzet hubu (dej si pozor, abys pres ni brzo nedostal). Pak jsem odpovedela pravdive jinym na prispevky tykajici se Tebe a Ty uz to zas beres jako duvod k vylejvani tech svejch jedovatosti.

Zadny clanek Ti nezverejnim, do prace bych Te nevzala a na pivo bych s Tebou uz vubec nesla (protoze na to chodim jen s kamarady), predpokladam, ze Vlastik Klima ma stejny nazor. Nicmene kdybys ke mne prisel na zkousku, samozrejme by s Tebou bylo nakladano jako s kymkoli jinym a pro jistotu bych si nekoho neutralniho prizvala prisedet, abych se nenechala unest a nevyrazila s Tebou dvere.

Tak uz jdi do haje prosimte. Ne, necitim se urazena, urazit nebo dotknout se me muze jen clovek, ktereho si alespon minimalne vazim. Jen me mrzi, ze se tak debilni diskuse odehrava zrovna pod timhle clankem.

Ad michani osobniho a pracovniho zivota: to se prave snazim nedelat. Kdybych to delala, hned na zacatku Ti reknu, kam mas jit, takto jsem se snazila Ti v klidu vysvetlit, co mi vadi. Ale je videt, ze to nezabira.

A pozdravem "nepiste mi a pokud mozno nepiste vubec"

Johanka

no tak to vidite, kdo tady jako prvni pouzil sproste slovo? ja to nebyl. Kdo tady jako prvni toho druheho oznacil za sveho nepritele? A s tim clankem? Ta by byla schopna z IP adresy odhalit moji identitu a nevzit ho a to ja nemuzu riskovat ani jako anonym. Ne johanko, kravou te nenazvu, protoze krava nejsi a ja te mam rad (treba jen tajne). A fakt nechapu co sem ti udelal tak strasnyho. A vyhrozovat fyzickym nasilim... to akorat potvrzuje co sem tu uz psal. Proste, trochu afektovana, ale jinak fajn holka. To pivo je mi lito, ale s tim asi nic nenadelam. Mimochodem, jeste mi dluzis za ten posledni clanek 300Kc a vzhledem k tomu, ze uz dalsi jaxi nebude a tech 500 nema sanci se tam nakumulovat, cislo uctu uz sem ti psal, tak pliiiiiis.

Penize chodi v polovine nasledujiciho mesice, takze za unor by Ti mely prijit behem par dnu, pokud neprijdou, napis.

A myslim, ze afektovany je tu nekdo jiny.

ale no tak se nezlob, sem taky jenom clovek, chvilku zhluboka dychej.... :-)

no tak johanko, mluv se mnou, ja proti tobe fakt necitim zadnou zast. 2 piva?

Jses nadrzenej nebo co? Nechteli byste si to jit ventilovat nekam jinam?

Člověk nemusí nezbytně používat sprostá slova, aby byl schopen urážet jako nikdo jiný.

Člověk nemusí nezbytně někoho označit jako svého nepřítele, aby jím ten člověk doopravdy byl.

Člověk nemusí nezbytně plácat kraviny, aby působil jako hovado, které je totálně mimo.

(Vím, o čem mluvím. Taky k těm lidem bohužel patřím... Tak už konečně zavři hubu a jdi se podívat na toho idiota v zrcadle!)

hmmm vidim se :-(

ale stejne mi to neda, zkus mi tu ukazat nejaky prispevek, kterym jsem tu nekoho urazil. Treba je zkus dat do souvislosti. Jsem ochoten uznat chybu...

jo a jeste jena vec, " do prace bych Te nevzala ", tady presne vidis to, co sem uz psal, nejses schopna od sebe oddelit profesni a osobni stranku veci. Pls, rekni mi co sem ti udelal?

Jestli ono to není tím, že by to Roota položilo. Kdepak nový deign, smrťák způsobil Rootovi smrt. Já bych Tě do práce taky nevzal, jestli Tě to potěší.

smrt by zpusobil rootu smrt? Vys od jaky chvile sem se do johanky pustil? Bylo to od chvile, kdy mi napsala ze "nesmim psat na roota protoze siju do pana Klimi". Teda, bylo to od chvile, kdy sem se podepsal vlastnim jmenem. Kdybych sil do nekoho jineho, tak si toho ani nevsimne. No a s tou praci, vis ze sou napriklad nekteri naprosto opacneho nazoru?

Ad michani osobniho a pracovniho zivota: ten autor SDL by ti byl ale ukradenej co?

Vykašlete se na to, to snad nemá smysl odpovídat. Já se těšil, že se tu v diskusi dozvím nějaké zajímavosti, a místo toho tu početně převažují nesmysly od ignorantů, kteří pravděpodobně netuší co to ta md5 vlastně je, a reakce na ně.

Radsi bych se zeptal
- myslite, ze ted Cinani svuj postup zverejni? Prijde mi, ze jakekoli dalsi cekani jaksi ztraci vyznam.
- co si myslite o tom puvodnim "zverejneni-nezverejneni" formou ukazky, naslednem "prokecnuti" ze se umi najit kolizi pro libovolny inic. vektor,...? Kdyby takhle nekdo publikoval objev v nejakem jinem oboru, setkalo by se to se znacnou nelibosti.
- teď se tedy rychle bude nahrazovat za SHA-256 a spol. Z takoveho letmeho nadhledu to u me budi trochu neduveru. Jsou to zase iterativni funkce zhruba stejneho typu. Nepredstavuju si, ze je mozne nejake "definitivni reseni", jde o cas, ale tady mi pripada, ze kryptoanalyza postupuje dost rychle, az vy a cinani sve vysledky zverejnite, pujde mozna jeste rychleji... Existuji nejake podle vas zajimave hasovaci fce postavena na uplne jinych zakladech?
- nejsou ty hase trochu presprilis popularni? Ma treba HMAC oproti MAC se symetrickou sifrou nejake bezpecnostni vyhody, nebo jde o rychlost?

Radši odpovím v novém vláknu protože v tomhle by možná nikdo seriózní diskusi nehledal.

Diky za prani, ale stejne by me zajimalo, co by podle vas mohlo prolomit ledy, jinymi slovy co povazujete za hodnotny vysledek v kryptologii v posledni dobe (teda krome md5)? Prosim alespon jeden, a pokud mozno nic obecneho. Myslim to doopravdy, zadny flame.
Diky, jsem zvedav.

Odpovidam na dotazy takhle zvlast, chtelo by to v tom redakcnim systemu umet zobrazovat treba jen nazory od urciteho data (ted musim prochazet vsechno, coz je pri takovem mnozstvi sila).

Cryptofest 19.3.2005
Primarne je www.cryptofest.cz zameren na neco jineho. Pokusim se ale vyhovet obema taborum - tem, co chteji novinky i tem, co jeste nevi nic moc o hasovani a ze zakulisi hasovacich funkci vubec nic. Nechci zadnou z techto skupin zklamat.

Kolize SHA-1 a Upozorneni pro certifikacni autority
Kontaktoval me tym Wangova-Lenstra-Weger, ktery udelal ty kolidujici certifikaty pro MD5 (viz http://crypto-world.info/news/index.php?prispevek=1232). Chteli by ted udelat totez pro SHA-1. Viz stranka http://www.win.tue.nl/~bdeweger/CollidingCertificates/index.html dole. Podari se jim pravdepodobne teoretickou slozitost metody Wangove a kol. 2^69 jeste stlacit na 2^66. Takze potom bude s SHA-1 v certifikatech pekna mela, protoze vetsina "silnejsich" certifikatu pouziva prave SHA-1.

Verte, ze tahle zprava nepotesi zadnou certifikacni autoritu na svete.

Díky za konstruktivní dotaz. Dávám ho mimo, a proto musím opakovat i text.

Datum: Dnes 23:23
Autor: jk
Titulek: Re: objevitel nebo zlepšovatel ?

Vykašlete se na to, to snad nemá smysl odpovídat. Já se těšil, že se tu v diskusi dozvím nějaké zajímavosti, a místo toho tu početně převažují nesmysly od ignorantů, kteří pravděpodobně netuší co to ta md5 vlastně je, a reakce na ně.

Odpověď: To je daň za demokracii. Diskuse odráží její stav. Misto věcného řešení problemů diskuse o nicem. Kdyby politici venovali cas na vytvareni a urovnavani tzv. vladni krize na věcné řešení problemů (jak říká Švejnar), mozna bychom meli do skolstvi o par miliard vic. Kdyby se TADY diskutovalo k veci, mohli bychom se neco dozvedet nebo vyresit. Treba ten protokol s ip. Nebo ty vase otazky. Jsou dobre, musel jsem se znovu na neco podivat. To obohati mne i vas.

Radsi bych se zeptal
- myslite, ze ted Cinani svuj postup zverejni? Prijde mi, ze jakekoli dalsi cekani jaksi ztraci vyznam.

Odpověď: Skutecne další čekání bylo napínání veřejnosti. Bylo to dost neobvykle. Číňané svůj postup ale už zveřejnili! Je to velmi čerstvá novinka. Proběhlo to v tichosti a nenápadně. Bylo to zřejmě tak, že jakmile se prof. Wangová dozvěděla, že její příspěvek byl přijat na konferenci Eurocrypt 2005, dala ho k ostatním pracem na své internetové stránky a nechala to osudu. První to našel nějaký člověk, který si přečetl můj článek, pak dal vyhledávat "Wang" a to ho dovedlo až k jejímu článku. Byl schován v čínských znacích ale anglický název prominoval. Tak jsem se to dozvěděl i já. Pak jsme se tomu s Pavlem Vondruškou chvíli věnovali, kdy to tam asi dala a výsledek je výše. Informace o tom je například na http://www.root.cz/zpravicky/cinsti-vedci-promluvili/ s mým komentářem k obsahu a zdroj je na
http://www.crypto-world.info/news/index.php?prispevek=1245 .

- co si myslite o tom puvodnim "zverejneni-nezverejneni" formou ukazky, naslednem "prokecnuti" ze se umi najit kolizi pro libovolny inic. vektor,...? Kdyby takhle nekdo publikoval objev v nejakem jinem oboru, setkalo by se to se znacnou nelibosti.

Odpověď: No vypadá to dramaticky, ale vsadil bych na jiný scénář. U inicializačních vektorů se spletli. Když na to byli upozorněni, vyrobili kolizi se správným IV. Pak už bylo každému jasné, že to umí pro jakýkoliv IV, tak to i napsali. Nezveřejnili to proto, že by jejich příspěvek pak nemohl být přijat na Eurocrypt 2005. Crypto 2004 už nestíhali, uzávěrky příspěvků jsou půl roku před konferencí! Je to opravdu velice divné, že by si nezkontrolovali MD5 podle kontrolních příkladů. Mám ale své zkušenosti. Když jsem publikoval ten svůj článek, nechal jsem tam také chybu - v příkladu pro volený inicializační vektor jsem kolizi (data) našel správně, ale část programu, která dělala výpis hodnot pěkně do složených závorek, použila MD5 se správným IV. No a tuhle hodnotu jsem pochopitelně dal do příspěvku. Právě proto, že to vypadá naprosto nerealisticky, bych si tipnul, že ta čínská chyba je ze života.

- teď se tedy rychle bude nahrazovat za SHA-256 a spol. Z takoveho letmeho nadhledu to u me budi trochu neduveru. Jsou to zase iterativni funkce zhruba stejneho typu. Nepredstavuju si, ze je mozne nejake "definitivni reseni", jde o cas, ale tady mi pripada, ze kryptoanalyza postupuje dost rychle, az vy a cinani sve vysledky zverejnite, pujde mozna jeste rychleji... Existuji nejake podle vas zajimave hasovaci fce postavena na uplne jinych zakladech?

Odpověď: Je to pravda, ten rychlý postup bourání hašovacích funkcí v minulém a letošním roce všechny trochu zaskočil a vyděsil. I NIST. Ukázalo se, že princip iterování v hašovacích funkcích je genericky špatný. To (pouze) teoreticky a pro budoucnost odrovnává i hašovací funkce SHS-256/384/512/224, i když jen teoreticky a jen koncepčně. V praxi mají a pravděpodobně ještě asi pár let budou mít dost vysokou složitost, aby mohly sloužit. Ono stačí 10-20 bitů složitosti navíc a rok se promění v tisíc nebo milion let, čili velikost hašového kódu hraje ohromnou roli. Teoretické výhrady k iterování se mohou v praxi, pokud není nic lepšího, vzít jako zanedbatelné riziko. Horší je to s rizikem, že někdo na něco zase přijde. Ale to je z jiného soudku, to existuje vždycky. Hašovací funkce nejsou podloženy žádnými důkazy o nerozbitelnosti. Nicméně se to riziko zdá být vždycky větší, když někdo na něco nového přijde. Pak to zase utichne a jede se dál. Na tohle nové paradigma v chování ke kryptografickým technikám jsem se snažil upozornit v článku "Nedůvěřujte kryptologům". Potěšilo mě, když Lenstra vlastně ve svém současném článku o hašovacích funkcích z 26.2. říká velmi podobně věci.

Nejsem žádný odborník na hašovací funkce, ale maslím, že všechny současné mají iterativní strukturu. Takže se bude muset hledat jiný koncept. K tomu byl snad už vypsán nějaký projekt. Adi Shamir je téhož názoru, že potřebujeme nový koncept. Je to logické, protože Joux a Kelsey-Schneier ukázali, že současný koncept je teoreticky špatný. Je potřeba si pospíšit, protože proces výběru nového standardu trvá několik let a to nehovořím o tom, že kryptologové nejsou připraveni a nemají v šuplíku žádný nový kocept, pokud vím.
Osvěžil jsem si Tiger (http://www.cs.technion.ac.il/~biham/Reports/Tiger/tiger/tiger.html), ale je také iterativní, navíc 192bitový výstup není perspektivní. Vnitřek je ovšem zajímavý. Má jen nevýhodu, že ty vnitřní funkce nejsou tak dobře prozkoumány. Tipuji, že nová hašovací funkce bude mít vnitřek vystavěn na stejných základech jako SHA-1,2, protože to jsou prozkoumané věci. Podobně jako AES má základy z DES, i když se tváří, že ne. Když se dobře podíváte na vnitřek mikroskopem, všude je nálepka "stará dobrá DES".

- nejsou ty hase trochu presprilis popularni? Ma treba HMAC oproti MAC se symetrickou sifrou nejake bezpecnostni vyhody, nebo jde o rychlost?

Jsou použity všude možně. Vývojáři si na ně zvykli a dají je všude, kde to jde. Mezi HMAC a MAC je čistě z praktického hlediska rozdíl jen v rychlosti - HMAC je pomalejší. Je to asi tak, že pokud někdo má už v aplikaci hašovací funkci, a nevadí mu rychlost, pak nemusí už implementovat symetrickou šifru a MAC k tomu, aby zajistil (nepadělatelnou) integritu dat. Použije prostě HMAC místo MAC a kód se nezvětší. Jinak HMAC i MAC zajišťují totéž.

Po dlouhe dobe k veci.... :-) Existuje vedni disciplina, ktera se snazi vymyslet hashovaci funkci a pritom dokazat, ze by jeji prolomeni bylo opravdu slozite? Myslim tim na matematicke urovni. Mohli bychom tak ziskat hashovaci funkci ktera by sla prolomit opravdu jen hrubou silou, protoze kazda jina metoda by byla slozitejsi. O tomhle nic nevim a rad bych se zeptal jestli si myslite, ze se nekdy neco takoveho objevi a jestli uz se na tom pracuje, pripadne jestli nad tim nekdo premysli?

Je to kryptologie. Ovšem je tak košatá, že na většinu otázek neexistují odpovědi. Hodně věcí je založeno na nepřímých důkazech. Tam, kde existují důkazy rigorózní, se také už stalo, že kryptosystém nebo metoda na nich založené, byly rozluštěny. Určitě se zeptáte jak je to možné. Možné je to tak, že formulace, které jsou dokázané, jsou v praxi většinou nepoužitelné. Takhle dopadl například kryptosystém na bázi problému batohu (knapsack problem). Bylo ukázáno, že je NP-úplný, ale kryptosystém na něm postavený, měl špatně vybudovaná padací vrátka. To už problém batohu ovšem neřešil. Naproti tomu problém RSA není dosud z hlediska teorie složitosti "otaxován", ale kryptosystém RSA docela dobře žije.

Pro hašovací funkce speciálně žádná vědní disciplína neexistuje. Základ pro jejich zkoumání tvoří pouze konferenční příspěvky, knihy a doktorské práce.

Podobně je tomu i v jiných oblastech. Například nedávno jsem zjistil, že v oblasti asynchronních proudových šifer existují za posledních 20 let trvání moderní kryptologie jen tři návrhy těchto šifer. Teoretický základ pak tvoří cca 10 zdrojů typu konferenčních příspěvků, doktorské práce.

U hašovacích funkcí je těch konceptů mnohem více a zdrojů dost. Nicméně se všichni upnuli na Merkle-Damgardovu konstrukci, protože je velmi přirozená (iterativní princip). Pravděpodobně se bude muset modifikovat, jak se o to pokusil například Stefan Lucks (2004).

Jestli někdo pracuje na novém konceptu nevím, ale brzo se to stane. Buď se připravuje nebo byl už spuštěn projekt na návrh nové hašovací funkce. Možná mě někdo doplní, kde to žije na internetu.

Podle logiky nekterych prispevku k tomuto clnaku jsem dospel k nazoru, ze vejtaha je Bruce Schneier, protoze ve svem Blogu z 10.3 (http://www.schneier.com/blog/) cituje Klimovum clanek. Uznejte nebylo by lepsi, aby radeji napsal vlastni? Takhle trapne se chlubit cizim perim :-)

(prosim berte jako nadsazku, ale soucasne to pisi pro ty, kteri psali, jak je jednoduche progooglovat Internet a prislusny postup sepsat, snad pochopi a otevre jim to oci ...)

slibuji, ze priste pred odeslanim po sobe prispevek prectu a opravim preklepy ...
- k tomuto clanku
- Klimuv

Dobry den,
vie mi niekto poradit s algoritmom pre SHA-256, mam tu specifikaciu od NIST a nieco mi nie je jasne.
1. Maximalna dlzka vstupnej spravy ma byt <2^64.
2. Vstupnu spravu treba vypnit "vatou" aby dlzka spravy bola nasobok 512 [pri SHA-256]
3. Ta vata je jedna 1 potom same 0 a posldnych 64 bitov je 64 bitove cislo s dlzkou spravy. Vzorec l + 1 + k = 448 mod 512. [l - dlzka spravy, k - pocet nul].

Moja otazka znie, co ked vstupna sprava ma o 1 az 64 bitov menej ako je maximum 2^64. Ako sa potom pridava tato vata "1000...+64-bit_cislo", vsak by sa celkova dlzka predlzila na 2^62+512 bitov.

Dakujem

P.S.: Samozrejme, ze tazko sa najde expert ci skor exprd, ktory vygeneruje vstupnu spravu dlzky 2^64. Ale ide mi o algoritmus [a aby to jedneho dna o 50 rokov nepadalo]

Nejde o to, kolik bitu ma vysledna doplnena zprava, ale o to, kolik bitu ma nedoplnena zprava. Nedoplnena ma mit maximalne 2^64 - 1, aby se jeji delka vesla do 64 bitu. Doplnena zprava muze prekracovat 2^64. To prave nastene pri puvodni delce treba 2^64 - 12. Doplnena zprava ma pak (2^64 - 12) + 1 + (11 + 448) + 64= 2^64 +512.

Aaa uz tomu asi rozumiem.

Lebo po doplneni sa sprava rozdeli na 512 bitove bloky M(1), M(2), .... az M(N).
A nie je obmedzeny maximalny pocet N blokov. Tie sa ajtak jeden po druhom spracuvavaju v hlavnej slucke "For i=1 to N"

Dakujem Vam a prajem vela uspechov.

Když si uložím MD5hash a soucet ASCII hodnot z originál hesla
a pak to porovnám, tak se mi tam pan Klíma
(mimochodem machr, zejtra jdu na přednášku na cryptofestu)
dostane také?

Myslim ze ne, pokud bude to heslo kvalitni. Na cryptofestu jsem to vysvetlil. Pro ostatni, kteri tam nebyli, jsem umistil rozsahlou prednasku o hasovacich funkcich na http://cryptography.hyperlink.cz/2005/cryptofest_2005.htm

No cas od casu se to stane kazdymu algoritmu, otazka je jakej hashovaci algoritmus pouzivat? SHA1?

myslim, ze SHA-1 do roka padne..., takze doporucuji SHA-256.