Перегляд вихідного коду сторінки Будова Меркла-Демґарда

'''Будова Меркла-Демґарда''' або '''геш-функція Меркла-Демґарда'''&nbsp;— це метод будови стійкої до колізій [[криптографічна геш-функція|криптографічної геш-функції]] зі стійкої до колізій [[однобічна функція стискання|однобічної функції стискання]].<ref name=GoldwasserBellare>Shafi Goldwasser|Goldwasser, S. and Bellare, M. [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"] {{Webarchive|url=https://web.archive.org/web/20120421084751/http://cseweb.ucsd.edu/~mihir/papers/gb.html |date=2012-04-21 }}. Summer course on cryptography, MIT, 1996-2001</ref>{{rp|145}} Цей підхід використовується багатьма розповсюдженими алгоритмами такими як [[MD5]], [[SHA1]] і [[SHA2]].

Будова Меркла-Демґарда була описана в Ph.D. тезах Ралфа Меркла в 1979.<ref>R.C. Merkle. [http://www.merkle.com/papers/Thesis1979.pdf ''Secrecy, authentication, and public key systems.''] {{Webarchive|url=https://web.archive.org/web/20180814211110/http://www.merkle.com/papers/Thesis1979.pdf |date=14 серпня 2018 }} Stanford Ph.D. thesis 1979, pages 13-15.</ref> [[Ральф Меркле]] і [[Іван Демґард]] незалежно довели, що якщо використати прийнятну схему доповнення і стійку до колізій функцію стискання, тоді геш-функція також буде стійкою до колізій.<ref>R.C. Merkle. ''A Certified Digital Signature''. In Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 218-238.</ref><ref>I. Damgård. ''A Design Principle for Hash Functions''. In Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 416-427.</ref>

Геш-функція Меркла-Демґарда спочатку застосовує [[#МД-сумісне доповнення|МД-сумісне доповнення]] отримуючи вихід довжини кратної до певного числа (наприклад 512 або 1024) — бо функція стискання не може обробити вхідні дані довільного розміру. Тоді геш-функція розбиває вхідні дані на блоки умовленого розміру і обробляє їх по одному функцією стискання, щоразу використовуючи блок на вході і блок утворений попереднім раундом.<ref name=GoldwasserBellare />{{rp|146}} З метою зробити будову безпечною, Меркл і Демґард запропонували, щоб повідомлення доповнювались доповненням, яке б кодувало довжину початкового повідомлення. Це називається ''довжинне доповнення'' ({{lang-en|length padding}}) або '''підсилення Меркла-Демґарда''' ({{lang-en|'''Merkle–Damgård strengthening'''}}).

[[Файл:Merkle-Damgard hash big.svg|thumb|400px|right|Геш будова Меркла-Демґарда]]

На діаграмі, однобічна функція стискання позначена як ''f'', і перетворює вхід певної довжини на вихід тої ж довжини. Алгоритм стартує з ініціалізаційним вектором, [[ініціалізаційний вектор]] (IV). IV це фіксоване значення (специфічне алгоритму або реалізації). Для кожного блоку повідомлення, функція стискання ''f'' бере поточний результат і поєднує його з наступним блоком повідомлення,  утворюючи проміжний результат. Останній блок доповнюється нулями і бітами, що представляють загальну довжину доданого повідомлення. (Нижче наведений приклад довжинного додавання в подробицях.)

Для зміцнення геш-функції, результат пропускають через ''завершальну функцію''. Завершальна функція може мати декілька цілей таких як додаткове стискання, краще змішування та [[лавиновий ефект]] на бітах геш-суми. Завершальна функція часто будується із використанням функції стискання{{citation needed|date=Січень 2011}} (Зауважте, що в деяких паперах довжинне доповнення називають «завершенням».).

== Алгоритми, що втілюють будову Меркла-Демґарда ==
* [[MD5]]
* [[SHA-1]], [[SHA-2]]

== Характеристики безпеки ==

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

* Довжинне доповнення&nbsp;— щойно атакувальник отримав одну колізію, він може знайти ще дуже дешево.
* Друга [[атака знаходження першовзору]] проти довгих повідомлень завжди набагато дієвіша від повного перебору.
* Мультиколізії (багато повідомлень з однаковим гешем) можна знайти з лише невеликими додатковими зусиллями ніж колізії.<ref>Antoine Joux. ''Multicollisions in iterated hash functions. Application to cascaded construction.'' In Advances in Cryptology - CRYPTO '04 Proceedings, Lecture Notes in Computer Science, Vol. 3152, M. Franklin, ed, Springer-Verlag, 2004, pp. 306–316.</ref>
* "Атака доповнення": За даним ''H(X)'' для невідомого входу ''X'', легко знайти значення ''H(pad(X) || Y)'', де ''pad''&nbsp;— функція доповнення. Тобто, можливо знайти геші вхідних повідомлень пов'язаних з ''X'' навіть хоча ''X'' залишається невідомим.<ref>Yevgeniy Dodis, Thomas Ristenpart, Thomas Shrimpton. ''Salvaging Merkle–Damgård for Practical Applications''. Preliminary version in Advances in Cryptology - EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, ed, Springer-Verlag, 2009, pp. 371–388.</ref> Випадковий оракул не має такої властивості, і це може призвести до простих атак навіть для схем доведено безпечним в моделі випадкового оракула.<ref>J.S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. ''Merkle–Damgård Revisited: How to Construct a Hash Function.'' Advances in Cryptology – CRYPTO '05 Proceedings, Lecture Notes in Computer Science, Vol. 3621, Springer-Verlag, 2005, pp. 21–39.</ref>

== Ширококанальна будова ==
[[Файл:WidePipeHashFunction.png|thumb|400px|right|Ширококанальна будова геша.Проміжні ланцюгові значення були подвоєні]]
Через декілька структурних слабкостей будови Меркла-Демґарда, особливо проблем довжинного доповнення і мультиколізійних атак, Стефан Лакс запропонував використати ширококанальний ({{lang-en|wide-pipe}}) геш<ref>S. Lucks, ''Design Principles for Iterated Hash Functions'', In: Cryptology ePrint Archive, Report 2004/253, 2004.</ref> замість будови Меркла-Демґарда. Ширококанальний геш дуже нагадує будову Меркла-Демґарда, але має більший розмір внутрішнього стану, довжина, що використовується алгоритмом більша за довжину виходу. Якщо потрібен геш в ''n'' біт, функція стискання ''f'' приймає ланцюгове значення в ''2n'' біт і ''m'' біт повідомлення і стискає це до ''2n'' біт.

Отже, на завершальному кроці друга функція стискання стискає останнє внутрішнє значення геш-значення (''2n'' біт) до кінцевого значення (''n'' біт). Цього можна досягнути простим відкиданням половини останнього виходу в ''2n'' біт. SHA-224 і SHA-384 утворені цим алгоритмом з SHA-256 і SHA-512, відповідно.

== Швидка ширококанальна будова ==
[[Файл:FastWidePipeHashFunction.png|thumb|400px|right|Швидка ширококанальна будова. У функції стискання використовується половина ланцюгового значення]]
Цей підхід продемонстрували Mridul Nandi і Souradyuti Paul, отже ширококанальна геш-функція може бути приблизно вдвічі швидшою, якщо ширококанальний стан можна розділити так: половина подається на вхід наступній функції стискання, а друга половина об'єднується з виходом функції стискання.<ref name="NP10">Mridul Nandi and Souradyuti Paul. Speeding Up the Widepipe: Secure and Fast Hashing. In Guang Gong and Kishan Gupta, editor, Indocrypt 2010, Springer, 2010.</ref>

== МД-сумісне доповнення ==
Як згадано у вступній частині, схема доповнення використовну в будові Меркла-Демґарда потрібно обирати обережно, щоб гарантувати безпечність схеми. Mihir Bellare надав достатні умови безпечності схеми доповнення: схема має бути "МД-сумісною" (первинне довженне доповнення використане Мерклом є прикладом МД-сумісного доповнення).<ref name=GoldwasserBellare />{{rp|145}} Conditions:
*<math>M</math> — це префікс <math>\mathsf{Pad}(M).</math>
*Якщо <math>|M_{1}| = |M_{2}|</math> тоді <math>|\mathsf{Pad}(M_{1})| = |\mathsf{Pad}(M_{2})|.</math>
*Якщо <math>|M_{1}| \neq |M_{2}|</math> тоді останній блок <math>\mathsf{Pad}(M_{1})</math> відмінне від останнього блоку <math>\mathsf{Pad}(M_{2}).</math>

З виконаними цими умовами, ми можемо знайти колізію в МД-функції саме тоді, коли ми знайдемо колізію в використаній функції стискання. Отже, будова Меркла-Демґарда доказово безпечна коли функція стискання безпечна.<ref name=GoldwasserBellare />{{rp|147}}

== Приклад довжинного доповнення ==

Щоб ''згодувати'' повідомлення функції стискання, останній блок треба доповнити константними даними (типово нулями) до повного блоку.
: ''Наприклад, нехай повідомлення до гешування це «HashInput» і розмір блоку функції стискання становить 8 байт (64 біти). Отже отримуємо 2 таких блоки:''
: <tt>HashInpu  t0000000</tt>

Але це створює проблему. Маючи друге повідомлення, яке різниться від першого лише нулями наприкінці, ми після доповнення можемо мати повідомлення однакового вигляду і, відповідно, з однаковою геш-сумою.
: ''В нашому прикладу, приміром, змінене повідомлення «HashInput00» утворило б ті самі блоки, що й первісне повідомлення «HashInput».''

Для запобігання цьому, перший біт доповнення потрібно змінити. Отже він має бути зміненим на «1».
: ''Отримуємо щось на кшталт цьому:''
: <tt>HashInpu  t1000000</tt>

Для подальшого ускладнення гешу, можна додатковим повідомленням додати довжину повідомлення.
: ''Отримаємо:''
: <tt>HashInpu  t1000000  00000009</tt>

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

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

: ''Припустимо, що у нас значення довжини кодується 5 байтами, отже воно додасться в завершальний блок як "00009":''
: <tt>HashInpu  t1000009</tt>

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

== Див. також ==

* [[Геш-функція]]

{{ВП-портали|Програмування|}}


{{Crypto-stub}}

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