Знаймо

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

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

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

MD5



План:


Введення

MD5 ( англ. Message Digest 5 ) - 128-бітний алгоритм хешування, розроблений професором Рональдом Л. Рівестом з Массачусетського технологічного інституту (Massachusetts Institute of Technology, MIT) в 1991. Призначений для створення "відбитків" або дайджестів повідомлення довільної довжини й наступної перевірки їх достовірності. Є поліпшеною в плані безпеки версією MD4. [1] Описано в RFC 1321. [2]


1. Історія

MD5 - один із серії алгоритмів з побудови дайджесту повідомлення, розроблений професором Рональдом Л. Рівестом з Массачусетського технологічного інституту. Розроблено в 1991, як більш надійний варіант попереднього алгоритму MD4. [1] Пізніше Гансом Доббертіном були знайдені недоліки алгоритму MD4.

В 1993 Берт ден Бур (Bert den Boer) і Антон Босселарс (Antoon Bosselaers) показали, що в алгоритмі можливі псевдоколлізіі, коли різним ініціалізувалися векторах відповідають однакові дайджести для вхідного повідомлення.

В 1996 Ганс Доббертін (Hans Dobbertin) оголосив про колізії в алгоритмі і вже в той час було запропоновано використовувати інші алгоритми хешування, такі як Whirlpool, SHA-1 або RIPEMD-160.

Через невеликого розміру хешу в 128 біт, можна розглядати birthday атаки. У березні 2004 був запущений проект MD5CRK з метою виявлення вразливостей алгоритму, використовуючи birthday атаки. Проект MD5CRK закінчився 17 серпня 2004, коли Ван Сяоюнь (Wang Xiaoyun), Фен Денг (Feng Dengguo), Лай Сюецзя (Lai Xuejia) і Юй Хунбо (Yu Hongbo) виявили уразливості в алгоритмі.

1 березня 2005 Arjen Lenstra, Xiaoyun Wang і Benne de Weger продемонстрували побудова двох X.509 документів з різними відкритими ключами і однаковим хешем MD5.

18 березня 2006 дослідник Властіміл Клима (Vlastimil Klima) опублікував алгоритм, який може знайти колізії за одну хвилину на звичайному комп'ютері, метод отримав назву "тунелювання".


2. Алгоритм MD5

Схема роботи алгоритму MD5

На вхід алгоритму надходить вхідний потік даних, хеш якого необхідно знайти. Довжина повідомлення може бути будь-який (у тому числі нульовою). Запишемо довжину повідомлення в L. Це число ціле і невід'ємне. Кратність небудь числах необов'язкова. Після надходження даних йде процес підготовки потоку до обчислень.

Нижче наведено 5 кроків алгоритму:


2.1. Крок 1. Вирівнювання потоку

Спочатку дописують одиничний біт в кінець потоку (байт 0x80), потім необхідне число нульових біт. Вхідні дані вирівнюються так, щоб їх новий розмір L ' був порівняємо з 448 по модулю 512 ( L '= 512 \ times N + 448 ). Вирівнювання відбувається, навіть якщо довжина вже порівнянна з 448.

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

У що залишилися 64 біта дописують 64-бітове представлення довжини даних (кількість біт в повідомленні) до вирівнювання. Спочатку записують молодші 4 байти. Якщо довжина перевершує 2 ^ {64} -1 , То дописують тільки молодші біти. Після цього довжина потоку стане кратною 512. Обчислення будуть грунтуватися на представленні цього потоку даних у вигляді масиву слів по 512 біт.

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

Для обчислень инициализируются 4 змінних розміром по 32 біта і задаються початкові значення шістнадцятиричними числами (шістнадцяткове представлення, спочатку молодший байт):

 А = 01 23 45 67; В = 89 AB CD EF; С = FE DC BA 98; D = 76 54 32 10. 

У цих змінних будуть зберігатися результати проміжних обчислень. Початковий стан ABCD називається ініціалізувалися вектором.

Визначимо ще функції і константи, які нам знадобляться для обчислень.

  • Будуть потрібні 4 функції для чотирьох раундів. Введемо функції від трьох параметрів - слів, результатом також буде слово.
1 раунд Fun F (X, Y, Z) = (X \ wedge {Y}) \ vee (\ neg {X} \ wedge {Z}) .
2 раунд Fun G (X, Y, Z) = (X \ wedge {Z}) \ vee (\ neg {Z} \ wedge {Y}) .
3 раунд Fun H (X, Y, Z) = X \ oplus Y \ oplus Z .
4 раунд Fun I (X, Y, Z) = Y \ oplus (\ neg {Z} \ vee X) .
  • Визначимо таблицю констант T [1 \ ldots64] - 64-елементна таблиця даних, побудована наступним чином: T [i] = \ mathrm {int} (4 \, 294 \, 967 \, 296 * | \ sin (i) |) , Де 4 \, 294 \, 967 \, 296 = 2 ^ {32} . [3]
  • Вирівняні дані розбиваються на блоки (слова) по 32 біта, і кожен блок проходить 4 раунди з 16 операторів. Всі оператори однотипні і мають вигляд: [abcd ksi], який визначається як a = b + ((a + Fun (b, c, d) + X [k] + T [i]) <<< s) , Де X - блок даних. X [k] = M [n * 16 + k], де k - номер 32-бітного слова з n-го 512-бітного блоку повідомлення, і s - Циклічний зсув вліво на s біт отриманого 32-бітного аргументу.

2.4. Крок 4. Обчислення в циклі

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

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

Раунд 1

 / * [Abcd ksi] a = b + ((a + F (b, c, d) + X [k] + T [i]) <<< s). * / [ABCD 0 7 1] [DABC 1 грудня 2] [CDAB 2 17 3] [BCDA 22 березня 4] [ABCD 4 7 5] [DABC 12 Травня 6] [CDAB 17 червня 7] [BCDA 22 липня 8] [ABCD 8 Липень 9] [DABC 12 вересня 10] [CDAB 17 жовтня 11] [BCDA 22 листопада 12] [ABCD 12 липня 13] [DABC 13 грудня 14] [CDAB 14 17 15] [BCDA 15 22 16] 

Раунд 2

 / * [Abcd ksi] a = b + ((a + G (b, c, d) + X [k] + T [i]) <<< s). * / [ABCD 1 Травень 17] [DABC 6 вересня 18] [CDAB 14 листопада 19] [BCDA 0 20 20] [ABCD 5 травня 21] [DABC 10 вересня 22] [CDAB 15 14 23] [BCDA 20 квітня 24] [ABCD 9 Травень 25] [DABC 14 вересня 26] [CDAB 14 березня 27] [BCDA 20 серпня 28] [ABCD 13 травня 29] [DABC 9 Лютий 30] [CDAB 14 липня 31] [BCDA 20 грудня 32] 

Раунд 3

 / * [Abcd ksi] a = b + ((a + H (b, c, d) + X [k] + T [i]) <<< s). * / [ABCD 5 квітня 33] [DABC 11 Серпня 34] [CDAB 16 листопада 35] [BCDA 14 23 36] [ABCD 1 квітня 37] [DABC 11 квітня 38] [CDAB 16 липня 39] [BCDA 23 жовтня 40] [ABCD 13 квітня 41] [DABC 0 11 42] [CDAB 16 березня 43] [BCDA 23 червня 44] [ABCD 9 квітня 45] [DABC 11 Грудня 46] [CDAB 15 16 47] [BCDA 23 лютого 48] 

Раунд 4

 / * [Abcd ksi] a = b + ((a + I (b, c, d) + X [k] + T [i]) <<< s). * / [ABCD 0 6 49] [DABC 7 жовтня 50] [CDAB 14 15 51] [BCDA 21 травня 52] [ABCD 6 грудня 53] [DABC 3 жовтня 54] [CDAB 15 жовтня 55] [BCDA 21 січня 56] [ABCD 8 червня 57] [DABC 15 жовтня 58] [CDAB 15 червня 59] [BCDA 13 21 60] [ABCD 4 червня 61] [DABC 11 жовтня 62] [CDAB 15 лютого 63] [BCDA 21 вересня 64] 

Підсумовуємо з результатом попереднього циклу:

 A = AA + AB = BB + BC = CC + CD = DD + D 

Після закінчення циклу необхідно перевірити, чи є ще блоки для обчислень. Якщо так, то змінюємо номер елемента масиву (n + +) і переходимо в початок циклу.


2.5. Крок 5. Результат обчислень

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

2.6. Порівняння MD5 і MD4

Алгоритм MD5 походить від MD4. У новий алгоритм додали ще один раунд, тепер їх стало 4 замість 3 в MD4. Додали нову константу для того, щоб звести до мінімуму вплив вхідного повідомлення, в кожному раунді на кожному кроці і кожен раз константа різна, вона підсумовується з результатом F і блоком даних. Змінилася функція G = XZ v (Y not (Z)) замість (XY v XZ v YZ). Результат кожного кроку складається з результатом попереднього кроку, через це відбувається більш швидка зміна результату. Змінився порядок роботи з вхідними словами в раундах 2 і 3.

Відмінності в швидкості роботи представлені в таблиці:

Таблиця порівняння швидкостей
MD5 MD4
RFC 2,614 сек 37359 Кб / с 2,574 сек 37940 Кб / с
OpenSSL 1,152 сек 84771 Кб / с 0,891 сек 109 603 Кб / с

Необхідно було обчислити 10000 хешей для повідомлення довжиною 10 000 байт. В якості реалізацій використовувалися OpenSSL і RFC 1321.


3. MD5-хеш-кодування

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

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

 MD5 ("md5") = 1bc29b36f623ba82aaf6724fd3b16718 

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

 MD5 ("md4") = c93d3bf7a7c4afe94b64e30c2ce39f4f 

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

 MD5 ("") = d41d8cd98f00b204e9800998ecf8427e 

4. Криптоаналіз

На даний момент існують кілька видів "злому" хешів MD5 - підбору повідомлення із заданим хешем:

4.1. Атаки переборного типу

Для повного перебору або перебору по словнику можна використовувати програми PasswordsPro [4], MD5BFCPF [5], John the Ripper. Для перебору по словнику існують готові словники. [6]

RainbowCrack - ще один метод злому хешу. Він заснований на генеруванні великої кількості хешей з набору символів, щоб по получившейся базі вести пошук заданого хешу. Хоча генерація хешей займає багато часу, зате наступний злом проводиться дуже швидко.


4.2. Колізії MD5

Колізія хеш-функції - це отримання однакового значення функції для різних повідомлень і ідентичного початкового буфера. На відміну від колізій, псевдоколлізіі визначаються як рівні значення хешу для різних значень початкового буфера, причому самі повідомлення можуть збігатися або відрізнятися. В 1996 Ганс Доббертін знайшов псевдоколлізіі в MD5, використовуючи певні ініціалізували вектори, відмінні від стандартних. Виявилося, що можна для відомого повідомлення побудувати друге, таке, що воно буде мати такий же хеш, як і вихідне. C точки зору математики це означає: MD5 (IV, L1) = MD5 (IV, L2), де IV - початкове значення буфера, а L1 і L2 - різні повідомлення. Наприклад, якщо взяти початкове значення буфера:

 A = 0x12AC2375 В = 0x3B341042 C = 0x5F62B97C D = 0x4BA763ED 

і задати вхідне повідомлення

AA1DDABE D97ABFF5 BBF0E1C1 32774244
1006363E 7218209D E01C136D 9DA64D0E
98A1FB19 1FAE44B0 236BB992 6B7A779B
1326ED65 D93E0972 D458C868 6B72746A

то, додаючи число 2 ^ 9 до певного 32-розрядному слову в блоковому буфері, можна отримати другу повідомлення з таким же хешем. Ханс Доббертін представив таку формулу:

L2_i = \ begin {cases} L1_i, & i \ ne 14; \ \ L1_i + 2 ^ 9, & i = 14. \ End {cases}

Тоді MD5 (IV, L1) = MD5 (IV, L2) = BF90E670752AF92B9CE4E3E1B12CF8DE.

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

В 2005 Ван Сяоюнь і Юй Хунбо з університету Шаньдуна в Китаї опублікували алгоритм, який може знайти дві різні послідовності в 128 байт, що дають однаковий MD5-хеш. Одна з таких пар (що відрізняються розряди виділені):

d131dd02c5e6eec4693d9a0698aff95c 2fcab5 8 712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325 7 1415a 085125e8f7cdc99fd91dbd f 280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2 b 487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080 a 80d1e c69821bcb6a8839396f965 2 b6ff72a70

і

d131dd02c5e6eec4693d9a0698aff95c 2fcab5 0 712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325 f 1415a 085125e8f7cdc99fd91dbd 7 280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2 3 487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080 2 80d1e c69821bcb6a8839396f965 a b6ff72a70

Кожен з цих блоків дає MD5-хеш, рівний 79054025255fb1a26e4bc422aef54eb4.


4.2.1. Метод Ван Сяоюня і Юй Хунбо

Метод Ван Сяоюня і Юй Хунбо використовує той факт, що MD5 побудований на ітераційному методі Меркле-Дамгарда. Поданий на вхід файл спочатку доповнюється, так щоб його довжина була кратна 64 байтам, після цього він ділиться на блоки по 64 байти кожен M 0, M 1,..., M n -1. Далі обчислюється послідовність 16-байтних станів s 0,..., s n за правилом s i +1 = f (s i, M i), де f деяка фіксована функція. Початковий стан s 0 називається ініціалізувалися вектором.

Метод дозволяє для заданого ініціалізує вектора знайти дві пари M, M ' і N, N ' , Такі що f (f (s, M), M ') = f (f (s, N), N') . Важливо відзначити, що цей метод працює для будь-якого ініціалізується вектора, а не тільки для вектора використовуваного за стандартом.

Ця атака є різновидом диференціальної атаки, яка, на відміну від інших атак цього типу, використовує цілочисельне віднімання а не XOR в якості міри різниці. При пошуку колізій використовується метод модифікації повідомлень: спочатку вибирається довільне повідомлення M 0, далі воно модифікується за деякими правилами, сформульованим у статті, після чого обчислюється диференціал хеш-функції, причому M'_0 = M_0 + dM_0 з імовірністю 2 -37. До M_0 і M'_0 застосовується функція стиснення для перевірки умов колізії; далі вибирається довільне M_1 , Модифікується, обчислюється новий диференціал, рівний нулю з імовірністю 2 -30, а рівність нулю диференціала хеш-функції як раз означає наявність колізії. Виявилося, що знайде одну пару M_0 і M'_0 , Можна міняти лише два останніх слова в M_0 , Тоді для знаходження нової пари M_1 і M'_1 потрібно всього близько 2 39 операцій хешування.

Застосування цієї атаки до MD4 дозволяє знайти колізію менше ніж за секунду. Вона також застосовна до інших хеш-функцій, таких як RIPEMD і HAVAL.

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


5. Приклади використання

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

За допомогою MD5 перевіряють цілісність викачаних файлів - так, деякі програми йдуть разом зі значенням хешу. Наприклад, диски для інсталяції.

MD5 використовується для хешування паролів. У системі UNIX кожен користувач має свій пароль і його знає тільки користувач. Для захисту паролів використовується хеширование. Передбачалося, що отримати справжній пароль можна лише повним перебором. При появі UNIX єдиним способом хешування був DES (Data Encryption Standard), але ним могли користуватися тільки мешканці США, тому що вихідні коди DES не можна було вивозити з країни. Під FreeBSD вирішили цю проблему. Користувачі США могли використовувати бібліотеку DES, а інші користувачі мають метод, дозволений для експорту. Тому в FreeBSD стали використовувати MD5 за замовчуванням. [11]. Деякі Linux -системи також використовують MD5 для зберігання паролів.

Багато системи використовують базу даних для зберігання паролів та існує декілька способів для зберігання паролів.

  1. Паролі зберігаються як є. При зломі такої бази всі паролі стануть відомі.
  2. Зберігаються тільки хеши паролів (за допомогою MD5, SHA). Знайти паролі можна лише повним перебором. Але за умови використання нескладного, популярного або просто нещасливого пароля (який зустрічався раніше і занесений в таблицю) така задача вирішується за частки секунди. Пароль з таблиці був знайдений всього за 0,036059 сек. [12]
  3. Зберігаються хеши паролів і кілька випадкових символів. До кожного паролю додається декілька випадкових символів (їх ще називають "salt" або " сіль ") і результат ще раз хешіруется. Наприклад, md5 (md5 (pass) + word). Знайти пароль за допомогою таблиць таким методом не вийде.
Приклад бази даних
спосіб id login password
1 5 anton mydata
2 5 anton md5 (mydata)
3 5 anton md5 (md5 (mydata) + word) і word

Існує кілька надбудов над MD5.

  • MD5 (HMAC) - HMAC - Keyed-Hashing for Message Authentication (хеширование з ключем для аутентифікації повідомлення) - алгоритм дозволяє хешіровать вхідне повідомлення L з деяким ключем K, таке хеширование дозволяє автентифікувати підпис.
  • MD5 ( Base64) - тут отриманий MD5-хеш кодується алгоритмом Base64.
  • MD5 (Unix) - алгоритм викликає тисячу разів стандартний MD5.

Примітки

  1. 1 2 What are MD2, MD4, and MD5? - www.rsa.com/rsalabs/node.asp?id=2253 (Англ.) . RSA Laboratories (2000). Читальний - www.webcitation.org/61AADFziE з першоджерела 24 серпня 2011.
  2. R. Rivest. The MD5 Message-Digest Algorithm - rfc.com.ru/rfc1321.htm (квітень 1992). Читальний - www.webcitation.org/61AADlMwU з першоджерела 24 серпня 2011.
  3. Іншими словами, в таблиці представлені по 32 біта після десяткової коми від значень функції sin.
  4. PasswordsPro - www.insidepro.com / rus / passwordspro.shtml. InsidePro Software. - Програма для відновлення паролів до хешам різних типів. Читальний - www.webcitation.org/61AAEI0wj з першоджерела 24 серпня 2011.
  5. Проект MD5 - md5bfcpf.sourceforge.net на сайті SourceForge.net
  6. CERIAS - Security Archive. Center for Education and Research in Information Assurance and Security (червень 2000).
  7. Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD - eprint.iacr.org/2004/199 (Англ.) (17 серпня 2004). Читальний - www.webcitation.org/61AAF4PT7 з першоджерела 24 серпня 2011.
  8. Philip Hawkes, Michael Paddon, Gregory G. Rose. Musings on the Wang et al. MD5 Collision - eprint.iacr.org/2004/264 (Англ.) (13 жовтня 2004). Читальний - www.webcitation.org/61AAFVLMw з першоджерела 24 серпня 2011.
  9. Vlastimil Kli'ma. Tunnels in Hash Functions: MD5 Collisions Within a Minute - eprint.iacr.org/2006/105 (Англ.) (17 квітня 2006). Читальний - www.webcitation.org/61AAFv2q7 з першоджерела 24 серпня 2011.
  10. Vlastimil Klima. MD5 collisions - cryptography.hyperlink.cz/MD5_collisions.html (Англ.) . Читальний - www.webcitation.org/61AAGKcF4 з першоджерела 24 серпня 2011.
  11. Bill Swingle. Керівництво FreeBSD (DES, MD5 і шифрування) - www.nbuv.gov.ua/books/2004/freebsd/crypt.html (2006). Читальний - www.webcitation.org/61AAGo23S з першоджерела 24 серпня 2011.
  12. An Online MD5 Hash Database - gdataonline.com /. Читальний - www.webcitation.org/61AAHHOkX з першоджерела 24 серпня 2011.

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

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