SHAvite-3

SHAvite-3
Разработчики	Эли Бихам, Ор Дункельман
Создан	2008
Опубликован	2009
Размер хеша	переменный, до 512 бит
Число раундов	12 или 16
Тип	хеш-функция

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

Название

Название функции SHAvite-3 произносится как «шавайт шалош» (ивр. шавайт три‎). Авторы назвали её так по следующим причинам:

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

История

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

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

Особенности дизайна

Особенностями хеш-функции SHAvite-3 являются:

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

Алгоритм

Раунд AES

Основная статья: Advanced Encryption Standard

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

$$AESRound_{subkey}(x)=MC(SR(SB(x)))\oplus subkey$$

HAIFA

Основная статья: HAIFA

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

1. Дополнения сообщения $M$ до некоторой длины, чтобы его можно было разбить на блоки равного размера. Обозначим дополненное сообщение $PM$;
2. Разбиения дополненного сообщение на $l$ равных по размеру блоков: $PM=(M_{1},M_{2},...,M_{l})$;
3. Взятия некоторого начальное значения $h_{0}=C(MIV,m,0,0)$, где $MIV$ — главное начальное значение, $m$ — желаемый размер дайджеста;
4. Вычисления последующего значения согласно формуле $h_{i}=C(h_{i-1},M_{i},numBits,salt)$, где $numBits$ — число захешированных к моменту вычисления $h_{i}$ бит сообщения, включая текущий блок. Иначе говоря $numBits$ — длина $(M_{1},M_{2},...,M_{i})$. Параметр $salt$ — соль. В приложениях, где использование соли не требуется, авторы SHAvite-3 предлагают использовать $salt=0$, допуская при этом снижение безопасности и увеличение скорости вычислений;
5. Сокращения конечного значения $h_{l}$ до требуемой длины $m$, это и будет результатом вычисления хеш-функции.

Дополнение сообщения

Если размер исходного сообщения — $A$, желаемый размер значения хеш-функции — $B$, а размер блока, с которым работает функция сжатия $C$, равен $n$, то дополнение сообщения $M$, которое имеет длину $len(M)$, до длины кратной $n$ выполняется в следующем порядке:

1. К сообщению $M$ приписывается в конец один бит со значением 1, получаем $(M,1)$;
2. Приписывается значение $A$, которое кодируется $a$ битами: $(M,1,A)$;
3. Приписывается значение $B$, которое кодируется $b$ битами: $(M,1,A,B)$;
4. После бита 1 вставляется минимальное количество нулей, которое необходимо для того, чтобы длина полученного сообщения $PM$ стала кратна $n$: $PM=(M,1,0,...,0,A,B)$. Количество нулей можно вычислить по формуле: $z=n-(len(M)+1+a+b)\ mod\ n$.

Разновидности алгоритма

Алгоритм SHAvite-3 имеет две разновидности, различающиеся используемой функцией сжатия $C$ и длиной дайджеста:

• SHAvite-3₂₅₆ использует функцию сжатия $C_{256}$ и позволяет получить хеш длиной до 256 бит;
• SHAvite-3₅₁₂ использует функцию сжатия $C_{512}$ и позволяет получить хеш длиной от 257 до 512 бит.

Генерация дайджеста

Если исходное сообщение — $M$, и требуется получить дайджест длиной $1\leq m\leq 512$, выполним следующую последовательность действий:

1. Определим $w$. Назовем первым случаем $1\leq m\leq 256$, а вторым — $256<m\leq 512$. В первом случае $w=256$, во втором — $w=512$.
2. Найдём $h_{0}=C_{w}(MIV_{w},m,0,0)$, где $MIV_{w}=C_{w}(0,0,0,0)$;
3. Дополним сообщение до размера, кратного $n$=512 в первом случае или до $n$=1024 — во втором. Для этого воспользуемся процедурой, описанной ранее, считая $a$=64 в первом случае и $a$=128 — во втором. При этом в обоих случаях $b$=16;
4. Разобьём дополненное сообщение $MP$ на блоки по $n$ бит и вычислим все $h_{i}$, за исключением последних двух. Если длина исходного сообщения такова, что в результате дополнения сообщения в конце образовался блок, который не содержит ни одного бита исходного сообщения, то $h_{l-1}=C_{w}(h_{l-2},M_{l-1},len(M),salt)$,$h_{l}=C_{w}(h_{l-1},M_{l},0,salt)$. В противном случае, $h_{l-1}$ вычисляется по тем же формулам, что и предыдущие $h_{i}$, а $h_{l}=C_{w}(h_{l-1},M_{l},0,salt)$;
5. Возьмём первые $m$ бит $h_{l}$. Это и есть требуемое значение хеш-функции.

Функции $C_{256}$ и $C_{512}$

Принимают на вход четыре битовых вектора:

• Цепное значение (chaining value) с размером $m_{c}$=256 бит для $C_{256}$ ($m_{c}=512$ бит для $C_{512}$);
• Блок сообщения с размером $n$=512 бит для $C_{256}$ ($n$=1024 бита для $C_{512}$);
• Соль с размером $s$=256 бит для $C_{256}$ ($s$=512 бит для $C_{512}$);
• Битовый счетчик с размером $b$=64 бита для $C_{256}$ ($b$=128 бит для $C_{512}$).

На выходе получается вектор с размером 256 бит для $C_{256}$ (512 бит для $C_{512}$).

Для реализации $C_{256}$ и $C_{512}$ используется конструкция Дэвиса-Мейера. Это значит, что цепное значение пересчитывается по формулам $h_{i}=E^{256}{(h_{i-1})}\oplus {h_{i-1}}$ и $h_{i}=E^{512}{(h_{i-1})}\oplus {h_{i-1}}$ соответственно.

Функция $E^{256}$

$E^{256}$ — 12-раундовый блочный шифр. Данный блочный шифр является сетью Фейстеля, которая состоит из 12 ячеек Фейстеля. $E^{256}$ принимает на вход 256-битный открытый текст $P$. Его можно разделить на две части $L_{0}$ и $R_{0}$ по 128 бит. $P=(L_{0},R_{0})$. Пересчёт значений на каждом раунде производится по формуле: $(L_{i+1},R_{i+1})=(R_{i},L_{i}\oplus F_{RK_{i}}^{3}(R_{i}))$.

Здесь $RK_{i}=(k_{i}^{0},k_{i}^{1},k_{i}^{2})$ — вектор из трех ключей, различный для каждого раунда, а $F^{3}$ — некая функция. В результате может быть вычислено возвращаемое значение: $E^{256}=(L_{12},R_{12})$.

Функция $F_{k}^{3}$

Функция $F_{k}^{3}(x)$ принимает на вход 128-битный текст $x$ и 384-битный ключ $k$, который получается объединением трех 128-битных ключей $k=(k^{0},k^{1},k^{2})$. Она заключается в троекратном применении раунда AES: $F_{(k_{i}^{0},k_{i}^{1},k_{i}^{2})}^{3}(x)=AESRound_{0}(AESRound_{k_{i}^{2}}(AESRound_{k_{i}^{1}}(x\oplus k_{i}^{0})))$. Входной вектор $x$ складывается по модулю 2 с ключом $k_{i}^{0}$, к результату применяются три раунда AES с разными ключами в следующем порядке: раунд AES с ключом $k_{i}^{1}$, ещё один раунд AES с ключом $k_{i}^{2}$, последний раунд с ключом 0 (128 бит).

Генерация ключей для $E^{256}$

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

• $msg[0],...,msg[15]$ — блок сообщения;
• $cnt[0],cnt[1]$ — битовый счетчик;
• $salt[0],...,salt[7]$ — соль.

В результате работы алгоритма получаем 144 значения (также 4-байтных):

• $rk[0],...,rk[143]$

// Алгоритм генерации ключей для 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[4];
    // Нелинейный шаг
    for (int r = 0; r < 2; r++) {
        // Выполнить раунд AES с ключем 0 над 128-битным значением,
        // которое является суммой по модулю 2 ранее вычисленных элеменов 
        // массива rk и соли (0-127 биты).
        // 128-битный результат записать в массив t
        AESRound0(
            rk[i-15]^salt[0], rg[i-14]^salt[1], rk[i-13]^salt[2], rk[i-16]^salt[3], 
            &t[0], &t[1], &t[2], &t[3]
        );
        for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4];
        if (i == 16) { rk[16] ^= cnt[0]; rk[17] ^= ~cnt[1]; }
        if (i == 56) { rk[16] ^= cnt[1]; rk[17] ^= ~cnt[0]; }
        i += 4;
        // Такой же раунд AES, как и ранее, 
        // но с оставшейся частью соли (128-255 биты)
        AESRound0(
            rk[i-15]^salt[4], rg[i-14]^salt[5], rk[i-13]^salt[6], rk[i-16]^salt[7], 
            &t[0], &t[1], &t[2], &t[3]
        );
        for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4];
        if (i == 84) { rk[86] ^= cnt[1]; rk[87] ^= ~cnt[0]; }
        if (i == 124) { rk[124] ^= cnt[0]; rk[127] ^= ~cnt[1]; }
        i += 4;
    }
    // Линейный шаг
    for (int r = 0; r != 16; ++r) {
        rk[i] = rk[i-16] ^ rk[i-3];
        i += 1;
    }
}

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

Ключи $RK_{i}=(k_{i}^{0},k_{i}^{1},k_{i}^{2})$ для вычисления функции $E^{256}$ получаются из $rk[0],...,rk[143]$ следующим образом:$k_{i}^{j}=(rk[y_{i}^{j}],rk[y_{i}^{j}+1],rk[y_{i}^{j}+2],rk[y_{i}^{j}+3])$, где $y_{i}^{j}=12*i+4*j$, $i\in [0,12),j\in [0,2)$.

Функция $E^{512}$

Данная функция реализована по аналогии с $E^{256}$, но принимает на вход 512-битный открытый текст $P$, который представляется в виде 4 частей по

128 бит: $P=(L_{0},A_{0},B_{0},R_{0})$. Пересчет выполняется по формуле $(L_{i+1},A_{i+1},B_{i+1},R_{i+1})=(R_{i},L_{i}\oplus F_{RK_{0,i}}^{4}(A_{i}),A_{i},B_{i}\oplus F_{RK_{1,i}}^{4}(R_{i}))$ за 14 раундов (в обновленной версии авторы предложили использовать 16 раундов). $E^{512}=(L_{14},A_{14},B_{14},R_{14})$.

Функция $F_{k}^{4}$

Принимает на вход 128 бит текста $x$ и 512-битный ключ $k=(k^{0},k^{1},k^{2},k^{3})$. Вычисляется как 4 раунда AES. $F_{(k_{i}^{0},k_{i}^{1},k_{i}^{2},k_{i}^{3})}^{4}(x)=AESRound_{0}(AESRound_{k_{i}^{3}}(AESRound_{k_{i}^{2}}(AESRound_{k_{i}^{1}}(x\oplus k_{i}^{0}))))$.

Генерация ключей для $E^{512}$

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

• $msg[0],...,msg[31]$ — блок сообщения
• $cnt[0],...,cnt[3]$ — битовый счетчик
• $salt[0],...,salt[15]$ — соль

В результате работы алгоритма получаем 448 значений (4-байтных):

• $rk[0],...,rk[447]$

// Алгоритм генерации ключей для 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[4];
    // Нелинейный шаг (7 раз)
    for (int r = 0; r < 2; r++) {
        AESRound0(
            rk[i-31]^salt[0], rg[i-30]^salt[1], rk[i-29]^salt[2], rk[i-32]^salt[3], 
            &t[0], &t[1], &t[2], &t[3]); // Раунд AES с ключем 0, соль 0-3
        for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4];
        if (i == 32) { rk[32] ^= cnt[0]; rk[33] ^= cnt[1]; 
                       rk[34]^= cnt[2]; rk[35] ^= ~cnt[3]; }
        i += 4;
        AESRound0(
            rk[i-31]^salt[4], rg[i-30]^salt[5], rk[i-29]^salt[6], rk[i-32]^salt[7], 
            &t[0], &t[1], &t[2], &t[3]); // Раунд AES с ключем 0, соль 4-7
        for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4];
        if (i == 164) { rk[164] ^= cnt[3]; rk[165] ^= cnt[2];
                        rk[166] ^= cnt[1]; rk[167] ^= ~cnt[0]; }
        i += 4;
        AESRound0(
            rk[i-31]^salt[8], rg[i-30]^salt[9], rk[i-29]^salt[10], rk[i-32]^salt[11], 
            &t[0], &t[1], &t[2], &t[3]); // Раунд AES с ключем 0, соль 8-11
        for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4];
        if (i == 440) { rk[440] ^= cnt[1]; rk[441] ^= cnt[0]; 
                        rk[442]^= cnt[3]; rk[443] ^= ~cnt[2]; }
        i += 4;
        AESRound0(
            rk[i-31]^salt[12], rg[i-30]^salt[13], rk[i-29]^salt[14], rk[i-32]^salt[15], 
            &t[0], &t[1], &t[2], &t[3]); // Раунд AES с ключем 0, соль 12-15
        for (int j = 0; j < 4; j++) rk[i+j] = t[j] ^ rk[i+j-4];
        if (i == 316) { rk[316] ^= cnt[2]; rk[317] ^= cnt[3];
                        rk[318] ^= cnt[0]; rk[319] ^= ~cnt[1]; }
        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;
    }
}

Здесь, как и в 256-битной версии, единственное отличие улучшенной версии от первоначально отправленной на конкурс SHA-3 — наличие операций побитового НЕ «~» перед значениями счетчика. Наличие таких операций дает гарантию, что по крайней мере 4 из 16 байт счетчика $(cnt[0],cnt[1],cnt[2],cnt[3])$ будут ненулевыми.

Далее ключи $RK_{p,i}=(k_{p,i}^{0},k_{p,i}^{1},k_{p,i}^{2},k_{p,i}^{3})$ для вычисления функции $E^{512}$ получаются из $rk[0],...,rk[447]$ следующим образом:$k_{p,i}^{j}=(rk[y_{p,i}^{j}],rk[y_{p,i}^{j}+1],rk[y_{p,i}^{j}+2],rk[y_{p,i}^{j}+3])$, где $y_{p,i}^{j}=32*i+16*p+4*j$, $i\in [0,14),p\in [0,2),j\in [0,4)$.

Быстродействие

В таблице представлены сравнительные данные скорости действия алгоритмов.

Алгоритм	Скорость (тактов/байт)
	32 бит	64 бит
MD5	7.4	8.8
SHA-1	9.8	9.5
SHA-256	28.8	25.3
SHA-512	77.8	16.9
SHAvite-3256 (изм.)	35.3	26.7
SHAvite-3256 (приб.)	26.6	18.6
SHAvite-3256 (c инстр. AES)	< 8	< 8
SHAvite-3512 (изм.)	55.0	38.2
SHAvite-3512 (приб.)	35.3	28.4
SHAvite-3512 (c инстр. AES)	< 12	< 12

Функция также может быть реализована аппаратно.

Длина	Технология	Размер	Пропускная способность
256	ASIC	10.3 Kgates	7.6 Mbps
		55.0 Kgates	604.4 Mbps
	FPGA	510 Slices	1.7 Mbps
		3585 Slice	872.3 Mbps
512	ASIC	18.5 Kgates	4.7 Mbps
		81 Kgates	907.7 Mbps
	FPGA	895 Slices	1.0 Mbps
		7170 Slices	1.12 Gbps

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

Ссылки

• Eli Biham, Orr Dunkelman. Официальная страница SHAvite-3. Архивная копия от 12 ноября 2013 на Wayback Machine (англ.) cs.technion.ac.il. Computer Science Department, Technion (проверено 09.12.2016)
• Eli Biham, Orr Dunkelman. Спецификация SHAvite-3 (Первоначальная версия) Архивная копия от 27 ноября 2020 на Wayback Machine (англ.) cs.technion.ac.il. Computer Science Department, Technion (опубликовано 01.02.2009, проверено 09.12.2016)
• Eli Biham, Orr Dunkelman. Спецификация SHAvite-3 (Улучшенная версия) Архивная копия от 23 сентября 2015 на Wayback Machine (англ.) cs.technion.ac.il. Computer Science Department, Technion (опубликовано 23.11.09, проверено 09.12.2016)
• Eli Biham, Orr Dunkelman. Обновления SHAvite-3 Архивная копия от 23 сентября 2015 на Wayback Machine (англ.) cs.technion.ac.il. Computer Science Department, Technion (опубликовано 23.08.2010, проверено 09.12.2016)
• Сайт NIST. Конкурс на алгоритм SHA-3 Архивная копия от 5 мая 2010 на Wayback Machine (англ.) csrc.nist.gov. NIST Computer Security Resource Center. (обновлено 14.09.2016, проверено 09.12.2016)
• Regenscheid A. et al. Результат первого раунда конкурса на алгоритм SHA-3 Архивная копия от 29 декабря 2009 на Wayback Machine (англ.) csrc.nist.gov. NIST Computer Security Resource Center. (опубликовано 2009, проверено 09.12.2016)
• Turan M. S. et al. Результат второго раунда конкурса на алгоритм SHA-3 Архивная копия от 15 февраля 2013 на Wayback Machine (англ.) csrc.nist.gov. NIST Computer Security Resource Center. (опубликовано 2011, проверено 09.12.2016)