Хеш-функции

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Функции сжатия
Общие сведения
Семейство MD/SHA
Криптографическая губка
Имитовставки

У Г А Т У
Общие сведения
Уфимский государственный авиационный технический университет
Криптографическая хеш-функция
[Hash], дайджест или профиль сообщения [message digest], цифровой отпечаток [digital fingerprint]
Односторонняя функция y=f(x), где x – двоичный код произвольной длины, y – двоичный код строго заданной длины
Должен обеспечиваться лавинный эффект - при незначительном изменении x, y меняется радикально
SHA3-256("The quick brown fox jumps over the lazy dog")=
69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04
SHA3-256("The quick brown fox jumps over the lazy dog.")=
a80f839cd4f83f6c3dafc87feae470045e4eb0d366397d5c6ce34ba1739f734d

У Г А Т У
Общие сведения
Уфимский государственный авиационный технический университет
Криптографическая хеш-функция
«Сильная» хэш-функция - вычислительно невозможно подобрать два аргумента, дающих одно и то же значение
«Слабая» хэш-функция – для любого заданного аргумента вычислительно невозможно подобрать другой, дающий то же значение
Хэш-функция с ключом (имитовставка, код аутентификации сообщения, Message Authentication Code, MAC) – чтобы вычислить значение, нужно знать не только аргумент, но и дополнительную информацию – ключ

У Г А Т У
Общие сведения
Уфимский государственный авиационный технический университет
Криптографическая хеш-функция
Под взломом хеш-функции подразумевается нахождение коллизий
Согласно парадоксу о днях рождения, если длина идеальной хеш-функции n и количество заданных пар аргумент-значение равно 2^(?⁄2), то вероятность наличия двух одинаковых значений равно 50%
Безопасная длина хеш-функции начинается примерно от 160 бит
«Случайный оракул» - идеальная хеш-функция
Таблица, содержащая пары аргумент-значения
При получении аргумента, система ищет его в таблице
Если он есть – выдается соответствующее значение
Если нет – оно генерируется случайным образом
Таблица должна быть единой для всех пользователей
Ни один из пользователей не имеет доступа к таблице

У Г А Т У
Общие сведения
Уфимский государственный авиационный технический университет
Функция сжатия

У Г А Т У
Общие сведения
Уфимский государственный авиационный технический университет
Функция сжатия
Особенности:
Итеративное вычисление легче реализовать
При обработке большого потока данных хеш-функцию можно вычислять на лету
Потенциальная уязвимость:
hash(IV, text_1||text_2) = hash( hash(text_1), text_2)
Защита: вместо h = hash(ОТ) вычисляется h = hash ( hash(ОТ) )

У Г А Т У
Линейка MD/SHA
Уфимский государственный авиационный технический университет
[Message Digest] – хеш-функции от Рональда Райвеста
MD2 (1989) – взломана и является устаревшей
MD4 (1990) – обнаружены уязвимости
MD5 (1991) – исправленная версия MD4, теоретически взломана, но все еще применяется
MD6 (2008) – на самостоятельное изучение
[Secure Hash Algorithm] – национальные стандарты в США
SHA-1 (1995) – разработана АНБ на основе MD4, взломана в 2014-2017
SHA-2 (2002) – расширение SHA-1 на другие длины
SHA-3/Keccak (2012/2007) – выбрана на основе конкурса SHA-3

У Г А Т У
Линейка MD/SHA
Уфимский государственный авиационный технический университет
MD4, MD5, SHA-1, SHA-2 основаны на одинаковых принципах и различаются особенностями и длиной

У Г А Т У
SHA256
Уфимский государственный авиационный технический университет
SHA-2 - по сути семейство хэш-функций, к которому относится и SHA-1
Наиболее популярна SHA-256, т. е. 256-битная
Дополнение последнего блока
Если до конца блока осталось <66 бит, создается еще один блок
К сообщению дописывается единица
В последние 64 бита последнего блока записывается число бит в исходном сообщении
Промежуток заполняется нулями
512-битный блок разбивается на 16 32-битных слов
Они расширяются до 80 32-битных слов
Каждое следующее слово определяется по формуле:
W(i) = XOR(W(i-3), W(i-8), W(i-14), W(i-16)) <<< 1

У Г А Т У
SHA256
Уфимский государственный авиационный технический университет
256-битный IV разбивается на 8 32-битных слов {a,b,c,d,e,f,g,h}
Каждое слово IV заполняется первыми 32 битами от дробной части квадратного корня одного из первых 8 простых чисел
После обработки всех блоков из этих слов составляется хеш-функция
Вычисление функции сжатия от одного блока состоит из 64 итераций
На каждой i-й итерации выполняются следующие преобразования:
a(i) = e(i) - d(i-1)) + MA(a(i-1), b(i-1), c(i-1)); // MA() – мажоритарная функция, i – номер итерации
b(i) = a(i-1); c(i) = b(i-1); d(i) = c(i-1);
e(i) = h(i-1)+W(t)+K(t)+( e(i-1)&f(i-1) OR !e(i-1)&g(i-1) ) + d(i-1) + XOR(e(i-1)>>>6, e(i-1)>>>11, e(i-1)>>>25);
f(i)=e(i-1); h(i)=f(i-1);
*мажоритарная функция – логическая функция, принимающая то же значение, что и большинство ее аргументов

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Функции сжатия
Криптографическая губка
Общие сведения
SHA-3 (Keccak)
Имитовставки

У Г А Т У
Общие сведения
Уфимский государственный авиационный технический университет
Криптографическая губка
Задана функция f(A) – псевдослучайное преобразование строки A состоящей из двух фрагментов R и С, длиной a=r+c
r – битовая скорость; с – битовая мощность
шаг 1. Хешируемый текст дополняется до целого числа блоков длиной r. Количество блоков обозначим как n, сами блоки как М1…Мn
шаг 2. Массив A заполняется нулями.
шаг 3. Заполннение губки [absorbing]. Для i=1:n
шаг 3.1 R=xor(R,Mi)
шаг 3.2 A=f(A)
шаг 4. Выжимание губки [squeezing]. Для i=1:m
шаг 4.1 A=f(A)
шаг 4.2 H(i)=R
Значением хеш-функции является H(1)…H(m)
Условие криптостойкости: мощность должна быть хотя бы вдвое больше, чем длина хеш-функции

У Г А Т У
SHA-3 (Keccak)
Уфимский государственный авиационный технический университет
Конкурс SHA-3 (2007-2012) завершился победой алгоритма Keccak
Версии функции часто обозначают Keccak-256, Keccak-512 и т.д., потому что “SHA” ассоциируется с SHA-2
А - массив 5х5 64-битных слов; изначально заполняется нулями
r и с определяются требуемой длиной хеша и необходимым условием криптостойкости
Для небольших длин хеш-функций отжатие можно не выполнять, достаточно взять нужное число бит из начала А после заполнения
Применяемые операции считаются стойкими к анализу побочных излучений шифратора
Порядок дополнения последнего блока:
если дополнить нужно 1 байт
то это байт 0х81
иначе
шаг 1. дописывается байт, состоящий из единиц.
шаг 2. в конец блока дописывается байт 0х80.
шаг 3. пространство между ними заполняется нулями

У Г А Т У
SHA-3 (Keccak)
Уфимский государственный авиационный технический университет
Преобразование f(A) – 24 раунда
На каждом выполняются операции:
\\ С(5x1), D(5x1) и В(5х5) – массивы переменных
\\ r(5x5) и RC(24x1) – массивы констант
\\ k – номер раунда
шаг 1. Для i=0…4 выполнить C[i] = xor(A[i,0], … , A[i,4])
шаг 2. Для i=0…4 выполнить D[i] = C[i-1] xor (C[i+1]>>>1)
шаг 3. Для i=0…4 для j=0…4 выполнить A[i,j] = A[i,j] xor D[i]
шаг 4. Для i=0…4 для j=0…4 выполнить B[j,2i+3j] = A[i,j] >>> r[i,j]
шаг 5. Для i=0…4 для j=0…4 выполнить A[i,j] = B[i,j] xor (~B[i+1,j] and B[i+2,j])
шаг 6. A[0,0] = A[0,0] xor RC[k-1]
Значения r[x][y]

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Функции сжатия
Криптографическая губка
Имитовставки
Имитовставки на основе блочных симметричных шифров
Имитовставка на основе бесключевых хеш-функций
Особенности применения

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

У Г А Т У
Имитовставки на основе шифров
Уфимский государственный авиационный технический университет

У Г А Т У
Имитовставки на основе шифров
Уфимский государственный авиационный технический университет
CBC-MAC:
Если размер блока больше, чем нужная длина MAC, можно использовать часть блока
Единая операция для шифрования и аутентификации позволяет сэкономить программный код или аппаратные ресурсы
Боб может генерировать сообщения с таким же MAC, как у присланного Алисой, подставляя нужные значения при расшифровке от последнего блока к первому
Если есть 2 сообщения A[1]..A[n] и B[1]..B[m] и CBC-MAC(A[1]..A[n])=T то CBC-MAC( xor(T,B[1]) || B[2]..B[M] ) = CBC-MAC( A[1]..A[n] || B[1]B[m] )
В первый блок сообщения записывается его длина и/или порядковый номер
Если Ева может подменить IV, то она может изменить первый блок без изменения СBC-MAC
Значение IV в стандарте CBC-MAC должно быть =0
В первый блок сообщения записывается его длина

У Г А Т У
Имитовставки на основе шифров
Уфимский государственный авиационный технический университет
C-MAC - Модификация CBC-MAC
Последний блок шифруется другим ключом, генерируемым на основе данных и исходного ключа в зависимости от конкретного протокола
В качестве ХФ берется не весь последний блок шифротекста, а только некоторое количество левых бит
Помимо режима CBC можно аналогичным образом использовать режим CFB
Пример – имитовставка ГОСТ28147-89

У Г А Т У
Имитовставки на основе хеш-функций
Уфимский государственный авиационный технический университет
H-MAC:
HMAC(M)=Hash( K xor O || Hash(K xor I || M) )
O, I и K – имеют ту же длину, что и хеш-функция
O и I – константы, в стандарте каждый их байт =0х5с и =0х36 соответственно
Если исходный ключ больше, чем K, то К вычисляется как хэш-функция от него
Если исходный ключ меньше, чем K, то он дополняется нулями

У Г А Т У
Имитовставки
Уфимский государственный авиационный технический университет
Особенности применения (задаются конкретным протоколом)
Имитовставка по возможности должна включать порядковый номер и направление передачи сообщения (от Алисы к Бобу, или от Боба к Алисе)
Имитовставка должна аутентифицировать не только содержание сообщения, но и его смысл
Не «20 80 753», а «температура 20 влажность 80 давление 753»
Принцип введен, чтобы избежать ошибок при переменной длине полей
Часто один и тот же текст нужно и шифровать, и аутентифицировать:
Можно добавить имитовставку, затем все вместе зашифровать
Можно зашифровать текст, затем вычислить имитовставку от ШТ
Если имитовставка не верна, можно не расшифровывать (актуально при DoS-атаках)
Злоумышленник видит пары сообщение-имитовставка
Ключи шифрования и аутентификации должны быть различны
Можно применить специальный режим шифрования с аутентификацией
Такие режимы часто запатентованы, либо не получили широкого применения