md5 коллизии

← →
cmp (2007-01-02 14:29) [0]

Помнится толи пару лет назад, толи несколько месяцев назад некая группа математиков отыскала возможность в алгоритме хэширования md5 получать коллизии. Но т.к. я не слишком дружу с математическо-криптографичискими терминами и не слишком хорошо понял эту ситуация. Объясните пожалуйста мне, что же собственно произошло: в каком смысле используются такие коллизии? Т.е. их алгоритм позволяет за несколько часов отскать такую пару данных, от которых возможно получить одинаковый хэш, я прав или нет?

← →
vidiv © (2007-01-02 14:33) [1]

> Т.е. их алгоритм позволяет за несколько часов отскать такую
> пару данных, от которых возможно получить одинаковый хэш,
> я прав или нет?

отыскали бы уже... пока прецендентов не было...

← →
Ученик чародея © (2007-01-02 14:41) [2]

> vidiv © (02.01.07 14:33) [1]
>
>
> > Т.е. их алгоритм позволяет за несколько часов отскать
> такую
> > пару данных, от которых возможно получить одинаковый хэш,
>
> > я прав или нет?
>
> отыскали бы уже... пока прецендентов не было...

Были. На LOU был линк на статью, где приводились два файла с одинаковыми md5.

← →
Real © (2007-01-02 14:42) [3]

Я тоже думаю всплыло бы где нить. А кто вообще разбирается в md5 в смысле алгоритма? Каким образом достигается необратимое шифрование и гарантия что одни и теже данные - дадут один и тот же хеш?

← →
Zeqfreed © (2007-01-02 14:46) [4]

Коллизии, разумеется, возможны. Но вот о легком пути их нахождения не слышал.

← →
DillerXX © (2007-01-02 14:52) [5]

Были уже, этот шум больше года назад был.. вроде как, какой-то математик на своём ноуте за 40 минут (если правильно запомнил) подобрал ту строку, хешировав которую, получается исходный хеш. Конечно, скорее всего, это была любая строка из множества строк, хеши от которых совпадали бы. На сколько я понял, такие совпадения в хешах и называются коллизиями.
У моего друга есть программа, которая и находит такие коллизии к хешам. Но, по его словам, входные данные там надо представлять в какой-то особой форме, и только тогда программа что-то найдёт. Типа "защита от ламера", чтоб всякие не пользовались. У него мат. базы не хватило для того чтобы понять как это всё устроено, если надо, могу выложить.

← →
Anatoly Podgoretsky © (2007-01-02 14:55) [6]

> Real (02.01.2007 14:42:03) [3]

Гарантия сто процентная

← →
Axis_of_Evil © (2007-01-02 15:01) [7]

Real © (02.01.07 14:42) [3]
гарантия что одни и теже данные - дадут один и тот же хеш?
алгоритм как-никак.

← →
Anatoly Podgoretsky © (2007-01-02 15:07) [8]

> Axis_of_Evil (02.01.2007 15:01:07) [7]

Он наверно думает, что каждый раз MD5 создает хеш с помощью генератора случайных чисел. Нафиг такой алгоритм нужен, если повторяемость не гарантируется.

← →
ferr © (2007-01-02 15:23) [9]

некоторые хеш-функции используют методы генерации случайных чисел, это удобно.

← →
Anatoly Podgoretsky © (2007-01-02 15:29) [10]

> ferr (02.01.2007 15:23:09) [9]

Скажи нафиг нужна такая функция, если проверить хеш не удастся?

← →
Real © (2007-01-02 15:29) [11]

> Он наверно думает, что каждый раз MD5 создает хеш с помощью
> генератора случайных чисел. Нафиг такой алгоритм нужен,
> если повторяемость не гарантируется.

Очень рад что вы на моих постах тестируете свой телепатор :) Но мне казалось что я довольно понятно задал вопрос: интересуют приниципы заложенные в алгоритм, а то что гарантия 100% - понятно итак, иначе какой бы толк был если бы работало через раз?

← →
cmp (2007-01-02 15:29) [12]

http://www.mscs.dal.ca/~selinger/md5collision/

Ссылка с примером, но приведенный пример меняет то о чём я думал, в примере две работоспособных программы с одинаковыми хэшами; под винду и под никс. Я думал, что коллизии только под какие-то рандомные данные можно отыскать, а тут...

← →
DillerXX © (2007-01-02 15:32) [13]

> Ссылка с примером, но приведенный пример меняет то о чём
> я думал, в примере две работоспособных программы с одинаковыми
> хэшами; под винду и под никс. Я думал, что коллизии только
> под какие-то рандомные данные можно отыскать, а тут...

То что в этом алгоритме есть коллизии, это очевидно. Он всегда возвращает строку длиной 32 символа, и принимать может любой размер строки на вход. Ну ясен пень, если мы подставим строку длиной 33 символа, коллизии возникнут 100%

← →
DillerXX © (2007-01-02 15:33) [14]

Тьфу, не так понял пост, извиняюсь.

← →
Real © (2007-01-02 15:34) [15]

> То что в этом алгоритме есть коллизии, это очевидно. Он
> всегда возвращает строку длиной 32 символа, и принимать
> может любой размер строки на вход. Ну ясен пень, если мы
> подставим строку длиной 33 символа, коллизии возникнут 100%

Если тебе так понятно, изложи свое понимание алгоритма?

P.S. Лень гуглить и читать официальные статьи :)

← →
ferr © (2007-01-02 15:36) [16]

> Скажи нафиг нужна такая функция, если проверить хеш не удастся?

Перечитывайте что я написал. Так например если в метод линейного зондирования добавить прыжки на "случайные" расстояния то можно будет избежать "кластеризации".

← →
ferr © (2007-01-02 15:37) [17]

> Если тебе так понятно, изложи свое понимание алгоритма?

хеш - отображение более мощного множества, в более маломощное :) => быть инъективным оно не может.

← →
vidiv © (2007-01-02 15:40) [18]

> Были. На LOU был линк на статью, где приводились два файла
> с одинаковыми md5.

как говориться, в стуию

← →
Джо © (2007-01-02 16:04) [19]

> [18] vidiv © (02.01.07 15:40)
>
> > Были. На LOU был линк на статью, где приводились два файла
>
> > с одинаковыми md5.
>
> как говориться, в стуию

А что, вполне нормальная ситуация. Таких файлов существует бесконечное множество, собственно.

← →
vidiv © (2007-01-02 16:09) [20]

> Джо © (02.01.07 16:04) [19]

проверил... жаль =(

← →
Джо © (2007-01-02 16:19) [21]

> [20] vidiv © (02.01.07 16:09)
> проверил... жаль =(

А как ты представляешь себе (чисто логически) преобразование бесконечного множества файлов к бесконечному множеству 32-символьных строк? Таких строк, по определению, существует вполне себе конечное множество.

← →
Ученик чародея © (2007-01-02 16:27) [22]

> vidiv © (02.01.07 15:40) [18]
>
>
> > Были. На LOU был линк на статью, где приводились два файла
> > с одинаковыми md5.
>
> как говориться, в стуию

http://linux.org.ua/cgi-bin/yabb/YaBB.pl?num=1133705914
http://linux.org.ua/cgi-bin/yabb/YaBB.pl?num=1110535173

← →
Real © (2007-01-02 16:30) [23]

> А как ты представляешь себе (чисто логически) преобразование
> бесконечного множества файлов к бесконечному множеству 32-
> символьных строк? Таких строк, по определению, существует
> вполне себе конечное множество.

Вот и я не понимаю :) Поэтому все добиваюсь от умных людей описания принципа и откуда вообще взялась уверенность что есть 100% гарантия уникальности хеша?

← →
Джо © (2007-01-02 16:33) [24]

> [23] Real © (02.01.07 16:30)
> и откуда вообще взялась уверенность что
> есть 100% гарантия уникальности хеша?

Нет этой гарантии и быть не может :)

← →
Zeqfreed © (2007-01-02 16:39) [25]

> Вот и я не понимаю :) Поэтому все добиваюсь от умных людей
> описания принципа и откуда вообще взялась уверенность что
> есть 100% гарантия уникальности хеша?

Так говорилось по-моему о 100% уверенности в том, что сколько хешей ни бери из одних и тех же данных, получишь один и тот же хеш. В [3] кто-то в этом усомнился ;)

← →
Anatoly Podgoretsky © (2007-01-02 17:15) [26]

Real © (02.01.07 16:30) [23]
А ты не передергивай, ты сначала хотел получить разные хеши от одинаковых данных.
Для разных данных тебе привели пример с 33 символами, 100% гарантия, что будет как минимум 256 одинаковых хешей.

← →
Vendict © (2007-01-02 17:32) [27]

ты не перепутал ? вроде была инфа, что умудрились RSA сломать, используя резидентную программу при шифровании на процессоре p4 с технологией HT

← →
DillerXX © (2007-01-02 17:50) [28]

Про RSA имхо утка...

← →
cmp (2007-01-02 20:39) [29]

Ещё у меня родился вопрос про md5: почему на русские символы по разному в разных вариантах генерирует хэши?
Например, возьмём "абвгд", и проверим по онлайн хэш генераторам.

http://gdataonline.com/makehash.php -- 9cdb481887ae90c61ad975dc8e2eaeff
http://www.pajhome.org.uk/crypt/md5/ -- 4100c4d44da9177247e44a5fc1546778
http://md5-online.de/ -- 21da85900e9a69bebf0ec05a237ee605

Проверьте, сами, и чему в таком случае верить? Как это объяснить?

← →
wicked © (2007-01-02 20:45) [30]

> Проверьте, сами, и чему в таком случае верить? Как это объяснить?

обьяснить различной кодировкой кирилицы, что влечет за собой различные входные "бинарные" данные... как минимум, есть 4 варианта:
- win1251
- KOI-8
- UTF8
- iso (блиннепомнюномера)
в каждой из кодировок одна и та же строчка будет по разному представлена, отсюда - разные значения хеша

← →
Zeqfreed © (2007-01-02 20:51) [31]

> почему на русские символы по разному в разных вариантах
> генерирует хэши?

Ну не любят русских авторы алгоритма md5 :(

← →
wicked © (2007-01-02 22:05) [32]

а вот и подтверждение всему вышесказанному :)
http://bash.org.ru/quote.php?num=30472

← →
Vendict © (2007-01-02 23:01) [33]

DillerXX © (02.01.07 17:50) [28]
Про RSA имхо утка...

врятли утка. глюк какой-то есть в этом НТ. при заполнении какого-то кэша, насколько я помню из статьи в компьютерре, этот резидент может перехватит секретный ключ, которым оперирует процессор при шифровании. но для этого нужно, чтобы этот резидент был запущен при шифровании.

← →
БЭГ (2007-01-03 08:12) [34]

> Anatoly Podgoretsky © (02.01.07 15:07) [8]

md5 использует алгоритм необратимого шифрования...
Таких алгоритмов куча...
Все очень просто... Понять как шифруется можно... А вот осмыслить как расшифровать не получается... :o) ...

Алгоритм на котором построен md5, держится в особом секрете...

← →
Джо © (2007-01-03 08:22) [35]

> [34] БЭГ (03.01.07 08:12)
> Алгоритм на котором построен md5, держится в особом секрете...

Что за глупость такая?

← →
Lamer@fools.ua © (2007-01-03 09:14) [36]

cmp (02.01.07 20:39) [29]
Например, возьмём "абвгд", и проверим по онлайн хэш генераторам.
а у меня вообще вышло 1A21452A078F2A09D40B1D69C58BEB8C

БЭГ (03.01.07 8:12) [34]
Алгоритм на котором построен md5, держится в особом секрете...

кусрчек кода из md5

function LRot32(a, b: longword): longword; begin Result:= (a shl b) or (a shr (32-b)); end; procedure TDCP_md5.Compress; var Data: array[0..15] of dword; A, B, C, D: dword; begin Move(HashBuffer,Data,Sizeof(Data)); A:= CurrentHash[0]; B:= CurrentHash[1]; C:= CurrentHash[2]; D:= CurrentHash[3]; A:= B + LRot32(A + (D xor (B and (C xor D))) + Data[ 0] + $d76aa478,7); D:= A + LRot32(D + (C xor (A and (B xor C))) + Data[ 1] + $e8c7b756,12); C:= D + LRot32(C + (B xor (D and (A xor B))) + Data[ 2] + $242070db,17); B:= C + LRot32(B + (A xor (C and (D xor A))) + Data[ 3] + $c1bdceee,22); A:= B + LRot32(A + (D xor (B and (C xor D))) + Data[ 4] + $f57c0faf,7); D:= A + LRot32(D + (C xor (A and (B xor C))) + Data[ 5] + $4787c62a,12); C:= D + LRot32(C + (B xor (D and (A xor B))) + Data[ 6] + $a8304613,17); B:= C + LRot32(B + (A xor (C and (D xor A))) + Data[ 7] + $fd469501,22); A:= B + LRot32(A + (D xor (B and (C xor D))) + Data[ 8] + $698098d8,7); D:= A + LRot32(D + (C xor (A and (B xor C))) + Data[ 9] + $8b44f7af,12); C:= D + LRot32(C + (B xor (D and (A xor B))) + Data[10] + $ffff5bb1,17); B:= C + LRot32(B + (A xor (C and (D xor A))) + Data[11] + $895cd7be,22); A:= B + LRot32(A + (D xor (B and (C xor D))) + Data[12] + $6b901122,7); D:= A + LRot32(D + (C xor (A and (B xor C))) + Data[13] + $fd987193,12); C:= D + LRot32(C + (B xor (D and (A xor B))) + Data[14] + $a679438e,17); B:= C + LRot32(B + (A xor (C and (D xor A))) + Data[15] + $49b40821,22); A:= B + LRot32(A + (C xor (D and (B xor C))) + Data[ 1] + $f61e2562,5); D:= A + LRot32(D + (B xor (C and (A xor B))) + Data[ 6] + $c040b340,9); C:= D + LRot32(C + (A xor (B and (D xor A))) + Data[11] + $265e5a51,14); B:= C + LRot32(B + (D xor (A and (C xor D))) + Data[ 0] + $e9b6c7aa,20); A:= B + LRot32(A + (C xor (D and (B xor C))) + Data[ 5] + $d62f105d,5); D:= A + LRot32(D + (B xor (C and (A xor B))) + Data[10] + $02441453,9); C:= D + LRot32(C + (A xor (B and (D xor A))) + Data[15] + $d8a1e681,14); B:= C + LRot32(B + (D xor (A and (C xor D))) + Data[ 4] + $e7d3fbc8,20); A:= B + LRot32(A + (C xor (D and (B xor C))) + Data[ 9] + $21e1cde6,5); D:= A + LRot32(D + (B xor (C and (A xor B))) + Data[14] + $c33707d6,9); C:= D + LRot32(C + (A xor (B and (D xor A))) + Data[ 3] + $f4d50d87,14); B:= C + LRot32(B + (D xor (A and (C xor D))) + Data[ 8] + $455a14ed,20); A:= B + LRot32(A + (C xor (D and (B xor C))) + Data[13] + $a9e3e905,5); D:= A + LRot32(D + (B xor (C and (A xor B))) + Data[ 2] + $fcefa3f8,9); C:= D + LRot32(C + (A xor (B and (D xor A))) + Data[ 7] + $676f02d9,14); B:= C + LRot32(B + (D xor (A and (C xor D))) + Data[12] + $8d2a4c8a,20); A:= B + LRot32(A + (B xor C xor D) + Data[ 5] + $fffa3942,4); D:= A + LRot32(D + (A xor B xor C) + Data[ 8] + $8771f681,11); C:= D + LRot32(C + (D xor A xor B) + Data[11] + $6d9d6122,16); B:= C + LRot32(B + (C xor D xor A) + Data[14] + $fde5380c,23); A:= B + LRot32(A + (B xor C xor D) + Data[ 1] + $a4beea44,4); D:= A + LRot32(D + (A xor B xor C) + Data[ 4] + $4bdecfa9,11); C:= D + LRot32(C + (D xor A xor B) + Data[ 7] + $f6bb4b60,16); B:= C + LRot32(B + (C xor D xor A) + Data[10] + $bebfbc70,23); A:= B + LRot32(A + (B xor C xor D) + Data[13] + $289b7ec6,4); D:= A + LRot32(D + (A xor B xor C) + Data[ 0] + $eaa127fa,11); C:= D + LRot32(C + (D xor A xor B) + Data[ 3] + $d4ef3085,16); B:= C + LRot32(B + (C xor D xor A) + Data[ 6] + $04881d05,23); A:= B + LRot32(A + (B xor C xor D) + Data[ 9] + $d9d4d039,4); D:= A + LRot32(D + (A xor B xor C) + Data[12] + $e6db99e5,11); C:= D + LRot32(C + (D xor A xor B) + Data[15] + $1fa27cf8,16); B:= C + LRot32(B + (C xor D xor A) + Data[ 2] + $c4ac5665,23); A:= B + LRot32(A + (C xor (B or (not D))) + Data[ 0] + $f4292244,6); D:= A + LRot32(D + (B xor (A or (not C))) + Data[ 7] + $432aff97,10); C:= D + LRot32(C + (A xor (D or (not B))) + Data[14] + $ab9423a7,15); B:= C + LRot32(B + (D xor (C or (not A))) + Data[ 5] + $fc93a039,21); A:= B + LRot32(A + (C xor (B or (not D))) + Data[12] + $655b59c3,6); D:= A + LRot32(D + (B xor (A or (not C))) + Data[ 3] + $8f0ccc92,10); C:= D + LRot32(C + (A xor (D or (not B))) + Data[10] + $ffeff47d,15); B:= C + LRot32(B + (D xor (C or (not A))) + Data[ 1] + $85845dd1,21); A:= B + LRot32(A + (C xor (B or (not D))) + Data[ 8] + $6fa87e4f,6); D:= A + LRot32(D + (B xor (A or (not C))) + Data[15] + $fe2ce6e0,10); C:= D + LRot32(C + (A xor (D or (not B))) + Data[ 6] + $a3014314,15); B:= C + LRot32(B + (D xor (C or (not A))) + Data[13] + $4e0811a1,21); A:= B + LRot32(A + (C xor (B or (not D))) + Data[ 4] + $f7537e82,6); D:= A + LRot32(D + (B xor (A or (not C))) + Data[11] + $bd3af235,10); C:= D + LRot32(C + (A xor (D or (not B))) + Data[ 2] + $2ad7d2bb,15); B:= C + LRot32(B + (D xor (C or (not A))) + Data[ 9] + $eb86d391,21); Inc(CurrentHash[0],A); Inc(CurrentHash[1],B); Inc(CurrentHash[2],C); Inc(CurrentHash[3],D); Index:= 0; FillChar(HashBuffer,Sizeof(HashBuffer),0); end; class function TDCP_md5.GetHashSize: integer; begin Result:= 128; end; procedure TDCP_md5.Init; begin Burn; CurrentHash[0]:= $67452301; CurrentHash[1]:= $efcdab89; CurrentHash[2]:= $98badcfe; CurrentHash[3]:= $10325476; fInitialized:= true; end; procedure TDCP_md5.Update(const Buffer; Size: longword); var PBuf: ^byte; begin if not fInitialized then raise EDCP_hash.Create("Hash not initialized"); Inc(LenHi,Size shr 29); Inc(LenLo,Size*8); if LenLo< (Size*8) then Inc(LenHi); PBuf:= @Buffer; while Size> 0 do begin if (Sizeof(HashBuffer)-Index)<= DWord(Size) then begin Move(PBuf^,HashBuffer[Index],Sizeof(HashBuffer)-Index); Dec(Size,Sizeof(HashBuffer)-Index); Inc(PBuf,Sizeof(HashBuffer)-Index); Compress; end else begin

Move(PBuf^,HashBuffer[Index],Size); Inc(Index,Size); Size:= 0; end; end; end;

> откуда вообще взялась уверенность что есть 100% гарантия
> уникальности хеша?

Спросите у тех, у кого такая уверенность есть.
У людей в здравом уме такая уверенность отсутствует.

> Алгоритм на котором построен md5, держится в особом секрете.
> ..

В таком страшном секрете, что аж отдельный RFC описывает этот алкогоритм.

http://www.2lib.ru/rfc/1321.html
особый секрет раскрыт

> http://www.pajhome.org.uk/crypt/md5/ -- 4100c4d44da9177247e44a5fc1546778

ИМХО это не "абвгд", а 01234 ;)

> БЭГ (03.01.2007 08:12:34) [34]

> Алгоритм на котором построен md5, держится в особом секрете...

Алгоритмы, которые держутся на секретности ничего не стоят, их даже не рассматривают в индустрии безопасности.

Меркурий в опасности, блин... :)
Бессонница сегодня мучила (не ешьте много оливье на ночь!), смотрел этот знатный фильм, и видел, что делают с теми, кто пытается докопаться до алгоритма... :)

cmp (02.01.07 15:29) [12]
http://www.mscs.dal.ca/~selinger/md5collision/
проверил ... и правда так ... стало страшно ....

> [21] Джо © (02.01.07 16:19)

Это даже не 32-символьная строка, а 128-битное число, что гораздо меньше.

> Вот и я не понимаю :) Поэтому все добиваюсь от умных людей
> описания принципа и откуда вообще взялась уверенность что
> есть 100% гарантия уникальности хеша?

Такой гарантии не было и нет. Наоборот, есть 100% гарантия,что коллизии будут. Так что устойчивость хеша определяется тем, насколько сложно подобрать коллизию. А вероятность того, что у случайных данных будет одинаковый хеш - 1/2^128

> [26] Anatoly Podgoretsky © (02.01.07 17:15)

Вообще-то, 256 хешей будет при наборе данных в 136 бит, это поменьше, чем 33 символа.

> [32] wicked © (02.01.07 22:05)

Точно :D

> Vga (04.01.2007 19:31:49) [49]

Даже спорить не охота, поскольку не оговорены начальные условия, мы говорим об разных вещах, если битовое то начиная с 17 символа коллизия гарантирована.

md5 коллизии Найти похожие ветки