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

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

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

Приклад

Розглянемо до прикладу хеш-функцію $H(x)=x\ {\bmod {1}}9$, визначену на множині цілих чисел. Її область значень складається з 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}$.

Література

• Askitis, Nikolas; Zobel, Justin (2005). Consens, M.; Navarro, G. (ред.). Cache-Conscious Collision Resolution in String Hash Tables. International Symposium on String Processing and Information Retrieval. String Processing and Information Retrieval SPIRE 2005. Lecture Notes in Computer Science. Т. 3772. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 91—102. doi:10.1007/11575832_11. ISBN 978-3-540-29740-6.
• Nimbe, Peter; Ofori Frimpong, Samuel; Opoku, Michael (20 серпня 2014). An Efficient Strategy for Collision Resolution in Hash Tables. International Journal of Computer Applications. 99 (10): 35—41. Bibcode:2014IJCA...99j..35N. doi:10.5120/17411-7990. ISSN 0975-8887.