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 більше, ніж 264, використовуються тільки 64 молодших біта. Ці біти додаються у вигляді двох 32-бітних слів, і першим додається слово, що містить молодші розряди.

На цьому етапі (після додавання бітів і довжини повідомлення) ми отримуємо повідомлення довжиною кратною 512 бітам. Це еквівалентно тому, що це повідомлення має довжину, кратну 16-ти 32-бітним словами. Кожне 32-бітове слово містить чотири 8-бітних, але слідують вони не підряд, а навпаки (наприклад, з восьми 8-бітних слів (abcdefgh) ми отримуємо два 32-бітних слова (dcba hgfe)). Нехай M [0 \ldots N-1] означає масив слів отриманого повідомлення (тут N кратно 16).

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

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

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

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

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

Результат (хеш-функція) виходить як ABCD. Тобто, ми виписуємо 128 біт, починаючи з молодшого біта A, і закінчуючи старшим бітом D.

Реалізація алгоритму на мові C міститься в RFC 1320.

Безпека[ред.ред. код]

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

Уразливості[ред.ред. код]

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

Див. також[ред.ред. код]