Topic 62
Електронний цифровий підпис
2. Односпрямовані хеш-функції
Хеш-функція призначена для стиснення документа М, що підписується, до декількох десятків або сотень біт. Хеш-функція h(•) приймає як аргумент повідомлення (документ) М довільної довжини і повертає хеш-значення h(М)=Н фіксованої довжини. Зазвичай хешована інформація є стислим двійковим поданням основного повідомлення довільної довжини. Слід зазначити, що значення хеш-функції h(М) складно залежить від документа М і дозволяє відновити сам документ М.
Хеш-функція повинна задовольняти цілу низку умов:
- хеш-функція має бути чутливою до всіляких змін у тексті М, таких як вставки, викиди, перестановки тощо;
- хеш-функція повинна мати властивість незворотності, тобто завдання підбору документа М', який мав би необхідне значення хеш-функції, має бути обчислювально нерозв'язною;
- ймовірність того, що значення хеш-функцій двох різних документів (незалежно від їх довжин) збігатимуться, має бути мізерно мала.
Більшість хеш-функцій будується на основі односпрямованої функції f(•), яка утворює вихідне значення довжиною n при завданні двох вхідних значень довжиною п. Цими входами є блок вихідного тексту М, та хеш-значення Ні-1 попереднього блоку тексту (рис.1 ):
Хеш-значення, що обчислюється при введенні останнього блоку тексту, стає хеш-значенням всього повідомлення М.
Рис.1. Побудова односпрямованої хеш-функції
В результаті односпрямована хеш-функція завжди формує вихід фіксованої довжини n (незалежно від довжини тексту).
Алгоритм безпечного хешування SНА
Алгоритм безпечного хешування SНА(Secure Hash Algorithm) розроблений НІСТ та АНБ США у рамках стандарту безпечного хешування SHS (Secure Hash Standard) у 1992 р. Алгоритм хешування SНА призначений для використання спільно з алгоритмом цифрового підпису DSA.
При введенні повідомлення М довільної довжини менше 264 біт алгоритм SНА виробляє 160-бітове вихідне повідомлення, зване дайджестом повідомлення МD (Message Digest). Потім цей дайджест повідомлення використовується як вход алгоритму DSA, який обчислює цифровий підпис повідомлення М. Формування цифрового підпису для дайджеста повідомлення, а не для самого повідомлення підвищує ефективність процесу підписання, оскільки дайджест повідомлення зазвичай набагато коротше самого повідомлення.
Такий же дайджест повідомлення повинен обчислюватися користувачем, що перевіряє отриманий підпис, при цьому як вход в алгоритм SНА використовується отримане повідомлення М.
Алгоритм хешування SНА названий безпечним, тому що він спроектований таким чином, щоб було обчислювально неможливо відновити повідомлення, що відповідає даному дайджесту, а також знайти два різні повідомлення, які дадуть однаковий дайджест. Будь-яка зміна повідомлення при передачі з дуже великою ймовірністю викликає зміну дайджеста, і прийнятий цифровий підпис не пройде перевірку.
Розглянемо докладніше роботу алгоритму хешування SНА. Насамперед вихідне повідомлення М доповнюють так, щоб воно стало кратним 512 біт. Додаткове набивання повідомлення виконується наступним чином: спочатку додається одиниця, потім йдуть стільки нулів, скільки необхідно для отримання повідомлення, яке на 64 біта коротше, ніж кратне 512, і нарешті додають 64-бітове уявлення довжини вихідного повідомлення.
Ініціалізується п'ять 32-бітових змінних увигляді:
А = 0 х 6 7 4 5 2 3 0 1
В = 0 х Е F З D А В 8 9
С = 0 х 9 8 В А D С F Е
D = 0 x 1 0 3 2 5 4 7 6
Е = 0 х З 3 D 2 Е 1 F 0
Потім розпочинається головний цикл алгоритму. У ньому обробляється по 512 біт співобіцяння по черзі для всіх 512-бітових блоків, які є в повідомленні. Перші п'ять змінних А, В, С, D, Е копіюються інші змінні a, b, с, d, е:
Головний цикл містить чотири цикли по 20 операцій кожен. Кожна операція реалізує нелінійну функцію від трьох із п'яти змінних а, b, с, d, е, а потім здійснює зсув і додавання.
Алгоритм SНА має наступний набір нелінійних функцій:
ft (Х, Y, Z) = (X Ù Y) Ú (( Ø X) Ù Z) для t = 0. 19,
ft (Х, Y, Z) = Х Å Y Å Z для t = 20. 39,
ft (Х, Y, Z) = (X Ù Y) Ú (X Ù Z) Ú (Y Ù Z) для t = 40. 59,
ft (Х, Y, Z) = Х Å Y Å Z для t = 60. 79,
де t – номер операції.
В алгоритмі використовуються також чотири константи:
Кt = 0х5А827999 для t = 0. 19,
Кt = 0х6ЕD9ЕВА1 для t = 20. 39,
Кt = 0х8F1ВВСDС для t = 40. 59,
Кt = 0хСА62С1D6 для t = 60. 79.
Блок повідомлення перетворюється з шістнадцяти 32-бітових слів (М0. М15) у вісімдесят 32-бітових слів (W0. W79) за допомогою наступного алгоритму:
де t – номер операції (для t = 1. 80),
Wt - t-й субблок розширеного повідомлення,
З урахуванням введених позначень головний цикл із вісімдесяти операцій можна описати так:
Схема виконання однієї операції показано на рис.2.
Після закінчення головного циклу значення а, b, с, d і е складаються з А,, С, D і Е відповідно, і алгоритм приступає до обробки наступного 512-бітового блоку даних. Остаточний вихідформується як конкатенації значень А, У, З, D і Е.
Рис.2. Схема виконання однієї операції алгоритму SHA
Оскільки алгоритм SНА видає 160-бітове хеш-значення, він більш стійкий до атак повного перебору та атак "дня народження", ніж більшість інших алгоритмів хешування, що формують 128-бітові хеш-значення.
Односпрямовані хеш-функції на основі симетричних блокових алгоритмів
Однонаправлену хеш-функцію можна побудувати, використовуючи симетричний блоковий алгоритм. Найбільш очевидний підхід у тому, щоб шифрувати повідомлення М у вигляді блочного алгоритму як СВС чи СFВ з допомогою фіксованого ключа і деякого вектора ініціалізації IV. Останній блок шифртексту можна розглядати як хеш-значення повідомлення М. При такому підході не завжди можливо побудувати безпечну односпрямовану хеш-функцію, але завжди можна отримати код автентифікації МАС (Message Authentication Code).
Більш безпечний варіант хеш-функції можна отримати, використовуючи блок повідомлення як ключ, попереднє хеш-значення - як вход, а поточне хеш-значення - як вихід. Реальні хеш-функції проектуються ще складнішими. Довжина блоку зазвичай визначається довжиною ключа, а довжина хеш-значення збігається з довжиною блоку.
Рис.3. Узагальнена схема формування хеш-функції
Оскільки більшість блокових алгоритмів є 64-бітовими, деякі схеми хешування проектують так, щоб хеш значення мало довжину, рівну подвійній довжині блоку.
Якщо прийняти, що одержувана хеш-функція коректна, безпека схеми хешування базується на безпеці блочного алгоритму, що лежить в її основі. Схема хешування, у якої довжина хеш-значення дорівнює довжині блоку, показанана рис.3. Її робота описується виразами:
де Ін – деяке випадкове початкове значення; А, В і С можуть набувати значення Мі, Ні-1, (Мі Å Ні-1) або бути константами.
Таблиця 1 Схеми безпечного хешування, у яких довжина хеш-значення дорівнює довжині блоку
Повідомлення М розбивається на блоки Мi прийнятої довжини, що обробляються по черзі.
Три різні змінні А, і С можуть приймати одне з чотирьох можливих значень, тому в принципі можна отримати 64 варіанти загальної схеми цього типу. З них 52 варіанти є тривіально слабкими, або небезпечними. Інші 12 безпечних схем хешування перераховані у табл.1.
Перші чотири схеми хешування, що є безпечними за всіх атак, наведено на рис.4.
Рис.4. Чотири схеми безпечного хешування
український стандарт ГОСТ Р 34.11-94 визначає алгоритм та процедуру обчислення хеш-функції для будь-яких послідовностей двійкових символів, що застосовуються укриптографічних методів обробки та захисту інформації. Цей стандарт базується на блоковому алгоритмі шифрування ГОСТ 28147-89, хоча в принципі можна було б використовувати й інший блоковий алгоритм шифрування з 64-бітовим блоком і 256-бітовим ключем.
Ця хеш-функція формує 256-бітове хеш-значення.
Функція стиснення Ні = f (Мi, Нi-1) (обидва операнда Мі та Ні-1 є 256-бітовими величинами) визначається наступним чином:
1. Генеруються 4 ключі шифрування Кj, j = 1. 4, шляхом лінійного змішування Мі, Ні-1 та деяких констант Сj.
2. Кожен ключ Кj використовують для шифрування 64-бітових підслів hі слова Нi-1 в режимі простої заміни: Si = EKj(hj).
Результуюча послідовність S4, S3, S2, S1 довжиною 256 біт запам'ятовується у часовій змінній S.
3. Значення Ні є складною, хоча й лінійною функцією змішування S, Мi та Нi-1.
При обчисленні остаточного хеш-значення повідомлення М враховуються значення трьох пов'язаних між собою змінних:
Нn – хеш-значення останнього блоку повідомлення;
Z-значення контрольної суми, одержуваної при додаванні по модулю 2 всіх блоків повідомлення;
L – довжина повідомлення.
Ці три змінні та доповнений останній блок М' повідомлення об'єднуються в остаточне хеш-значення таким чином:
Ця хеш-функція визначена стандартом ГОСТ Р 34.11-94 для використання спільно з українським стандартом електронного цифрового підпису.