Хеш-функція

Чи траплялося вам працювати з великими обсягами даних, де важливо швидко знаходити, перевіряти або захищати інформацію?

Саме тут на сцену виходить хеш-функція як інструмент компактного і надійного перетворення даних.

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

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

Визначення хеш-функції

Хеш-функція -мати всіх блокчейнів, хранителька паролів і просто цікава технологія.

Про хеш-функції мало говорять за межами вузького прошарку експертів з мережевої безпеки. А даремно. Без неї у нас не було б ні блокчейна, ні NFT, ні навіть електронних довідок у «Дії» – а вкрасти пароль з будь-якого сервісу було б справою кількох хвилин.

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

Що таке хеш-функція

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

Початковим повідомленням може бути що завгодно: рядок із пісні, код програми або, скажімо, роман «Ловець снів» Стівена Кінга китайською мовою. Неважливо, якої довжини буде вихідний текст, – на виході все одно вийде бітовий масив одного і того ж розміру. Наприклад, для функції SHA-1 це 160 біт, або рівно 40 символів.

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

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

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

Для чого потрібна хеш-функція

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

Один із популярних варіантів використання хеша – зберігання паролів на сайті. Коли ви заходите в особистий кабінет, ваші дані не передаються в базу даних у відкритому вигляді – інакше хакери давно вкрали б усі акаунти у світі.

Під час авторизації пароль спочатку хешується і тільки потім записується в базу даних. Під час наступної спроби входу пароль знову переводиться в хеш і звіряється з хешем на сервері. Якщо хеші збіглися, ви потрапляєте в особистий кабінет.

Однак у хакерів і на цей випадок є хитрість. Оскільки один і той самий текст видає однаковий хеш, можна просто хешувати найпопулярніші паролі та підставляти їх під час злому. У Мережі можна знайти цілі словники, які містять тисячі колись злитих дехешованих паролів.

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

Ще один приклад використання хешів – перевірка цілісності файлів. Наприклад, коли ви запускаєте гру зі Steam, лаунчер стежить, що все встановлено правильно, і жоден заповзятливий користувач не заліз у файли гри та не нашпигував їх під зав’язку різними модами і чітами.

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

Де використовується хеш-функція

Ось ще кілька сфер, де використовується хешування:

• Блокчейн – щоб гарантувати справжність транзакцій. У кожен блок ланцюга додається хеш попередньої операції – якщо поміняти дані хоч трохи, хеші не збігатимуться і мережа не прийме зміни.
• Цифрові підписи – щоб дистанційно підписувати документи без поїздок в офіси та зустрічей із кур’єрами.
• Хеш-таблиці – це свого роду бази даних, де всі дані захищені від перезапису.
• Антивіруси – зберігають віруси у вигляді так званого нечіткого хеша, який дає змогу шукати нові модифікації шкідливих програм.
• Системи контролю версій (Git) – для перевірки цілісності об’єктів у репозиторії: файлів, коммітів, дерев тощо.

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

Настав час з’ясувати, що за математична магія перетворює звичайний текст на мішанину із символів. Для цього ми покроково розберемо роботу алгоритму SHA-1 – зараз він вважається застарілим, але для розуміння основ підходить ідеально.

Хешувати будемо звичайну програмістську «рибу» – фразу «Hello, world!». Оскільки комп’ютер спілкується тільки мовою нулів і одиниць, насамперед алгоритм переведе текст у двійковий код.

Нюанс у тому, що хеш-функція оперує тільки блоками по 512 біт – а в нашій фразі тільки 104 біти. Тому доповнимо блок – почнемо з одиниці, а решту заповнимо нулями. У самому кінці блоку додамо двійковий код, що позначає розмір повідомлення в бітах, – у нас це 104, або 1101000.

Після цього алгоритм підготує основу для майбутнього хеша. За замовчуванням це п’ять констант по вісім символів – на виході якраз вийде фраза довжиною 40 символів і розміром 160 біт.

Виглядають константи так:

• h0 = 0×67452301
• h1 = 0xEFCDAB89
• h2 = 0×98BADCFE
• h3 = 0×10325476
• h4 = 0xC3D2E1F0

А далі починається магія. Алгоритм дробить вихідне повідомлення на 80 шматочків і перемішує з кожною з констант. Кожна ітерація циклу оновлює значення h0-h4 доти, доки не закінчиться вихідне повідомлення. Поступово хеш виглядатиме все більш і більш випадковим.

Як цей цикл виглядає в псевдокоді, можна подивитися під спойлером.

Виконується функція в кілька раундів: один блок довжиною 512 біт – одна ітерація. Оскільки у фразі «Hello, world!» менше 512 біт, алгоритм опрацює її в один захід. Але навіть якби ми подали на вхід усі чотири томи «Війни і миру», хешування все одно зайняло б лише кілька секунд.

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

На виході отримуємо готовий хеш.

Безпека хеш-функції

В ідеалі хеш-функція має володіти такими властивостями:

• Унікальність – два різних повідомлення не можуть видати однаковий хеш (насправді бувають винятки – про це пізніше).
• «Лавинний ефект» – якщо у вихідних даних поміняти хоча б одну букву, вийде зовсім інший хеш.
• Передбачуваність – для одного і того ж повідомлення завжди виходить однаковий хеш.
• Незворотність – не можна просто так взяти і прочитати те, що захешовано.
• Швидкість – щоб дані швидко оброблялися у високонавантажених системах.

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

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

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

Утім, найсучаснішим хеш-функціям ця проблема майже не загрожує. Наприклад, SHA-256, яка використовується в блокчейні, може видавати 2^256 варіантів хешів – це всього в 100 разів менше, ніж кількість атомів у космосі. Нарватися на колізію під час роботи з нею майже неможливо – про якийсь брутфорс і говорити не доводиться.

Якщо, звісно, у вас немає під рукою квантового комп’ютера (але навіть і це, за словами експертів, не гарантія успішного злому ?).

Коротко про головне

• Криптографічна хеш-функція – це алгоритм, який приймає на вхід повідомлення і перетворює його на хеш, тобто бітовий масив фіксованого розміру. Наприклад, для SHA-1 це 160 біт, а для SHA-256 – 256 біт.
• Для кожного повідомлення створюється свій унікальний хеш. Якщо поміняти у вхідних даних хоча б один символ, хеш зміниться до невпізнання.
• Хеш можна присвоїти будь-якому файлу: тексту, пісні або комп’ютерній грі. Ключовий сенс – переконатися, що дані не можна змінити або підробити.
• Результат роботи хеш-функції незворотній – алгоритм не можна запустити у зворотний бік і отримати вихідне повідомлення. Цим хешування відрізняється від шифрування, де, як правило, є ключ дешифрування.
• Хешування використовується для різних завдань: для безпечного зберігання паролів на сайті, створення цифрових підписів, захисту ігрових даних, підтвердження транзакцій у блокчейні та багато чого іншого.

Висновок

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

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