Односторонняя хэш функция это
Хэш-код создается функцией Н :
- Хэш-функция Н должна применяться к блоку данных любой длины.
- Хэш-функция Н должна создавать выход фиксированной длины.
- Н(М) относительно легко (за полиномиальное время) вычисляется для любого значения М .
- Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н(M)=h .
- Для любого данного М вычислительно невозможно найти М′ ≠ M такое, что H(M)=H(M′) .
- Вычислительно невозможно найти произвольную пару (M,M′) такую, что H(M)=H(M′) .
Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Шестое свойство защищает против класса атак, известных как атака "день рождения".
Применение хеш-функций
Рассмотрим несколько достаточно простых примеров применения хеш-функций:
• Верификация пароля
Проверка пароля обычно использует криптографические хеши. Хранение всех паролей пользователей в виде открытого текста может привести к массовому нарушению безопасности, если файл паролей будет скомпрометирован. Одним из способов уменьшения этой опасности является хранение в базе данных не самих паролей, а их хешей. При выполнении хеширования исходные пароли не могут быть восстановлены из сохраненных хеш-значений, поэтому если вы забыли свой пароль вам предложат сбросить его и придумать новый.
• Цифровая подпись
Подписываемые документы имеют различный объем, поэтому зачастую в схемах ЭП подпись ставится не на сам документ, а на его хеш. Вычисление хеша позволяет выявить малейшие изменения в документе при проверке подписи. Хеширование не входит в состав алгоритма ЭП, поэтому в схеме может быть применена любая надежная хеш-функция.
Предлагаю также рассмотреть следующий бытовой пример:
Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать решить задачу сам, но все же хотел бы быть уверенным, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш и сообщает Бобу (сохраняя решение в секрете). Затем, когда Боб сам придумает решение, Алиса может доказать, что она получила решение раньше Боба. Для этого ей нужно попросить Боба хешировать его решение и проверить, соответствует ли оно хеш-значению, которое она предоставила ему раньше.
Теперь давайте поговорим о SHA-3.
Национальный институт стандартов и технологий (NIST) в течение 2007—2012 провёл конкурс на новую криптографическую хеш-функцию, предназначенную для замены SHA-1 и SHA-2.
Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:
Способность противостоять атакам злоумышленников
• Производительность и стоимость
Вычислительная эффективность алгоритма и требования к оперативной памяти для программных реализаций, а также количество элементов для аппаратных реализаций
• Гибкость и простота дизайна
Гибкость в эффективной работе на самых разных платформах, гибкость в использовании параллелизма или расширений ISA для достижения более высокой производительности
В финальный тур попали всего 5 алгоритмов:
Победителем и новым SHA-3 стал алгоритм Keccak.
Давайте рассмотрим Keccak более подробно.
Функция перестановок
Базовая функция перестановки состоит из раундов по пять шагов:
Тета, Ро, Пи, Хи, Йота
Далее будем использовать следующие обозначения:
Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как
Обозначим результат преобразования состояния функцией перестановки
Также обозначим функцию, которая выполняет следующее соответствие:
- обычная функция трансляции, которая сопоставляет биту бит ,
где - длина слова (64 бит в нашем случае)
Я хочу вкратце описать каждый шаг функции перестановок, не вдаваясь в математические свойства каждого.
Шаг
Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и
Схематическое представление функции:
Шаг
Отображение направлено на трансляции внутри слов (вдоль оси z).
Проще всего его описать псевдокодом и схематическим рисунком:
Шаг
Шаг представляется псевдокодом и схематическим рисунком:
Шаг
Шаг является единственный нелинейным преобразованием в
Псевдокод и схематическое представление:
Шаг
Отображение состоит из сложения с раундовыми константами и направлено на нарушение симметрии. Без него все раунды были бы эквивалентными, что делало бы его подверженным атакам, использующим симметрию. По мере увеличения раундовые константы добавляют все больше и больше асимметрии.
Ниже приведена таблица раундовых констант для бит
Все шаги можно объединить вместе и тогда мы получим следующее:
Где константы являются циклическими сдвигами и задаются таблицей:
Понятие хеш-функции
Хеш-функцией (hash function) называется математическая или иная функция , которая для строки произвольной длины вычисляет некоторое целое значение или некоторую другую строку фиксированной длины. Математически это можно записать так:
Хеш-функции широко применяются в современной криптографии.
Результат ( 0110 0101(2) или 65(16) ) и будет значением хеш-функции.
Поэтому рассмотренная хеш- функция не годится для криптографических применений. В криптографии хеш- функция считается хорошей, если трудно создать два прообраза с одинаковым значением хеш-функции, а также, если у выхода функции нет явной зависимости от входа.
Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:
Создать хеш-функцию, которая удовлетворяет всем перечисленным требованиям – задача непростая. Необходимо также помнить, что на вход функции поступают данные произвольного размера, а хеш-результат не должен получаться одинаковым для данных разного размера.
где hi-1 – результат, полученный при вычислении хеш-функции для предыдущего блока входных данных.
Итоги
В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash Algorithm
Использование блочных алгоритмов шифрования для формирования хеш-функции
В качестве хеш-функции можно использовать блочный алгоритм симметричного шифрования . Если используемый блочный алгоритм криптографически стоек, то и хеш- функция на его основе будет надежной.
- практически невозможно без знания ключа шифрования вычисление хеш-значения для заданного открытого массива информации;
- практически невозможен без знания ключа шифрования подбор открытых данных под заданное значение хеш-функции.
В качестве начального хеш-кода h0 берут некоторую константу. Шифрование производится в режиме простой замены. При использовании указанного способа размер блока совпадает с длиной ключа и размером хеш-значения будет длина блока .
Во всех этих схемах длина формируемого хеш-значения равна длине блока при шифровании. Все эти, а также некоторые другие схемы использования блочного алгоритма шифрования для вычисления хеш-значений могут применяться на практике.
Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является относительно низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них – MD5 , SHA-1 , SHA -2 и ГОСТ Р 34.11-94).
Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.
Общие сведения
Криптографическая хеш-функция - это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера.
Для идеальной хеш-функции выполняются следующие условия:
Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.
Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.
На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.
Любой заинтересованный читатель задаст себе вопрос: "А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?"
Ответ таков: на выходе получим все те же 256 бит!
Дело в том, что 256 бит - это соответствий, то есть различных входов имеют свой уникальный хеш.
Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:
Надеюсь, теперь нет сомнений в том, что это очень внушительное число!
Поэтому ничего не мешает нам сопоставлять длинному входному массиву данных массив фиксированной длины.
"Парадокс дня рождения"
Так называемый "парадокс дня рождения" состоит в следующем.
Первая задача. Каким должно быть число k , чтобы для данного значения X и значений Y1, …, Yk , каждое из которых принимает значения от 1 до n, вероятность того, что хотя бы для одного Yi выполнялось равенство X=Y
Для одного значения Y вероятность того, что X=Y , равна 1/n .
Соответственно, вероятность того, что X ≠ Y , равна 1 – 1/n .
Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. (1 – 1/n) k .
Следовательно, вероятность по крайней мере одного совпадения равна
P (X = Yi) = 1 – (1 – 1/n) k
По формуле бинома Ньютона
Теперь рассмотрим вторую задачу. Обозначим P(n,k) вероятность того, что в множестве из k элементов, каждый из которых может принимать n значений, есть хотя бы два с одинаковыми значениями. Чему должно быть равно k , чтобы P(n,k) была бы больше 0,5 ?
Число различных способов выбора элементов таким образом, чтобы при этом не было дублей, равно
Всего возможных способов выбора элементов равно
Вероятность того, что дублей нет, равна
Вероятность того, что есть дубли, соответственно равна
Известно, что Если хэш-код имеет длину m бит, т.е. принимает 2 m значений, то
Подобный результат называется "парадоксом дня рождения", потому что в соответствии с приведенными выше рассуждениями для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0,5, в группе должно быть всего 23 человека. Этот результат кажется удивительным, возможно, потому, что для каждого отдельного человека вероятность того, что с его днем рождения совпадет день рождения у кого-то другого в группе, достаточно мала.
Тем не менее, возможны различного рода атаки, основанные на "парадоксе дня рождения". Возможна следующая стратегия:
Вследствие этого длина хэш-кода должна быть достаточно большой. Длина, равная 64 битам, в настоящее время не считается безопасной. Пред-почтительнее, чтобы длина составляла не менее 100 битов.
Хэш-функция должна удовлетворять целому ряду условий:
- хэш-функция должна быть чувствительна к всевозможным изменениям в тексте М, таким как вставки, выбросы, перестановки и т.п.;
- хэш-функция должна обладать свойством необратимости, то есть задача подбора документа , который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;
- вероятность того, что значения хэш-функции двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала.
Большинство хэш-функции строится на основе однонаправленной функции , аргументами, которой являются две величины: блок исходного документа и хэш-значение , предыдущего блока документа (рис.7.1): .
Часто функции хэширования строят, используя в качестве однонаправленной функции – симметричный блочный алгоритм шифрования (DES, ГОСТ 28147-89) в режиме с обратной связью, принимая последний блок шифротекста за хэш-значение всего документа. Так как длина блока в указанных алгоритмах невелика (64 бита), то часто в качестве хэш-значения используют два блока шифротекста. Одна из возможных схем хэширования на основе блочного алгоритма шифрования изображена на рис.7.2.
7.3. Алгоритм электронной цифровой подписи RSA
Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.
Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа и , затем находит их произведение и значение функции Эйлера . Далее отправитель вычисляет число из условий: , НОД и число из условий: , .
Пара чисел является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число сохраняется автором как секретный ключ для подписывания. Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис.7.3.
Недостатками алгоритма цифровой подписи RSA являются:
1. При вычислении модуля , ключей и для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение при подписании важных документов нельзя допускать такую возможность даже теоретически.
2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. , необходимо использовать при вычислениях , и целые числа не менее (или около ) каждое, что требует больших вычислительных затрат, превышающих на 20..30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.
3. Цифровая подпись RSA уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.
Тогда злоумышленник может легко вычислить подпись S3 для документа Мз, даже не зная секретного ключа
Понятие однонаправленной функции является центральным в криптографии с открытыми ключами. На основе однонаправленности построены как хэш функции, так и ассиметричные криптоалгоритмы с открытым ключем.
Однонаправленные функции относительно легко вычисляются, но обратное вычисление затруднено либо вычислительной сложностью недостижимое на существующей вычислительной технике, либо наличием неограниченного множества исходных значений x дающих зашифрованное значение.
То есть, зная x, просто рассчитать f(x), но по известному f(x) нелегко вычислить x. Здесь "нелегко" означает, что для вычисления x по f(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компьютеры мира.
Хорошим примером однонаправленной функции служит разбитая тарелка. Легко разбить тарелку на тысячу крошечных кусочков. Однако нелегко снова сложить тарелку из этих кусочков.
Это звучит красиво, но туманно и непонятно. Математически строгого доказательства существования однонаправленных функций нет, нет и реальных свидетельств возможности их построения. Несмотря на это многие функции выглядят в точности как однонаправленные: мы можем рассчитать их и, до сих пор, не знаем простого способа инвертировать их. Например, в ограниченной окрестности легко вычислить x 2 , но намного сложнее x 1/2 .
Однонаправленная функция с люком - это особый тип однонаправленной функции, с секретной лазейкой. Ее легко вычислить в одном направлении и трудно - в обратном. Но если вам известен секрет, вы можете легко рассчитать и обратную функцию. То есть, легко вычислить f(x) по заданному x, но трудно по известному f(x) вычислить x. Однако, существует небольшая секретная информация, y, позволяющая, при знании f(x) и y, легко вычислить x.
В качестве хорошего примера однонаправленной функции с люком рассмотрим часы. Легко разобрать часы на сотни малюсеньких кусочков и трудно снова собрать из этих деталей работающие часы. Но с секретной информацией - инструкцией по сборке - намного легче решить эту задачу.
Однонаправленные хэш‑функции
Хэш‑функции, долгое время использующиеся в компьютерных науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, длины (называемую значением хэш‑функции).
В качестве примера простой хэш‑функции можно рассматривать XOR всех входных байтов дающий один байт суммы.
Смысл хэш‑функции состоит в получении характерного признака прообраза - значения, по которому анализируются различные прообразы при решении обратной задачи. Так как обычно хэш‑функция представляет собой соотношение "многие к одному", невозможно со всей определенностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности.
Цифровые подписи
Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, согласия с ним. Что же так притягательно в подписи [1392]?
1. Подпись достоверна. Она убеждает получателя документа в том, что подписавший сознательно подписал документ.
2. Подпись неподдельна. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.
3. Подпись не может быть использована повторно. Она является частью документа, жулик не сможет перенести подпись на другой документ.
4. Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изменить.
5. От подписи не возможно отречься. Подпись и документ материальны. Подписавший не сможет впоследствии утверждать, что он не подписывал документ.
В действительности ни одно из этих утверждений не является полностью справедливым. Подписи можно подделать, свести с одного листа бумаги на другой, документы могут быть изменены после подписания. Однако, мы миримся с этими проблемами из-за того, что мошенничество затруднительно и может быть обнаружено.
Хотелось бы реализовать что-нибудь подобное и на компьютерах, но есть ряд проблем. Во-первых, компьютерные файлы скопировать не просто, а очень просто. Даже если подпись человека трудно подделать (например, графическое изображение рукописной подписи), можно легко вырезать правильную подпись из одного документа и вставить в другой. Простое наличие такой подписи ничего не означает. Во вторых, компьютерные файлы очень легко можно изменить после того, как они подписаны, не оставляя ни малейшего следа изменения.
Подпись документа с помощью симметричных криптосистем и посредника
Трент - это обладающий властью посредник, которому доверяют. Он может связываться и с Алисой, и с Бобом (и со всеми другими желающими подписывать цифровые документы). Он выдает секретный ключ, KA, Алисе и другой секретный ключ, KB, - Бобу. Эти ключи определяются задолго до начала действия протокола и могут быть использованы многократно для многих подписей.
Также ли это хорошо, как подпись на бумаге? Посмотрим на требуемые свойства:
4. Подписанный документ нельзя изменить. Если Боб попытается, получив документ, изменить его, Трент обнаружит мошенничество уже описанным способом.
Если Боб захочет показать Кэрол документ, подписанный Алисой, он не сможет раскрыть ей свой секретный ключ. Ему придется снова обратиться к Тренту:
(2) Трент расшифровывает полученный пакет с помощью ключа KB.
(4) Трент шифрует полученный от Боба пакет ключом KC, который он выделил для Кэрол, и посылает Кэрол шифрованный пакет.
Подпись документа с помощью криптографии с открытыми ключами
Существуют алгоритмы с открытыми ключами, которые можно использовать для цифровых подписей. В некоторых алгоритмах - примером является RSA - для шифрования может быть использован или открытый, или закрытый ключ. Зашифруйте документ своим закрытым ключом, и вы получите надежную цифровую подпись. Основной протокол прост:
(1) Алиса шифрует документ своим закрытым ключом, таким образом подписывая его.
(2) Алиса посылает подписанный документ Бобу.
(3) Боб расшифровывает документ, используя открытый ключ Алисы, таким образом проверяя подпись.
Этот протокол гораздо лучше предыдущего. Трент не нужен ни для подписи документов, ни для ее проверки. (Он нужен для подтверждения, что открытый ключ принадлежит именно Алисе.) Трент не нужен сторонам даже для разрешения споров: Если Боб не смог осуществить этап (3), то он знает, что подпись неправильна. Такая подпись соответствует всем требованиям:
2. Эта подпись неподдельна. Только Алиса знает свой закрытый ключ.
3. Эту подпись нельзя использовать повторно. Подпись является функцией документа и не может быть перенесена на другой документ.
4. Подписанный документ нельзя изменить. После любого изменения документа подпись не сможет больше подтверждаться открытым ключом Алисы.
5. От подписи невозможно отказаться. Бобу не требуется помощь Алисы при проверке ее подписи.
Подпись документа и метки времени
На самом деле, при определенных условиях Боб сможет смошенничать. Он может повторно использовать документ и подпись совместно. Это не имеет значения, если Алиса подписала контракт (одной копией подписанного контракта больше, одной меньше), но что если Алиса поставила цифровую подпись под чеком?
Предположим, что Алиса послала Бобу подписанный чек на $100. Боб отнес чек в банк, который проверил подпись и перевел деньги с одного счета на другой. Боб, выступающий в роли жулика, сохранил копию электронного чека. На следующей неделе он снова отнес его в этот или другой банк. Банк подтвердил подпись и перевел деньги с одного счета на другой. Если Алиса не проверяет свою чековую книжку, Боб сможет проделывать это годами.
Подпись документа с помощью криптографии с открытыми ключами и однонаправленных хэш-функций
На практике алгоритмы с открытыми ключами часто недостаточно эффективны для подписи больших документов. Для экономии времени протоколы цифровой подписи нередко используют вместе с однонаправленными хэш-функциями. Алиса подписывает не документ, а значение хэш-функции для данного документа. В этом протоколе однонаправленная хэш-функция и алгоритм цифровой подписи согласовываются заранее.
(1) Алиса получает значение однонаправленной хэш-функции для документа.
(2) Алиса шифрует это значение своим закрытым ключом, таким образом подписывая документ.
(3) Алиса посылает Бобу документ и подписанное значение хэш-функции.
(4) Боб получает значение однонаправленной хэш-функции для документа, присланного Алисой. Затем, используя алгоритм цифровой подписи, он расшифровывает подписанное значение хэш-функции с помощью открытого ключа Алисы. Если подписанное значение хэш-функции совпадает с рассчитанным, подпись правильна.
Скорость заметно возрастает и, так как вероятность получить для двух различных документов одинаковое 160‑битное значение хэш-функции составляет только один шанс из 2 160 , можно безопасно приравнять подпись значения хэш-функции и подпись документа. Должна использоваться только однонаправленная хэш-функция, иначе создать разные документы с одним и тем же значением хэш-функции нетрудно, и подпись одного документа приведет к ошибочной подписи сразу многих документов.
У протокола есть и другие выгоды. Во-первых, подпись может быть отделена от документа. Во-вторых, значительно уменьшаются требования к объему памяти получателя, в котором хранятся документы и подписи. Архивная система может использовать этот протокол для подтверждения существования документов, не храня их содержания. В центральной базе данных могут храниться лишь значения хэш-функции для файлов. Вовсе не нужно просматривать файлы, пользователи помещают свои значения хэш-функции в базу данных, а база данных хранит эти значения, помечая их временем получения документа. Если в будущем возникнет какое-нибудь разногласие по поводу автора и времени создания документа, база данных сможет разрешить его при помощи хранящегося в ней значения хэш‑функции. Подобная система имеет большое значение при хранении секретной информации: Алиса может подписать документ и сохранить его в секрете. Ей понадобится опубликовать документ, только если она захочет доказать свое авторство.
MD4
После первого появления алгоритма Берт ден Боер и Антон Босселаерс (Antoon Bosselaers) достигли успеха при криптоанализе последних двух из трех этапов алгоритма [202]. Ральфу Мерклу совершенно независимо удалось вскрыть первые два этапа [202]. Эли Бихам рассмотрел использование дифференциального криптоанализа против первых двух этапов MD4 [159]. Хотя все эти вскрытия не были распространены на полный алгоритм, Ривест усилил свою разработку. В результате появилась MD5.
MD5
MD5 является скомпрометированным алгоритмом и не рекомендуется к применению. С использованием мощных видеокарт подбор значений выполняется за несколько минут, при использовании радужных алгоритмов - в режиме реального времени. Однако алгоритм продолжает применяться для подсчета контрольной суммы файлов в UNIX, протоколе SSH и т.п., где криптостойкость не самый критичный фактор.
Инициализируются четыре переменных:
A = 0x01234567
B = 0x89abcdef
C = 0xfedcba98
D = 0x76543210
Они называются переменными сцепления.
Четыре переменных копируются в другие переменные: A в a, B в b, C в c и D в d.
Главный цикл состоит из четырех очень похожих этапов (у MD4 было только три этапа). На каждом этапе 16 раз используются различные операции.
Каждая операция представляет собой нелинейную функцию над тремя из a, b, c и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе.
Далее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из переменных a, b, c и d.
Наконец результат заменяет одну из переменных a, b, c и d.
См. Рис. 3.2. и Рис. 3.3. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая функция).
F(X,Y,Z) = (X Ù Y) Ú ((ØX) Ù Z)
G(X,Y,Z) = (X Ù Z) Ú (Y Ù (ØZ))
H(X,Y,Z) = X Å Y Å Z
I(X,Y,Z) = Y Å (X Ú (ØZ))
(Å - это XOR, Ù - AND, Ú - OR, а Ø - NOT.)
Рис 3.2. Главный цикл алгоритма MD5
После всего этого a, b, c и d добавляются к A, B, C и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C и D.
Аннотация: В этой лекции сформулировано понятие хеш-функции, а также приведен краткий обзор алгоритмов формирования хеш-функций. Кроме того, рассмотрена возможность использования блочных алгоритмов шифрования для формирования хеш-функции.
Цель лекции: познакомиться с понятием "хеш- функция ", а также с принципами работы таких функций.
"Парадокс дня рождения"
Так называемый "парадокс дня рождения" состоит в следующем.
Первая задача. Каким должно быть число k , чтобы для данного значения X и значений Y1, …, Yk , каждое из которых принимает значения от 1 до n, вероятность того, что хотя бы для одного Yi выполнялось равенство X=Y
Для одного значения Y вероятность того, что X=Y , равна 1/n .
Соответственно, вероятность того, что X ≠ Y , равна 1 – 1/n .
Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. (1 – 1/n) k .
Следовательно, вероятность по крайней мере одного совпадения равна
P (X = Yi) = 1 – (1 – 1/n) k
По формуле бинома Ньютона
Теперь рассмотрим вторую задачу. Обозначим P(n,k) вероятность того, что в множестве из k элементов, каждый из которых может принимать n значений, есть хотя бы два с одинаковыми значениями. Чему должно быть равно k , чтобы P(n,k) была бы больше 0,5 ?
Число различных способов выбора элементов таким образом, чтобы при этом не было дублей, равно
Всего возможных способов выбора элементов равно
Вероятность того, что дублей нет, равна
Вероятность того, что есть дубли, соответственно равна
Известно, что Если хэш-код имеет длину m бит, т.е. принимает 2 m значений, то
Подобный результат называется "парадоксом дня рождения", потому что в соответствии с приведенными выше рассуждениями для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0,5, в группе должно быть всего 23 человека. Этот результат кажется удивительным, возможно, потому, что для каждого отдельного человека вероятность того, что с его днем рождения совпадет день рождения у кого-то другого в группе, достаточно мала.
Тем не менее, возможны различного рода атаки, основанные на "парадоксе дня рождения". Возможна следующая стратегия:
Вследствие этого длина хэш-кода должна быть достаточно большой. Длина, равная 64 битам, в настоящее время не считается безопасной. Пред-почтительнее, чтобы длина составляла не менее 100 битов.
Хэш-функция должна удовлетворять целому ряду условий:
- хэш-функция должна быть чувствительна к всевозможным изменениям в тексте М, таким как вставки, выбросы, перестановки и т.п.;
- хэш-функция должна обладать свойством необратимости, то есть задача подбора документа , который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;
- вероятность того, что значения хэш-функции двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала.
Большинство хэш-функции строится на основе однонаправленной функции , аргументами, которой являются две величины: блок исходного документа и хэш-значение , предыдущего блока документа (рис.7.1): .
Часто функции хэширования строят, используя в качестве однонаправленной функции – симметричный блочный алгоритм шифрования (DES, ГОСТ 28147-89) в режиме с обратной связью, принимая последний блок шифротекста за хэш-значение всего документа. Так как длина блока в указанных алгоритмах невелика (64 бита), то часто в качестве хэш-значения используют два блока шифротекста. Одна из возможных схем хэширования на основе блочного алгоритма шифрования изображена на рис.7.2.
7.3. Алгоритм электронной цифровой подписи RSA
Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.
Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа и , затем находит их произведение и значение функции Эйлера . Далее отправитель вычисляет число из условий: , НОД и число из условий: , .
Пара чисел является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число сохраняется автором как секретный ключ для подписывания. Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис.7.3.
Недостатками алгоритма цифровой подписи RSA являются:
1. При вычислении модуля , ключей и для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение при подписании важных документов нельзя допускать такую возможность даже теоретически.
2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. , необходимо использовать при вычислениях , и целые числа не менее (или около ) каждое, что требует больших вычислительных затрат, превышающих на 20..30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.
3. Цифровая подпись RSA уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.
Тогда злоумышленник может легко вычислить подпись S3 для документа Мз, даже не зная секретного ключа
Понятие однонаправленной функции является центральным в криптографии с открытыми ключами. На основе однонаправленности построены как хэш функции, так и ассиметричные криптоалгоритмы с открытым ключем.
Однонаправленные функции относительно легко вычисляются, но обратное вычисление затруднено либо вычислительной сложностью недостижимое на существующей вычислительной технике, либо наличием неограниченного множества исходных значений x дающих зашифрованное значение.
То есть, зная x, просто рассчитать f(x), но по известному f(x) нелегко вычислить x. Здесь "нелегко" означает, что для вычисления x по f(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компьютеры мира.
Хорошим примером однонаправленной функции служит разбитая тарелка. Легко разбить тарелку на тысячу крошечных кусочков. Однако нелегко снова сложить тарелку из этих кусочков.
Это звучит красиво, но туманно и непонятно. Математически строгого доказательства существования однонаправленных функций нет, нет и реальных свидетельств возможности их построения. Несмотря на это многие функции выглядят в точности как однонаправленные: мы можем рассчитать их и, до сих пор, не знаем простого способа инвертировать их. Например, в ограниченной окрестности легко вычислить x 2 , но намного сложнее x 1/2 .
Однонаправленная функция с люком - это особый тип однонаправленной функции, с секретной лазейкой. Ее легко вычислить в одном направлении и трудно - в обратном. Но если вам известен секрет, вы можете легко рассчитать и обратную функцию. То есть, легко вычислить f(x) по заданному x, но трудно по известному f(x) вычислить x. Однако, существует небольшая секретная информация, y, позволяющая, при знании f(x) и y, легко вычислить x.
В качестве хорошего примера однонаправленной функции с люком рассмотрим часы. Легко разобрать часы на сотни малюсеньких кусочков и трудно снова собрать из этих деталей работающие часы. Но с секретной информацией - инструкцией по сборке - намного легче решить эту задачу.
Однонаправленные хэш‑функции
Хэш‑функции, долгое время использующиеся в компьютерных науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, длины (называемую значением хэш‑функции).
В качестве примера простой хэш‑функции можно рассматривать XOR всех входных байтов дающий один байт суммы.
Смысл хэш‑функции состоит в получении характерного признака прообраза - значения, по которому анализируются различные прообразы при решении обратной задачи. Так как обычно хэш‑функция представляет собой соотношение "многие к одному", невозможно со всей определенностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности.
Цифровые подписи
Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, согласия с ним. Что же так притягательно в подписи [1392]?
1. Подпись достоверна. Она убеждает получателя документа в том, что подписавший сознательно подписал документ.
2. Подпись неподдельна. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.
3. Подпись не может быть использована повторно. Она является частью документа, жулик не сможет перенести подпись на другой документ.
4. Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изменить.
5. От подписи не возможно отречься. Подпись и документ материальны. Подписавший не сможет впоследствии утверждать, что он не подписывал документ.
В действительности ни одно из этих утверждений не является полностью справедливым. Подписи можно подделать, свести с одного листа бумаги на другой, документы могут быть изменены после подписания. Однако, мы миримся с этими проблемами из-за того, что мошенничество затруднительно и может быть обнаружено.
Хотелось бы реализовать что-нибудь подобное и на компьютерах, но есть ряд проблем. Во-первых, компьютерные файлы скопировать не просто, а очень просто. Даже если подпись человека трудно подделать (например, графическое изображение рукописной подписи), можно легко вырезать правильную подпись из одного документа и вставить в другой. Простое наличие такой подписи ничего не означает. Во вторых, компьютерные файлы очень легко можно изменить после того, как они подписаны, не оставляя ни малейшего следа изменения.
Подпись документа с помощью симметричных криптосистем и посредника
Трент - это обладающий властью посредник, которому доверяют. Он может связываться и с Алисой, и с Бобом (и со всеми другими желающими подписывать цифровые документы). Он выдает секретный ключ, KA, Алисе и другой секретный ключ, KB, - Бобу. Эти ключи определяются задолго до начала действия протокола и могут быть использованы многократно для многих подписей.
Также ли это хорошо, как подпись на бумаге? Посмотрим на требуемые свойства:
4. Подписанный документ нельзя изменить. Если Боб попытается, получив документ, изменить его, Трент обнаружит мошенничество уже описанным способом.
Если Боб захочет показать Кэрол документ, подписанный Алисой, он не сможет раскрыть ей свой секретный ключ. Ему придется снова обратиться к Тренту:
(2) Трент расшифровывает полученный пакет с помощью ключа KB.
(4) Трент шифрует полученный от Боба пакет ключом KC, который он выделил для Кэрол, и посылает Кэрол шифрованный пакет.
Подпись документа с помощью криптографии с открытыми ключами
Существуют алгоритмы с открытыми ключами, которые можно использовать для цифровых подписей. В некоторых алгоритмах - примером является RSA - для шифрования может быть использован или открытый, или закрытый ключ. Зашифруйте документ своим закрытым ключом, и вы получите надежную цифровую подпись. Основной протокол прост:
(1) Алиса шифрует документ своим закрытым ключом, таким образом подписывая его.
(2) Алиса посылает подписанный документ Бобу.
(3) Боб расшифровывает документ, используя открытый ключ Алисы, таким образом проверяя подпись.
Этот протокол гораздо лучше предыдущего. Трент не нужен ни для подписи документов, ни для ее проверки. (Он нужен для подтверждения, что открытый ключ принадлежит именно Алисе.) Трент не нужен сторонам даже для разрешения споров: Если Боб не смог осуществить этап (3), то он знает, что подпись неправильна. Такая подпись соответствует всем требованиям:
2. Эта подпись неподдельна. Только Алиса знает свой закрытый ключ.
3. Эту подпись нельзя использовать повторно. Подпись является функцией документа и не может быть перенесена на другой документ.
4. Подписанный документ нельзя изменить. После любого изменения документа подпись не сможет больше подтверждаться открытым ключом Алисы.
5. От подписи невозможно отказаться. Бобу не требуется помощь Алисы при проверке ее подписи.
Подпись документа и метки времени
На самом деле, при определенных условиях Боб сможет смошенничать. Он может повторно использовать документ и подпись совместно. Это не имеет значения, если Алиса подписала контракт (одной копией подписанного контракта больше, одной меньше), но что если Алиса поставила цифровую подпись под чеком?
Предположим, что Алиса послала Бобу подписанный чек на $100. Боб отнес чек в банк, который проверил подпись и перевел деньги с одного счета на другой. Боб, выступающий в роли жулика, сохранил копию электронного чека. На следующей неделе он снова отнес его в этот или другой банк. Банк подтвердил подпись и перевел деньги с одного счета на другой. Если Алиса не проверяет свою чековую книжку, Боб сможет проделывать это годами.
Подпись документа с помощью криптографии с открытыми ключами и однонаправленных хэш-функций
На практике алгоритмы с открытыми ключами часто недостаточно эффективны для подписи больших документов. Для экономии времени протоколы цифровой подписи нередко используют вместе с однонаправленными хэш-функциями. Алиса подписывает не документ, а значение хэш-функции для данного документа. В этом протоколе однонаправленная хэш-функция и алгоритм цифровой подписи согласовываются заранее.
(1) Алиса получает значение однонаправленной хэш-функции для документа.
(2) Алиса шифрует это значение своим закрытым ключом, таким образом подписывая документ.
(3) Алиса посылает Бобу документ и подписанное значение хэш-функции.
(4) Боб получает значение однонаправленной хэш-функции для документа, присланного Алисой. Затем, используя алгоритм цифровой подписи, он расшифровывает подписанное значение хэш-функции с помощью открытого ключа Алисы. Если подписанное значение хэш-функции совпадает с рассчитанным, подпись правильна.
Скорость заметно возрастает и, так как вероятность получить для двух различных документов одинаковое 160‑битное значение хэш-функции составляет только один шанс из 2 160 , можно безопасно приравнять подпись значения хэш-функции и подпись документа. Должна использоваться только однонаправленная хэш-функция, иначе создать разные документы с одним и тем же значением хэш-функции нетрудно, и подпись одного документа приведет к ошибочной подписи сразу многих документов.
У протокола есть и другие выгоды. Во-первых, подпись может быть отделена от документа. Во-вторых, значительно уменьшаются требования к объему памяти получателя, в котором хранятся документы и подписи. Архивная система может использовать этот протокол для подтверждения существования документов, не храня их содержания. В центральной базе данных могут храниться лишь значения хэш-функции для файлов. Вовсе не нужно просматривать файлы, пользователи помещают свои значения хэш-функции в базу данных, а база данных хранит эти значения, помечая их временем получения документа. Если в будущем возникнет какое-нибудь разногласие по поводу автора и времени создания документа, база данных сможет разрешить его при помощи хранящегося в ней значения хэш‑функции. Подобная система имеет большое значение при хранении секретной информации: Алиса может подписать документ и сохранить его в секрете. Ей понадобится опубликовать документ, только если она захочет доказать свое авторство.
MD4
После первого появления алгоритма Берт ден Боер и Антон Босселаерс (Antoon Bosselaers) достигли успеха при криптоанализе последних двух из трех этапов алгоритма [202]. Ральфу Мерклу совершенно независимо удалось вскрыть первые два этапа [202]. Эли Бихам рассмотрел использование дифференциального криптоанализа против первых двух этапов MD4 [159]. Хотя все эти вскрытия не были распространены на полный алгоритм, Ривест усилил свою разработку. В результате появилась MD5.
MD5
MD5 является скомпрометированным алгоритмом и не рекомендуется к применению. С использованием мощных видеокарт подбор значений выполняется за несколько минут, при использовании радужных алгоритмов - в режиме реального времени. Однако алгоритм продолжает применяться для подсчета контрольной суммы файлов в UNIX, протоколе SSH и т.п., где криптостойкость не самый критичный фактор.
Инициализируются четыре переменных:
A = 0x01234567
B = 0x89abcdef
C = 0xfedcba98
D = 0x76543210
Они называются переменными сцепления.
Четыре переменных копируются в другие переменные: A в a, B в b, C в c и D в d.
Главный цикл состоит из четырех очень похожих этапов (у MD4 было только три этапа). На каждом этапе 16 раз используются различные операции.
Каждая операция представляет собой нелинейную функцию над тремя из a, b, c и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе.
Далее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из переменных a, b, c и d.
Наконец результат заменяет одну из переменных a, b, c и d.
См. Рис. 3.2. и Рис. 3.3. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая функция).
F(X,Y,Z) = (X Ù Y) Ú ((ØX) Ù Z)
G(X,Y,Z) = (X Ù Z) Ú (Y Ù (ØZ))
H(X,Y,Z) = X Å Y Å Z
I(X,Y,Z) = Y Å (X Ú (ØZ))
(Å - это XOR, Ù - AND, Ú - OR, а Ø - NOT.)
Рис 3.2. Главный цикл алгоритма MD5
После всего этого a, b, c и d добавляются к A, B, C и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C и D.
Аннотация: В этой лекции сформулировано понятие хеш-функции, а также приведен краткий обзор алгоритмов формирования хеш-функций. Кроме того, рассмотрена возможность использования блочных алгоритмов шифрования для формирования хеш-функции.
Цель лекции: познакомиться с понятием "хеш- функция ", а также с принципами работы таких функций.
Keccak
Хеш-функции семейства Keccak построены на основе конструкции криптографической губки, в которой данные сначала «впитываются» в губку, а затем результат Z «отжимается» из губки.
Любая губчатая функция Keccak использует одну из семи перестановок которая обозначается , где
перестановки представляют собой итерационные конструкции, состоящие из последовательности почти одинаковых раундов. Число раундов зависит от ширины перестановки и задаётся как где
В качестве стандарта SHA-3 была выбрана перестановка Keccak-f[1600], для неё количество раундов
Далее будем рассматривать
Давайте сразу введем понятие строки состояния, которая играет важную роль в алгоритме.
Строка состояния представляет собой строку длины 1600 бит, которая делится на и части, которые называются скоростью и ёмкостью состояния соотвественно.
Соотношение деления зависит от конкретного алгоритма семейства, например, для SHA3-256
В SHA-3 строка состояния S представлена в виде массива слов длины бит, всего бит. В Keccak также могут использоваться слова длины , равные меньшим степеням 2.
Алгоритм получения хеш-функции можно разделить на несколько этапов:
• Строка P делится на n блоков длины
• «Впитывание»: каждый блок дополняется нулями до строки длиной бит (b = r+c) и суммируется по модулю 2 со строкой состояния , далее результат суммирования подаётся в функцию перестановки и получается новая строка состояния , которая опять суммируется по модулю 2 с блоком и дальше опять подаётся в функцию перестановки . Перед началом работы криптографической губки все элементыравны 0.
• «Отжимание»: пока длина результата меньше чем , где - количество бит в выходном массиве хеш-функции, первых бит строки состояния добавляется к результату . После каждой такой операции к строке состояния применяется функция перестановок и данные продолжают «отжиматься» дальше, пока не будет достигнуто значение длины выходных данных .
Все сразу станет понятно, когда вы посмотрите на картинку ниже:
Функция дополнения
Свойства
Криптографическая хеш-функция должна уметь противостоять всем известным типам криптоаналитических атак.
В теоретической криптографии уровень безопасности хеш-функции определяется с использованием следующих свойств:
Pre-image resistance
Second pre-image resistance
Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что
Collision resistance
Давайте чуть более подробно поговорим о каждом из перечисленных свойств.
Несмотря на то, что хеш-функций без коллизий не существует, некоторые из них достаточно надежны и считаются устойчивыми к коллизиям.
Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что
Отсюда становится ясно, что атака по нахождению второго прообраза включает в себя поиск коллизии. Поэтому любая хеш-функция, устойчивая к коллизиям, также устойчива к атакам по поиску второго прообраза.
Неформально все эти свойства означают, что злоумышленник не сможет заменить или изменить входные данные, не меняя их хеша.
В частности, хеш-функция должна вести себя как можно более похоже на случайную функцию, оставаясь при этом детерминированной и эффективно вычислимой.
Читайте также: