Вимоги до хеш-функцій
Хеш-функцією називається одностороння функція, призначена для отримання дайджесту або "відбитків пальців" файлу, повідомлення або деякого блоку даних.
Хеш-код створюється функцією Н: h = H (M)
Де М є повідомленням довільної довжини і h є хеш-кодом фіксованої довжини.
Хеш-функція Н, яка використовується для аутентифікації повідомлень, повинна мати наступні властивості:
1. Хеш-функція Н повинна застосовуватися до блоку даних будь-якої довжини.
2. Хеш-функція Н створює вихід фіксованої довжини.
3. Н (М) відносно легко (за поліноміальний час) обчислюється для будь-якого значення М.
4. Для будь-якого даного значення хеш-коду h обчислювально неможливо знайти M таке, що Н (M) = h.
5. Для будь-якого даного х обчислювально неможливо знайти y x, що H (y) = H (x).
6. Обчислювально неможливо знайти довільну пару (х, y) таку, що H (y) = H (x).
Перші три властивості вимагають, щоб хеш-функція створювала хеш-код для будь-якого повідомлення.
Четверте властивість визначає вимога однобічності хеш-функції: легко створити хеш-код по цим повідомленням, але неможливо відновити повідомлення з даного хеш-коду. Це властивість важливо, якщо аутентифікація з використанням хеш-функції включає секретне значення. Саме секретне значення може не надсилатися, проте, якщо хеш-функція не є односторонньою, противник може легко розкрити секретне значення.
Хеш-функція, яка задовольняє першим п'яти властивостям, називається простий або слабкою хеш-функцією. Якщо крім того здійснюється шістьма властивість, то така функція називається сильною хеш-функцією. Шосте властивість захищає проти класу атак, відомих як атака "день народження".
Все хеш-функції виконуються наступним чином. Вхідний значення (повідомлення, файл і т.п.) розглядається як послідовність n-бітних блоків. Вхідний значення обробляється послідовно блок за блоком, і створюється n-бітове значення хеш-коду.
Одним з найпростіших прикладів хеш-функції є побітно XOR кожного блоку:
Де Сi - i-ий біт хеш-коду, 1 i n,
k - число n-бітових блоків входу.
bij - i-ий біт в j-му блоці.
В результаті виходить хеш-код довжини n, відомий як поздовжній надлишковий контроль. Це ефективно при випадкових збоях для перевірки цілісності даних.
Часто при використанні подібного поздовжнього надлишкового контролю для кожного блоку виконується однобітний циклічний зсув після обчислення хеш-коду. Це дасть ефект "випадковості" входу і знищить будь-яку регулярність, яка присутня у вхідних значеннях.
Хоча другий варіант вважається кращим для забезпечення цілісності даних і запобігання від випадкових збоїв, він не може використовуватися для виявлення навмисних модифікацій переданих повідомлень. Знаючи повідомлення, атакуючий легко може створити нове повідомлення, яке має той же самий хеш-код. Для цього слід підготувати альтернативне повідомлення і потім приєднати n-бітний блок, який є хеш-кодом нового повідомлення, і блок, який є хеш-кодом старого повідомлення.
Розглянемо алгоритм отримання дайджесту повідомлення MD5 (RFC +1321), розроблений Роном Ривестом з MIT. Алгоритм отримує на вході повідомлення довільної довжини і створює в якості виходу дайджест повідомлення довжиною 128 біт.
ABCD - не започатковано вектор, що складається з 4 підвектора довжиною 8 шістнадцяткових цифр (4 байта). Yi - i-ий блок вихідного тексту, HMD5 - модуль, що складається з 4 циклічних обробок.
Хеш-функції сімейства SHA
Алгоритм отримує на вході повідомлення максимальної довжини 2 64 біт і створює в якості виходу дайджест повідомлення довжиною 160 біт.
Порівняння SHA-1 і MD5
Довжина повідомлення (в бітах)
Довжина блоку (в бітах)
Під безпекою треба розуміти стійкість до атак класу "день народження".
Хеш-функція ГОСТ 3411
Алгоритм ГОСТ 3411 є вітчизняним стандартом для хеш-функцій. Його структура досить сильно відрізняється від структури алгоритмів SHA-1,2 або MD5, в основі яких лежить алгоритм MD4.
Довжина хеш-коду, створюваного алгоритмом ГОСТ 3411, дорівнює 256 бітам. Алгоритм розбиває повідомлення на блоки, довжина яких також дорівнює 256 бітам. Крім того, параметром алгоритму є стартовий вектор хешування Н - довільне фіксоване значення довжиною також 256 біт.
Повідомлення обробляється блоками по 256 біт справа наліво.
Коди аутентифікації повідомлень - МАС
В даному випадку під МАС (Message Authentication Code) розуміється деякий аутентифікатор, що є певним способом обчисленим блоком даних, за допомогою якого можна перевірити цілісність повідомлення. В деякій мірі симетричне шифрування всього повідомлення може виконувати функцію аутентифікації цього повідомлення. Але в такому випадку повідомлення повинно містити достатню надмірність, яка дозволяла б перевірити, що повідомлення не було змінено. Надмірність може бути у вигляді певним чином відформатованого повідомлення, тексту на конкретній мові і т.п. Якщо повідомлення допускає довільну послідовність бітів (наприклад, зашифрований ключ сесії), то симетричне шифрування всього повідомлення не може забезпечувати його цілісність, так як при дешифрування в будь-якому випадку вийде послідовність бітів, правильність якої перевірити не можна. Тому набагато частіше використовується крітографіческі створений невеликий блок даних фіксованого розміру, так званий аутентифікатор або имитовставка, за допомогою якого перевіряється цілісність повідомлення. Цей блок даних може створюватися за допомогою секретного ключа, який поділяють відправник і одержувач. МАС обчислюється в той момент, коли відомо, що повідомлення коректно. Після цього МАС приєднується до повідомлення і передається разом з ним одержувачу. Одержувач обчислює МАС, використовуючи той же самий секретний ключ, і порівнює обчислене значення з отриманим. Якщо ці значення збігаються, то з великою часткою ймовірності можна вважати, що при пересиланні зміни повідомлення не відбулося.