Хеш-функції: поняття та основи

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

Що це таке?

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

Характеристики

Розглянемо ключові характеристики досліджуваних алгоритмів. У числі таких:

наявність внутрішніх алгоритмів перетворення даних вихідної довжини в більш коротку послідовність символів;

відкритість для криптографічного перевірки;

наявність алгоритмів, що дозволяють надійно зашифрувати початкові дані;

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

У числі інших найважливіших властивостей хеш-функції:

здатність обробляти первинні масиви даних довільної довжини;

формувати хешірованние блоки фіксованої довжини;

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

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

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

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




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

Структура

Вивчимо те, якою може бути структура розглянутих функцій. Як ми відзначили вище, в серед головних вимог до розглянутих алгоритмів — забезпечення однонаправленості шифрування. Людина, що має в розпорядженні тільки хеш, практично не повинен мати можливості отримати на його основі вихідний документ. У якій структурі може бути представлена використовувана в подібних цілях хеш-функція? Приклад її складання може бути таким: H (hash, тобто, хеш) = f (T (текст), H1), де H1 — алгоритм обробки тексту T. Ця функція хеширует T таким чином, що без знання H1 відкрити його як повноцінний файл буде практично неможливо.

Використання хеш-функцій на практиці: завантаження файлів

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

Хеш-функція і ЕЦП

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

Перевірка паролів

Ще одна можлива область застосування хешування — організація алгоритмів перевірки паролів, встановлених для розмежування доступу до тих або іншим файловим ресурсів. Яким чином при вирішенні подібних завдань можуть бути задіяні ті чи інші види хеш-функцій? Дуже просто. Справа в тому, що на більшості серверів, доступ до яких підлягає розмежуванню, паролі зберігаються у вигляді хешування значень. Це цілком логічно — якщо б паролі були представлені у вихідному текстовому вигляді, хакери, які отримали доступ до них, могли б запросто читати секретні дані. У свою чергу, на основі хеш обчислити пароль непросто. Яким чином здійснюється перевірка доступу користувача при використанні розглянутих алгоритмів? Пароль, що вводиться користувачем, звіряється з тим, що зафіксований в хеш-функції, що зберігається на сервері. Якщо значення текстових блоків збігаються — користувач отримує необхідний доступ до ресурсів. В якості інструменту перевірки паролів може бути задіяна найпростіша хеш-функція. Але на практиці IT-фахівці найчастіше використовують комплексні багатоступінчасті криптографічні алгоритми. Як правило, вони доповнюються застосуванням стандартів передачі даних по захищеному каналу — так, щоб хакери не змогли знайти або обчислити пароль, переданий з комп'ютера користувача на сервер — до того, як він буде звірятися з хешірованнимі текстовими блоками.

Колізії хеш-функцій

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

Історія появи

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

Популярні стандарти хешування

Розглянемо тепер, в яких популярних стандарти можуть бути представлені хеш-функції. У числі таких — CRC. Даний алгоритм являє собою циклічний код, званий також контрольною сумою. Цей стандарт характеризується простотою і в той же час універсальністю — за допомогою нього можна хешировать самий широкий спектр даних. CRC — один з найпоширеніших алгоритмів, які не належать до криптографічних. У свою чергу, при шифруванні досить широке застосування знаходять стандарти MD4 і MD5. Ще один популярний криптографічний алгоритм — SHA-1. Зокрема, він характеризується розміром хеша 160 біт, що більше, ніж у MD5 — даний стандарт підтримує 128 біт. Є російські стандарти, що регулюють використання хеш-функцій, — ГОСТ Р 3411-94 а також замінив його ГОСТ Р 3411-2012. Можна відзначити, що величина хеша, передбачена алгоритмами, прийнятими в РФ, становить 256 біт. Стандарти, про які йде мова, можуть бути класифіковані за різними підставами. Наприклад, є ті, що використовують блочні алгоритми і спеціалізовані. Простота обчислень на основі стандартів першого типу часто супроводжується їх невисокою швидкістю. Тому в якості альтернативи блочних алгоритмів можуть задіюватися ті, що припускають менший обсяг необхідних обчислювальних операцій. До швидкодіючим стандартам прийнято відносити, зокрема, зазначені вище MD4 MD5 а також SHA. Розглянемо специфіку спеціальних алгоритмів хешування на прикладі SHA докладніше.

Особливості алгоритму SHA

Застосування хеш-функцій, що базуються на стандарті SHA, найчастіше здійснюється в області розробки засобів цифрового підпису документів DSA. Як ми зазначили вище, алгоритм SHA підтримує хеш 160 біт (забезпечуючи так званий «дайджест» послідовності символів). Спочатку розглянутий стандарт ділить масив даних на блоки по 512 біт. При необхідності, якщо довжина останнього блоку не дотягує до зазначеної цифри, структура файлу доповнюється 1 і необхідною кількістю нулів. Також в кінці відповідного блоку вписується код, що фіксує довжину повідомлення. Розглянутий алгоритм задіює 80 логічних функцій, за допомогою яких обробляється 3 слова, представлені в 32 розрядах. Також у стандарті SHA передбачено використання 4 констант.

Порівняння алгоритмів хешування

Вивчимо те, як співвідносяться властивості хеш-функцій, що належать до різних стандартів, на прикладі зіставлення характеристик російського стандарту ГОСТ Р 3411-94 і американського SHA, який ми розглянули вище. Насамперед, слід відзначити те, що алгоритм, розроблений в РФ, передбачає здійснення 4 операцій по шифруванню в розрахунку на 1 цикл. Це відповідає 128 раундів. У свою чергу, протягом 1 раунду при залученні SHA передбачається обчислення близько 20 команд, при тому, що лише раундів 80. Таким чином, використання SHA дозволяє протягом 1 циклу обробити 512 біт вихідних даних. У той час як російський стандарт здатний здійснити операції за цикл в 256 біт даних.

Специфіка новітнього російського алгоритму

Вище ми відзначили, що стандарт ГОСТ Р 3411-94 був замінений більш новим — ГОСТ Р 3411-2012 «Стрибог». Досліджуємо його специфіку докладніше. За допомогою даного стандарту можуть бути реалізовані, як і у випадку з алгоритмами, розглянутими вище, криптографічні хеш-функції. Можна відзначити, що новітній російський стандарт підтримує блок вхідних даних в обсязі 512 біт. Основні переваги ГОСТ Р 3411-2012:

високий рівень захищеності від злому шифрів;

надійність, підкріплена задіянням перевірених конструкцій;

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

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

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

Розглянемо більш детально, яким чином досліджувані нами типи алгоритмів можуть бути задіяні у сфері криптографії. Ключова вимога до відповідних функцій — стійкість до колізій, про які ми сказали вище. Тобто не повинні формуватися повторювані значення хеш-функції, якщо значення ці вже присутні в структурі сусіднього алгоритму. Іншим зазначеним вище критеріям криптографічні функції також повинні відповідати. Зрозуміло, що завжди є якась теоретична можливість відновлення вихідного файлу на основі хеш, особливо якщо в доступі є потужний обчислювальний інструмент. Проте подібний сценарій передбачається звести до мінімуму, завдяки надійним алгоритмами шифрування. Так, обчислити хеш-функцію буде дуже складно, якщо її обчислювальна стійкість відповідає формулі 2^{n/2}. Інший найважливіший критерій криптографічного алгоритму — зміна хеша у разі коригування початкового масиву даних. Вище ми відзначили, що стандарти шифрування повинні мати чутливістю на рівні 1 біта. Так, дане властивість — ключовий фактор забезпечення надійного захисту паролем доступу до файлів.

Повторне схеми

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

Блочний алгоритм

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