Алгоритм SHA-320.12.2020 22:33

Что такое хеш-функция?

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

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

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

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

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

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

Что из себя представляет SHA-3?

SHA-3 является важным криптографическим алгоритмом для обеспечения информационной безопасности, а также целостности данных в цифровых операциях. Недавние безопасные хеш-алгоритмы, включая MD5, RIPEMD, SHA-0, SHA-1 и SHA-2 устарели и были признаны восприимчивыми к атакам различного рода.

SHA-3 (Keccak) — алгоритм хеширования переменной разрядности, разработанный группой во главе с Йоаном Дайменом в 2012 году. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202. Keccak был выбран в качестве официального алгоритма для SHA-3 в 2012 году. [1] Keccak основан на конструкции Sponge (Губка), которая является новым способом проектирования хеш-функций, помимо стратегии итерационного метода Меркла — Дамгора, реализуемой в MD (x).

Алгоритмы MD (x) основаны на методе вычислений в цикле с использованием простых логических операций типа OR, XOR, AND, NOT. поэтому становится возможным построение коллизий с одинаковым, заранее выбранным префиксом. Однако, как показало время алгоритмы MD (x) перестали быть безопасными из-за программ, способных находить коллизии за сравнительно небольшое время.

Губка — это итеративная конструкция для создания функции с произвольной длиной на входе и произвольной длиной на выходе на основе преобразований перестановки.

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

1 этап: Дополнение

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

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

b = 25 * 2^l $b= state \ size$ $value\ of\ l = \{0, 1, 2, 3, 4, 5, 6\}$ $value\ of\ b = \{25, 50, 100, 200, 400, 800, 1600\}$

Для SHA-3 значение l принимается равным 6. Чем больше размер, тем выше безопасность, которую он обеспечивает. Теперь, основываясь на значении »», мы также решаем, сколько вычислительных раундов необходимо выполнить для каждой части дополненного сообщения.

rounds = 12 + 2 * l
rounds = 12 + 12 = 24 ; as l = 6
$24\ rounds\ in\ total$

Теперь мы знаем, что для SHA-3 размер состояния будет равен 1600 битам, а количество раундов вычислений — 24.

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

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

Первый и последний бит заполнения будут »1», а все биты между ними »0». После заполнения они делятся на » » частей, где $n\ * \ r$ эквивалентно длине дополненного сообщения. Математически это можно представить в следующем виде:

p = n * r ;
$p = length\ of\ message\ after\ padding$
$n = number\ of\ parts\ in\ which\ we\ divide\ 'p'$
$r =\ length\ of\ the\ rate$

2 этап: Размер состояния

Сумма значений » ' и ' ' всегда будет равна 1600, что продемонстрировано в таблице.

Теперь понятно, что длина дополненного сообщения точно кратна »» в зависимости от нужной длины хеша.( делится на блоков длины : P0,P1,…,Pn-1 )

Размер части состояния, который записывается и считывается, называется «скоростью» (англ. rate) и обозначается , а размер части, которая нетронута вводом / выводом, называется «емкостью» (англ. capacity) и обозначается .

Далее алгоритм можно условно разделить на две условные части: «впитывание» и «отжимание».

3 этап: Функция впитывания

Каждый блок дополняется нулями до строки длины бит (b=r+c) и суммируется по модулю 2 со строкой состояния аналогичной длины . Перед началом работы функции все элементы равны нулю. Для каждого следующего блока состояние — строка, полученная применением функции перестановок к результату предыдущего шага.

Рассмотрим более подробно функции перестановок. Функция перестановок, используемая в SHA-3, включает в себя исключающее «ИЛИ» (XOR), побитовое «И» (AND) и побитовое отрицание (NOT). Функция определена для строк длины-степени 2. w=2^l(l=6) →w=64 Состояние можно представить в виде трёхмерного массива размером 5×5×5 .

Тогда элемент массива A[i][j][k] будет размером (5i+j)×w+k строки состояния

Внутри функции мы выполняем один и тот же набор из пяти операций $\{θ, ρ, π, χ, ι\}$ в течение двадцати четырех раз.

На каждом шаге обозначим входной массив выходной массив :

Шаг :

Для всех и таких, что 0≤?<5,0≤?<? , положим

$C(i,k) = A[i,0,k] \oplus A[i,1,k] \oplus A[i,2,k] \oplus A[i,3,k] \oplus A[i,4,k]$

Для всех (i,j,k) таких что 0≤i<5,0≤j<5,0≤k<W :
$A'[i,j,k]=a[i,j,k]\ \oplus \ D[i,k]$

Шаг :

Для всех , таких, что $0≤k<w:\ A′[0,0,k]=A[0,0,k]$
Пусть в начале (i,j)=(1,0) . Для от 0 до 23:

Для всех таких, что $0 ≤k<w, A'[i,j,k]=A[i,j,(k-(t+1)(t+x)/2)\ mod \ w]$
$(i, j) = (j, (2i+3j)\ mod \ 5)$

Шаг :

Для всех (i,j,k) , таких, что $0≤i<5,0≤j<5,0≤k<w:\ A′[i,j,k]=A[(i+3j)\ mod\ 5,i,k]$

Шаг :

Для всех (i,j,k) , таких, что 0≤i<5,0≤j<5 ,

Шаг :

Введем дополнительную функцию rc(t) , где вход-целове число

Алгоритм rc(t) :

Если $t\ mod\ 255=0$ , то возвращается 1
Пусть
Для от 1 до 255:
1. $R = 0\ ||\ R$
Возвращается

Алгоритм :

i_r -номер раунда

Для всех , таких, что $0≤i<5, 0≤j<5, 0≤l<w:\ A'[i,j,k]=A[i,j,k]$
Пусть — массив длинны , заполненный нулями
Для от 0 до :
Для массива в стороку длины

Алгоритм перестановок:

Перевод строки в массив
Для от до $12+2l-1:\ A'=ι(χ (π(ρ(θ(A)))), i_r)$
Перевод массива в строку длины

4 этап: Функция отжимания

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

Строка длины бит возвращается в качестве результата

Криптоустойчивость SHA-3

Семейство хеш-функций Keccak было подвергнуто интенсивному криптоанализу с момента его представления на конкурс SHA-3 в 2008 [5]. В 2012 году Национальный институт стандартов и технологий США выбрал Keccak победителем конкурса SHA-3. Семейство SHA-3 состоит из четырех криптографических хэш-функций c фиксированным размером хеша и двух расширяемых выходных функций (XOFs) с именами SHAKE128 и SHAKE256, каждая из которых основана на экземпляре алгоритмов Keccak.

Подробно сосредоточимся на коллизиях семейства Keccak, то есть на поиске двух разных исходных сообщениях, дающих разное значение хеша. Лучшие предыдущие практические атаки столкновений на семейство Keccak-это Keccak -224 и KECCAK -256, уменьшенные до 4 раундов, найденных Dinur l.[3] в 2012 году и позже представлен в журнальной версии [4]. После этого теоретические результаты улучшились до 5-раундового KECCAK -256. Однако на практике количество раундов остается на уровне 4. Чтобы продвинуть криптоанализ Keccak, команда разработчиков алгоритма предложила уменьшить количество раундов в Keccak challenge [6] т.е рассматривать хеш с размером 160 для атаки с по поиску коллизий и хеш размером 80 для атаки прообраза с каждым из 4 размеров внутренних состояний (state size в 1 шаге дополнения) , уменьшенных до 12 раундов т.е. полагается равным 0 в 1 шаге дополнения. Идеальные уровни безопасности обоих алгоритмов установлены на уровне 2^80 единичных вычислений для коллизий и прообразов соответственно. Здесь количество вычислений значительно ниже, чем у основных 4 экземпляров SHA-3, однако это количество остается вне досягаемости текущего вычислительного ресурса. Теоретические результаты были найдены Dinur l. против KECCAK -256 со сложностями $2^{115}$ с использованием обобщенных внутренних дифференциалов. Насколько известно, это остается единственным результатом атаки коллизиями против SHA-3, уменьшенным до 5 раундов на сегодняшний день.

Теоретическая оценка результатов по поиску коллизий на сервере с 32 ядрами процессоров AMD. Таблица взята из источника [2]

Теперь перейдем к рассмотрению алгебраических методов для установки атак прообразов на несколько вариантов Keccak, основанных на свойствах χ шага и линейных перестановок . Атаки прообраза на SHA-3 одинаковы, за исключением того, что временная сложность может быть на 2^2 больше из-за двух дополнительных битов заполнения. В общем случае здесь мы находим прообразы сообщения длиной ≤r-2 бита, устанавливая (r−1) -й бит входного состояния равным 1, так что дополненное сообщение

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

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

Однако последние биты не могут быть выбраны, так как не предусмотрено добавления битов сообщения, поэтому допускается выбирать только «переменные» линейных структуры из первых битов r−1 . Именно поэтому стоит использовать разные линейные структуры для различных примеров.

Основная идея атак состоит в том, чтобы установить и решить линейные уравнения. Сложность в этом разделе измеряется количеством решений для линейной системы уравнений.

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

SHAKE128 (M, x) -это экземпляр стандарта SHA-3, определенного из Keccak [r=1344 , c=256] , с неограниченной выходной длиной (SHA3-X в табл 1) Рассмотрим атаку прообраза на SHAKE128 (M, 128) , обозначаемой далее SHAKE128 для простоты.

Данные взяты из источника [7]

Устанавливаем a[i, j] с =0,2 и =0,1,2,3 в качестве переменных и накладываем некоторые условия на входные биты таким образом, чтобы все выходные биты после двух раундов были линейными, как показано на рис. 10. A[0, 4] устанавливается на любую константу, такую что является исходным сообщением. Полосы серого и светло-серого цветов заданы только единицами и нулями. Чтобы убедиться, что все выходные биты после двух раундов являются линейными, потребуется:

Данные взяты из источника [7]

Все эти 6×64 линейных уравнения линейно независимы и, таким образом, имеют $2^{128}$ решений. Полагаем, что существует одно решение, соответствующее заданному 128-битному хеш-значению.

Поскольку мы имеем 64 вероятностных уравнения, общая вероятность этой системы равна $0.75^{64}=2^{-26.6}$ . Вполне можно ожидать правильного решения от $2^{26.6}$ таких систем, которое может быть получено путем изменения значений A[0,4] . Таким образом, сложность этой атаки составляет $2^{26.6}$

Заключение

В целом результаты по поиску коллизий и описанная атака прообраза показывают, что на сегодняшний день алгоритм SHA-3 / Keccak является одним из самых безопасных и эффективных алгоритмов хеширования. Некоторые утверждают, что он не будет взломан в ближайшие 20–30 лет. Развитие в мире квантовых вычислений может сократить эти временные рамки, но пока что данный алгоритм все еще один из лучших алгоритмов хеширования, который человечество имеет на данный момент.