В самых различных отраслях информационных технологий находят свое применение хэш-функции. Они предназначены для того, чтобы, с одной стороны, значительно упростить обмен данными между пользователями и обработку файлов, используемых в тех или иных целях, с другой — оптимизировать алгоритмы обеспечения контроля доступа к соответствующим ресурсам. Хэш-функция — один из ключевых инструментов обеспечения парольной защиты данных, а также организации обмена документов, подписанных с помощью ЭЦП. Существует большое количество стандартов, посредством которых может осуществляться кэширование файлов. Многие из них разработаны российскими специалистами. В каких разновидностях могут быть представлены хэш-функции? Каковы основные механизмы их практического применения?
Что это такое?
Для начала исследуем понятие хэш-функции. Под данным термином принято понимать алгоритм преобразования некоторого объема информации в более короткую последовательность символов посредством математических методов. Практическую значимость хэш-функции можно проследить в самых разных областях. Так, их можно задействовать при проверке файлов и программ на предмет целостности. Также криптографические хеш-функции задействуются в алгоритмах шифрования.
Характеристики
Рассмотрим ключевые характеристики исследуемых алгоритмов. В числе таковых:
- наличие внутренних алгоритмов преобразования данных исходной длины в более короткую последовательность символов;
- открытость для криптографической проверки;
- наличие алгоритмов, позволяющих надежно шифровать изначальные данные;
- адаптированность к расшифровке при задействовании небольших вычислительных мощностей.
В числе иных важнейших свойств хэш-функции:
- способность обрабатывать изначальные массивы данных произвольной длины;
- формировать хешированные блоки фиксированной длины;
- распределять значения функции на выходе равномерно.
Рассматриваемые алгоритмы также предполагают чувствительность к данным на входе на уровне 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, российские стандарты криптографического шифрования.
Хеширование (от англ. hashing) - преобразование входных данных произвольной длины в выходную битовую строку фиксированной длины таким образом, чтобы изменение входных данных приводило к непредсказуемому изменению выходных данных. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем или хеш-кодом.
Задачи хеширования
Проверка парольной фразы
Сегодня опасно хранить пароли на целевых объектах, ведь от туда они могут быть похищены злоумышленниками и использованы в своих целях. Поэтому там хранятся только хеши паролей, которые нельзя обратить и узнать пароль. При проверки же пароля, вводимый пароль подвергается хешированию и сравниваются хеш-значения.
Самые распространенные алгоритмы: MD5 (MD4, MD2), SHA1.
Ускорение поиска данных
Например, в базе данных, при записи текстовых полей может расчитываться их хеш-код и записываться в отдельное поле. Тогда при поиске данных нужно будет вычислить хеш-код данных и искать уже не по всей базе, а только по одному ее разделу.
Вычисление контрольной суммы .
Для проверки пакета на наличие ошибок часто используется контрольная сумма, которая передается вместе с сообщением. На приемном конце, при получении сообщения еще раз вычисляется контрольная сумма и если значение совпадает с переданным значит сообщение передано без ошибок.
Вычисление электронной цифровой подписи .
Электронная цифровая подпись используется для защиты электронного документа от подделки. Получается в результате преобразования информации с использованием закрытого ключа, позволяет идентифицировать владельца ключа подписи и установить отсутствие искажения информации в электронном документе
Требования, предъявляемые к алгоритму хэширования
Хэш-функция может быть применена к аргументу любого размера.
Выходное значение имеет фиксированный размер.
Скорость вычисления хэш-функции должна быть такой, что скорость формирования цифровой подписи при использовании хэш-функции должна существенно превышать скорость формирования цифровой подписи при использовании самого сообщения.
Хэш-функция является односторонней функцией. Таким образом, для любого m с вычислительной точки зрения невозможно найти такой открытый текст X, h (X) = m
Вероятность того, что значения хэш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала.
Алгоритм MD 5
MD5 (Message Digest 5) – алгоритм хеширования, разработанный Р. Ривестом из Массачусетского технологического института (MIT) в 1991 году
Подробное описание алгоритма может быть найдено в RFC 1321.
На выходе алгоритм выдает 128-битный дайджест(отпечаток) сообщения. Длина исходного сообщения может быть любой.
Алгоритм MD5 уязвим к некоторым атакам, например возможно создание двух сообщений с одинаковой хеш-суммой, поэтому его использование не рекомендуется в новых проектах.
Алгоритм SHA -1
Алгоритм безопасного хэширования SHA (Secure Hash Algorithm) принят в качестве стандарта США в 1992 году.
Описан в RFC 3174.
Предназначен для использования совместно с алгоритмом цифровой подписи. При вводе открытого текста алгоритм вырабатывает 160-битовое выходное сообщение (digest (“дайджест”), краткое изложение), используемое при выработке цифровой подписи.
Алгоритм хэширования SНА назван безопасным, потому что он спроектирован таким образом, чтобы было вычислительно невозможно восстановить сообщение, соответствующее данному дайджесту, а также найти два различных сообщения, которые дадут одинаковый дайджест.
Отличия алгоритмов SHA и MD5 состоят в следующем:
1. SHA выдает 160-битовое хэш-значение и более устойчив к атакам полного перебора чем MD5, формирующий 128-битовое хэш-значение.
2. Сжимающая функция SHA включает 80 раундов, а не 64 как в MD5.
3. Усложнен процесс перемешивания.
Алгоритмы семейства SHA -2
Алгоритмы подсемейства SHA -2 , так же как и алгоритм SHA -1 , были разработаны Агентством национальной безопасности США и опубликованы Национальным институтом стандартов и технологий (NIST) в федеральном стандарте обработки информации FIPS PUB 180–2 в августе 2002 года.
Алгоритмы семейства SHA-2 используются в SSL , SSH , S / MIME , DNSSEC , X .509 , PGP , IPSec , при передачи файлов по сети (BitTorrent ).
Алгоритмы хэширования
MD5 md5 = new MD5CryptoServiceProvider();
string stringToHash = "Съешь еще этих мягких французских булок да выпей чаю";
byte hash = md5.ComputeHash(Encoding.Unicode.GetBytes(stringToHash));
Console.WriteLine(ByteHelper.ByteArrayToHexString(hash));
string anotherStringToHash = "The quick brown fox jumps over the lazy dog";
HashAlgorithm sha512 = HashAlgorithm.Create("SHA512");
Console.WriteLine(
ByteHelper.ByteArrayToHexString(
sha512.ComputeHash(
Encoding.Unicode.GetBytes(
Хеширование или хэширование (англ. hashing ) - преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом . Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией » или «функцией свёртки ». Исходные данные называются входным массивом, «ключом » или «сообщением ». Результат преобразования (выходные данные) называется «хешем », «хеш-кодом », «хеш-суммой », «сводкой сообщения ».
Хеширование применяется в следующих случаях:
- при построении ассоциативных массивов ;
- при поиске дубликатов в сериях наборов данных;
- при построении уникальных идентификаторов для наборов данных;
- при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в них ошибок (возникших случайно или внесённых намеренно), возникающих при хранении и/или передаче данных;
- при сохранении паролей в системах защиты в виде хеш-кода (для восстановления пароля по хеш-коду требуется функция, являющаяся обратной по отношению к использованной хеш-функции);
- при выработке электронной подписи (на практике часто подписывается не само сообщение, а его «хеш-образ»);
- и др.
Виды «хеш-функций»
«Хорошая» хеш-функция должна удовлетворять двум свойствам :
- быстрое вычисление;
- минимальное количество «коллизий ».
Введём обозначения:
∀ k ∈ (0 ; K) : h (k) < M {\displaystyle \forall k\in (0;\,K):h(k)В качестве примера «плохой» хеш-функции можно привести функцию с M = 1000 {\displaystyle M=1000} , которая десятизначному натуральному числу K {\displaystyle K} сопоставляет три цифры, выбранные из середины двадцатизначного квадрата числа K {\displaystyle K} . Казалось бы, значения «хеш-кодов» должны равномерно распределяться между «000 » и «999 », но для «реальных » данных это справедливо лишь в том случае, если «ключи » не имеют «большого» количества нулей слева или справа .
Рассмотрим несколько простых и надёжных реализаций «хеш-функций».
«Хеш-функции», основанные на делении
1. «Хеш-код» как остаток от деления на число всех возможных «хешей»
Хеш-функция может вычислять «хеш» как остаток от деления входных данных на M {\displaystyle M} :
h (k) = k mod M {\displaystyle h(k)=k\mod M}где M {\displaystyle M} - количество всех возможных «хешей» (выходных данных).
При этом очевидно, что при чётном M {\displaystyle M} значение функции будет чётным при чётном k {\displaystyle k} и нечётным - при нечётном k {\displaystyle k} . Также не следует использовать в качестве M {\displaystyle M} степень основания системы счисления компьютера , так как «хеш-код» будет зависеть только от нескольких цифр числа k {\displaystyle k} , расположенных справа, что приведёт к большому количеству коллизий . На практике обычно выбирают простое M {\displaystyle M} ; в большинстве случаев этот выбор вполне удовлетворителен.
2. «Хеш-код» как набор коэффициентов получаемого полинома
Хеш-функция может выполнять деление входных данных на полином по модулю два. В данном методе M {\displaystyle M} должна являться степенью двойки, а бинарные ключи ( K = k n − 1 k n − 2 . . . k 0 {\displaystyle K=k_{n-1}k_{n-2}...k_{0}} ) представляются в виде полиномов , в качестве «хеш-кода» «берутся» значения коэффициентов полинома , полученного как остаток от деления входных данных K {\displaystyle K} на заранее выбранный полином P {\displaystyle P} степени m {\displaystyle m} :
K (x) mod P (x) = h m − 1 x m − 1 + ⋯ + h 1 x + h 0 {\displaystyle K(x)\mod P(x)=h_{m-1}x^{m-1}+\dots +h_{1}x+h_{0}} h (x) = h m − 1 . . . h 1 h 0 {\displaystyle h(x)=h_{m-1}...h_{1}h_{0}}При правильном выборе P (x) {\displaystyle P(x)} гарантируется отсутствие коллизий между почти одинаковыми ключами .
«Хеш-функции», основанные на умножении
Обозначим символом w {\displaystyle w} количество чисел, представимых машинным словом . Например, для 32-разрядных компьютеров, совместимых с IBM PC , w = 2 32 {\displaystyle w=2^{32}} .
Выберем некую константу A {\displaystyle A} так, чтобы A {\displaystyle A} была взаимно простой с w {\displaystyle w} . Тогда хеш-функция, использующая умножение, может иметь следующий вид:
h (K) = [ M ⌊ A w ∗ K ⌋ ] {\displaystyle h(K)=\left}В этом случае на компьютере с двоичной системой счисления M {\displaystyle M} является степенью двойки, и h (K) {\displaystyle h(K)} будет состоять из старших битов правой половины произведения A ∗ K {\displaystyle A*K} .
Среди преимуществ хеш-функций, основанных на делении и умножении, стоит отметить выгодное использование неслучайности реальных ключей. Например, если ключи представляют собой арифметическую прогрессию (например, последовательность имён «Имя 1», «Имя 2», «Имя 3»), хеш-функция, использующая умножение, отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшит количество коллизий по сравнению со случайной ситуацией .
Одной из хеш-функций, использующих умножение, является хеш-функция, использующая хеширование Фибоначчи . Хеширование Фибоначчи основано на свойствах золотого сечения . В качестве константы A {\displaystyle A} здесь выбирается целое число, ближайшее к φ − 1 ∗ w {\displaystyle \varphi ^{-1}*w} и взаимно простое с w {\displaystyle w} , где φ {\displaystyle \varphi } - это золотое сечение .
Хеширование строк переменной длины
Вышеизложенные методы применимы и в том случае, если необходимо рассматривать ключи, состоящие из нескольких слов, или ключи переменной длины. Например, можно скомбинировать слова в одно при помощи сложения по модулю w {\displaystyle w} или операции «исключающее или ». Одним из алгоритмов, работающих по такому принципу, является хеш-функция Пирсона.
Универсальное хеширование
Методы борьбы с коллизиями
Коллизией (иногда конфликтом или столкновением) называется случай, при котором одна хеш-функция для разных входных блоков возвращает одинаковые хеш-коды.
Методы борьбы с коллизиями в хеш-таблицах
Большинство первых работ, описывающих хеширование, посвящено методам борьбы с коллизиями в хеш-таблицах. Тогда хеш-функции применялись при поиске текста в файлах большого размера. Существует два основных метода борьбы с коллизиями в хеш-таблицах:
- метод цепочек (метод прямого связывания);
- метод открытой адресации.
При использовании метода цепочек в хеш-таблице хранятся пары «связный список ключей» - «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе, создаётся новая пара «список ключей» - «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется N {\displaystyle N} ключей и M {\displaystyle M} списков, средний размер хеш-таблицы составит N M {\displaystyle {\frac {N}{M}}} . В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в M {\displaystyle M} раз.
При использовании метода открытой адресации в хеш-таблице хранятся пары «ключ» - «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; пара «ключ» - «хеш-код» сохраняется в таблице. В этом случае при поиске по таблице по сравнению со случаем, в котором используются связные списки, ссылки не используются, выполняется последовательный перебор пар «ключ» - «хеш-код», перебор прекращается после обнаружения нужного ключа. Последовательность, в которой просматриваются ячейки таблицы, называется последовательностью проб .
Криптографическая соль
Применение хеш-функций
Хеш-функции широко используются в криптографии, а также во многих структурах данных - хеш-таблицаx , фильтрах Блума и декартовых деревьях .
Криптографические хеш-функции
Среди множества существующих хеш-функций принято выделять
Одним из ключевых слов, которые новички слышат, когда узнают о блокчейне, являются понятия хэша и алгоритма хэширования , которые кажутся распространёнными для безопасности. Запуск децентрализованной сети и консенсуса, такой как биткойн или сеть эфириум с десятками тысяч узлов, соединенных через p2p, требует, как “надежности”, так и эффективности проверки. То есть, эти системы нуждаются в способах кодирования информации в компактном формате, позволяющем обеспечить безопасную и быструю проверку ее участниками
В закладки
Основным примитивом, обрабатываемым как Биткойном, так и Эфириумом, является понятие блока , который представляет собой структуру данных, включающую транзакции, временную метку и другие важные метаданные. Критическая часть их безопасности включает в себя возможность сжимать большие куски информации о глобальном состоянии сети в короткий стандарт сообщений, который может быть эффективно проверен, если это необходимо, известный как хэш .
Даже изменение одного символа во входных данных приведет к совершенно другому хэшу.
Криптографические хэши используются везде, от хранения паролей до систем проверки файлов. Основная идея состоит в том, чтобы использовать детерминированный алгоритм (алгоритмический процесс, который выдает уникальный и предопределенный результат для задачи входных данных), который принимает один вход и создает строку фиксированной длины каждый раз. То есть, использование одного и того же ввода всегда приводит к одному и тому же результату. Детерминизм важен не только для хэшей, но и для одного бита, который изменяется во входных данных, создавая совершенно другой хэш. Проблема с алгоритмами хэширования - неизбежность коллизий. То есть, тот факт, что хэши являются строкой фиксированной длины, означает, что для каждого ввода, который мы можем себе представить, есть другие возможные входы, которые приведут к тому же хэшу . Коллизия - это плохо . Это означает, что, если злоумышленник может создавать коллизии, он может передавать вредоносные файлы или данные, как имеющие правильный и неправильный хэш и скрываться под правильным хешем. Цель хорошей хэш-функции состоит в том, чтобы сделать чрезвычайно сложным для злоумышленников найти способы генерации входных данных, которые хешируются с одинаковым значением. Вычисление хэша не должно быть слишком простым, так как это облегчает злоумышленникам искусственное вычисление коллизий. Алгоритмы хэширования должны быть устойчивы к «атакам нахождения прообраза». То есть, получая хеш, было бы чрезвычайно сложно вычислить обратные детерминированные шаги, предпринятые для воспроизведения значения, которое создало хэш (т.е нахождение прообраза).
Учитывая S = hash (x), найти X должно быть почти невозможно.
Напомним, что «хорошие» алгоритмы хэширования имеют следующие свойства:
- Изменение одного бита во входных данных должно создать эффект изменения всего хеша;
- Вычисления хеша не должно быть слишком простым, высокая сложность нахождения прообраза;
- Должен иметь очень низкую вероятность коллизии;
Взлом хешей
Одним из первых стандартов алгоритма хэширования был MD5 hash, который широко использовался для проверки целостности файлов (контрольных сумм) и хранения хэшированных паролей в базах данных веб-приложений. Его функциональность довольно проста, так как она выводит фиксированную 128-битную строку для каждого входа и использует тривиальные однонаправленные операции в нескольких раундах для вычисления детерминированного результата. Его короткая выходная длина и простота операций сделали MD5 очень легким для взлома и восприимчивым к атаке «дня рождения».
Что такое «Атака дня рождения?»
Вы когда-нибудь слышали о том, что если вы поместите 23 человека в комнату, есть 50% шанс, что у двух из них будет один и тот же день рождения? Доведение числа до 70 человек в комнате дает вам 99,9% шанс. Если голуби рассажены в коробки, причем число голубей больше числа коробок, то хотя бы в одной из клеток находится более одного голубя. То есть фиксированные ограничения на выход означают, что существует фиксированная степень перестановок, на которых можно найти коллизию.
По крайне мере, один отсек будет иметь внутри 2-ух голубей.
На самом деле MD5 настолько слаб к сопротивлению к коллизиям, что простой бытовой Процессор Pentium 2,4 ГГц может вычислить искусственные хэш-коллизии в течение нескольких секунд. Кроме того, его широкое использование в более ранние дни текущей сети создало тонны утечек MD5 предварительных прообразов в интернете, которые можно найти с помощью простого поиска Google их хэша.
Различия и развитие алгоритмов хеширования Начало: SHA1 и SHA2
NSA (Агентство национальной безопасности) уже давно является пионером стандартов алгоритмов хэширования, с их первоначальным предложением алгоритма Secure Hashing Algorithm или SHA1, создающий 160-битные выходы фиксированной длины. К сожалению, SHA1 просто улучшил MD5, увеличив длину вывода, количество однонаправленных операций и сложность этих односторонних операций, но не дает каких-либо фундаментальных улучшений против более мощных машин, пытающихся использовать различные атаки. Так как мы можем сделать что-то лучше?
Использование SHA3
В 2006 году Национальный институт стандартов и технологий (NIST) запустил конкурс, чтобы найти альтернативу SHA2, которая будет принципиально отличаться в своей архитектуре, чтобы стать стандартом. Таким образом, SHA3 появился как часть большой схемы алгоритмов хэширования, известной как KECCAK (произносится Кетч-Ак). Несмотря на название, SHA3 сильно отличается своим внутренним механизмом, известным как «конструкция губки», которая использует случайные перестановки для «Впитывания» и «Выжимания» данных, работая в качестве источника случайности для будущих входов, которые входят в алгоритм хэширования.
Хеширование и proof-of-work
Когда дело дошло до интеграции алгоритма хеширования в блокчейн протоколы, биткоин использовал SHA256, в то время как Ethereum использовал модифицированный SHA3 (KECCAK256) для своего PoW. Однако важным качеством выбора хэш-функции для блокчейна с использованием доказательства работы является эффективность вычислений указанного хэша. Алгоритм хеширования биткойна SHA256 может быть вычислен достаточно просто с помощью специализированного оборудования, известного как специализированные интегральные схемы (или ASIC). Много было написано об использовании ASIC в майнинг пуле и о том, как они делают протокол направленным на централизацию вычислений. То есть доказательство работы стимулирует группы вычислительно эффективных машин объединяться в пулы и увеличивать то, что мы обозначаем “хэш-мощностью”, или мерой количества хэшей, которые машина может вычислить за интервал времени. Ethereum, выбрал модифицированный SHA3 известный как KECCAK 256. Кроме того, алгоритм PoW в Ethereum - Dagger-Hashimoto, должен был быть трудно вычисляемым для аппаратного обеспечения.
Почему биткоин использует двойное шифрование SHA256?
Биткойн имеет интересный способ хэширования данных с помощью SHA256, поскольку он выполняет две итерации алгоритма в своем протоколе. Обратите внимание: это не контрмера для атак на день рождения, так как ясно, что если hash (x) = hash (y), то hash (hash (x)) = hash (hash (y)). Вместо этого двойной SHA256 используется для смягчения «Атаки удлинения сообщения - тип атаки на хэш-функцию, заключающейся в добавлении новой информации в конец исходного сообщения». Атака опасна тем, что можно поменять запрос, а соответственно выполнить то, за что этот запрос отвечает (например, перевод денег)
SHA3 не был единственным прорывом, который вышел из конкурса хеширования NIST в 2006 году. Несмотря на то, что SHA3 выиграл, алгоритм, известный как BLAKE, занял второе место. Для реализации шардинга Ethereum 2.0 использует более эффективное. Алгоритм хэширования BLAKE2b, который является высокоразвитой версией BLAKE от конкурентов, интенсивно изучается за его фантастическую эффективность по сравнению с KECCAK256 при сохранении высокой степени безопасности. Вычисление BLAKE2b фактически в 3 раза быстрее, чем KECCAK на современном процессоре.
Будущее алгоритмов хэширования
Кажется, что независимо от того, что мы делаем, мы просто либо (1) увеличиваем сложность внутренних хеш-операций, либо (2) увеличиваем длину хеш-выхода, надеясь, что компьютеры атакующих не будут достаточно быстрыми, чтобы эффективно вычислять ее коллизию. Мы полагаемся на двусмысленность предварительных прообразов односторонних операций для обеспечения безопасности наших сетей. То есть цель безопасности алгоритма хеширования состоит в том, чтобы сделать как можно более сложным для любого, кто пытается найти два значения, которые хешируются на один и тот же вывод, несмотря на то, что существует бесконечное количество возможных столкновений. «Как насчет будущего квантовых компьютеров? Будут ли алгоритмы хэширования безопасными?» Короткий ответ и текущее понимание заключаются в том, что да, алгоритмы хэширования выдержат испытание временем против квантовых вычислений. То, что квантовые вычисления смогут сломать, - это те проблемы, которые имеют строгую математическую структуру, основанную на аккуратных трюках и теории, такой как шифрование RSA. С другой стороны, алгоритмы хэширования имеют менее формальную структуру во внутренних конструкциях. Квантовые компьютеры действительно дают повышенную скорость в вычислении неструктурированных проблем, таких как хэширование, но в конце концов, они все равно будут грубо атаковать так же, как компьютер сегодня попытается это сделать. Независимо от того, какие алгоритмы мы выбираем для наших протоколов, ясно, что мы движемся к вычислительно-эффективному будущему, и мы должны использовать наше лучшее суждение, чтобы выбрать правильные инструменты для работы и те, которые, мы надеемся, выдержат испытание временем.
_____________________________________________________________________________
______________________________________________________________________________
В рамках данной статьи, я расскажу вам что такое Хэш , зачем он нужен, где и как применяется, а так же наиболее известные примеры.
Многие задачи в области информационных технологий весьма критичны к объемам данных. Например, если нужно сравнить между собой два файла размером по 1 Кб и два файла по 10 Гб, то это совершенно разное время. Поэтому алгоритмы, позволяющие оперировать более короткими и емкими значениями, считаются весьма востребованными.
Одной из таких технологий является Хэширование, которое нашло свое применение при решении массы задач. Но, думаю вам, как обычному пользователю, все еще непонятно, что же это за зверь такой и для чего он нужен. Поэтому далее я постараюсь объяснить все наиболее простыми словами.
Примечание : Материал рассчитан на обычных пользователей и не содержит многих технических аспектов, однако для базового ознакомления его более, чем достаточно.
Что такое Хэш или Хэширование?
Начну с терминов.
Хэш-функция, Функция свертки - это специального вида функция, которая позволяет преобразовывать произвольной длины тексты к коду фиксированной длины (обычно, короткая цифро-буквенная запись).
Хэширование - это сам процесс преобразования исходных текстов.
Хэш, Хеш-код, Значение Хэш, Хэш-сумма - это выходное значение Хэш-функции, то есть полученный блок фиксированный длины.
Как видите, у терминов несколько образное описание, из которого сложно понять для чего это все нужно. Поэтому сразу приведу небольшой пример (об остальных применениях расскажу чуть позже). Допустим, у вас есть 2 файла размером 10 Гб. Как можно быстро узнать какой из них нужный? Можно использовать имя файла, но его легко переименовать. Можно смотреть даты, но после копирования файлов даты могут быть одинаковыми или в иной последовательности. Размер, как сами понимаете, мало чем может помочь (особенно, если размеры совпадают или вы не смотрели точные значения байтов).
Вот тут-то и нужен этот самый Хэш, который представляет собой короткий блок, формирующийся из исходного текста файла. У этих двух файлов по 10 Гб будет два разных, но коротких Хэш-кода (что-то вроде "ACCAC43535" и "BBB3232A42"). Используя их, можно будет быстро узнать нужный файл, даже после копирования и смены имен.
Примечание : В связи с тем, что Хэш в компьютером мире и в интернете весьма известное понятие, то нередко все то, что имеет отношение к Хэшу, сокращают до этого самого слова. Например, фраза "у меня используется Хэш MD5" в переводе означает, что на сайте или где-то еще используется алгоритм хэширования стандарта MD5.
Свойства Хеш-функций
Теперь, расскажу о свойствах Хэш-функций, чтобы вам было легче понять где применяется и для чего нужно Хэширование. Но, сначала еще одно определение.
Коллизия - это ситуация, когда для двух разных текстов получается одна и та же Хэш-сумма. Как сами понимаете, раз блок фиксированной длины, то он имеет ограниченное число возможных значений, а следовательно возможны повторы.
А теперь к самим свойствам Хэш-функций:
1. На вход может подаваться текст любого размера, а на выходе получается блок данных фиксированной длины. Это следует из определения.
2. Хэш-сумма одних и тех же текстов должна быть одинаковой. В противном случае, такие функции просто бесполезны - это аналогично случайному числу.
3. Хорошая функция свертки должна иметь хорошее распределение. Согласитесь, что если размер выходного Хэша, к примеру, 16 байт, то если функция возвращает всего 3 разных значения для любых текстов, то толку от такой функции и этих 16 байт никакого (16 байт это 2^128 вариантов, что примерно равно 3,4 * 10^38 степени).
4. Как хорошо функция реагирует на малейшие изменения в исходном тексте. Простой пример. Поменяли 1 букву в файле размером 10 Гб, значение функции должно стать другим. Если же это не так, то применять такую функцию весьма проблематично.
5. Вероятность возникновения коллизии. Весьма сложный параметр, рассчитываемый при определенных условиях. Но, суть его в том, что какой смысл от Хэш-функции, если полученная Хэш-сумма будет часто совпадать.
6. Скорость вычисления Хэша. Какой толк от функции свертки, если она будет долго вычисляться? Никакой, ведь тогда проще данные файлов сравнивать или использовать иной подход.
7. Сложность восстановления исходных данных из значения Хэша. Эта характеристика больше специфическая, нежели общая, так как не везде требуется подобное. Однако, для наиболее известных алгоритмов эта характеристика оценивается. Например, исходный файл вы вряд ли сможете получить из этой функции. Однако, если имеет место проблема коллизий (к примеру, нужно найти любой текст, который соответствует такому Хэшу), то такая характеристика может быть важной. Например, пароли, но о них чуть позже.
8. Открыт или закрыт исходный код такой функции. Если код не является открытым, то сложность восстановления данных, а именно криптостойкость, остается под вопросом. Отчасти, это проблема как с шифрованием .
Вот теперь можно переходить к вопросу "а для чего это все?".
Зачем нужен Хэш?
Основные цели у Хэш-функций всего три (вернее их предназначения).
1. Проверка целостности данных. В данном случае все просто, такая функция должна вычисляться быстро и позволять так же быстро проверить, что, к примеру, скачанный из интернета файл не был поврежден во время передачи.
2. Рост скорости поиска данных. Фиксированный размер блока позволяет получить немало преимуществ в решении задач поиска. В данном случае, речь идет о том, что, чисто технически, использование Хэш-функций может положительно сказываться на производительности. Для таких функций весьма важное значение представляют вероятность возникновения коллизий и хорошее распределение.
3. Для криптографических нужд. Данный вид функций свертки применяется в тех областях безопасности, где важно чтобы результаты сложно было подменить или где необходимо максимально усложнить задачу получения полезной информации из Хэша.
Где и как применяется Хэш?
Как вы, вероятно, уже догадались Хэш применяется при решении очень многих задач. Вот несколько из них:
1. Пароли обычно хранятся не в открытом виде, а в виде Хэш-сумм, что позволяет обеспечить более высокую степень безопасности. Ведь даже если злоумышленник получит доступ к такой БД, ему еще придется немало времени потратить, чтобы подобрать к этим Хэш-кодам соответствующие тексты. Вот тут и важна характеристика "сложность восстановления исходных данных из значений Хэша".
Примечание : Советую ознакомиться со статьей пара советов для повышения уровня безопасности паролей .
2. В программировании, включая базы данных. Конечно же, чаще всего речь идет о структурах данных, позволяющих осуществлять быстрый поиск. Чисто технический аспект.
3. При передачи данных по сети (включая Интернет). Многие протоколы, такие как TCP/IP, включают в себя специальные проверочные поля, содержащие Хэш-сумму исходного сообщения, чтобы если где-то произошел сбой, то это не повлияло на передачу данных.
4. Для различных алгоритмов, связанных с безопасностью. Например, Хэш применяется в электронных цифровых подписях.
5. Для проверки целостности файлов. Если обращали внимание, то нередко в интернете можно встретить у файлов (к примеру, архивы) дополнительные описания с Хэш-кодом. Эта мера применяется не только для того, чтобы вы случайно не запустили файл, который повредился при скачивании из Интернета, но и бывают просто сбои на хостингах . В таких случаях, можно быстро проверить Хэш и если требуется, то перезалить файл.
6. Иногда, Хэш-функции применяются для создания уникальных идентификаторов (как часть). Например, при сохранении картинок или просто файлов, обычно используют Хэш в именах совместно с датой и временем. Это позволяет не перезаписывать файлы с одинаковыми именами.
На самом деле, чем дальше, тем чаще Хэш-функции применяются в информационных технологиях. В основном из-за того, что объемы данных и мощности самых простых компьютеров сильно возрасли. В первом случае, речь больше о поиске, а во втором речь больше о вопросах безопасности.
Известные Хэш-функции
Самыми известными считаются следующие три Хэш-функции.
