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

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

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

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

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

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

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

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

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

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

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

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

Структура

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Популярные стандарты хеширования

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

В свою очередь, при шифровании достаточно широкое применение находят стандарты MD4 и MD5. Еще один популярный криптографический алгоритм — SHA-1. В частности, он характеризуется размером хэша 160 бит, что больше, чем у MD5 — данный стандарт поддерживает 128 бит. Есть российские стандарты, регулирующие использование хэш-функций, — ГОСТ Р 34.11-94, а также заменивший его ГОСТ Р 34.11-2012. Можно отметить, что величина хэша, предусмотренная алгоритмами, принятыми в РФ, составляет 256 бит.

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

Особенности алгоритма 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, российские стандарты криптографического шифрования.

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

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

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

Что происходит, когда размер входных данных меньше фиксированного размера выходных данных (например, хеширование пароля "abc")?

Хорошо, дайте мне посмотреть, есть ли у меня это прямо:

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

6 ответов

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

Устойчивость к прообразу - это другое свойство, чем обратимость. Функция обратима, если задано y = f (x), существует ровно один x, который подходит (легко или нет). Например, определим f (x) = x mod 10. Тогда f не обратимо. Из f (x) = 7 вы не можете определить, было ли x 17, 27 или что-то еще. Но f не является устойчивым к прообразу, так как значения x "такие, что f (x) = 7 легко найти. x "= 17, 27, 12341237 и т.д. все работают.

При выполнении криптографии вам обычно нужны функции, устойчивые к прообразу (и другие свойства, такие как сопротивление столкновению), а не только то, что не обратимо.

Предупреждение: длинный ответ

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

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

(Несмотря на распространенное мнение о ненадежности MD5, MD5 по-прежнему устойчив к прообразу. Любой, кто не верит мне, может дать мне все, что хеширует до . Что MD5 не имеет, это сопротивление столкновения , что совсем другое.)

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

Так возникает вопрос: почему бы и нет? (Или, другими словами, как вы делаете функцию прообразом устойчивой?)

Ответ заключается в том, что криптографические хеш-функции имитируют хаотические системы. Они берут ваше сообщение, разбивают его на блоки, смешивают эти блоки вокруг, блокируют некоторые из блоков, смешивают эти блоки вокруг и повторяют это много раз (ну, одна криптографическая хэш-функция делает это, другие имеют свои собственные методы). Поскольку блоки взаимодействуют друг с другом, блок C не только должен взаимодействовать с блоком D, чтобы создать блок A, но он должен взаимодействовать с блоком E, чтобы создать блок B. Теперь, конечно, вы можете найти значения блоков C, D, E, который будет генерировать блоки A и B в вашем хеш-значении, но по мере того, как вы идете дальше назад, вам понадобится блок F, который взаимодействует с C, чтобы сделать D, а с E сделать B, и такой блок не может делать как в в то же время! Вы должны были угадать неправильные значения для C, D и E.

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

1: Основная цель хэша состоит в том, чтобы отобразить очень и очень большое пространство в меньшем, но все же очень большом пространстве (например, MD5, который возьмет "что угодно" и преобразует его в пространство размером 2 ^ 128 - большой, но не такой большой, как aleph-0.)

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

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

Таким образом, хороший хеш, который даже использует пространство назначения, затруднит поиск двух входов с одним и тем же выходом, просто по шансам: если MD5 будет идеальным, вероятность того, что два входа будет иметь одинаковый выход, будет 2 ^ -128. Это довольно приличные шансы: лучшее, что вы можете сделать, не прибегая к большему выходному пространству. (По правде говоря, MD5 не совершенен, что является одной из вещей, которые делают его уязвимым.)

Но все равно будет верно, что огромное количество входов будет отображаться на любой заданный хеш, поскольку входное пространство "бесконечно", а деление бесконечности на 2 ^ 128 все равно дает вам бесконечность.

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

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

edit . В криптографии важно также, чтобы хеш-функция была устойчивой к атакам preimage, интуитивно, что трудно угадать вход для данного выхода, даже зная много других пар ввода/вывода, Функция "sum", вероятно, можно было бы догадаться довольно легко (но поскольку она уничтожает данные, все же может быть нелегко отменить).

Это свойства хэш-функций вообще.

Слово предостережения, однако, MD5 больше не следует использовать из-за обнаруженных в нем уязвимостей. Проверьте раздел "Уязвимости" и внешние ссылки, подробно описывающие эти атаки. http://en.wikipedia.org/wiki/Md5 Вы можете сделать столкновение MD5, изменив только 128 бит в сообщении.

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

SHA-256 является безопасной отправной точкой для технологий в течение следующих нескольких десятилетий.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конец работы -

Эта тема принадлежит разделу:

Конспект лекций по дисциплине программно-аппаратные средства защиты информации основные понятия и определения

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

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Твитнуть

Все темы данного раздела:

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

Сервисы безопасности
Основными сервисами безопасности являются следующие: Конфиденциальность - предотвращение пассивных атак для передаваемых или хранимых данных.

Модель сетевого взаимодействия
Модель безопасного сетевого взаимодействия в общем виде можно представить следующим образом:

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

Сеть Фейстеля
Блочный алгоритм преобразовывает n-битный блок незашифрованного текста в n-битный блок зашифрованного текста. Число блоков длины n равно 2n. Для того чтобы преобразование было обр

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

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

Используемые критерии при разработке алгоритмов
Принимая во внимание перечисленные требования, обычно считается, что алгоритм симметричного шифрования должен: · Манипулировать данными в больших блоках, предпочтительно размером 16

Принципы разработки
Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 г

Теперь рассмотрим последовательность преобразований, используемую в каждом раунде.

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

Недостатки двойного DES
Простейший способ увеличить длину ключа состоит в повторном применении DES с двумя разными ключами. Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрова

Тройной DES с двумя ключами
Очевидное противодействие атаке "встреча посередине" состоит в использовании третьей стадии шифрования с тремя различными ключами. Это поднимает стоимость лобовой атаки до 2168

Алгоритм Blowfish
Blowfish является сетью Фейстеля, у которой количество итераций равно 16. Длина блока равна 64 битам, ключ может иметь любую длину в пределах 448 бит. Хотя перед

Генерация подключей
Подключи вычисляются с использованием самого алгоритма Blowfish. 1. Инициализировать первый Р -массив и четыре S-boxes фиксированной строкой. 2. Выполнить опе

Криптографическая стойкость
Следующие характеристики IDEA характеризуют его криптографическую стойкость: 1. Длина блока: длина блока должна быть достаточной, чтобы скрыть все статистиче

Последовательность преобразований отдельного раунда
Рассмотрим последовательность преобразований отдельного раунда. Одним из основных элементов алгоритма, обеспечивающих диффузию, является структура, называемая МА (умножение/с

Создание подключей
Пятьдесят два 16-битных подключа создаются из 128-битного ключа шифрования следующим образом. Первые восемь подключей, которые обозначим как Z1, Z2, ...,

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

Алгоритм ГОСТ 28147
Алгоритм ГОСТ 28147 является отечественным стандартом для алгоритмов симметричного шифрования. ГОСТ 28147 разработан в 1989 году, является блочным алгоритмо

Режимы выполнения алгоритмов симметричного шифрования
Для любого симметричного блочного алгоритма шифрования определено четыре режима выполнения. ECB - Electronic Codebook - каждый блок из 64 бит незашифрова

Режим ECB
Данный режим является самым простым режимом, при котором незашифрованный текст обрабатывается последовательно, блок за блоком. Каждый блок шифруется, используя один и тот же ключ. Если сообщение дл

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

Режим CFB
Блочный алгоритм предназначен для шифрования блоков определенной длины. Однако можно преобразовать блочный алгоритм в поточный алгоритм шифрования, используя последние два режима. Поточный

Режим OFB
Данный режим подобен режиму CFB. Разница заключается в том, что выход алгоритма в режиме OFB подается обратно в регистр, тогда как в режиме CFB в регистр подается результат при

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

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

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

Циклическое шифрование
Рис. 3.14.Циклическое шифрование В данном случ

Генератор псевдослучайных чисел ANSI X9.17
Один из наиболее сильных генераторов псевдослучайных чисел описан в ANSI X9.17. В число приложений, использующих эту технологию, входят приложения финансовой безопасности и PGP.

Историческая справка
2 января 1997 года NIST объявил о начале разработки AES, и 12 сентября 1997 года были представлены официальные требования к алгоритмам. В этих требованиях указывалось, что целью NI

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

Критерий оценки
В сентябре 1997 года, объявив об алгоритмах кандидатов, специалисты NIST определили общий критерий, который должен использоваться при сравнении алгоритмов. Критерий оценки бы

Качественный или количественный критерий
На одной из первых встреч по планированию второго этапа обсуждений была рассмотрена возможность количественного подхода, используя который каждый алгоритм или комбинация алгоритмов будет получать о

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

Запасной алгоритм
Как уже отмечалось, существует взаимосвязь между обсуждениями проблемы нескольких алгоритмов AES и выбором запасного алгоритма, особенно в случае единственного алгоритма AES. Backu

Модификация алгоритмов
На первом и втором этапах обсуждения был отмечен интерес к увеличению числа раундов в некоторых алгоритмах. Во многих случаях увеличение количества раундов объяснялось. Так, про Rijndael

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

Языки реализации ПО
Выполнение также зависит от использования конкретного языка (например, ассемблер, компилируемый или интерпретируемый язык высокого уровня). В некоторых случаях играет роль конкретное ПО. Сущ

Изменение скорости выполнения в зависимости от длины ключа
Программное выполнение MARS, RC6 и Serpent не очень сильно изменяется в зависимости от длины ключа. Однако для Rijndael иTwofish установление ключа или шиф

Краткий вывод о скорости выполнения на основных программных платформах
Огромное количество информации собрано относительно скорости финалистов на различных программных платформах. Эти платформы включают 32-битные процессоры (реализации на С и Java), 64-битные п

Окружения с ограничениями пространства
В некоторых окружениях, обладающих небольшими объемами RAM и/или ROM для таких целей, как хранение кода (обычно в ROM), представление объектов данных, таких как S-boxes (которые могут

Замечания по финалистам
MARS имеет определенные сложности в силу гетерогенной структуры раунда (четыре различных типа раунда). Для S-boxes необходимо 2 Kbytes ROM, что не является проблемой,

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

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

Основные способы использования алгоритмов с открытым ключом
Основными способами использования алгоритмов с открытым ключом являются шифрование/дешифрование, создание и проверка подписи и обмен ключа. Шифрование с о

Описание алгоритма
Алгоритм, разработанный Ривестом, Шамиром и Адлеманом, использует выражения с экспонентами. Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа n. Шифро

Создание ключей
Создание ключей включает следующие задачи: 1. Определить два простых числа р и q. 2. Выбрать е и вычислить d. Прежде всего, рассмотрим проблемы, связанные с выбором р и q

Обсуждение криптоанализа
Можно определить четыре возможных подхода для криптоанализа алгоритма RSA: 1. Лобовая атака: перебрать все возможные закрытые ключи. 2. Разложить n на два простых со

Алгоритм обмена ключа Диффи-Хеллмана
Первая публикация данного алгоритма открытого ключа появилась в статье Диффи и Хеллмана, в которой вводились основные понятия криптографии с открытым ключом и в общих чертах упоминалс

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

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

Шаг 4: Обработка последовательности 512-битных (16-словных) блоков
Основой алгоритма является модуль, состоящий из четырех циклических обработок, обозначенный как HMD5. Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую фу

Шаг 5: Выход
После обработки всех L 512-битных блоков выходом L-ой стадии является 128-битный дайджест сообщения. Рассмотрим более детально логику каждого из четырех циклов выполнения одного 512

Алгоритм MD4
Алгоритм MD4 является более ранней разработкой того же автора Рона Ривеста. Первоначально данный алгоритм был опубликован в октябре 1990 г., незначительно измененная версия была опубликована

Усиление алгоритма в MD5
Алгоритм MD5 имеет следующее свойство: каждый бит хэш-кода является функцией от каждого бита входа. Комплексное повторение элементарных функций fF, fG, fH

Шаг 4: Обработка сообщения в 512-битных (16-словных) блоках
Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как HSHA. Все 80 циклических обработок имеют одинаковую структуру.

Шаг 5: Выход
После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения. Рассмотрим более детально логику в каждом из 80 циклов обработки одного 512-битног

Сравнение SHA-1 и MD5
Оба алгоритма, SHA-1 и MD5, произошли от MD4, поэтому имеют много общего. Можно суммировать ключевые различия между алгоритмами. &nbs

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

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

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

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

Постановка задачи

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

Требования

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

• Необратимость или стойкость к восстановлению прообраза : для заданного значения хэш-функции m должно быть вычислительно невозможно найти блок данных X , для которого H(X)=m .
• Стойкость к коллизиям первого рода или восстановлению вторых прообразов : для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N , для которого H(N)=H(M) .
• Стойкость к коллизиям второго рода : должно быть вычислительно невозможно подобрать пару сообщений (M, M") , имеющих одинаковый хэш.

Данные требования не являются независимыми:

• Обратимая функция нестойка к коллизиям первого и второго рода.
• Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

Принципы построения

Итеративная последовательная схема

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

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

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

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

Сжимающая функция на основе симметричного блочного алгоритма

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

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

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

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

Применения

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

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

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

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

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

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

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows. В них хранятся лишь хэш-значения парольных фраз из учётных записей пользователей.

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

Пусть некий клиент, с именем name, производит аутентификацию по парольной фразе, pass, на некоем сервере. На сервере хранится значение хэш-функции H(pass,R2), где R2 - псевдослучайное, заранее выбранное, число. Клиент посылает запрос (name, R1), где R1 - псевдослучайное, каждый раз новое, число. В ответ сервер посылает значение R2. Клиент вычисляет значение хэш-функции H(R1,H(pass,R2)) и посылает его на сервер. Сервер также вычисляет значение H(R1,H(pass,R2)) и сверяет его с полученным. Если значения совпадают - аутентификация верна.

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

Случайный оракул

Напомним свойство перемешивания, которое присуще функции хэширования: при любом аргументе хэширование неотличимо с вычислительной точки зрения от строки битов, равномерно распределенных в области значений функции. Если заменить последнее выражение фразой "принадлежит генеральной совокупности равномерно распределенных величин", мы получим весьма мощную гипотетическую функцию, называемую случайный оракул (randome oracle). Он обладает тремя свойствами: детерминированность, эффективность, равномерность распределения результирующих значений. Однако,все известные вычислительные модели в той или иной степени не соответствуют модели случайного оракула. Равномерность и детерминированность величин, вычисляемых случайным оракулом, означает, что энтропия его результатов выше, чем энтропия чисел, поступающих на вход. Поскольку свойства перемешивания, которым обладает хэш-функция является лишь предположением вычислительного характера, реальная хэш-функция должна обеспечивать лишь вычислительную неразличимость, то есть результаты должны иметь некое распределение вероятностей в области значений, которое невозможно определить за полиномиальное время. Итак, реальные функции хэширования лишь имитируют поведение случайного оракула, хоть и с высокой точностью.

Атака на основе парадокса дней рождений

Предположим, что функция хэширования h действительно является случайным оракулом. В атаке по методу квадратного корня (атака на основе парадокса дней раждения) предполагается, что для обнаружения коллизий с ненулевой вероятностью достаточно выполнить 2 в степени |h|/2 случайных вычислений значения функции хэширования. Для организации атаки на основе парадокса дней рождений атакующий должен сгенерировать пары "сообщение-хэшированное значение", пока не обнаружаться два сообщения m и m`, удовлетворяющие условиям m не равно m`, h(m)=h(m`). Такая пара сообщений называется коллизией(collision) функции хэширования h. Например, для функции хэшироания SHA-1 выполняется условие |h|=160, а значит его стойкость на основе парадокса дней рождения оценивается величиной 2 80 .

Сравнительная характеристика наиболее известных функций

Существует длинный перечень криптографических хеш-функций, хотя многие из них были признаны уязвимыми и не должны быть использованы. Даже если хэш-функция никогда не была взломана, успешная атака против ослабленного варианта может подорвать доверие экспертов и привести к отказу от хэш-функции. Например, в августе 2004 года были найдены слаюости в ряде хэш-функций, которые были популярны в то время, в том числе SHA-0, RIPEMD и MD5. Это поставило под сомнение долгосрочную безопасность более поздних алгоритмов, которые являются производными от этих хеш-функций - в частности, SHA-1 (усиленный вариант SHA-0), RIPEMD- 128 , и RIPEMD-160 (оба усиленные версии RIPEMD). Ни SHA-0 , ни RIPEMD широко не используются, так как они были заменены на более усиленные версии. По состоянию на 2009, двумя наиболее часто используемыми криптографическими хэш-функциями являются MD5 и SHA-1. Тем не менее, MD5 была взломана, атака против него была также использована для взлома SSL в 2008. Функции SHA-0 и SHA-1 были разработаны в АНБ. В феврале 2005 года сообщалось, что проведена успешная атака на SHA-1, найдены коллизии за, примерно, 2 69 операций хэширования, а не в 2 80 , которые ожидаются для 160-битной хэш-функции. В августе 2005 года сообщалось, об еще одном успешном нападении на SHA-1: нахождение коллизии за 2 63 операций. Новые приложения могут избежать этих проблем с безопасностью функции SHA-1 с помощью более продвинутых членов семьи SHA , например, SHA-2. Тем не менее, для обеспечения долгосрочной надежности приложений, использующих хэш-функций, был устроен конкурс на лучший проект - замену SHA-2. 2 октября 2012 года, Keccak был выбран в победителем в конкурсе, устроенном NIST. Версия этого алгоритма как ожидается, станет стандартным FIPS в 2014 году под названием SHA-3. Некоторые из следующих алгоритмов часто используется в приложениях криптографии.Обратите внимание, что этот список не включает кандидатов в текущем конкурсе NIST.

Алгоритм	Размер выхода	Размер внутреннего состояния	Размер блока	Длина	Размер слова	Количество раундов	Атаки (сложность:раунды)
							Атака «дней рождения»	Нахождение второго прообраза	Нахождение прообраза
ГОСТ 34.11-45	256	256	256	256	32	256	Yes (2 105)	Yes (2 192 ])	Yes (2 192)
HAVAL	256/224/192/160/128	256	1,024	64	32	160/128/96	Да	Нет	Нет
MD2	128	384	128	-	32	864	Да (2 63.3 ])	Да (2 73 ])	Да (2sup>73])
MD4	128	128	512	64	32	48	Да (3)	Да (2 64)	Да (2 78.4)
MD5	128	128	512	64	32	64	Да (2 20.96)	Да (2 123.4)	Да (2 123.4)
PANAMA	256	8,736	256	-	32	-	Да	Нет	Нет
RIPEMD	128	128	512	64	32	48	Да (2 18)	Нет	Нет
RIPEMD-128/256	128/256	128/256	512	64	32	64	Нет	Нет	Нет
RIPEMD-160	160	160	512	64	32	80	Да (2 51)	Нет	Нет
RIPEMD-320	320	320	512	64	32	80	Нет	Нет	Нет

9.1. Хэш-функции на основе блочных шифров

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

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

См. подробнее в хрестоматии

Хэш-функция — это преобразование, получающее из данных произвольной длины некое значение (свертку) фиксированной длины. Простейшими примерами являются контрольные суммы (например, 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. аргумент x
2. значение H (x)
3. значение H (x) легко вычислить;
4. для любого фиксированного x вычислительно невозможно найти другой x"!=x , такой что H(x")=H(x) . Пара x"!=x , когда H(x")=H(x) называется коллизией хэш-функции.

Сильной хэш-функцией называется односторонняя функция H(x), удовлетворяющая условиям 1–3 для слабой хэш-функции и свойству 4": 4") вычислительно невозможно найти любую пару x"!=x, такой что H(x")=H(x).

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

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

1. аргумент х функции H(k, x) может быть строкой бит произвольной длины;
2. значение H(k, x) должно быть строкой бит фиксированной длины;
3. при любых k и x легко вычислить H(k, x) ;
4. для любого х должно быть трудно вычислить H(k, x), не зная k ;
5. должно быть трудно определить k даже при большом числе неизвестных пар {x, H(k, x)} при выбранном наборе х или вычислить по этой информации H(k, x") для x"!=x .

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

Некоторые алгоритмы хэш-функций:

• MD 2. Message Digest. Алгоритм криптографической сверки. Порождает 128- bit блок от сообщения произвольной длины.
• MD 4. Другой алгоритм свертки. Порождает 128-bit блок.
• MD 5. Существенно переделанный MD 4. Автор тот же – Риверст.
• SHA. Результирующий хэш равен 160-bit.
• ГОСТ Р34.11–94. Российский алгоритм. Длина свертки – 256 бит (очень удобно для формирования по паролю ключа для ГОСТ 28147–89).

Основная идея применения криптографических функций состоит в том, чтобы хэш-величины служили в качестве компактного репрезентативного образа входной двоичной строки, и их можно использовать как если бы они однозначно отождествлялись с этой строкой, хотя для области определения D и области значений R с (имеются в виду мощности множеств), функция типа «множество — один» подразумевает, что существование столкновений (пары входов с одинаковым выходом) неизбежно. Область применения хэш-функции четко не оговорена: она используется «для реализации процедур электронной цифровой подписи (ЭЦП), при передаче, обработке и хранении информации в автоматизированных системах».

— множество двоичных строк длиной n бит;

— двоичная строка, состоящая из n нулей;

— сложение двоичных слов A и B по .

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

• последовательного (итерационного);
• параллельного.

9.2. Важнейшие практически используемые стойкие хэш-функции

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

Рис. 1. Метод последовательного хэширования.

Если необходимо хэшировать сообщение , то хэширование выполняется следующим образом:

Здесь – функция сжатия, а – переменная сцепления.

Если последний блок содержит меньше чем n бит, то он «набивается» до достижения длины n . В отличие от стандартных предпосылок, предполагающих, что сообщение предварительно уже было разбито на блоки и произведена «набивка» последнего блока (это соответствует форматированию входного сообщения априори) до начала хэширования, в ГОСТ Р34.11–94 процедура хэширования ожидает конца сообщения (форматирование входного сообщения апостериори). «Набивка» производится следующим образом: последний блок сдвигается вправо, а затем освободившиеся разряды заполняются нулями до достижения длины в 256 бит. Алгоритм хэширования по ГОСТ Р34.11–94 можно классифицировать как устойчивый к столкновениям (n = 256, следовательно атака по парадоксу дней рождения потребует приблизительно операций хэширования) код, а также выявляющий модификации (Collision Resistant Hash Function , CRHF ). Хэш-функцию по ГОСТ Р34.11–94 можно легко преобразовать в код аутентификации сообщения любым известным методом (например, HMAC, методом секретного префикса, суффикса, оболочки и т. д.).

См. подробнее в хрестоматии

Однако разработчики предусмотрели дополнительные меры защиты, для чего параллельно рассчитываются:

Рассчитанные значения в финальной функции сжатия используются для вычисления итогового хэша (см. рис. 2).

Рис. 2. Общая схема функции хэширования по ГОСТ Р34.11– 94.

Замечание 1 («набивка»). Указывать в передаваемом сообщении, сколько было добавлено нулей к последнему блоку, не требуется, т. к. длина сообщения участвует в хэшировании.

Рис. 3. «Набивка» сообщения.

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

Безопасный хэш-алгоритм SHA-1 (Secure Hash Algorithm – 1) был разработан национальным институтом стандартов и технологии (NIST) и опубликован в качестве федерального информационного стандарта (FIPS PUB 180) в 1993 г.

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

Шаг 1 : добавление недостающих битов. Сообщение добавляется таким образом, чтобы его длина была кратна 448 по модулю 512 (длина448 mod 512). Добавление осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512. Добавление состоит из единицы, за которой следует необходимое количество нулей.

Шаг 2 : добавление длины. К сообщению добавляется блок из 64 битов. Этот блок трактуется как беззнаковое 64-битное целое число и содержит длину исходного сообщения до добавления. Результатом первых двух шагов является сообщение, длина которого кратна 512 битам. Расширенное сообщение может быть представлено как последовательность 512-битных блоков Y 0, Y 1,..., YL -1. Таким образом, общая длина расширенного сообщения есть L * 512 бит (результат кратен шестнадцати 32-битным словам).

Шаг 3 : инициализация SHA-1 буфера. Используется 160-битный буфер для хранения промежуточных и окончательных результатов расчета хэш-функции. Буфер может быть представлен как пять 32-битных регистров для хранения чисел A, B, C, D и E. Эти регистры инициализируются следующими шестнадцатеричными числами: A=67452301; B=EFCDAB 89; C=98 BADCFE; D=10325476; E=C 3 D 2 E 1 F 0.

Шаг 4 : обработка сообщения в 512-битных (16-словных) блоках. Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как HSHA. Все 80 циклов обработки каждого блока имеют одинаковую структуру.

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

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

	5A827999 (целая часть числа );
	6 ED 9 EBA 1 (целая часть числа );
	8 F 1 BBCDC (целая часть числа );
	CA 62 C 1 D 6 (целая часть числа ).

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

Шаг 5 : выход. После обработки всех 512-битных блоков сообщения выходом L-й стадии алгоритма является 160-битный дайджест сообщения. Рассмотрим более детально логику работы в каждом из 80-и циклов обработки для одного 512-битного блока. Новые (рассчитанные) значения для переменных A, B, C, D, E на выходе каждого цикла обработки можно представить так:

Здесь: A, B, C, D, E – пять 32-битных слов из буфера; t – номер цикла 0 ≤t ≤79; – элементарная логическая функция; – циклический левый сдвиг 32-битного аргумента на s битов; – 32-битное слово, полученное из текущего входного 512-битного блока; – дополнительная константа; знак «+» – сложение по модулю .

Рис. 5. Логика выполнения отдельного цикла.

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

Номер цикла	ft (B , C , D )

На практике используются только три различные функции. Для 0 ≤t ≤19 функция является условной: if B then C else D. Для 20 ≤t ≤39 и 60 ≤t ≤79 функция создает бит четности. Для 40 ≤t ≤59 функция является истинной, если два или три аргумента истинны. 32-битные слова получаются из очередного 512-битного блока сообщения следующим образом.

Рис. 6. Получение входных значений переменной для каждого цикла
из очередного (текущего) 512-битного обрабатываемого блока .

Первые 16 значений берутся непосредственно из 16 слов текущего блока . Оставшиеся значения определяются следующим образом: . В первых 16 циклах обработки вход состоит из 32-битного слова данного блока . Для оставшихся 64 циклов вход состоит из XOR нескольких слов из блока сообщения .

Алгоритм SHA-1 можно суммировать следующим образом:

где IV – начальное значение буфера переменных A, B, C, D, E;

– результат обработки q-го блока сообщения;

L – число блоков в сообщении, включая поля добавления и длины;

Σ 32 – сумма по модулю , выполняемая отдельно для каждого слова буфера;

SHA – значение дайджеста сообщения.

Хеширование паролей – метод, позволяющий пользователям запоминать не 128 байт, т. е. 256 шестнадцатеричных цифр ключа, а некоторое осмысленное выражение, слово или последовательность символов, называющееся паролем. Действительно, при разработке любого криптоалгоритма следует учитывать, что в половине случаев конечным пользователем системы является человек, а не автоматическая система. Это ставит вопрос о том, удобно и вообще реально ли человеку запомнить 128-битный ключ (32 шестнадцатиричные цифры). Предел запоминаемости лежит на границе 8–12 подобных символов, а следовательно, если мы будем заставлять пользователя оперировать именно ключом, то мы практически вынудим его к записи ключа на каком-либо листке бумаги или электронном носителе, например в текстовом файле. Это, естественно, резко снижает защищенность системы.

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

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

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

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

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

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