вимагає лише одноразової модифікації одного повідомлення для перших 14 слів. Цим часом можна знехтувати. Для кожного обраного повідомлення необхідна лише подвійна модифікація одного повідомлення для останніх двох слів та семикратна модифікація декількох повідомлень для корекції 7 умов на другому етапі, а кожна модифікація декількох повідомлень вимагає декілька операцій, тому загальний час обох видів модифікацій не перевищує двох MD5 операцій для кожного обраного повідомлення. Відповідно до імовірності диференціалу першого етапу, легко визначити, що складність знаходження не перевищує MD5 операцій.
Аналогічно ми можемо показати, що складність знаходження не перевищує MD5 операцій.
Дві колізії MD5 наведені у таблиці 2. Відомо, що дві колізії починаються з однакового першого 512-бітного блоку, і що даний перший блок задовольняє всі необхідні вимоги, тому легко знайти декілька других блоків , , які дають колізію.
Таблиця 2. Дві пари колізій для MD5. є хеш-значенням з прямим порядком слідування байт та без доповнення повідомлення, а є хеш-значенням із слідуванням байтів починаючи зі старшого та доповненням повідомлень.
Маємо, що дві послідовності:
0xd1 0x31 0xdd 0x02 0xc5 0xe6 0xee 0xc4 0x69 0x3d 0x9a 0x06 0x98 0xaf 0xf9 0x5c
0x2f 0xca 0xb5 0x87 0x12 0x46 0x7e 0xab 0x40 0x04 0x58 0x3e 0xb8 0xfb 0x7f 0x89
0x55 0xad 0x34 0x06 0x09 0xf4 0xb3 0x02 0x83 0xe4 0x88 0x83 0x25 0x71 0x41 0x5a
0x08 0x51 0x25 0xe8 0xf7 0xcd 0xc9 0x9f 0xd9 0x1d 0xbd 0xf2 0x80 0x37 0x3c 0x5b
0xd8 0x82 0x3e 0x31 0x56 0x34 0x8f 0x5b 0xae 0x6d 0xac 0xd4 0x36 0xc9 0x19 0xc6
0xdd 0x53 0xe2 0xb4 0x87 0xda 0x03 0xfd 0x02 0x39 0x63 0x06 0xd2 0x48 0xcd 0xa0
0xe9 0x9f 0x33 0x42 0x0f 0x57 0x7e 0xe8 0xce 0x54 0xb6 0x70 0x80 0xa8 0x0d 0x1e
0xc6 0x98 0x21 0xbc 0xb6 0xa8 0x83 0x93 0x96 0xf9 0x65 0x2b 0x6f 0xf7 0x2a 0x70
0xd1 0x31 0xdd 0x02 0xc5 0xe6 0xee 0xc4 0x69 0x3d 0x9a 0x06 0x98 0xaf 0xf9 0x5c
0x2f 0xca 0xb5 0x07 0x12 0x46 0x7e 0xab 0x40 0x04 0x58 0x3e 0xb8 0xfb 0x7f 0x89
0x55 0xad 0x34 0x06 0x09 0xf4 0xb3 0x02 0x83 0xe4 0x88 0x83 0x25 0xf1 0x41 0x5a
0x08 0x51 0x25 0xe8 0xf7 0xcd 0xc9 0x9f 0xd9 0x1d 0xbd 0x72 0x80 0x37 0x3c 0x5b
0xd8 0x82 0x3e 0x31 0x56 0x34 0x8f 0x5b 0xae 0x6d 0xac 0xd4 0x36 0xc9 0x19 0xc6
0xdd 0x53 0xe2 0x34 0x87 0xda 0x03 0xfd 0x02 0x39 0x63 0x06 0xd2 0x48 0xcd 0xa0
0xe9 0x9f 0x33 0x42 0x0f 0x57 0x7e 0xe8 0xce 0x54 0xb6 0x70 0x80 0x28 0x0d 0x1e
0xc6 0x98 0x21 0xbc 0xb6 0xa8 0x83 0x93 0x96 0xf9 0x65 0xab 0x6f 0xf7 0x2a 0x70
дають на виході однакове хеш-значення 79054025255fb1a26e4bc422aef54eb4.
Висновок
Даний матеріал показує, що знаходження колізії для MD5 є цілком реальною задачею.
Також ця атака може бути застосована для знаходження колізій для інших хеш-функцій, зокрема HAVAL-128, MD4, RIPEMD, SHA-0. Аналіз результатів для цих функцій наступний:
Часова складність для знаходження колізії MD4 є приблизно MD4 операцій без застосування модифікації декількох повідомлень, та приблизно MD4 операцій з застосуванням даного прийому.
Часова складність для знаходження колізії HAVAL-128 є приблизно MD4 операцій без застосування модифікації декількох повідомлень, та приблизно HAVAL-128 операцій з застосуванням даного прийому.
Часова складність для знаходження колізії RIPEMD є приблизно RIPEMD операцій без застосування модифікації декількох повідомлень, та приблизно RIPEMD операцій з застосуванням даного прийому.
Часова складність для знаходження колізії SHA-0 є приблизно SHA-0 операцій без застосування модифікації декількох повідомлень, та приблизно SHA-0 операцій з застосуванням даного прийому.
Додаток
Таблийця 3. Диференційні характеристики для першої ітерації
Таблиця 4. Набір достатніх умов для існування диференціалу першої ітерації
Таблиця 5. Всі диференційні характеристики для диференціалу другої ітерації
Таблиця 6. Набір достатніх умов для існування диференціалу другої ітерації
Використана література
Xiaoyun Wang and Hongbo Yu How to Break MD5 and Other Hash Functions
RFC1321