Поспелова Екатерина Викторовна

Национальный Горный Университет,Украина

Алгоритм хеширования SHA-3

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

Ввиду алгоритмической схожести SHA-2 и SHA-1, а также наличия у последней потенциальных уязвимостей, 2 ноября 2007 года Национальный Институт стандартов и технологий принимает решение о начале конкурса на новую хеш-функцию SHA-3,которая базировалась бы совершенно на ином алгоритме. Конкурс проходил в несколько раундов. 2 Октября 2012 года NIST утвердил в качестве SHA-3 алгоритм Keccak.

Keccak - алгоритм хеширования, разработанный Гвидо Бертони (Guido Bertoni), ДжоаномДейменом (Joan Daemen), Михаэлем Петерсом (Michael Peeters) и Жилем Ван Аске (Gilles Van Assche).

В основе SHA-3 лежит конструкция под названием Sponge. Данную конструкцию можно представить следующим образом:

Cхема состоит из двух этапов:

Absorbing (впитывание), в котором исходное сообщение M подвергается многораундовым перестановкам f и Squeezing(отжатие), в котором происходит вывод получившегося в результате перестановок значения Z.

Рекомендации по выбору параметров

В данном алгоритме присутствуют параметры r и c.
Хеш-функция Keccak реализована таким образом, что функцию перестановки f, применяемую для каждого блока M_i, пользователь может выбирать самостоятельно из набора предопределенных функции b={f-25, f-50, f-100, f-200, f-400, f-800, f-1600}.
Для того чтобы в пользовательской реализации использовалась функция f-800, необходимо выбрать такие r и c, чтобы выполнялось равенство r+c=800.
Кроме того, изменяя значения r и c, вы тем самым изменяете количество раундов вашей хеш-функции. Количество раундов вычисляется по формуле n=12+2l, где 2^l=(b/25). При b=1600, количество раундов n =12+2*6= 24.

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

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

SHA-224: r=1156, c=448.

SHA-256: r=1088, c=512.

SHA-384: r=832, c=768.

SHA-512: r=576, c=1024.

Процесс хеширования

На вход алгоритма подается исходное сообщение M, длина которого должна быть кратна r.При необходимости дополнить М до длины кратной r, к сообщению дописывается единичный байт 0х01, необходимое количество нулей и ко всей последовательностидобавить байт со значением 0x80.Еслиже необходимо дополнить всего один байт, то достаточно добавить байт 0x81.

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

Функция f выполняет перемешивание внутреннего состояния алгоритма.

Состояние алгоритма (обозначим его S) представляет из себя массив размером 5×5, элементами которого являются 64-битные слова, инициализированные нулевыми битами. Размер состояния составляет 1600 бит.

Функция f выполняет 24 раунда, в каждом из которых производятся следующие действия:

Также в каждом раунде выполняется сложение по модуля 2 раундовой константы RC и словаA[0, 0]. Массив RC[i] - это набор констант, которые являются предопределенными для каждогоi-гораунда:

Массив С[]представляетизсебявременный массив, аналогичный по размерности массиву состояния S.

Массивы A[] и B[] – временные массивы, содержащие 5 64-битный слов.

Массив r[] представляет собой предопределенный набор значений, в котором указывается на сколько необходимо сдвигать байты в каждом раунде. Значения всех элементов данного массива продемонстрированы в таблице ниже:

~C[x+1,y] – поразрядное дополнение к C[x+1,y].

Все операции с индексами массива выполняются по модулю 5.

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

Преимущества алгоритма

Этот алгоритм стал самым производительным на аппаратной реализации среди финалистов, а также использовал не распространенный принцип криптографической губки. Таким образом атаки, рассчитанные на предыдущие алгоритмы SHA-1 и SHA-2, не применимы к данному алгоритму. Еще одним существенным преимуществом SHA-3 является возможность его реализации на миниатюрных встраиваемых устройствах.

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

Следует отметить, что малейшее изменение исходного сообщения приводит к значительным изменениям хеш-значения благодаря такому криптографическому свойству как лавинный эффект Строка «A little body often harbours a great soul» имеет хеш-значение размером 224 бита H=2730e312ble5459a3cc23100a838a02c683a4ba926d03257e27a5a84.

При добавлении точки в конец строки «A little body often harbours a great soul.» хеш-значение H₁=e109fd01088302f20159ee5ec87239bd3bb01bf9e600f8cc81858c56.

Уязвимости алгоритма

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

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