Колізія хеш-функції
Колізія хеш-функції— два різні вхідні блоки даних x і y для хеш-функції H таких, що H(x) = H(y).
Колізії існують для більшості хеш-функцій, але для «хороших» хеш-функцій частота їх виникнення близька до теоретичного мінімуму. У деяких окремих випадках, коли безліч різних вхідних даних звичайно, можна задати ін'єктивну хеш-функцію, що за визначенням не має колізій. Однак для хеш-функцій, що приймають вхід змінної довжини і повертають хеш постійної довжини (таких як MD5), колізії зобов'язані існувати, оскільки хоча б для одного значення хеш-функції відповідне йому безліч вхідних даних (повний прообраз) буде нескінченно - і будь-які два набори даних із цієї множини утворюють колізію.
Зміст
Розглянемо як приклад хеш-функцію H ( x ) = x mod 19 >19> , Визначену на безлічі цілих чисел. Її область значень складається з 19 елементів (кільця відрахувань за модулем 19), а область визначення - нескінченна. Оскільки безліч прообразів свідомо більше безлічі значень, колізії повинні існувати.
Побудуємо колізію для цієї хеш-функції для вхідного значення 38, хеш-сума якого дорівнює нулю. Так як функція H (x) - періодична з періодом 19, то для будь-якого вхідного значенняy, значенняy+ 19 матиме ту ж хеш-суму, що іy. Зокрема, для вхідного значення 38 тієї ж хеш-сумою будуть володіти вхідні значення 57, 76, і т. д. Таким чином, пари вхідних значень (38,57), (38,76) утворюють колізії хеш-функції H ( x ).
Так як криптографічні хеш-функції використовуються для підтвердження незмінності вихідної інформації, можливість швидкого відшукання колізії для них зазвичай рівнозначна дискредитації.Наприклад, якщо хеш-функція використовується для створення цифрового підпису, то вміння знаходити для неї колізії фактично рівносильне вмінню підробляти цифровий підпис. Тому мірою криптостійкості хеш-функції вважається обчислювальна складність знаходження колізії. В ідеалі не повинно існувати способу відшукання колізій швидше, ніж повний перебір. Якщо для деякої хеш-функції знаходиться спосіб отримання колізій істотно швидший, ніж повний перебір, то ця хеш-функція перестає вважатися криптостійкою і використовуватись для передачі та зберігання секретної інформації. Теоретичні та практичні питання пошуку та використання колізій щорічно обговорюються в рамках міжнародних конференцій (таких як CRYPTO або ASIACRYPT), на великій кількості ресурсів Інтернету, а також у багатьох публікаціях.
Властивості криптографічних хеш-функцій
Для того, щоб хеш-функціяHвважалася криптографічно стійкою, вона повинна задовольняти три основні вимоги, на яких заснована більшість застосувань хеш-функцій у криптографії:
Використання колізій для злому
Як приклад можна розглянути просту процедуру автентифікації користувача:
- при реєстрації в системі користувач вводить свій пароль, до якого застосовується деяка хеш-функція, значення якої записується до бази даних;
- при кожному введенні пароля, до нього застосовується та ж хеш-функція, а результат порівнюється з тим, що записаний у БД.
При такому підході, навіть якщо зловмисник отримає доступ до бази даних, він не зможе відновити вихідні паролі користувачів (за умови незворотності хеш-функції, що використовується). Однак, якщо зловмисник вміє знаходити колізії для хеш-функції, що використовується, йому нескладе труднощів знайти підроблений пароль, який матиме ту ж хеш-суму, що і пароль користувача.
Можна використовувати колізії для підробки повідомлень: інформація про валютні операції, наприклад, часто шифрується за допомогою хеш-функцій; зловмисник, маючи метод знаходження колізій цієї хеш-функції, може замінити повідомлення підробленим і тим самим вплинути на хід валютної операції.
Так само можна використовувати колізії для підробки цифрових підписів та сертифікатів.
Захист від використання колізій
Існує ряд методів захисту від злому, захисту від підробки паролів, підписів та сертифікатів, навіть якщо зловмиснику відомі методи побудови колізій для будь-якої хеш-функції.
Одним з методів є додавання «солі», тобто додавання деякої послідовності символів до даних, що хешуються, застосовується, наприклад, при зберіганні UNIX-паролей. При цьому та ж «сіль» додається також і до хешу, що отримується, що істотно підвищує складність одночасної побудови колізій першого роду догрупіпаролів, так як кожен з них повинен починатися зі свого власного значення «солі». Однак, "сіль" не ускладнює атаку на кожен пароль окремо.
Методи пошуку колізій
Крім того, існує атака подовженням повідомлення, яка для відомого значення H ( x ) дозволяє обчислити H ( x ‖ y ) = H ( H ( x ) ‖ y ) , де ‖ позначає конкатенацію. Атака розширення для деяких хеш-функцій працює навіть при забезпеченністійкості до колізій першого роду,стійкості до колізій другого роду, а також властивостінезворотності. Мається на увазі, що немає необхідності знати X, а достатньо знати лише його хеш. Таким чином можна, наприклад, дописувати додаткову інформацію дочужого повідомлення. Для запобігання цій атакі використовують різні методи: додають додатковий раунд при хешуванні, відмінний від попередніх; застосовують багаторазове хешування; або використовують комбінацію попередніх двох методів.
Більшість сучасних хеш-функцій мають однакову структуру, засновану на розбиття вхідного тексту на блоки і наступному ітераційному процесі, в якому на кожній ітерації використовується деяка функція G (x, y), деx— черговий блок вхідного тексту , аy- результат попередньої операції. Однак така схема недосконала, оскільки, знаючи функцію G можна проводити аналіз даних у проміжках між ітераціями, що полегшує пошук колізій.
Часто знаходження колізій хеш-функцій передує знаходження їїпсевдоколізій, тобто двох різних значень початкового буфера, які для одного і того ж повідомлення дають рівні значення хеш-функції.
Колізії хеш-функцій MD4 та MD5
У 1996 році Ганс Доббертін знайшов псевдоколізії в MD5, використовуючи певні вектори, що ініціалізують вектори, відмінні від стандартних. Виявилося, що можна для відомого повідомлення побудувати друге, таке, що воно матиме такий самий хеш, як вихідне. З погляду математики це, що MD5(IV,L1) = MD5(IV,L2) , де IV — початкове значення буфера, а L1 і L2 — різні повідомлення.
У 2004 році китайські дослідники Ван Сяоюнь (Wang Xiaoyun), Фен Денго (Feng Dengguo), Лай Сюецзя (Lai Xuejia) та Юй Хунбо (Yu Hongbo) оголосили про виявлену ними вразливість в алгоритмі, що дозволяє за невеликий час (1 година) p690 (англ.) українськ.) знаходити колізії.
Колізії хеш-функції SHA-1
Крістоф де Каньєр та Крістіан Рехберг пізніше представили вдосконалену версію атаки наSHA-1, за що були удостоєні нагороди за найкращу статтю на конференції ASIACRYPT 2006. Ними була представлена двоблокова колізія на 64-раундовий алгоритм з обчислювальною складністю близько 235 операцій.
Зважаючи на те, що теоретичні атаки на SHA-1 виявилися успішними, NIST планує повністю відмовитися від використання SHA-1 у цифрових підписах.
Колізії інших хеш-функцій
Для другої модифікації хеш-функції WHIRLPOOL, яка називається Whirlpool-T, на 2009 рік не запропоновано алгоритмів пошуку колізій або псевдоколізій; Суттєвим обмеженням для їх знаходження є складність самої функції та велика довжина (512 біт) вихідного ключа.
Хеш-функція ГОСТ Р 34.10-2001 по криптостойкости мало відрізняється від ГОСТ Р 34.10-94, знаходження колізій для якої зводиться до обчислення дискретного логарифму групи точок еліптичної кривої з імовірно експоненційною складністю. Наприклад, для 256-бітових параметрів дискретне логарифмування за допомогою ρ-метода або λ-метода Полларда вимагатиме виконання близько 10 30 ^> операцій.
Колізії ускладнюють використання хеш-таблиць, оскільки порушують однозначність відповідності між хеш-кодами та даними. Тим не менш, існують спеціальні методики для подолання складнощів, що виникають: