MD5

MD5 (Message Digest 5) — 128-бітний алгоритм гешування, розроблений професором Рональдом Л. Рівестом в 1991 році. Призначений для створення «відбитків» або «дайджестів» повідомлень довільної довжини. Прийшов на зміну MD4, що був недосконалим. Описаний в RFC 1321. З 2011 року відповідно RFC 6151 алгоритм вважається ненадійним.

У 2004 році китайські дослідники Сяоюнь Ван (Xiaoyun Wang), Денгуо Фен (Dengguo Feng), Сюецзя Лай (Xuejia Lai) і Хонбо Ю (Hongbo Yu) повідомили про знаходження ними вразливості в алгоритмі, що дозволяє за невеликий час (1 годину на кластері IBM p690) знаходити колізії геш-функцій[1][2].

У 2006 році чеський дослідник Властимил Клима опублікував алгоритм, що дозволяє знаходити колізії з довільним початковим вектором (A,B,C,D) на звичайному комп'ютері за лічені хвилини, цей метод було названо «тунелюванням»[3].

2009 року підрозділ Національного управління кібербезпеки США US-CERT рекомендував відмовитися від застосування цього алгоритму через виявлені вразливості[4] Відповідний RFC 6151 було опубліковано в березні 2011 року.

Одною базовою вимогою для будь-якої криптографічної геш-функції є те, що має бути неможливо знайти два конкретні повідомлення, які гешують одне значення. MD5 не задовільняє цієї вимоги. Такі колізії можуть виявлятися за секунди на звичайному настільному комп'ютері.

На 2020 рік, MD5 все ще широко використовується, незважаючи на свої вразливості.

Використання MD5
Android ROMs використовують такий тип контрольної суми

Вибірки повідомлень MD5 широко використовувались у світі програмного забезпечення для гарантування правильної передачі файла. Наприклад, файлові сервери часто надають попередньо підраховану контрольну суму MD5 (відому як md5sum) для файлів, так що користувач може порівняти контрольну суму завантаженого файла з нею. Більшість юніксових операційних систем включають утиліти MD5 до своїх дистрибутивів. Користувачі Windows можуть використовувати інтегровану функцію PowerShell "Get-FileHash", інсталювати утиліту Microsoft або використовувати сторонні програми.

Оскільки дуже легко генерувати колізії у MD5, особа, яка створила файл, може створити другий файл із такою ж контрольною сумою, тому цей прийом не може захистити від деяких форм зловмисного втручання. У деяких випадках контрольній сумі не можна довіряти (наприклад, якщо вона була отримана за тим самим каналом, що і завантажений файл), у цьому випадку MD5 може забезпечити лише функціональність перевірки помилок: він розпізнає пошкоджене або неповне завантаження, що часто трапляється при завантаженні великих файлів.

Історично MD5 використовувався для зберігання одностороннього хешу пароля, часто з розтягуванням ключів. NIST не включає MD5 у свій список рекомендованих хешів для зберігання паролів.

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

Алгоритм MD5
Блок схема роботи алгоритму MD5

Початковий етап підготовки
  • Вхідні дані вирівнюються так, щоб їхній розмір можна було порівняти з 448 по модулю з 512. Спочатку дописують одиничний біт (навіть якщо довжина порівняна з 448), далі необхідна кількість нульових бітів .
  • Дописування 64-бітного представлення довжини даних по вирівнюванню. Якщо довжина перевищує , то дописують молодші біти.

Допоміжні таблиці та функції
  • Ініціалізуть 4 змінних розміром по 32 біта:
    • А = 01 23 45 67;
    • В = 89 AB CD EF;
    • С = FE DC BA 98;
    • D = 76 54 32 10.

Вирівнювані дані розбиваються на блоки по 32 біта, і кожен проходить 4 раунди з 16 операторів. Всі оператори однотипні і мають вигляд: [abcd k s i], визначений як , де X - блок даних, а T[1..64] - 64-елементна таблиця, побудована наступним чином: , s - циклічний зсув вліво на s біт отриманого 32-бітного аргументу.

  • В першому раунді Fun F(X, Y, Z) = XY v (not X)Z
  • В другому раунді Fun G(X, Y, Z) = XZ v (not Z)Y.
  • В третьому раунді Fun Н(Х, Y, Z) = Х xor Y xor Z.
  • В четвертому раунді Fun I(Х, Y, Z) = Y xor (X v (not Z)).

Циклічна процедура обчислення

Саме обчислення проходить наступним чином:

  • Зберігаються значення A, B, C і D, що залишились після операцій з попередніми блоками(або їх початкові значення якщо блок перший)

AA = A

BB = B

CC = C

DD = D

Раунд 1

/*[abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  0 7  1][DABC  1 12  2][CDAB  2 17  3][BCDA  3 22  4]
[ABCD  4 7  5][DABC  5 12  6][CDAB  6 17  7][BCDA  7 22  8]
[ABCD  8 7  9][DABC  9 12 10][CDAB 10 17 11][BCDA 11 22 12]
[ABCD 12 7 13][DABC 13 12 14][CDAB 14 17 15][BCDA 15 22 16]

Раунд 2

/*[abcd k s i] a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  1 5 17][DABC  6 9 18][CDAB 11 14 19][BCDA  0 20 20]
[ABCD  5 5 21][DABC 10 9 22][CDAB 15 14 23][BCDA  4 20 24]
[ABCD  9 5 25][DABC 14 9 26][CDAB  3 14 27][BCDA  8 20 28]
[ABCD 13 5 29][DABC  2 9 30][CDAB  7 14 31][BCDA 12 20 32]

Раунд 3

/*[abcd k s i] a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  5 4 33][DABC  8 11 34][CDAB 11 16 35][BCDA 14 23 36]
[ABCD  1 4 37][DABC  4 11 38][CDAB  7 16 39][BCDA 10 23 40]
[ABCD 13 4 41][DABC  0 11 42][CDAB  3 16 43][BCDA  6 23 44]
[ABCD  9 4 45][DABC 12 11 46][CDAB 15 16 47][BCDA  2 23 48]

Раунд 4

/*[abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
[ABCD  0 6 49][DABC  7 10 50][CDAB 14 15 51][BCDA  5 21 52]
[ABCD 12 6 53][DABC  3 10 54][CDAB 10 15 55][BCDA  1 21 56]
[ABCD  8 6 57][DABC 15 10 58][CDAB  6 15 59][BCDA 13 21 60]
[ABCD  4 6 61][DABC 11 10 62][CDAB  2 15 63][BCDA  9 21 64]

Проміжний результат

Виконати наступні операції

A = AA + A
B = BB + B
C = CC + C
D = DD + D

Після цього перевірити, чи є ще блоки, якщо є, то повторюють циклічну процедуру обчислення для наступного 32-х бітового блоку.

Результат

Після обчислення для всіх блоків даних, отримуємо кінцевий хеш у регістрах A B C D. Якщо вивести слова у зворотному порядку DCBA, то отримаємо MD5 хеш.

MD5-хеші

Хеш містить 128 біт (16 байт) і зазвичай представляється як послідовність з 32 шістнадцяткових цифр.

Кілька прикладів хешу: 

 MD5 ("md5") = 1bc29b36f623ba82aaf6724fd3b16718

Навіть невелика зміна вхідного повідомлення (у нашому випадку на один біт: ASCII символ «5» з кодом 0x35 16 = 00011010 '1 ' 2 замінюється на символ «4» з кодом 0x34 16 = 00011010 '0 ' 2 ) призводить до повної зміни хешу. Така властивість алгоритму називається лавинним ефектом. 

 MD5 ("md4") = c93d3bf7a7c4afe94b64e30c2ce39f4f

Приклад MD5-хешу для «нульового» рядка: 

 MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

Імплементації і використання

Наступні криптографічні бібліотеки підтримують MD5:

Джерела
  1. Xiaoyun Wang and Dengguo Feng and Xuejia Lai and Hongbo Yu (received 16 Aug 2004, last revised 17 Aug 2004). Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. Cryptology ePrint Archive: Report 2004/199. Процитовано 12 листопада 2018.
  2. Philip Hawkes and Michael Paddon and Gregory G. Rose (13 жовтня 2004). Musings on the Wang et al. MD5 Collision. Cryptology ePrint Archive: Report 2004/264. Процитовано 12 листопада 2018.
  3. Vlastimil Klima (received 18 Mar 2006, last revised 17 Apr 2006). Tunnels in Hash Functions: MD5 Collisions Within a Minute. Cryptology ePrint Archive: Report 2006/105. Процитовано 12 листопада 2018.
  4. CERT Vulnerability Notes Database. Software Engineering Institute. Original Release Date: 2008-12-31; Last Revised: 2009-01-21. Процитовано 12 листопада 2018.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.