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

История

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

Алгоритм

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

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

M	исходное сообщение длиной 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 возвращает сообщение длиной m _l = 1024 * max(1, [ m _l-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 _-1 нулевой вектор длиной 128 байт.
• Если требуется, то расширяем M _L , добавляя справа нулевые биты, пока его длина не станет кратна 384 байт. Теперь разобьём M _L на блоки 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 байт.

Константы

t 0	t 1	t 2	t 3	t 4
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
r i-n	10	5	13	10	11	12	2	7	14	15	7	13	11	7	6	12
l i-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 = 16 r . (В каждом раунде будет 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-t 0}

x = x ⊕ (A _{i-t 1} ^ A _{i-t 2} ) ⊕ (A _{i-t 3} ^ A _{i-t 4} )

x = x ⊕ (x >> r _i-n )

Ai = x ⊕ (x << l _i-n )

Возвратить A [ t + n - 16 .. t + n - 1].

Примечания

Ссылки