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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Колізією хеш-функції H називаються два різних вхідних блоки даних x і y таких, що H(x) = H(y).

Колізії існують для більшості хеш-функцій, але для «хороших» хеш-функцій частота їх виникнення близька до теоретичного мінімуму. В деяких окремих випадках, коли множина різних вхідних даних є скінченною, можна задати ін'єктивну хеш-функцію, за визначенням без колізій. Однак, для хеш-функцій, які приймають вхідні дані змінної довжини і повертають хеш постійної довжини (таких як MD5), колізії обов'язково будуть існувати, оскільки хоча б для одного значення хеш-функції відповідна йому вхідна множина значень буде безкінечною — і будь-які два значення з цієї множини утворюють колізію.

Приклад[ред.ред. код]

Розглянемо в якості прикладу хеш-функцію H(x)=x\ \bmod 19, визначену на множині цілех чисел. Її область значень складається з 19 елементів, а область визначення — безкінечна. Через те, що область множина прообразів явно більше множини значень, колізії мають існувати.

Побудуємо колізію для цієї хеш-функції для вхідного значення 38, хеш-сума якого дорівнює нулю. через те, що функція H(x) — періодична з періодом 19, то для будь-якого вхідного значення y, значення y+19 буде мати таку саму хеш-суму, що і y. Зокрема, для вхідного значення 38 таку саму хеш-суму будуть мати 57, 76 і т. д. Таким чином пари вхідних значень (38,57), (38,76) утворюють колізії хеш-функції H(x).

Колізії криптографічних хеш-функцій[ред.ред. код]

Через те, що криптографічні хеш-функції використовуються для підтвердження незмінності вхідної інформації, можливість швидкого знаходження колізій для них рівноцінна дискредитації. Наприклад, якщо хеш-функція використовується для створення цифрового підпису, тоді вміння знаходити колізії рівноцінне вмінню підробляти цифрові підписи. Тому ступенем криптографічної стійкості хеш-функції вважається обчислювальна складність знаходження колізій. В ідеалі не має існувати способу знайдення колізій ніж повний перебір. Якщо для деякої хеш-функції знаходиться спосіб знайдення колізій значно швидший за повний перебір, тоді ця хеш-функція припиняє вважатися криптостійкою і використовуватись для передачі і збереження секретної інформації. Теоретичні і практичні питання знаходження і використання колізій щорічно обговорюються в рамках міжнародних конференцій (наприклад, CRYPTO та ASIACRYPT), а також в багатьох публікаціях.

Властивості криптографічних хеш-функцій[ред.ред. код]

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

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

Використання колізій для зламу[ред.ред. код]

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

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

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

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

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

Захист від використання колізій[ред.ред. код]

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

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

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

Методи пошуку колізій[ред.ред. код]

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