- MD6
-
Криптографическая хеш-функция Название MD6
Создан Опубликован Размер хеша переменный, 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].
Примечания
- ↑ Ronald L. Rivest, The MD6 hash function A proposal to NIST for SHA-3
- ↑ Schneier, Bruce MD6 Withdrawn from SHA-3 Competition (July 1, 2009). Архивировано из первоисточника 21 марта 2012. Проверено 9 июля 2009.
- ↑ http://blog.fortify.com/repo/Fortify-SHA-3-Report.pdf
Ссылки
Хеш-функции Общего назначения Криптографические JH • HAVAL • Keccak (SHA-3) • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94
Категории:- Криптографические хеш-функции
- Хеш-функции
Wikimedia Foundation. 2010.