MD6

MD6
Криптографическая хеш-функция
Название

MD6

Создан

2008

Опубликован

2008

Размер хеша

переменный, 0<d≤512

Число раундов

переменное. По-умолчанию, Без ключа=40+[d/4], с ключом=max(80,40+(d/4))

Тип

хеш-функция

MD6 (англ. Message Digest 6) — алгоритм хеширования переменной разрядности, разработанный профессором Рональдом Ривестом из Массачусетского Технологического Института в 2008 году[1]. Предназначен для создания «отпечатков» или дайджестов сообщений произвольной длины. Предлагается на смену менее совершенному MD5. По заявлению авторов, алгоритм устойчив к дифференциальному криптоанализу. Зная MD6, невозможно восстановить входное сообщение, так как разным сообщениям может соответствовать один MD6. Используется для проверки целостности и, в некотором смысле, подлинности опубликованных сообщений, путем сравнения дайджеста сообщения с опубликованным. Эту операцию называют «проверка хеша» (hashcheck). Хэш-функции также широко используются для генерации ключей фиксированной длины для алгоритмов шифрования на основе заданной ключевой строки.

Содержание

История

MD6 — один из серии алгоритмов по построению дайджеста сообщения, разработанный профессором Рональдом Л. Ривестом из Массачусетского Технологического Института. MD6 был впервые представлен на конференции Crypto 2008 в качестве кандидата на стандарт SHA-3. Однако позднее в 2009 на этой же конференции Ривест заявил, что MD6 ещё не готова к тому, чтобы стать стандартом. На официальном сайте MD6 он заявил, что, хотя, формально, заявка не отозвана, в алгоритме ещё остаются проблемы со скоростью и неспособностью обеспечить безопасность в версии с уменьшенным количеством раундов.[2] В итоге MD6 не прошёл во второй круг соревнования. Ранее, в декабре 2008, исследователь из Fortify Software открыл ошибку, связанную с переполнением буфера в оригинальной реализации MD6. 19 февраля 2009 профессор Ривест опубликовал данные об этой ошибке, а также представил исправление реализации.[3]

Алгоритм

В алгоритме хеш-функции использованы весьма оригинальные идеи. За один проход обрабатывается 512 байт, затрудняя проведение ряда атак и облегчая распараллеливание, для чего также применяются древовидные структуры.

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

M исходное сообщение длиной 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.
  • Обозначим 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, если j = 1, иначе z = 0;
  • Обозначим V как 8-байтовое значение r ǁ L ǁ z ǁ p ǁ keylen ǁ d аналогично предыдущей операции;
  • Обозначим U = (L + 1) * 256 + i – уникальный 8-байтовый идентификатор текущего блока;
  • Ci = ƒ(Q ǁ K ǁ U ǁ V ǁ 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. Ronald L. Rivest, The MD6 hash function A proposal to NIST for SHA-3
  2. Schneier, Bruce MD6 Withdrawn from SHA-3 Competition (July 1, 2009). Архивировано из первоисточника 21 марта 2012. Проверено 9 июля 2009.
  3. http://blog.fortify.com/repo/Fortify-SHA-3-Report.pdf

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "MD6" в других словарях:

  • MD6 — General Designers Ronald 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 Yin First… …   Wikipedia

  • MD6 — L algorithme MD6, pour Message Digest 6, est une fonction de hachage cryptographique qui permet d obtenir l empreinte numérique d un fichier (on parle souvent de message). MD6 a été développée par un groupe[1] mené par Ronald L. Rivest,… …   Wikipédia en Français

  • Message Digest 6 — MD6 L algorithme MD6, pour Message Digest 6, est une fonction de hachage cryptographique qui permet d obtenir l empreinte numérique d un fichier (on parle souvent de message). MD6 a été développée par un groupe[1] mené par Ronald L. Rivest,… …   Wikipédia en Français

  • MD2 — Криптографическая хеш функция Название MD2 Создан 1989 г. Опубликован апрель 1992 г. Размер хеша 128 бит Число раундов 18 Тип хеш функция MD2 (The MD2 Message Diges …   Википедия

  • Conficker — Common name Aliases Mal/Conficker A(Sophos) Win32/Conficker.A (CA) W32.Downadup (Symantec) W32/Downadup.A (F Secure) Conficker.A (Panda) Net Worm.Win32.Kido.bt ( …   Wikipedia

  • MD5 — General Designers Ronald Rivest First published April 1992 Series MD2, MD4, MD5, MD6 Detail Digest sizes 128 bits …   Wikipedia

  • MD4 — General Designers Ronald Rivest First published October 1990[1] Series MD2, MD4, MD5, MD6 Detail Dige …   Wikipedia

  • NIST hash function competition — La NIST hash function competition est une compétition organisée par la NIST afin de trouver une nouvelle fonction de hachage (SHA 3) destinée à remplacer les anciennes fonctions SHA 1 et SHA 2. Sommaire 1 Participants 1.1 Finalistes 1.2 …   Wikipédia en Français

  • Криптография — Немецкая криптомашина Lorenz использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от др. греч …   Википедия

  • Ривест, Рональд Линн — Рональд Л. Ривест Ronald L. Rivest …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»