http://eprint.iacr.org/2004/199.pdf un http://www.md5crk.com/md5col.zip

Tajā pdfā ir nekorekts pierādījums. Viņi nepareizu sākuma vekotru paņēmuši bija. Īstajam MD5 vēl nekas nav pierādīts.

Par ko ir springtne?

neviens nav teicis, ka md5 nevar būt šāda problēma. respektīvi nav pierādīts ne tiešais, ne apgrieztais, tādēļ šāda lieta ne tā ka ļoti izbrīnītu...

Teorētiski jau jebkurai hash funkcijai tiek pieļautas kolīzijas - jautājums ir tikai cik liela ir varbūtība, ka kolīzija gadīsies?

vot, vot - kaa jau kaklz teica. peec Dirihlee principa, ja mums ir hasha rezultaats uz n bitiem, tad njemot visas n bitu mesaages + veel vienu mees dabuusim vismaz vienu koliiziju. Alelujah!

viss loģiski, pilnīgi unikāls hash varētu būt tikai tieši tāda paša garuma vai grāks kā saturs, kurš tiek hašots; ar galvu padomaajot, tur nav nekas jauns vai nebijis.

http://www.freedom-to-tinker.com/archives/000663.html http://diveintomark.org/public/2004/08/md5crack.py

Ja nemaldos, runa ir par to, ka līdz šim tā bija teorija - uzģenerēt divus dažādus sūdasūdus ar identisku MD5 var, bet tīšām to izdarīt ir nejēgā grūti.

Un te nu cilvēki, ja nemaldos, ir to izdarījuši apzināti :) Protams, ja es visu saprotu.

Neviens jau nestrīdās par to, vai MD5 ir unikāla čeksumma, vai nav (pēdējais ir pareizais vairants). Runa, kā jau minēju, ir par to, ka šāda čeksumma vairs nav kritērijs, uz kuru varētu paļauties.

Jap, par to tiešām springtne ir. Ātrais lasāmgabals, ko ar to iesākt, atradās šitāds, nepretendējot uz pilnību: http://citeseer.ist.psu.edu/cache/papers/cs/23311/http:zSzzSzdenis.ijs.sizSzstudentszSzpubzSzcsitrcek.pdf/minimising-the-risk-of.pdf

abet SHA-1 tak veel ir OK ?

Patīk man šie komentāri par to ka nav pierādīta ne kolīziju esamība, ne neesamība atsevišķām hash funkcijām. Manuprāt, Dirihlē principu, ar kura palīdzību katrai hash funkcijai var pierādīt, ka tā rada kolīzijas, māca skolas matemātikā 5. klasē.

tad jau gan skolas tagad advanceejushaas. manos laikos veel neko taadu nemaacija ;)

fxz, aha - es ne*iju skolā tajā dienā, kad mācīja urtu "", tapēc tagad tādu nemāku.

Arturs, nevis kolīziju esamība vai neesamība, bet tiešām algoritma kolīziju atrašanai esamība vai neesamība. Saproties, cilvēki tic, ka viņas ir ļoti grūti atrodamas, bet matemātiski pierādīts tas nav, un reku daži parāda, cik ļoti nav.

Algoritms kolīziju atrašanai? Lūdzu:

for i=1 to 2^HashFunction.bitCount+1 for j=1 to 2^HashFunction.bitCount+1 if (i <> j) and (hash(i) == hash(j)) output(i, j)

Cita lieta ir, ka varbūt polinomiāla laika algoritms neeksistē, bet nu augstāk minētais jau arī ir algoritms.

Nuja. Neprecīzi izteicos. Bet tajos rakstos jau figurē 2 ^ daudz_mazāk, un par to arī bēda.

Nē. http://www.cryptography.com/cnews/hash.html

tas gadijumaa nebija rakstiits jau MD5 specifikaacijaa?

btw, adresee no 19. komenta raxtiits, ka ar shito SSL sertifikaatus gaazt nevar, bet var gaazt digitaalos parakstus.

tagad, njemot veeraa, ka cilveeku rakstiitaa valoda nav kompakts storage format (tb ir ljoti viegli kompreseeejama), no kaa izriet, ka nepietiek ar random burtu virkni, lai dabuutu jaunu message textu, ko paraxtiit ar to pashu paraxtu. veel mazaaka iespeejamiiba.

man jau liekas, ka 2+2=4 un 3+1=4 !!! :) Arī "A" + "B" = "C" + "@" , vai ne? Tās ir manas speciāli radītās kolīzijas! :))))

Kirils, ko nu izdomāji... Doma it kā pareiza, bet ne jau "kompakts storage format" ir īstais vārds. Toties manā ielinkotajā pdfā (un droši vien arī MD5 specifikācijā) ir minēts, ka jis apstrādā doto virkni pa blokiem, no kā tiešām izriet, ka pietiek kolīzēt daļu ziņojuma, piemēram, lietotājam neredzamu HTML komentāru, un vakars klāt. Tas laikam nozīmē, ka e-dokumentu sistēmas būs jādizainē tuvu plaintextam... Ļoti jauki, return to innocence.