Колізією хеш-функції називаються два різних вхідних блоки даних і таких, що
Колізії існують для більшості хеш-функцій, але для «хороших» хеш-функцій частота їх виникнення близька до теоретичного мінімуму. В деяких окремих випадках, коли множина різних вхідних даних є скінченною, можна задати ін'єктивну хеш-функцію, за визначенням без колізій. Однак, для хеш-функцій, які приймають вхідні дані змінної довжини і повертають хеш постійної довжини (таких як MD5), колізії обов'язково будуть існувати, оскільки хоча б для одного значення хеш-функції відповідна йому вхідна множина значень буде безкінечною — і будь-які два значення з цієї множини утворюють колізію.
Приклад Редагувати
Розглянемо до прикладу хеш-функцію , визначену на множині цілих чисел. Її область значень складається з 19 елементів, а область визначення — безкінечна. Через те, що область множини прообразів явно більше множини значень, колізії мають існувати.
Побудуємо колізію для цієї хеш-функції для вхідного значення 38, хеш-сума якого дорівнює нулю. через те, що функція — періодична з періодом 19, то для будь-якого вхідного значення y, значення y+19 буде мати таку саму хеш-суму, що і y. Зокрема, для вхідного значення 38 таку саму хеш-суму будуть мати 57, 76 і т. д. Таким чином пари вхідних значень (38,57), (38,76) утворюють колізії хеш-функції .
Колізії криптографічних хеш-функцій Редагувати
Через те, що криптографічні хеш-функції використовуються для підтвердження незмінності вхідної інформації, можливість швидкого знаходження колізій для них рівноцінна дискредитації. Наприклад, якщо хеш-функція використовується для створення цифрового підпису, тоді вміння знаходити колізії рівноцінне вмінню підробляти цифрові підписи. Тому ступенем криптографічної стійкості хеш-функції вважається обчислювальна складність знаходження колізій. В ідеалі не має існувати способу знайдення колізій ніж повний перебір. Якщо для деякої хеш-функції знаходиться спосіб знайдення колізій значно швидший за повний перебір, тоді ця хеш-функція припиняє вважатися криптостійкою і використовуватись для передачі і збереження секретної інформації. Теоретичні і практичні питання знаходження і використання колізій щорічно обговорюються в рамках міжнародних конференцій (наприклад, CRYPTO та ASIACRYPT), а також в багатьох публікаціях.
Властивості криптографічних хеш-функцій Редагувати
Для того, щоб хеш-функція H вважалась криптографічно стійкою, вона має задовольняти трьом основним вимогам, на яких ґрунтуються більшість застосувань хеш-функцій в криптографії:
- Незворотність: для заданого значення хеш-функції m має бути практично неможливо знайти блок даних , для якого .
- Стійкість до колізій першого роду: для заданого повідомлення M має бути практично неможливо підібрати друге повідомлення N, для якого .
- Стійкість до колізій другого роду: має бути практично неможливо підібрати пару повідомлень , які мають однаковий хеш.
Використання колізій для зламу Редагувати
Як приклад можна розглянути процедуру автентифікації користувача:
- при реєстрації в системі користувач вводить свій пароль, до якого застосовується деяка хеш-функція, значення якої записується в базу даних;
- при кожному введені паролю, до нього застосовується та сама хеш-функція, а результат порівнюється з тим, що записаний в БД.
При такому підході, навіть якщо зловмисник отримає доступ до БД, він не зможе відновити паролі користувачів (при умові незворотності хеш-функції). Однак, якщо зловмисник вміє знаходити колізії для цієї хеш-функції, він зможе знайти підробний пароль, який буде мате ту саму хеш-суму, що і пароль користувача.
Можна використати колізії для підробки повідомлень: інформація про валютні операції, наприклад, часто шифрується за допомогою хеш-функцій; зловмисник, володіючи методом знаходження колізій цієї хеш-функції, може підмінити повідомлення підробним і тим самим вплинути на хід валютної операції.
Схожим чином можна використати колізії для підробки цифрового підпису і сертифіката.
Захист від використання колізій Редагувати
Існує кілька методів захисту від зламу, підробки паролів, підписів, сертифікатів, навіть якщо зловмиснику відомі методи побудови колізій для якої-небудь хеш-функції.
Одним з методів є метод «salt», який застосовується при збереженні UNIX-паролів — додавання деякої послідовності символів перед хешуванням. Іноді ця послідовність додається до отриманого хеша. Після такої процедури, підсумкові хеш-таблиці значно складніше аналізувати, а через те, що послідовність секретна, істотно підвищується складність побудови колізій — зловмиснику має бути відома послідовність «salt».
Іншим методом є конкатенація хешів, отриманих від двох різних хеш-функцій. При цьому, для того щоб підібрати колізії до хеш-функції , яка є конкатенацією хеш-функції и , необхідно знати методи побудови колізій для , і . Недоліком конкатенації є збільшення розміру хеша, що часто неприйнятно в реальних застосунках.
Методи пошуку колізій Редагувати
Одним з найбільш простих і універсальних методів пошуку колізій є атака «днів народження». За допомогою цієї атаки знаходження колізії для хеш-функції розрядності біт потрібно в середньому близько операцій. Через це n-бітова хеш-функція вважається криптостійкою, якщо обчислювальна складність знаходження колізій для неї близька до .
Література Редагувати
- Askitis, Nikolas; Zobel, Justin (2005). Cache-Conscious Collision Resolution in String Hash Tables. У Consens, M.; Navarro, G. International Symposium on String Processing and Information RetrievalString Processing and Information Retrieval SPIRE 2005. Lecture Notes in Computer Science 3772 (Berlin, Heidelberg: Springer Berlin Heidelberg): 91–102. ISBN 978-3-540-29740-6. doi:10.1007/11575832_11.
- 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. ISSN 0975-8887. doi:10.5120/17411-7990.
| Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. (червень 2023) |