РЕФЕРАТ

на тему

“Пошук колізій хеш-функції MD5”

Вступ

MD5 – одна з найбільш широко використовуваних сучасних криптографічних хеш-функцій. Вона була розроблена у 1992 році як вдосконалення MD4, і з тих пір її захищеність була детально досліджена декількома авторами. Найвідомішим результатом була частинна колізія, у якій початкове значення хеш-функції замінювалося нестандартним значенням, яке було результатом атаки. Наразі розроблена нова атака, яка дозволяє ефективно знаходити колізії. Вона дозволяє знаходити колізії MD5, витрачаючи на це 15-60 хвилин роботи комп’ютера (Pentium4 1.6GHz). Ця атака є диференційною атакою, яка на відміну від інших диференційних аткак, використовує для визначення різниці не операцію XOR, а модульне цілочисельне віднімання. Ця атака дістала назву модульно-диференційної. Застосування цієї атаки на MD4 дозволяє знаходити колізії за долі секунди. Ця атака також застосовна для інших хеш-функцій, таких як RIPEMD та HAVAL.

Загальновідомо, що цифрові підписи дуже важливі в інформаційній безпеці. Захищеність цифрових підписів залежить від криптографічної стійкості хеш-функцій, на основі яких вони реалізовані. Хеш-функції також мають багато інших застосувань у криптографії, зокрема для реалізації цілостності даних у СКБД, групових підписів, електронної оплати та реалізації багатьох інших криптографічних протоколів. Використання хеш-функцій дозволяє не тільки покращити безпеку, а й значно підвищити рівень ефективності алгоритмів. В наш час найбільш використовуваними є дві хеш-функції – MD5 та SHA1.

MD5 (Message-Digest Algorithm) – це хеш-функція, розроблена Роном Рівестом (Ron Rivest) як вдосконалена версія MD4. З моменту її створення було знайдено кілька слабких місць. В 1993 Б. ден Бояром (B. den Boer) та А.Босселаерсом (A.Bosselaers) був знайдений різновид псевдо-колізій MD5, який складався з однакових повідомлень, отриманих із різних наборів початкових значень. Ця атака виявила уразливість в MD5. На конференції Eurocrypt’96 Х.Доббертін (H.Dobbertin) представив частинну колізію, яка містила два різних 512-бітних повідомлення з вибраним початковим значенням .

Проте Х.Доббертін (H.Dobbertin) не зміг представити реальну колізію до MD5, його атака лише відкривала уразливість повного MD5. Це давало можливість знаходити спеціальні різниці за одну ітерацію.

Ця атака дала поштовх для вивчення питання, чи можливо знайти пару повідомлень, що складалися б з двох блоків, які б давали колізію після другого блоку. Тобто необхідно знайти пару та , таку що

де , , , є початковими значеннями для MD5. Далі буде показано, що такі колізії MD5 можуть бути знайдені ефективно: для визначення першого блоку необхідно приблизно MD5 операцій, а знаходження другого блоку потребує приблизно MD5 операцій. Програмна реалізація цієї атаки на IBM P690 потребує приблизно одну годину, щоб знайти та (в кращому випадку на це витрачається лише 15 хвилин). Далі необхідно лише від 15 секунд до 5 хвилин, щоб знайти другий блок та . Дві такі колізії були представлені на Crypto’04.

Опис MD5

Перед тим як дати опис структури MD5, опишемо ітераційний процес для хеш-функцій.

Переважно хеш-функції ітерується стискаючою функцією , яка стискає -бітний блок повідомлення в -бітне хеш значення , де . Для MD5 , а . Ітераційний метод часто називають мета-методом Меркле-Дамгарда (Merkle-Damgard meta-method). Для повідомлення, що складається з декількох -бітних блоків, ітераційний процес має наступний вигляд:

де , і є початковим значенням для хеш-функції.

Тепер опишемо стискаючу функцію для MD5. Вихідне повідомлення розбивається на 512-бітні блоки. Дописується послідовність 10000...0 || 64 бітного значення довжини послідовності в бітах. Кожний 512-бітний блок розбиваємо на 32-бітні слова, . Алгоритм стиснення для складається з чотирьох етапів, на кожному з яких виконується 16 операцій. Чотири послідовних етапи операцій мають наступний вигляд:

де операція + означає додавання по модулю . та є залежними від етапу константами. є словом повідомлення. є операцією циклічного зміщення вліво на біт. Детальна інформація про слідування повідомлень і зміну позицій наведена у таблиці 3.

На кожному етапі використовується одна нелінійна функція із поданих нижче:

де , , є 32-бітними словами.

Зв’язані змінні ініціюються наступним чином:

Ми вибираємо колізію диференційно з двох наступних ітерацій: Нехай значення залежить від попереднього блоку повідомлення. Після чотирьох етапів стиснене значення знаходиться послівним додаванням зв’язаних змінних до .

Диференціальна атака на MD5

Базові поняття

Перед тим як дати опис атаки, означимо деякі поняття.

та відображають два 512-бітні повідомлення. позначає різницю між двома блоками повідомлень: .

, , , відповідно є результатом -го, -го, -го та -го кроку по стисненню , де . , , , отримуються аналогічно.

, , , відображають відповідно -й біт , , , , де найменш значимим є перший біт, а найбільш значимим є 32-й біт.

є -м бітом результату нелінійної функції на -му кроці операції.

є бітом різниці, що отримується в результаті зміни -го біта . , ( може бути , , , , ) є результуючим значенням зміни -го біта слова . отримується зміною -го біта з 0 на 1, а отримується зміною -го біта з 1 на 0.

позначає різницю, яка отримується зміною -го, -го, …, -го біта . Знак “+” (ним зазвичай нехтують) означає, що біт був змінений із 0 на 1, а знак “-” означаэ, що біт був змінений з 1 на 0.

Диференціальна колізія для MD5

Дана атака може знайти багато реальних колізій, які утворені з двох 1024-бітних повідомлень та з оригінального початкового значення MD5:

Ми вибираємо колізію диференційно з двох наступних ітерацій:

де

Ненульові складові та розміщені на 5-й,