Колізія геш-функції

Для того, щоб хеш-функція H вважалась криптографічно стійкою, вона має задовольняти трьом основним вимогам, на яких ґрунтуються більшість застосувань хеш-функцій в криптографії:

• Незворотність: для заданого значення хеш-функції m має бути практично неможливо знайти блок даних ${\displaystyle X}$, для якого ${\displaystyle H(X)=m}$.
• Стійкість до колізій першого роду: для заданого повідомлення M має бути практично неможливо підібрати друге повідомлення N, для якого ${\displaystyle H(N)=H(M)}$.
• Стійкість до колізій другого роду: має бути практично неможливо підібрати пару повідомлень ${\displaystyle ~(M,M')}$, які мають однаковий хеш.

Як приклад можна розглянути процедуру автентифікації користувача:

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

При такому підході, навіть якщо зловмисник отримає доступ до БД, він не зможе відновити паролі користувачів (при умові незворотності хеш-функції). Однак, якщо зловмисник вміє знаходити колізії для цієї хеш-функції, він зможе знайти підробний пароль, який буде мате ту саму хеш-суму, що і пароль користувача.

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

Схожим чином можна використати колізії для підробки цифрового підпису і сертифіката.

Існує кілька методів захисту від зламу, підробки паролів, підписів, сертифікатів, навіть якщо зловмиснику відомі методи побудови колізій для якої-небудь хеш-функції.

Одним з методів є метод «salt», який застосовується при збереженні UNIX-паролів — додавання деякої послідовності символів перед хешуванням. Іноді ця послідовність додається до отриманого хеша. Після такої процедури, підсумкові хеш-таблиці значно складніше аналізувати, а через те, що послідовність секретна, істотно підвищується складність побудови колізій — зловмиснику має бути відома послідовність «salt».

Іншим методом є конкатенація хешів, отриманих від двох різних хеш-функцій. При цьому, для того щоб підібрати колізії до хеш-функції ${\displaystyle C(x)=y(x)\|z(x)}$, яка є конкатенацією хеш-функції ${\displaystyle y(x)}$ и ${\displaystyle z(x)}$, необхідно знати методи побудови колізій для ${\displaystyle y(x)}$, і ${\displaystyle z(x)}$. Недоліком конкатенації є збільшення розміру хеша, що часто неприйнятно в реальних застосунках.

Одним з найбільш простих і універсальних методів пошуку колізій є атака «днів народження». За допомогою цієї атаки знаходження колізії для хеш-функції розрядності ${\displaystyle n}$ біт потрібно в середньому близько ${\displaystyle 2^{n/2}}$ операцій. Через це n-бітова хеш-функція вважається криптостійкою, якщо обчислювальна складність знаходження колізій для неї близька до ${\displaystyle 2^{n/2}}$.