POC: MD5 Message Digest algoritmus hash ütközés

Milyen alternatívákat javasoltok, ami kvázi gyors (mert szerintem az MD% relatíve elég gyors volt), legalább olyan sokrétűen használható, mint az MD5 (kezdve az adattitkosítástól a különféle állományok ellenörző-összegéig), és minél szélesebb körben, többféle rendszeren elérhető. Azaz, mi jön az MD5 után...?

Természetesen, ha 16 byte-nál több adatot,mondjuk 17byte-ot 16byte-ra konvertálunk, egy hash függvény segítségével, akkor lesz egy csomó olyan bemenet, amire ugyanaz a kimenet. Ez ugyanúgy érvényes az SHA1-re mint az MD5-re. A hir itt inkább az, hogy ehhez bizonyos esetekben nem kell végigpróbálgatni az összes 17,18... byte-os szekvenciát, hogy találjunk ilyen ütközést,hanem ez viszonylag egyszerüen számolható... Szerencsére ez meglehetősen ritka eset. S nem arról van szó, megértésem szerint, hogy tetszőleges bemenethez tudnak egy olyan polinomikus algoritmust, ami kiköpne pár azonos MD5 hash-el rendelkező szekvenciát.

Helyenként szerintem megtévesztő a cikk fogalmazása, így szeretnék pontosítani/cáfolni/kérdezni/mittommén...

Az md5 egy 128 bites, vagyis ha nem hexán írjuk le, hanem nyersen 8 biten, akkor 16 byte hosszú ellenőrző összeg. A skatulyaelv szerint teljesen triiviális, hogy már a legfeljebb 16 byte hosszú, vagy akár mondjuk a pontosan 17 byte hosszú fájlok között is dögivel kell hogy legyen ütközés. Ez nem az md5 gyengesége, hanem tetszőleges hash algoritmus természetes velejárója. Az tehát már a legelső pillanattól kezdve nyilvánvaló kellett hogy legyen, hogy ütközések igenis vannak.

A kérdés sokkal inkább az, hogy mennyire könnyű tényleges találni ütközést.

Két különböző kérdést is feltehetünk egy hash algoritmussal kapcsolatban. Az első, hogy véletlenszerű bemenetre mennyire véletlenszerű a hash értéke, vagyis az egyes hash értékek valószínűsége mennyire egyezik meg. Ilyen téren az md4 és md5 is nagyszerűen muzsikál. A másik az, hogy mennyire támadható, vagyis mennyire nehéz egy másik fájllal azonos hash értékű (és lehetőleg azonos hosszú) fájlt generálni. Ez security szempontból lehet fontos. Ilyen szempontból az md4 gyenge volt, ezért született meg az md5, de most ugyebár úgy fest, hogy az md5 sem túl jó.

Ennek ugyanakkor némiképp ellentmond a hírben az, hogy egyelőre még nem tudnak tetszőleges bemeneti adatokkal dolgozni... ha ez nem megy még, akkor nem értem: mi a probléma az md5-tel? Vagy bizonyos fájlokhoz könnyű, másokhoz nehéz ütközést konstruálni?

A feltörők dolgát segítheti, hogy az md5 egy inkrementális valami, ami sorra veszi a byte-okat és mindegyik valamit teker a hash értékén. Ennek eredményeképp ha valaki már talált két fájlt azonos md5-tel, akkor ha azonos bytesorozatot még hozzáfűz mindkettőhöz, ugyanaz marad az md5.

Tudtommal az md5 mögött nem igazán van komoly matematika, csak amolyan ad-hoc így-úgy-amúgy kavarjuk össze a byte-okat.

Szóba került több helyen, hogy úgy fest, a 128 bit kevés, ideje lépni valami nagyobb értékre. Ebben egyetértek, ugyanakkor pont amiatt, mert a dolognak nincsen kialakult bombabiztos matematikája, szerintem egy darab valami szabályszerűséget mutató szépen megkonstruált 2N bites hash algoritmus helyett sokkal többet ér két tök különböző N bites hash egymás után írása, mert nincsen bennük közös hibamodulus, közös támadható felület - nem egy, hanem két algoritmust kell feltörni. Persze kettő helyett lehet még több is. Mint ahogy a hír is jelzi: az md5 és a sha1 hash egymás után írása egyelőre még jól állja a sarat, szerintem nem pusztán a nagyobb méret miatt, szerintem egy md5+sha1 egymás után írása szerencsésebb, mint mondjuk egy 288 bites md5-variáns.

De itt pontosan errol van szo sajnos szerintem.

De az biztos hogy ez a program konnyeden general ket olyan bementet amiknek azonos a MD5 hash-e, es igy mar az biztos, hogy nem mondhato el az MD5-rol hogy utkozes-ellenallo (CRHF) lenne.

Egyszerübb úgy megérteni imho, hogy az eredeti file, tar iso vagy akármi egy jó nagy szám. A Message Digest algoritmus ebből mint értelmezési tartományból az MD5 fimgerprint értékkészletébe rendel. Most pedig leírták az 'inverz függvényt'.

Annak esélye szinte nulla, hogy ezt biztonsági résként lehessen használni, mert ahhoz az kellene, hogy

1. az eredeti fileról készített fingerprintet beadjuk bemenetként ebbe az inverz függvénybe

2. megvizsgáljuk az összes kimeneti eredményt, hátha olyan kód az a szám az adott computeres környezet számára, ami megtévesztéstésig hasonlít az eredeti filera, és épp véletlenül egy trójaiként használható kódrészt is tartalmaz.

egyedül egyes filecserélőknél lehet ezzel kellemetlenséget okozni úgy, hogy ilyen 'visszagenerált' fileokkal elrontsa vki a tőle épp letöltők adott fileszeletét. Pl. hibás lesz igy a P2P töltögetett film egy részre.

Tökéletes megoldás nincs, mert az ilyen algoritmusok

'értelmezési tarománya' mindig nagyságrendekkel nagyobb mint az 'értékkészlete'. különben nincs sok értelme a fingerprintnek, ha akkora vagy nagyobb mint az eredeti file.

Ha ez kevés megoldás lehet helyette pl. a digitális aláírás.

> Szóba került több helyen, hogy úgy fest, a 128 bit kevés, ideje lépni valami nagyobb értékre. Ebben

> egyetértek, ugyanakkor pont amiatt, mert a dolognak nincsen kialakult bombabiztos matematikája, szerintem

> egy darab valami szabályszerűséget mutató szépen megkonstruált 2N bites hash algoritmus helyett sokkal

> többet ér két tök különböző N bites hash egymás után írása, mert nincsen bennük közös hibamodulus, közös

> támadható felület - nem egy, hanem két algoritmust kell feltörni. Persze kettő helyett lehet még több is. Mint

> ahogy a hír is jelzi: az md5 és a sha1 hash egymás után írása egyelőre még jól állja a sarat, szerintem nem

> pusztán a nagyobb méret miatt, szerintem egy md5+sha1 egymás után írása szerencsésebb, mint

> mondjuk egy 288 bites md5-variáns.

Ebben teljesen egyetértek, bár két algoritmus kétszer annyi idő. Viszont tény, hogy jelentősen megnöveli az adatbiztonságot, pontosan a különböző algoritmusok eltérő sajátosságai miatt. Érdemes lenne ezentúl a csomagokat és az iso -kat (meg mindent) így duplán aláírni.

2.-es pont: pontosan erről van szó, attól hogy két filének ugyanaz a fingerprintje, és az egyik pl. az ssh forráskódja a másik pedig valami bináris zagyvalék lesz, az azért elég feltűnő, nem? :)

>bár két algoritmus kétszer annyi idő.

ez nem igaz. mindket algoritmus ciklusban vegigmegy a bytokon, es csinal veluk valamit. => ossze lehet gyogyitani oket, hogy csak egyszer menjenek vegig a byte-okon.

mar csak egy jo nevet kell kitalani, az osszetett algoritmusnak, es megirni. ;)

így van, ezért nem rejt biztonsági kockázatot. Maximum idegesítő ha a másik töltődik le így hiteles fileként.

prygme azt akarja mondani, hogy rendben, lesznek azonos hash értékű fáljok, de már ezért is dolgozni kell, hogy találjak a kicserélendőhöz egy másik ilyen fájt, de hogy ez a másik fájl még azt is teljesítse, hogy értelmes is legyen, azaz el legyen benne rejtve egy gonosz program bináris szekvenciája, miközben az egész többé-kevésbé hasonlít az eredetire (pl. be lehet boot-olni, mint linux kernelt) annak már igen-igen kicsit a valószínűsége. legalábbis ez utóbbit már nagyságrendekkel több ideig kellene keresgélni. És így végülis nem olyan nagy a kockázat.

> Milyen alternatívákat javasoltok, ami kvázi gyors (mert szerintem az MD%
> relatíve elég gyors volt), legalább olyan sokrétűen használható, mint az
> MD5 (kezdve az adattitkosítástól a különféle állományok
> ellenörző-összegéig), és minél szélesebb körben, többféle rendszeren
> elérhető. Azaz, mi jön az MD5 után...?

SHA1, esetleg kombinálva az MD5-tel.

--
--- Friczy ---
'Death is not a bug, it's a feature'

prygme <prygme@yahoo.com> wrote:
> Ha ez kevés megoldás lehet helyette pl. a digitális aláírás.

Csak épp a digtális aláírás szintén hash-képzésen alapul, és ha a
hash-algoritmusod md5, akkor ....

--
--- Friczy ---
'Death is not a bug, it's a feature'

> Ez igaz? Ha igaz, az eleg baj.

Attol meg hogy ez igaz, nem jelenti azt hogy baj lenne.

Brute force modszerrel lehet keresni ket azonos hash-sel rendelkezo inputot, SOT, ha jol emlekszem regebben mar az rsync listan volt rola szo, hogy veletlenul talaltak ilyet.

Ezekhez hozzafuzve tovabbi (ugyanazt az) adatot pedig az md5 ugyanaz marad, nincs ebben semmi ujdonsag.

Akkor van baj, ha _tetszoleges_ inputhoz konnyen generalhato vele azonos hosszu, hozza nagyon hasonlo tartalmu, vele azonos md5sum-mal rendelkezo output. Itt nem errol van szo.

ui: nem neztem meg nagyon alaposan a kodot, igy ha megis arrol van szo hogy ilyen algoritmust talaltak volna, akkor tenyleg baj van. Kulonben nincs.

A fingerprint viszonylag jó eloszlása garantálja azt, hogy lokális (viszonylag kicsi) változtatásokat marha nagy valószínűséggel "észrevesz" az algoritmus.

Ha létezik két iso kb azonos mérettel akkor és azonos MD5-tel, akkor a két file byte szinten valószínűleg nagyon-nagyon sok helyen eltér egymástól, ráadásul még annak is garantálódnia kellene, hogy a stream:

1. jó filsystem (pl. iso9660)

2. jó állomáynnevek

3. az állományok az opresz számáramegfelelő formátumuak

4. A CPU számára értelemesen végrehajtható utasításokat tartalmaz.

5. Számodra olysható pl. egy szövegfile tartalma (Alfanumerikus karakterek VS teljes ASCII tábla)

6. stb.

Két sör, és már gépelni sem tudok :-))

Az nem túl szerencsés ha MD5-öt használna vki digitális aláíráshoz; bár a magyar törvények szerint az is digitális aláírásnak számít, ha simán az oldal aljára gépeli valaki a nevét :)

Normál esetben, rsa-ban kell két lehetőleg jó nagy prímszám pl. X és Y

és mert D^(X-1)(Y-1)=1(mod XY) így D nem osztható sem X sem Y-al.

Majd kell egy nyilvános kulcs N, és egy titkos T.

NT=1 (mod(T-1)(N-1))

így ha a file le van kódolva az egyik kulccsal, akkor csak a másikkal olvasható vissza

(D^T)^N=D(mod XY)

Mivel csak N a nyilvános valamint a modulusz, ebből nemigen lehet kideríteni, hogy mi az X Y ill. T.

Szóval imho a digitálisan aláírt file továbbra is bobmabiztos módszer arra, hogy megbizonyodhassunk arról, hogy az adott file tényleg hitelesen a nyilvános kulcs tulajdonosától származik. (Persze kitudja lehet, hogy az nsanak már van kvantumszámítógépe :D))

Ugy erzem nem tudod hogy mukodik a digitalis alairas a gyakorlatban...

részletesebben ha kifejtenéd.....

A script már augusztusban is kint volt a neten, bár egyszerűbb formában. Akkor próbáltam ki.

~$ ls -l md5test.pl

-rwxr-xr-x 1 panther users 1018 aug 21 18:21 md5test.pl*

~$ cat md5test.pl

#!/usr/bin/perl -w

use strict;

my $v1=

Na szóval azt akartam mondani, hogy a cikk semmi újat nem mondott: A hash algoritmusnál lehet két különböző bemenet (ezek száma végtelen) esetén azonos kimenet (ezeké meg véges), ráadásul script sem új. Mindkettő megvolt már augusztusban: itt a cik

A digitális aláírás a gyakorlatban úgy működik, hogy először is az
aláírandó adatból képeznek egy hash-t. Az aszimmetrikus kódolással ezt a
hash-t írják alá (úgy is mondhatnánk, hogy az aláíró személy privát
kulcsával elkódolják. Az aláírás ellenőrzője pedig egyrészt az üzenetből
ismét kiszámítja a hash-t, majd az aláíró nyilvános kulcsával
visszafejti az aláíró által küldött hash-t, és összehasonlítja a kettőt.

Ebből következik, hogy hiába bombabiztos az RSA kód (ami egyébként
matematikailag nem bizonyított), ha a hash algoritmus kijátszható.

--
--- Friczy ---
'Death is not a bug, it's a feature'

Öööö, ezt nem értem. A privát kulccsal kódolt üzenetet hogy fejtik vissza a publikussal?

A "collision resistance" és a "one-wayness" nem ugyanaz. Az utóbbi tudtommal nem sérült. Tehát szó sincs arról, hogy egy meglévő hash értékhez tudnának üzenetet hegeszteni, vagy egy meglévő üzenethez azonos hash-t eredményező másik üzenetet.

Amit meg tudnak csinálni, az az, hogy az "elméleti valószínűségből" levezethető próbálkozásszámnál lényegesen kevesebb lépésből tudnak kettő, azonos hash-t eredményező üzenetet generálni. Fontos, hogy nem egy üzenetnek, hanem egy párnak a generálásáról van szó.

Azokban az FTP-s letöltésekben, ahol az MD5 rendes, titkos kulcs használatával készült aláírásban szerepel, az integritás továbbra is védett (harmadik személy nem piszkálhat bele, ha a publikus kulcsot megbízhatóan be lehet szerezni).

A letagadhatatlanság viszont sérül. A teáltalad letöltött csomag lehet egy olyan M' üzenet is, amit az üzemeltető egy M-mel egy párban generált. Nem nehéz kigondolni olyan helyzetet, hogy "fizetsz egy szoftver letöltéséért, amelynek helyes működéséért a gyártó a digitális aláírásával anyagi felelősséget vállal". Ebben a helyzetben fontos lehet, hogy ha M' kinyiffantja a gépedet, a gyártó ne tudjon gyorsan előrántani egy M-et, hogy márpedig ő azt adta el neked, és azt is írta alá. (Persze ezzel azt is állítaná, hogy valaki M-ből szándékosan M'-t tudott csinálni, ami a one-wayness megdöntését jelentené, úgyhogy nem hinnének neki.)

További nehézség az olyan stripwire-szerű támadó számára, aki vírusirtóként spyware-t akar eladni neked, hogy a különbséget csak olyan blokkban rejtheti el, ami az MD5-számára azonos. Ez azt jelenti, hogy (mondjuk programkód esetén) a kódnak tartalmaznia kell a jó meg a rosszindulatú kódot is, ami ugrótáblaként használná a blokkot. (Muszáj ugyanis egy jóindulatú kóddal is rendelkeznie ahhoz, hogy a rosszat letagadhassa.) Viszont a jóindulatú kód a rossztól csak az ugrótáblában különbözik, a beépített funkcionalitásban nem, vagyis visszafejtéssel leleplezhető.

Az ütközés még szerződések elektronius megkötésekor is veszélyt jelent, ld. birthday attack [en.wikipedia.org]. Ezért minden elektronikusan aláírandó szerződésbe bele kell szúrni pár újsort, mielőtt aláírná az ember, nem szabad mástól kapott, előre gyártott szerződést sign-olni.

Olvassátok el ezt is [www.securityfocus.com].

Bocs, ha szétcsúszott, mindjárt elalszom.

Micskó Gábor wrote:
> Ez igy van. Viszont erre mondta multkor PaXTeam a kovetkezoket:
>
> Szerző: PaXTeam (pageexec (a) freemail hu) Ideje: Augusztus 20, Péntek,
> 21:37:42
>
> (Adatok | Üzenet küldése) http://pax.grsecurity.net
>
> (HASH: 0efe-81f5)
>
> nem feltetlenul kicsi, ha megnezed a peldakat, akkor lathatod, hogy az
> utkozo bytesorozatok csak nehany bitben ternek el egymastol, ez pedig eleg
> lehet arra, hogy pl. egy felteteles ugroutasitast atirjon valaki (pl.
> jelszoellenorzo kodban).

a stripwire -ben hozott binarisok pontosan 6helyen ternek el egymastol. byte -ra
ugyanaz az eredmeny, megis van elteres, igaz nem tul nagy. Ha mar 2db 128byte
-os binarisban is ennyi elteres lehet, akkor egy nagyobb forraskodban, mint pl
egy kernel, igen nagy zuroket okozhat.

Szerintem...


IroNiQ
--
Web: http://ironiq.hu
Email: iron@ironiq.hu
LinuxCounter: #331532

> Öööö, ezt nem értem. A privát kulccsal kódolt üzenetet hogy fejtik vissza a
> publikussal?

Ahogy a publikussal kódolt üzenetet a priváttal. Az aszimmetrikus
titkosításnak az a gyakorlati lényege, hogy az egyik kulccsal elkódolt
üzenetet csak a párjával lehet visszafejteni. A két kulcs alapvetően
egyenértékű, generálás után az egyiket kinevezik privátnak, a másikat
publikusnak, de az algoritmus oda-vissza működik.

--
--- Friczy ---
'Death is not a bug, it's a feature'

Igen, de ennek a digitális aláírásnak a "párja" a titkosítás, amikor nem azt akarjuk elérni, hogy tudja a címzett, hogy tőlünk van, hanem hogy CSAK ő tudja elolvasni. Namostha a címzett publikus kulcsával kódolt _hash_-t a címzett dekódolja a saját privát kulcsával, akkor ő csak a hash-t tudja megtudni, amiből nem lehet megtudni az üzenetet. Épp ezért nem hiszem, hogy az ilyen dogoknál (a digitális aláírást is beleértve) a hasht kódolnák...

> Igen, de ennek a digitális aláírásnak a "párja" a titkosítás, amikor nem
> azt akarjuk elérni, hogy tudja a címzett, hogy tőlünk van, hanem hogy CSAK
> ő tudja elolvasni. Namostha a címzett publikus kulcsával kódolt _hash_-t a
> címzett dekódolja a saját privát kulcsával, akkor ő csak a hash-t tudja
> megtudni, amiből nem lehet megtudni az üzenetet. Épp ezért nem hiszem, hogy
> az ilyen dogoknál (a digitális aláírást is beleértve) a hasht kódolnák...

A dolog nem attól függ, hogy te mit hiszel, vagy sem. Pláne, ha
félreérted a leírtakat :)

Az aláírásnál az aláíró a saját privát kulcsával kódolja el a hash-t.
Ezt csak az aláíró publikus kulcsával lehet dekódolni (nem pedig a
címzett privát kulcsával, ahogy te írtad). Ha biztos vagyok benne, hogy
az aláíró publikus kulcsát ismerem, és azzal dekódolni tudom a hash-t,
akkor biztos lehetek benne, hogy ezt a hash-t az aláíró személy kódolta
el.

--
--- Friczy ---
'Death is not a bug, it's a feature'

Aham. Köszönöm a választ! Újat tanultam (nem tudtam, hogy fordítva is működik). De csak most esett le, hogy miért így van :)

> Az aláírásnál az aláíró a saját privát kulcsával kódolja el a hash-t.

> Ezt csak az aláíró publikus kulcsával lehet dekódolni (nem pedig a

> címzett privát kulcsával, ahogy te írtad).

Ezt a részét a dolognak én értem, csak itt a titkosításról beszéltem.

Már kezd rosszul állni a szénám, vagyis valószínűleg én vagyok kevéssé informálva, ezért világosítsatok fel. Az elég valószínű, hogy titkosításnál (ha azt akarom hogy a címzetten kívül más ne tudja az üzenet tartalmát) nem a hasht kódolják le, mint fentebb is írtam. Akkor a digitális aláírásnál miért a hash-t kódolja le az illető (ugye a saját privát kulcsával), az egész üzenetet miért nem lehet? Na erre kérek akkor egy választ.

Kösz: én.

A nyilvanos kulcsu(aszimmetrikus) titkositas "draga".

Ezert altalaban csak a hasht kodoljak el alairaskor.

Ugyanez az oka, hogy titkositaskor altalaban hibrib modszert alkalmaznak: aszimmetrikus es szimmetrikus kodolas vegyiteset: aszimmetrikusan csak egy szimmetrikus kulcsot kodolnak el, majd szimmetrikusan magat az egesz uzenetet.

Tovabba:

* alairaskor, mivel csak a hasht kodolod el, az eredeti uzenet barki altal olvashato marad. Ez sok esetben jo dolog.

* titkositaskor pedig olyan titkos uzenetet is keszithetsz a hibrid modszerrel, amit tobb szemely is dekodolni tud es megsem noveled meg a titkositott uzenet meretet jelentosen. Ugyanis maga az uzenet mindig a szimkulccsal lesz csak elkodolva es a szimkulcsot(ami kis mennyisegu adat) kell csak annyifelekeppen elkodolnod, ahany embernek szanod az uzenetet.

> Már kezd rosszul állni a szénám, vagyis valószínűleg én vagyok kevéssé
> informálva, ezért világosítsatok fel. Az elég valószínű, hogy titkosításnál
> (ha azt akarom hogy a címzetten kívül más ne tudja az üzenet tartalmát) nem
> a hasht kódolják le, mint fentebb is írtam.

Titkosításnál egy véletlen kulcsot (session key) generál a rendszer,
magát az üzenetet ezzel a kulccsal kódolják el (szimmetrikus kódolással,
lehet pl. 3des, AES, vagy bármi, ami megfelelő erősségű. A címzett
publikus kulcsával a session key-t kódolják el. A címzett a saját privát
kulcsával vissza tudja olvasni a session key-t, és a session key
segítségével az egész üzenetet.
> Akkor a digitális aláírásnál
> miért a hash-t kódolja le az illető (ugye a saját privát kulcsával), az
> egész üzenetet miért nem lehet? Na erre kérek akkor egy választ.

Ugyanazért, amiért a kódolásnál is a session-keyt kódolják. Az
aszimmetrikus kódolásnak sok jó tulajdonsága mellett van egy roppant
nagy hátránya: sokkal lassabb, mint a szimmetrikus. Egy hosszú üzenet
(akár több megabyte) RSA kódolással történő titkosítása nagyon hosszú
ideig tarthat, így gyorsabb, és közel ugyanazt a biztonságot nyújtja
(feltételezve, hogy a hash függvény jó, innen indultunk ki).

Titkosításnál van még egy előny: ha több címzett van, akkor csak a
session keyt kell minden címzett publikus kulcsával elkódolni, így az
üzenet rövidebb lesz, mintha ugyanazt mindenkinek külön-külön
elkódolnák.

--
--- Friczy ---
'Death is not a bug, it's a feature'

Köszönöm szépen a felvilágosítást, neked és samsonnak is.