MD6

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

Історія 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 ≤ 512Kдовільне ключове значення довжиною keylen байт (0 ≤ keylen ≤ 64), доповнене праворуч нулями числом в 64 — keylenLневід'ємний параметр розміром 1 байт, 0 ≤ L ≤ 64 (за замовчуванням L=64), позначає число паралельних обчислень і глибину дереваrневід'ємний параметр розміром 12 біт: число раундів (за замовчуванням r=40+[d/4])Qмасив з 15 елементів по 8 байт, його значення вказано нижчеƒфункція стиснення MD6, перетворює 712 байт вхідних даних (включаючи блок B розміром 512 байт) в результат C розміром 128 байт з використанням r раундів обчисленьPARпаралельна операція стиснення для кожного рівня дерева, ніколи не викликається при L = 0SEQпослідовна операція стиснення, ніколи не викликається при L = 64 <nowiki> Q = {0x7311c2812425cfa0, 0x6432286434aac8e7, 0xb60450e9ef68b7c1, 0xe8fb23908d9f06f1, 0xdd2e76cba691e5bf, 0x0cd0d63b2c30bc41, 0x1f8ccf6823058f8a, 0x54e5ed5b88e3775d, 0x4ad12aae0a6d6031, 0x3e7f16bb88222e0d, 0x8af8671d3fb50c2c, 0x995ad1178bd25c31, 0xc878c1dd04c4b633, 0x3b72066c7a1552ac, 0x0d6f3522631effcb} </nowiki>Масив 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 байт.

Константи t0t1t2t3t41718213167 (i — n) mod 160123456789101112131415ri-n10513101112271415713117612li-n1124916159271562298155319 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].

Примітки