Структура Меркла-Дамгарда

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

Алгоритмы

§ Message-Digest algorithm 5 (MD5)

§ SHA-1, SHA-2, SHA-3

Вопрос 11.

Целостность информации.

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

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

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

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

MAC.

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

§ простота вычисления дайджеста от сообщения;

§ сжатие данных — входное сообщение произвольной битовой длины преобразуется в дайджест фиксированной длины;

§ стойкость ко взлому — имея одну и более пар сообщение-дайджест, (x[i], h(x[i])), вычислительно невозможно получить новую сообщение пару (x, h(x)), для какого-либо нового сообщения x.

Если не выполняется последнее свойство, то MAC может быть подделан. Также последнее свойство подразумевает, что ключ невозможно вычислить, то есть, имея одну или более пар (x[i], h(x[i])) с ключом k, вычислительно невозможно получить этот ключ.

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

§ на блочных шифрах — например: CBC-MAC, RIPE-MAC1, RIPE-MAC3;

§ получение MAC из MDC;

§ кастомизированные алгоритмы — например: MAA, MD5-MAC;

§ на потоковых шифрах — например: CRC-based MAC.

Обеспечение целостности данных с использование шифрации и MAC

В канал посылается сообщение следующего вида: E _k(x || h _k1(x)). Такая схема обеспечения целостности имеет преимущество над схемой с MDC: если шифр будет взломан, MAC все равно будет обеспечивать целостность данных. Недостатком является то, что используется два различных ключа, для криптоалгоритма и для MAC. При использовании подобной схемы, следует быть уверенным, что какие-либо зависимости между алгоритмом MAC и алгоритмом шифрации не приведут к уязвимости системы. Рекомендуется, чтобы эти два алгоритма были независимыми.

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

HMAC.

(хеш-код идентификации сообщений). Наличие способа проверить целостность информации, передаваемой или хранящийся в ненадежной среде является неотъемлемой и необходимой частью мира открытых вычислений и коммуникаций. Механизмы, которые предоставляют такие проверки целостности на основе секретного ключа обычно называют кодом аутентичности сообщения(MAC). Как правило, МАС используется между двумя сторонами, которые разделяют секретный ключ для проверки подлинности информации, передаваемой между этими сторонами. Этот стандарт определяет MAC. Механизм, который использует криптографические хеш-функции в сочетании с секретным ключом называется HMAC.

Основная цель:

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

§ Чтобы сохранить первоначальное исполнение хэш-функции, без каких нибудь значительных ухудшении

§ Использовать и обрабатывать ключи более простым способом.

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

Принцип работы

1. Если длина ключа К = b, то K ₀ = K. Переходим сразу к шагу 4.

2. Если длина ключа K > b, то применяем H к ключу K для получения L-байтовой строки. Добавить нули к левой части этой строки для создания b-байтовой строки K ₀.Переходим сразу к шагу 4.

3. Если длина ключа K < b то добавляем нули к левой части K для создания b-байтовой строки K ₀ (например, если К имеет длину 20 байтов и b = 64, то к левой части К будет добавлено 44 нулевых байта 0x00).

4. K ₀ ipad — (xor побитовое исключающее ИЛИ) для получения b-байтового блока S_i.

5. Сложить М с S_i.

6. Применить Н к потоку, созданному на шаге 5.

7. K ₀ opad для получения b-байтового блока S_o.

8. Сложить результат хеширования на шаге 6 с S_o.

9. Применить Н к потоку, созданному на шаге 8 и вывести результат.

или если выразить одной математической формулой: