SHAvite-3 — криптографическая хеш-функция, разработанная израильскими криптографами Эли Бихамом () и Ором Дункельманом (). Одна из четырнадцати участников второго раунда конкурса SHA-3, организованного NIST. SHAvite-3 основана на сочетании компонентов AES c фреймворком HAIFA. Данная хеш-функция использует такие криптографические примитивы, как сеть Фейстеля и конструкцию Девиса-Мейера. Семейство хеш-функций SHAvite-3 включает в себя два алгоритма — SHAvite-3256 и SHAvite-3512.

Название Название функции SHAvite-3 произносится как «шавайт шалош» (). Авторы назвали её так по следующим причинам: Shavit переводится с иврита как комета — разработанная хеш-функция является защищённой и быстрой (); Shavite — последователь Шивы — индусского божества; цифра 3 в названии — существовали две предыдущие версии, которые не были опубликованы.

История Алгоритм SHAvite-3 был специально разработан для участия в конкурсе SHA-3. В числе требований, предъявляемых к хеш-функции, была возможность получения дайджестов длиной 224, 256, 384 и 512 бит для замены семейства криптографических алгоритмов SHA-2. Авторы SHAvite-3 разработали две функции: SHAvite-3256 для генерации дайджеста длиной 224, 256 бит и SHAvite-3512 для генерации дайджеста длиной 384 и 512 бит. По результатам первого раунда конкурса была обнаружена уязвимость лежащего в основе алгоритма блочного шифра, которая, однако, не привела к компрометации хеш-функции.

Авторами была предложена модификация к первоначально заявленной на конкурс версии, чтобы повысить защищенность алгоритма. Изменение было названо улучшенной (tweaked) версией и касалось обоих алгоритмов SHAvite-3256 и SHAvite-3512. После этого последовало исправление ошибки в реализации раундовой функции AES и улучшена криптостойкость SHAvite-3512 путём увеличения количества раундов с 14 до 16. Функция дошла до второго раунда конкурса криптографических функций, но до финала не была допущена за недостаточную защищённость инициализации S-блоков, лежащих в основе блочного шифра, что приводило к относительно низкому уровню безопасности 512-разрядной версии . В то же время, хеш-функция имела относительно низкие показатели пропускной способности.

Особенности дизайна Особенностями хеш-функции SHAvite-3 являются: итерации функций сжатия для получения хеш-функции производятся с помощью алгоритма HAIFA; алгоритм позволяет получить хеш произвольной длины, не превышающий 512 бит; поддерживает соли; функция сжатия разработана с использованием известных и хорошо изученных компонент: сети Фейстеля, раундовых функций AES и регистров сдвига с линейной обратной связью.

Алгоритм

Раунд AES

В своей основе SHAvite-3 использует раунд AES. Раунд определяет операции над 128 битным числом . Данные 128 бит разбиваются на 16 блоков по 8 бит, после чего блоки записываются в виде матрицы размера 4×4. Каждый элемент матрицы представляет значение в поле GF(28). Раунд состоит из последовательного применения операций SubBytes (), ShiftRows (), MixColumns () и сложения по модулю 2 с раундовым ключом .

HAIFA

SHAvite-3 построен на режиме итераций для хеш-функций HAIFA. HAIFA задает правила, по которым выполняется дополнение сообщения до нужной длины, его сжатие со специальной функцией и сокращение полученного на выходе значения до требуемой длины. Таким образом, вычисление хеш-функции по алгоритму SHAvite-3 заключается в выполнении последовательно нескольких шагов: Дополнения сообщения до некоторой длины, чтобы его можно было разбить на блоки равного размера. Обозначим дополненное сообщение ; Разбиения дополненного сообщение на равных по размеру блоков: ; Взятия некоторого начальное значения , где  — главное начальное значение,  — желаемый размер дайджеста; Вычисления последующего значения согласно формуле , где  — число захешированных к моменту вычисления бит сообщения, включая текущий блок. Иначе говоря  — длина . Параметр  — соль. В приложениях, где использование соли не требуется, авторы SHAvite-3 предлагают использовать , допуская при этом снижение безопасности и увеличение скорости вычислений; Сокращения конечного значения до требуемой длины , это и будет результатом вычисления хеш-функции.

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

Разновидности алгоритма Алгоритм SHAvite-3 имеет две разновидности, различающиеся используемой функцией сжатия и длиной дайджеста: SHAvite-3256 использует функцию сжатия и позволяет получить хеш длиной до 256 бит; SHAvite-3512 использует функцию сжатия и позволяет получить хеш длиной от 257 до 512 бит.

Генерация дайджеста Если исходное сообщение — , и требуется получить дайджест длиной , выполним следующую последовательность действий: Определим . Назовем первым случаем , а вторым — . В первом случае , во втором — . Найдём , где ; Дополним сообщение до размера, кратного =512 в первом случае или до =1024 — во втором. Для этого воспользуемся процедурой, описанной ранее, считая =64 в первом случае и =128 — во втором. При этом в обоих случаях =16; Разобьём дополненное сообщение на блоки по бит и вычислим все , за исключением последних двух. Если длина исходного сообщения такова, что в результате дополнения сообщения в конце образовался блок, который не содержит ни одного бита исходного сообщения, то ,. В противном случае, вычисляется по тем же формулам, что и предыдущие , а ; Возьмём первые бит . Это и есть требуемое значение хеш-функции.

Функции C256 и C512 Принимают на вход четыре битовых вектора: Цепное значение (chaining value) с размером =256 бит для ( бит для ); Блок сообщения с размером =512 бит для (=1024 бита для ); Соль с размером =256 бит для (=512 бит для ); Битовый счетчик с размером =64 бита для (=128 бит для ). На выходе получается вектор с размером 256 бит для (512 бит для ).

Для реализации и используется конструкция Дэвиса-Мейера. Это значит, что цепное значение пересчитывается по формулам и соответственно.

Функция E256  — 12-раундовый блочный шифр. Данный блочный шифр является сетью Фейстеля, которая состоит из 12 ячеек Фейстеля. принимает на вход 256-битный открытый текст . Его можно разделить на две части и по 128 бит. . Пересчёт значений на каждом раунде производится по формуле: .

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

Функция F3k Функция принимает на вход 128-битный текст и 384-битный ключ , который получается объединением трех 128-битных ключей . Она заключается в троекратном применении раунда AES: . Входной вектор складывается по модулю 2 с ключом , к результату применяются три раунда AES с разными ключами в следующем порядке: раунд AES с ключом , ещё один раунд AES с ключом , последний раунд с ключом 0 (128 бит).

Генерация ключей для E256 Для вычисления функции требуется по три 128-битных ключа в каждом из 12 раундов. Для этого используется из одного ключа. В качестве единственного ключа, из которого впоследствии будут созданы 36, используется совокупность блока сообщения (512 бит), соли (256 бит) и битового счетчика (64 бита). В алгоритме все операции производятся над 4-байтными значениями. Введем следующие обозначения:  — блок сообщения;  — битовый счетчик;  — соль. В результате работы алгоритма получаем 144 значения (также 4-байтных):

// Алгоритм генерации ключей для E^256 на языках C/C++

// Первые 16 значений результирующего массива // проинициализировать исходным сообщением for (int i = 0; i < 16; i++) rk[i] = msg[i]; int i = 16; for (int k = 0; k < 4; k++) { uint32_t t; // Нелинейный шаг for (int r = 0; r < 2; r++) { // Выполнить раунд AES с ключем 0 над 128-битным значением, // которое является суммой по модулю 2 ранее вычисленных элеменов // массива rk и соли (0-127 биты). // 128-битный результат записать в массив t AESRound0( rk[i-15]^salt, rg[i-14]^salt, rk[i-13]^salt, rk[i-16]^salt, &t, &t, &t, &t ); for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4]; if (i == 16) { rk ^= cnt; rk ^= ~cnt; } if (i == 56) { rk ^= cnt; rk ^= ~cnt; } i += 4; // Такой же раунд AES, как и ранее, // но с оставшейся частью соли (128-255 биты) AESRound0( rk[i-15]^salt, rg[i-14]^salt, rk[i-13]^salt, rk[i-16]^salt, &t, &t, &t, &t ); for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4]; if (i == 84) { rk ^= cnt; rk ^= ~cnt; } if (i == 124) { rk ^= cnt; rk ^= ~cnt; } i += 4;

// Линейный шаг for (int r = 0; r != 16; ++r) { rk[i] = rk[i-16] ^ rk[i-3]; i += 1;

Представленный выше алгоритм — модифицированная авторами версия. Единственное отличие от изначально отправленного на конкурс SHA-3 варианта — наличие операций побитового отрицания «~» счетчика. Отрицание было добавлено, чтобы увеличить криптографическую стойкость хеш-функции. Наличие таких операций дает гарантию, что по крайней мере 4 из 8 байт счетчика будут ненулевыми.

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

Функция E256 Данная функция реализована по аналогии с , но принимает на вход 512-битный открытый текст , который представляется в виде 4 частей по

128 бит: . Пересчет выполняется по формуле за 14 раундов (в обновленной версии авторы предложили использовать 16 раундов). .

Функция F4k Принимает на вход 128 бит текста и 512-битный ключ . Вычисляется как 4 раунда AES. .

Генерация ключей для E256 Для вычисления функции требуется по восемь 128-битных ключей в каждом из 14 раундов. Всего — 112 ключей. Они составляются на основе блока сообщения (1024 бита), соли (512 бит) и битового счетчика (128 бита). Все операции производятся над 4-байтными значениями. Введем следующие обозначения:  — блок сообщения  — битовый счетчик  — соль В результате работы алгоритма получаем 448 значений (4-байтных):

// Алгоритм генерации ключей для E^512 на языках C/C++

// Первые 32 значений результирующего массива // проинициализировать исходным сообщением for (int i = 0; i < 32; i++) rk[i] = msg[i]; int i = 32; for (int k = 0; k < 7; k++) { uint32_t t; // Нелинейный шаг (7 раз) for (int r = 0; r < 2; r++) { AESRound0( rk[i-31]^salt, rg[i-30]^salt, rk[i-29]^salt, rk[i-32]^salt, &t, &t, &t, &t); // Раунд AES с ключем 0, соль 0-3 for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4]; if (i == 32) { rk ^= cnt; rk ^= cnt; rk^= cnt; rk ^= ~cnt; } i += 4; AESRound0( rk[i-31]^salt, rg[i-30]^salt, rk[i-29]^salt, rk[i-32]^salt, &t, &t, &t, &t); // Раунд AES с ключем 0, соль 4-7 for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4]; if (i == 164) { rk ^= cnt; rk ^= cnt; rk ^= cnt; rk ^= ~cnt; } i += 4; AESRound0( rk[i-31]^salt, rg[i-30]^salt, rk[i-29]^salt, rk[i-32]^salt, &t, &t, &t, &t); // Раунд AES с ключем 0, соль 8-11 for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4]; if (i == 440) { rk ^= cnt; rk ^= cnt; rk^= cnt; rk ^= ~cnt; } i += 4; AESRound0( rk[i-31]^salt, rg[i-30]^salt, rk[i-29]^salt, rk[i-32]^salt, &t, &t, &t, &t); // Раунд AES с ключем 0, соль 12-15 for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4]; if (i == 316) { rk ^= cnt; rk ^= cnt; rk ^= cnt; rk ^= ~cnt; } i += 4;

if (k == 6) break; // не совершать 7 линейный шаг // Линейный шаг (6 раз) for (int r = 0; r != 32; ++r) { rk[i] = rk[i-32] ^ rk[i-7]; i += 1;