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

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

Хэш-код создается функцией Н:

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

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

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

1. Хэш-функция Н должна применяться к блоку данных любой длины.

2. Хэш-функция Н создает выход фиксированной длины.

3. Н (М) относительно легко (за полиномиальное время) вычисляется для любого значения М.

4. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h.

5. Для любого данного х вычислительно невозможно найти , что H (y) = H (x).

6. Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x).

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

Четвертое свойство определяет требование односторонности хэш-функции : легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду . Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. При перехвате передачи атакующий получает сообщение М и хэш-код С = Н (S AB || M). Если атакующий может инвертировать хэш-функцию , то, следовательно, он может получить S AB || M = H -1 (C). Так как атакующий теперь знает и М и S AB || M, получить S AB совсем просто.

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

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

Конец работы -

Эта тема принадлежит разделу:

Конспект лекций по дисциплине программно-аппаратные средства защиты информации основные понятия и определения

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

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

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

Модель сетевого взаимодействия
Модель безопасного сетевого взаимодействия в общем виде можно представить следующим образом:

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

Сеть Фейстеля
Блочный алгоритм преобразовывает n-битный блок незашифрованного текста в n-битный блок зашифрованного текста. Число блоков длины n равно 2n. Для того чтобы преобразование было обр

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

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

Используемые критерии при разработке алгоритмов
Принимая во внимание перечисленные требования, обычно считается, что алгоритм симметричного шифрования должен: · Манипулировать данными в больших блоках, предпочтительно размером 16

Принципы разработки
Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 г

Теперь рассмотрим последовательность преобразований, используемую в каждом раунде.

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

Недостатки двойного DES
Простейший способ увеличить длину ключа состоит в повторном применении DES с двумя разными ключами. Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрова

Тройной DES с двумя ключами
Очевидное противодействие атаке "встреча посередине" состоит в использовании третьей стадии шифрования с тремя различными ключами. Это поднимает стоимость лобовой атаки до 2168

Алгоритм Blowfish
Blowfish является сетью Фейстеля, у которой количество итераций равно 16. Длина блока равна 64 битам, ключ может иметь любую длину в пределах 448 бит. Хотя перед

Генерация подключей
Подключи вычисляются с использованием самого алгоритма Blowfish. 1. Инициализировать первый Р -массив и четыре S-boxes фиксированной строкой. 2. Выполнить опе

Криптографическая стойкость
Следующие характеристики IDEA характеризуют его криптографическую стойкость: 1. Длина блока: длина блока должна быть достаточной, чтобы скрыть все статистиче

Последовательность преобразований отдельного раунда
Рассмотрим последовательность преобразований отдельного раунда. Одним из основных элементов алгоритма, обеспечивающих диффузию, является структура, называемая МА (умножение/с

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

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

Алгоритм ГОСТ 28147
Алгоритм ГОСТ 28147 является отечественным стандартом для алгоритмов симметричного шифрования. ГОСТ 28147 разработан в 1989 году, является блочным алгоритмо

Режимы выполнения алгоритмов симметричного шифрования
Для любого симметричного блочного алгоритма шифрования определено четыре режима выполнения. ECB - Electronic Codebook - каждый блок из 64 бит незашифрова

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

Режим CBC
Для преодоления недостатков ECB используют способ, при котором одинаковые незашифрованные блоки преобразуются в различные зашифрованные. Для этого в качестве входа алгоритма используе

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

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

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

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

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

Циклическое шифрование
Рис. 3.14.Циклическое шифрование В данном случ

Генератор псевдослучайных чисел ANSI X9.17
Один из наиболее сильных генераторов псевдослучайных чисел описан в ANSI X9.17. В число приложений, использующих эту технологию, входят приложения финансовой безопасности и PGP.

Историческая справка
2 января 1997 года NIST объявил о начале разработки AES, и 12 сентября 1997 года были представлены официальные требования к алгоритмам. В этих требованиях указывалось, что целью NI

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

Критерий оценки
В сентябре 1997 года, объявив об алгоритмах кандидатов, специалисты NIST определили общий критерий, который должен использоваться при сравнении алгоритмов. Критерий оценки бы

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

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

Запасной алгоритм
Как уже отмечалось, существует взаимосвязь между обсуждениями проблемы нескольких алгоритмов AES и выбором запасного алгоритма, особенно в случае единственного алгоритма AES. Backu

Модификация алгоритмов
На первом и втором этапах обсуждения был отмечен интерес к увеличению числа раундов в некоторых алгоритмах. Во многих случаях увеличение количества раундов объяснялось. Так, про Rijndael

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

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

Изменение скорости выполнения в зависимости от длины ключа
Программное выполнение MARS, RC6 и Serpent не очень сильно изменяется в зависимости от длины ключа. Однако для Rijndael иTwofish установление ключа или шиф

Краткий вывод о скорости выполнения на основных программных платформах
Огромное количество информации собрано относительно скорости финалистов на различных программных платформах. Эти платформы включают 32-битные процессоры (реализации на С и Java), 64-битные п

Окружения с ограничениями пространства
В некоторых окружениях, обладающих небольшими объемами RAM и/или ROM для таких целей, как хранение кода (обычно в ROM), представление объектов данных, таких как S-boxes (которые могут

Замечания по финалистам
MARS имеет определенные сложности в силу гетерогенной структуры раунда (четыре различных типа раунда). Для S-boxes необходимо 2 Kbytes ROM, что не является проблемой,

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

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

Основные способы использования алгоритмов с открытым ключом
Основными способами использования алгоритмов с открытым ключом являются шифрование/дешифрование, создание и проверка подписи и обмен ключа. Шифрование с о

Описание алгоритма
Алгоритм, разработанный Ривестом, Шамиром и Адлеманом, использует выражения с экспонентами. Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа n. Шифро

Создание ключей
Создание ключей включает следующие задачи: 1. Определить два простых числа р и q. 2. Выбрать е и вычислить d. Прежде всего, рассмотрим проблемы, связанные с выбором р и q

Обсуждение криптоанализа
Можно определить четыре возможных подхода для криптоанализа алгоритма RSA: 1. Лобовая атака: перебрать все возможные закрытые ключи. 2. Разложить n на два простых со

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

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

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

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

Шаг 5: Выход
После обработки всех L 512-битных блоков выходом L-ой стадии является 128-битный дайджест сообщения. Рассмотрим более детально логику каждого из четырех циклов выполнения одного 512

Алгоритм MD4
Алгоритм MD4 является более ранней разработкой того же автора Рона Ривеста. Первоначально данный алгоритм был опубликован в октябре 1990 г., незначительно измененная версия была опубликована

Усиление алгоритма в MD5
Алгоритм MD5 имеет следующее свойство: каждый бит хэш-кода является функцией от каждого бита входа. Комплексное повторение элементарных функций fF, fG, fH

Шаг 4: Обработка сообщения в 512-битных (16-словных) блоках
Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как HSHA. Все 80 циклических обработок имеют одинаковую структуру.

Шаг 5: Выход
После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения. Рассмотрим более детально логику в каждом из 80 циклов обработки одного 512-битног

Сравнение SHA-1 и MD5
Оба алгоритма, SHA-1 и MD5, произошли от MD4, поэтому имеют много общего. Можно суммировать ключевые различия между алгоритмами. &nbs

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

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

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

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

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

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

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

Применение криптографических хеш-функций в создании электронной подписи

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

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

повышение криптостойкости;
снижение сложности процесса;
обеспечение совместимости.

Применение криптографических хеш-функций при аутентификации парольной фразы

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

Наиболее распространенные криптографические хеш-функции

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

MD5 - один из самых распространённых алгоритмов, являющийся криптографической хеш-функцией, размер которой составляет 128 бит. В ближайшее время готовится обновление версии, так как она уже не соответствует высоким стандартам криптоустойчивости.
ГОСТ Р 34.11-94 - отечественная криптографическая хеш-функция, генерирующая дайджест длиной 256 бит.
ГОСТ Р 34.11-2012 - обновлённая версия, отличающаяся высокой стойкостью к попыткам взлома и стабильностью в работе. Объем выдаваемого хеша может быть как 512, так и 256 бит. Как правило, применяется в системе государственного документооборота, создавая электронные подписи.
SHA-1 - криптографическая хеш-функция, преобразующая информацию в строку, длина которой равняется 160 битам. Не обладает достаточным уровнем криптоустойчивости.
SHA-2 - криптографическая хеш-функция, созданная на основе алгоритмов SHA: 224; 256; 384; 512; 512/256; 512/224. Несмотря на высокую стойкость к взлому, данный алгоритм используется крайне редко. Причина - неудачный результат одного из криптоанализов, во время которого было выявлено критическое количество коллизий (повторений хеша). Разработчики намерены создать новую криптографическую хеш-функцию SHA-3, которая будет основана на алгоритме Keccak.

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

Контрольные суммы

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

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

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

Простейшим случаем такого алгоритма является деление сообщения на 32- или 16- битные слова и их суммирование, что применяется, например, в TCP/IP .

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

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

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

Применение хеширования

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

хорошая перемешиваемость данных
быстрый алгоритм вычисления

Сверка данных

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

Проверка на наличие ошибок

Например, контрольная сумма может быть передана по каналу связи вместе с основным текстом. На приёмном конце, контрольная сумма может быть рассчитана заново и её можно сравнить с переданным значением. Если будет обнаружено расхождение, то это значит, что при передаче возникли искажения и можно запросить повтор.

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

Проверка парольной фразы

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

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP . В них хранятся лишь хеш-значения парольных фраз из учётных записей пользователей.

Ускорение поиска данных

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

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

Список алгоритмов

SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
RIPEMD-160
RIPEMD-320
Snefru
Tiger (Whirlpool
IP Internet Checksum (RFC 1071)

Ссылки

Wikimedia Foundation . 2010 .

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

Требования

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

Необратимость или стойкость к восстановлению прообраза : для заданного значения хеш-функции m не должен быть вычислен блок данных X , для которого ${H(X)=m}.$
Стойкость к коллизиям первого рода или восстановлению вторых прообразов : для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N , для которого $H(N)=H(M).$
Стойкость к коллизиям второго рода : должно быть вычислительно невозможно подобрать пару сообщений $(M, M"),$ имеющих одинаковый хеш.

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

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

Принципы построения

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

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

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

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

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

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

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

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

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

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

Применения

Электронная подпись

Пусть некий клиент, с именем name , производит аутентификацию по парольной фразе, pass , на некоем сервере. На сервере хранится значение хеш-функции H (pass , R 2) , где R 2 - псевдослучайное, заранее выбранное число. Клиент посылает запрос (name , R 1 ), где R 1 - псевдослучайное, каждый раз новое число. В ответ сервер посылает значение R 2 . Клиент вычисляет значение хеш-функции H (R 1 , H (pass , R 2)) и посылает его на сервер. Сервер также вычисляет значение H (R 1 , H (pass , R 2)) и сверяет его с полученным. Если значения совпадают - аутентификация верна.

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

См. также



Общего назначения

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

Функции формирования ключа

Напишите отзыв о статье "Криптографическая хеш-функция"

Отрывок, характеризующий Криптографическая хеш-функция

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

«Monsieur le prince Koutouzov, – писал он, – j"envoie pres de vous un de mes aides de camps generaux pour vous entretenir de plusieurs objets interessants. Je desire que Votre Altesse ajoute foi a ce qu"il lui dira, surtout lorsqu"il exprimera les sentiments d"estime et de particuliere consideration que j"ai depuis longtemps pour sa personne… Cette lettre n"etant a autre fin, je prie Dieu, Monsieur le prince Koutouzov, qu"il vous ait en sa sainte et digne garde,
Moscou, le 3 Octobre, 1812. Signe:
Napoleon».
[Князь Кутузов, посылаю к вам одного из моих генерал адъютантов для переговоров с вами о многих важных предметах. Прошу Вашу Светлость верить всему, что он вам скажет, особенно когда, станет выражать вам чувствования уважения и особенного почтения, питаемые мною к вам с давнего времени. Засим молю бога о сохранении вас под своим священным кровом.
Москва, 3 октября, 1812.
Наполеон. ]

«Je serais maudit par la posterite si l"on me regardait comme le premier moteur d"un accommodement quelconque. Tel est l"esprit actuel de ma nation», [Я бы был проклят, если бы на меня смотрели как на первого зачинщика какой бы то ни было сделки; такова воля нашего народа. ] – отвечал Кутузов и продолжал употреблять все свои силы на то, чтобы удерживать войска от наступления.
В месяц грабежа французского войска в Москве и спокойной стоянки русского войска под Тарутиным совершилось изменение в отношении силы обоих войск (духа и численности), вследствие которого преимущество силы оказалось на стороне русских. Несмотря на то, что положение французского войска и его численность были неизвестны русским, как скоро изменилось отношение, необходимость наступления тотчас же выразилась в бесчисленном количестве признаков. Признаками этими были: и присылка Лористона, и изобилие провианта в Тарутине, и сведения, приходившие со всех сторон о бездействии и беспорядке французов, и комплектование наших полков рекрутами, и хорошая погода, и продолжительный отдых русских солдат, и обыкновенно возникающее в войсках вследствие отдыха нетерпение исполнять то дело, для которого все собраны, и любопытство о том, что делалось во французской армии, так давно потерянной из виду, и смелость, с которою теперь шныряли русские аванпосты около стоявших в Тарутине французов, и известия о легких победах над французами мужиков и партизанов, и зависть, возбуждаемая этим, и чувство мести, лежавшее в душе каждого человека до тех пор, пока французы были в Москве, и (главное) неясное, но возникшее в душе каждого солдата сознание того, что отношение силы изменилось теперь и преимущество находится на нашей стороне. Существенное отношение сил изменилось, и наступление стало необходимым. И тотчас же, так же верно, как начинают бить и играть в часах куранты, когда стрелка совершила полный круг, в высших сферах, соответственно существенному изменению сил, отразилось усиленное движение, шипение и игра курантов.

Русская армия управлялась Кутузовым с его штабом и государем из Петербурга. В Петербурге, еще до получения известия об оставлении Москвы, был составлен подробный план всей войны и прислан Кутузову для руководства. Несмотря на то, что план этот был составлен в предположении того, что Москва еще в наших руках, план этот был одобрен штабом и принят к исполнению. Кутузов писал только, что дальние диверсии всегда трудно исполнимы. И для разрешения встречавшихся трудностей присылались новые наставления и лица, долженствовавшие следить за его действиями и доносить о них.
Кроме того, теперь в русской армии преобразовался весь штаб. Замещались места убитого Багратиона и обиженного, удалившегося Барклая. Весьма серьезно обдумывали, что будет лучше: А. поместить на место Б., а Б. на место Д., или, напротив, Д. на место А. и т. д., как будто что нибудь, кроме удовольствия А. и Б., могло зависеть от этого.
В штабе армии, по случаю враждебности Кутузова с своим начальником штаба, Бенигсеном, и присутствия доверенных лиц государя и этих перемещений, шла более, чем обыкновенно, сложная игра партий: А. подкапывался под Б., Д. под С. и т. д., во всех возможных перемещениях и сочетаниях. При всех этих подкапываниях предметом интриг большей частью было то военное дело, которым думали руководить все эти люди; но это военное дело шло независимо от них, именно так, как оно должно было идти, то есть никогда не совпадая с тем, что придумывали люди, а вытекая из сущности отношения масс. Все эти придумыванья, скрещиваясь, перепутываясь, представляли в высших сферах только верное отражение того, что должно было совершиться.
«Князь Михаил Иларионович! – писал государь от 2 го октября в письме, полученном после Тарутинского сражения. – С 2 го сентября Москва в руках неприятельских. Последние ваши рапорты от 20 го; и в течение всего сего времени не только что ничего не предпринято для действия противу неприятеля и освобождения первопрестольной столицы, но даже, по последним рапортам вашим, вы еще отступили назад. Серпухов уже занят отрядом неприятельским, и Тула, с знаменитым и столь для армии необходимым своим заводом, в опасности. По рапортам от генерала Винцингероде вижу я, что неприятельский 10000 й корпус подвигается по Петербургской дороге. Другой, в нескольких тысячах, также подается к Дмитрову. Третий подвинулся вперед по Владимирской дороге. Четвертый, довольно значительный, стоит между Рузою и Можайском. Наполеон же сам по 25 е число находился в Москве. По всем сим сведениям, когда неприятель сильными отрядами раздробил свои силы, когда Наполеон еще в Москве сам, с своею гвардией, возможно ли, чтобы силы неприятельские, находящиеся перед вами, были значительны и не позволяли вам действовать наступательно? С вероятностию, напротив того, должно полагать, что он вас преследует отрядами или, по крайней мере, корпусом, гораздо слабее армии, вам вверенной. Казалось, что, пользуясь сими обстоятельствами, могли бы вы с выгодою атаковать неприятеля слабее вас и истребить оного или, по меньшей мере, заставя его отступить, сохранить в наших руках знатную часть губерний, ныне неприятелем занимаемых, и тем самым отвратить опасность от Тулы и прочих внутренних наших городов. На вашей ответственности останется, если неприятель в состоянии будет отрядить значительный корпус на Петербург для угрожания сей столице, в которой не могло остаться много войска, ибо с вверенною вам армиею, действуя с решительностию и деятельностию, вы имеете все средства отвратить сие новое несчастие. Вспомните, что вы еще обязаны ответом оскорбленному отечеству в потере Москвы. Вы имели опыты моей готовности вас награждать. Сия готовность не ослабнет во мне, но я и Россия вправе ожидать с вашей стороны всего усердия, твердости и успехов, которые ум ваш, воинские таланты ваши и храбрость войск, вами предводительствуемых, нам предвещают».
Но в то время как письмо это, доказывающее то, что существенное отношение сил уже отражалось и в Петербурге, было в дороге, Кутузов не мог уже удержать командуемую им армию от наступления, и сражение уже было дано.
2 го октября казак Шаповалов, находясь в разъезде, убил из ружья одного и подстрелил другого зайца. Гоняясь за подстреленным зайцем, Шаповалов забрел далеко в лес и наткнулся на левый фланг армии Мюрата, стоящий без всяких предосторожностей. Казак, смеясь, рассказал товарищам, как он чуть не попался французам. Хорунжий, услыхав этот рассказ, сообщил его командиру.

Основные определения, свойства и прочее...

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

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

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

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

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

Важным криптографическим примитивом, который, как правило, строится на основе хэш-функции, является ключевая функция хэширования (message authentication code, MAC). Ключевая функция хэширования также действует на множестве всех возможных сообщений, а ее значения лежат во множестве двоичных векторов конечной фиксированной длины n, однако в процессе вычисления хэш-кода используется некоторый секретный параметр – ключ K (как правило, представляющий собой также двоичный вектор конечной длины). К ключевым функциям хэширования также предъявляется требование о быстроте и эффективности вычисления хэш-кода. Основные криптографические требования к ключевым функциям хэширования можно сформулировать следующим образом:

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

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

Аутентификация (целостность) сообщений

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

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

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

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

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

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

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

Невозможность отказа от авторства (использование хэш-функций при вычислении электронной цифровой подписи)

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

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

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

Идентификация с использованием паролей

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

Другие сферы использования хэш-функций

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

Блочные шифры (например, Shacal-2).
Поточные шифры.
Генераторы псевдослучайных чисел.

Итеративная конструкция Меркля-Дамгорда

По итеративному принципу построено абсолютное большинство хэш-функций, используемых в настоящее время на практике (например, хэш-функции MD5, SHA-1, семейство хэш-функций SHA-2, отечественный стандарт на хэш-функцию ГОСТ Р 34.11-94).

В 1989 году Р. Меркль (Ralph C. Merkle) и И. Дамгорд (Ivan Damgaard) независимо предложили итеративный принцип построения криптографических функций хэширования. Данный принцип позволяет свести задачу построения хэш-функции на множестве сообщений различной длины к задаче построения отображения, действующего на множестве фиксированной конечной длины.

Опишем итеративную конструкцию Меркля-Дамгорда в общем виде. Пусть M – некоторое сообщение, подлежащее хэшированию.

Сообщение M определенным образом дополняется и разбивается на блоки одинаковой фиксированной длины m, т.е. получаем сообщение m1||…||mt. Затем последовательно вычисляются значения некоторой функции g, называемой функцией сжатия (compression function): h(i) = g(h(i-1),mi), i=1,…,t, где h(0) – некоторое фиксированное значение, называемое инициализационным вектором (initialization vector, initial value, IV). Значением итерационной функции хэширования является значение h(t).

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

HMAC

Конструкция HMAC позволяет построить ключевую функцию хэширования на основе любой бесключевой хэш-функции. Данную конструкцию предложили в 1996 году М. Белларе (Mihir Bellare), Р. Канетти (Ran Canetti), Х. Кравчук (Hugo Krawczyk).

Ключевую хэш-функцию, построенную на основе бесключевой хэш-функции H с использованием конструкции HMAC, принято обозначать HMAC-H (например, HMAC-MD5).

Пусть K – секретный ключ, M – сообщение, подлежащее хэшированию, тогда HMAC-H (K,M) = H((K+opad)||H((K+ipad)||M)), где + – покоординатное сложение векторов по модулю 2 (операция XOR), opad, ipad – некоторые фиксированные константы.

Стойкость конструкции HMAC-H основана на криптографических свойствах хэш-функции H и длине используемого ключа. Конструкция HMAC стандартизирована организациями ANSI, IETF, ISO и NIST. Конструкция HMAC получила столь широкое применение, что само название «HMAC» стало по существу синонимом термина «ключевая хэш-функция».

Вспомогательная литература

B. Preneel, Analysis and Design of Cryptographic Hash Functions, Technical report, Katholieke Universiteit Leuven, Belgium, 2003.
А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, «Основы криптографии», Гелиос АРВ, М., 2001.
I. Damgaard, A Design Principle for Hash Functions, CRYPTO-89, 1989, pp. 416-427.
R. Merkle, One Way Hash Functions and DES, CRYPTO-89, 1989, pp. 428-446.
HMAC: Keyed-Hashing for Message Authentication, RFC 2104, February 1997.
ANSI X9.71, Keyed Hash Message Authentication Code.
NIST, FIPS PUB 198, The Keyed-Hash Message Authentication Code (HMAC), March 2002.
J. Kim, A. Biryukov, B. Preneel, S. Hong, On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1, Cryptology ePrint Archive, Report 2006/187,