MD6

MD6 (англ. Message Digest 6) — алгоритм хешування змінної розрядності, розроблений професором Рональдом Рівестом з Массачусетського Технологічного Інституту в 2008 році. Призначений для створення «відбитків» або дайджестів повідомлень довільної довжини. Пропонується на зміну менш досконалого MD5. За заявою авторів, алгоритм стійкий до диференціального криптоаналізу. Використовується для перевірки цілісності і, у деякому сенсі, достовірності опублікованих повідомлень, шляхом порівняння дайджесту повідомлення з опублікованими. Цю операцію називають «перевірка хешу» (англ. hashcheck). Хеш-функції також широко використовуються для генерації ключів фіксованої довжини для алгоритмів шифрування на основі заданого ключового рядка.

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))

Історія

MD6 — один із серії алгоритмів побудови дайджесту повідомлення, розроблений професором Рональдом Л. Рівестом з Массачусетського Технологічного Інституту. MD6 був вперше представлений на конференції Crypto 2008 як кандидат на стандарт SHA-3. Однак пізніше в 2009 на цій же конференції Рівест заявив, що MD6 ще не готовий до того, щоб стати стандартом. На офіційному сайті MD6 він заявив, що, хоча формально, заявка не відкликана, в алгоритмі ще залишаються проблеми зі швидкістю і нездатністю забезпечити безпеку у версії зі зменшеною кількістю раундів. У результаті MD6 не пройшов до другого кола змагання. Раніше, в грудні 2008, дослідник з Fortify Software знайшов помилку, пов'язану з переповненням буфера в оригінальній реалізації MD6. 19 лютого 2009 професор Рівест опублікував дані про цю помилку, а також представив виправлення реалізації.

Алгоритми

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

Вхідні данні і процедури

М	вхідне повідомлення довжиною m, 1 ≤ m ≤ (2^64-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, M₀ = M, m₀ = m.

Основний цикл

• l = l + 1.

• Якщо l = L + 1, повертаємо SEQ(M_l-1,d,K,L,r) як результат.

• M_l = PAR(M_l-1,d,K,L,r,l). Позначимо m_l як довжину M_l в бітах.

• Якщо M_l = 8 * c (тобто довжина M_l становить 8 * c байт), Повертаємо останні d бітів M_l. Інакше повертаємося до початку циклу.

Операція PAR

PAR повертає повідомлення довжиною ml = 1024 * max(1, [ml-1 / 4096]).

Тіло процедури

• Якщо потрібно, то розширюємо M_l-1, додаючи праворуч нульові біти, поки його довжина не стане кратна 512 байт. Тепер розіб'ємо M_l-1 на блоки B₀, B₁, …, B_j-1, где j = max(1, [m_l-1 / 512]);

• Для кожного блоку B_i, i = 0, 1, …, j-1, паралельно обчислюємо C_i за наступним алгоритмом:
  • Позначимо через p число доповнених бітів B_i, 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 * 2⁵⁶ + i — унікальний 8-байтовий ідентифікатор поточного блоку;
  • C_i = ƒ(Q ǁ K ǁ U ǁ V ǁ B_i).

• Повертаємо M_l = C₀ ǁ C₁ ǁ … ǁ C_j-1.

Операція SEQ

SEQ повертає хеш довжиною d біт. Дана операція ніколи не викликається, якщо L = 64.

Тіло процедури

• Позначимо через C₋₁ нульовий вектор довжиною 128 байт.

• Якщо потрібно, то розширюємо ML, додаючи праворуч нульові біти, поки його довжина не стане кратна 384 байтів. Тепер розіб'ємо ML на блоки B₀, B₁, …, B_j-1, где j = max(1, [m_L / 384]).

• Для кожного блоку B_i, i = 0, 1, …, j-1, паралельно обчислюємо C_i за наступним алгоритмом:
  • Позначимо через p число доповнених бітів B_i, 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) * 2⁵⁶ + i — унікальний 8-байтовий ідентифікатор поточного блоку;
  • C_i = ƒ(Q ǁ K ǁ U ǁ V ǁ C_i-1 ǁ B_i).
• Повертаємо останні d біт значення C_j-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

S_i-n = S^|_(i-n)/16

S^|₀ = 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 = S_i-n ⊕ A_i-n ⊕ A_i-t0

x = x ⊕ (A_i-t1 ^ A_i-t2) ⊕ (A_i-t3 ^ A_i-t4): x = x ⊕ (x >> r_i-n): Ai = x ⊕ (x << l_i-n)

Повернути A[t + n-16 .. t + n-1].

Примітки

1. Рональд Рівест et Al., The MD6 Hash Function [ 12 серпня 2017 у Wayback Machine.], Crypto 2008
2. Ronald L. Rivest. . Архів оригіналу за 9 листопада 2020.
3. Schneier, Bruce (1 липня 2009). MD6 Withdrawn from SHA-3 Competition. Архів оригіналу за 21 березня 2012. Процитовано 9 липня 2009.
4. (PDF). Архів оригіналу (PDF) за 22 лютого 2012. Процитовано 31 грудня 2016.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()