Довідка та теорія
Криптографічний геш відображає будь-який вхід на вихід фіксованої довжини, що поводиться як випадковий відбиток. Дві властивості роблять його корисним: лавинний ефект і стійкість до колізій.
Лавинний ефект
Невелика зміна входу — навіть один біт — має перевернути
приблизно половину бітів виходу. Виходи для схожих
входів виглядають абсолютно непов'язаними, тож не можна
відновити вхід або підлаштувати його під цільовий геш.
Межа днів народження
Для b-бітного гешу є B = 2ᵇ можливих
виходів. Колізія (два входи з однаковим гешем) стає ймовірною
набагато раніше за B — приблизно після √B вибірок.
Імовірність приблизно 1 − e^(−n²⁄2B) для n
вибірок.
Чому √B, а не B
Кожна нова вибірка може зіткнутися з кожною попередньою, тож
кількість пар зростає як n². Саме це квадратичне
зростання пояснює, чому в кімнаті лише з 23 людей імовірно
збігаються дні народження, і чому 256-бітний геш потребує ~2¹²⁸
роботи для злому грубою колізією — усе одно астрономічно важко.
Про цю симуляцію
Заради швидкості геш тут — мала детермінована функція змішування (FNV-1a плюс xorshift), а не SHA-256. Вона все одно демонструє лавинний ефект і межу днів народження, що є властивостями будь-якого доброго гешу.
Поширені запитання
Що таке криптографічна геш-функція?
Це функція, що відображає будь-який вхід на вихід фіксованої довжини, який поводиться як випадковий відбиток. Однаковий вхід завжди дає однаковий вихід, але вихід не розкриває нічого корисного про вхід.
Що таке лавинний ефект?
Лавинний ефект означає, що крихітна зміна входу — навіть один біт — перевертає приблизно половину бітів виходу. Це робить так, що схожі входи дають абсолютно непов'язані геші.
Що таке геш-колізія?
Колізія — це коли два різні входи дають однаковий вихід гешу. Добрий геш робить пошук такої пари обчислювально неможливим.
Що таке парадокс днів народження у гешуванні?
Це несподіваний результат: колізії стають ймовірними вже після приблизно квадратного кореня з кількості можливих виходів, набагато раніше, ніж підказує інтуїція.
Чому колізії ймовірніші, ніж очікувалося?
Бо кожна нова вибірка може зіткнутися з кожною попередньою, тож кількість пар зростає квадратично. Тому шанс будь-якої колізії зростає набагато швидше, ніж шанс влучити в одне конкретне значення.
Скільки вибірок спричиняє ймовірну колізію?
Для b-бітного гешу з B = 2 у степені b виходів колізія стає ймовірною приблизно після квадратного кореня з B вибірок. Імовірність приблизно дорівнює 1 мінус e у степені мінус n у квадраті поділити на 2B.
Чому має змінюватися близько половини бітів?
Якби кожен біт виходу був незалежною чесною монетою, перевертання будь-якого входу змінювало б кожен біт виходу з імовірністю одна друга, тож у середньому перевертається половина. Це ідеал, який наслідує стійкий геш.
Чи є геш у цій симуляції справжнім SHA-256?
Ні. Заради швидкості він використовує малу детерміновану функцію змішування FNV-1a плюс xorshift. Вона все одно демонструє лавинний ефект і межу днів народження, що є властивостями будь-якого доброго гешу.
Навіщо вихід фіксованої довжини?
Дайджест фіксованої довжини дозволяє порівнювати, зберігати й індексувати дані будь-якого розміру у сталому просторі; саме це робить підписи, перевірки цілісності та докази ефективними.
Наскільки великим має бути геш для стійкості до колізій?
Через межу днів народження геш має містити приблизно вдвічі більше бітів, ніж потрібний рівень безпеки. 256-бітний геш дає близько 128 бітів стійкості до колізій.