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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если вспомнить, насколько рандомизируют входное сообщение блочные шифры, можно в качестве функции хэш-преобразования использовать какой-нибудь блочный шифр. То, что блочные шифры являются обратимыми преобразованиями, не противоречит свойствам хэш-функции, поскольку блочный шифр необратим по ключу шифрования, и, если в качестве ключа шифрования использовать выход предыдущего шага хэш-преобразования, а в качестве шифруемого сообщения очередной блок сообщения (или наоборот), то можно получить хэш-функцию с хорошими криптографическими характеристиками. Такой подход использован, например, в российском стандарте хэширования – ГОСТ Р 34.11-94. Эта хэш-функция формирует 256-битное выходное значение, используя в качестве преобразующей операции блочный шифр ГОСТ 28147-89 (рис.2.17). Функция хэширования H получает на вход хэш, полученный на предыдущем шаге (значение h 0 произвольное начальное число), а также очередной блок сообщения m i . Ее внутренняя структура представлена на рис.2.18. Здесь в блоке шифрующего преобразования для модификации h i в s i используется блочный шифр ГОСТ 28147-89. Перемешивающее преобразование представляет собой модифицированную перестановку Фейштеля. Для последнего блока m N (N – общее количество блоков сообщения) выполняется набивка до размера 256 бит с добавлением истинной длины сообщения.Параллельно подсчитывается контрольная суммасообщения ∑ и суммарная длина L, которые участвуют в финальной функции сжатия.

Основным недостатком хэш-функций на основе блочных шифров является невысокая скорость их работы. Поэтому были спроектированы ряд специализированных алгоритмов, которые, обеспечивая аналогичную стойкость к атакам, выполняют гораздо меньшее количество операций над входными данными и обеспечивают большую скорость работы. Примерами подобного рода алгоритмов являются: MD2, MD4, MD5, RIPEMD – 160, SHA. Рассмотрим подробнее структуру алгоритма хэширования SHA (Secure Hash Algorithm), который описан в стандарте SHS и обеспечивает безопасность электронной цифровой подписи DSA, формируя 160-битный дайджест сообщения.

Сначала сообщение разбивается на блоки длиной 512 бит. Если длина сообщения не кратна 512, к последнему блоку приписывается справа 1, после чего он дополняется нулями до 512 бит. В конец последнего блока записывается код длины сообщения. В результате сообщение приобретает вид n 512-разрядных блоков M 1 , M 2 , …, M n .

Алгоритм SHA использует 80 логических функций f 0 , f 1 , …, f 79 , которые производят операции над тремя 32-разрядными словами (B,C,D):

В алгоритме используются также специальным образом инициализированные 4 константы K i и 5 начальных значений H i .

Делим массив M на группы из 16 слов W 0 , W 1 ,…,W 15 (W 0 самое левое слово).
Для t = 16 - 79 W t = S 1 (W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16)
S k означает операцию циклического сдвига влево на k разрядов.
Пусть теперь A = H 0 , B = H 1 , C = H 2 , D = H 3 , E = H 4 .
for t = 0 to 79 do
TEMP = S 5 (A) + f t (B, C, D) + E + W t + K i .
E = D; D = C; C = S 30 (B); B = A; A = TEMP;
Пусть H 0 = H 0 + A; H 1 = H 1 + B; H 2 = H 2 + C; H 3 = H 3 + D; H 4 = H 4 + E.

Графически один цикл SHA представлен на рис.2.19.

В результате обработки массива М будет получено 5 слов H 0 , H 1 , H 2 , H 3 , H 4 с общей длиной 160 бит, которые и образуют дайджест сообщения.

Из приведенных данных ясно, что сложность американского стандарта хэширования ниже, чем у российского. Российский стандарт предполагает выполнение четырех шифрований за один цикл выработки хэша, или в общей сложности 128 раундов. Каждый раунд шифрования требует примерно полтора десятка элементарных машинных операций, что существенно увеличивает затраты машинного времени на выполнение линейных перемешивающих операций. Один раунд выработки хэша SHA гораздо проще: он весь может быть реализован примерно за 15-20 команд, общее количество раундов всего 80, и за один цикл выработки хэша обрабатывается вдвое больше исходных данных - 512 против 256 в ГОСТ P34.ll - 94. Таким образом, можно предположить, что быстродействие программных реализаций SHA будет примерно в 3-6 раз быстрее, чем у отечественного стандарта.

Основная задача хэш-функций – генерация дайджестов, уникальных для конкретного документа. Если для двух различных входных блоков хэш-функция дает одинаковый дайджест, такая ситуация называется хэш-коллизией . Из теоремы, носящей название «парадокс дней рождения», следует, что для n-битного хэш-значения необходимо в среднем 2 n/2 различных входных сообщений, чтобы возникла коллизия. Это делает практически невозможным изменение документа при его подписи с помощью, например, алгоритма SHА путем простого подбора, поскольку при таком подходе потребуется сгенерировать около 2 80 различных сообщений, чтобы получить аналогичное подменяемому по получаемому дайджесту. Эта цифра недостижима для современного уровня технологий.

Лекция

доцента кафедры ИВТ Гродненского госуниверситета

канд. техн. наук Ливак Елены Николаевны

Функции хэширования.

Механизм хэш-функций

Функции хэширования играют главную роль в современной криптографии.

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

С помощью хэш-функций реализуют

1.Проверку целостности данных (обнаружение изменений)

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

Очевидно, что неравенство сравниваемых величин означает нарушение целостности.

2.Системы аутентификации

Используют хэширование паролей.

3.Создание и проверку ЭЦП

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

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

1)по заданному y = h ( x ) определить x (односторонняя функция h );

2)для заданного x найти другое x´ , такое, что h(x)= h(x´) (свободная от коллизий функция h );

3)найти пару x, x´ (x ≠ x´) , такую, что h(x)= h(x´) (строго свободная от коллизий функция h ).

Обратим внимание, значение хэш-функции также называют

Хэш-код

Функция (значение) свертки

Профиль сообщения

Дайджест сообщения

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

Цифровой отпечаток

Код аутентичности сообщения

Код обнаружения манипуляций

Функции хэширования (Алгоритмы создания дайджестов сообщений)

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

SHA - Secure Hash Algorithm (1992)

160-разрядный хэш-код (дайджест). НЕ устойчив к коллизиям.

512- битовые блоки .

SHA-1 - Secure Hash Algorithm 1 (1995)

Модификация SHA . Исправлены недостатки. Решает проблему коллизий.

· MAC - Message Authentication Code - код аутентификации (проверки подлинности) сообщения.

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

· HMAC

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

Алгоритм HMAC [представлен в документе RFC 2104] принят как обязательный в протоколе IPSec и используется в ряде других протоколов Internet (TLS , SET и другие)

Широко используются на практике также функции, разработанные Роном Ривестом:

· MD2 - Message Digest #2

Низкоскоростной, но очень надежный алгоритм, создающий 128-разрядные дайджесты данных любого объема.

MD4 - Message Digest #4 (1990)

Более скоростной, но менее надежный алгоритм, создающий 128-разрядные дайджесты данных любого объема. 512-битовые блоки. Есть дефекты.

· MD5 - Message Digest #5 (1992)

Версия MD 4 с повышенной надежностью, преимущества также и в скорости. 128-разрядные дайджесты данных любого объема.

Неустойчив к коллизиям! Не используется для долговременных ЭЦП.

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

Современные технологии распределенных вычислений и многопроцессорные компьютеры демонстрируют недостаточную защищенность 128-битовых хэш-кодов. «Кроме того, были разработаны сценарии целого ряда атак, демонстрирующих уязвимость MD 5 в отношении современных методов криптоанализа» [Шнайер].

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

Заметим также, что в российском стандарте ГОСТ Р 34.11-94 (в основе схемы Эль-Гамаля и Шнорра) длина хэш-кода равна 256 битам.

Защищенная функция хэширования SHA –1 (Secure Hash Algorithm )

Алгоритм SHA был разработан Национальным институтом стандартов и технологии США (NIST ) и опубликован в виде федерального стандарта обработки информации в 1993 г. Пересмотренная версия вышла в 1995 г.

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

Основные характеристики алгоритма SHA приведены в таблице.

Основные характеристики SHA

Длина хэш-кода
Длина обрабатываемых блоков
Число шагов алгоритма	80 (4 раунда по 20 шагов )
Максимальная длина хэшируемых данных
Число базовых функций
Число аддитивных констант

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

1.На вход поступает k -бит ов ый блок данных, где k < 2 64 .

2. k -битовый блок дополняется так, чтобы его длина стала кратной 512 разрядам (данные обрабатываются 512-битовыми блоками). Структура дополнения следующая: 100...0 (от 1 до 512 бит).

3.К полученному результату добавляется 64-битовое представление длины исходного блока данных.

4.Инициализируются пять 32-разрядных переменных:

A = 0x67452301

B = 0xefcdab89

C = 0x98badcfe

D = 0x10325476

E = 0 xc 3 d 2 e 1 f 0

5.Производится обработка 512-битовых блоков данных в 4 раунда по 20 операций каждый.

На рисунке (см . в презентации к лекции) представлена схема одной операции SHA . Циклический сдвиг влево на s разрядов обозначен « s ; W t – подблок дополненного сообщения такой, что:

W t = M t (0 ≤ t ≤ 15), где M t – 32-битовый блок данных

W t = (W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16) « 1 (16 ≤ t ≤ 79).

Соответствие аддитивных констант K t и нелинейных функций F t номеру операции представлено в таблице (см . презентацию к лекции).

6.Значения переменных a , b , c , d , e складываются, соответственно, с A , B , C , D , E .

7.Обрабатывается следующий блок данных.

8.Окончательный результат получается конкатенацией значений A , B , C , D , E .

На выходе получается 160-битовый хэш-код.

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

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

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

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

Для данного аргумента x невозможно найти другой аргумент y такой, что h(x) = h(y) . Такие хеш-функции называют стойкими в смысле вычисления коллизий или стойкими в слабом смысле .

В случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то это значение называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой .

На практике хеш-функции используют в следующих целях:

Для ускорения поиска данных в БД;

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

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

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

Рис.10.1. Процедура вычисления значения хеш-функции

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

2) Для инициализации процедуры хеширования используется синхропосылка y 0 .

3) Прообраз X разбивается на n блоков x i (i = 1 .. n) фиксированной длины L бл , над которыми выполняется однотипная процедура хеширования f(y i-1 , x i) , зависящая от результата хеширования предыдущего блока y i-1 .

4) Хеш-образом h(T) исходного сообщения Т будет результат процедуры хеширования y n , полученный после обработки последнего блока x n .

10.2. MD5

MD5 (англ. Message Digest 5) – 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 г. Является улучшенной в плане безопасности версией MD4 .

Ниже приведен алгоритм вычисления хеша.

1. Выравнивание потока.

В конец исходного сообщения, длиной L , дописывают единичный бит, затем необходимое число нулевых бит так, чтобы новый размер L" был сравним с 448 по модулю 512 (L’ mod 512 = 448). Добавление нулевых бит выполняется, даже если новая длина, включая единичный бит, уже сравнима с 448.

2. Добавление длины сообщения.

К модифицированному сообщению дописывают 64-битное представление длины данных (количество бит в сообщении). Т.е. длина сообщения T становится кратной 512 (T mod 512 = 0). Если длина исходного сообщения превосходит 2 64 - 1, то дописывают только младшие 64 бита. Кроме этого, для указанного 64-битного представления длины вначале записываются младшие 32 бита, а затем старшие 32 бита.

3. Инициализация буфера.

Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения (шестнадцатеричное представление):

A = 67 45 23 01;
B = EF CD AB 89;
C = 98 BA DC FE;
D = 10 32 54 76.

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

4. Вычисление хеша в цикле.

Исходное сообщение разбивается на блоки T , длиной 512 бит. Для каждого блока в цикле выполняется процедура, приведенная на рис.10.2. Результат обработки всех блоков исходного сообщения в виде объединения 32-битных значений переменных ABCD и будет являться хешем.

Рис.10.2. Шаг основного цикла вычисления хеша

В каждом раунде над переменными ABCD и блоком исходного текста Т в цикле (16 итераций) выполняются однотипные преобразования по следующей схеме.

Рис.10.3. Одна итерация цикла раунда

Условные обозначения.

1) RF - раундовая функция, определяемая по следующей таблице.

Таблица 10.1. Раундовые функции RF

2) t j - j-ая 32-битовая часть блока исходного сообщения Т с обратным порядком следования байт;

3) k i - целая часть константы, определяемой по формуле

k i = 2 32 * | sin(i + 16 * (r - 1)) |, (10.1)

где i – номер итерации цикла (i = 1..16);
r – номер раунда (r = 1..4).

Аргумент функции sin измеряется в радианах.

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

5) <<< s i – циклический сдвиг влево на s i разрядов.

Используемая 32-битовая часть блока исходного сообщения t j и величина циклического сдвига влево s i зависят от номера итерации и приведены в следующей таблице.

Таблица 10.2. Величины, используемые на шаге цикла раунда

№ итерации		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Раунд 1	t j	t 1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10	t 11	t 12	t 13	t 14	t 15	t 16
	s i	7	12	17	22	7	12	17	22	7	12	17	22	7	12	17	22
Раунд 2	t j	t 2	t 7	t 12	t 1	t 6	t 11	t 16	t 5	t 10	t 15	t 4	t 9	t 14	t 3	t 8	t 13
	s i	5	9	14	20	5	9	14	20	5	9	14	20	5	9	14	20
Раунд 3	t j	t 6	t 9	t 12	t 15	t 2	t 5	t 8	t 11	t 14	t 1	t 4	t 7	t 10	t 13	t 16	t 3
	s i	4	11	16	23	4	11	16	23	4	11	16	23	4	11	16	23
Раунд 4	t j	t 1	t 8	t 15	t 6	t 13	t 4	t 11	t 2	t 9	t 16	t 7	t 14	t 5	t 12	t 3	t 10
	s i	6	10	15	21	6	10	15	21	6	10	15	21	6	10	15	21

После 4 раундов новое (модифицированное) значение каждой из переменных ABCD складывается (⊞ ) с исходным (значением переменной до 1-го раунда).

5. Перестановка байт в переменных ABCD . После обработки всех блоков исходного сообщения для каждой переменной выполняется обратная перестановка байт.

Поиск коллизий.

В 2004 г. китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии.

10.3. Применение шифрования для получения хеш-образа

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

Напомним что в случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то хеш-образ называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой .

В качестве примера приведем режим (сцепление блоков шифра - Cipher Block Chaining).

Рис.10.4. Схема алгоритма DES в режиме сцепления блоков шифра

Последний зашифрованный блок C n и есть хеш-образ сообщения T = {T 1 , T 2 , …, T n } .

1 ГОСТ 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования».

2 ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».

Вопросы для самопроверки

1. Дайте определение понятиям: « », « », « ».