Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

MD4



План:


Введення

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

Одна операція MD4. Хешування з MD4 складається з 48 таких операцій, згрупованих у 3 раунди по 16 операцій. F - нелінійна функція; в кожному раунді функція змінюється. M i означає 32-бітний блок вхідного повідомлення, а K i - 32-бітова константа, різна для кожної операції.

1. Алгоритм MD4

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

m_0 m_1 \ ldots m_ {b-1}

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


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

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

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


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

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

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


1.3. Крок 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 

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

Для початку визначимо три допоміжні функції, кожна з яких отримує на вхід три 32-бітових слова, і по ним обчислює одне 32-бітове слово.

F (X, Y, Z) = XY \ lor \ neg X ZG (X, Y, Z) = XY \ lor XZ \ lor YZH (X, Y, Z) = X \ oplus Y \ oplus Z

На кожну бітову позицію F діє як умовний вираз: якщо X , То Y ; Інакше Z . Функція F могла б бути визначена з використанням ~ + замість \ Lor , Оскільки ~ XY і \ Neg XZ не можуть рівнятися 1 одночасно. G діє на кожну бітову позицію як функція максимального значення: якщо принаймні в двох словах з X, Y, Z відповідні біти дорівнюють 1 , То G видасть 1 в цьому біті, а інакше G видасть біт, що дорівнює 0 . Цікаво відзначити, що якщо біти X , Y і Z статистично незалежні, то біти F (X, Y, Z) і G (X, Y, Z) будуть також статистично незалежні. Функція H реалізує побітовий xor , Вона володіє таким же властивістю, як F і G .

Алгоритм хешування на абстрактному мові програмування:

 / * Обробляємо кожен блок з 16-ти слів * /  for  i  =  0  to N  /  16  -  1  do  / * Заносимо i-ий блок в змінну X * /  for  j  =  0  to  15  do  set X  [  j  ]  to M  [  i  *  16  +  j  ]  .  end  / * Кінець циклу по j * /  / * Зберігаємо A як AA, B як BB, C як CC, і D як DD * /  AA  =  A BB  =  B CC  =  C DD  =  D  / * Раунд 1 * /  / * Нехай [abcd ks] означає наступну операцію: a = (a + F (b, c, d) + X [k]) <<< s. * /  / * Виконуємо 16 таких операцій: * /  [  ABCD  0  3  ]  [  DABC  1  7  ]  [  CDAB  2  11  ]  [  BCDA  3  19  ]  [  ABCD  4  3  ]  [  DABC  5  7  ]  [  CDAB  6  11  ]  [  BCDA  7  19  ]  [  ABCD  8  3  ]  [  DABC  9  7  ]  [  CDAB  10  11  ]  [  BCDA  11  19  ]  [  ABCD  12  3  ]  [  DABC  13  7  ]  [  CDAB  14  11  ]  [  BCDA  15  19  ]  / * Раунд 2 * /  / * Нехай [abcd ks] означає наступну операцію: a = (a + G (b, c, d) + X [k] + 5A827999) <<< s. * /  / * Виконуємо 16 таких операцій: * /  [  ABCD  0  3  ]  [  DABC  4  5  ]  [  CDAB  8  9  ]  [  BCDA  12  13  ]  [  ABCD  1  3  ]  [  DABC  5  5  ]  [  CDAB  9  9  ]  [  BCDA  13  13  ]  [  ABCD  2  3  ]  [  DABC  6  5  ]  [  CDAB  10  9  ]  [  BCDA  14  13  ]  [  ABCD  3  3  ]  [  DABC  7  5  ]  [  CDAB  11  9  ]  [  BCDA  15  13  ]  / * Раунд 3 * /  / * Нехай [abcd ks] означає наступну операцію: a = (a + H (b, c, d) + X [k] + 6ED9EBA1) <<< s. * /  / * Виконуємо 16 таких операцій: * /  [  ABCD  0  3  ]  [  DABC  8  9  ]  [  CDAB  4  11  ]  [  BCDA  12  15  ]  [  ABCD  2  3  ]  [  DABC  10  9  ]  [  CDAB  6  11  ]  [  BCDA  14  15  ]  [  ABCD  1  3  ]  [  DABC  9  9  ]  [  CDAB  5  11  ]  [  BCDA  13  15  ]  [  ABCD  3  3  ]  [  DABC  11  9  ]  [  CDAB  7  11  ]  [  BCDA  15  15  ]  / * Потім виробляємо наступні операції додавання. (Збільшуємо значення в кожному регістрі на величину, яку він мав перед початком ітерації по i * /  A  =  A  +  AA B  =  B  +  BB C  =  C  +  CC D  =  D  +  DD end  / * Кінець циклу по i * / 

Зауваження. Величина 5A827999 - шістнадцяткова 32-бітова константа, перші байти - старші. Вона являє собою квадратний корінь з 2. Вона ж у вісімковому представленні: 013240474631. Величина 6ED9EBA1 - шістнадцяткова 32-бітова константа, перші байти - старші. Вона являє собою квадратний корінь з 3. Вона ж у вісімковому представленні: 015666365641. Ці дані наведені в книзі Кнут, Мистецтво програмування, видання 1981 року, том 2, стор 660, таблиця 2.


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

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

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

2. Приклади хешів

128-бітові MD4 хеши являють собою 32-х значне число в 16-ричном форматі. У наступному прикладі показаний хеш 43-байтной рядки ASCII :

 MD4 ("The quick brown fox jumps over the lazy dog") = 1bee69a46ba811185c194762abaeae90 

Будь навіть сама незначна зміна хешіруемой інформації призводить до отримання повністю відмінного хешу, наприклад, зміна в прикладі однієї букви з d на c:

 MD4 ("The quick brown fox jumps over the lazy c og") = b86e130ce7028da59e672d56ad0113df 

Приклад MD4 хешу для "нульовий" рядки:

 MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0 

3. Порівняння з MD5

  • MD4 використовує три цикли з 16 кроків кожен, у той час як MD5 використовує чотири цикли з 16 кроків кожен.
  • У MD4 додаткова константа в першому циклі не застосовується. Аналогічна додаткова константа використовується для кожного з кроків у другому циклі. Інша додаткова константа використовується для кожного з кроків у третьому циклі. У MD5 різні додаткові константи, Т [i], застосовуються для кожного з 64 кроків.
  • MD5 використовує чотири елементарні логічні функції, по одній на кожному циклі, в порівнянні з трьома в MD4, по одній на кожному циклі.
  • У MD5 на кожному кроці поточний результат складається з результатом попереднього кроку. Наприклад, результатом першого кроку є змінене слово А. Результат другого кроку зберігається в D і утворюється додаванням А до циклічно зсунуто вліво на певне число біт результату елементарної функції. Аналогічно, результат третього кроку зберігається в С і утворюється додаванням D до циклічно зсунуто вліво результату елементарної функції. MD4 це останнє додавання не включає.

4. Безпека

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


5. Уразливості

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


Цей текст може містити помилки.

Схожі роботи | скачати
© Усі права захищені
написати до нас