Перейти до вмісту

MD6

Матеріал з Вікіпедії — вільної енциклопедії.
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

[ред. | ред. код]

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].

Примітки

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


Замок Це незавершена стаття з криптографії.
Ви можете допомогти проєкту, виправивши або дописавши її.
Отримано з https://uk.wikipedia.org/w/index.php?title=MD6&oldid=44011857