WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте
MD6
Создан 2008
Опубликован 2008
Размер хеша переменный, 0<d≤512
Число раундов переменное. По-умолчанию, Без ключа=40+[d/4], с ключом=max(80,40+(d/4))
Тип хеш-функция

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

Константы

t0t1t2t3t4
1718213167
(i - n) mod 160123456789101112131415
ri-n10513101112271415713117612
li-n1124916159271562298155319

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). Проверено 9 июля 2009. Архивировано 21 марта 2012 года.
  3. ↑ Архивированная копия (недоступная ссылка). Проверено 28 ноября 2010. Архивировано 22 февраля 2012 года.

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии