MD6
Загальні | |
---|---|
Розробники | Рональд Рівест, 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)) [1] |
MD6 (англ. Message Digest 6) — алгоритм хешування змінної розрядності, розроблений професором Рональдом Рівестом з Массачусетського Технологічного Інституту в 2008 році[2]. Призначений для створення «відбитків» або дайджестів повідомлень довільної довжини. Пропонується на зміну менш досконалого MD5. За заявою авторів, алгоритм стійкий до диференціального криптоаналізу. Використовується для перевірки цілісності і, у деякому сенсі, достовірності опублікованих повідомлень, шляхом порівняння дайджесту повідомлення з опублікованими. Цю операцію називають «перевірка хешу» (англ. hashcheck). Хеш-функції також широко використовуються для генерації ключів фіксованої довжини для алгоритмів шифрування на основі заданого ключового рядка.
MD6 — один із серії алгоритмів побудови дайджесту повідомлення, розроблений професором Рональдом Л. Рівестом з Массачусетського Технологічного Інституту. MD6 був вперше представлений на конференції Crypto 2008 як кандидат на стандарт SHA-3. Однак пізніше в 2009 на цій же конференції Рівест заявив, що MD6 ще не готовий до того, щоб стати стандартом. На офіційному сайті MD6 він заявив, що, хоча формально, заявка не відкликана, в алгоритмі ще залишаються проблеми зі швидкістю і нездатністю забезпечити безпеку у версії зі зменшеною кількістю раундів.[3] У результаті MD6 не пройшов до другого кола змагання. Раніше, в грудні 2008, дослідник з Fortify Software знайшов помилку, пов'язану з переповненням буфера в оригінальній реалізації MD6. 19 лютого 2009 професор Рівест опублікував дані про цю помилку, а також представив виправлення реалізації.[4]
У алгоритмі хеш-функції застосовані досить оригінальні ідеї. за один прохід обробляється 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 повертає повідомлення довжиною 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 повертає хеш довжиною 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 як підсумковий хеш.
Як вхідні дані функція приймає масив 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. The MD6 hash function A proposal to NIST for SHA-3. Архів оригіналу за 9 листопада 2020.
- ↑ Schneier, Bruce (1 липня 2009). MD6 Withdrawn from SHA-3 Competition. Архів оригіналу за 21 березня 2012. Процитовано 9 липня 2009.
- ↑ Архівована копія (PDF). Архів оригіналу (PDF) за 22 лютого 2012. Процитовано 31 грудня 2016.
{{cite web}}
: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
![]() |
Це незавершена стаття з криптографії. Ви можете допомогти проєкту, виправивши або дописавши її. |