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

Криптографічна хеш-функція (CHF) існує з 1980-х років і знаходить широке застосування в криптографії, перевірці цілісності даних, індексації баз даних та інших сферах.

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

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

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

Характеристики криптографічних хеш-функцій

Пошук за запитом "SHA256 Generator" показує, що різні веб-сайти, які використовують один і той же алгоритм, послідовно генерують ідентичні хеш-значення для схожих вхідних текстів.

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

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

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

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

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

Візьмемо для прикладу згаданий MD5, чи можуть різні файли генерувати однакове хеш-значення? Відповідь - так, але ймовірність цього вкрай низька. Це явище відоме як зіткнення криптографічних хешів, яке може статися як випадково, так і внаслідок навмисної атаки. Стандартна ймовірність зіткнення для алгоритму MD5 становить близько 1/2¹²⁸, що робить випадкові випадковості дуже малоймовірними. Однак MD5 вважається вразливим до навмисних атак на зіткнення, оскільки створити однакове хеш-значення для двох різних відкритих текстів відносно легко. Тому, хоча алгоритм MD5 все ще можна використовувати для завдань, які не пов'язані з безпекою, він більше не підходить для завдань безпечної автентифікації (таких як автентифікація ключів або цифрових підписів).

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

Ethereum використовує криптографічну хеш-функцію KECCAK-256, яку багато людей помилково ідентифікують як SHA-3 (в тому числі в докторській дисертації засновника Celestia), оскільки ця функція спочатку була записана як "sha3" в Solidity. Через плутанину його згодом перейменували на Кекчак256.

MetaMask використовує різні криптографічні хеш-функції в своїх операціях:

• Набір з 12 слів з рандомізованої комбінації 2048 слів пропозиції BIP39 утворює допоміжні слова.
• Кожне слово відповідає значенню, що разом створює початкові цілі числа.
• MetaMask застосовує функцію SHA-256 до початкового цілого числа, генеруючи приватний ключ для імпорту існуючих гаманців. Іноді це саме те, що потрібно ввести при імпорті існуючого гаманця на новий пристрій.
• Алгоритм ECDSA обробляє приватний ключ для отримання відкритого ключа.
• MetaMask генерує хеш відкритого ключа за допомогою функції Keccak-256, беручи останні 20 байт хешу (перетворені в шістнадцяткову систему числення, тобто довжиною в 40 букв або цифр) і додаючи до них 0x, що стає адресою ETH.

Як працює функція криптографічного хешування в блокчейні

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

Під час майнінгу біткоїна майнери об'єднують дані транзакцій із заголовком блоку, який містить деталі транзакції, а також метадані, такі як часові мітки та випадкові числа. Майнери намагаються створити певний хеш SHA-256, ітеративно підбираючи випадкові числа (так звані "nonce") в заголовку блоку, щоб задовольнити певні критерії, які зазвичай починаються з певної кількості початкових нулів. Враховуючи природу хеш-функції SHA-256, єдиним методом виявлення сумісного хешу є постійне експериментування з різними випадковими числами.

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

Окрім майнінгу, криптографічні хеш-функції відіграють ключову роль у встановленні зв'язків між блоками та відстеженні змін транзакцій у системах блокчейн. Хеш-покажчики слугують структурами даних, що полегшують індексування, пошук та перевірку модифікацій даних. Кожна транзакція в блокчейні проходить хешування перед тим, як бути організованою в блоки. Згодом хеш-покажчик пов'язує кожен блок з його попередником, зберігаючи хеш даних попереднього блоку. Взаємопов'язана природа блоків забезпечує незмінність всередині блокчейну; будь-яка модифікація транзакції призводить до зміни хеш-значення, що, відповідно, змінює хеші всіх наступних блоків. Наприклад, розглянемо блокчейн, що складається з двох блоків:

• Блок 1: містить хеші транзакцій T1, T2 і T3.

• Блок 2: містить хеші транзакцій T4, T5 і T6, а також хеш Блоку 1.

Якщо хтось спробує підробити транзакцію T1 у Блоці 1, йому потрібно буде перекалібрувати хеш-значення Блоку 1 та оновити нове значення у Блоці 2. Однак, через односпрямований характер криптографічних хеш-функцій та їхню стійкість до попереднього зображення, змінити транзакцію T1 у Блоці 1 на основі хеш-значення Блоку 2 виявляється складним завданням.

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

У сфері блокчейну криптографічна хеш-функція виконує кілька важливих ролей:

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

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

• Механізм консенсусу: В рамках механізму консенсусу Proof of Work (PoW) майнери повинні визначити значення nonce, що відповідає вимогам складності, шляхом виконання хеш-функцій.

Майбутнє криптографічних хеш-функцій

2 вересня 2022 року Віталік опублікував у Twitter (X) запитання, яка криптографічна хеш-функція залишиться безпечною, якщо буде винайдено квантовий комп'ютер, що використовує алгоритм Шора.

Джерело: твіт Віталіка

Він зазначив, що квантовий комп'ютер, здатний використовувати алгоритм Шора, може зламати RSA (давню криптосистему з відкритим ключем) або будь-що, засноване на факторизації, еліптичних кривих і групах невідомого порядку. Однак, хеш-значення (наприклад, SHA-256) добре працюють в контексті квантових обчислень, хоча їх безпека буде дещо знижена, тому рекомендується використовувати довші хеш-значення.

Висновок

Наскільки надійні криптографічні хеш-функції, такі як SHA-256? "256" у SHA-256 означає 2, піднесене до степеня 256, число настільки велике, що його важко зрозуміти конкретно.

Джерело: 3Blue1Brown

Тим не менш, 3Blue1Brown представила яскраву аналогію, яка допоможе зрозуміти безпеку криптографічних хеш-функцій: уявіть собі сценарій, в якому 4 мільярди людей на Землі володіють комп'ютером з винятковими обчислювальними можливостями, що в 1000 разів перевищує обчислювальну потужність Google по всьому світу. Одночасно уявіть собі космос з 4 мільярдами планет і 4 мільярдами галактик, подібний до Чумацького Шляху! Навіть за таких екстремальних умов знадобиться понад 500 мільярдів років, перш ніж з'явиться шанс 1 до 4 мільярдів точно вгадати "конкретні вхідні дані, необхідні для генерації вихідного хеш-значення SHA-256".