MD4 (Message Digest 4) — криптографическая хеш-функция, разработанная профессором Массачусетского университета Рональдом Ривестом в 1990 году, и впервые описанная в RFC 1186. Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения. Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для выполнения процедур проверки подлинности удаленных рабочих станций Windows. Является предшественником MD5.
Предполагается, что на вход подано сообщение, состоящее из b {displaystyle b} бит, хеш которого нам предстоит вычислить. Здесь b {displaystyle b} — произвольное неотрицательное целое число; оно может быть нулём, не обязано быть кратным восьми, и может быть сколь угодно большим. Запишем сообщение побитно, в виде:
m 0 m 1 … m b − 1 {displaystyle m_{0}m_{1}ldots m_{b-1}}
Ниже приведены 5 шагов, используемые для вычисления хеша сообщения.
Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448. Таким образом, в результате расширения, сообщению недостает 64 бита до длины, кратной 512 битам. Расширение производится всегда, даже если сообщение изначально имеет нужную длину.
Расширение производится следующим образом: один бит, равный 1, добавляется к сообщению, а затем добавляются биты, равные 0, до тех пор, пока длина сообщения не станет равной 448 по модулю 512. В итоге, к сообщению добавляется как минимум 1 бит, и как максимум 512.
64-битное представление b {displaystyle b} (длины сообщения перед добавлением набивочных битов) добавляется к результату предыдущего шага. В маловероятном случае, когда b {displaystyle b} больше, чем 2 64 {displaystyle 2^{64}} , используются только 64 младших бита. Эти биты добавляются в виде двух 32-битных слов, и первым добавляется слово, содержащее младшие разряды.
На этом этапе (после добавления битов и длины сообщения) мы получаем сообщение длиной, кратной 512 битам. Это эквивалентно тому, что это сообщение имеет длину, кратную 16-ти 32-битным словам. Каждое 32-битное слово содержит четыре 8-битных, но следуют они не подряд, а наоборот (например, из восьми 8-битных слов (a b c d e f g h) мы получаем два 32-битных слова (dcba hgfe)). Пусть M [ 0 … N − 1 ] {displaystyle M[0ldots N-1]} означает массив слов получившегося сообщения (здесь N {displaystyle N} кратно 16).
Для вычисления хеша сообщения используется буфер, состоящий из 4 слов (32-битных регистров): ( A , B , C , D ) {displaystyle (A,B,C,D)} . Эти регистры инициализируются следующими шестнадцатеричными числами (младшие байты сначала):
word A {displaystyle A} : 01 23 45 67 word B {displaystyle B} : 89 ab cd ef word C {displaystyle C} : fe dc ba 98 word D {displaystyle D} : 76 54 32 10
Для начала определим три вспомогательные функции, каждая из которых получает на вход три 32-битных слова, и по ним вычисляет одно 32-битное слово.
F ( X , Y , Z ) = X Y ∨ ¬ X Z {displaystyle F(X,Y,Z)=XYlor
eg XZ} G ( X , Y , Z ) = X Y ∨ X Z ∨ Y Z {displaystyle G(X,Y,Z)=XYlor XZlor YZ} H ( X , Y , Z ) = X ⊕ Y ⊕ Z {displaystyle H(X,Y,Z)=Xoplus Yoplus Z}
На каждую битовую позицию F {displaystyle F} действует как условное выражение: если X {displaystyle X} , то Y {displaystyle Y} ; иначе Z {displaystyle Z} . Функция F {displaystyle F} могла бы быть определена с использованием + {displaystyle +} вместо ∨ {displaystyle lor } , поскольку X Y {displaystyle XY} и ¬ X Z {displaystyle
eg XZ} не могут равняться 1 {displaystyle 1} одновременно. G {displaystyle G} действует на каждую битовую позицию как функция максимального значения: если по крайней мере в двух словах из X , Y , Z {displaystyle X,Y,Z} соответствующие биты равны 1 {displaystyle 1} , то G {displaystyle G} выдаст 1 {displaystyle 1} в этом бите, а иначе G {displaystyle G} выдаст бит, равный 0 {displaystyle 0} . Интересно отметить, что если биты X {displaystyle X} , Y {displaystyle Y} и Z {displaystyle Z} статистически независимы, то биты F ( X , Y , Z ) {displaystyle F(X,Y,Z)} и G ( X , Y , Z ) {displaystyle G(X,Y,Z)} будут также статистически независимы. Функция H {displaystyle H} реализует побитовый x o r {displaystyle xor} , она обладает таким же свойством, как F {displaystyle F} и G {displaystyle G} .
Алгоритм хеширования на абстрактном языке программирования:
/* Обрабатываем каждый блок из 16-ти слов */ for i = 0 to N/16-1 do /* Заносим i-ый блок в переменную X */ for j = 0 to 15 do set X[j] to M[i*16+j]. end /* конец цикла по j */ /* Сохраняем A как AA, B как BB, C как CC, и D как DD */ AA = A BB = B CC = C DD = D /* Раунд 1 */ /* Пусть [abcd k s] означает следующую операцию: a = (a + F(b,c,d) + X[k]) <<< s. */ /* Производим 16 следующих операций: */ [ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19] [ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19] [ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19] [ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19] /* Раунд 2 */ /* Пусть [abcd k s] означает следующую операцию: a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */ /* Производим 16 следующих операций: */ [ABCD 0 3] [DABC 4 5] [CDAB 8 9] [BCDA 12 13] [ABCD 1 3] [DABC 5 5] [CDAB 9 9] [BCDA 13 13] [ABCD 2 3] [DABC 6 5] [CDAB 10 9] [BCDA 14 13] [ABCD 3 3] [DABC 7 5] [CDAB 11 9] [BCDA 15 13] /* Раунд 3 */ /* Пусть [abcd k s] означает следующую операцию: a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */ /* Производим 16 следующих операций: */ [ABCD 0 3] [DABC 8 9] [CDAB 4 11] [BCDA 12 15] [ABCD 2 3] [DABC 10 9] [CDAB 6 11] [BCDA 14 15] [ABCD 1 3] [DABC 9 9] [CDAB 5 11] [BCDA 13 15] [ABCD 3 3] [DABC 11 9] [CDAB 7 11] [BCDA 15 15] /* Затем производим следующие операции сложения. (Увеличиваем значение в каждом регистре на величину, которую он имел перед началом итерации по i */ A = A + AA B = B + BB C = C + CC D = D + DD end /* конец цикла по i */
Замечание. Величина 5A827999 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 2. Она же в восьмеричном представлении: 013240474631. Величина 6ED9EBA1 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 3. Она же в восьмеричном представлении: 015666365641. Эти данные приведены в книге Кнут, Искусство программирования, издание 1981 года, том 2, стр 660, таблица 2.
Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит, начиная с младшего бита A, и заканчивая старшим битом D.
Реализация алгоритма на языке C содержится в RFC 1320.
128-битные MD4 хеши представляют собой 32-значное число в 16-ричном формате. В следующем примере показан хеш 43-байтной строки ASCII:
MD4(«The quick brown fox jumps over the lazy dog») = 1bee69a46ba811185c194762abaeae90
Любое даже самое незначительное изменение хешируемой информации приводит к получению полностью отличного хеша, например, изменение в примере одной буквы с d на c:
MD4(«The quick brown fox jumps over the lazy cog») = b86e130ce7028da59e672d56ad0113df
Пример MD4 хеша для «нулевой» строки:
MD4(«») = 31d6cfe0d16ae931b73c59d7e0c089c0
Уровень безопасности, закладывавшийся в MD4, был рассчитан на создание достаточно устойчивых гибридных систем электронной цифровой подписи, основанных на MD4 и криптосистеме с открытым ключом. Рональд Ривест считал, что алгоритм хеширования MD4 можно использовать и для систем, нуждающихся в сильной криптостойкости. Но в то же время он отмечал, что MD4 создавался прежде всего как очень быстрый алгоритм хеширования, поэтому он может быть плох в плане криптостойкости. Как показали последовавшие исследования, он был прав, и для приложений, где важна прежде всего криптостойкость, стал использоваться алгоритм MD5.
Уязвимости в MD4 были продемонстрированы в статье Берта ден Бура и Антона Босселарса в 1991 году. Первая коллизия была найдена Гансом Доббертином в 1996 году.
Читайте также
Почему женщины так любят, когда им дарят розы
Веками розы считались символом любви и красоты. И нет ничего
Идеальное сочетание стиля и качества: CROCOTARI — сумки и рюкзаки из натуральной и эко кожи
В мире моды всегда ценятся предметы, которые сочетают в себе
Преимущества аренды зала для проведения дня рождения
Большие светодиодные экраны и видеостены: эффективный способ привлечения внимания
Отдых на Мальдивах: релаксация в раю
Как сделать Декларацию соответствия на обувь?
Практически любая обувь, попадающая на прилавки магазинов, предварительно проходит обязательную
Для ведения определённых видов деятельности, компаниям необходимо получать лицензию. Самостоятельно
Барная карта: навигатор для вашего гостя
Барная карта – ключевой элемент любого заведения, где должное внимание
Особенности лечения молочных зубов
Родители редко приводят к стоматологам детей с проблемами молочных зубов.
Сатин: особенности, применение и уход
Сатин — одна из популярных и востребованных тканей на рынке
Шопинг-антистресс: интернет-магазин брендовой одежды VIPAVENUE
Как восстановить работу пылесоса
Пылесос – незаменимый помощник в борьбе с пылью и грязью
Как Лила (древняя индийская игра) помогает решать жизненные проблемы
Mocheqi Musk — бренд профессиональной косметики для волос
Mocheqi Musk (Мачеки Маск) — это бренд профессиональной косметики, специализирующийся
Закодироваться от курения: новые методы борьбы со вредной привычкой
Курение является одной из самых распространенных и опасных привычек современного