Криптографічна хеш-функція — це хеш-функція, яка є алгоритмом, що приймає довільний блок даних і повертає рядок встановленого розміру, (криптографічне) хеш-значення, таке що (випадкові або навмисні) зміни даних (з дуже високою ймовірністю) змінять хеш-значення. Дані до кодування часто звуть «повідомлення», а хеш-значення іноді називають дайджест повідомлення () або просто дайджест, дослівно «стислий виклад».
Ідеальна криптографічна хеш-функція має чотири основні властивості: легкість обчислення хеш-значення для будь-якого повідомлення нездійсненно утворити повідомлення для заданого хеш-значення нездійсненно змінити повідомлення без зміни хеша (лавиновий ефект) нездійсненно знайти два різних повідомлення з тим самим хешем
Криптографічні хеш-функції часто застосовуються в інформаційній безпеці, особливо в цифровому підписі, коді автентифікації повідомлення (MAC) та інших формах автентифікації. Їх також можна використати як звичайну хеш-функцію, для індексування даних в хеш-таблиці, для виявлення повторення даних або унікального ототожнювання файлів і як контрольну суму для виявлення пошкодження даних. Насправді, в розрізі інформаційної безпеки, криптографічні хеш-значення іноді називають (цифровими) відбитками пальців, контрольними сумами або просто хеш-значеннями,хоча всі ці терміни означають функції швидше з різними властивостями і цілями.
Властивості Більшість криптографічних хеш-функцій спроектовано так, щоб на вхід подавався рядок довільної довжини, а на виході ми отримували хеш-значення встановленої довжини.
Криптографічна хеш-функція повинна витримувати всі відомі типи криптографічних атак. Щонайменше, вона повинна мати наступні властивості:
Першовзорова стійкість для певного хешу має бути складно знайти повідомлення , таке що . Ця концепція стосується односторонньої функції. Функції, що не відповідають цій властивості вразливі до атак знаходження першовзору. Друга першовзорова стійкість Для певного входу має бути складно знайти інший вхід — де , такий що . Цю властивість іноді називають слабка колізійна стійкість (), і функцій, що не мають цієї властивості вразливі до атак знаходження першовзору другого роду. Колізійна стійкість Повинно бути складно знайти два різних повідомлення і , таких що . Така двійка зветься криптографічна хеш-колізія. Цю властивість іноді називають сильна колізійна стійкість (). Воно вимагає щонайменше вдвічі довшого хеш-значення ніж потрібно для першовзорової стійкості, інакше колізії можна знайти за допомогою атаки «днів народження».
Ці властивості мають на увазі, що зловмисник не може змінити вхідні дані без зміни дайджесту. Отже,якщо два рядки мають однаковий дайджест можна бути впевненим, що й самі вони такі.
Функції, що відповідають цим вимогам все ще можуть мати небажані властивості. Наразі популярні криптографічні хеш-функції вразливі до атак через довжинне доповнення (): знаючи і , але не знаючи , через вибір відповідного нападник може обчислити де позначає конкатенацію. Цю властивість можна використати, щоб розбити наївну схему автентифікацію побудовану на хеш-функції. HMAC обходить цю проблему.
В ідеалі, користувач може забажати сильніших вимог. Унеможливити для супротивника знайти два повідомлення з істотно схожими дайджестами; або виявити буді-яку корисну інформацію про дані, маючи лише дайджест. Отже, криптографічна хеш-функція наскільки можливо подібно до випадкової функції, залишаючись детерміністичною і ефективно обчислювальною.
Алгоритми контрольних сум, такі як CRC32 та інші циклічні надлишкові перевірки, спроектовані із дотриманням набагато слабших вимог, і зазвичай непридатні для використання як криптографічні хеш-функції. Наприклад, CRC використовували для цілісності повідомлень в WEP стандарті шифрування, але була легко віднайдена атака, що використовувала лінійність контрольної суми.
Ступінь складності У криптографічній практиці, складність зазвичай значить майже певно поза досяжністю будь-якого супротивника, який не повинен мати змогу зламати систему впродовж часу коли безпека система вважається потрібною. Внаслідок цього значення терміна залежить від застосування, бо зусилля, що зловмисник може затратити на задачу зазвичай пропорційне його очікуваній вигоді. Однак, через те, що необхідні зусилля ростуть дуже швидко з довжиною дайджесту, навіть покращення потужності обчислення в тисячі разів можна знешкодити додаванням кількох десятків бітів наприкінці.
У деяких теоретичних аналізах складність має особливе математичне значення, таке як нерозв'язний за асимптотичний поліноміальний час. Такі інтерпретації складності важливі у вивчанні доказово безпечних криптографічних хеш-функцій, але зазвичай не мають сильного зв'язку з практичною безпекою. Наприклад, алгоритм експоненці́йного часу іноді може бути досить швидким для здійсненної атаки. І навпаки, алгоритм поліноміального часу (наприклад, такий що вимагає n20 кроків для ключа в n цифр) може бути занадто повільним для практичного використання.
Приклад використання Покажемо можливе використання криптографічної хеш-функції: Аліса подає складну математичну проблему Бобові, і заявляє, що вона розв'язала її. Боб хотів би розв'язати її самостійно, але також хоче впевнитись що Аліса не блефує. Отже Аліса записує свій розв'язок, додає випадкове криптографічне число. Обчислює хеш-значення і передає його Бобу (тоді як розв'язок і випадкове число залишаються в секреті). Тоді, за кілька днів, Боб приходить зі своїм розв'язком, і Аліса може довести, що вона мала розв'язок раніше відкриваючи випадкове число Бобові. (Це приклад простої схеми зобов'язання).
Застосування Перевірка цілісності файлів або повідомлень
Важливим застосуванням безпечних хешів є перевірка цілісності повідомлень. Визначення чи були внесені якісь зміни в повідомлення (або файл), наприклад, можна здійснити порівнянням дайджестів до і після передачі (або іншої події).
Пов'язаним застосуванням є перевірка паролів. Зазвичай паролі не зберігаються відкритим текстом, а зберігаються їх хеш-значення. Для автентифікації користувача, пароль наданий користувачем хешується і порівнюється зі збереженим хешем. Це також значить, що первинний пароль неможливо відновити, і при втраті його необхідно замінити новим.
Ідентифікатор файлу або даних
Геш-значення також може слугувати як спосіб надійного ототожнення файлів; декілька систем керування версіями, включно з Git, Mercurial і , використовують різнотипного вмісту для унікального ототожнення. Геші використовують для ідентифікації файлів в peer-to-peer мережах спільного використання файлів. Наприклад, , варіант хеша MD4 поєднаний із розміром файлу, забезпечує достатню інформацію для знаходження джерела файлу, завантаження файлу і перевірки його вмісту. Інший приклад — це magnet-посилання. Такі файлові хеші часто використовують як кореневі хеші або .
Одне з головних застосувань хеш-функцій — це можливість швидкого пошуку даних в хеш-таблиці. Будучи хеш-функцією певного типу, криптографічна хеш-функція поводиться добре і тут також.
Однак, порівняно зі стандартною хеш-функцією, криптографічна хеш-функції тяжіють до більшої обчислювальної складності. Через це, їх більше використовують у випадках, де користувачу необхідно захистити себе від можливої підробки зловмисником.
Псевдовипадкова генерація й утворення ключів
Геш-функції також можна використати, як породжувач псевдовипадкових бітів або для виведення нових ключів чи паролів з одного секретного ключа або пароля.
Геш-функції засновані на блочних шифрах Існує декілька способів використання блочних шифрів для побудови криптографічних хеш-функцій, особливо односторонньої функції стискання.
Методи нагадують режими операцій блочних шифрів зазвичай використовні для шифрування. Всі добре відомі хеш-функції, включно з MD4, MD5, SHA-1 і SHA-2 побудовані зі складових подібних до блочних шифрів спроектованих для них, із гарантією, що отримана функція не бієктивна. Серед фіналістів змагання хеш-функцій від NIST (SHA-3) присутні хеш-функції зі складовими подібними до блочних шифрів (наприклад, Skein, BLAKE) та функції на основі інших дизайнів (Наприклад, , Keccak).
Стандартний блочний шифр такий як AES можна використати замість цих спеціальних блочних шифрів; це може бути корисним коли вбудована система має забезпечувати шифрування і хешування з мінімальним за розміром кодом або розміром плати. Однак, такий підхід відбувається на дієвості і безпеці. Шифри в хеш-функціях створені для хешування: вони використовують великі ключі і блоки, можуть дієво змінювати ключ щоблока, і розроблені і перевірені на стійкість до атак з пов'язаними ключами. Шифри загального призначення мають різні цілі. Зокрема, розміри ключа і блоку в AES роблять нетривіальним використання його для утворення довгих хеш-значень; шифрування з AES стає менш дієвим коли ключ змінюється щоблока; і атака з пов'язаними ключами робить його менш безпечним для використання в хеш-функціях ніж для шифрування.
Будова Меркла-Демґарда
Геш-функція повинна бути в змозі перевести повідомлення довільної довжини в вихід встановленої довжини. Цього можна досягти через розбиття даних на вході в ряд блоків однакової довжини, і опрацювання їх послідовно із використанням односторонньої функції стискання. Функція стискання може бути розроблена для хешування або утворена з блочного шифру. Геш-функція побудована за будовою Меркла-Демґарда є настільки колізійно стійкою наскільки така її функція стискання; Будь-яку колізію хеш-функції в цілому можна прослідити до колізії в функції стискання.
Останній оброблений блок також повинен бути однозначно довжинно-доповненим; це критично для безпеки побудови. Такий підхід зветься — будова Меркла-Демґарда. Найширше використовні хеш-функції, включно з SHA-1 і MD5, мають такий вигляд.
Будова має деякі властиві вади, включно з атаками через довжинне доповнення () і створити-і-вставити (), також не може використати переваги паралельного обчислення. Тому, багато учасників змагання хеш-функцій від NIST спроектовані на інших засадах.
Використання в побудові інших криптографічних примітивів Геш-функції можна використати для будови інших криптографічних примітивів. Щоб отримані примітиви були криптографічно безпечними, треба обережно підходити до будови, щоб вислід був правильним.
MAC (Також відомі як хеш-функції з ключем) часто будують з хеш-функцій. HMAC є таким прикладом.
Так само як і блочні шифри можливо використовувати для будови хеш-функцій, хеш-функції можливо використовувати для побудови шифрів. Будови Luby-Rackoff із використанням хеш-функцій можуть бути доказово безпечними, якщо підлегла функція безпечна. Також багато хеш-функцій (включно з SHA-1 і SHA-2) побудовані із використанням спеціально розроблених блочних шифрів в будові Дейвіса-Меєра () або іншій. Див. , BEAR і LION.
Генератор псевдовипадкових чисел можна побудувати із використанням хеш-функції. Це робиться поєднанням (секретного) випадкового зерна з лічильником і наступним хешуванням.
Деякі функції, такі як Skein, Keccak і видають довільної довжини потік і їх можна використати як потоковий шифр, хоча потоковий шифр також можна побудувати і з хеш-функції з дайджестом встановленого розміру. Часто це роблять спочатку будуючи криптографічно безпечний генератор псевдовипадкових чисел і тоді використовуючи цей потік як ключ. Потоковий шифр SEAL, що використовує SHA-1 для побудови внутрішніх таблиць, які потім використовуються в генераторі ключа. Не надається гарантії, що SEAL так само сильний або слабкий як SHA-1.
Конкатенація криптографічних хеш-функцій Зчеплюючи виходи кількох хеш-функцій ми отримуємо стійкість до колізій настільки високу як у найсильнішого з використаних алгоритмів. Наприклад, старіші версії TLS/SSL використовують об'єднані суми MD5 і SHA-1; це гарантувало, що метод віднайденя колізій в одній з цих функцій не дозволить підробити трафік захищений обома.