Криптографічні хеш-функції

У цьому уроці ми розглянемо криптографічні хеш-функції, що широко використовуються для швидкої перевірки та автентифікації.

До кінця уроку ми охопимо:

• Що таке криптографічні хеш-функції
• Приклади коду на Python, що демонструють використання хеш-функцій
• Огляд застосувань криптографічного хешування
• Безпека криптографічного хешування
• Загрози цим алгоритмам з боку як класичних, так і квантових комп'ютерів

Вступ до криптографічного хешування

Хеш-функції являють собою цінний інструмент у криптографії, оскільки дозволяють здійснювати перевірку з дотриманням конфіденційності. Тому хеш-функції є важливим компонентом механізмів автентифікації та цілісності даних, таких як коди автентифікації повідомлень на основі хешів (HMAC) та цифрові підписи. Ця стаття розглядає базові ідеї та міркування безпеки, що лежать в основі криптографічних хеш-функцій, і описує потенційні вразливості у зв'язку з появою квантових обчислень.

Базова логіка та принципи побудови хеш-функцій

Існує багато ситуацій, де автентифікацію та перевірку цілісності потрібно виконувати дешево, не розкриваючи приватну інформацію стороні, що проводить перевірку.

Наприклад, при завантаженні програмного забезпечення з віддаленого сервера потрібен ефективний механізм для перевірки того, що завантажене ПЗ не було змінено після того, як оригінальний автор його створив. Аналогічно, при автентифікації користувачів веб-застосунків бажано використовувати механізм, що не передбачає фізичного зберігання або передачі реальних паролів, що може поставити під загрозу їхню конфіденційність.

Криптографічні хеш-функції (КХФ) ефективно й безпечно вирішують ці потреби.

Принципово, криптографічна хеш-функція приймає вхідні дані (або повідомлення) довільної довжини і повертає рядок фіксованої довжини з n бітів. Вивід КХФ також називається дайджестом. Корисна КХФ повинна задовольняти кілька ключових властивостей:

1. Рівномірність: Дайджести, що виробляються КХФ, мають бути рівномірно розподілені та виглядати випадковими. Мета — забезпечити, щоб вивід не розкривав жодної інформації про вхід.
2. Детермінованість: Для даного вхідного значення КХФ завжди має виробляти той самий дайджест, тобто вона має бути детермінованою.
3. Необоротність: КХФ є односпрямованою функцією — тобто за даним дайджестом має бути практично неможливо обернути хешування й отримати вхід.
4. Приблизна ін'єктивність: Хоча КХФ є функціями «багато до одного», вони мають виглядати як функції «один до одного». Це досягається поєднанням великого розміру вихідного простору з ефектом лавини, при якому незначні зміни у вхідних даних призводять до кардинально різних дайджестів. Ця характеристика відома як приблизна ін'єктивність.

З огляду на це, можна перевірити фрагмент даних стосовно оригінального екземпляра, порівнявши дайджест даних із дайджестом оригіналу.

• Якщо два дайджести збігаються, з великою ймовірністю можна бути впевненим, що дані ідентичні оригіналу.
• Якщо дайджести відрізняються, можна бути певним, що дані були підроблені або є недійсними.

Оскільки дайджести КХФ самі по собі не розкривають реальний вміст даних чи оригіналу, вони дозволяють здійснювати перевірку, зберігаючи конфіденційність.

Mathematical description

Хеш-функцію $H$ можна визначити як:

$H : Σ^* \rightarrow \{0,1\}^n$

де $Σ^*$ — множина всіх можливих рядків, які ми можемо вважати двійковими рядками будь-якої довжини.

Той факт, що розмір вхідної області $Σ^*$ функції $H$ необмежений, тоді як розмір кообласті $\{0,1\}^n$ обмежений, означає, що $H$ є відображенням «багато до одного», що відображає нескінченно багато входів у будь-який даний n-бітний рядок.

Властивості рівномірності та детермінованості добре описуються моделлю випадкового оракула криптографічного хешування.

Приклад криптографічного хешування на Python із SHA-256

Цей простий приклад демонструє криптографічне хешування за допомогою популярного алгоритму SHA-256 з бібліотеки Python cryptography. Спочатку ми покажемо, як незначна відмінність у відкритих текстах призводить до великої різниці в хеш-дайджестах.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

Два повідомлення відрізняються рівно одним символом.

Далі ми створюємо об'єкти hash для здійснення процесу хешування, що включає виклики двох методів: update і finalize.

Ми бачимо, що завдяки ефекту лавини в КХФ SHA-256, різниця в один символ у вхідних повідомленнях призводить до двох кардинально різних дайджестів.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Застосування криптографічного хешування

Унікальні властивості КХФ роблять їх придатними для широкого спектра застосувань:

• Перевірки цілісності даних: Хеш-функції можна використовувати для створення контрольної суми для набору даних. Будь-яке змінення даних, навмисне чи ні, призведе до іншої контрольної суми, попереджаючи системи або користувачів про зміну. Контрольна сума також зазвичай значно компактніша за вихідні дані, що робить порівняння контрольних сум дуже швидким.

Рисунок 1. Безпечне хешування для забезпечення цілісності даних

• Цифрові підписи: Криптографічні хеші є необхідними для функціонування цифрових підписів, оскільки вони передбачають порівняння криптографічно захешованих повідомлень для встановлення автентичності та цілісності зі збереженням конфіденційності.

Рисунок 2. Цифрові підписи

• Блокчейн і криптовалюти: Криптовалюти на кшталт Bitcoin значною мірою покладаються на КХФ, зокрема для забезпечення цілісності транзакцій і механізмів консенсусу, таких як proof of work.

Безпека криптографічного хешування

Безпека КХФ зазвичай оцінюється на основі стійкості до двох типів атак: pre-image та collision.

Стійкість до pre-image

Стійкість до pre-image означає, що за даним дайджестом має бути практично неможливо знайти вхід.

Це пов'язано з односпрямованою властивістю КХФ.

Хороша КХФ розроблена таким чином, що зловмисник, який бажає провести атаку pre-image, не має кращого варіанту, ніж метод грубої сили, часова складність якого дорівнює $2^n$.

mathematical details

За даною КХФ $H$ і дайджестом $g$ має бути обчислювально неможливо знайти будь-яке вхідне значення $m$ із прообразу $g$ таке, що $H(m) = g$.

Стійкість до collision

Стійкість до collision означає, що знайти два різних входи, які хешуються до одного й того самого дайджесту, є складним завданням.

Криптографічна хеш-колізія виникає, коли два входи хешуються до одного дайджесту. Хоча колізії неминуче існують з огляду на природу КХФ «багато до одного», хороша КХФ робить пошук такої колізії практично неможливим.

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

mathematical details of hash collisions

$m_1, m_2$ можна знайти таким чином, що $H(m_1) = H(m_2)$.

Довжина хешу

Стійкість до колізій є суворішою вимогою, ніж стійкість до pre-image, і вимагає вихідних довжин удвічі більших, ніж необхідно для стійкості до pre-image. Це пов'язано з тим, що атака грубою силою, відома як birthday attack, яка може використовуватися для виявлення хеш-колізій, має часову складність $2^{n/2}$.

За відсутності криптоаналітичних слабкостей безпека хеш-функції визначається передусім довжиною хешу. Чим довший хеш, тим більш безпечним він є, оскільки атаки грубою силою стають складнішими.

Широко використовувані криптографічні хеш-функції

Наступна таблиця містить деякі широко вживані криптографічні хеш-функції разом із довжинами їхніх хешів та основними сферами застосування:

Хеш-функція	Довжина виводу (біти)	Основні застосування
MD5	128	Перевірка цілісності файлів, старі системи, некрипто-використання
SHA-1	160	Застарілі системи, Git для контролю версій
SHA-256	256	Криптовалюти (Bitcoin), цифрові підписи, сертифікати
SHA-3	Змінна (до 512)	Різні криптографічні застосування, наступник SHA-2
Blake2	Змінна (до 512)	Криптографія, заміна MD5/SHA-1 в деяких системах
Blake3	Змінна (до 256)	Криптографія, хешування файлів, цілісність даних

• MD5 та SHA-1, хоча ще й зустрічаються в менш чутливих застосуваннях, вважаються застарілими з точки зору стійкості до колізій і не рекомендуються для нових систем. SHA-256, частина сімейства SHA-2, широко використовується і наразі є безпечним для більшості застосувань.
• SHA-3 — новіший стандарт, обраний NIST у 2015 році як переможець конкурсу хеш-функцій NIST. Він розроблений як повна заміна SHA-2, але також має деякі відмінні внутрішні характеристики і є стійким до певних типів атак, що можуть бути ефективними проти SHA-2.
• Blake2 і Blake3 — криптографічні хеш-функції, швидші за MD5, SHA-1, SHA-2 і SHA-3, але принаймні такі ж безпечні, як останній стандарт, SHA-3. Вони дедалі більше використовуються в нових системах, особливо там, де важлива швидкість.

Квантові ризики для традиційного криптографічного хешування

Основна квантова загроза для криптографічного хешування пов'язана з атаками грубою силою.

За заданим дайджестом зловмисник перебиратиме випадкові входи, поки не знайде той, що дає той самий дайджест.

З $n$ бітами у вхідних даних існує $2^n$ можливих значень. Тому зловмисникові потрібно перебрати близько $2^{n-1}$ входів, щоб мати більше 50% шансів на успіх.

Алгоритм Гровера

Для такого неструктурованого контексту пошуку алгоритм Гровера може забезпечити квадратичне прискорення за допомогою техніки, відомої як квантове підсилення амплітуди, знижуючи часову складність атаки pre-image до $2^{n/2}$.

На практиці це означає, що 256-бітна КХФ, яка наразі вважається безпечною проти атак pre-image з боку класичних комп'ютерів, забезпечуватиме той самий рівень безпеки, що й 128-бітна КХФ, якщо їй протистоїть квантовий зловмисник, який використовує алгоритм Гровера.

Алгоритм Гровера сам по собі не надає додаткових квантових прискорень щодо атак на колізії понад ліміт, встановлений birthday attack, яка може виконуватися на класичних комп'ютерах. Оскільки класична birthday attack вже вимагає від КХФ застосування довжин хешів удвічі довших, ніж потрібно для стійкості до pre-image, той факт, що пошук Гровера фактично вдвічі скорочує довжину хешу щодо атак pre-image, не становить практичної загрози.

Наприклад, у випадку SHA-256 виконання порядку $2^{128}$ операцій для проведення атаки pre-image з допомогою Гровера все ще буде нездійсненним у найближчому майбутньому.

Алгоритм BHT

Квантовий алгоритм, що поєднує аспекти birthday attack з пошуком Гровера, був запропонований у 1997 році Брассаром, Гойєром і Таппом (BHT) і теоретично забезпечує масштабування $O(2^{n/3})$ для пошуку хеш-колізій. Однак це покращене масштабування ґрунтується на існуванні технології квантової пам'яті з довільним доступом QRAM, якої наразі не існує.

Без QRAM досяжне масштабування становить $\tilde{O}(2^{2n/5})$, і для довжин хешів, що наразі використовуються, це незначне покращення здатності до пошуку колізій порівняно з birthday attack не є критичною загрозою.

Підсумок

Криптографічні хеш-функції є важливим компонентом для забезпечення цілісності та конфіденційності даних у цифрових інформаційних системах і знаходять широке застосування в багатьох контекстах.

Вимоги до безпеки КХФ в основному визначаються через їхню стійкість до атак pre-image і collision. Для добре розроблених КХФ довжина хешу є хорошим показником рівня безпеки.

Хоча поява квантових комп'ютерів, що виконують алгоритми Гровера і BHT, теоретично впливає на стійкість до pre-image і collision традиційних КХФ, великі довжини хешів, що вже використовуються сьогодні, означають, що сучасні алгоритми криптографічного хешування, такі як SHA-3, найімовірніше залишаться безпечними, якщо не будуть виявлені досі невідомі криптоаналітичні атаки.

Актуальність КХФ полягає в їхній ролі як фундаментального будівельного блоку для квантово-стійких криптографічних схем, що гарантує безпеку цифрової інформації навіть перед лицем потенційних майбутніх досягнень у квантових обчислювальних алгоритмах і технологіях.