További részletek az SHA1-ről

Titkosítás, biztonság, privát szféra

Bruce Schneier blogjában további fejtegetéseket olvashatunk a pár nappal ezelőtt felröppentett SHA1 ügyről. Schneier szerint megszületett az első olyan támadási lehetőség az SHA1 ellen, amely gyorsabb, mint a brute force támadás.

Három kínai crypto szakember pár nappal ezelőtt megmutatta, hogy az SHA1 nem ütközés-mentes. Elkészítettek egy olyan algoritmust, amely gyorsabban találja meg az ütközéseket az SHA1-ben, mint ha valaki nyers erővel próbálná meg feltörni azt.A felfedezés szerint már nem 2^80-on próbálkozás kell ahhoz, hogy ütközést találjanak az SHA1-ben, hanem csak 2^69-en. Ez azt jelenti, hogy 2.000-szer gyorsabban lehet eredményt elérni, mint a brute force megoldással.

A szakember, hogy érzékeltesse a problémát az alábbi példát hozta:

1999-ben egy csapat titkosítási szakember épített egy DES törő gépet. A gép 2^56-on DES műveletet végzett el 56 óra alatt. A gép 250 ezer dollárban került, de másolatok már készíthetők 50-75 ezer dollárból is. Moore törvényének értelmében, ha hasonló gépet építenénk ma, az már 2^60-on műveletet tudna elvégezni 56 óra alatt, és 2^69 számítást három és negyed éven belül. Vagy egy 25-30 millió dolláros gép már most el tud végezni 2^69-en műveletet 56 óra alatt.

A szakember példaként hozta az elosztott számítást is. Például a Distributed.net által végzett sikeres kódtörést 2002-ben.

Néhány szakember a dologról:

Jon Callas, PGP:

"It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off."

Érdekes olvasmány. Érdemes elolvasni.

Szerencsére a szakemberek szerint van megoldás. Ezek lehetnek az SHA-224, SHA-256, SHA-384, és az SHA-512.

Az írás itt.

( snq- | 2005. 02. 19., szo – 20:21 )

>> Ez azt jelenti, hogy 2.000-szer (2048) gyorsabban lehet eredményt elérni, mint a brute force megoldással

ez is brute force

>> Három kínai crypto szakember pár nappal ezelőtt megmutatta, hogy az SHA1 nem ütközés-mentes

mivel egyetlen hash funcio sem utkozesmentes (hashmeret altalaban kisebb mint a bemeneti adatok merete, tehat ez termeszetes), sok ujat nem mondtak el ezzel. max azt, hogy a malicsuszok max 2^69 probalkozasbol tudnak prezentalni egy zagyvalekot, aminek a hash-e megegyezik az en adataim hash-evel (aminek a tartalmat a malicsusz nem ismeri). fajlcserelo halozaton biztos kellemetlen tud lenni

> fajlcserelo halozaton biztos kellemetlen tud lenni

Gondolom ennek tudomanyos jelentosege van. Ha valaki ir egy algoritmust, ami valamit 2.000-szer gyorsabban csinal, mint a mas elotte, az mar magaban is szenzacio. Plane ha az a valaki egyetemista. Szakdolgozatnak nem lesz rossz. Rosszul gondolom?

Nem, nem erről van szó. Tegyük fel hogy a linux rendszered nem md5-tel, hanem sha1-el kódolva tárolná a jelszavak hash-ét a shadow fileban, mert (eddig) az SHA-1 jóval biztonságosabbnak tűnt, mint az md5 (nem tudom most mi a helyzet). Ezek után ha valaki valahogy megszerzi a shadow-t, gyorsabban tud egy olyan jelszót generálni, amivel be fog tudni lépni, mert a hash-e ugyanaz lesz mint mondjuk a root-nak, hiszen a belépési információ a user/pass pár helyett valójában a user/password_hash pár.

A linux itt rossz példa, mert md5 a szabvány, viszont a legtöbb helyen (pl. a pgp, openpgp szabványokban is) a secure digest algoritmus sha-1. És ha van gyorsabb algoritmus, akkor lehet célhardvert készíteni. Nem abból kell kiindulni hogy engem nem érint, és hogy ez még mindig "elég lassú" algoritmus, hanem abból, hogy az sha-1 elvi törhetetlensége csorbult. Ez _majdnem_ olyan mintha azt mondták volna, hogy az RSA elméletileg hibás/gyenge.

nezd, ha mar meg tudja szerezni a shadow-t, akkor felesleges pocsolnie (foleg mivel az altala generalt 'jelszo' lehet, hogy 700 billiard karakteres lesz).

>> ..hanem abból, hogy az sha-1 elvi törhetetlensége csorbult

egy one-way-hashnel sztem nincs ertelme torhetosegrol beszelni, egszeruen arrol van szo, hogy konnyebben lehet utkozest talalni, mint gondoltak anno. de sztem sem lehet szo nelkul elmenni a dolog mellett, mivel kevesebb hiba biztos nem lesz benne, csak tobb

snq- <snq@freemail.hu> wrote:
> egy one-way-hashnel sztem nincs ertelme torhetosegrol beszelni, egszeruen
> arrol van szo, hogy konnyebben lehet utkozest talalni, mint gondoltak anno.
> de sztem sem lehet szo nelkul elmenni a dolog mellett, mivel kevesebb hiba
> biztos nem lesz benne, csak tobb

Az SHA-1 és MD5 algoritmusok gyengeségének az elektronikus aláírás
esetén van elég nagy jelentősége. A múltkori MD5-mizéria is arról szólt,
hogy viszonylag könnyű úgy megváltoztatni egy szöveget, hogy ugyanaz
legyen a hash érték, mint az eredetié. A lényeg ezen volt, és nem az
ütközésmentességen. Így ugyanis megoldható, hogy aláírt szövegnek
tüntessünk fel egy olyat, ami nem volt ténylegesen aláírva, és ez egy
elektronikus úton kötött szerződés esetében több, mint kellemetlen.

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

>> és ez egy

elektronikus úton kötött szerződés esetében több, mint kellemetlen

tehat a peldadban a malicsusz ismeri az eredeti szerzodes szoveget, es keszit egy olyan szoveget, ami 1) ertelmes, 2) szamara kedvezobb, mint az eredeti, 3) a hash-e megegyezik az eredetievel. sok sikert hozza. ha esetleg keszen van vele, es perelni akar, bemutatom az eredeti szerzodest (hash ugyanaz, birosag dont)

> tehat a peldadban a malicsusz ismeri az eredeti szerzodes szoveget, es
> keszit egy olyan szoveget, ami 1) ertelmes, 2) szamara kedvezobb, mint az
> eredeti, 3) a hash-e megegyezik az eredetievel. sok sikert hozza. ha
> esetleg keszen van vele, es perelni akar, bemutatom az eredeti szerzodest
> (hash ugyanaz, birosag dont)

Na igen. Persze nem biztos, hogy a bíróság neked kedvező módon dönt,
pláne, ha a szerződés nem mindkét fél által aláírt szerződés, hanem
esetleg egy adott időszakon belül kötelező árajánlat, amit csak te írtál
alá. Ilyen esetben a nálad lévő aláírt példánnyal nem sokra mész,
elvégre azt te bármikor kreálhattad, viszont a partnernél lévő aláírt
szöveget bajosan tagadod le.

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

elmeletben sokminden elofordulhat. a fenti peldat igazabol a "viszonylag könnyű úgy megváltoztatni egy szöveget, hogy ugyanaz

legyen a hash érték, mint az eredetié" hozzasolasodra irtam. sztem jelenleg ott tart a dolog (md5 vagy sha1), hogy iszonyat szamitasi munkaval lehetseges olyan ertelmetlen bitsorozat megtalalasa, aminek a hash-e megegyezik egy masikeval. de az, hogy az eloallitott szoveg reszben ertelmes legyen + garbage, neadjisten teljes egeszeben ertelmes legyen...

Gentoo alatt ugye forrásokat töltesz le, és a portage a csomag forrás csomagjának az MD5jét tárolja. Telepítettem valamit, letöltötte a portage a fájlt, az MD5 egyezett a tárolttal a fájl viszont hibás volt. Letöltöttem mégegyszer, és akkor jó volt. (Szóval az MD5 jó volt).. Ritka eset, de megtörténik.