[matematika] halmazelméleti feladat

Algoritmusok

Bizonyítsd be, hogy létezik olyan a!=b; a,b ∈ (eleme) MD5SUM,
amire md5(a)=md5(b)

azaz létezik két különböző md5sum, amiknek az md5sumjuk ugyanaz.

szerk. rossz megoldás kivéve.

  • 5249 megtekintés

( bri | 2011. 05. 04., sze – 15:06 )

bruteforce? csak 340282366920938463463374607431768211456 hash-t kell megvizsgálni!

viccet félretéve: szerintem valószínű, de az md5 természetét valamennyire ismerve nem hiszem, hogy találnál a bruteforce-nál elegánsabb megoldást. amiért valószínű: az MD5SUM halmaz elemszáma 16^32, te pedig egy olyan leképezést konstruálsz meg, ami minden elemhez hozzárendel egy másik elemet ugyanebből a halmazból. statisztikailag (ami md5 hashek vizsgálata esetén annyira nem lehet rossz közelítés) annak az esélye, hogy az ilyen módon létrehozott hozzárendelés bijektív, majdnem 0.

fixme!

alias killall='echo "Wenn ist das Nunstück git und Slotermeyer? Ja. Beiherhund das Oder die Flipperwaldt gersput." | espeak -vde' #That's not funny.

értem én, de a feladatnak megoldása, ha találsz egyet, pontosabban kettőt, aminek ugyanaz. kis szerencsével hamar meglesz, kis szerencse nélkül meg küldd ki computing gridbe. ;)

alias killall='echo "Wenn ist das Nunstück git und Slotermeyer? Ja. Beiherhund das Oder die Flipperwaldt gersput." | espeak -vde' #That's not funny.

( tomaza | 2011. 05. 04., sze – 15:45 )

- vannak az md5-nek olyasmi tervezési szempontjai hogy (hasraütök!) pl.: 1bit hibát ki kell tudnia mutatni, vagy ha 4 közel van egymáshoz azokat is.. talán van ezek közt valami olyasmi (de nem hiszem) amiről lehet következtetni arra hogy ilyen kicsi adatot meg kell tudnia különböztetni

- picit a fentebbi statisztikkához kapcsolódó: mivel az md5 nem 128 hanem 512-es blokkokban dolgozik, a maradékkot paddinggal kitölti amit az addigi adatokból generál, azaz nem egy permutáció(szerűséget) fog végrehajtani hanem tényleg számításba jön az hogy egyszerűen statisztikai alapon lesz ütközés, tehát lesz két md5 aminek az md5-e egyezik

lezserül fogalmaztam mert így rövidebb és még érthető, de ha nem érthető akkor nálad van a hiba
"hiba": nem értem mi a gondod, egyik felhasználása az ilyen hash kódoknak a hibakimatatás, egy hosszab "szövegben" fordult-e át bit
"ki kell mutatnia": igen, _tervezik_ az ilyen kódokat, akármekkora adatmennyiségben egy bithibát vagy bizonyos típusú csomózódásokat, pl ha jól rémlik 4-et ki kell ha közel vannak egymáshoz (nem tudom, talán 256 bitnyire max, de pl 3 bithibát már nem, sőt az is lehet keverem más hash-el, de ilyen jellegű bizonyított tulajdonságai biztos vannak)

mondj rám bármit, de most tényleg nálad van a hiba

ha elég sokat foglalkoztál akkor értened kell mit értek alatta, szal csak kötözködsz
az 1 bit példa volt, szándékosan egyszerű hogy érthető legyen mire gondolok, és mert nem ismerem ilyen jól az md5-ö5t hogy fejből vágnám pontosan miket tud

btw: ha elég sokat foglalkoztál akkor a kérdésre is válaszolhatnál ;)

"The message is "padded" (extended) so that its length (in bits) is
congruent to 448, modulo 512.
"

http://www.ietf.org/rfc/rfc1321.txt
..megint lezserül fogalmaztam, mert gondoltam mivel már _írtam_ ezt, csak azt pontosítottam, és semmi lényegi köze a feladathoz, gondoltam senki nem köt bele, szóval mégegy akki örül hogy a feladatot megértette (már aki elolvasta:) , és a kérdést újra le tudta írni mint lentebb, meg többen ezen a node-on.. ?

:)

( bigwig | 2011. 05. 04., sze – 15:49 )

Megprobalom megegyszer: http://hup.hu/node/9721

Ha a kerdes elmeleti, akkor meg nem ertem. Az MD5 hash fuggveny. Tipikusan egy hash fuggveny ertelmezesi tartomanya vegtelen, ertekkeszlete veges. Utkozes van.

nem az a kérdés van-e ütközés, hanem hogy pontosan 128biten van-e ütközés, márpedig van olyan hash ami nem ütközik, permutációnak hívják

azok az ütközéskereső cikkek, programok, 128-tól sokkal nagyobb (most nem tudom, azt hiszem 512bites vagy 256 byteos) ütközéseket hoznak csak példának, iletve szándékos generált pl pdf-ben is az eltérő rész ekkora

( mrev | 2011. 05. 04., sze – 15:55 )

Pofonegyszerű. Az md5sum függvény szétszortírozza a halmazokat anyiféle dobozba, ahány féle értéke lehet az md5sumnak. Ez egy véges szám. Akármekkora is ez a szám, létezik ennél több különböző halmaz (végtelen van). Emiatt lesz olyan doboz, amibe a szortírozás során egynél több halmaz jut.

--
CCC3

Ha jol tudom,az teny, hogy az osszes 128bites szam eloallithato md5summal, ez a kimeneti ter. Viszont, ha letezik olyan collision, hogy ket 128bites szam md5sumja ugyanaz, akkor az azt jelenti, hogy a 128bites inputok kimeneti tere kisebb mint 128 bit.

Ha ez sikerul,akkor meglenne az eredeti kerdesre is a valasz. En nem latom, hogy az algoritmusban lenne nem-injektiv muvelet.

nem egyszeruen a feltett kerdes, mert lehetne mas kibuvo is, peldaul ha nem igaz, hogy az osszes 128bites szam eloall md5sumkent.

nem-injektiv muvelet : altalaban ha a kepter kisebb mint az ertekkeszlet.

a modulo fuggveny ilyen, 2*2 mod 10 = 102*2 mod 10

Ami kapora jon, hasznalnak mod fuggvenyt abban a reszben is, ami a 128 bites uzenetre vonatkozik, nem csak a kiegeszitettben (van egy csomo rotate, ami miatt a mod ervenyes lesz ezen a teruletes is). Szoval van informacioveszteseg, bizonyos byteok legfelso bitje sosem lesz hatassal a kimenetre, ha jol ertem. Mar csak azt kell megtalalni, hogy valami trukk folyaman valahol ujrahasnositjak-e ezeket a biteket, vagy sem. Javitson ki valaki, ha ez hulyeseg.

Szerk: tevedtem, a wikipedias algoritmusban rosszul ertelmeztem mi az az i valtozo, amin alkalmazzak a modulo fuggvenyt.

az igen-igen csúnya lenne, ha meg lehetne fogni, hogy melyik bájtoknak melyik bitjeit módosíthatjuk úgy, hogy ne változzon tőle az md5 hash :)

alias killall='echo "Wenn ist das Nunstück git und Slotermeyer? Ja. Beiherhund das Oder die Flipperwaldt gersput." | espeak -vde' #That's not funny.

( oldhercules | 2011. 05. 04., sze – 17:06 )

igazából másképpen is lehetne fogalmazni:
az md5 tetszőleges n bites blokkból generál 128 bites hash-t. mivel n lehet nagyobb mint 128 garantált az ütközés
a kérdés pedig az, hogy ha n=128, akkor is előfordulhat-e ütközés
(felételezve, hogy az MD5SUMS == 128biten ábrázolható számok)

( szemet | 2011. 05. 04., sze – 18:17 )

Talán segít, hogy ezzel a módszerrel akartak brute-force ütközést találni, mielőtt sikerült analitikusan is ez-az:
http://en.wikipedia.org/wiki/MD5CRK

Talán innen kiindulva találsz valami egzaktabb levezetést a feedback ciklus méretének várhatóértékére...

( tomaza | 2011. 05. 04., sze – 21:31 )

látom hogy oda van írva a megoldás, de a gyengébbek kedvéért az eredményt is odaírhatnád :)

nem tudom hogy mi az a "null", de azt nem írtad hogy a körön van-e..

odaírtam a megoldást :) - ez matematikailag bizonyítja, hogy van.
Brute force elő lehet állítani, csak idő kell hozzá. A csatolt forrás szerint egy mai 2 gigaflops-os processzorral úgy 346 év alatt, a kína Tianhe-IA szuperszámítógéppel (2,566 petaflops) kb 2,5 óra alatt előállna az eredmény :)

( szemet | 2011. 05. 04., sze – 21:37 )

Szerintem nem jó ez így. Mert mi még itt a garancia, hogy körön kívülről indulsz vagy indulhatsz? (Vagy csak nem értem a "NULL" értelmét...)

Ha pl. 1 kör van, vagy csak diszjunkt körök vannak amik között nincs átjárás, akkor nem ok. Ugye azt kéne épp belátni talán, hogy nem így van, azaz lehetséges körön kívüli 128 bittel bejutni egy körbe...

(Miután javasoltam ezt a körkereséses wiki oldalt, pont erre gondoltam, hogy ez így önmagában még mindig kevés lesz - vagy csak én nem értem;)

annak a null-nak a hossza nem 128 hanem 0 bit, és nem bizonyít semmit ez a megoldás, csak hogy nem olvastad el ezt, és ezt

semmit, de semmit nem használtál fel az md5-ből, csak hogy egy fv.

128 biten ettől még lehet egy permutáció is az md5, azaz körbejárod mind a 2^128 lehetőséget, meg lehet nem permutáció is, tehát valóban a körön kívülről indulsz, ezzel csak a bruteforcot gyorsítod, nem bizonytasz semmit

inkább nem példát mondanék hanem hogy hol hibázott: ha az első lépésben belép a körbe akkor az a piros pont előtt két fekete közül a jobboldali egyszerűen nem része a kérdéses halmaznak, nem "eleme md5", márpedig ő feltételezte hogy az a fekete az tényleg fekete lesz, hisz ott van a rajzon