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

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

Постановка задачі

Хеш-функції, що тривалий час використовуються в комп'ютерних науках, являють собою функції, математичні або інші, які отримують на вхід рядок змінної довжини (називається прообразом) і перетворюють її на рядок фіксованої, зазвичай меншої, довжини (називається значенням хеш-функції) . Як простий хешфункції можна розглядати функцію, яка отримує прообраз і повертає байт, що є XOR всіх вхідних байтів. Сенс хеш-функції полягає у отриманні характерної ознаки, прообразу-значення, яким аналізуються різні прообрази під час вирішення зворотного завдання. Так як зазвичай хеш-функція є співвідношення "багато до одного", неможливо з усією діловістю сказати, що два рядки збігаються, але їх можна використовувати, отримуючи прийнятну оцінку точності. Однонаправлена хеш-функція - це хеш-функція, яка працює тільки в одному напрямку. Легко обчислити значення хеш-функції прообразу, але важко створити прообраз, значення хеш-функції якого дорівнює заданій величині. Згадані раніше хеш-функції, взагалі кажучи, не є односпрямованими: задавши конкретний байт, не важко створити рядок байтів, XOR яких дає задане значення. З односпрямованою хеш-функцією такий варіант неможливий. Хеш-функція є відкритою, таємниці її розрахунку немає. Безпека односпрямованої хеш-функції полягає саме у її односпрямованості. Вихід не має видимої залежності від входу. Зміна одного біта прообразу призводить до зміни (в середньому) половини бітів значення хеш-функції, що також відомо як лавинний ефект.Обчислювально неможливо знайти прообраз, що відповідає заданому значенню хеш-функції

Вимоги

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

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

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

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

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

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

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

Принципи побудови

Ітеративна послідовна схема

У випадку, в основі побудови хеш-функції лежить ітеративна послідовна схема (Структура Меркля-Дамгарда). Ядром алгоритму єстискаюча функція- перетворенняkвхідних уnвихідних біт, деn- розрядність хеш-функції, аk- довільне число більшеn. При цьому стискаюча функція повинна задовольняти всі умови криптостійкості.

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

p align="justify"> При проектуванні хеш-функцій на основі ітеративної схеми виникає проблема з розміром вхідного потоку даних. Розмір вхідного потоку даних повинен бути кратний(k-n). Як правило, перед початком алгоритму дані розширюються якимось заздалегідь відомим способом.

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

Стискаюча функція на основі симетричного блочного алгоритму

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

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

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

Основним недоліком хеш-функцій, спроектованих на основі блокових алгоритмів є низька швидкість роботи. Необхідну криптостійкість можна забезпечити і меншу кількість операцій над вхідними даними. Існують швидші алгоритми хешування, спроектованих самостійно, з нуля, виходячи з вимог криптостійкості (найпоширеніші з них - MD5, SHA-1, SHA-2 та ГОСТ Р 34.11-94).

Застосування

Електронний цифровий підпис

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

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

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

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

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

Прикладом у разі можуть бути ОС GNU/Linux і Microsoft Windows. Вони зберігаються лише хеш-значення парольних фраз з облікових записів користувачів.

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

Нехай якийсь клієнт, з ім'ям name, здійснює аутентифікацію за парольною фразою, pass, на якомусь сервері. На сервері зберігаєтьсязначення хеш-функції H(pass, R2), де R2 - псевдовипадкове, заздалегідь обране число. Клієнт посилає запит (name, R1), де R1 - псевдовипадкове, щоразу нове число. У відповідь сервер надсилає значення R2. Клієнт обчислює значення хеш-функції H(R1,H(pass,R2)) та посилає його на сервер. Сервер також обчислює значення H(R1,H(pass,R2)) та звіряє його з отриманим. Якщо значення збігаються, автентифікація вірна.

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

Випадковий оракул

Нагадаємо властивість перемішування, яке властиво функції хешування: при будь-якому аргументі хешування не відрізняється з обчислювальної точки зору від рядка бітів, рівномірно розподілених в області значень функції. Якщо замінити останнє вираз фразою " належить генеральної сукупності рівномірно розподілених величин " , ми матимемо дуже потужну гіпотетичну функцію, звану випадковий оракул (randome oracle). Він має три властивості: детермінованість, ефективність, рівномірність розподілу результуючих значень. Однак, всі відомі обчислювальні моделі тією чи іншою мірою не відповідають моделі випадкового оракула. Рівномірність і детермінованість величин, що обчислюються випадковим оракулом, означає, що ентропія його результатів вища, ніж ентропія чисел, що надходять на вхід. Оскільки властивості перемішування, яким володіє хеш-функція є лише припущенням обчислювального характеру, реальна хеш-функція повинна забезпечувати лише обчислювальну нерозрізненість, тобто результати повинні мати певний розподіл ймовірностей у сфері значень, яке неможливо визначити заполіноміальний час. Отже, реальні функції хешування лише імітують поведінку випадкового оракула, хоч і з високою точністю.

Атака на основі парадоксу днів народжень

Припустимо, що функція хешування h справді є випадковим оракулом. В атаці за методом квадратного кореня (атака на основі парадоксу днів народження) передбачається, що для виявлення колізій з ненульовою ймовірністю достатньо виконати 2 ступеня h/2 випадкових обчислень значення функції хешування. Для організації атаки на основі парадоксу днів народжень атакуючий повинен згенерувати пари "повідомлення-хешоване значення", поки не виявлятимуться два повідомлення m і m`, що задовольняють умовам m не дорівнює m`, h(m)=h(m`). Така пара повідомлень називається колізією функції хешування h. Наприклад, функції хешироанія SHA-1 виконується умова h=160, отже його стійкість з урахуванням феномена днів народження оцінюється величиною 2 80 .