Криптографічні функції хешування: ефект лавини, зіткнення та межа дня народження

Що криптографічний хеш обіцяє

Криптографічна хеш-функція приймає вхідні дані будь-якої довжини та генерує фіксований розмір виводу – 256 біт для SHA-256 – і повинна задовольняти три властивості, щоб вважатися безпечною: стійкість до preimage (за заданим хешем неможливо знайти будь-який вхідний запис, що його генерує), стійкість до другого preimage (за заданим вхідному запису неможливо знайти інший вхідний запис з тим самим хешем) та стійкість до зіткнень (неможливо знайти два різних вхідних записи з однаковим хешем, що за теоремою про народження строго складніше, ніж стійкість до другого preimage). Жодна з цих властивостей не є математично доведеною неможливістю зламати – це емпіричні твердження, які витримують стікання, поки ніхто не опублікує атаки швидше, ніж грубий пошук.

Ефект лавин

Добра функція хешування демонструє ефект лавини: перемикання одного біта вхідних даних повинно змінювати приблизно половину вихідних бітів, таким чином, що це виглядає статистично невідрізним від кидання нової монети для кожного вихідного біта. Це те, що гарантує внутрішній дизайн SHA-256 — 64 раунди бітових обертань, XOR, модульних доданків та нелінійних функцій вибору/більшістю на стані 256 біт. Немає видимого зв’язку між вхідними та вихідними даними; хеш для "hello" і хеш для "Hello" не мають жодної змістовної структури, незважаючи на те, що відрізняються лише одним бітом у вхідних даних.

SHA-256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e... SHA-256("Hello") = 185f8db32271fe25f561a6fc938b2e26... // один біт перемикається у вхідних даних -> ~50% вихідних бітів відрізняються, // без помітного шаблону, що пов’язує два хеші Це пояснює, чому хеші використовуються для перевірки цілісності та чому вони роблять жахливу структуру з локальної залежності — ви не можете використовувати хеш для пошуку "подібних" вхідних даних так, як це можна було б із, наприклад, пізнавального хешу зображень, оскільки поведінка лавини навмисно руйнує будь-який зв’язок між схожістю вхідних даних і схожістю вихідних даних.

SHA-256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e...
SHA-256("Hello") = 185f8db32271fe25f561a6fc938b2e26...
// one bit flipped in the input -> ~50% of output bits differ,
// with no discernible pattern connecting the two digests

Звичайне обмеження дня народжень: зіткнення відбуваються ближче, ніж здається на перший погляд

Для хешу з n-бітовим виходом, середнє число спроб знайти конкретний преобразник становить приблизно 2ⁿ. Однак, пошук будь-якого зіткнення між двома невідомими вхідними даними набагато дешевше, завдяки парадоксу дня народжень: якщо у кімнаті лише 23 людини, то ймовірність того, що дві з них мають однаковий день народження, становить більше ніж 50%, оскільки порівнюються всі пари, а не шукається конкретну дату. Та ж математика означає, що в хеші зіткнення очікується після приблизно 2ⁿ/² випадкових спроб, а не 2ⁿ. Для 256-бітного хешу це все ще астрономічні 2¹²⁸ операцій — безпечно з практичної точки зору — але для 128-бітного хешу це лише 2⁶⁴, що знаходиться в межах досяжності спеціалізованого обладнання, що є однією з причин, чому 128-бітні розбиття вважаються занадто короткими для нових криптографічних застосувань.

expected tries for a collision  ≈ sqrt(2^n) = 2^(n/2)
n = 256 (SHA-256)  -> ~2^128 tries  (infeasible)
n = 128 (MD5-ish)  -> ~2^64  tries  (feasible with enough hardware)
n =  64             -> ~2^32  tries  (feasible on a laptop in hours)

Коли хешні функції насправді порушуються

MD5 (128 біт) має практичні зіткнення з 2004 року і зараз вважається криптографічно зламаним — атаки зіткнень виконуються за лічені секунди на звичайному обладнанні. SHA-1 (160 біт) був зламаний у 2017 році, коли Google та CWI Amsterdam опублікували атаку SHAttered, що призвело до двох різних PDF-файлів із однаковими хешами SHA-1 після приблизно 2⁶³ обчислень — значно менше, ніж 2⁸⁰ теоретичний межа силового збрукування «день народження», оскільки атака використовувала структурні слабкості в алгоритмі стиснення SHA-1, а не покладалася на чистое силове збрукування. SHA-2 (SHA-256/SHA-512) та SHA-3 (структурно відмінний дизайн типу «sponge», стандартизований у 2015 році спеціально для захисту від будь-яких майбутніх структурних слабкостей, виявлених у сімействі SHA-2) досі не зламані станом на сьогоднішній день.

Хешування паролів – це інша проблема

SHA-256 навмисно швидкий — і це абсолютно неправильно для зберігання паролів, оскільки швидке хешування робить дешевшими атаки типу груба сила та дощ таблиць проти викрадених баз даних паролів. Хешування паролів використовує спеціалізовані повільні функції замість цього – bcrypt, scrypt і Argon2 (поточна рекомендована за замовчуванням), які додають налаштований фактор роботи та, для scrypt і Argon2, навмисно великі вимоги до пам’яті, щоб протистояти паралелізму GPU та ASIC, так що перевірка одного пароля займає мілісекунди для легітимного входу, а перевірка мільярда кандидатів займає відповідно більше часу для нападника.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Hash Functions і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.