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

Будова Меркла-Демґарда або геш-функція Меркла-Демґарда — це метод будови стійкої до колізій криптографічної геш-функції зі стійкої до колізій однобічної функції стискання.^[1]^:145 Цей підхід використовується багатьма розповсюдженими алгоритмами такими як MD5, SHA1 і SHA2.

Будова Меркла-Демґарда була описана в Ph.D. тезах Ралфа Меркла в 1979.^[2] Ральф Меркле і Іван Демґард незалежно довели, що якщо використати прийнятну схему доповнення і стійку до колізій функцію стискання, тоді геш-функція також буде стійкою до колізій.^[3]^[4]

Геш-функція Меркла-Демґарда спочатку застосовує МД-сумісне доповнення отримуючи вихід довжини кратної до певного числа (наприклад 512 або 1024) — бо функція стискання не може обробити вхідні дані довільного розміру. Тоді геш-функція розбиває вхідні дані на блоки умовленого розміру і обробляє їх по одному функцією стискання, щоразу використовуючи блок на вході і блок утворений попереднім раундом.^[1]^:146 З метою зробити будову безпечною, Меркл і Демґард запропонували, щоб повідомлення доповнювались доповненням, яке б кодувало довжину початкового повідомлення. Це називається довжинне доповнення (англ. length padding) або підсилення Меркла-Демґарда (англ. Merkle–Damgård strengthening).

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

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

Алгоритми, що втілюють будову Меркла-Демґарда ред.

MD5
SHA-1, SHA-2

Характеристики безпеки ред.

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

Довжинне доповнення — щойно атакувальник отримав одну колізію, він може знайти ще дуже дешево.
Друга атака знаходження першовзору проти довгих повідомлень завжди набагато дієвіша від повного перебору.
Мультиколізії (багато повідомлень з однаковим гешем) можна знайти з лише невеликими додатковими зусиллями ніж колізії.^[5]
"Атака доповнення": За даним H(X) для невідомого входу X, легко знайти значення H(pad(X) || Y), де pad — функція доповнення. Тобто, можливо знайти геші вхідних повідомлень пов'язаних з X навіть хоча X залишається невідомим.^[6] Випадковий оракул не має такої властивості, і це може призвести до простих атак навіть для схем доведено безпечним в моделі випадкового оракула.^[7]

Ширококанальна будова ред.

Ширококанальна будова геша.Проміжні ланцюгові значення були подвоєні

Через декілька структурних слабкостей будови Меркла-Демґарда, особливо проблем довжинного доповнення і мультиколізійних атак, Стефан Лакс запропонував використати ширококанальний (англ. wide-pipe) геш^[8] замість будови Меркла-Демґарда. Ширококанальний геш дуже нагадує будову Меркла-Демґарда, але має більший розмір внутрішнього стану, довжина, що використовується алгоритмом більша за довжину виходу. Якщо потрібен геш в n біт, функція стискання f приймає ланцюгове значення в 2n біт і m біт повідомлення і стискає це до 2n біт.

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

Швидка ширококанальна будова ред.

Швидка ширококанальна будова. У функції стискання використовується половина ланцюгового значення

Цей підхід продемонстрували Mridul Nandi і Souradyuti Paul, отже ширококанальна геш-функція може бути приблизно вдвічі швидшою, якщо ширококанальний стан можна розділити так: половина подається на вхід наступній функції стискання, а друга половина об'єднується з виходом функції стискання.^[9]

МД-сумісне доповнення ред.

Як згадано у вступній частині, схема доповнення використовну в будові Меркла-Демґарда потрібно обирати обережно, щоб гарантувати безпечність схеми. Mihir Bellare надав достатні умови безпечності схеми доповнення: схема має бути "МД-сумісною" (первинне довженне доповнення використане Мерклом є прикладом МД-сумісного доповнення).^[1]^:145 Conditions:

$M$ — це префікс ${\mathsf {Pad}}(M).$
Якщо $|M_{1}|=|M_{2}|$ тоді $|{\mathsf {Pad}}(M_{1})|=|{\mathsf {Pad}}(M_{2})|.$
Якщо $|M_{1}|\neq |M_{2}|$ тоді останній блок ${\mathsf {Pad}}(M_{1})$ відмінне від останнього блоку ${\mathsf {Pad}}(M_{2}).$

З виконаними цими умовами, ми можемо знайти колізію в МД-функції саме тоді, коли ми знайдемо колізію в використаній функції стискання. Отже, будова Меркла-Демґарда доказово безпечна коли функція стискання безпечна.^[1]^:147

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

Щоб згодувати повідомлення функції стискання, останній блок треба доповнити константними даними (типово нулями) до повного блоку.

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

HashInpu t0000000

Але це створює проблему. Маючи друге повідомлення, яке різниться від першого лише нулями наприкінці, ми після доповнення можемо мати повідомлення однакового вигляду і, відповідно, з однаковою геш-сумою.

В нашому прикладу, приміром, змінене повідомлення «HashInput00» утворило б ті самі блоки, що й первісне повідомлення «HashInput».

Для запобігання цьому, перший біт доповнення потрібно змінити. Отже він має бути зміненим на «1».

Отримуємо щось на кшталт цьому:

HashInpu t1000000

Для подальшого ускладнення гешу, можна додатковим повідомленням додати довжину повідомлення.

Отримаємо:

HashInpu t1000000 00000009

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

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

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

HashInpu t1000009

Примітки ред.

↑ ^а ^б ^в ^г Shafi Goldwasser|Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" [Архівовано 2012-04-21 у Wayback Machine.]. Summer course on cryptography, MIT, 1996-2001
↑ R.C. Merkle. Secrecy, authentication, and public key systems. [Архівовано 14 серпня 2018 у Wayback Machine.] Stanford Ph.D. thesis 1979, pages 13-15.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ S. Lucks, Design Principles for Iterated Hash Functions, In: Cryptology ePrint Archive, Report 2004/253, 2004.
↑ Mridul Nandi and Souradyuti Paul. Speeding Up the Widepipe: Secure and Fast Hashing. In Guang Gong and Kishan Gupta, editor, Indocrypt 2010, Springer, 2010.

Див. також ред.

Геш-функція

Це незавершена стаття з криптографії.
Ви можете допомогти проєкту, виправивши або дописавши її.

[GoldwasserBellare-1] а ^б ^в ^г Shafi Goldwasser|Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" [Архівовано 2012-04-21 у Wayback Machine.]. Summer course on cryptography, MIT, 1996-2001

[2] R.C. Merkle. Secrecy, authentication, and public key systems. [Архівовано 14 серпня 2018 у Wayback Machine.] Stanford Ph.D. thesis 1979, pages 13-15.

[3] 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.

[4] 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.

[5] 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.

[6] 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.

[7] 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.

[8] S. Lucks, Design Principles for Iterated Hash Functions, In: Cryptology ePrint Archive, Report 2004/253, 2004.

[NP10-9] Mridul Nandi and Souradyuti Paul. Speeding Up the Widepipe: Secure and Fast Hashing. In Guang Gong and Kishan Gupta, editor, Indocrypt 2010, Springer, 2010.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]