Хеш і алгоритми хешування – це ключові поняття, з якими знайомляться новачки в сфері блокчейну і які завжди йдуть об руку з безпекою. Для підтримки децентралізованих мереж і консенсусних механізмів, серед яких Біткойн або Ethereum з тисячею вузлів, з’єднаних за допомогою p2p, необхідна “відсутність довіри” і ефективна система підтвердження. Цим мережам потрібні компактні способи шифрування інформації, які дозволяли б учасникам проводити швидку і безпечну перевірку.
Блок – одна з основних складових Біткойну і Ethereum. Блок містить інформацію про транзакції, тимчасові мітки та інші істотні метадані. Величезну роль у забезпеченні безпеки відіграє можливість стискати великі обсяги інформації про глобальний стан мережі в короткі стандартні повідомлення, які при необхідності можна легко перевірити. Ці повідомлення і є хеш.
Якщо змінити хоча б один символ вхідного значення, вийде зовсім інший хеш!
Криптографічні хеші використовуються скрізь, починаючи із зберігання паролів і закінчуючи системами перевірки. Їх суть полягає у використанні детермінованого алгоритму, який бере вхідні дані і створює рядок з фіксованою довжиною. Таким чином, ті ж вхідні дані завжди будуть перетворені в однакові вихідні дані.
Детермінізм важливий не тільки для хешів, адже навіть якщо змінити один біт вхідних даних, вийде зовсім інший хеш.
Проблема алгоритмів хешування полягає в неминучості колізій. Так як довжина рядка такого хешу фіксована, то можуть існувати і інші вхідні дані, що утворюють той же хеш. Колізії — це погано. Це означає, що зловмисник може створювати колізії за запитом, може передавати шкідливі файли або дані з коректним хешем і видавати ці дані за правильні. Хороша функція хешування повинна максимально ускладнювати для зловмисників процес пошуку шляхів створення вхідних даних з тим же значенням хешу.
Процес розрахунку хешу не повинен бути занадто ефективним, так як в цьому випадку зловмисники легко можуть обчислити колізії. Алгоритми хешування повинні бути стійкими до атак знаходження прообразу. Необхідно максимально ускладнювати процес розрахунку кроків для знаходження вихідного значення, з якого був створений хеш (наприклад, прообразу).
Необхідно, щоб спосіб обчислення x для s= hash (x) був практично неможливим.
Отже, «гідні» алгоритми хешування повинні мати три властивості:
- якщо змінити один біт вхідних даних, повинен утворитися лавинний ефект і вийти зовсім інший хеш;
- невелика ймовірність колізій;
- ефективність, яка не жертвує колізійною стійкістю.
Злом хешів
Один з перших стандартів алгоритмів хешування — хеш MD5. Цей алгоритм користувався популярністю для перевірки цілісності файлів (контрольні суми) та зберігання хешованих паролів в базах даних веб-додатків. Його функціонал досить простий — він видає рядок з фіксованою довжиною 128 біт для кожного вхідного значення і використовує стандартні односторонні операції в декількох циклах для обчислення детермінованого вихідного значення. Через коротку довжину вихідного значення і простоту операцій хеш MD5 дуже легко піддається злому, зокрема атаці “днів народження”.
Атака «днів народження»
Існує відоме твердження про те, що якщо в кімнаті знаходяться 23 людини, то шанс того, що двоє з них народилися в один день, дорівнює 50%. Якщо в кімнаті знаходяться 70 осіб, то ця ймовірність збільшується до 99,9%. Це відбувається згідно з принципом Діріхле, який стверджує, що якщо помістити 100 голубів в 99 коробок, то в одній з коробок виявиться два голуба. Обмеження фіксованої довжини вихідного значення означає, що існує фіксований рівень комбінацій для колізій.
Хеш MD5 настільки вразливий до колізій, що навіть на простому процесорі Pentium з частотою 2,4 ГГц, можна обчислити колізії хешу всього за кілька секунд. Більш того, широке застосування цього хешу на зорі існування мережі створило мільйони прообразів MD5, які можна було знайти за допомогою звичайного пошуку Google по їх хешу.
Різноманітність і еволюція алгоритмів хешування
Початок: SHA1 і SHA2
АНБ (так-так, АНБ) вже протягом довгого часу є піонером по створенню стандартів алгоритмів хешування. Саме АНБ запропонував алгоритм Secure Hashing Algorithm або SHA1 з фіксованою довжиною вихідного значення в 160 біт. На жаль, SHA1 набагато перевершував MD5 завдяки збільшенню значення, кількості односторонніх операцій та їх складності, але цей хеш не пропонував грунтовних поліпшень захисту від більш потужних машин, що створюють різні вектори атаки.
SHA3
У 2006 році Національний інститут стандартів і технологій США (NIST — National Institute of Standards and Technology) оголосив конкурс на створення альтернативи алгоритмом SHA2, яка повинна була фундаментально відрізнятися за своїм дизайном і стати новим стандартом. З схеми алгоритмів хешування під назвою KECCAK (вимовляється як «кечак») з’явився алгоритм SHA3.
Хоча SHA3 і має схожу з попередніми алгоритмами назву, він сильно відрізняється за своєю внутрішньою структурою механізмом криптографічної губки. Цей механізм здійснює випадкові перестановки для поглинання і створення даних, служачи джерелом випадковості для вхідних даних, які будуть потрапляти в алгоритм хешування в майбутньому.
Обробка вхідних даних за допомогою криптографічної губки KECCAK256
SHA3 зберігає початковий стан з великою кількістю бітів інформації, ніж у вихідному значенні, і тим самим перевершує обмеження колишніх алгоритмів. Цей алгоритм став стандартом NIST в 2015 році.
Хешування і доказ виконаної роботи
В рамках впровадження алгоритму хешування в протокол блокчейну для алгоритму доказу виконаної роботи Bitcoin використовував SHA256, а пізніше Ethereum — модифіковану версію SHA3 (KECCAK256). При виборі хеш-функції для блокчейну з доказом виконаної роботи дуже важлива ефективність обчислення хешу.
SHA256 біткойну може бути вкрай ефективно обчислений за допомогою спеціального апаратного забезпечення – спеціалізованих інтегральних мікросхем (ASIC-Application Specific Integrated Circuits). Про використання ASIC в майнінгових пулах та про те, як вони призводять до централізації обчислення, написано дуже багато. Доказ виконаної роботи провокує створення пулів з груп ефективних в обчислювальному відношенні машин, завдяки чому збільшується так звана «хеш-потужність» або кількість хешів, які може обчислювати машина за певний період часу.
Майнінг в пулі проти соло-майнінгу ніяк не збільшує хеш-потужність учасника. Швидкість знаходження хешів при фіксованій хеш-потужності обладнання учасника не змінюється, якщо порівнювати з соло-майнінгом. Однак, зібрана від різних учасників хеш-потужність всіх учасників пулу, дозволяє знаходити блоки частіше, ніж у кожного з одиничних учасників пулу. Відповідно, пул знаходить блоки частіше і виплачує винагороду за блок всім учасникам пулу в одиницю часу пропорційно хеш-потужності, що бере участь в пулі — за вирахуванням комісії пулу. Наприклад, учасник з 1Ghash/s при майнінзі біткойна соло міг би очікувати подію «знаходження блоку» — і отримання за нього нагороду в розмірі 12,5 BTC — коли-небудь протягом п’яти років (наприклад!). Участь у пулі тією ж потужністю 1Ghash/s (за умови не зміни складності на інтервалі п’яти років!) дозволяє тому ж майнеру отримувати 12,5 BTC частинами, рівномірно протягом тих же п’яти років. Це вирішує проблему майнера з виплатами фіату в реалі на підтримку ферми.
В Ethereum впроваджений модифікований алгоритм SHA3-KECCAK256. Алгоритм доказу виконаної роботи Ethereum під назвою Dagger-Hashimoto вимагав від апаратного забезпечення занадто багато пам’яті для обчислень.
Біткойн і подвійний SHA256
Біткойн хешує дані за допомогою SHA256 незвичайним способом: він запускає в протоколі два види алгоритму. Потрібно розуміти, що це не міра проти атак «днів народження», тому що якщо hash(x) = hash(y), то hash(hash(x)) = hash(hash(y)). Подвійний алгоритм SHA256 використовується для боротьби з атакою подовженням повідомлення.
Якщо зловмисники знають довжину вхідних даних хешу, то можуть змусити хеш-функцію взяти певну частину внутрішнього стану, додавши секретний рядок до значення хешу. Через цю нестачу алгоритму SHA256 з сімейства алгоритмів SHA2 Біткойн обчислює хеш двічі.
Ethereum 2.0 і BLAKE
SHA3 – не єдиний винахід, що з’явився в результаті конкурсу NIST в 2006 році. Друге місце зайняв алгоритм BLAKE. Для сегментування Ethereum 2.0 більш ефективне хешування — це практично обов’язкова вимога, яка серйозно досліджується командами розробників. Ретельному аналізу піддається алгоритм хешування BLAKE2b — сильно вдосконалена версія BLAKE,через свою фантастичну ефективність в порівнянні з KECCAK256 і високого рівня безпеки.
На сучасному процесорі обчислення за допомогою BLAKE2b проводиться в три рази швидше, ніж за допомогою KECCAK.
Майбутнє алгоритмів хешування
Схоже, що майбутнє алгоритмів хешування зводиться або до (1) збільшення складності внутрішніх операцій хешування, або до (2) збільшення довжини вихідного значення хешу в надії на те, що комп’ютери зловмисників не встигнуть обчислити колізії.
Для забезпечення безпеки мереж розробники покладаються на неоднозначність прообразів односторонніх операцій. Таким чином, в цілях безпеки алгоритму хешування необхідно як можна сильніше ускладнити процес пошуку двох значень хешу з однаковими вихідними даними, незважаючи на наявність нескінченної кількості можливих колізій.
Чи встоять алгоритми хешування проти квантових обчислень майбутнього?
Якщо коротко, то виходячи з поточної ситуації, можна відповісти, що так, алгоритми хешування пройдуть перевірку часом і встоять проти квантових обчислень. Квантові обчислення можуть створити проблеми щодо суворих базових математичних структур з використанням спритних трюків і таких теорій, як шифрування за методом RSA. Однак, алгоритми хешування мають більш формальну внутрішню структуру.
Квантові комп’ютери дійсно прискорюють процес обчислення таких неструктурованих завдань, як хешування, але вони все одно будуть використовувати атаку «грубою силою», як це роблять звичайні комп’ютери сьогодні.
Незалежно від того, які алгоритми використовуються в протоколах, ясно одне — нас чекає ефективне щодо обчислень майбутнє і ми повинні розумно підходити до вибору правильних інструментів для цієї справи, і тоді алгоритми витримають перевірку часом.
