MD6

MD6 () — алгоритм хеширования переменной разрядности, разработанный профессором Рональдом Ривестом из Массачусетского Технологического Института в 2008 годуRonald L. Rivest, The MD6 hash function A proposal to NIST for SHA-3 . Предназначен для создания «отпечатков» или дайджестов сообщений произвольной длины. Предлагается на смену менее совершенному MD5. По заявлению авторов, алгоритм устойчив к дифференциальному криптоанализу. Используется для проверки целостности и, в некотором смысле, подлинности опубликованных сообщений, путём сравнения дайджеста сообщения с опубликованным. Эту операцию называют «проверка хеша» (hashcheck). Хеш-функции также широко используются для генерации ключей фиксированной длины для алгоритмов шифрования на основе заданной ключевой строки.

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

Алгоритм

В алгоритме хеш-функции использованы весьма оригинальные идеи. За один проход обрабатывается 512 байт, затрудняя проведение ряда атак и облегчая распараллеливание, для чего также применяются древовидные структуры. Входные данные и процедуры Mисходное сообщение длиной 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 байт.

Константы 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].

Примечания

Ссылки Официальная страница MD6.

Категория:Криптографические хеш-функции Категория:NIST hash function competition