Перевірка захищеності Хеш-функції

Підпис і повідомлення передаються разом у вигляді пари (m, s). Перевірка пари складається з трьох етапів.

1. Дешифрування s шляхом піднесення до степеню e, що являє собою відкритий ключ: h^’ = s^e mod n.

2. Обчислення h(m) за отриманим m.

3. Перевірка умови h^’ = h(m). Якщо умова виконується, підпис правильний. В іншому разі – ні.

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

Зловмисник вибирає випадкове число r | 1 < r < n, і обчислює h^’ = r^e mod n.

Він знаходить прообраз h^’, тобто таке значення m, що h(m) = h^’ (для стандартної хеш-функції це цілком можливо).

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

Відправник вибирає два повідомлення m і m^’, такі, що h(m) = h(m^’).

Він підписує m і відправляє (m, s). Потім він відмовляється від свого повідомлення, стверджуючи, що відправляв повідомлення m^’.

Яка загроза міститься у цій атаці. Припустимо, m – електронний чек на 10000 грн., а m^’ – чек на суму 10 грн. Тоді відмова відправника породжує велику проблему. Враховуючи парадокс днів народження, захищені від колізій хеш-функції будуються складніше, ніж односторонні. Щоб знайти повторення у значеннях хеш-функції f, необхідно запам’ятовувати результати обчислень f(x₁), f(x₂) f(x₃), і так далі, доки не виявиться повторення. Якщо значення функції f має довжину n бітів, то очікуваний збіг з’явиться після О(2^n/2) ітерацій. Для порівняння згадаємо, що для обчислення прообразу при відомому значенні функції f очікуваний об’єм обчислень має порядок О(2ⁿ). Отже, для досягнення необхідного рівня стійкості функція, стійка відносно колізій і визначена на множині рядків довжиною 80 бітів повинна приймати значення, що належать множині 160-бітових рядків. Але і цього ще недостатньо. Криптографічна хеш-функція повинна мати властивість захищеності від других прообразів. Ця властивість полягає в тому, що за отриманим повідомленням m повинно бути практично неможливо знайти таке m^’ ¹ m, для якого h(m) = h(m^’). Ця вимога забезпечує стійкість проти наступної атаки.

Користувач B отримує підписане повідомлення (m, s).

Користувач B знаходить інше повідомлення m^’, для якого h(m) = h(m^’).

Користувач B ставить підпис користувача A на своєму повідомленні m^’ і відправляє (m^’, s) від імені A. У підсумку криптографічні хеш-функції повинні мати три властивості: а) захищеність від відновлення прообразів – повинно бути неможливо у обчислювальному відношенні знайти повідомлення з поданим значенням хеш–функції; б) захищеність від колізій – неможливо у обчислювальному відношенні знайти два повідомлення з одним і тим же значенням хеш-функції; в) захищеність від других прообразів – за поданим повідомленням неможливо у обчислювальному відношенні знайти інше повідомлення з тим же значенням хеш-функції.

Проаналізуємо зв’язок між цими властивостями.

Лема 1. Властивість захищеності від відновлення прообразів сильніше захищеності від колізій і других прообразів.

Доведення. Нехай h – функція, а О - оракул (алгоритм), який зламує захищеність від відновлення прообразів функції h, тобто за поданим y знаходить такий x, що h(x) = y. Тоді, використовуючи оракула, можна знайти колізію. Дійсно, вибравши випадкове x, можна підрахувати y = h(x), а підставивши y в оракул, можна отримати x^’ таке, що y = h(x^’). Оскільки область визначення функції h нескінчена, ймовірність події x = x^’ близька до нуля. Тому пара (x, x^’) – колізія. Аналогічно можна показати, що за допомогою оракула О можна знайти другий прообраз. Лема 2. Захищеність від других прообразів сильніше захищеності від колізій. Доведення. Нехай існує оракул О, який за поданим x може знайти x^’ ¹ x, для якого h(x^’) = h(x). Тоді для будь-якого повідомлення m₁ за допомогою оракула О можна отримати інше повідомлення m₂, таке, що h(m₁) = h(m₂). А це означає, що m₁ і m₂ утворюють колізію. Криптографічні хеш-функції, захищені від колізій, можна використовувати як основу MAC. Одна з можливостей побудови MAC на основі хеш-функції полягає у приєднанні до повідомлення ключа і застосуванні до такої конструкції хеш-функції.

MAC = h(m || k).

Для підвищення стійкості цей метод застосовують у модифікованому вигляді:

HMAC = h(k||P₁|| h(k|| P₂||m)),

де P₁, P₂ – послідовності символів, що використовуються для поповнення вхідних даних до повних блоків.

Хеш-функції можна також розглядати як спеціальний тип кодів виявлення втручання (MDC – manipulation detection code). Наприклад, хеш-функцію можна використовувати для захисту цілісності великих файлів так, як це робиться в деяких програмах захисту від вірусів. А саме, обчислюється значення хеш-функції від вмісту файлу і або зберігається в якомусь безпечному місці (наприклад, на дискеті, схованій у сейф), або розміщується у файл з подібними даними, який потім підписується цифровим підписом.

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