Обчислення хеш функції. Алгоритми хешування – просте пояснення складного. Що таке «Атака дня народження?»

(Іноді хешування, англ. hashing) - перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями чи функціями згортки, які результати називають хешом, хеш-кодом чи дайджестом повідомлення (англ. message digest).

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

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

Контрольні суми

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

Платою за таку високу швидкість є відсутність криптостійкості – легка можливість підігнати повідомлення під наперед відому суму. Також зазвичай розрядність контрольних сум (типове число: 32 біти) нижче, ніж криптографічних хешей (типові числа: 128, 160 і 256 біт), що означає можливість виникнення ненавмисних колізій. Найпростішим випадком такого алгоритму є розподіл повідомлення на 32- або 16-бітові слова та їх підсумовування, що застосовується, наприклад, TCP/IP.

Як правило, до такого алгоритму пред'являються вимоги відстеження типових апаратних помилок, таких, як кілька помилкових біт, що йдуть до заданої довжини. Сімейство алгоритмів т.з. "циклічних надлишкових кодів" задовольняє цим вимогам. До них відноситься, наприклад, CRC32, що використовується в апаратурі Ethernet та у форматі упакованих файлів ZIP.

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

• Незворотність: для заданого значення хеш-функції mповинно бути обчислювально неможливо знайти блок даних X, для котрого H(X) = m.


• Стійкість до колізій першого роду: для заданого повідомлення Mповинно бути обчислювально неможливе підібрати інше повідомлення N, для котрого H(N) = H(M).


• Стійкість до колізій другого роду: має бути обчислювально неможливим підібрати пару повідомлень (M, M"), що мають однаковий хеш.

• Оборотна функція нестійка до колізій першого та другого роду.


• Функція, нестійка до колізій першого роду; нестійка до колізій другого роду; зворотне неправильне.

Атака «днів народження» дозволяє знаходити колізії для хеш-функції з довжиною значень nбітів у середньому приблизно за 2 n/2 обчислень хеш-функції. Тому n-бітна хеш-функція вважається криптостійкою, якщо обчислювальна складність знаходження колізій для неї близька до 2 n/2.

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

Застосування хеш-функцій

• хороша перемішування даних
• швидкий алгоритм обчислення

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

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



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

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

Хешування

Хешування(іноді «хешування», англ. hashing) - перетворення за детерменованим алгоритмом вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш-функціямиабо функціями згортки, а їх результати називають хешем, хеш-кодомабо зведенням повідомлення(англ. message digest). Якщо два рядки хеш-коды різні, рядки гарантовано різняться, якщо однакові - рядки, мабуть, збігаються.

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

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

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

Історія

Першою серйозною роботою, пов'язаною з пошуком у великих файлах, була стаття Уеслі Пітерсона (англ. W. Wesley Peterson ) в IBM Journal of Research and Development 1957 року, де він визначив відкриту адресацію, і навіть вказав на погіршення продуктивності при видаленні. Через шість років було опубліковано роботу Вернера Бухгольця (нім. Werner Buchholz ), у якій проведено широке дослідження хеш-функцій. Протягом кількох наступних років хешування широко використовувалося, проте не було опубліковано жодних значних робіт.

У 1967 році хешування в сучасному значенні згадано в книзі Херберта Хеллермана "Принципи цифрових обчислювальних систем". У 1968 році Роберт Морріс (англ. Robert Morris ) опублікував у Communications of the ACM великий огляд з хешування, ця робота вважається ключовою публікацією, що вводить поняття про хешування в науковий обіг і закріпила термін, що раніше застосовувався тільки в жаргоні фахівців, «хеш».

До початку 1990-х років у російськомовній літературі як еквівалент терміну «хешування» завдяки роботам Андрія Єршова використовувалося слово «розстановка», а для колізій використовувався термін "конфлікт" (Єршов використовував "розстановку" з 1956 року, в російськомовному виданні книги Вірта "Алгоритми та структури даних" 1989 року також використовується термін "розстановка"). Пропонувалося також назвати метод російським словом «окрошка». Однак жоден із цих варіантів не прижився, і в російськомовній літературі використовується переважно термін «хешування».

Види хеш-функцій

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

1. швидко обчислюватися;
2. Мінімізувати кількість колізій

Припустимо, для певності, що кількість ключів , а хеш-функція має не більше різних значень:

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

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

Хеш-функції засновані на розподілі

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

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

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

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

Мультиплікативна схема хешування

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

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

Серед переваг цих двох методів варто відзначити, що вони вигідно використовують те, що реальні ключі невипадкові, наприклад, якщо ключі являють собою арифметичну прогресію (припустимо послідовність імен «ІМЯ1», «ІМЯ2», «ІМЯ3»). Мультиплікативний метод відобразить арифметичну прогресію приблизно на арифметичну прогресію різних хеш-значень, що зменшує кількість колізій порівняно з випадковою ситуацією.

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

Хешування рядків змінної довжини

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

Універсальне хешування

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

Опис

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

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

Методи боротьби з колізіями

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

У хеш-таблицях

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

1. Метод ланцюжків (метод прямого зв'язування)
2. Метод відкритої адресації

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

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

Криптографічна сіль

Існує кілька способів захисту від підробки паролів і підписів , що працюють навіть у тому випадку, якщо криптоаналітику відомі способи побудови колізій для використовуваної хеш-функції. Одним із таких методів є додавання криптографічної солі (рядки випадкових даних) до вхідних даних (іноді «сіль» додається і до хеш-коду), що значно ускладнює аналіз підсумкових хеш-таблиць. Даний метод, наприклад, використовується для зберігання паролів у UNIX-подібних операційних системах.

Застосування хеш-функцій

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

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

Ці вимоги не є незалежними:

• Оборотна функція нестійка до колізій першого та другого роду.
• Функція, нестійка до колізій першого роду; нестійка до колізій другого роду; зворотне неправильне.

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

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

Контрольні суми

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

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

Платою за таку високу швидкість є відсутність криптостійкості – легка можливість підігнати повідомлення під наперед відому суму. Також зазвичай розрядність контрольних сум (типове число: 32 біти) нижче, ніж криптографічних хешей (типові числа: 128, 160 і 256 біт), що означає можливість виникнення ненавмисних колізій.

Найпростішим випадком такого алгоритму є розподіл повідомлення на 32- або 16-бітові слова та їх підсумовування, що застосовується, наприклад, TCP/IP.

Як правило, до такого алгоритму пред'являються вимоги відстеження типових апаратних помилок, таких, як кілька помилкових біт, що йдуть до заданої довжини. Сімейство алгоритмів т.з. "циклічних надлишкових кодів" задовольняє цим вимогам. До них відноситься, наприклад, CRC32 , застосовуваний у пристроях Ethernet та у форматі стиснення даних ZIP .

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

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

Геометричне хешування

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

Прискорення пошуку даних

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

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

Примітки

Література

• Брюс Шнайєр"Прикладна криптографія. Протоколи, алгоритми, вихідні тексти мовою Сі". – М.: Тріумф, 2002. –

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

В закладки

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

Навіть зміна одного символу у вхідних даних призведе до іншого хешу.

Криптографічні хеші використовуються скрізь від зберігання паролів до систем перевірки файлів. Основна ідея полягає в тому, щоб використовувати детермінований алгоритм (алгоритмічний процес, який видає унікальний та зумовлений результат для завдання вхідних даних), який приймає один вхід та створює рядок фіксованої довжини щоразу. Тобто, використання одного й того ж введення завжди призводить до одного й того самого результату. Детермінізм важливий не тільки для хеш, але і для одного біта, який змінюється у вхідних даних, створюючи зовсім інший хеш. Проблема з алгоритмами хешування – неминучість колізій.Тобто той факт, що хеші є рядком фіксованої довжини, означає, що для кожного введення, яке ми можемо собі уявити, є інші можливі входи, які призведуть до того ж хешу. Колізія – це погано. Це означає, що якщо зловмисник може створювати колізії, він може передавати шкідливі файли або дані, які мають правильний і неправильний хеш і ховатися під правильним хешом. Мета хорошої хеш-функції полягає в тому, щоб зробити надзвичайно складним для зловмисників знайти способи генерації вхідних даних, які хешуються з однаковим значенням. Обчислення хеша має бути занадто простим, оскільки це полегшує зловмисникам штучне обчислення колізій. Алгоритми хешування мають бути стійкими до «атак знаходження прообразу».Тобто, отримуючи хеш, було б надзвичайно складно обчислити зворотні детерміновані кроки, зроблені для відтворення значення, яке створило хеш (тобто знаходження прообразу).

Враховуючи S = ​​hash(x), знайти X має бути майже неможливо.

Нагадаємо, що «хороші» алгоритми хешування мають такі властивості:

• Зміна одного біта у вхідних даних має створити ефект зміни всього хешу;
• Обчислення хешу повинно бути занадто простим, висока складність знаходження прообразу;
• Має дуже низьку ймовірність колізії;

Злом хешей

Одним із перших стандартів алгоритму хешування був MD5 hash, який широко використовувався для перевірки цілісності файлів (контрольних сум) та зберігання хешованих паролів у базах даних веб-додатків. Його функціональність досить проста, тому що вона виводить фіксований 128-бітний рядок для кожного входу і використовує тривіальні односпрямовані операції в кількох раундах для обчислення детермінованого результату. Його коротка вихідна довжина та простота операцій зробили MD5 дуже легким для злому та сприйнятливим до атаки «дня народження».

Що таке «Атака дня народження?»

Ви коли-небудь чули про те, що якщо ви помістите 23 особи в кімнату, є 50% шанс, що у двох із них буде один і той же день народження? Доведення числа до 70 осіб у кімнаті дає 99,9% шанс. Якщо голуби розсаджені в коробки, причому кількість голубів більша за кількість коробок, то хоча б в одній з клітин знаходиться більше одного голуба. Тобто фіксовані обмеження на вихід означають, що існує фіксований ступінь перестановок, на яких можна знайти колізію.

Принаймні, один відсік буде мати всередині двох голубів.

Насправді MD5 настільки слабкий до опору до колізій, що простий побутовий процесор Pentium 2,4 ГГц може обчислити штучні хеш-колізії протягом декількох секунд. Крім того, його широке використання в попередні дні поточної мережі створило тонни витоків MD5 попередніх прообразів в інтернеті, які можна знайти за допомогою простого пошуку Google їх хеша.

Відмінності та розвиток алгоритмів хешування Початок: SHA1 та SHA2

NSA (Агентство національної безпеки) вже давно є піонером стандартів алгоритмів хешування, з їхньою початковою пропозицією алгоритму Secure Hashing Algorithm або SHA1, що створює 160-бітні виходи фіксованої довжини. На жаль, SHA1 просто покращив MD5, збільшивши довжину виведення, кількість односпрямованих операцій та складність цих односторонніх операцій, але не дає будь-яких фундаментальних покращень проти потужніших машин, які намагаються використовувати різні атаки. То як ми можемо зробити щось краще?

Використання SHA3

У 2006 році Національний інститут стандартів і технологій (NIST) запустив конкурс, щоб знайти альтернативу SHA2, яка буде принципово відрізнятися у своїй архітектурі, щоб стати стандартом. Таким чином, SHA3 з'явився як частина великої схеми алгоритмів хешування, відомої як KECCAK (вимовляється Кетч-Ак). Незважаючи на назву, SHA3 сильно відрізняється своїм внутрішнім механізмом, відомим як "конструкція губки", яка використовує випадкові перестановки для "Всмоктування" і "Витискання" даних, працюючи як джерело випадковості для майбутніх входів, які входять в алгоритм хешування.

Хешування та proof-of-work

Коли справа дійшла до інтеграції алгоритму хешування в блокчейн протоколи, біткоін використовував SHA256, тоді як Ethereum використовував модифікований SHA3 (KECCAK256) для свого PoW. Однак важливою якістю вибору хеш-функції для блокчейну з використанням доказу роботи є ефективність обчислень зазначеного хеш. Алгоритм хешування біткойна SHA256 може бути обчислений досить просто за допомогою спеціалізованого обладнання, відомого як спеціалізовані інтегральні схеми (або ASIC). Багато було написано про використання ASIC у майнінг пулі та про те, як вони роблять протокол спрямованим на централізацію обчислень. Тобто доказ роботи стимулює групи обчислювально-ефективних машин об'єднуватися в пули і збільшувати те, що ми позначаємо “хеш-потужністю”, або мірою кількості хешів, які машина може обчислити за інтервал часу. Ethereum, вибрав модифікований SHA3 відомий як KECCAK 256. Крім того, алгоритм PoW Ethereum - Dagger-Hashimoto, повинен був бути важко обчислюваним для апаратного забезпечення.

Чому біткоїн використовує подвійне шифрування SHA256?

Біткойн має цікавий спосіб хешування даних за допомогою SHA256, оскільки він виконує дві ітерації алгоритму у своєму протоколі. Зверніть увагу: це не контрзахід для атак на день народження, оскільки ясно, що якщо hash(x) = hash(y), то hash(hash(x))=hash(hash(y)). Натомість подвійний SHA256 використовується для пом'якшення "Атаки подовження повідомлення - тип атаки на хеш-функцію, що полягає в додаванні нової інформації в кінець вихідного повідомлення". Атака небезпечна тим, що можна змінити запит, а відповідно виконати те, за що цей запит відповідає (наприклад, переказ грошей)

SHA3 ​​не був єдиним проривом, який вийшов із конкурсу хешування NIST у 2006 році. Незважаючи на те, що SHA3 виграв, алгоритм, відомий як BLAKE, зайняв друге місце. Для реалізації шардингу Ethereum 2.0 використовує ефективніше. Алгоритм хешування BLAKE2b, який є високорозвиненою версією BLAKE від конкурентів, інтенсивно вивчається за його фантастичну ефективність порівняно з KECCAK256 за збереження високого ступеня безпеки. Обчислення BLAKE2b практично в 3 рази швидше, ніж KECCAK на сучасному процесорі.

Майбутнє алгоритмів хешування

Здається, що незалежно від того, що ми робимо, ми просто або (1) збільшуємо складність внутрішніх хеш-операцій, або (2) збільшуємо довжину хеш-виходу, сподіваючись, що комп'ютери атакуючих не будуть достатньо швидкими, щоб ефективно обчислювати її колізію. Ми покладаємося на двозначність попередніх прообразів односторонніх операцій для забезпечення безпеки наших мереж. Тобто мета безпеки алгоритму хешування полягає в тому, щоб зробити якомога складнішим для будь-кого, хто намагається знайти два значення, які хешуються на той самий висновок, незважаючи на те, що існує нескінченна кількість можливих зіткнень. «Як щодо майбутнього квантових комп'ютерів? Чи будуть алгоритми хешування безпечними? Коротка відповідь та поточне розуміння полягають у тому, що так, алгоритми хешування витримають випробування часом проти квантових обчислень. Те, що квантові обчислення зможуть зламати, - це проблеми, які мають сувору математичну структуру, засновану на акуратних трюках і теорії, як-от шифрування RSA. З іншого боку, алгоритми хешування мають менш формальну структуру у внутрішніх конструкціях. Квантові комп'ютери дійсно дають підвищену швидкість у обчисленні неструктурованих проблем, таких як хешування, але врешті-решт вони все одно грубо атакуватимуть так само, як комп'ютер сьогодні спробує це зробити. Незалежно від того, які алгоритми ми вибираємо для наших протоколів, зрозуміло, що ми рухаємося до обчислювально-ефективного майбутнього, і ми маємо використовувати наше найкраще судження, щоб вибрати правильні інструменти для роботи та ті, які, ми сподіваємось, витримають випробування часом.

_____________________________________________________________________________

______________________________________________________________________________

Нерідко при завантаженні торентів або безпосередньо самих файлів в описі стоїть щось на кшталт «ad33e486d0578a892b8vbd8b19e28754» (наприклад, ex.ua), нерідко з припискою «md5». Це хеш-код – результат, який видає хеш-функція після обробки вхідних даних. У перекладі з англійської хеш означає плутанину, марихуану, траву або страву з дрібно нарізаного м'яса та овочів. дуже і дуже складно, можна сказати, що практично неможливо. Тоді виникає запитання: «Навіщо взагалі потрібні всі ці вони видають незрозумілу абракадабру, яка ще й не розшифровується?». Про це й йтиметься у цій статті.

Що таке хеш-функція та як вона діє?

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

Навіщо потрібна хеш-функція?

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

Хеш-функції: якими вони буваютьт

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

1. Функція перевірки цілісності інформації

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

2. Криптографічна функція

Використовується для захисту від НД. Вони дозволяють перевірити, чи не відбулося спотворення даних у результаті НД під час передачі файлів через мережу. Справжній хеш в цьому випадку є загальнодоступним, а хеш отриманого файлу можна обчислити за допомогою різних програм. Такі функції мають довгий і стабільний термін роботи, а пошук колізій (можливих збігів результату від різних вихідних даних) дуже ускладнений. Саме такі функції використовують для зберігання БД паролів (SH1, SH2, MD5) та іншої цінної інформації.

3. Функція, призначена для створення ефективної структури даних

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

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

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

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

Примітка: Матеріал розрахований на звичайних користувачів і не містить багатьох технічних аспектів, проте для базового ознайомлення його більш ніж достатньо.

Що таке Хеш чи Хешування?

Почну із термінів.

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

Хешування- це процес перетворення вихідних текстів.

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

Як бачите, терміни мають дещо образний опис, з якого складно зрозуміти для чого це все потрібно. Тому відразу наведу невеликий приклад (про інші застосування розповім трохи пізніше). Допустимо, у вас є 2 файли розміром 10 Гб. Як можна швидко дізнатися який із них потрібний? Можна використовувати ім'я файлу, але його можна легко перейменувати. Можна дивитися дати, але після копіювання файлів дати можуть бути однаковими або в іншій послідовності. Розмір, як самі розумієте, мало чим може допомогти (особливо якщо розміри збігаються або ви не дивилися точні значення байтів).

Ось тут і потрібен цей самий Хеш, який є коротким блоком, що формується з вихідного тексту файлу. У цих двох файлів по 10 Гб буде два різні, але короткі Хеш-коди (щось на кшталт "ACCAC43535" і "BBB3232A42"). Використовуючи їх, можна буде швидко дізнатися потрібний файл, навіть після копіювання та зміни імен.

Примітка: У зв'язку з тим, що Хеш у комп'ютерному світі та в інтернеті дуже відоме поняття, то нерідко все те, що має відношення до Хеш, скорочують до цього самого слова Наприклад, фраза "у мене використовується Хеш MD5" у перекладі означає, що на сайті або десь ще використовується алгоритм хешування стандарту MD5.

Властивості Хеш-функцій

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

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

А тепер до самих властивостей Хеш-функцій:

1. На вхід може подаватися текст будь-якого розміру, а на виході виходить блок даних фіксованої довжини. Це випливає із визначення.

2. Хеш-сума тих самих текстів має бути однаковою. В іншому випадку, такі функції просто марні - це аналогічно до випадкового числа.

3. Хороша функція згортки повинна мати добрий розподіл. Погодьтеся, що якщо розмір вихідного Хеша, наприклад, 16 байт, то якщо функція повертає всього 3 різних значення для будь-яких текстів, то користі від такої функції і цих 16 байт ніякого (16 байт це 2^128 варіантів, що приблизно дорівнює 3, 4 * 10 ^ 38 ступеня).

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

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

6. Швидкість обчислення Хеша. Який толк від функції згортки, якщо вона довго обчислюватиметься? Жодної, адже тоді простіше дані файлів порівнювати або використовувати інший підхід.

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

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

Ось тепер можна переходити до питання "а навіщо це все?"

Навіщо потрібний Хеш?

Основні цілі у Хеш-функцій всього три (вірніше їх призначення).

1. Перевірка цілісності даних. В даному випадку все просто, така функція повинна обчислюватися швидко і дозволяти так само швидко перевірити, що, наприклад, завантажений з інтернету файл не пошкоджено під час передачі.

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

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

Де і як застосовується хеш?

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

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

Примітка: Раджу ознайомитися зі статтею пари порад для підвищення рівня безпеки паролів

2. У програмуванні, включаючи бази даних. Звичайно, найчастіше йдеться про структури даних, що дозволяють здійснювати швидкий пошук. Суто технічний аспект.

3. Під час передачі даних через мережу (включаючи Інтернет). Багато протоколів, таких як TCP/IP, включають спеціальні перевірочні поля, що містять Хеш-суму вихідного повідомлення, щоб якщо десь стався збій, то це не вплинуло на передачу даних.

4. Для різних алгоритмів, пов'язаних із безпекою. Наприклад, Хеш застосовується в електронних цифрових підписах.

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

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

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

Відомі Хеш-функції

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