Перегляд вихідного коду сторінки Одностороння функція стискання

В [[криптографія| криптографії]], '''одностороння функція стиснення'''&nbsp;— це така функція, яка перетворює два вхідні аргументи фіксованої довжини, на результат фіксованої довжини.{{Sfn|Menezes|Van Oorschot|Vanstone|2001|p=328}} Функція [[Одностороння функція|одностороння]] в тому сенсі, що важко вгадати аргументи значення функції для яких дорівнює заданій величині. Односторонні функції стиснення не пов'язані зі звичними алгоритмами [[стиснення даних]], які натомість можуть бути оберненими точно ([[стиснення без втрат]]) або приблизно ([[Стиснення з утратами|стиснення з втратами]]).

[[Файл: One-way compression.svg | thumb | 200px | right | Одностороння функція стиснення]]

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

Односторонні функції стиснення часто будуються з [[Блочний шифр| блочних шифрів]]. Для того, щоб перетворити будь-який звичайний блочний шифр в односторонню функцію стиснення, існують методи '''Девіса-Мейєра''', '''Матіса-Мейера-Осеаса''', '''Міагучі-Пренеля''' (функції стиснення одноблокової довжини), та '''MDC-2/Меєра-Шіллінга''', '''MDC-4''', '''Hirose''' (довжини два блоки). Ці методи докладно описані нижче. ({{iw|MDC-2}} - також назва хеш-функціх запатентованої [[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'').
* {{iw|Стійкість до колізій|||Collision resistance}}: Треба щоб знайти два такі різні аргументи для яких функція дає однаковий результат було важко, тобто зловмисник не повинен могти знайти пару повідомлень m1 ≠ m2 таких що ''hash''(''m1'') = ''hash''(''m2''). Через [[парадокс днів народження]] (див. також [[атака «днів народження»]]) існує 50% ймовірність знайти колізію за час приблизно 2<sup>n/2</sup> де n кількість біт у виході геш-функції. Таким чином атака на геш-функцію не повинна знаходити колізію за менш ніж 2<sup>n/2</sup> спроб.

В ідеалі, під "неможливістю" в стійкості до прообразу і другого прообразу слід розуміти обчислювальну складність приблизно 2<sup>n</sup>, де n - кількість біт у виході функції. Проте, особливо для випадку стійкості до другого прообразу це досить складна проблема.{{Citation needed}}

== Будова Меркле — Демґарда ==
{{Головна стаття|Будова Меркла-Демґарда}}

[[Файл:Merkle-Damgard hash big.svg|thumb|400px|right|Будова Меркла-Дамгарда, де IV&nbsp;— початкове значення згортки (фіксований вектор), f — функція стискання.]]

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

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

Останній блок повинен бути {{iw|доповнення (криптографія)|доповненим за довжиною||Padding (cryptography)}}.

Коли застосовується доповнення за довжиною (яке також називають MD-посилення ({{lang-en|MD-strengthening}})), атаки не здатні знайти колізії швидше за час парадоксу днів народження (2<sup>n/2</sup>, де n розмір блоку в бітах) якщо використана функція f стійка до колізій.<ref name="damgard89">Ivan Damgård. A design principle for hash functions. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 416–427. Springer, 1989.</ref><ref name="merkle89">Ralph Merkle. One way hash functions and DES. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 428–446. Springer, 1989.</ref> Таким чином, Будова Меркла-Демґардаt зводить задачу знаходження правильної геш-функції, до знаходження функції стискання.

Атака знаходження другого прообразу (маючи повідомлення m1 зловмисник знаходить інше повідомлення m2 таке що hash(m1) = hash(m2)) можлива, згідно [[Джон Келсі|Келсі]] та [[Брюс Шнайєр|Шнаєром]]<ref name="ks05">John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2<sup>n</sup> work. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 474–490. Springer, 2005.</ref> для 2<sup>k</sup>-блокового повідомлення за час k &times; 2<sup>n/2+1</sup>+2<sup>n-k+1</sup>. Складність більша за 2<sup>n/2</sup> але нижча за 2<sup>n</sup> при довгих повідомленнях, і для коротких повідомлень наближається до 2<sup>n</sup>.

== Побудова з блочних шифрів ==
[[Файл:Block cipher.svg|thumb|200px|right|Типовий сучасний блочний шифр]]

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

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

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

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

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

Якщо блочний шифр має {{iw|розмір блоку (криптографія)|розмір блоку||Block size (cryptography)}} наприклад 128 біт, методи одноблокової довжини створюють геш-функцію яка має розмір блоку 128 біт і дає геш розміром 128 біт. Методи стискання двоблокової довжини утворюють геші з розміром вдвічі більшим за розмір блоку блочного шифру. Таким чином 128-бітний шифр може перетворитися в 256-бітну геш-функцію.

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

{{section-stub|дата=жовтень 2018}}

== Структура Девіса-Мейєра ==
[[Файл:Davies-Meyer hash.svg|thumb|230px|right|Схема Девіса-Мейєра]]

В даній схемі блок повідомлення <math>m_{i}</math> і попереднє значення геш-функції <math>H_{i-1}</math> надходять в якості ключа й блоку відкритого тексту відповідно на вхід блочного шифру <math>E</math>. Одержаний в результаті шифрування блок закритого тексту підсумовується ([[Виключна диз'юнкція|операція XOR]]) з результатом попередньої ітерації гешування (<math>H_{i-1}</math>) для отримання наступного значення геш-функції (<math>H_{i}</math>). {{sfn | Авезова Яна Едуардівна | 2015 | p = 61}}

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

: <math>H_i = E_{m_i}{(H_{i-1})} \oplus {H_{i-1}}.</math>

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

Важливою властивістю конструкції Девіса-Мейєра є те, що навіть якщо базовий блок шифрування є повністю безпечним, можна обчислити [[Нерухома точка|нерухомі точки]] для побудови: для будь-якого <math>m</math> можна знайти значення <math>h</math> таке що <math>E_m(h) \oplus h = h</math> : просто нужно установить <math>h = E_m^{-1}(0)</math>.{{sfn|Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing|August 2001|p = 375}}

Безпека структури Девіса-Мейєра була вперше доведена Р.Вінтерніцом. {{Sfn | R. Winternitz. ''A secure one-way hash function built from DES.'' In Proceedings of the IEEE Symposium on Information Security and Privacy | 1984 | pp = 88-90}}

== Структура Матіса-Мейєра-Осеаса ==
[[Файл:Matyas-Meyer-Oseas hash.svg|thumb|230px|right|Схема Матіса-Мейєєра-Осеаса]]

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

У даній конструкції блок повідомлення <math>m_{i}</math> і попереднє значення хеш-функції <math>H_{i-1}</math> надходять в якості ключа й блоку відкритого тексту відповідно на вхід блочного шифру <math>E</math>. Але вже значення <math>H_{i-1}</math> піддається попередній обробці відповідно до розділу <math>g</math> через можливі відмінності в розмірах геш-суми й розмірі ключа шифру <math>E</math>. Ця функція реалізує відображення n-бітного значення хеш-функції в k-бітний ключ шифру <math>E</math>. В результаті застосування операції шифрування, виходить блок закритого тексту, який підсумовується з відповідним йому блоком відкритого тексту (<math>m_{i}</math>). {{Sfn | Авезова Яна Едуардівна | 2015 | pp = 61-62}}

: <math>H_i = E_{g(H_{i-1})}(m_i)\oplus H_{i-1}\oplus m_i.</math>

== Див. також ==
* [[Whirlpool (криптографія)]]
* [[Блочний шифр]]

== Література ==
* {{Cite book
| last1 = Menezes
| first1 = A. J
| last2 = Van Oorschot
| first2 = Paul C
| last3 = Vanstone
| first3 = Scott A
| title = Handbook of applied cryptography
| location = Boca Raton, Fla.; London
| date = 2001
| url = https://archive.org/details/handbookofapplie0000mene
| publisher = CRC
| isbn = 978-0-8493-8523-0
| ref = harv
| url-access = registration
}}
* Брюс Шнайер Прикладная криптография, 2006, 2-e изд.
* В.&nbsp;В.&nbsp;Ященко Введение в криптографию, 1999
* С.Баричев, Р.Серов Основы современной криптографии, 2001
* [http://studydoc.ru/doc/134761/neformal._naya-model._-narushitelya С.&nbsp;В.&nbsp;Дубров Основы современной криптографии]
* R. Winternitz A secure one-way hash function built from DES
* [http://jrnl.nau.edu.ua/index.php/Infosecurity/article/download/12955/18090 УДОСКОНАЛЕНА ФУНКЦІЯ ГЕШУВАННЯ MD4]

=== Наукові стаття ===
* [http://cyberrus.com/wp-content/uploads/2015/09/vkb_11_8.pdf Авезова Яна Эдуардовна СОВРЕМЕННЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ ХЭШ-ФУНКЦИЙ НА ПРИМЕРЕ ФИНАЛИСТОВ КОНКУРСА SHA-3]
* [http://www.hups.mil.gov.ua/periodic-app/article/1988/soivt_2012_2_23.pdf А.&nbsp;В.&nbsp;Антонов РАЗВИТИЕ МЕТОДА ПОСТРОЕНИЯ ХЕШ-ФУНКЦИИ]

== Примітки ==
{{reflist}}

[[Категорія:Криптографічні геш-функції]]
[[Категорія:Криптографічні примітиви]]