Хеш-функції¶
Навіщо потрібні хеш-функції¶
Хеш-функції — один з найважливіших інструментів в інформатиці. Вони використовуються всюди: від перевірки завантажених файлів до захисту паролів і побудови ефективних структур даних. В цій лекції ми розберемося, що таке хеш-функція, які властивості вона має, і чому без неї не обходиться жодна сучасна система.
Почнемо з кількох практичних прикладів, щоб зрозуміти, які задачі вирішують хеш-функції.
Перевірка цілісності даних¶
Уявіть, що ви завантажили з інтернету файл розміром 2 гігабайти. Як переконатися, що файл завантажився без помилок? Порівнювати кожен байт з оригіналом — довго і потребує доступу до оригіналу. А якщо замість цього порахувати контрольну суму — наприклад, скласти значення всіх байтів файлу і отримати одне число? Тоді достатньо порівняти лише це число з тим, що опублікував автор файлу.
Це і є найпростіша ідея хеш-функції: перетворити дані довільного розміру у значення фіксованого розміру — відбиток (fingerprint). Якщо відбитки збігаються — дані, найімовірніше, однакові. Якщо ні — точно різні.
На практиці проста сума байтів — занадто примітивна: якщо два байти поміняються місцями, сума не зміниться, і помилку не буде виявлено. Тому використовують складніші хеш-функції (MD5, SHA-256), які реагують на будь-яку зміну даних. Але ідея залишається тією самою: великий файл → короткий відбиток → порівняння.
Зберігання паролів¶
Коли ви реєструєтесь на сайті, ваш пароль потрібно десь зберегти, щоб потім перевіряти при вході. Але зберігати пароль у відкритому вигляді — небезпечно: якщо зловмисник отримає доступ до бази даних, він дізнається паролі всіх користувачів.
Рішення: зберігати не сам пароль, а його хеш. При вході користувач вводить пароль, система обчислює хеш і порівнює зі збереженим. Якщо хеші збігаються — пароль правильний. При цьому навіть адміністратор бази не знає паролів користувачів — він бачить лише хеші, а хеш-функція необоротна: з хешу неможливо відновити пароль.
Цифрові підписи¶
Уявіть, що викладач надсилає студентам PDF з умовами іспиту. Як студент може переконатися, що файл дійсно від викладача, а не підроблений кимось? І що ніхто не змінив умови після відправки?
Для цього існує цифровий підпис. Аналогія: коли ви підписуєте паперовий документ — ваш підпис підтверджує, що саме ви його схвалили. Цифровий підпис працює так само, але для електронних документів.
Чому тут потрібна хеш-функція? Справа в тому, що алгоритми шифрування (на яких побудований цифровий підпис) працюють дуже повільно для великих обсягів даних. Шифрування одного байта може потребувати сотні математичних операцій. Зашифрувати весь документ розміром 10 мегабайтів — це мільярди операцій.
А тепер порівняйте: хеш-функція перетворює ці 10 мегабайтів у рядок довжиною 32 байти. Зашифрувати 32 байти — миттєва операція. Тому замість того, щоб шифрувати весь документ, автор:
- Обчислює хеш документа (10 МБ → 32 байти)
- Шифрує лише цей хеш своїм приватним ключем — це і є цифровий підпис
Одержувач перевіряє підпис: обчислює хеш документа самостійно, дешифровує підпис публічним ключем автора і порівнює два хеші. Якщо збігаються — документ справжній і не був змінений.
Fingerprint (відбиток) SSH-ключа¶
Коли ви вперше підключаєтесь до віддаленого сервера через SSH, термінал показує щось на зразок наведеного нижче повідомлення. Ви могли бачити подібний вивід, коли працювали з Git — він використовує SSH для передачі файлів на сервер і завжди перевіряє цілісність з'єднання та авторизацію користувача:
The authenticity of host 'example.com' can't be established.
ED25519 key fingerprint is SHA256:nThbg6kXUpJWGl7E1IGOCspRomTxdCARLviKw6E5SY8.
Are you sure you want to continue connecting (yes/no)?
SSH-ключ сервера — це довгий рядок із сотень символів. Порівнювати його вручну — нереально. Замість цього SSH обчислює хеш ключа і показує вам короткий відбиток (fingerprint). Ви можете зателефонувати адміністратору сервера, попросити його продиктувати відбиток, і порівняти — цього достатньо, щоб переконатися, що ви підключаєтесь до правильного сервера, а не до підробки.
Ефективні структури даних¶
Хеш-функції також дозволяють будувати структури даних, в яких пошук, вставка і видалення працюють в середньому за \(O(1)\) — тобто за сталий час, незалежно від кількості даних. Як саме це працює — ми розглянемо в наступній лекції.
Саме це і робить хеш-функція: перетворює дані довільного розміру у значення фіксованого розміру. Перш ніж дати строге означення, нам потрібно згадати кілька важливих математичних понять.
Функція як відображення¶
Означення¶
Означення функції
Функція \(f: A \to B\) — це правило, за яким кожному елементу множини \(A\) (область визначення) ставиться у відповідність рівно один елемент множини \(B\) (область значень).
Простими словами: функція — це "чорна скринька", яка приймає щось на вхід і видає результат. Для одного й того самого входу вона завжди видає однаковий результат.
Наприклад:
- \(f(x) = 2x\) — кожному числу ставить у відповідність його подвоєне значення
- \(f(x) = x^2\) — кожному числу ставить у відповідність його квадрат
- \(f(\text{"Іванов"}) = 5\) — студенту ставить у відповідність його оцінку
Оборотність функцій¶
Деякі функції є оборотними: знаючи результат, можна однозначно відновити вхід. Наприклад, для \(f(x) = 2x\): якщо \(f(x) = 10\), то \(x = 5\) — єдиний варіант.
Означення: оборотна (ін'єктивна) функція
Функція \(f: A \to B\) називається оборотною (або ін'єктивною), якщо для будь-яких \(x_1 \neq x_2\) з множини \(A\) виконується \(f(x_1) \neq f(x_2)\). Тобто різні входи завжди дають різні результати.
Але не всі функції оборотні. І це ключовий момент для розуміння хеш-функцій.
Необоротні функції¶
Приклад 1: квадрат числа¶
Якщо \(f(x) = 4\), то \(x = 2\) чи \(x = -2\)? Невідомо — обидва значення дають однаковий результат. Функція втрачає інформацію про знак.
Приклад 2: тангенс¶
Якщо \(f(x) = 0\), то \(x\) може бути \(0\), \(\pi\), \(2\pi\), \(-\pi\), \(3\pi\), \(\ldots\) — нескінченна кількість прообразів. З одного значення тангенса неможливо визначити, який саме кут був на вході.
Приклад 3: кількість дільників¶
Розглянемо:
- \(f(12) = 6\) (дільники: 1, 2, 3, 4, 6, 12)
- \(f(18) = 6\) (дільники: 1, 2, 3, 6, 9, 18)
- \(f(8) = 4\) (дільники: 1, 2, 4, 8)
- \(f(10) = 4\) (дільники: 1, 2, 5, 10)
Зовсім різні числа дають однаковий результат. Більше того, для будь-якого \(k\) існує нескінченно багато чисел, що мають рівно \(k\) дільників. Відновити вхід неможливо в принципі.
Строге означення¶
Означення: необоротна функція
Функція \(f: A \to B\) називається необоротною, якщо існує хоча б один елемент \(b \in B\), для якого рівняння \(f(x) = b\) має більше одного розв'язку (або не має розв'язків взагалі). Тобто знаючи значення \(f(x)\), неможливо однозначно визначити \(x\).
Всі три приклади вище — необоротні функції. Хеш-функція також є необоротною, і це одна з її ключових властивостей.
Чому це важливо
Хеш-функція — це яскравий приклад необоротної функції. Вона свідомо побудована так, щоб з результату (хешу) було неможливо відновити вхідні дані. Це фундаментально для безпеки: навіть знаючи хеш пароля, зловмисник не може обчислити сам пароль.
Властивість локальності¶
Означення¶
Перед тим як визначити хеш-функцію, введемо ще одне важливе поняття.
Розглянемо спочатку приклади. Функція \(f(x) = 2x\): якщо змінити \(x\) на \(0.01\), вихід зміниться на \(0.02\). Функція "плавна", передбачувана — невелика зміна входу дає невелику зміну виходу.
Ще приклад: \(f(x) = x^2\). При \(x = 100\) маємо \(f(100) = 10000\), а \(f(101) = 10201\) — різниця \(201\), пропорційна зміні входу. Знову: мала зміна аргументу — відносно мала зміна результату.
Функції, що поводяться так "гладко", мають спільну властивість. Дамо їй строге означення.
Означення: властивість локальності
Функція \(f\) має властивість локальності, якщо для будь-якого \(\varepsilon > 0\) існує таке \(\delta > 0\), що з \(|x_1 - x_2| < \delta\) випливає \(|f(x_1) - f(x_2)| < \varepsilon\).
Простими словами: якщо два входи близькі між собою, то і їхні виходи близькі.
Функції з властивістю локальності — це неперервні функції, графік яких можна намалювати, не відриваючи ручку від паперу. Більшість функцій, з якими ви працювали в математиці (\(\sin x\), \(x^2\), \(e^x\)), мають цю властивість.
Функція Діріхле: екстремальний приклад¶
Цікавий факт
Існує функція, яка повністю позбавлена локальності.
Функція Діріхле визначається так:
Чому вона не має локальності? Тому що в будь-якому, навіть найменшому околі будь-якої точки є і раціональні, і ірраціональні числа. Функція "стрибає" між 0 і 1 нескінченно часто — її неможливо намалювати. Будь-яка, навіть мікроскопічна зміна входу може повністю змінити вихід.
Локальність і хеш-функції: два різних світи¶
Тепер головне питання: чи повинна хеш-функція мати локальність? Відповідь залежить від того, для чого ми використовуємо хеш.
Криптографічні хеш-функції (для паролів, цифрових підписів, перевірки цілісності) — не повинні мати локальність. Це критична вимога безпеки. Уявіть: ваш пароль — password1, а хеш від нього — abc123. Якщо хеш-функція має локальність, то пароль password2 дасть щось близьке — наприклад, abc124. Зловмисник, знаючи хеш abc123, зможе здогадатися, що пароль схожий на щось, що дає abc12..., і перебрати варіанти значно швидше.
Тому криптографічні хеш-функції побудовані так, щоб мінімальна зміна входу повністю змінювала вихід:
Змінилася одна буква — хеш змінився повністю. В криптографії це називають лавинний ефект (avalanche effect): зміна одного біта входу змінює приблизно 50% бітів виходу.
Некриптографічні хеш-функції (для структур даних, пошуку дублікатів тощо) — можуть мати локальність. Для них головне — щоб значення розподілялися рівномірно по всіх можливих значеннях. Якщо сусідні числа дають сусідні хеші — це не проблема, поки результати розподілені більш-менш порівну. Ми побачимо це на конкретному прикладі нижче.
Це ключова різниця між двома типами хеш-функцій, і ми детальніше розглянемо її в кінці лекції.
Означення хеш-функції¶
Тепер ми готові дати строге означення.
Означення хеш-функції
Хеш-функція — це функція \(h: U \to \{0, 1, \ldots, m-1\}\), де:
- \(U\) — множина всіх можливих вхідних даних (може бути нескінченною)
- \(m\) — розмір множини можливих хеш-значень (фіксоване натуральне число)
що задовольняє такі властивості:
- Детермінованість — для одного входу завжди повертає однаковий результат
- Фіксований розмір виходу — незалежно від розміру входу, результат завжди з множини \(\{0, 1, \ldots, m-1\}\)
- Рівномірний розподіл — хеш-значення розподіляються якомога рівномірніше по всій множині \(\{0, \ldots, m-1\}\)
Для криптографічних хеш-функцій додається ще одна вимога:
- Відсутність локальності (лавинний ефект) — малі зміни входу мають повністю змінювати вихід
Прості хеш-функції для цілих чисел¶
Хеш через залишок від ділення¶
Найпростіша хеш-функція для цілих чисел:
де \(m\) — кількість можливих хеш-значень.
int hash_int(int x, int m) {
int h = x % m;
if (h < 0) h += m; // Handle negative numbers
return h;
}
Чому h < 0?
В C++ оператор % для від'ємних чисел може повернути від'ємний результат: -7 % 5 = -2. Для хеш-функції нам потрібне значення з \(\{0, \ldots, m-1\}\), тому додаємо \(m\).
Приклад обчислення¶
Нехай \(m = 7\):
| Ключ \(x\) | \(h(x) = x \bmod 7\) |
|---|---|
| 10 | 3 |
| 17 | 3 |
| 25 | 4 |
| 42 | 0 |
| 7 | 0 |
Зверніть увагу: ключі 10 і 17 дають однаковий хеш (3), і ключі 42 і 7 теж (0). Це колізії — ми розглянемо їх детальніше нижче.
Ця функція має локальність — і це нормально¶
Подивимось на послідовні числа:
| Ключ \(x\) | \(h(x) = x \bmod 7\) |
|---|---|
| 10 | 3 |
| 11 | 4 |
| 12 | 5 |
| 13 | 6 |
| 14 | 0 |
Сусідні числа дають сусідні хеші — функція має чітку локальність. Якби це був криптографічний хеш, це була б катастрофа: знаючи хеш одного числа, можна вгадати хеш сусіднього.
Але для багатьох практичних застосувань це прийнятно. Чому? Уявіть гардероб у театрі з 7 вішалками, пронумерованими від 0 до 6. Кожен глядач здає пальто на вішалку з номером = номер квитка \(\bmod 7\). Глядачі з квитками 10 і 11 повісять пальта на вішалки 3 і 4 — сусідні. Але це не проблема! Головне, щоб пальта розподілилися рівномірно по всіх вішалках, а не скупчилися на одній. Функція \(x \bmod 7\) якраз це забезпечує.
А от для паролів така функція не підійде: якщо зловмисник знає, що хеш пароля — 3, він знає, що пароль при діленні на 7 дає залишок 3. Це значно звужує перебір.
Вибір \(m\): чому це важливо¶
Хеш-функція \(h(x) = x \bmod m\) виглядає простою, але її якість сильно залежить від вибору \(m\). Головна вимога — рівномірний розподіл. Якби ключі були рівномірно випадковими числами, будь-який \(m\) давав би хороший результат. Але на практиці ключі рідко бувають випадковими.
Реальні дані мають структуру¶
Подивіться на типові ключі, з якими працюють програми:
- ID користувачів з автоінкрементом — послідовність з кроком 1 (
10001, 10002, 10003, ...) - Адреси в пам'яті на 64-бітних системах завжди кратні 8 (вимоги вирівнювання)
- Розміри буферів зазвичай кратні 1024 або 4096
- Мітки часу (timestamps) — числа з кроком 1 секунда або 60 секунд
- Штрих-коди, номери замовлень — часто ідуть з якимось фіксованим кроком
Спільне у всіх цих прикладах — ключі утворюють арифметичну прогресію: \(a, a+d, a+2d, a+3d, \ldots\) з якимось кроком \(d\).
Що стається, коли \(m\) і крок мають спільний дільник¶
Візьмемо реалістичний приклад: хешуємо парні числа (крок \(d = 2\)), а \(m\) обрали рівним 10:
| Ключ \(x\) | \(h(x) = x \bmod 10\) |
|---|---|
| 100 | 0 |
| 102 | 2 |
| 104 | 4 |
| 106 | 6 |
| 108 | 8 |
| 110 | 0 |
| 112 | 2 |
Хеші попадають лише в комірки \(\{0, 2, 4, 6, 8\}\) — половина можливих значень недосяжна в принципі, незалежно від того, скільки парних ключів ми розглянемо. Колізії стаються вдвічі частіше, ніж могли б.
Ще гірше, якщо крок кратний \(m\). Ключі 10, 20, 30, 40, ... при \(m = 10\) — усі хешуються в 0. Із 10 можливих значень реально використовується лише одне.
Формальне пояснення¶
Лема про арифметичну прогресію
Якщо ключі утворюють арифметичну прогресію \(x_i = a + i \cdot d\), то значення \(h(x_i) = (a + i d) \bmod m\) набуває рівно
різних значень.
Простими словами: чим більший спільний дільник між кроком \(d\) і параметром \(m\), тим менше значень набуватиме хеш. Якщо \(\gcd(d, m) = k\), то \(\dfrac{k-1}{k}\) частини діапазону залишаються недосяжними — і це не залежить від того, скільки ключів ми розглянемо.
Перевіримо на попередніх прикладах:
- \(d = 2\), \(m = 10\): \(\gcd(2, 10) = 2\) → використовується \(10 / 2 = 5\) комірок з 10 ✓
- \(d = 10\), \(m = 10\): \(\gcd(10, 10) = 10\) → використовується \(10 / 10 = 1\) комірка з 10 ✓
Чому просте число рятує¶
Нехай \(m = p\) — просте число. Тоді для будь-якого \(d\), що не кратне \(p\), маємо \(\gcd(d, p) = 1\). А це означає:
— хеш набуває всіх \(p\) можливих значень. Будь-яка арифметична прогресія з кроком, меншим за \(p\), розподіляється рівномірно по всьому діапазону.
Подивимось на той самий приклад (парні числа, крок \(d = 2\)), але з \(m = 11\):
| Ключ \(x\) | \(h(x) = x \bmod 11\) |
|---|---|
| 100 | 1 |
| 102 | 3 |
| 104 | 5 |
| 106 | 7 |
| 108 | 9 |
| 110 | 0 |
| 112 | 2 |
| 114 | 4 |
| 116 | 6 |
| 118 | 8 |
| 120 | 10 |
| 122 | 1 |
Всі 11 комірок заповнюються по черзі — ідеальний рівномірний розподіл. Просте число «не резонує» з жодним природним кроком у даних.
Інтуїція
Складене число \(m\) має дільники, за які «зачіпаються» патерни у ключах. У простого числа дільників немає (окрім 1 і самого себе), тому жоден регулярний патерн з ним не співпадає.
Окремий випадок: \(m = 2^k\)¶
Спокусливо обрати \(m\) як степінь двійки, бо \(x \bmod 2^k\) обчислюється через побітове AND:
Це найшвидша можлива операція взяття залишку — одна інструкція процесора. Але ціна така:
Старші біти повністю ігноруються. Розглянемо \(m = 16\) (беремо 4 молодших біти):
| Ключ \(x\) (hex) | \(h(x) = x \bmod 16\) |
|---|---|
0x10000005 |
5 |
0x20000005 |
5 |
0x30000005 |
5 |
0xFFFF0005 |
5 |
Числа можуть відрізнятися в мільярди разів, але якщо їхні молодші біти однакові — колізія гарантована.
Це особливо болюче для вказівників: на 64-бітних системах об'єкти вирівняні по 8 байтів, тобто молодші 3 біти адрес завжди нульові. Хеш-функція з \(m = 8\) дасть усім вказівникам значення 0.
Візуалізація різниці¶
Як розподіляються ключі з кроком 2 при різних значеннях \(m\) (X — значення, яке набуває хеш, . — недосяжне значення):
m = 10 (складене): X . X . X . X . X . ← 5 з 10 використано
m = 16 (степінь 2): X . X . X . X . X . X . X . X . X . ← 8 з 16 використано
m = 11 (просте): X X X X X X X X X X X ← 11 з 11 використано
Практична рекомендація¶
Практична рекомендація
Обирайте \(m\) як просте число, не близьке до степеня двійки. Наприклад:
- замість \(m = 1024\) — візьміть \(m = 1009\) або \(m = 1013\)
- замість \(m = 65536\) — візьміть \(m = 65521\) або \(m = 65539\)
- замість \(m = 10^6\) — візьміть \(m = 999983\)
Знайти найближче просте число легко: достатньо перевірити кілька чисел поспіль на простоту.
Хеш-функції для рядків¶
Наївний підхід: сума кодів символів¶
Найпростіша ідея — додати коди (ASCII-значення) всіх символів:
int hash_string_naive(const char* str, int m) {
int sum = 0;
for (int i = 0; str[i] != '\0'; ++i) {
sum += str[i];
}
int h = sum % m;
if (h < 0) h += m;
return h;
}
Проблема: рядки-анаграми дають однаковий хеш:
hash("abc") = (97 + 98 + 99) % m = 294 % m
hash("cba") = (99 + 98 + 97) % m = 294 % m
hash("bac") = (98 + 97 + 99) % m = 294 % m
Усі перестановки букв дають однаковий результат — це дуже погана хеш-функція.
Поліноміальний хеш¶
Щоб порядок символів впливав на хеш, помножимо кожен символ на степінь деякого числа \(p\):
де \(s_i\) — код \(i\)-го символу, \(p\) — основа (зазвичай просте число, наприклад 31 або 53).
Тепер порядок символів має значення: кожен символ множиться на різну степінь \(p\).
int hash_string_poly(const char* str, int m) {
long long h = 0;
long long p_pow = 1; // p^0 = 1
int p = 31; // Base (prime number)
for (int i = 0; str[i] != '\0'; ++i) {
h = (h + (str[i] - 'a' + 1) * p_pow) % m;
p_pow = (p_pow * p) % m;
}
return (int)h;
}
Приклад обчислення¶
Для рядка "abc" з \(p = 31\), \(m = 1000\):
Для "cba":
Анаграми "abc" і "cba" тепер мають різні хеші: 946 і 26.
Чому \(p = 31\)?
Число 31 — просте, що дає хороший розподіл. Крім того, множення на 31 легко оптимізується компілятором: \(31 \cdot x = 32 \cdot x - x = (x \ll 5) - x\). Це одна з причин, чому Java використовує саме 31 у своїй стандартній хеш-функції для рядків.
Хеші в Linux¶
Обчислення хешу файлу¶
В Linux можна обчислити хеш будь-якого файлу прямо в терміналі:
# MD5 (128 біт, 32 hex-символи)
md5sum myfile.txt
# d41d8cd98f00b204e9800998ecf8427e myfile.txt
# SHA-1 (160 біт, 40 hex-символів)
sha1sum myfile.txt
# da39a3ee5e6b4b0d3255bfef95601890afd80709 myfile.txt
# SHA-256 (256 біт, 64 hex-символи)
sha256sum myfile.txt
# e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 myfile.txt
Зверніть увагу на довжину: MD5 дає 32 символи, SHA-1 — 40, SHA-256 — 64. Чим довший хеш, тим менша ймовірність колізій.
Де зберігаються хеші паролів¶
В Linux паролі користувачів не зберігаються у відкритому вигляді. Замість цього зберігаються їх хеші у файлі /etc/shadow:
Формат запису: $алгоритм$сіль$хеш, де:
| Префікс | Алгоритм |
|---|---|
$1$ |
MD5 |
$5$ |
SHA-256 |
$6$ |
SHA-512 |
$y$ |
yescrypt (сучасний) |
Сіль (salt) — це випадковий рядок, який додається до пароля перед хешуванням. Завдяки цьому два користувачі з однаковим паролем матимуть різні хеші.
Коротка історія хеш-алгоритмів¶
Чому алгоритми змінюються
Історія хеш-функцій — це історія перегонів між криптографами і тими, хто намагається їх зламати.
MD5 (1991, Рональд Рівест):
- Розмір хешу: 128 біт
- Довгий час був стандартом
- 2004 рік: китайська криптографиня Ван Сяоюнь (Wang Xiaoyun) знайшла спосіб генерувати колізії за хвилини
- Сьогодні: не використовують для безпеки, але все ще використовують для перевірки цілісності (завантаження файлів)
SHA-1 (1995, NSA):
- Розмір хешу: 160 біт
- Замінив MD5 як стандарт безпеки
- 2017 рік: Google продемонстрував практичну колізію (проект SHAttered) — два різних PDF з однаковим SHA-1 хешем
- Сьогодні: застарілий, браузери не приймають SHA-1 сертифікати
SHA-256 (2001, NSA, сімейство SHA-2):
- Розмір хешу: 256 біт
- Поточний стандарт безпеки
- Використовується в Bitcoin, TLS, цифрових підписах
- Колізій не знайдено станом на сьогодні
Чому MD5 все ще використовується
Для перевірки цілісності (чи завантажився файл коректно) MD5 достатній — нам не потрібна стійкість до навмисних атак, лише виявлення випадкових помилок. А MD5 працює швидше за SHA-256. Тому на сайтах завантажень досі часто бачимо MD5 або SHA-1 контрольні суми.
Колізії¶
Означення¶
Означення колізії
Колізія — це ситуація, коли два різних входи дають однаковий хеш:
Ми вже бачили приклади колізій: при \(m = 7\) ключі 10 і 17 мають однаковий хеш 3. Але чи можна побудувати хеш-функцію без колізій?
Чому колізії неминучі¶
Відповідь: ні, якщо множина можливих входів більша за множину хеш-значень. Це прямий наслідок фундаментального математичного принципу.
Принцип Діріхле¶
Формулювання¶
Принцип Діріхле (Pigeonhole Principle)
Якщо \(n\) предметів розкласти в \(m\) комірок, і \(n > m\), то хоча б в одній комірці опиниться більше одного предмета.
Простими словами: якщо 10 голубів сідають у 9 клітинок, то хоча б в одній клітинці буде два голуби. Це здається очевидним, але наслідки для хеш-функцій — фундаментальні.
flowchart LR
subgraph "Ключі (n = 5)"
k1["10"]
k2["17"]
k3["25"]
k4["42"]
k5["7"]
end
subgraph "Хеш-значення (m = 4)"
h0["0"]
h1["1"]
h2["2"]
h3["3"]
end
k1 --> h3
k2 --> h3
k3 --> h2
k4 --> h0
k5 --> h05 ключів, 4 можливих хеш-значення → принаймні одна колізія гарантована.
Застосування до хеш-функцій¶
Розглянемо хеш-функцію для рядків. Множина всіх можливих рядків нескінченна, а множина хеш-значень \(\{0, 1, \ldots, m-1\}\) — скінченна (наприклад, \(m = 1000\)). За принципом Діріхле, для будь-якого \(m\) існують рядки з однаковим хешем.
Фундаментальний висновок
Колізії неможливо уникнути — це математичний факт. Тому завдання хеш-функції — не уникати колізій, а мінімізувати їх кількість через рівномірний розподіл.
Узагальнення принципу Діріхле¶
Принцип можна посилити з обох боків. Якщо \(n\) предметів розкласти в \(m\) комірок, то:
- хоча б в одній комірці буде не менше ніж \(\lceil n/m \rceil\) предметів;
- хоча б в одній комірці буде не більше ніж \(\lfloor n/m \rfloor\) предметів.
Обидва твердження випливають з того самого простого факту: якщо середнє значення по комірках дорівнює \(n/m\), то максимум не може бути меншим за середнє, а мінімум — більшим. Для хеш-функцій критичне саме перше твердження — воно дає нижню оцінку на кількість колізій у найбільш завантаженій комірці.
Наприклад: якщо 10 000 ключів хешуються в 1000 комірок, то хоча б одна комірка міститиме не менше \(\lceil 10000/1000 \rceil = 10\) ключів, і хоча б одна — не більше \(\lfloor 10000/1000 \rfloor = 10\) ключів. Тут обидва числа збіглись, бо ділення без залишку. Для 10 500 ключів у 1000 комірок нижня оцінка стане \(\lceil 10500/1000 \rceil = 11\), а верхня оцінка «найлегшої» — \(\lfloor 10500/1000 \rfloor = 10\).
Парадокс днів народження (Birthday Paradox)¶
Задача¶
Скільки людей потрібно зібрати в кімнаті, щоб ймовірність того, що хоча б у двох з них збігається день народження, була більшою за 50%?
Інтуїтивна відповідь: "мабуть, десь 180 — половина від 365". Правильна відповідь: лише 23 людини.
Чому так мало?¶
Ключове спостереження: ми шукаємо збіг не конкретної дати, а будь-якої пари. При 23 людях кількість можливих пар:
253 пари, кожна з яких може дати збіг — це вже багато.
Формула¶
Нехай хеш-функція ідеально рівномірна — тобто для кожного нового елемента всі \(m\) можливих значень однаково ймовірні. Розмістимо \(k\) елементів один за одним і порахуємо ймовірність, що жоден з них не зіткнеться з попередніми.
- 1-й елемент: отримує будь-яке з \(m\) значень. Колізії ще бути не може — ймовірність «немає колізії» дорівнює \(\dfrac{m}{m} = 1\).
- 2-й елемент: одне значення вже зайняте попереднім, вільних — \(m - 1\) з \(m\). Ймовірність уникнути колізії: \(\dfrac{m-1}{m}\).
- 3-й елемент: зайняті 2 значення, вільних — \(m - 2\). Ймовірність: \(\dfrac{m-2}{m}\).
- \(\ldots\)
- \(k\)-й елемент: зайняті \(k - 1\) значень, вільних — \(m - k + 1\). Ймовірність: \(\dfrac{m-k+1}{m}\).
Щоб колізій не було жодного разу, всі \(k\) кроків мають пройти без зіткнення. Ймовірність послідовності таких подій — це добуток ймовірностей кожного кроку (за умови, що попередні пройшли успішно):
Кожен наступний множник менший за попередній рівно на \(\dfrac{1}{m}\). Це не випадково: з кожним додаваним елементом у «зайнятих» стає на одне значення більше, а у «вільних» — на одне менше. Тому чисельник кожного разу зменшується на 1.
Ймовірність хоча б однієї колізії — це доповнення до одиниці:
Тепер знайдемо, при якому \(k\) ймовірність колізії сягає 50% — перемножувати \(k\) дробів напряму для великих значень незручно, треба щось простіше.
Почнемо з переписування кожного множника у трохи іншому вигляді:
Тож добуток виглядає так:
Прологарифмуємо обидві частини — логарифм добутку розпадається на суму логарифмів:
Тут стане в пригоді наближення для малих \(x\):
(його легко перевірити: наприклад, \(\ln(1 - 0{,}01) = -0{,}01005\ldots\), а \(\ln(1 - 0{,}001) = -0{,}001000\ldots\)). Застосовуючи його до кожного доданку, отримуємо:
У чисельнику — знайома сума арифметичної прогресії: \(0 + 1 + 2 + \ldots + (k-1) = \dfrac{k(k-1)}{2}\). При великих \(k\) значення \(k - 1\) майже не відрізняється від \(k\), тому \(k(k-1) \approx k^2\). Отримуємо:
Колізія стає ймовірною (\(P(\text{немає колізій}) < \tfrac{1}{2}\)) тоді, коли:
Тобто імовірність знайти колізію перевищує 50% тоді, коли кількість елементів \(k\) сягає приблизно \(\sqrt{m}\). У практичних оцінках так і пишуть: \(k \approx \sqrt{m}\) — це правильний порядок величини з точністю до сталого множника \(\approx 1{,}18\).
Для дня народження (\(m = 365\)): \(\sqrt{365} \approx 19\), а з поправкою — \(1{,}177 \cdot 19 \approx 22{,}5\). Звідси і знамениті «23 людини».
| \(m\) (кількість хеш-значень) | \(k\) для ~50% імовірності колізії |
|---|---|
| 365 (дні року) | ~23 |
| 1 000 | ~39 |
| 1 000 000 | ~1 177 |
| \(2^{128}\) (MD5) | \(\approx 2^{64}\) |
| \(2^{256}\) (SHA-256) | \(\approx 2^{128}\) |
Для допитливих: звідки взялося наближення \(\ln(1-x) \approx -x\)
Ця формула — приклад апроксимації, коли складну функцію замінюють простішою поблизу певної точки. У математичному аналізі існує потужний і елегантний інструмент — ряд Тейлора, — що систематично будує такі наближення для широкого класу функцій. З нього природно випливають відомі формули на кшталт \(\ln(1-x) \approx -x\), \(\sin x \approx x\), \(e^x \approx 1 + x\) для малих \(x\). Ряди Тейлора трапляються в найнеочікуваніших місцях — від фізики й комп'ютерної графіки до машинного навчання та фінансової математики. Якщо вам цікаво зазирнути глибше — час, присвячений їхньому вивченню, окупається багато разів.
Практичний висновок¶
Атака на основі парадоксу днів народження (birthday attack)
Парадокс днів народження пояснює, чому 128-бітний хеш (MD5) не такий надійний, як здається. Хоча \(2^{128}\) — астрономічне число, для знаходження колізії достатньо перебрати лише \(\approx 2^{64}\) варіантів — що цілком реалістично для сучасних комп'ютерів. Саме тому MD5 вважається зламаним для криптографічних цілей.
Для SHA-256 потрібно \(\approx 2^{128}\) спроб — це все ще далеко за межами можливостей будь-яких комп'ютерів.
Криптографічні vs некриптографічні хеш-функції¶
Не всі хеш-функції однакові. Залежно від призначення, до них висувають різні вимоги.
Некриптографічні хеш-функції¶
Призначення: структури даних для швидкого пошуку (розглянемо в наступній лекції), перевірка цілісності, виявлення дублікатів.
Вимоги:
- Швидкість обчислення
- Рівномірний розподіл
- Мінімум колізій
Приклади: поліноміальний хеш, FNV, MurmurHash, CityHash.
Безпека не є вимогою — ці хеші не призначені для захисту від зловмисників.
Криптографічні хеш-функції¶
Призначення: зберігання паролів, цифрові підписи, криптовалюти (Bitcoin та інші).
Вимоги (на додачу до попередніх):
| Властивість | Зміст | Складність атаки |
|---|---|---|
| Незворотність (preimage resistance) | Дано хеш \(h\). Знайти будь-який вхід \(x\), для якого \(hash(x) = h\) — неможливо. | \(O(m)\) |
| Стійкість до другого прообразу (second preimage resistance) | Дано фіксований вхід \(x_1\). Знайти інший \(x_2 \neq x_1\), що дає той самий хеш — неможливо. Атакувальник не обирає \(x_1\). | \(O(m)\) |
| Стійкість до колізій (collision resistance) | Знайти будь-яку пару \(x_1 \neq x_2\) з однаковим хешем — неможливо. Атакувальник вільно підбирає обидва входи. | \(O(\sqrt{m})\) |
| Лавинний ефект | Зміна одного біта входу змінює ~50% бітів виходу | — |
Три сценарії атаки
Розглянемо, що фіксоване, а що вільне для атакувальника у кожному з цих сценаріїв:
- Незворотність: дано лише хеш, треба відновити вхід.
- Другий прообраз: дано конкретний документ \(x_1\) (наприклад, легітимний договір), треба підробити інший документ \(x_2\) з таким самим хешем.
- Колізія: атакувальник вільно генерує документи парами («чесний» і «шахрайський») і шукає збіг хешів.
Свобода вибору обох входів робить колізійну атаку значно дешевшою: за парадоксом днів народження достатньо \(O(\sqrt{m})\) спроб замість \(O(m)\).
Як це ламає цифрові підписи. Може здатися, що для підробки підпису потрібен саме другий прообраз (дано підписаний документ — треба знайти інший з тим самим хешем, \(O(m)\) операцій). Але на практиці атака йде простішим шляхом:
- Зловмисник заздалегідь готує дві різні версії документа — «чесну» та шахрайську — підбираючи їх так, щоб їхні хеші збіглися. Це колізійна атака, вона коштує лише \(O(\sqrt{m})\).
- Просить жертву підписати «чесну» версію. Жертва обчислює хеш, шифрує його своїм приватним ключем — отримує підпис для хешу \(h\).
- Оскільки шахрайська версія має той самий хеш \(h\), цей самий підпис дійсний і для неї. Зловмисник поширює шахрайську версію як нібито підписану жертвою.
Суть у тому, що атакувальник сам контролює обидва документи до моменту підписання — а отже, йому достатньо звичайної колізії, а не другого прообразу. Саме тому MD5 вважається зламаним для підписів: теоретична межа \(\sqrt{m} = 2^{64}\) уже цілком досяжна, а завдяки відомим слабкостям самого алгоритму колізії MD5 на практиці знаходять узагалі за секунди. У той самий час \(O(2^{128})\) операцій для другого прообразу все ще недосяжні.
Як згенерувати саме «документ», а не випадковий набір байтів
На перший погляд атака здається неможливою: щоб два файли мали однаковий хеш, треба ж наперед знати це значення і підібрати під нього байти — а це задача знаходження прообразу, \(O(m)\).
Але колізійна атака влаштована інакше. Криптоаналіз ніколи не фіксує хеш наперед — він просто шукає будь-яку пару вхідних даних, хеші яких випадково збігаються. Яким саме буде це число, ніхто не контролює; важливо лише те, що для обох файлів воно однакове. Саме тому задача реалістична: достатньо \(O(\sqrt{m})\) спроб.
Залишається інженерний нюанс: знайдені «колізійні байти» — це, з погляду людини, бінарне сміття. Щоб отримати два осмислені документи з одним хешем, використовують один із двох трюків.
Двоголовий файл. Готують єдиний шаблон документа, всередині якого одразу два варіанти видимого тексту — «чесний» і «шахрайський» — та логіка рендерингу: «якщо службовий блок \(X = B_1\), показати перший, інакше — другий». Криптоаналіз підбирає \(B_1 \neq B_2\), при яких хеш цілого файлу збігається для обох значень. Виходять два файли, що відрізняються лише блоком \(X\), але при відкритті показують різні документи. Так у середині 2000-х демонстрували пару PostScript-контрактів з однаковим MD5: один виводив «заплатити 1 000 доларів», другий — «заплатити 1 000 000 доларів».
Chosen-prefix collision. Тонший і потужніший підхід: атакувальник бере два цілком різних готових документи — з будь-яким видимим текстом і форматуванням — і додає до кожного коротке «склеювальне сміття» у ділянки, які формат ігнорує (коментарі, метадані, EXIF-теги). Це сміття обчислюється так, щоб хеші двох документів збіглися. Жодних умовних перемикачів — два повноцінно різні файли з однаковим хешем. Саме цей тип атаки в 2012 році використав шкідник Flame для підробки цифрового сертифіката Microsoft.
Цифровий підпис: як це працює¶
Одне з найважливіших застосувань криптографічних хешів — цифровий підпис. Ідея:
Автор підписує:
flowchart LR
D1["Документ"] --> H1["hash(документ)\n= abc123..."]
H1 --> E1["Шифруємо хеш\nприватним ключем"]
E1 --> S1["Цифровий підпис"]Одержувач перевіряє:
flowchart LR
D2["Документ"] --> H2["hash(документ)\n= abc123..."]
S2["Цифровий підпис"] --> E2["Дешифруємо підпис\nпублічним ключем"]
H2 --> C["Порівнюємо хеші"]
E2 --> C
C --> R{"Збігаються?"}
R -->|Так| OK["Документ автентичний ✓"]
R -->|Ні| FAIL["Документ змінений ✗"]Чому хешують, а не шифрують весь документ? Бо документ може важити гігабайти, а хеш — завжди фіксованого розміру (32-64 байти). Шифрування хешу — миттєве.
Цікавий факт
Відбиток (fingerprint) SSH-ключа, який ми бачили на початку лекції — це саме хеш публічного ключа. Коли ви вперше підключаєтесь до сервера, SSH показує відбиток, щоб ви могли переконатися, що підключаєтесь до правильного сервера, а не до підробки.
Підсумок¶
Ключові поняття¶
| Поняття | Що запам'ятати |
|---|---|
| Функція | Відображення \(f: A \to B\) — правило, що кожному елементу \(A\) ставить у відповідність елемент \(B\) |
| Необоротна функція | З результату неможливо однозначно відновити вхід |
| Локальність | Малі зміни входу → малі зміни виходу. Криптографічні хеш-функції не мають мати цю властивість |
| Хеш-функція | \(h: U \to \{0, \ldots, m-1\}\) — детермінована, фіксований вихід, рівномірний розподіл |
| Колізія | Два різних входи з однаковим хешем — неминучі за принципом Діріхле |
| Принцип Діріхле | \(n\) предметів у \(m\) комірок, \(n > m\) → є комірка з \(\geq 2\) предметами |
| Парадокс днів народження | Колізія ймовірна при \(\approx \sqrt{m}\) елементах — значно менше, ніж \(m\) |
| Лавинний ефект | Зміна 1 біта входу → зміна ~50% бітів виходу (вимога криптографічних хешів) |
Попередня: Сортування | Задачі: Хеш-функції