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

Описание

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

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

Коллизия хеш-функции

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

В хеш-таблицах

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

Метод цепочек (метод прямого связывания)

Метод открытой адресации

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

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

Криптографическая соль

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

Применение хеш-функций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассматриваемые алгоритмы также предполагают чувствительность к данным на входе на уровне 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, российские стандарты криптографического шифрования.

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

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

Построения систем контроля целостности данных при их передаче или хранении,

Аутентификации источника данных.

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

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

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

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

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

Хеш-функцией называется всякая функция h: Х ® Y,

легко вычислимая и такая, что для любого сообщения М значение h(M) = Н (свертка) имеет фиксированную битовую длину.

Цифровая подпись

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

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

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

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

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

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

Похожая информация.

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

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

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

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

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

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

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

Требования

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

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

2. Стойкость к поиску второго прообраза - вычислительно невозможно, зная сообщение m и его свертку H(m), найти такое другое сообщение m′ ≠ m , чтобы H(m) = H(m′).

3. Стойкость к коллизиям

Доказуемо безопасные хеш-функции

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

Криптографическая хеш-функция является доказуемо защищённой от коллизий, если задача нахождения коллизий может быть средуцирована за полиномиальное время от задачи P {\displaystyle P} , которая считается неразрешимой за полиномиальное время . Иначе говоря, если алгоритм A {\displaystyle A} позволял бы за полиномиальное время решить задачу нахождения коллизий при существовании редуцирующего алгоритма R {\displaystyle R} , работающего также за полиномиальное время, то последний позволил бы алгоритму A {\displaystyle A} решить задачу P {\displaystyle P} за полиномиальное время, что противоречит её сложности, а значит задача нахождения коллизий не легче задачи P {\displaystyle P} .

Аналогично определяется доказуемая защищённость от поиска первого и второго прообраза.

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

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

Недостатки доказательного подхода

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

Примеры доказуемо безопасных хеш-функции

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

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

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

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

Злоумышленник будет искать прообраз для идеальной хеш-функции следующим образом: у него есть число h, и ему надо найти такое m, что H(m) = h. Если это идеальная хеш-функция, то злоумышленнику остается лишь перебирать все возможные M и проверять, чему равна хеш-функция от этого сообщения. Результат вычисления, если m перебирается полностью, есть фактически случайное число. Если число h лежит в диапазоне от 0 до 2 n {\displaystyle 2^{n}} , то тогда в среднем на поиски нужного h злоумышленник будет тратить 2 n − 1 {\displaystyle 2^{n-1}} итераций. Таким образом, вычисление прообраза займёт в два раза меньше итераций, чем в идеальном случае.

Вычисление второго прообраза останется 2 n {\displaystyle 2^{n}} . В поиске коллизий оценка даст 2 n {\displaystyle 2^{n}} , причём это не совсем точный результат. Данная оценка идет из оценки так называемого «Парадокса дней рождения».

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

«Атака дней рождения»

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

Для 60 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле , только тогда, когда в группе не менее 367 человек (ровно на 1 больше, чем число дней в високосном году; с учётом високосных лет).

Семейство хеш-функций MD и SHA

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

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

Хэш-функции, долгое время использующиеся в компьютерных науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, дли- ны (называемую значением хэш-функции). В качестве простой хэшфункции можно рассматривать функцию, которая получает прообраз и возвращает байт, представляющий собой 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.