MD6 (англ. Message Digest 6) — алгоритм хешування змінної розрядності, розроблений професором Рональдом Рівестом з Массачусетського Технологічного Інституту в 2008 році. Призначений для створення «відбитків» або дайджестів повідомлень довільної довжини. Пропонується на зміну менш досконалого MD5. За заявою авторів, алгоритм стійкий до диференціального криптоаналізу. Використовується для перевірки цілісності і, у деякому сенсі, достовірності опублікованих повідомлень, шляхом порівняння дайджесту повідомлення з опублікованими. Цю операцію називають «перевірка хешу» (англ. hashcheck). Хеш-функції також широко використовуються для генерації ключів фіксованої довжини для алгоритмів шифрування на основі заданого ключового рядка.
Загальні | |
---|---|
Розробники | Рональд Рівест, Benjamin Agre, Dan Bailey, Sarah Cheng, Christopher Crutchfield, Yevgeniy Dodis, Kermin Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Eran Tromer, Yiqun Lisa Yin |
Уперше оприлюднений | 2008 |
Серія | MD2, MD4, MD5, MD6 |
Деталі | |
Розмір даджеста | Змінна, 0<d≤512 біт |
Структура | дерева Меркле |
Раундів | Змінна. Стандартно, Unkeyed=40+[d/4], Keyed=max(80,40+(d/4)) |
Історія
MD6 — один із серії алгоритмів побудови дайджесту повідомлення, розроблений професором Рональдом Л. Рівестом з Массачусетського Технологічного Інституту. MD6 був вперше представлений на конференції Crypto 2008 як кандидат на стандарт SHA-3. Однак пізніше в 2009 на цій же конференції Рівест заявив, що MD6 ще не готовий до того, щоб стати стандартом. На офіційному сайті MD6 він заявив, що, хоча формально, заявка не відкликана, в алгоритмі ще залишаються проблеми зі швидкістю і нездатністю забезпечити безпеку у версії зі зменшеною кількістю раундів. У результаті MD6 не пройшов до другого кола змагання. Раніше, в грудні 2008, дослідник з Fortify Software знайшов помилку, пов'язану з переповненням буфера в оригінальній реалізації MD6. 19 лютого 2009 професор Рівест опублікував дані про цю помилку, а також представив виправлення реалізації.
Алгоритми
У алгоритмі хеш-функції застосовані досить оригінальні ідеї. за один прохід обробляється 512 байт, ускладнюючи проведення низки атак і полегшуючи розпаралелювання, для чого застосовується деревоподібні структури.
Вхідні данні і процедури
М | вхідне повідомлення довжиною m, 1 ≤ m ≤ (264-1) біт |
d | довжина результуючого геша в бітах, 1 ≤ d ≤ 512 |
K | довільне ключове значення довжиною keylen байт (0 ≤ keylen ≤ 64), доповнене праворуч нулями числом в 64 — keylen |
L | невід'ємний параметр розміром 1 байт, 0 ≤ L ≤ 64 (за замовчуванням L=64), позначає число паралельних обчислень і глибину дерева |
r | невід'ємний параметр розміром 12 біт: число раундів (за замовчуванням r=40+[d/4]) |
Q | масив з 15 елементів по 8 байт, його значення вказано нижче |
ƒ | функція стиснення MD6, перетворює 712 байт вхідних даних (включаючи блок B розміром 512 байт) в результат C розміром 128 байт з використанням r раундів обчислень |
PAR | паралельна операція стиснення для кожного рівня дерева, ніколи не викликається при L = 0 |
SEQ | послідовна операція стиснення, ніколи не викликається при L = 64 |
Q = {0x7311c2812425cfa0, 0x6432286434aac8e7, 0xb60450e9ef68b7c1, 0xe8fb23908d9f06f1, 0xdd2e76cba691e5bf, 0x0cd0d63b2c30bc41, 0x1f8ccf6823058f8a, 0x54e5ed5b88e3775d, 0x4ad12aae0a6d6031, 0x3e7f16bb88222e0d, 0x8af8671d3fb50c2c, 0x995ad1178bd25c31, 0xc878c1dd04c4b633, 0x3b72066c7a1552ac, 0x0d6f3522631effcb}Масив Q
Основна процедура
Ініціалізація
Позначимо l = 0, M0 = M, m0 = m.
Основний цикл
- l = l + 1.
- Якщо l = L + 1, повертаємо SEQ(Ml-1,d,K,L,r) як результат.
- Ml = PAR(Ml-1,d,K,L,r,l). Позначимо ml як довжину Ml в бітах.
- Якщо Ml = 8 * c (тобто довжина Ml становить 8 * c байт), Повертаємо останні d бітів Ml. Інакше повертаємося до початку циклу.
Операція PAR
PAR повертає повідомлення довжиною ml = 1024 * max(1, [ml-1 / 4096]).
Тіло процедури
- Якщо потрібно, то розширюємо Ml-1, додаючи праворуч нульові біти, поки його довжина не стане кратна 512 байт. Тепер розіб'ємо Ml-1 на блоки B0, B1, …, Bj-1, где j = max(1, [ml-1 / 512]);
- Для кожного блоку Bi, i = 0, 1, …, j-1, паралельно обчислюємо Ci за наступним алгоритмом:
- Позначимо через p число доповнених бітів Bi, 0 ≤ p ≤ 4096. (p завжди більше нуля для i = j-1.);
- Позначимо z = 1, якщо j = 1, інакше z = 0;
- Позначимо V як 8-байтове значення r ǁ L ǁ z ǁ p ǁ keylen ǁ d таким чином:
- 4 біта нулів;
- 12 біт r;
- 8 біт L;
- 4 біта z;
- 16 біт p;
- 8 біт keylen.
- 12 біт d.
- Позначимо U = l * 256 + i — унікальний 8-байтовий ідентифікатор поточного блоку;
- Ci = ƒ(Q ǁ K ǁ U ǁ V ǁ Bi).
- Повертаємо Ml = C0 ǁ C1 ǁ … ǁ Cj-1.
Операція SEQ
SEQ повертає хеш довжиною d біт. Дана операція ніколи не викликається, якщо L = 64.
Тіло процедури
- Позначимо через C−1 нульовий вектор довжиною 128 байт.
- Якщо потрібно, то розширюємо ML, додаючи праворуч нульові біти, поки його довжина не стане кратна 384 байтів. Тепер розіб'ємо ML на блоки B0, B1, …, Bj-1, где j = max(1, [mL / 384]).
- Для кожного блоку Bi, i = 0, 1, …, j-1, паралельно обчислюємо Ci за наступним алгоритмом:
- Позначимо через p число доповнених бітів Bi, 0 ≤ p ≤ 3072. (p завжди більше нуля для i = j-1.);
- Позначимо z = 1, якщо i = j-1, інакше z = 0;
- Позначимо V як 8-байтове значення r ǁ L ǁ z ǁ p ǁ keylen ǁ d аналогічно попередньої операції;
- Позначимо U = (L + 1) * 256 + i — унікальний 8-байтовий ідентифікатор поточного блоку;
- Ci = ƒ(Q ǁ K ǁ U ǁ V ǁ Ci-1 ǁ Bi).
- Повертаємо останні d біт значення Cj-1 як підсумковий хеш.
Функція стиснення MD6
Вхідні і вихідні дані
Як вхідні дані функція приймає масив N, що складається з n = 89 8-байтових слів (712 байт) і число раундів r.
Функція повертає масив C з 16 елементів по 8 байт.
Константи
t0 | t1 | t2 | t3 | t4 |
---|---|---|---|---|
17 | 18 | 21 | 31 | 67 |
(i — n) mod 16 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
ri-n | 10 | 5 | 13 | 10 | 11 | 12 | 2 | 7 | 14 | 15 | 7 | 13 | 11 | 7 | 6 | 12 |
li-n | 11 | 24 | 9 | 16 | 15 | 9 | 27 | 15 | 6 | 2 | 29 | 8 | 15 | 5 | 31 | 9 |
Si-n = S|(i-n)/16
S|0 = 0x0123456789abcde
S* = 0x7311c2812425cfa0
S|j+1 = (S|j <<< 1) ⊕ (S|j ^ S*)
Тіло функції
Позначимо t = 16r. (У кожному раунді буде 16 кроків)
Позначимо через A[0..t + n-1] масив t + n 8-байтових елементів. Перші n елементів необхідно скопіювати з вхідного масиву N.
Основний цикл функції виглядає наступним чином:
- for i = n to t + n 1: /* t steps */
- x = Si-n ⊕ Ai-n ⊕ Ai-t0
- x = x ⊕ (Ai-t1 ^ Ai-t2) ⊕ (Ai-t3 ^ Ai-t4): x = x ⊕ (x >> ri-n): Ai = x ⊕ (x << li-n)
Повернути A[t + n-16 .. t + n-1].
Примітки
- Рональд Рівест et Al., The MD6 Hash Function [ 12 серпня 2017 у Wayback Machine.], Crypto 2008
- Ronald L. Rivest. . Архів оригіналу за 9 листопада 2020.
- Schneier, Bruce (1 липня 2009). MD6 Withdrawn from SHA-3 Competition. Архів оригіналу за 21 березня 2012. Процитовано 9 липня 2009.
- (PDF). Архів оригіналу (PDF) за 22 лютого 2012. Процитовано 31 грудня 2016.
{{}}
: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
Це незавершена стаття з криптографії. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
MD6 angl Message Digest 6 algoritm heshuvannya zminnoyi rozryadnosti rozroblenij profesorom Ronaldom Rivestom z Massachusetskogo Tehnologichnogo Institutu v 2008 roci Priznachenij dlya stvorennya vidbitkiv abo dajdzhestiv povidomlen dovilnoyi dovzhini Proponuyetsya na zminu mensh doskonalogo MD5 Za zayavoyu avtoriv algoritm stijkij do diferencialnogo kriptoanalizu Vikoristovuyetsya dlya perevirki cilisnosti i u deyakomu sensi dostovirnosti opublikovanih povidomlen shlyahom porivnyannya dajdzhestu povidomlennya z opublikovanimi Cyu operaciyu nazivayut perevirka heshu angl hashcheck Hesh funkciyi takozh shiroko vikoristovuyutsya dlya generaciyi klyuchiv fiksovanoyi dovzhini dlya algoritmiv shifruvannya na osnovi zadanogo klyuchovogo ryadka MD6ZagalniRozrobnikiRonald Rivest Benjamin Agre Dan Bailey Sarah Cheng Christopher Crutchfield Yevgeniy Dodis Kermin Fleming Asif Khan Jayant Krishnamurthy Yuncheng Lin Leo Reyzin Emily Shen Jim Sukha Eran Tromer Yiqun Lisa YinUpershe oprilyudnenij2008SeriyaMD2 MD4 MD5 MD6DetaliRozmir dadzhestaZminna 0 lt d 512 bitStrukturadereva MerkleRaundivZminna Standartno Unkeyed 40 d 4 Keyed max 80 40 d 4 IstoriyaMD6 odin iz seriyi algoritmiv pobudovi dajdzhestu povidomlennya rozroblenij profesorom Ronaldom L Rivestom z Massachusetskogo Tehnologichnogo Institutu MD6 buv vpershe predstavlenij na konferenciyi Crypto 2008 yak kandidat na standart SHA 3 Odnak piznishe v 2009 na cij zhe konferenciyi Rivest zayaviv sho MD6 she ne gotovij do togo shob stati standartom Na oficijnomu sajti MD6 vin zayaviv sho hocha formalno zayavka ne vidklikana v algoritmi she zalishayutsya problemi zi shvidkistyu i nezdatnistyu zabezpechiti bezpeku u versiyi zi zmenshenoyu kilkistyu raundiv U rezultati MD6 ne projshov do drugogo kola zmagannya Ranishe v grudni 2008 doslidnik z Fortify Software znajshov pomilku pov yazanu z perepovnennyam bufera v originalnij realizaciyi MD6 19 lyutogo 2009 profesor Rivest opublikuvav dani pro cyu pomilku a takozh predstaviv vipravlennya realizaciyi AlgoritmiU algoritmi hesh funkciyi zastosovani dosit originalni ideyi za odin prohid obroblyayetsya 512 bajt uskladnyuyuchi provedennya nizki atak i polegshuyuchi rozparalelyuvannya dlya chogo zastosovuyetsya derevopodibni strukturi Vhidni danni i proceduri M vhidne povidomlennya dovzhinoyu m 1 m 264 1 bit d dovzhina rezultuyuchogo gesha v bitah 1 d 512 K dovilne klyuchove znachennya dovzhinoyu keylen bajt 0 keylen 64 dopovnene pravoruch nulyami chislom v 64 keylen L nevid yemnij parametr rozmirom 1 bajt 0 L 64 za zamovchuvannyam L 64 poznachaye chislo paralelnih obchislen i glibinu dereva r nevid yemnij parametr rozmirom 12 bit chislo raundiv za zamovchuvannyam r 40 d 4 Q masiv z 15 elementiv po 8 bajt jogo znachennya vkazano nizhche ƒ funkciya stisnennya MD6 peretvoryuye 712 bajt vhidnih danih vklyuchayuchi blok B rozmirom 512 bajt v rezultat C rozmirom 128 bajt z vikoristannyam r raundiv obchislen PAR paralelna operaciya stisnennya dlya kozhnogo rivnya dereva nikoli ne viklikayetsya pri L 0 SEQ poslidovna operaciya stisnennya nikoli ne viklikayetsya pri L 64 Q 0x7311c2812425cfa0 0x6432286434aac8e7 0xb60450e9ef68b7c1 0xe8fb23908d9f06f1 0xdd2e76cba691e5bf 0x0cd0d63b2c30bc41 0x1f8ccf6823058f8a 0x54e5ed5b88e3775d 0x4ad12aae0a6d6031 0x3e7f16bb88222e0d 0x8af8671d3fb50c2c 0x995ad1178bd25c31 0xc878c1dd04c4b633 0x3b72066c7a1552ac 0x0d6f3522631effcb Masiv Q Osnovna procedura Inicializaciya Poznachimo l 0 M0 M m0 m Osnovnij cikl l l 1 Yaksho l L 1 povertayemo SEQ Ml 1 d K L r yak rezultat Ml PAR Ml 1 d K L r l Poznachimo ml yak dovzhinu Ml v bitah Yaksho Ml 8 c tobto dovzhina Ml stanovit 8 c bajt Povertayemo ostanni d bitiv Ml Inakshe povertayemosya do pochatku ciklu Operaciya PAR PAR povertaye povidomlennya dovzhinoyu ml 1024 max 1 ml 1 4096 Tilo proceduri Yaksho potribno to rozshiryuyemo Ml 1 dodayuchi pravoruch nulovi biti poki jogo dovzhina ne stane kratna 512 bajt Teper rozib yemo Ml 1 na bloki B0 B1 Bj 1 gde j max 1 ml 1 512 Dlya kozhnogo bloku Bi i 0 1 j 1 paralelno obchislyuyemo Ci za nastupnim algoritmom Poznachimo cherez p chislo dopovnenih bitiv Bi 0 p 4096 p zavzhdi bilshe nulya dlya i j 1 Poznachimo z 1 yaksho j 1 inakshe z 0 Poznachimo V yak 8 bajtove znachennya r ǁ L ǁ z ǁ p ǁ keylen ǁ d takim chinom 4 bita nuliv 12 bit r 8 bit L 4 bita z 16 bit p 8 bit keylen 12 bit d Poznachimo U l 256 i unikalnij 8 bajtovij identifikator potochnogo bloku Ci ƒ Q ǁ K ǁ U ǁ V ǁ Bi Povertayemo Ml C0 ǁ C1 ǁ ǁ Cj 1 Operaciya SEQ SEQ povertaye hesh dovzhinoyu d bit Dana operaciya nikoli ne viklikayetsya yaksho L 64 Tilo proceduri Poznachimo cherez C 1 nulovij vektor dovzhinoyu 128 bajt Yaksho potribno to rozshiryuyemo ML dodayuchi pravoruch nulovi biti poki jogo dovzhina ne stane kratna 384 bajtiv Teper rozib yemo ML na bloki B0 B1 Bj 1 gde j max 1 mL 384 Dlya kozhnogo bloku Bi i 0 1 j 1 paralelno obchislyuyemo Ci za nastupnim algoritmom Poznachimo cherez p chislo dopovnenih bitiv Bi 0 p 3072 p zavzhdi bilshe nulya dlya i j 1 Poznachimo z 1 yaksho i j 1 inakshe z 0 Poznachimo V yak 8 bajtove znachennya r ǁ L ǁ z ǁ p ǁ keylen ǁ d analogichno poperednoyi operaciyi Poznachimo U L 1 256 i unikalnij 8 bajtovij identifikator potochnogo bloku Ci ƒ Q ǁ K ǁ U ǁ V ǁ Ci 1 ǁ Bi Povertayemo ostanni d bit znachennya Cj 1 yak pidsumkovij hesh Funkciya stisnennya MD6 Vhidni i vihidni dani Yak vhidni dani funkciya prijmaye masiv N sho skladayetsya z n 89 8 bajtovih sliv 712 bajt i chislo raundiv r Funkciya povertaye masiv C z 16 elementiv po 8 bajt Konstanti t0 t1 t2 t3 t4 17 18 21 31 67 i n mod 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ri n 10 5 13 10 11 12 2 7 14 15 7 13 11 7 6 12 li n 11 24 9 16 15 9 27 15 6 2 29 8 15 5 31 9 Si n S i n 16 S 0 0x0123456789abcde S 0x7311c2812425cfa0 S j 1 S j lt lt lt 1 S j S Tilo funkciyi Poznachimo t 16r U kozhnomu raundi bude 16 krokiv Poznachimo cherez A 0 t n 1 masiv t n 8 bajtovih elementiv Pershi n elementiv neobhidno skopiyuvati z vhidnogo masivu N Osnovnij cikl funkciyi viglyadaye nastupnim chinom for i n to t n 1 t steps x Si n Ai n Ai t0 x x Ai t1 Ai t2 Ai t3 Ai t4 x x x gt gt ri n Ai x x lt lt li n Povernuti A t n 16 t n 1 PrimitkiRonald Rivest et Al The MD6 Hash Function 12 serpnya 2017 u Wayback Machine Crypto 2008 Ronald L Rivest Arhiv originalu za 9 listopada 2020 Schneier Bruce 1 lipnya 2009 MD6 Withdrawn from SHA 3 Competition Arhiv originalu za 21 bereznya 2012 Procitovano 9 lipnya 2009 PDF Arhiv originalu PDF za 22 lyutogo 2012 Procitovano 31 grudnya 2016 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite web title Shablon Cite web cite web a Obslugovuvannya CS1 Storinki z tekstom archived copy yak znachennya parametru title posilannya Ce nezavershena stattya z kriptografiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi