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

Нередко при скачивании торрентов или непосредственно самих файлов в описании стоит что-то наподобие «ad33e486d0578a892b8vbd8b19e28754» (например, в ex.ua), нередко с припиской «md5». Это хеш-код - результат, который выдает хэш-функция после обработки входящих данных. В переводе с английского хэш обозначает путаницу, марихуану, травку или блюдо из мелко нарезанного мяса и овощей. очень и очень сложно, можно сказать, что практически невозможно. Тогда возникает вопрос: «Зачем вообще нужны все эти они выдают непонятную абракадабру, которая еще и не поддается расшифровке?». Об этом и пойдет речь в данной статье.

Что такое хэш-функция и как она действует?

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

Зачем нужна хеш-функция?

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

Хэш-функции: какими они бываю т

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

1. Функция для проверки целостности информации

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

2. Криптографическая функция

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

3. Функция, предназначенная для создания эффективной структуры данных

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

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

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

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

Известные Хэш-функции

Самыми известными считаются следующие три Хэш-функции.

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

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

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

Какими характеристиками должна обладать хеш-функция?

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

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

• CRC – циклический избыточный код или контрольная сумма. Алгоритм весьма прост, имеет большое количество вариаций в зависимости от необходимой выходной длины. Не является криптографическим!
• MD 5 – очень популярный алгоритм. Как и его предыдущая версия MD 4 является криптографической функцией. Размер хеша 128 бит.
• SHA -1 – также очень популярная криптографическаяфункция. Размер хеша 160 бит.
• ГОСТ Р 34.11-94 – российский криптографический стандарт вычисления хеш-функции. Размер хеша 256 бит.

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

Чем удобнее рассчитывать хеш? Сейчас существует большое количество подобных утилит как платных, так и свободных для использования. Мне лично понравилась HashTab . Во-первых, утилита при установке встраивается в виде вкладки в свойства файлов, во-вторых, позволяет выбирать большое количество алгоритмов хеширования, а в третьих является бесплатной для частного некоммерческого использования.

Что есть российского? Как было сказано выше в России есть стандарт хеширования ГОСТ Р 34.11-94, который повсеместно используется многими производителями средств защиты информации. Одним из таких средств является программа фиксации и контроля исходного состояния программного комплекса «ФИКС». Эта программа является средством контроля эффективности применения СЗИ.

ФИКС (версия 2.0.1) для Windows 9x/NT/2000/XP

• Вычисление контрольных сумм заданных файлов по одному из 5 реализованных алгоритмов.
• Фиксация и последующий контроль исходного состояния программного комплекса.
• Сравнение версий программного комплекса.
• Фиксация и контроль каталогов.
• Контроль изменений в заданных файлах (каталогах).
• Формирование отчетов в форматах TXT, HTML, SV.
• Изделие имеет сертификат ФСТЭК по НДВ 3 № 913 до 01 июня 2013 г.

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

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

Хеширование (от англ. 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(