Одностороння функція стискання

В криптографії, одностороння функція стиснення — це така функція, яка перетворює два вхідні аргументи фіксованої довжини, на результат фіксованої довжини.^[1] Функція одностороння в тому сенсі, що важко вгадати аргументи значення функції для яких дорівнює заданій величині. Односторонні функції стиснення не пов'язані зі звичними алгоритмами стиснення даних, які натомість можуть бути оберненими точно (стиснення без втрат) або приблизно (стиснення з втратами).

Одностороння функція стиснення

Одностороння функція стиснення використовується, наприклад, в структурі Меркла-Демґардаа всередині криптографічних геш-функцій.

Односторонні функції стиснення часто будуються з блочних шифрів. Для того, щоб перетворити будь-який звичайний блочний шифр в односторонню функцію стиснення, існують методи Девіса-Мейєра, Матіса-Мейера-Осеаса, Міагучі-Пренеля (функції стиснення одноблокової довжини), та MDC-2/Меєра-Шіллінга, MDC-4, Hirose (довжини два блоки). Ці методи докладно описані нижче. (MDC-2^[en] - також назва хеш-функціх запатентованої IBM.)

Стиснення

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

Наприклад, хай аргумент А має довжину в 128 біт, аргумент B теж 128 біт, і вони стискуються в один результат довжини 128 біт. Це те ж саме, якщо б один-єдиний 256-бітовий аргумент стискувався в 128-бітний результат.

Деякі функції стиснення не стискують вдвічі, а з якимось іншим коефіцієнтом. Наприклад, аргумент А може бути 256-бітовим, а аргумент B 128-бітовим, і вони можуть стискатися в 128 біт. Тобто, в цілому 384 вхідних бітів стискаються разом до 128 вихідних бітів.

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

Односторонність

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

• Легко обчислити: Якщо відомі аргументи, легко отримати результат.
• Стійкість до прообразу: Якщо зловмисник знає лише вихідні дані, для нього буде нереально обчислити вхідні. Іншими словами, для результату функції h, неможливо обчислити m таке що hash(m)=h.
• Стійкість до другого прообразу: Маючи вхідні дані m1 вихідними для яких є h, треба щоб знайти інше значення m2 на виході для якого теж було h тобто hash(m1)=hash(m2).
• Стійкість до колізій^[en]: Треба щоб знайти два такі різні аргументи для яких функція дає однаковий результат було важко, тобто зловмисник не повинен могти знайти пару повідомлень m1 ≠ m2 таких що hash(m1) = hash(m2). Через парадокс днів народження (див. також атака «днів народження») існує 50% ймовірність знайти колізію за час приблизно 2^n/2 де n кількість біт у виході геш-функції. Таким чином атака на геш-функцію не повинна знаходити колізію за менш ніж 2^n/2 спроб.

В ідеалі, під "неможливістю" в стійкості до прообразу і другого прообразу слід розуміти обчислювальну складність приблизно 2ⁿ, де n - кількість біт у виході функції. Проте, особливо для випадку стійкості до другого прообразу це досить складна проблема.^{[джерело?]}

Будова Меркле — Демґарда

Будова Меркла-Дамгарда, де IV — початкове значення згортки (фіксований вектор), f — функція стискання.

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

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

Останній блок повинен бути доповненим за довжиною^[en].

Коли застосовується доповнення за довжиною (яке також називають MD-посилення (англ. MD-strengthening)), атаки не здатні знайти колізії швидше за час парадоксу днів народження (2^n/2, де n розмір блоку в бітах) якщо використана функція f стійка до колізій.^[2][3] Таким чином, Будова Меркла-Демґардаt зводить задачу знаходження правильної геш-функції, до знаходження функції стискання.

Атака знаходження другого прообразу (маючи повідомлення m1 зловмисник знаходить інше повідомлення m2 таке що hash(m1) = hash(m2)) можлива, згідно Келсі та Шнаєром^[4] для 2^k-блокового повідомлення за час k × 2^n/2+1+2^n-k+1. Складність більша за 2^n/2 але нижча за 2ⁿ при довгих повідомленнях, і для коротких повідомлень наближається до 2ⁿ.

Побудова з блочних шифрів

Типовий сучасний блочний шифр

Також, односторонні функції стискання будують з блочних шифрів.

Блочні шифри (як і односторонні функції стискання) отримують на вхід дві послідовності фіксованої довжини (ключ і відкритий текст) і повертають одну вихідну послідовність (шифротекст) яка має таку саму довжину як і вхідний відкритий текст.

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

Деякими методами для перетворення звичайного блочного шифру в односторонню функцію стискання є методи Девіса-Меєра, Матіаса-Меєра-Осеаса, Міягучі-Пренеля (функції стискання одноблокової довжини) та MDC-2, MDC-4, Хіроші (функції стискання двоблокової довжини).

Функції стискання одноблокової довжини виводять скільки ж біт, скільки обробляється використаним блочним шифром. Відповідно, функції стискання двоблокової довжини виводять вдвічі більше біт.

Якщо блочний шифр має розмір блоку^[en] наприклад 128 біт, методи одноблокової довжини створюють геш-функцію яка має розмір блоку 128 біт і дає геш розміром 128 біт. Методи стискання двоблокової довжини утворюють геші з розміром вдвічі більшим за розмір блоку блочного шифру. Таким чином 128-бітний шифр може перетворитися в 256-бітну геш-функцію.

Ці методи потім використовуються в будові Меркле — Демґарда і їх детальніше розглядають нижче.

Структура Девіса-Мейєра

Схема Девіса-Мейєра

В даній схемі блок повідомлення ${\displaystyle m_{i}}$ і попереднє значення геш-функції ${\displaystyle H_{i-1}}$ надходять в якості ключа й блоку відкритого тексту відповідно на вхід блочного шифру ${\displaystyle E}$. Одержаний в результаті шифрування блок закритого тексту підсумовується (операція XOR) з результатом попередньої ітерації гешування (${\displaystyle H_{i-1}}$) для отримання наступного значення геш-функції (${\displaystyle H_{i}}$). ^[5]

В математичних позначеннях схему Девіса-Мейєра можна записати як:

${\displaystyle H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}.}$

Якщо блоковий шифр використовує, наприклад, 256-бітний ключ, то кожен блок повідомлень (${\displaystyle m_{i}}$) являє собою 256-бітний фрагмент повідомлення. Якщо ж блоковий шифр використовує розмір блоку в 128 біт, то вхідні й вихідні значення хеш-функції в кожному раунді становлять 128 біт.

Важливою властивістю конструкції Девіса-Мейєра є те, що навіть якщо базовий блок шифрування є повністю безпечним, можна обчислити нерухомі точки для побудови: для будь-якого ${\displaystyle m}$ можна знайти значення ${\displaystyle h}$ таке що ${\displaystyle E_{m}(h)\oplus h=h}$ : просто нужно установить ${\displaystyle h=E_{m}^{-1}(0)}$.^[6]

Безпека структури Девіса-Мейєра була вперше доведена Р.Вінтерніцом. ^[7]

Структура Матіса-Мейєра-Осеаса

Схема Матіса-Мейєєра-Осеаса

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

У даній конструкції блок повідомлення ${\displaystyle m_{i}}$ і попереднє значення хеш-функції ${\displaystyle H_{i-1}}$ надходять в якості ключа й блоку відкритого тексту відповідно на вхід блочного шифру ${\displaystyle E}$. Але вже значення ${\displaystyle H_{i-1}}$ піддається попередній обробці відповідно до розділу ${\displaystyle g}$ через можливі відмінності в розмірах геш-суми й розмірі ключа шифру ${\displaystyle E}$. Ця функція реалізує відображення n-бітного значення хеш-функції в k-бітний ключ шифру ${\displaystyle E}$. В результаті застосування операції шифрування, виходить блок закритого тексту, який підсумовується з відповідним йому блоком відкритого тексту (${\displaystyle m_{i}}$). ^[8]

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}.}$

Див. також

• Whirlpool (криптографія)
• Блочний шифр

Література

• Menezes, A. J; Van Oorschot, Paul C; Vanstone, Scott A (2001). Handbook of applied cryptography. Boca Raton, Fla.; London: CRC. ISBN 978-0-8493-8523-0.
• Брюс Шнайер Прикладная криптография, 2006, 2-e изд.
• В. В. Ященко Введение в криптографию, 1999
• С.Баричев, Р.Серов Основы современной криптографии, 2001
• С. В. Дубров Основы современной криптографии
• R. Winternitz A secure one-way hash function built from DES
• УДОСКОНАЛЕНА ФУНКЦІЯ ГЕШУВАННЯ MD4

Наукові стаття

• Авезова Яна Эдуардовна СОВРЕМЕННЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ ХЭШ-ФУНКЦИЙ НА ПРИМЕРЕ ФИНАЛИСТОВ КОНКУРСА SHA-3
• А. В. Антонов РАЗВИТИЕ МЕТОДА ПОСТРОЕНИЯ ХЕШ-ФУНКЦИИ

Примітки

1. Menezes, Van Oorschot та Vanstone, 2001, с. 328.
2. Ivan Damgård. A design principle for hash functions. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 416–427. Springer, 1989.
3. Ralph Merkle. One way hash functions and DES. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 428–446. Springer, 1989.
4. John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2ⁿ work. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 474–490. Springer, 2005.
5. Авезова Яна Едуардівна, 2015, с. 61.
6. Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing та August 2001, с. 375.
7. R. Winternitz. A secure one-way hash function built from DES. In Proceedings of the IEEE Symposium on Information Security and Privacy, 1984, с. 88—90.
8. Авезова Яна Едуардівна, 2015, с. 61—62.