Ми обираємо таким чином, щоб різниці 3-4 етапу існували з великою імовірністю. вибирається не тільки щоб забезпечити існування різниць 3-4 етапу, але і щоб отримати різницю результатів, які можуть бути відмінені результатом різниці .

Колізія різниць з усіма характеристиками може посилатися на таблиці 3 та 5. Стовпці обох таблиць мають однакове значення. Ми лише дамо пояснення до таблиці 3. Перший стовпець означає крок, другий стовпець є змінною на кожному кроці для , третій є словом повідомлення для на кожному кроці, четвертий позначає зміну, п’ятий та шостий стовпці є відповідно різницею слів повідомлень та різницею для та , у сьомому знаходиться зв’язана змінна для . Порожні значення у шостому та п’ятому стовпцях означають нульові різниці, а кроки, які не відображені у таблиці мають нульові різниці одночасно для слів повідомлення і для зв’язаних змінних.

Достатні умови для існування характеристик

Далі ми опишемо як отримати набір достатніх умов, які б гарантували існування диференціальної характеристики на восьмому кроці MD5 (таблиця 3). Інші умови знаходяться аналогічно.

Диференційна характеристика на восьмому кроці MD5 є:

Кожна зв’язана змінна задовольняє одному з наступних рівнянь:

Відповідно до операцій восьмого кроку, маємо:

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

Висновок базується на двох наступних фактах:

З того що і випливай, що .

Фіксація однієї або двох змінних в таким чином, щоб зменшувалося до однієї змінної.

Ми отримали набір достатніх умов що гарантує існування диференційних характеристик.

Умови для кожного ненульового біта в .

(а) Умови і гарантують зміну першого біта .

i. Якщо , то ми знаємо,, що .

ii. Після , знаходитьсяу позиції .

iii. Так як , то .

(b) Умови , і гарантують зміну 16-го і 17-го біта .

(с) Умови , , і гарантують зміну 18-го, 19-го, 20-го та 21-го біта .

(d) Умови і гарантують зміну 24-го біта . Це може бути представлене у вигляді рівняння:

Умови для кожного нульового біта в .

Умова гарантує зміну бітів з 7-го по 12 в та 17-го біта в , в результаті чого не змінюються біти в . Це легко підтвердити наступним рівнянням:

Умови гарантують, що зміна -го біта в результаті не змінює в , де .

Умови гарантують, що зміна і-го біта в не змінить , де .

Умова гарантує, що 6-й біт в в результаті не змінить .

Умова гарантує, що зміна 32-го біта в і 32-го біта в не змінить .

Умова гарантує, що зміна -го біта в та -го біта в в результаті не змінить , де .

Умова гарантує, що зміна 12-го біта в та 12-го біта в не змінить .

Умова гарантує, що зміна 24-го біта в та 24-го біта в , не змінить .

Зміна 7-го біта в , та не змінює .

За схожим принципом ми можемо отримати набір достатніх умов (таблиця 4 та таблиця 6), які гарантують існування всіх диференціальних характеристик в диференціальній колізії.

Модифікація повідомлень

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

Для кожного блоку повідомлення (аналогічно ) та проміжних значень ( або та для другого блоку) ми виконуємо наступні процедури, щоб модифікувати (або відповідно) так, щоб всі умови першого етапу (перші 16 кроків) виконувалися (таблиця 4 і таблиця 6).

Легко модифікувати так, щоб умови першого етапу виконувалися з імовірністю 1.

Наприклад, щоб забезпечити виконання 3-ї умови для в таблиці 4, ми модифікуємо наступним чином:

Модифікацією кожного слова повідомлення можна досягти виконання всіх умов першого етапу. Диференіціал першого етапу знаходиться з імовірністю .

Аналогічно модифікуємо . Після модифікації диференціал знаходиться з імовірністю .

Модифікакація декількох повідомлень. Далі ми можемо досягти виконання частини умов перших 32 кроків шляхом модифікації декількох повідомлень.

Наприклад, якщо , ми змінюємо його на модифікацією за умови що модифікація обумовлює частинну колізію на 2-6 кроках, а умови першого етапу так само виконуються. Дивись таблицю 1.

Деякі інші умови можуть бути зкоректовані аналогічним способом модифікації. Після таких модифікацій 37 умов 2-4 етапів залишається невизначеними в таблиці 4, а 30 умов 2-4 етапів залишається невизначеними в таблиці 6. Таким чином диференціал 1-ї ітерації отримується з імовірністю , а диференціал другої ітерації – з імовірністю .

Таблиця 1. Модифікація повідомлення для корекції

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

Після наведеного опису легко показати атаку на MD5.

Далі описується як знаходиться колізія двох блоків слідуючої форми:

1. Повторювати наступні дії, поки не буде знайдений перший блок.

(a) Обирається довільне повідомлення .

(b) модифікується способом, описаним в попередньому розділі.

(с) Тоді з та отримується диференціал першої ітерації з імовірністю .

(d) Перевіряється, чи всі характеристики дійсно виконуються після застосування стискаючої функції на та .

2. Повторювати наступні кроки, поки не буде знайдена колізія

(а) Обрати довільне повідомлення .

(b) модифікується способом, описаним в попередньому розділі.

(с) Тоді з та отримується диференціал другої ітерації з імовірністю .

(d) Перевіряється чи отримується з цієї пари повідомлень колізія.

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