Что такое Хэш или Хэширование? Хэш-функция: что это такое, зачем нужна и какой бывает.

Аннотация: В этой лекции сформулировано понятие хеш-функции, а также приведен краткий обзор алгоритмов формирования хеш-функций. Кроме того, рассмотрена возможность использования блочных алгоритмов шифрования для формирования хеш-функции.

Цель лекции: познакомиться с понятием "хеш-функция", а также с принципами работы таких функций.

Понятие хеш-функции

Хеш-функцией (hash function) называется математическая или иная функция, которая для строки произвольной длины вычисляет некоторое целое значение или некоторую другую строку фиксированной длины. Математически это можно записать так:

где М – исходное сообщение, называемое иногда прообразом , а h – результат, называемый значением хеш-функции (а также хеш-кодом или дайджестом сообщения (от англ. message digest )).

Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер, например, 64 или 128 бит. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи. Так, например, хеширование может применяться для сравнения данных: если у двух массивов данных хеш-коды разные, массивы гарантированно различаются; если одинаковые - массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет из-за того, что количество значений хеш-функций всегда меньше, чем вариантов входных данных. Следовательно, существует множество входных сообщений, дающих одинаковые хеш-коды (такие ситуации называются коллизиями ). Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Хеш-функции широко применяются в современной криптографии.

Простейшая хеш-функция может быть составлена с использованием операции "сумма по модулю 2" следующим образом: получаем входную строку, складываем все байты по модулю 2 и байт-результат возвращаем в качестве значения хеш-фукнции. Длина значения хеш-функции составит в этом случае 8 бит независимо от размера входного сообщения.

Например, пусть исходное сообщение, переведенное в цифровой вид, было следующим (в шестнадцатеричном формате):

Переведем сообщение в двоичный вид, запишем байты друг под другом и сложим биты в каждом столбике по модулю 2:

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Результат (0110 0101 (2) или 65 (16) ) и будет значением хеш-функции.

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

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:

хеш-функция должна быть применима к сообщению любого размера;
вычисление значения функции должно выполняться достаточно быстро;
при известном значении хеш-функции должно быть трудно (практически невозможно) найти подходящий прообраз М ;
при известном сообщении М должно быть трудно найти другое сообщение М’ с таким же значением хеш-функции, как у исходного сообщения;
должно быть трудно найти какую-либо пару случайных различных сообщений с одинаковым значением хеш-функции.

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

В настоящее время на практике в качестве хеш-функций применяются функции, обрабатывающие входное сообщение блок за блоком и вычисляющие хеш-значение h i для каждого блока M i входного сообщения по зависимостям вида

h i =H(M i ,h i-1),

где h i-1 – результат, полученный при вычислении хеш-функции для предыдущего блока входных данных.

В результате выход хеш-функции h n является функцией от всех n блоков входного сообщения.

Использование блочных алгоритмов шифрования для формирования хеш-функции

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

Простейшим способом использования блочного алгоритма для получения хеш-кода является шифрование сообщения в режиме CBC . В этом случае сообщение представляется в виде последовательности блоков, длина которых равна длине блока алгоритма шифрования. При необходимости последний блок дополняется справа нулями, чтобы получился блок нужной длины. Хеш-значением будет последний зашифрованный блок текста. При условии использования надежного блочного алгоритма шифрования полученное хеш-значение будет обладать следующими свойствами:

практически невозможно без знания ключа шифрования вычисление хеш-значения для заданного открытого массива информации;
практически невозможен без знания ключа шифрования подбор открытых данных под заданное значение хеш-функции.

Сформированное таким образом хеш-значение обычно называют имитовставкой или аутентификатором и используется для проверки целостности сообщения. Таким образом, имитовставка – это контрольная комбинация, зависящая от открытых данных и секретной ключевой информации. Целью использования имитовставки является обнаружение всех случайных или преднамеренных изменений в массиве информации. Значение, полученное хеш-функцией при обработке входного сообщения, присоединяется к сообщению в тот момент, когда известно, что сообщение корректно. Получатель проверяет целостность сообщения путем вычисления имитовставки полученного сообщения и сравнения его с полученным хеш-кодом, который должен быть передан безопасным способом. Одним из таких безопасных способов может быть шифрование имитовставки закрытым ключом отправителя, т.е. создание подписи. Возможно также шифрование полученного хеш-кода алгоритмом симметричного шифрования, если отправитель и получатель имеют общий ключ симметричного шифрования.

Указанный процесс получения и использования имитовставки описан в отечественном стандарте ГОСТ 28147-89. Стандарт предлагает использовать младшие 32 бита блока, полученного на выходе операции шифрования всего сообщения в режиме сцепления блоков шифра для контроля целостности передаваемого сообщения. Таким же образом для формирования имитовставки можно использовать любой блочный алгоритм симметричного шифрования .

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

На самом деле возможны еще несколько схем использования блочного шифра для формирования хеш-функции. Пусть М i – блок исходного сообщения, h i – значение хеш-функции на i-том этапе, f – блочный алгоритм шифрования, используемый в режиме простой замены, – операция сложения по модулю 2. Тогда возможны, например, следующие схемы формирования хеш-функции:

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

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является относительно низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них – MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

В самых различных отраслях информационных технологий находят свое применение хэш-функции. Они предназначены для того, чтобы, с одной стороны, значительно упростить обмен данными между пользователями и обработку файлов, используемых в тех или иных целях, с другой — оптимизировать алгоритмы обеспечения контроля доступа к соответствующим ресурсам. Хэш-функция — один из ключевых инструментов обеспечения парольной защиты данных, а также организации обмена документов, подписанных с помощью ЭЦП. Существует большое количество стандартов, посредством которых может осуществляться кэширование файлов. Многие из них разработаны российскими специалистами. В каких разновидностях могут быть представлены хэш-функции? Каковы основные механизмы их практического применения?

Что это такое?

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

Характеристики

Рассмотрим ключевые характеристики исследуемых алгоритмов. В числе таковых:

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

В числе иных важнейших свойств хэш-функции:

способность обрабатывать изначальные массивы данных произвольной длины;
формировать хешированные блоки фиксированной длины;
распределять значения функции на выходе равномерно.

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

Требования к хэш-функциям

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

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

Структура

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

В какой структуре может быть представлена используемая в подобных целях хеш-функция? Пример ее составления может быть таким: H (hash, то есть, хэш) = f (T (текст), H1), где H1 — алгоритм обработки текста T. Данная функция хеширует T таким образом, что без знания H1 открыть его как полноценный файл будет практически невозможно.

Использование хэш-функций на практике: скачивание файлов

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

В большинстве случаев для каждого файла определяется некая контрольная сумма — это и есть хэш. Она должна быть одинаковой для объекта, располагающегося на сервере и скачанного на компьютер пользователя. Если это не так, то файл может не открыться либо запуститься не вполне корректно.

Хэш-функция и ЭЦП

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

Электронная подпись представляет собой шифрование файла при задействовании открытого и закрытого ключей. То есть к исходному файлу прикрепляется зашифрованное с помощью закрытого ключа сообщение, а проверка ЭЦП осуществляется посредством открытого ключа. Если хэш-функция обоих документов совпадает — файл, находящийся у получателя, признается подлинным, а подпись отправителя распознается как верная.

Хеширование, как мы отметили выше, не является непосредственно компонентом ЭЦП, однако позволяет весьма эффективно оптимизировать алгоритмы задействования электронной подписи. Так, шифроваться может, собственно, только хэш, а не сам документ. В итоге скорость обработки файлов значительно возрастает, одновременно становится возможным обеспечивать более эффективные механизмы защиты ЭЦП, так как акцент в вычислительных операциях в этом случае будет ставиться не на обработке исходных данных, а на обеспечении криптографической стойкости подписи. Хэш-функция к тому же делает возможным подписывать самые разные типы данных, а не только текстовые.

Проверка паролей

Еще одна возможная область применения хеширования — организация алгоритмов проверки паролей, установленных для разграничения доступа к тем или иным файловым ресурсам. Каким образом при решении подобных задач могут быть задействованы те или иные виды хеш-функций? Очень просто.

Дело в том, что на большинстве серверов, доступ к которым подлежит разграничению, пароли хранятся в виде хэшированных значений. Это вполне логично — если бы пароли были представлены в исходном текстовом виде, хакеры, получившие доступ к ним, могли бы запросто читать секретные данные. В свою очередь, на основе хэш вычислить пароль непросто.

Каким образом осуществляется проверка доступа пользователя при задействовании рассматриваемых алгоритмов? Пароль, вводимый пользователем, сверяется с тем, что зафиксирован в хэш-функции, что хранится на сервере. Если значения текстовых блоков совпадают — пользователь получает необходимый доступ к ресурсам.

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

Коллизии хэш-функций

В теории хэш-функций предусмотрено такое явление, как коллизия. В чем его сущность? Коллизия хэш-функции — ситуация, при которой два разных файла имеют одинаковый хэш-код. Это возможно, если длина целевой последовательности символов будет небольшой. В этом случае вероятность совпадения хэша будет выше.

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

История появления

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

Особенности алгоритма SHA

Применение хэш-функций, базирующихся на стандарте SHA, чаще всего осуществляется в области разработки средств цифровой подписи документов DSA. Как мы отметили выше, алгоритм SHA поддерживает хэш 160 бит (обеспечивая так называемый «дайджест» последовательности символов). Изначально рассматриваемый стандарт делит массив данных на блоки по 512 бит. При необходимости, если длина последнего блока не дотягивает до указанной цифры, структура файла дополняется 1 и необходимым количеством нулей. Также в конце соответствующего блока вписывается код, фиксирующий длину сообщения. Рассматриваемый алгоритм задействует 80 логических функций, посредством которых обрабатывается 3 слова, представленные в 32 разрядах. Также в стандарте SHA предусмотрено использование 4 констант.

Сравнение алгоритмов хеширования

Изучим то, как соотносятся свойства хэш-функций, относящихся к разным стандартам, на примере сопоставления характеристик российского стандарта ГОСТ Р 34.11-94 и американского SHA, который мы рассмотрели выше. Прежде всего, следует отметить то, что алгоритм, разработанный в РФ, предполагает осуществление 4 операций по шифрованию в расчете на 1 цикл. Это соответствует 128 раундам. В свою очередь, в течение 1 раунда при задействовании SHA предполагается вычисление порядка 20 команд, при том что всего раундов 80. Таким образом, использование SHA позволяет в течение 1 цикла обработать 512 бит исходных данных. В то время как российский стандарт способен осуществить операции за цикл в 256 бит данных.

Специфика новейшего российского алгоритма

Выше мы отметили, что стандарт ГОСТ Р 34.11-94 был заменен более новым — ГОСТ Р 34.11-2012 «Стрибог». Исследуем его специфику подробнее.

Посредством данного стандарта могут быть реализованы, как и в случае с алгоритмами, рассмотренными выше, криптографические хеш-функции. Можно отметить, что новейший российский стандарт поддерживает блок входных данных в объеме 512 бит. Основные преимущества ГОСТ Р 34.11-2012:

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

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

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

Рассмотрим более подробно, каким образом исследуемые нами типы алгоритмов могут задействоваться в сфере криптографии. Ключевое требование к соответствующим функциям — стойкость к коллизиям, о которых мы сказали выше. То есть не должны формироваться повторяющиеся значения хеш-функции, если значения эти уже присутствуют в структуре соседствующего алгоритма. Прочим отмеченным выше критериям криптографические функции также должны соответствовать. Понятно, что всегда есть некая теоретическая возможность восстановления исходного файла на основе хэша, особенно если в доступе есть мощный вычислительный инструмент. Однако подобный сценарий предполагается свести к минимуму, благодаря надежным алгоритмам шифрования. Так, вычислить хэш-функцию будет очень сложно, если ее вычислительная стойкость соответствует формуле 2^{n/2}.

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

Итеративные схемы

Изучим теперь то, каким образом могут быть выстроены криптографические алгоритмы хеширования. В числе самых распространенных схем решения данной задачи — задействование итеративной последовательной модели. Она основана на использовании так называемой сжимающей функции, при которой количество входных бит существенно больше, чем тех, что фиксируются на выходе.

Разумеется, сжимающая функция обязана соответствовать необходимым критериям криптостойкости. При интеративной схеме первая операция по обработке потока входных данных делится на блоки, размер которых исчисляется в битах. Соответствующий алгоритм также задействует временные переменные величиной в заданном количестве бит. В качестве первого значения задействуется общеизвестное число, в то время как последующие блоки данных объединяются со значением рассматриваемой функции на выходе. Значением хэша становятся выходные показатели бит для последней итерации, в которых учитывается весь входной поток, включая первое значение. Обеспечивается так называемый «лавинный эффект» хеширования.

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

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

Блочный алгоритм

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

Однако, как мы отметили выше, рассматривая различные виды хеш-функций, блочные алгоритмы часто сопровождаются необходимостью задействования больших вычислительных мощностей. Если они недоступны — скорость обработки файлов может быть недостаточной для решения практических задач, связанных с использованием хэш-функций. Вместе с тем требуемую криптостойкость можно реализовать и при небольшом количестве операций с потоками исходных данных, в частности к решению подобных задач приспособлены рассмотренные нами алгоритмы — MD5, SHA, российские стандарты криптографического шифрования.

Он же хеш «хэш-функция»

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

Понятие «хэширование» означает детерминистское (однозначное и точно известное) вычисление набора символов фиксированной длины на основе входных данных произвольной длины. При этом изменение хотя бы одного символа в исходных данных гарантирует (с вероятностью, близкой к 100%), что и полученная фиксированная строка будет иной. Можно сказать, что хэширование это «снятие отпечатка» с большого набора данных.

Для чего всё это нужно? Давайте рассмотрим пример: вы скачали большой файл (положим, zip-архив) и желаете убедиться, что в нём нет ошибок. Вы можете узнать «хэш-сумму» (тот самый отпечаток) этого файла и сверить его с опубликованным на сайте. Если строки хэш-сумм различаются, то файл однозначно «битый».

Другой пример: чтобы обезопасить данные пользователей, банк не должен хранить их пароли такими, какие они есть, в своей базе данных. Вместо этого банк хранит хэш-суммы этих паролей и каждый раз при вводе пароля вычисляет его хэш-сумму и сверяет её с хранимой в базе. И тут возникает резонный вопрос о возможных «коллизиях», то есть одинаковых результатах хэширования разных паролей. Хорошая хэш-функция должна сводить коллизии к абсолютному минимуму, а для этого её нужно сделать довольно сложной и запутанной.

Находится в списке.

Методы сжатия преобразуемых данных на основе однонаправленных ХЭШ-функций

Хэш-функция (hash, hash-function) – это преобразование, получающее из данных произвольной длины некое значение (свертку) фиксированной длины. Простейшими примерами являются контрольные суммы (например, crc32). Бывают:

· криптографические хэши;

· программистские хэши.

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

m - исходные данные,

h(m) – хэш-функция от них.

Необратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0.

Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1 не равно m2, но h(m1) = h(m2).

Криптографические хэш-функции разделяются на два класса:

Хэш-функции без ключа (MDC (Modification (Manipulation) Detect Code) - коды),

Хэш-функции c ключом (MАC (Message Authentication Code) - коды).

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

Слабой хэш-функцией называется односторонняя функция H(x), удовлетворяющая следующим условиям:

1. аргумент х может быть строкой бит произвольной длины;

2. значение h(x) должно быть строкой бит фиксированной длины;

3. значение h(x) легко вычислить;

4. для любого фиксированного x вычислительно невозможно найти другой x" ≠ x, такой что h(x")=h(x).

Пара x" ≠ x, когда h(x")=h(x) называется коллизией хэш-функции.

Сильной хэш-функцией называется односторонняя функция h(x), удовлетворяющая условиям 1-4 для слабой хэш-функции и свойству 5:

5. вычислительно невозможно найти любую пару x" ≠ x, такую, что h(x")=h(x).
Поскольку из свойств 1-2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 5 говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.

Существует несколько алгоритмов вычисления хэш-функций

MD2 (Message Digest) – алгоритм криптографической свертки. Порождает блок длиной 128 бит от сообщения произвольной длины. Общая схема работы MD2:

a. дополнение текста сообщений до длины, кратной 128 бит;

b. вычисление 16-битной контрольной суммы, старшие разряды отбрасываются;

c. добавление контрольной суммы к тексту;

d. повторное вычисление контрольной суммы.

Алгоритм MD2 очень медленный, поэтому чаще применяются MD4, MD5, SHA (Secure Hash Algorithm). Результирующий хэш имеет длину 160 бит.

ГОСТ Р34.11-94. Российский алгоритм. Длина свертки - 256 бит (очень удобно для формирования по паролю ключа для ГОСТ 28147-89).

Национальный институт стандартов и технологий (НИСТ) США на своем веб-сайте http://www.nist.gov/sha/ опубликовал спецификации новых алгоритмов хеширования SHA-256, SHA-384 и SHA-512, цель которых - обеспечить уровень криптостойкости хэша, соответствующий длинам ключей нового стандарта шифрования DES.

Напомним, что n-битный хэш - это отображение сообщения произвольной длины в n-битную псевдослучайную последовательность (хэш-значение). Криптографический хэш, как особая разновидность такой функции, это n-битный хэш, обладающий свойствами «однонаправленности» и «стойкости к коллизиям».

До настоящего времени наиболее популярными хеш-функциями были созданные Райвистом MD4 и MD5, генерирующие хэш-коды длиной n=128, и алгоритм SHA-1, разработанный в АНБ США и порождающий хэш-код длиной n=160.

ГОСТ Р34.10-94 «Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма».

Вопросы:

1. Понятие хеш-функции.

2. Использование блочных алгоритмов шифрования для формирования хеш-функции.

3. Обзор алгоритмов формирования хеш-функций.

1. Понятие хеш-функции

Хеш-функцией (hash function) называется математическая или иная функция, которая для строки произвольной длины вычисляет некоторое целое значение или некоторую другую строку фиксированной длины. Математически это можно записать так:

h = H(M) ,

где М – исходное сообщение, называемое иногда прообразом , а h – результат, называемый значением хеш-функции (а также хеш-кодом или дайджестом сообщения (от англ. message digest )).

Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер, например, 64 или 128 бит. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи. Так, например, хеширование может применяться для сравнения данных: если у двух массивов данных хеш-коды разные, массивы гарантированно различаются; если одинаковые - массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет из-за того, что количество значений хеш-функций всегда меньше, чем вариантов входных данных. Следовательно, существует множество входных сообщений, дающих одинаковые хеш-коды (такие ситуации называются коллизиями ). Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Хеш-функции широко применяются в современной криптографии.

Простейшая хеш- функция может быть составлена с использованием операции "сумма по модулю 2" следующим образом: получаем входную строку, складываем все байты по модулю 2 и байт-результат возвращаем в качестве значения хеш-фукнции. Длина значения хеш-функции составит в этом случае 8 бит независимо от размера входного сообщения.

2 B 1 4 A 9 5 F E 4

Переведем сообщение в двоичный вид, запишем байты друг под другом и сложим биты в каждом столбике по модулю 2:

0010 1011

0001 0100

1010 1001

0101 1111

1110 0100

——————-

0010 1101

Результат: 0010 1101 или 2 D и будет значением хеш-функции.

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:

· хеш-функция должна быть применима к сообщению любого размера;

· вычисление значения функции должно выполняться достаточно быстро;

· при известном значении хеш-функции должно быть трудно (практически невозможно) найти подходящий прообраз М ;

· при известном сообщении М должно быть трудно найти другое сообщение М’ с таким же значением хеш-функции, как у исходного сообщения;

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

В настоящее время на практике в качестве хеш-функций применяются функции, обрабатывающие входное сообщение блок за блоком и вычисляющие хеш- значение h i для каждого блока M i входного сообщения по зависимостям вида

h i = H(M i ,h i-1),

где h i-1 – результат, полученный при вычислении хеш-функции для предыдущего блока входных данных.

В результате выход хеш-функции h n является функцией от всех n блоков входного сообщения.

2. Использование блочных алгоритмов шифрования для формирования хеш-функции.

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

Простейшим способом использования блочного алгоритма для получения хеш-кода является шифрование сообщения в режиме CBC (Cipher Block Chaining – Режим сцепления блоков шифротекста ). В этом случае сообщение представляется в виде последовательности блоков, длина которых равна длине блока алгоритма шифрования. При необходимости последний блок дополняется справа нулями, чтобы получился блок нужной длины. Хеш-значением будет последний зашифрованный блок текста. При условии использования надежного блочного алгоритма шифрования полученное хеш- значение будет обладать следующими свойствами:

· практически невозможно без знания ключа шифрования вычисление хеш-значения для заданного открытого массива информации;

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

Сформированное таким образом хеш- значение обычно называют имитовставкой или аутентификатором и используется для проверки целостности сообщения. Таким образом, имитовставка – это контрольная комбинация, зависящая от открытых данных и секретной ключевой информации. Целью использования имитовставки является обнаружение всех случайных или преднамеренных изменений в массиве информации. Значение, полученное хеш-функцией при обработке входного сообщения, присоединяется к сообщению в тот момент, когда известно, что сообщение корректно. Получатель проверяет целостность сообщения путем вычисления имитовставки полученного сообщения и сравнения его с полученным хеш-кодом, который должен быть передан безопасным способом. Одним из таких безопасных способов может быть шифрование имитовставки закрытым ключом отправителя, т.е. создание подписи. Возможно также шифрование полученного хеш-кода алгоритмом симметричного шифрования, если отправитель и получатель имеют общий ключ симметричного шифрования.

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

Таким образом, если обычную схему шифрования сообщения М с помощью блочного шифра f на ключе К мы записывали как E= f(M,K) , то схему получения хеш-кода h по описанному выше алгоритму можно представить как

h i = f ( h i -1 , M )

В качестве начального хеш-кода h 0 берут некоторую константу. Шифрование производится в режиме простой замены. При использовании указанного способа размер блока совпадает с длиной ключа и размером хеш-значения будет длина блока.

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

h i = f ( M , h i -1 ,)

На самом деле возможны еще несколько схем использования блочного шифра для формирования хеш-функции. Пусть М i – блок исходного сообщения, h i – значение хеш-функции на i -том этапе, f – блочный алгоритм шифрования, используемый в режиме простой замены, – операция сложения по модулю 2. Тогда возможны, например, следующие схемы формирования хеш-функции:

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является относительно низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования (наиболее распространенные из них – MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

3. Обзор алгоритмов формирования хеш-функций.

В настоящее время предложены и практически используются различные специальные алгоритмы для вычисления хеш-функции. Наиболее известными алгоритмами являются MD5, SHA-1, SHA-2 и другие версии SHA, а также отечественный алгоритм, изложенный в ГОСТ Р 34.11-94.

Алгоритм MD5 появился в начале 90-х годов ХХ века в результате усовершенствования алгоритма формирования хеш-функции MD4. Символы в названии " MD" означают Message Digest – краткое изложение сообщения. Автор алгоритмов MD4 и MD5 – Р. Ривест (R.Rivest). В результате использования MD5 для произвольного сообщения формируется 128-битное хеш- значение. Входные данные обрабатываются блоками по 512 бит. В алгоритме используются элементарные логические операции ( инверсия, конъюнкция, сложение по модулю 2, циклические сдвиги и др.), а также обыкновенное арифметическое сложение. Комплексное повторение этих элементарных функций алгоритма обеспечивает то, что результат после обработки хорошо перемешан. Поэтому маловероятно, чтобы два сообщения, выбранные случайно, имели одинаковый хеш-код. Алгоритм MD5 имеет следующее свойство: каждый бит полученного хеш-значения является функцией от каждого бита входа. Считается, что MD5 является наиболее сильной хеш-функцией для 128-битного хеш-значения.

Алгоритм SHA ( Secure Hash Algorithm – Безопасный хеш- алгоритм) был разработан национальным институтом стандартов и технологии ( NIST) США и опубликован в качестве американского федерального информационного стандарта в 1993 году. SHA-1, как и MD5, основан на алгоритме MD4. SHA-1 формирует 160-битное хеш- значение на основе обработки исходного сообщения блоками по 512 бит. В алгоритме SHA-1 также используются простые логические и арифметические операции. Наиболее важным отличием SHA-1 от MD5 является то, что хеш-код SHA-1 на 32 бита длиннее, чем хеш-код MD5. Если предположить, что оба алгоритма одинаковы по сложности для криптоанализа, то SHA-1 является более стойким алгоритмом. Используя атаку методом грубой силы (лобовую атаку), труднее создать произвольное сообщение, имеющее данный хеш-код, а также труднее создать два сообщения, имеющие одинаковый хеш-код.

В 2001 году национальный институт стандартов и технологии США принял в качестве стандарта три хеш-функции с большей длиной хеш-кода, чем у SHA-1. Часто эти хеш-функции называют SHA-2 или SHA-256, SHA-384 и SHA-512 (в названии указывается длина создаваемого алгоритмами хеш-кода). Эти алгоритмы отличаются не только длиной создаваемого хеш-кода, но и используемыми внутренними функциями и длиной обрабатываемого блока (у SHA-256 длина блока – 512, а у SHA-384 и SHA-512 длина блока – 1024 бита). Постепенные усовершенствования алгоритма SHA ведут к увеличению его криптостойкости. Несмотря на отличия рассматриваемых алгоритмов друг от друга, все они являются дальнейшим развитием SHA-1 и MD4 и имеют похожую структуру.

В России принят ГОСТ Р34.11-94, который является отечественным стандартом для хеш-функций. Его структура довольно сильно отличается от структуры алгоритмов SHA-1,2 или MD5, в основе которых лежит алгоритм MD4. Длина хеш-кода, создаваемого алгоритмом ГОСТ Р 34.11-94, равна 256 битам. Алгоритм последовательно обрабатывает исходное сообщение блоками по 256 бит справа налево. Параметром алгоритма является стартовый вектор хеширования – произвольное фиксированное значение длиной также 256 бит. В алгоритме ГОСТ Р 34.11-94 используются операции перестановки, сдвига, арифметического сложения, сложения по модулю 2. В качестве вспомогательной функции в ГОСТ 34.11-94 используется алгоритм по ГОСТ 28147-89 в режиме простой замены.

4. Требования к хэш-функциям

Хэш-функцией называется односторонняя функция, предназначенная для получения дайджеста или "отпечатков пальцев" файла, сообщения или некоторого блока данных.

Хэш-код создается функцией Н :

h = H (M)

Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины.

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

Хэш-функция Н , которая используется для аутентификации сообщений, должна обладать следующими свойствами:

1. Хэш-функция Н должна применяться к блоку данных любой длины.

2. Хэш-функция Н создает выход фиксированной длины.

3. Н (М) относительно легко (за полиномиальное время) вычисляется для любого значения М .

4. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h .

5. Для любого данного х вычислительно невозможно найти , что

H (y) = H (x).

6. Вычислительно невозможно найти произвольную пару (х , y ) такую, что H (y) = H (x) .

Первые три свойства требуют, чтобы хэш-функция создавала хэш-код для любого сообщения.

Четвертое свойство определяет требование односторонности хэш-функции: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду. Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. При перехвате передачи атакующий получает сообщение М и хэш-код С = Н (SAB || M) . Если атакующий может инвертировать хэш-функцию, то, следовательно, он может получить SAB || M = H-1 (C) . Так как атакующий теперь знает и М и SAB || M , получить SAB совсем просто.

Пятое свойство гарантирует, что невозможно найти другое сообщение, чье значение хэш-функции совпадало бы со значением хэш-функции данного сообщения. Это предотвращает подделку аутентификатора при использовании зашифрованного хэш-кода. В данном случае противник может читать сообщение и, следовательно, создать его хэш-код. Но так как противник не владеет секретным ключом, он не имеет возможности изменить сообщение так, чтобы получатель этого не обнаружил. Если данное свойство не выполняется, атакующий имеет возможность выполнить следующую последовательность действий: перехватить сообщение и его зашифрованный хэш-код, вычислить хэш-код сообщения, создать альтернативное сообщение с тем же самым хэш-кодом, заменить исходное сообщение на поддельное. Поскольку хэш-коды этих сообщений совпадают, получатель не обнаружит подмены.

Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Шестое свойство защищает против класса атак, известных как атака " день рождения ".

5. Простые хэш-функции

Все хэш-функции выполняются следующим образом. Входное значение (сообщение, файл и т.п.) рассматривается как последовательность n -битных блоков. Входное значение обрабатывается последовательно блок за блоком, и создается m -битное значение хэш-кода.

Одним из простейших примеров хэш-функции является побитовый XOR каждого блока:

С i - i -ый бит хэш-кода, 1 <= i <= n .

k – число n -битных блоков входа.

b ij – i -ый бит в j -ом блоке.

Затем все сообщение шифруется, включая хэш-код, в режиме СВС для создания зашифрованных блоков Y1, Y2, …, YN+1. По определению СВС имеем:

Но XN+1 является хэш-кодом:

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

Первоначальный стандарт, предложенный NIST, использовал простой XOR, который применялся к 64-битным блокам сообщения, затем все сообщение шифровалось, используя режим СВС.

"Парадокс дня рождения"

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

Так называемый " парадокс дня рождения " состоит в следующем. Предположим, количество выходных значений хэш-функции Н равно n . Каким должно быть число k , чтобы для конкретного значения X и значений Y1, , Yk вероятность того, что хотя бы для одного Yi выполнялось равенство

H (X) = H (Y)

была бы больше 0,5.

Для одного Y вероятность того, что H (X) = H (Y) , равна 1/n .

Соответственно, вероятность того, что , равна 1 – 1/n .

Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. (1 – 1/n)k .

Следовательно, вероятность, по крайней мере, одного совпадения равна

1 - (1 - 1/n)k

Таким образом, мы выяснили, что для m -битового хэш-кода достаточно выбрать 2m-1 сообщений, чтобы вероятность совпадения хэш-кодов была больше 0,5.

Теперь рассмотрим следующую задачу: обозначим P (n, k) вероятность того, что в множестве из k элементов, каждый из которых может принимать n значений, есть хотя бы два с одинаковыми значениями. Чему должно быть равно k , чтобы P (n, k) была бы больше 0,5 ?

Число различных способов выбора элементов таким образом, чтобы при этом не было дублей, равно

n(n-1) ... (n-k+1)=n!/(n-k)!

Всего возможных способов выбора элементов равно n k

Вероятность того, что дублей нет, равна n!/(n-k)!n k

Вероятность того, что есть дубли, соответственно равна

1 - n!/(n-k)!nk P (n, k) = 1 - n! / ((n-k)! x nk) = 1 - (n x (n-1) x ... x (n-k-1)) / nk = 1 - [ (n-1)/n x (n-2)/n x ... x (n-k+1)/n] = 1 - [(1- 1/n) x (1 - 2/n) x ... x (1 - (k-1)/n)]

Если хэш-код имеет длину m бит, т.е. принимает 2m значений, то

Подобный результат называется "парадоксом дня рождения", потому что в соответствии с приведенными выше рассуждениями для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0,5, в группе должно быть всего 23 человека. Этот результат кажется удивительным, возможно, потому, что для каждого отдельного человека в группе вероятность того, что с его днем рождения совпадет день рождения кого-то другого в группе, достаточно мала.

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

Н (М") = Н (М) ,

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

Тем не менее, возможны различного рода атаки, основанные на "парадоксе дня рождения". Возможна следующая стратегия:

1. Противник создает 2 m/2 вариантов сообщения, каждое из которых имеет некоторый определенный смысл. Противник подготавливает такое же количество сообщений, каждое из которых является поддельным и предназначено для замены настоящего сообщения.

2. Два набора сообщений сравниваются в поисках пары сообщений, имеющих одинаковый хэш-код. Вероятность успеха в соответствии с "парадоксом дня рождения" больше, чем 0,5. Если соответствующая пара не найдена, то создаются дополнительные исходные и поддельные сообщения до тех пор, пока не будет найдена пара.

3. Атакующий предлагает отправителю исходный вариант сообщения для подписи. Эта подпись может быть затем присоединена к поддельному варианту для передачи получателю. Так как оба варианта имеют один и тот же хэш-код, будет создана одинаковая подпись. Противник будет уверен в успехе, даже не зная ключа шифрования.

Таким образом, если используется 64-битный хэш-код, то необходимая сложность вычислений составляет порядка 232.

В заключение отметим, что длина хэш-кода должна быть достаточно большой. Длина, равная 64 битам, в настоящее время не считается безопасной. Предпочтительнее, чтобы длина составляла порядка 100 битов.

Использование цепочки зашифрованных блоков

Существуют различные хэш-функции, основанные на создании цепочки зашифрованных блоков, но без использования секретного ключа. Одна из таких хэш-функций была предложена Рабином. Сообщение М разбивается на блоки фиксированной длины М1, М2, . . . , МN и используется алгоритм симметричного шифрования, например DES, для вычисления хэш-кода G следующим образом:

Н 0 - начальное значение Н i = E Mi G = H N

Это аналогично использованию шифрования в режиме СВС, но в данном случае секретного ключа нет. Как и в случае любой простой хэш-функции, этот алгоритм подвержен "атаке дня рождения", и если шифрующим алгоритмом является DES и создается только 64-битный хэш-код, то система считается достаточно уязвимой.

Могут осуществляться другие атаки типа "дня рождения", которые возможны даже в том случае, если противник имеет доступ только к одному сообщению и соответствующему ему зашифрованному хэш-коду и не может получить несколько пар сообщений и зашифрованных хэш-кодов. Возможен следующий сценарий: предположим, что противник перехватил сообщение с аутентификатором в виде зашифрованного хэш-кода, и известно, что незашифрованный хэш-код имеет длину m битов. Далее противник должен выполнить следующие действия:

· Используя описанный выше алгоритм, вычислить незашифрованный хэш-код G .

· Создать поддельное сообщение в виде Q1, Q2, . . . , QN-2 .

· Вычислить Н i = E Qi для 1 <= i <= N-2 .

· Создать 2 m/2 случайных блоков Х и для каждого такого блока Х вычислить Е Х . Создать дополнительно 2 m/2 cлучайных блока Y и для каждого блока Y вычислить D Y [G] , где D – дешифрующая функция, соответствующая Е . Основываясь на "парадоксе дня рождения" можно сказать, что с высокой степенью вероятности эта последовательность будет содержать блоки Х и Y такие, что Е Х = D Y [Y] .

· Создать сообщение Q1, Q2, . . . , QN-2, X, Y . Это сообщение имеет хэш-код G и, следовательно, может быть использовано вместе с зашифрованным аутентификатором.

Эта форма атаки известна как атака "встреча посередине". В различных исследованиях предлагаются более тонкие методы для усиления подхода, основанного на цепочке блоков. Например, Девис и Прайс описали следующий вариант:

Возможен другой вариант:

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

Дальнейшие исследования были направлены на поиск других подходов к созданию функций хэширования.

Хэш-функция MD5

Рассмотрим алгоритм получения дайджеста сообщения MD5 (RFC 1321), разработанный Роном Ривестом из MIT.

Логика выполнения MD5

Алгоритм получает на входе сообщение произвольной длины и создает в качестве выхода дайджест сообщения длиной 128 бит. Алгоритм состоит из следующих шагов:

Рис. 8.1. Логика выполнения MD5

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

Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512 (). Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное 512. Добавление производится всегда, даже если сообщение имеет нужную длину. Например, если длина сообщения 448 битов, оно дополняется 512 битами до 960 битов. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое количество нулей.

Шаг 2: добавление длины

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

В результате первых двух шагов создается сообщение, длина которого кратна 512 битам. Это расширенное сообщение представляется как последовательность 512-битных блоков Y 0 , Y 1 , . . ., Y L-1 , при этом общая длина расширенного сообщения равна L * 512 битам. Таким образом, длина полученного расширенного сообщения кратна шестнадцати 32-битным словам.

Рис. 8.2. Структура расширенного сообщения

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

Используется 128-битный буфер для хранения промежуточных и окончательных результатов хэш-функции. Буфер может быть представлен как четыре 32-битных регистра (A, B, C, D). Эти регистры инициализируются следующими шестнадцатеричными числами:

А = 01234567 В = 89ABCDEF C = FEDCBA98 D = 76543210

Шаг 4: обработка последовательности 512-битных (16-словных) блоков

Основой алгоритма является модуль, состоящий из четырех циклических обработок, обозначенный как HMD5. Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую функцию, обозначаемую f F , f G , f H и f I соответственно.

Рис. 8.3. Обработка очередного 512-битного блока

Каждый цикл принимает в качестве входа текущий 512-битный блок Y q , обрабатывающийся в данный момент, и 128-битное значение буфера ABCD, которое является промежуточным значением дайджеста, и изменяет содержимое этого буфера. Каждый цикл также использует четвертую часть 64-элементной таблицы T, построенной на основе функции sin. i-ый элемент T, обозначаемый T[i], имеет значение, равное целой части от 2 32 * abs (sin (i)), i задано в радианах. Так как abs (sin (i)) является числом между 0 и 1, каждый элемент Т является целым, которое может быть представлено 32 битами. Таблица обеспечивает "случайный" набор 32-битных значений, которые должны ликвидировать любую регулярность во входных данных.

Для получения MD q+1 выход четырех циклов складывается по модулю 2 32 с MD q . Сложение выполняется независимо для каждого из четырех слов в буфере.

CLS s – циклический сдвиг влево на s битов 32-битного аргумента.

X [k] – M – k-ое 32-битное слово в q-ом 512 блоке сообщения.

T [i] – i-ое 32-битное слово в матрице Т.

+ – сложение по модулю 2 32 .

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

Массив из 32-битных слов X содержит значение текущего 512-битного входного блока, который обрабатывается в настоящий момент. Каждый цикл выполняется 16 раз, а так как каждый блок входного сообщения обрабатывается в четырех циклах, то каждый блок входного сообщения обрабатывается по схеме, показанной на Рис. 4 , 64 раза. Если представить входной 512-битный блок в виде шестнадцати 32-битных слов, то каждое входное 32-битное слово используется четыре раза, по одному разу в каждом цикле, и каждый элемент таблицы Т, состоящей из 64 32-битных слов, используется только один раз. После каждого шага цикла происходит циклический сдвиг влево четырех слов A, B, C и D. На каждом шаге изменяется только одно из четырех слов буфера ABCD. Следовательно, каждое слово буфера изменяется 16 раз, и затем 17-ый раз в конце для получения окончательного выхода данного блока.

дайджест.

2. Скорость: программная реализация алгоритма должна выполняться достаточно быстро. В частности, алгоритм должен быть достаточно быстрым на 32-битной архитектуре. Поэтому алгоритм основан на простом множестве элементарных операций над 32-битными словами.

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

4. Желательна little- endian архитектура: некоторые архитектуры процессоров (такие как линия Intel 80xxx) хранят левые байты слова в позиции младших адресов байта (little- endian). Другие (такие как SUN Sparcstation) хранят правые байты слова в позиции младших адресов байта (big MD4 дополнительная константа в первом цикле не применяется. Аналогичная дополнительная константа используется для каждого из шагов во втором цикле. Другая дополнительная константа используется для каждого из шагов в третьем цикле. В хэш-кода является функцией от каждого бита входа. Комплексное повторение элементарных функций f F , f G , f H и f I обеспечивает то, что результат хорошо перемешан; то есть маловероятно, чтобы два сообщения, выбранные случайно, даже если они имеют явно похожие закономерности, имели одинаковый дайджеста, которые создают одно и то же выходное значение. Это означает, что выполнение MD5 над единственным блоком из 512 бит приведет к одинаковому выходу для двух различных входных значений в буфере ABCD. Пока способа расширения данного подхода для успешной атаки на MD5 не существует.