MD6
| Криптографическая</br>хеш-функция | |
| Название |
MD6 |
|---|---|
| Создан | |
| Опубликован | |
| Размер хеша |
переменный, 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 байт.
Константы
| 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"
Примечания
- ↑ Ronald L. Rivest, [people.csail.mit.edu/rivest/Rivest-TheMD6HashFunction.ppt The MD6 hash function A proposal to NIST for SHA-3]
- ↑ Schneier, Bruce [www.schneier.com/blog/archives/2009/07/md6.html MD6 Withdrawn from SHA-3 Competition] (July 1, 2009). Проверено 9 июля 2009. [www.webcitation.org/66KjhwBRu Архивировано из первоисточника 21 марта 2012].
- ↑ blog.fortify.com/repo/Fortify-SHA-3-Report.pdf
Ссылки
- [groups.csail.mit.edu/cis/md6/ Официальная страница MD6.]
| ||||||||||||||
Отрывок, характеризующий MD6
– Eh bien, et vous restez comme vous etes, chere princesse? – заговорила она. – On va venir annoncer, que ces messieurs sont au salon; il faudra descendre, et vous ne faites pas un petit brin de toilette! [Ну, а вы остаетесь, в чем были, княжна? Сейчас придут сказать, что они вышли. Надо будет итти вниз, а вы хоть бы чуть чуть принарядились!]Маленькая княгиня поднялась с кресла, позвонила горничную и поспешно и весело принялась придумывать наряд для княжны Марьи и приводить его в исполнение. Княжна Марья чувствовала себя оскорбленной в чувстве собственного достоинства тем, что приезд обещанного ей жениха волновал ее, и еще более она была оскорблена тем, что обе ее подруги и не предполагали, чтобы это могло быть иначе. Сказать им, как ей совестно было за себя и за них, это значило выдать свое волнение; кроме того отказаться от наряжения, которое предлагали ей, повело бы к продолжительным шуткам и настаиваниям. Она вспыхнула, прекрасные глаза ее потухли, лицо ее покрылось пятнами и с тем некрасивым выражением жертвы, чаще всего останавливающемся на ее лице, она отдалась во власть m lle Bourienne и Лизы. Обе женщины заботились совершенно искренно о том, чтобы сделать ее красивой. Она была так дурна, что ни одной из них не могла притти мысль о соперничестве с нею; поэтому они совершенно искренно, с тем наивным и твердым убеждением женщин, что наряд может сделать лицо красивым, принялись за ее одеванье.
– Нет, право, ma bonne amie, [мой добрый друг,] это платье нехорошо, – говорила Лиза, издалека боком взглядывая на княжну. – Вели подать, у тебя там есть масака. Право! Что ж, ведь это, может быть, судьба жизни решается. А это слишком светло, нехорошо, нет, нехорошо!
Нехорошо было не платье, но лицо и вся фигура княжны, но этого не чувствовали m lle Bourienne и маленькая княгиня; им все казалось, что ежели приложить голубую ленту к волосам, зачесанным кверху, и спустить голубой шарф с коричневого платья и т. п., то всё будет хорошо. Они забывали, что испуганное лицо и фигуру нельзя было изменить, и потому, как они ни видоизменяли раму и украшение этого лица, само лицо оставалось жалко и некрасиво. После двух или трех перемен, которым покорно подчинялась княжна Марья, в ту минуту, как она была зачесана кверху (прическа, совершенно изменявшая и портившая ее лицо), в голубом шарфе и масака нарядном платье, маленькая княгиня раза два обошла кругом нее, маленькой ручкой оправила тут складку платья, там подернула шарф и посмотрела, склонив голову, то с той, то с другой стороны.
– Нет, это нельзя, – сказала она решительно, всплеснув руками. – Non, Marie, decidement ca ne vous va pas. Je vous aime mieux dans votre petite robe grise de tous les jours. Non, de grace, faites cela pour moi. [Нет, Мари, решительно это не идет к вам. Я вас лучше люблю в вашем сереньком ежедневном платьице: пожалуйста, сделайте это для меня.] Катя, – сказала она горничной, – принеси княжне серенькое платье, и посмотрите, m lle Bourienne, как я это устрою, – сказала она с улыбкой предвкушения артистической радости.
Но когда Катя принесла требуемое платье, княжна Марья неподвижно всё сидела перед зеркалом, глядя на свое лицо, и в зеркале увидала, что в глазах ее стоят слезы, и что рот ее дрожит, приготовляясь к рыданиям.
– Voyons, chere princesse, – сказала m lle Bourienne, – encore un petit effort. [Ну, княжна, еще маленькое усилие.]
Маленькая княгиня, взяв платье из рук горничной, подходила к княжне Марье.
– Нет, теперь мы это сделаем просто, мило, – говорила она.
Голоса ее, m lle Bourienne и Кати, которая о чем то засмеялась, сливались в веселое лепетанье, похожее на пение птиц.
– Non, laissez moi, [Нет, оставьте меня,] – сказала княжна.
И голос ее звучал такой серьезностью и страданием, что лепетанье птиц тотчас же замолкло. Они посмотрели на большие, прекрасные глаза, полные слез и мысли, ясно и умоляюще смотревшие на них, и поняли, что настаивать бесполезно и даже жестоко.
– Au moins changez de coiffure, – сказала маленькая княгиня. – Je vous disais, – с упреком сказала она, обращаясь к m lle Bourienne, – Marieie a une de ces figures, auxquelles ce genre de coiffure ne va pas du tout. Mais du tout, du tout. Changez de grace. [По крайней мере, перемените прическу. У Мари одно из тех лиц, которым этот род прически совсем нейдет. Перемените, пожалуйста.]
– Laissez moi, laissez moi, tout ca m'est parfaitement egal, [Оставьте меня, мне всё равно,] – отвечал голос, едва удерживающий слезы.
M lle Bourienne и маленькая княгиня должны были признаться самим себе, что княжна. Марья в этом виде была очень дурна, хуже, чем всегда; но было уже поздно. Она смотрела на них с тем выражением, которое они знали, выражением мысли и грусти. Выражение это не внушало им страха к княжне Марье. (Этого чувства она никому не внушала.) Но они знали, что когда на ее лице появлялось это выражение, она была молчалива и непоколебима в своих решениях.
– Vous changerez, n'est ce pas? [Вы перемените, не правда ли?] – сказала Лиза, и когда княжна Марья ничего не ответила, Лиза вышла из комнаты.
Княжна Марья осталась одна. Она не исполнила желания Лизы и не только не переменила прически, но и не взглянула на себя в зеркало. Она, бессильно опустив глаза и руки, молча сидела и думала. Ей представлялся муж, мужчина, сильное, преобладающее и непонятно привлекательное существо, переносящее ее вдруг в свой, совершенно другой, счастливый мир. Ребенок свой, такой, какого она видела вчера у дочери кормилицы, – представлялся ей у своей собственной груди. Муж стоит и нежно смотрит на нее и ребенка. «Но нет, это невозможно: я слишком дурна», думала она.
– Пожалуйте к чаю. Князь сейчас выйдут, – сказал из за двери голос горничной.
Она очнулась и ужаснулась тому, о чем она думала. И прежде чем итти вниз, она встала, вошла в образную и, устремив на освещенный лампадой черный лик большого образа Спасителя, простояла перед ним с сложенными несколько минут руками. В душе княжны Марьи было мучительное сомненье. Возможна ли для нее радость любви, земной любви к мужчине? В помышлениях о браке княжне Марье мечталось и семейное счастие, и дети, но главною, сильнейшею и затаенною ее мечтою была любовь земная. Чувство было тем сильнее, чем более она старалась скрывать его от других и даже от самой себя. Боже мой, – говорила она, – как мне подавить в сердце своем эти мысли дьявола? Как мне отказаться так, навсегда от злых помыслов, чтобы спокойно исполнять Твою волю? И едва она сделала этот вопрос, как Бог уже отвечал ей в ее собственном сердце: «Не желай ничего для себя; не ищи, не волнуйся, не завидуй. Будущее людей и твоя судьба должна быть неизвестна тебе; но живи так, чтобы быть готовой ко всему. Если Богу угодно будет испытать тебя в обязанностях брака, будь готова исполнить Его волю». С этой успокоительной мыслью (но всё таки с надеждой на исполнение своей запрещенной, земной мечты) княжна Марья, вздохнув, перекрестилась и сошла вниз, не думая ни о своем платье, ни о прическе, ни о том, как она войдет и что скажет. Что могло всё это значить в сравнении с предопределением Бога, без воли Которого не падет ни один волос с головы человеческой.
