Будова Меркла-Демґарда або геш-функція Меркла-Демґарда — це метод будови стійкої до колізій криптографічної геш-функції зі стійкої до колізій однобічної функції стискання. Цей підхід використовується багатьма розповсюдженими алгоритмами такими як MD5, SHA1 і SHA2.
Будова Меркла-Демґарда була описана в Ph.D. тезах Ралфа Меркла в 1979.Ральф Меркле і незалежно довели, що якщо використати прийнятну схему доповнення і стійку до колізій функцію стискання, тоді геш-функція також буде стійкою до колізій.
Геш-функція Меркла-Демґарда спочатку застосовує МД-сумісне доповнення отримуючи вихід довжини кратної до певного числа (наприклад 512 або 1024) — бо функція стискання не може обробити вхідні дані довільного розміру. Тоді геш-функція розбиває вхідні дані на блоки умовленого розміру і обробляє їх по одному функцією стискання, щоразу використовуючи блок на вході і блок утворений попереднім раундом. З метою зробити будову безпечною, Меркл і Демґард запропонували, щоб повідомлення доповнювались доповненням, яке б кодувало довжину початкового повідомлення. Це називається довжинне доповнення (англ. length padding) або підсилення Меркла-Демґарда (англ. Merkle–Damgård strengthening).
На діаграмі, однобічна функція стискання позначена як f, і перетворює вхід певної довжини на вихід тої ж довжини. Алгоритм стартує з ініціалізаційним вектором, ініціалізаційний вектор (IV). IV це фіксоване значення (специфічне алгоритму або реалізації). Для кожного блоку повідомлення, функція стискання f бере поточний результат і поєднує його з наступним блоком повідомлення, утворюючи проміжний результат. Останній блок доповнюється нулями і бітами, що представляють загальну довжину доданого повідомлення. (Нижче наведений приклад довжинного додавання в подробицях.)
Для зміцнення геш-функції, результат пропускають через завершальну функцію. Завершальна функція може мати декілька цілей таких як додаткове стискання, краще змішування та лавиновий ефект на бітах геш-суми. Завершальна функція часто будується із використанням функції стискання[] (Зауважте, що в деяких паперах довжинне доповнення називають «завершенням».).
Алгоритми, що втілюють будову Меркла-Демґарда
Характеристики безпеки
Своєю поширеністю будова завдячує факту доведеному Мерклом і Демґагрдом, що якщо однобічна функція стискання колізійно стіка, тоді те ж можна сказати про геш-функцію побудовану з неї. На жаль ця будова також має декілька небажаних властивостей:
- Довжинне доповнення — щойно атакувальник отримав одну колізію, він може знайти ще дуже дешево.
- Друга атака знаходження першовзору проти довгих повідомлень завжди набагато дієвіша від повного перебору.
- Мультиколізії (багато повідомлень з однаковим гешем) можна знайти з лише невеликими додатковими зусиллями ніж колізії.
- "Атака доповнення": За даним H(X) для невідомого входу X, легко знайти значення H(pad(X) || Y), де pad — функція доповнення. Тобто, можливо знайти геші вхідних повідомлень пов'язаних з X навіть хоча X залишається невідомим. Випадковий оракул не має такої властивості, і це може призвести до простих атак навіть для схем доведено безпечним в моделі випадкового оракула.
Ширококанальна будова
Через декілька структурних слабкостей будови Меркла-Демґарда, особливо проблем довжинного доповнення і мультиколізійних атак, Стефан Лакс запропонував використати ширококанальний (англ. wide-pipe) геш замість будови Меркла-Демґарда. Ширококанальний геш дуже нагадує будову Меркла-Демґарда, але має більший розмір внутрішнього стану, довжина, що використовується алгоритмом більша за довжину виходу. Якщо потрібен геш в n біт, функція стискання f приймає ланцюгове значення в 2n біт і m біт повідомлення і стискає це до 2n біт.
Отже, на завершальному кроці друга функція стискання стискає останнє внутрішнє значення геш-значення (2n біт) до кінцевого значення (n біт). Цього можна досягнути простим відкиданням половини останнього виходу в 2n біт. SHA-224 і SHA-384 утворені цим алгоритмом з SHA-256 і SHA-512, відповідно.
Швидка ширококанальна будова
Цей підхід продемонстрували Mridul Nandi і Souradyuti Paul, отже ширококанальна геш-функція може бути приблизно вдвічі швидшою, якщо ширококанальний стан можна розділити так: половина подається на вхід наступній функції стискання, а друга половина об'єднується з виходом функції стискання.
МД-сумісне доповнення
Як згадано у вступній частині, схема доповнення використовну в будові Меркла-Демґарда потрібно обирати обережно, щоб гарантувати безпечність схеми. Mihir Bellare надав достатні умови безпечності схеми доповнення: схема має бути "МД-сумісною" (первинне довженне доповнення використане Мерклом є прикладом МД-сумісного доповнення).
Conditions:- — це префікс
- Якщо тоді
- Якщо тоді останній блок відмінне від останнього блоку
З виконаними цими умовами, ми можемо знайти колізію в МД-функції саме тоді, коли ми знайдемо колізію в використаній функції стискання. Отже, будова Меркла-Демґарда доказово безпечна коли функція стискання безпечна.
Приклад довжинного доповнення
Щоб згодувати повідомлення функції стискання, останній блок треба доповнити константними даними (типово нулями) до повного блоку.
- Наприклад, нехай повідомлення до гешування це «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.
Див. також
Це незавершена стаття з криптографії. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Budova Merkla Demgarda abo gesh funkciya Merkla Demgarda ce metod budovi stijkoyi do kolizij kriptografichnoyi gesh funkciyi zi stijkoyi do kolizij odnobichnoyi funkciyi stiskannya 145 Cej pidhid vikoristovuyetsya bagatma rozpovsyudzhenimi algoritmami takimi yak MD5 SHA1 i SHA2 Budova Merkla Demgarda bula opisana v Ph D tezah Ralfa Merkla v 1979 Ralf Merkle i nezalezhno doveli sho yaksho vikoristati prijnyatnu shemu dopovnennya i stijku do kolizij funkciyu stiskannya todi gesh funkciya takozh bude stijkoyu do kolizij Gesh funkciya Merkla Demgarda spochatku zastosovuye MD sumisne dopovnennya otrimuyuchi vihid dovzhini kratnoyi do pevnogo chisla napriklad 512 abo 1024 bo funkciya stiskannya ne mozhe obrobiti vhidni dani dovilnogo rozmiru Todi gesh funkciya rozbivaye vhidni dani na bloki umovlenogo rozmiru i obroblyaye yih po odnomu funkciyeyu stiskannya shorazu vikoristovuyuchi blok na vhodi i blok utvorenij poperednim raundom 146 Z metoyu zrobiti budovu bezpechnoyu Merkl i Demgard zaproponuvali shob povidomlennya dopovnyuvalis dopovnennyam yake b koduvalo dovzhinu pochatkovogo povidomlennya Ce nazivayetsya dovzhinne dopovnennya angl length padding abo pidsilennya Merkla Demgarda angl Merkle Damgard strengthening Gesh budova Merkla Demgarda Na diagrami odnobichna funkciya stiskannya poznachena yak f i peretvoryuye vhid pevnoyi dovzhini na vihid toyi zh dovzhini Algoritm startuye z inicializacijnim vektorom inicializacijnij vektor IV IV ce fiksovane znachennya specifichne algoritmu abo realizaciyi Dlya kozhnogo bloku povidomlennya funkciya stiskannya f bere potochnij rezultat i poyednuye jogo z nastupnim blokom povidomlennya utvoryuyuchi promizhnij rezultat Ostannij blok dopovnyuyetsya nulyami i bitami sho predstavlyayut zagalnu dovzhinu dodanogo povidomlennya Nizhche navedenij priklad dovzhinnogo dodavannya v podrobicyah Dlya zmicnennya gesh funkciyi rezultat propuskayut cherez zavershalnu funkciyu Zavershalna funkciya mozhe mati dekilka cilej takih yak dodatkove stiskannya krashe zmishuvannya ta lavinovij efekt na bitah gesh sumi Zavershalna funkciya chasto buduyetsya iz vikoristannyam funkciyi stiskannya dzherelo Zauvazhte sho v deyakih paperah dovzhinne dopovnennya nazivayut zavershennyam Algoritmi sho vtilyuyut budovu Merkla DemgardaMD5 SHA 1 SHA 2Harakteristiki bezpekiSvoyeyu poshirenistyu budova zavdyachuye faktu dovedenomu Merklom i Demgagrdom sho yaksho odnobichna funkciya stiskannya kolizijno stika todi te zh mozhna skazati pro gesh funkciyu pobudovanu z neyi Na zhal cya budova takozh maye dekilka nebazhanih vlastivostej Dovzhinne dopovnennya shojno atakuvalnik otrimav odnu koliziyu vin mozhe znajti she duzhe deshevo Druga ataka znahodzhennya pershovzoru proti dovgih povidomlen zavzhdi nabagato diyevisha vid povnogo pereboru Multikoliziyi bagato povidomlen z odnakovim geshem mozhna znajti z lishe nevelikimi dodatkovimi zusillyami nizh koliziyi Ataka dopovnennya Za danim H X dlya nevidomogo vhodu X legko znajti znachennya H pad X Y de pad funkciya dopovnennya Tobto mozhlivo znajti geshi vhidnih povidomlen pov yazanih z X navit hocha X zalishayetsya nevidomim Vipadkovij orakul ne maye takoyi vlastivosti i ce mozhe prizvesti do prostih atak navit dlya shem dovedeno bezpechnim v modeli vipadkovogo orakula Shirokokanalna budovaShirokokanalna budova gesha Promizhni lancyugovi znachennya buli podvoyeni Cherez dekilka strukturnih slabkostej budovi Merkla Demgarda osoblivo problem dovzhinnogo dopovnennya i multikolizijnih atak Stefan Laks zaproponuvav vikoristati shirokokanalnij angl wide pipe gesh zamist budovi Merkla Demgarda Shirokokanalnij gesh duzhe nagaduye budovu Merkla Demgarda ale maye bilshij rozmir vnutrishnogo stanu dovzhina sho vikoristovuyetsya algoritmom bilsha za dovzhinu vihodu Yaksho potriben gesh v n bit funkciya stiskannya f prijmaye lancyugove znachennya v 2n bit i m bit povidomlennya i stiskaye ce do 2n bit Otzhe na zavershalnomu kroci druga funkciya stiskannya stiskaye ostannye vnutrishnye znachennya gesh znachennya 2n bit do kincevogo znachennya n bit Cogo mozhna dosyagnuti prostim vidkidannyam polovini ostannogo vihodu v 2n bit SHA 224 i SHA 384 utvoreni cim algoritmom z SHA 256 i SHA 512 vidpovidno Shvidka shirokokanalna budovaShvidka shirokokanalna budova U funkciyi stiskannya vikoristovuyetsya polovina lancyugovogo znachennya Cej pidhid prodemonstruvali Mridul Nandi i Souradyuti Paul otzhe shirokokanalna gesh funkciya mozhe buti priblizno vdvichi shvidshoyu yaksho shirokokanalnij stan mozhna rozdiliti tak polovina podayetsya na vhid nastupnij funkciyi stiskannya a druga polovina ob yednuyetsya z vihodom funkciyi stiskannya MD sumisne dopovnennyaYak zgadano u vstupnij chastini shema dopovnennya vikoristovnu v budovi Merkla Demgarda potribno obirati oberezhno shob garantuvati bezpechnist shemi Mihir Bellare nadav dostatni umovi bezpechnosti shemi dopovnennya shema maye buti MD sumisnoyu pervinne dovzhenne dopovnennya vikoristane Merklom ye prikladom MD sumisnogo dopovnennya 145 Conditions M displaystyle M ce prefiks Pad M displaystyle mathsf Pad M Yaksho M1 M2 displaystyle M 1 M 2 todi Pad M1 Pad M2 displaystyle mathsf Pad M 1 mathsf Pad M 2 Yaksho M1 M2 displaystyle M 1 neq M 2 todi ostannij blok Pad M1 displaystyle mathsf Pad M 1 vidminne vid ostannogo bloku Pad M2 displaystyle mathsf Pad M 2 Z vikonanimi cimi umovami mi mozhemo znajti koliziyu v MD funkciyi same todi koli mi znajdemo koliziyu v vikoristanij funkciyi stiskannya Otzhe budova Merkla Demgarda dokazovo bezpechna koli funkciya stiskannya bezpechna 147Priklad dovzhinnogo dopovnennyaShob zgoduvati povidomlennya funkciyi stiskannya ostannij blok treba dopovniti konstantnimi danimi tipovo nulyami do povnogo bloku Napriklad nehaj povidomlennya do geshuvannya ce HashInput i rozmir bloku funkciyi stiskannya stanovit 8 bajt 64 biti Otzhe otrimuyemo 2 takih bloki HashInpu t0000000 Ale ce stvoryuye problemu Mayuchi druge povidomlennya yake riznitsya vid pershogo lishe nulyami naprikinci mi pislya dopovnennya mozhemo mati povidomlennya odnakovogo viglyadu i vidpovidno z odnakovoyu gesh sumoyu V nashomu prikladu primirom zminene povidomlennya HashInput00 utvorilo b ti sami bloki sho j pervisne povidomlennya HashInput Dlya zapobigannya comu pershij bit dopovnennya potribno zminiti Otzhe vin maye buti zminenim na 1 Otrimuyemo shos na kshtalt comu HashInpu t1000000 Dlya podalshogo uskladnennya geshu mozhna dodatkovim povidomlennyam dodati dovzhinu povidomlennya Otrimayemo HashInpu t1000000 00000009 Dlya uniknennya dvoznachnosti dovzhina povidomlennya sama po sobi maye buti stijkoyu do dovzhinnih dopovnen Najposhirenishe vtilennya vikoristovuye vstanovlenij bitovij rozmir v suchasnih algoritmah zazvichaj 64 abo 128 bit i vstanovlenu poziciyu naprikinci ostannogo bloku dlya shifruvannya znachennya dovzhini povidomlennya Narazi ce troshki marnotratno cherez neobhidnist geshuvannya odnogo dodatkovogo bloku dlya dovzhini povidomlennya Tozh prisutnya neznachna optimizaciya yaku vikoristovuyut bilshist gesh algoritmiv Yaksho do ostannogo bloku dodano dostatno nuliv znachennya dovzhini mozhna natomist vstaviti tudi Pripustimo sho u nas znachennya dovzhini koduyetsya 5 bajtami otzhe vono dodastsya v zavershalnij blok yak 00009 HashInpu t1000009PrimitkiShafi Goldwasser Goldwasser S and Bellare M Lecture Notes on Cryptography 2012 04 21 u Wayback Machine Summer course on cryptography MIT 1996 2001 R C Merkle Secrecy authentication and public key systems 14 serpnya 2018 u 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 Damgard 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 Damgard 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 Damgard 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 Div takozhGesh funkciya Ce nezavershena stattya z kriptografiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi