Перегляд вихідного коду сторінки Колізія геш-функції

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

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

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

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

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

=== Властивості криптографічних хеш-функцій ===
{{main|криптографічна хеш-функція}}
Для того, щоб хеш-функція ''H'' вважалась криптографічно стійкою, вона має задовольняти трьом основним вимогам, на яких ґрунтуються більшість застосувань хеш-функцій в криптографії:
* ''Незворотність'': для заданого значення хеш-функції ''m'' має бути практично неможливо знайти блок даних <math>X</math>, для якого <math>H(X)=m</math>.
* Стійкість до ''колізій першого роду'': для заданого повідомлення ''M'' має бути практично неможливо підібрати друге повідомлення ''N'', для якого <math>H(N)=H(M)</math>.
* Стійкість до ''колізій другого роду'': має бути практично неможливо підібрати пару повідомлень <math>~(M, M')</math>, які мають однаковий хеш.

=== Використання колізій для зламу ===
Як приклад можна розглянути процедуру [[Автентифікація|автентифікації]] користувача:
* при реєстрації в системі користувач вводить свій пароль, до якого застосовується деяка хеш-функція, значення якої записується в [[База даних|базу даних]];
* при кожному введені паролю, до нього застосовується та сама хеш-функція, а результат порівнюється з тим, що записаний в БД.
При такому підході, навіть якщо зловмисник отримає доступ до БД, він не зможе відновити паролі користувачів (при умові незворотності хеш-функції). Однак, якщо зловмисник вміє знаходити колізії для цієї хеш-функції, він зможе знайти підробний пароль, який буде мате ту саму [[хеш-сума|хеш-суму]], що і пароль користувача.

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

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

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

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

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

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


== Література ==
* {{cite conference |conference=International Symposium on String Processing and Information Retrieval |last1=Askitis|first1=Nikolas |last2=Zobel |first2=Justin |title=Cache-Conscious Collision Resolution in String Hash Tables |date=2005 |work=String Processing and Information Retrieval SPIRE 2005 |pages=91–102 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |series=Lecture Notes in Computer Science |volume=3772 |doi=10.1007/11575832_11| isbn=978-3-540-29740-6 |editor1-last=Consens |editor1-first=M. |editor2-last=Navarro |editor2-first=G.}}
* {{Cite journal|last1=Nimbe|first1=Peter|last2=Ofori Frimpong|first2=Samuel |last3=Opoku |first3=Michael |date=2014-08-20 |title=An Efficient Strategy for Collision Resolution in Hash Tables|url=http://dx.doi.org/10.5120/17411-7990 |journal=International Journal of Computer Applications |volume=99|issue=10|pages=35–41|doi=10.5120/17411-7990 |bibcode=2014IJCA...99j..35N|issn=0975-8887|doi-access=free}}

{{Мало джерел|дата=червень 2023}}

{{Геш-функції та коди аутентифікації повідомлення}}
[[Категорія:Криптографічні атаки]]
[[Категорія:Хешування]]