Для чего может использоваться функция md4

Описание алгоритма хэширования MD4

Лабораторная работа №4

Реализация и исследование свойств алгоритмов хэширования

Введение

Функция хэширования – это функция, которая принимает на вход строку битов (или байтов) произвольной длины и выдаёт результат фиксированной длины. Результат работы хэш-функции называется хэш-кодом (или просто хэшем) сообщения. Хэш-функции находят широкое применение в теории кодирования, передачи информации, в разработке программного обеспечения. Примером простейших хэш-функций являются контрольные суммы и CRC-коды. Основное их назначение – обнаружение случайных повреждений данных. В криптографических приложениях к хэш-функциям предъявляются более жёсткие требования. Функции, отвечающие этим требованиям, называются криптографическими хэш-функциями. Наиболее известными алгоритмами хэширования являются алгоритмы семейств MD и SHA. Кроме того, можно построить хэш-функцию на основе блочного симметричного шифра. Ниже приведены основные области применения криптографических хэш-функций.

· Проверка целостности сообщения.

· Электронная цифровая подпись.

· Получение значения фиксированной длины.

· Генерация псевдослучайных чисел.

· Хранение и проверка паролей.

Свойства криптографических хэш-функций

Пусть M – сообщение, H – функция хэширования, h = H(M) – хэш-код.

Криптографическая хэш-функция должна обладать следующими свойствами:

1. Зная M, легко вычислить h.

2. Зная h, трудно найти M, для которого h = H(M).

4. Трудно найти два разных сообщения M и M¢, для которых H(M) = H(M¢ ).

5. Хэш-коды близких по содержимому сообщений должны сильно различаться.

6. Все значения хэш-функции равновероятны.

Свойство 1 требует, чтобы алгоритм вычисления хэш-кода являлся эффективным. Обычно в таких алгоритмах широко используются поразрядные операции над машинными словами.

Два сообщения M и M¢, для которых H(M) = H(M¢ ), называются коллизией. Задача поиска коллизий является более простой, чем поиск прообраза: согласно парадоксу «дней рождения» для нахождения коллизии достаточно перебрать в среднем 2 n/2 различных сообщений.

Свойство 5 утверждает, что два сообщения, отличающиеся всего одним битом, должны иметь сильно различающиеся хэш-коды. Данное свойство часто называют «лавинным» эффектом.

Свойство 6 требует, чтобы хэш-функция была близка к случайному отображению, то есть значение хэш-функции можно рассматривать как псевдослучайное число.

Описание алгоритма хэширования MD4

Алгоритм MD4 генерирует 128-битный хэш-код для произвольного входного сообщения. Входное сообщение представляет собой поток битов (или байтов), и может иметь произвольную битовую длину (в том числе нулевую), которую обозначим буквой b.

Словом будем называть 32-разрядное целое значение (unsigned int в языках C/C++). Последовательность байтов сообщения можно рассматривать как последовательность 32-битных слов. Группа из четырёх байтов рассматривается как слово, в котором младший байт является первым байтом группы. Например, группе из четырёх байтов (0x6F, 0x02, 0xE5, 0x8C) соответствует слово 0x8CE5026F (префикс 0x обозначает число в 16-ричной системе счисления). Обратное преобразования слова в последовательность байтов выполняется аналогично. Блоком будем называть последовательность из 512 битов. Блок можно представить в виде массива из 16-ти 32-битных слов.

Таким образом, исходное сообщение разбивается на блоки длиной 512 битов, каждый из которых последовательно подвергается процедуре хэширования. Результат хэширования предыдущего блока используется при вычислении хэша следующего блока.

Перед хэшированием сообщение расширяется так, чтобы его длина была кратной 512. Расширение сообщения состоит из двух этапов.

На первом этапе к сообщению добавляется единичный бит «1». После этого к нему добавляется необходимое число нулевых битов, чтобы длина сообщения была равна 448 по модулю 512. Единичный бит добавляется всегда, даже если длина сообщения уже равна 448 по модулю 512.

На втором этапе к сообщению добавляется 64-битное представление числа b (длины исходного сообщения). Отметим, что первое 32-битное слово содержит младшую часть b, а второе слово – старшую (второе слово равно нулю, если длина сообщения не превосходит 2 24 ). При записи этих 32-битных слов порядок байтов также обращается. В итоге длина расширенного сообщения будет кратной 512.

Для вычисления хэш-кода сообщения используется буфер, состоящий из 4-х слов: A, B, C, D. Вначале им присваиваются следующие шестнадцатеричные значения: A = 0x67452301, B = 0xefcdab89, C = 0x98badcfe, D = 0x10325476.

Представим блок в виде массива X, состоящего из 16 слов (X[0]…X[15]). Для каждого такого блока выполняются 3 раунда преобразований. Введём следующие обозначения.

Для первого раунда выражение [abcd k s] обозначает операцию

a = (a + F(b, c, d) + X[k]) n ) до разумного количества использовать не весь хэш-код, а лишь его часть. Пусть алгоритм MD4 возвращает хэш-код в виде четырёх слов A, B, C, D. Тогда в качестве хэш-кода будем использовать только младшие k битов слова A (т.е. k не должно превышать 32). Поиск коллизии производить следующим образом. Последовательно генерировать псевдослучайные строки фиксированной длины L и вычислять их хэш-коды. Для хранения результатов этих операций использовать 2 массива: в один массив записываются сгенерированные строки, а во второй – соответствующие им хэш-коды. Указанные действия продолжать до обнаружения двух одинаковых элементов в массиве хэш-кодов. Вывести на экран соответствующие строки – обнаруженную коллизию, а также количество сгенерированных при её поиске строк.

Задание 4. Программно реализовать поиск прообраза для заданного хэш-кода некоторой строки. В качестве хэш-кода также использовать только часть реального хэш-кода (см. Задание 3). Исходным сообщением является парольная фраза, для которой вычисляется частичный хэш-код длиной k младших бит слова A. Путем формирования псевдослучайных строк найти строку, дающую тот же самый частичный хэш. Вывести найденную строку и количество потребовавшихся итераций. В задании 4 для генерации строк использовать только печатные символы.

Источник

Для чего может использоваться функция md4

MD4 (Message Digest 4) — хеш-функция, разработанная профессором Массачусетского университета Рональдом Ривестом в 1990 году, и впервые описанная в RFC 1186. Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения. Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для выполнения процедур проверки подлинности удаленных рабочих станций Windows. Является предшественником MD5.

Содержание

Алгоритм MD4

Предполагается, что на вход подано сообщение, состоящее из бит, хеш которого нам предстоит вычислить. Здесь — произвольное неотрицательное целое число; оно может быть нулем, не обязано быть кратным восьми, и может быть сколь угодно большим. Запишем сообщение побитово, в виде:

Ниже приведены 5 шагов, используемые для вычисления хеша сообщения.

Шаг 1. Добавление недостающих битов.

Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448. Таким образом, в результате расширения, сообщению недостает 64 бита до длины, кратной 512 битам. Расширение производится всегда, даже если сообщение изначально имеет нужную длину.

Расширение производится следующим образом: один бит, равный 1, добавляется к сообщению, а затем добавляются биты, равные 0, до тех пор, пока длина сообщения не станет равной 448 по модулю 512. В итоге, к сообщению добавляется как минимум 1 бит, и как максимум 512.

Шаг 2. Добавление длины сообщения.

64-битное представление (длины сообщения перед добавлением набивочных битов) добавляется к результату предыдущего шага. В маловероятном случае, когда больше, чем , используются только 64 младших бита. Эти биты добавляются в виде двух 32-битных слов, и первым добавляется слово, содержащее младшие разряды.

На этом этапе (после добавления битов и длины сообщения) мы получаем сообщение длиной кратной 512 битам. Это эквивалентно тому, что это сообщение имеет длину, кратную 16-ти 32-битным словам. Каждое 32-битное слово содержит четыре 8-битных, но следуют они не подряд, а наоборот (например, из восьми 8-битных слов (a b c d e f g h) мы получаем два 32-битных слова (dcba hgfe)). Пусть означает массив слов получившегося сообщения (здесь кратно 16).

Шаг 3. Инициализация MD-буфера.

Для вычисления хеша сообщения используется буфер, состоящий из 4 слов (32-битных регистров): . Эти регистры инициализируются следующими шестнадцатеричными числами (младшие байты сначала):

Шаг 4. Обработка сообщения блоками по 16 слов.

Для начала определим три вспомогательные функции, каждая из которых получает на вход три 32-битных слова, и по ним вычисляет одно 32-битное слово.

На каждую битовую позицию действует как условное выражение: если , то ; иначе . Функция могла бы быть определена с использованием вместо , поскольку и не могут равняться одновременно. действует на каждую битовую позицию как функция максимального значения: если по крайней мере в двух словах из соответствующие биты равны , то выдаст в этом бите, а иначе выдаст бит, равный . Интересно отметить, что если биты , и статистически независимы, то биты и будут также статистически независимы. Функция реализует побитовый , она обладает таким же свойством, как и .

Алгоритм хеширования на абстрактном языке программирования:

Замечание. Величина 5A827999 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 2. Она же в восьмеричном представлении: 013240474631. Величина 6ED9EBA1 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 3. Она же в восьмеричном представлении: 015666365641. Эти данные приведены в книге Кнут, Искусство программирования, издание 1981 года, том 2, стр 660, таблица 2.

Шаг 5. Формирование хеша.

Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит, начиная с младшего бита A, и заканчивая старшим битом D.

Реализация алгоритма на языке C содержится в RFC 1320.

Примеры хешей

128-битные MD4 хеши представляют собой 32-х значное число в 16-ричном формате. В следующем примере показан хеш 43-байтной строки ASCII:

Любое даже самое незначительное изменение хешируемой информации приводит к получению полностью отличного хеша, например, изменение в примере одной буквы с d на c:

Пример MD4 хеша для «нулевой» строки:

Сравнение с MD5

Безопасность

Уровень безопасности, закладывавшийся в MD4, был рассчитан на создание достаточно устойчивых гибридных систем электронной цифровой подписи, основанных на MD4 и криптосистеме с открытым ключом. Рональд Ривест считал, что алгоритм хеширования MD4 можно использовать и для систем, нуждающихся в сильной криптостойкости. Но в то же время он отмечал, что MD4 создавался прежде всего как очень быстрый алгоритм хеширования, поэтому он может быть плох в плане криптостойкости. Как показали последовавшие исследования, он был прав, и для приложений, где важна прежде всего криптостойкость, стал использоваться алгоритм MD5.

Уязвимости

Уязвимости в MD4 были продемонстрированы в статье Берта ден Бура и Антона Босселарса в 1991 году. Первая коллизия была найдена Гансом Доббертином в 1996 году.

Источник

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

MD4 (Message Digest 4)

MD4

General
Designers	Ronald Rivest
First published	October 1990 [1]
Series	MD2, MD4, MD5, MD6
Cipher detail
Digest sizes	128 bits
Block sizes	512 bits
Rounds	3
Best public cryptanalysis
A collision attack published in 2007 can find collisions for full MD4 in less than 2 hash operations. [2]

MD4 (Message Digest 4) — хеш-функция, разработанная профессором Массачусетского технологического института Рональдом Ривестом в 1990 году, и впервые описанная в RFC 1186. Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения. Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для выполнения процедур проверки подлинности удаленных рабочих станций Windows. Является предшественником MD5.

Содержание

Алгоритм MD4

Предполагается, что на вход подано сообщение, состоящее из b <\displaystyle

> бит, хеш которого нам предстоит вычислить. Здесь b <\displaystyle

> — произвольное неотрицательное целое число; оно может быть нулем, не обязано быть кратным восьми, и может быть сколь угодно большим. Запишем сообщение побитово, в виде: m 0 m 1 … m b − 1 <\displaystyle m_0 m_1 \ldots m_>

Ниже приведены 5 шагов, используемые для вычисления хеша сообщения.

Шаг 1. Добавление недостающих битов.

Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448. Таким образом, в результате расширения, сообщению недостает 64 бита до длины, кратной 512 битам. Расширение производится всегда, даже если сообщение изначально имеет нужную длину.

Расширение производится следующим образом: один бит, равный 1, добавляется к сообщению, а затем добавляются биты, равные 0, до тех пор, пока длина сообщения не станет равной 448 по модулю 512. В итоге, к сообщению добавляется как минимум 1 бит, и как максимум 512.

Шаг 2. Добавление длины сообщения.

64-битное представление b <\displaystyle

> (длины сообщения перед добавлением набивочных битов) добавляется к результату предыдущего шага. В маловероятном случае, когда b <\displaystyle

Шаг 3. Инициализация MD-буфера.

Шаг 4. Обработка сообщения блоками по 16 слов.

Для начала определим три вспомогательные функции, каждая из которых получает на вход три 32-битных слова, и по ним вычисляет одно 32-битное слово.

Алгоритм хеширования на абстрактном языке программирования:

Замечание. Величина 5A827999 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 2. Она же в восьмеричном представлении: 013240474631. Величина 6ED9EBA1 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 3. Она же в восьмеричном представлении: 015666365641. Эти данные приведены в книге Кнут, Искусство программирования, издание 1981 года, том 2, стр 660, таблица 2.

Шаг 5. Формирование хеша.

Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит, начиная с младшего бита A, и заканчивая старшим битом D.

Источник

Для чего может использоваться функция md4

MD4 (Message Digest 4) — криптографическая хеш-функция, разработанная профессором Массачусетского университета Рональдом Ривестом в 1990 году, и впервые описанная в RFC 1186. Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения. Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для выполнения процедур проверки подлинности удаленных рабочих станций Windows. Является предшественником MD5.

Ниже приведены 5 шагов, используемые для вычисления хеша сообщения.

Шаг 1. Добавление недостающих битов.

Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448. Таким образом, в результате расширения, сообщению недостает 64 бита до длины, кратной 512 битам. Расширение производится всегда, даже если сообщение изначально имеет нужную длину.

Расширение производится следующим образом: один бит, равный 1, добавляется к сообщению, а затем добавляются биты, равные 0, до тех пор, пока длина сообщения не станет равной 448 по модулю 512. В итоге, к сообщению добавляется как минимум 1 бит, и как максимум 512.

Шаг 2. Добавление длины сообщения.

Шаг 3. Инициализация MD-буфера.

Шаг 4. Обработка сообщения блоками по 16 слов.

Для начала определим три вспомогательные функции, каждая из которых получает на вход три 32-битных слова, и по ним вычисляет одно 32-битное слово.

Замечание. Величина 5A827999 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 2. Она же в восьмеричном представлении: 013240474631. Величина 6ED9EBA1 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 3. Она же в восьмеричном представлении: 015666365641. Эти данные приведены в книге Кнут, Искусство программирования, издание 1981 года, том 2, стр 660, таблица 2.

Шаг 5. Формирование хеша.

Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит, начиная с младшего бита A, и заканчивая старшим битом D.

Реализация алгоритма на языке C содержится в RFC 1320.

128-битные MD4 хеши представляют собой 32-значное число в 16-ричном формате. В следующем примере показан хеш 43-байтной строки ASCII:

Любое даже самое незначительное изменение хешируемой информации приводит к получению полностью отличного хеша, например, изменение в примере одной буквы с d на c:

Пример MD4 хеша для «нулевой» строки:

Уровень безопасности, закладывавшийся в MD4, был рассчитан на создание достаточно устойчивых гибридных систем электронной цифровой подписи, основанных на MD4 и криптосистеме с открытым ключом. Рональд Ривест считал, что алгоритм хеширования MD4 можно использовать и для систем, нуждающихся в сильной криптостойкости. Но в то же время он отмечал, что MD4 создавался прежде всего как очень быстрый алгоритм хеширования, поэтому он может быть плох в плане криптостойкости. Как показали последовавшие исследования, он был прав, и для приложений, где важна прежде всего криптостойкость, стал использоваться алгоритм MD5.

Уязвимости в MD4 были продемонстрированы в статье Берта ден Бура и Антона Босселарса в 1991 году. Первая коллизия была найдена Гансом Доббертином в 1996 году.

Источник

Для чего может использоваться функция md4

Меню

MD4 (Message Digest 4) — хеш-функция, разработанная профессором Массачусетского университета Рональдом Ривестом в 1990 году, и впервые описанная в RFC 1186.

Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения.
Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для выполнения процедур проверкиподлинности удаленных рабочих станций Windows. Является предшественником MD5.

Алгоритм MD4

Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448. Таким образом, в результате расширения, сообщению недостает 64 бита до длины, кратной 512 битам. Расширение производится всегда, даже если сообщение изначально имеет нужную длину.

Расширение производится следующим образом: один бит, равный 1, добавляется к сообщению, а затем добавляются биты, равные 0, до тех пор, пока длина сообщения не станет равной 448 по модулю 512. В итоге, к сообщению добавляется как минимум 1 бит, и как максимум 512

Шаг 2. Добавление длины сообщения.

64-битное представление b (длины сообщения перед добавлением набивочных битов) добавляется к результату предыдущего шага. В маловероятном случае, когда b больше, чем 2 в степени 64, используются только 64 младших бита. Эти биты добавляются в виде двух 32-битных слов, и первым добавляется слово, содержащее младшие разряды.

На этом этапе (после добавления битов и длины сообщения) мы получаем сообщение длиной кратной 512 битам. Это эквивалентно тому, что это сообщение имеет длину, кратную 16-ти 32-битным словам. Пусть M[0. N-1] означает массив слов получившегося сообщения (здесь N кратно 16).

На каждую битовую позицию F действует как условное выражение: если X, то Y; иначе Z. Функция F могла бы быть определена с использованием вместо V, поскольку XY и _XZ не могут равняться 1 одновременно. G действует на каждую битовую позицию как функция максимального значения: если по крайней мере в двух словах из X,Y,Z соответствующие биты равны 1, то G выдаст 1 в этом бите, а иначе G выдаст бит, равный 0. Интересно отметить, что если биты X, Y и Z статистически независимы, то биты F(X,Y,Z) и G(X,Y,Z) будут также статистически независимы. Функция H реализует побитовый xor, она обладает таким же свойством, как F и G.

Шаг 5. Формирование хеша. Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит, начиная с младшего бита A, и заканчивая старшим битом D.

Источник