Тема: md5

**nons** · 11.06.2005 20:17

Нужна была инфа по алгоритму шифрования md5, вот что нашел (может кому еще нужно и полезно будет

;)):

Краткое описание алгоритма MD5
Вначале допускаем,что имеем на входе сообщение из b-бит,и что мы желаем найти Message Digest этой последовательности бит.Число b является произвольным неотрицательным целым;b может быть равным нулю,оно не обязательно должно быть множителем 8,и оно может быть произвольно большим.Представим последовательность бит сообщения как:

m_0 m_1 m_2 . . . . . . m{b-1}

Следующие пять этапов выполняются для подсчета Message Digest сообщения.

Этап 1.Присоединение заполняющих (дополнительных) битов.

Сообщение расширяется так,чтобы его длина (в битах) совпадала с 448,по модулю 512. Дополнение всегда выполняется, даже если длина сообщения - уже совпадает с 448 по модулю 512. Дополнение выполняется следующим образом: одиночный "1" бит добавляется к сообщению, и далее "0" биты добавляются так что длина в битах заполняемого сообщения соответствует 448 по модулю 512.В общем случае,минимум один бит и максимум 512 бит добавляется.

Этап 2. Добавление длины

64-битное представление входной последовательности b (длина сообщения перед расширением дополнительными битами) присоединяется к результату предыдущего этапа.Маловероятно,что длина b будет больше,чем 2^64 поэтому и используется 64-х разрядная величина для хранения длины b.(Эти биты добавляются как два 32-х разрядных слова,младшее заносится первым).
В этом месте окончательное сообщение(после выполнения первого и второго этапов) имеет длину, кратную 512 битам,т.е сообщение имеет длину,которая точно кратна 16-ти словам. Последовательность М[0 . . . . N-1] является словами окончательного сообщения,где N кратно 16.

Этап 3. Инициализация MD буфера.

Буфер на 4-е слова (A,B,C,D) используется для подсчета Message Digest.Каждое из A,B,C,D является 32-х битным регистром.Эти регистры инициализируются следующими шестнадцатиричными значениями,где первым следует самый младший байт:

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

Программисты из RSA Data Security,Inc., дабы не утруждать себя и остальных людей по поводу происхождения этих чисел,просто назвали их магическими константами.

Этап 4.Обработка сообщения в блоках по 16 слов.

Сначала определяются четыре вспомагательных функции каждая из которых имеет на входе три 32-битных слова и производит одно 32-битное слово на выходе.

F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))

В каждой битовой позиции функция F действует как условный опреатор : если X то Y иначе Z. Функция F могла бы определяться с использованием операцию + вместо v,так как выражение XY and not(X)Z никогда не будет иметь 1 в одинаковых битовых позициях. Если биты X,Y и Z независимы и несмещены(??),то каждый бит после выполнения F(X,Y,Z) будет независим и несмещен.
Функции G,H и I подобны функции F,они действуют в "побитовом соответствии" для нахождения выходного значения от входных битов X,Y и Z,тем же способом,что если биты X,Y и Z независимы и несмещены,то каждый бит после выполнения вышеуказанных функций будет независим и несмещен.Обратите внимание,что функция H(X,Y,Z) является поразрядной операцией исключающего ИЛИ (т.е. функцией контроля четности входных значений).Далее на этом этапе происходит четыре цикла,в которых происходит трансформация битов сообщения при помощи вышеуказанных функций,функций циклического сдвига,и таблицы константных значений.

Этап 5.Вывод

В результате выполнения предыдущих этапов Message Digest производит на выходе числа A,B,C,D,общая длина которых 128 бит.

Вот пример программы на Pascal'e:

Код:

Алгоритм MD5, Нахождение 128 битного хэша
http://forum.vingrad.ru
Function md5(s:string):string;
var a:array[0..15] of byte;
i:integer;

LenHi, LenLo: longword;
Index: DWord;
HashBuffer: array[0..63] of byte;
CurrentHash: array[0..3] of DWord;

procedure Burn;
begin
LenHi:= 0; LenLo:= 0;
Index:= 0;
FillChar(HashBuffer,Sizeof(HashBuffer),0);
FillChar(CurrentHash,Sizeof(CurrentHash),0);
end;

procedure Init;
begin
Burn;
CurrentHash[0]:= $67452301;
CurrentHash[1]:= $efcdab89;
CurrentHash[2]:= $98badcfe;
CurrentHash[3]:= $10325476;
end;

function LRot32(a, b: longword): longword;
begin
Result:= (a shl b) or (a shr (32-b));
end;

procedure 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;


procedure Update(const Buffer; Size: longword);
var
PBuf: ^byte;
begin
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;

procedure Final(var Digest);
begin
HashBuffer[Index]:= $80;
if Index>= 56 then Compress;
PDWord(@HashBuffer[56])^:= LenLo;
PDWord(@HashBuffer[60])^:= LenHi;
Compress;
Move(CurrentHash,Digest,Sizeof(CurrentHash));
Burn;
end;


begin
Init;
Update(s[1],Length(s));
Final(a);
result:='';
for i:=0 to 15 do
result:=result+IntToHex(a[i],0);
Burn;
end;

**Mozart** · 12.06.2005 00:09

Полезно было бы еслиб расшифровку кто-нить написал бы...а так....

**nons** · 12.06.2005 02:36

Сообщение от Mozart

Полезно было бы еслиб расшифровку кто-нить написал бы...а так....

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

**Mozart** · 12.06.2005 19:36

Сообщение от n0ns3ns3

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

Обсуждалось не раз...Если первичная запись будет состоять более чем из 5 символов, время на переборку довольно огромное получится...

**nons** · 12.06.2005 19:52

Сообщение от Mozart

Обсуждалось не раз...Если первичная запись будет состоять более чем из 5 символов, время на переборку довольно огромное получится...

хех, ..иначе этот метод шифорования не получил бы такого распростанения ;)

**nons** · 13.06.2005 04:27

вот, нашел на сайте античата (но к кодингу это уже мало относится, больше к Underground'у ;))

Ранее мы сообщали о работах и исследованиях, в которых их авторы демонстрировали возможность взлома алгоритма формирования хэшей MD5, а также SHA-0/1. Особенно здесь прославились китайские криптоаналитики (исследователи компьютерной безопасности) - например, широко известны статьи о возможности взлома MD4, MD5, SHA X. Wang. Суть исследований сводилась к доказательству того, что совершенно разные блоки данных (текстовые документы, например) могут иметь одинаковые хэши - то, что на языке криптоаналитиков называется хэш-коллизией. До сих пор не удавалось, тем не менее, получить более-менее осмысленный документ, который бы мог подменить истинный (хотя ранее Kaminski и Mikle демонстрирровали исполняемые файлами с одинаковыми хэшами, а Lenstra, Wang и de Weger продемонстрировали 2 сертификата X.509). Однако недавно появилась доольно интересная совместная работа исследователей из немецкого института криптологии и IT-безопасности CITS и университета в Маннхейме под названием "Attacking Hash Functions by Poisoned Messages "The Story of Alice and her Boss". В ней авторы приводят вполне осмысленные документы формата PS (Postscript), которые имеют одинаковые хэш-функции. Таким образом, теперь полностью подтверждена практическая возможность взлома MD5.

От меня: незнаю, как можно это использовать при взломе конкретного хеша, но воможно скоро нам откроют алгоримт и больше не придется мучатся с хешами...

Источник: http://www.cits.rub.de/MD5Collisions/

**JiF** · 13.06.2005 19:23

Сообщение от n0ns3ns3

хех, ..иначе этот метод шифорования не получил бы такого распростанения ;)

Это и не шифрование, а хеширование

путать незя

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

badc0de · 17.10.2005 17:32

Кстати, если еще актуально.. хэши md5 (оригинальный алгоритм из rfc), вскрывается за очень короткое время. Идея основана на генерации таблиц хэшей заранее. (правда объем этих табличек слегка великоват будет

Дополнительная информация:
http://www.antsight.com/zsl/rainbowcrack/

**nons** · 15.11.2005 21:13

сюда же, ;)
сорцы генератора коллизий хешей MD4 и MD5

Тема: md5

Опции темы

Отображение

md5

Информация о теме

Пользователи, просматривающие эту тему

Ваши права