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^[en] рекомендував відмовитися від застосування цього алгоритму через виявлені вразливості^[4] Відповідний RFC 6151 було опубліковано в березні 2011 року.

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

На 2023 рік, MD5 все ще широко використовується,^{[джерело?]} незважаючи на свої вразливості.

Цей розділ треба вікіфікувати для відповідності стандартам якості Вікіпедії. Будь ласка, допоможіть додаванням доречних внутрішніх посилань або вдосконаленням розмітки статті. (квітень 2021)

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (квітень 2021)

В іншому мовному розділі є повніша стаття MD5#Applications(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (квітень 2021) Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.

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

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

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

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

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

• Ініціалізуть 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], визначений як ${\displaystyle a=b+((a+Fun(b,c,d)+X[k]+T<i>)<<<s)}$, де X - блок даних, а T[1..64] - 64-елементна таблиця, побудована наступним чином: ${\displaystyle T[i]=int(4294967296*|sin(i)|)}$, 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 хеш.

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

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

 MD5 ("md5") = 1bc29b36f623ba82aaf6724fd3b16718 

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

 MD5 ("md4") = c93d3bf7a7c4afe94b64e30c2ce39f4f 

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

 MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

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

• Botan
• Bouncy Castle
• cryptlib^[en]
• Crypto++^[en]
• Libgcrypt
• Nettle^[en]
• OpenSSL
• wolfSSL

• RFC 1321
• Generate MD5 Online (онлайн сервіс для генерування MD5)^{[недоступне посилання з серпня 2019]}(англ.)

Це незавершена стаття з криптографії. Ви можете допомогти проєкту, виправивши або дописавши її.