MD4

MD4 (Message Digest 4) — хеш-функція, розроблена професором Массачусетського університету Рональдом Рівестом в 1990 році, і вперше описана в RFC 1186. Для довільного вхідного повідомлення функція генерує 128-розрядне хеш-значення, зване дайджестом повідомлення. Цей алгоритм використовується в протоколі аутентифікації MS-CHAP, розробленому корпорацією Майкрософт для виконання процедур перевірки автентичності віддалених робочих станцій Windows. Є попередником MD5.

Алгоритм MD4

Передбачається, що на вхід подано повідомлення, що складається з b біт, хеш якого нам належить обчислити. Тут b  — довільне невід'ємне ціле число; воно може бути нулем, не зобов'язано бути кратним восьми, і може бути як завгодно великим. Запишемо повідомлення побітово, у вигляді:

$m_{0}m_{1}\ldots m_{b-1}$

Нижче наведено 5 кроків, які використовуються для обчислення хешу повідомлення.

Крок 1. Додавання відсутніх бітів.

Повідомлення розширюється так, щоб його довжина в бітах за модулем 512 дорівнювала 448. Таким чином, в результаті розширення, повідомленням бракує 64 біта до довжини, кратної 512 бітам. Розширення виробляється завжди, навіть якщо повідомлення спочатку має потрібну довжину.

Розширення проводиться таким чином: один біт, що дорівнює 1, додається до повідомлення, а потім додаються біти, рівні 0, до тих пір, поки довжина повідомлення не стане рівною 448 по модулю 512. У підсумку, до повідомлення додається як мінімум 1 біт, і як максимум 512.

Крок 2. Додавання довжини повідомлення.

64-бітове представлення ~ b ~ (довжини повідомлення перед додаванням набивальних бітів) додається до результату попереднього кроку. У малоймовірному випадку, коли b більше, ніж 2⁶⁴, використовуються тільки 64 молодших біта. Ці біти додаються у вигляді двох 32-бітних слів, і першим додається слово, що містить молодші розряди.

На цьому етапі (після додавання бітів і довжини повідомлення) ми отримуємо повідомлення довжиною кратною 512 бітам. Це еквівалентно тому, що це повідомлення має довжину, кратну 16-ти 32-бітним словами.

Крок 3. Ініціалізація MD-буфера.

Для обчислення хешу повідомлення використовується буфер, що складається з 4 слів (32-бітних регістрів): (H1, H2, H3, H4). Ці регістри ініціалізуються наступними шістнадцятирозрядними числами:

       word $H1$: 67 45 23 01
       word $H2$: EF CD АВ 89
       word $H3$: 98 BA DC FE
       word $H4$: 10 32 54 76

Крок 4. Обробка повідомлення блоками по 16 слів.

Перш за все, оголосимо три порозрядні функції F, G, H, які приймають на вхід три 32-бітні числа:

$F(X,Y,Z)=XY\lor \neg XZ$
$G(X,Y,Z)=XY\lor XZ\lor YZ$
$H(X,Y,Z)=X\oplus Y\oplus Z$

Також оголосимо константи:

y[0..15]=0
y[16..31]='5A827999'
y[32.. 47]='6ED9EBA1'

z[0..15]=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
z[16..31]=[0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15]
z[32..47]= [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]

s[0..15]=[3,7,11,19,3,7,11,19,3,7,11,19,3,7,11,19]
s[16..31]=[3,5,9,13,3,5,9,13,3,5,9,13,3,5,9,13]
s[32..47]=[3,9,11,15,3,9,11,15,3,9,11,15,3,9,11, 15]

Потік вхідних даних складається із 16 одночасно загружених слів в масив X. Далі виконуються наступні дії для кожних 16 слів:

(А,В,C,D) = (Н1,Н2,Н3,Н4)
Виконати перший раунд.
Виконати другий раунд.
Виконати третій раунд.
(Н1,Н2,Н3,Н4) = (Н1+А, Н2+В,Н3+С,H4+D)

Самі раунди це наступний ітеративний процес:

//Раунд 1
for(int i=0;i<16;i++){
    t = A + f(B,C,D)+x[z[j]] + y[j].
    (A,B,C,D) = (D,t <<< s[j],B,C)
}

//Раунд 2
for(int i=16;i<32;i++){
    t = A + g(B,C,D)+x[z[j]] + y[j].
    (A,B,C,D) = (D,t <<< s[j],B,C)
}

//Раунд 3
for(int i=32;i<48;i++){
    t = A + h(B,C,D)+x[z[j]] + y[j].
    (A,B,C,D) = (D,t <<< s[j],B,C)
}

Де <<< - циклічний зсув вліво.

Крок 5. Формування хешу.

Результатом (хеш-функцією) буде конкатенація H1, H2, H3, H4.

Безпека

Рівень безпеки, закладений у MD4, був розрахований на створення досить стійких гібридних систем електронного цифрового підпису, заснованих на MD4 і криптосистемі з відкритим ключем. Рональд Рівест вважав, що алгоритм хешування MD4 можна використовувати і для систем, які потребують сильної криптостійкості. Але в той же час він відзначав, що MD4 створювався передусім як дуже швидкий алгоритм хешування, тому він може бути поганий в плані криптостійкості. Як показали подальші дослідження, він був правий, і для додатків, де важлива насамперед криптостійкість, став використовуватися алгоритм MD5.

Уразливості

Уразливості в MD4 були продемонстровані у статті Берта ден Бура та Антона Босселарса в 1991 році. Перша колізія була знайдена Гансом Доббертіном в 1996 році.

Див. також

• Хеш-функція

Література

• Kaufman, Charlie; Perlman, Radia; Speciner, Mike (2002). Network security: private communication in a public world (вид. 2.). Upper Saddle River, NJ London: Prentice Hall PTR. ISBN 0130460192.

Посилання

• RFC 1186