SHAvite-3

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

Название

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

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

История

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

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

К особенностям хеш-функции SHAvite-3 относятся следующие факты:

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

Алгоритм

Раунд AES

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

В своей основе SHAvite-3 использует раунд AES. Раунд определяет операции над текстом размером 128 бит. 128 бит текста представляются в виде матрицы размера 4×4. Каждый элемент матрицы имеет размер 8 бит и представляет значение в поле 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\leq m\leq 256$, а вторым — $256<m\leq 512$. В первом случае $w=256$, во втором — $w=512$.

1. Найдем $h_{0}=C_{w}(MIV_{w},m,0,0)$, где $MIV_{w}=C_{w}(0,0,0,0)$.
2. Дополним сообщение до размера, кратного $n$=512 в первом случае или до $n$=1024 — во втором. Для этого воспользуемся процедурой, описанной ранее, считая $a$ =64 в первом случае и $a$=128 — во втором. При этом в обоих случаях $b$=16.
3. Разобьем дополненное сообщение $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)$.
4. Первые $m$ бит $h_{l}$ и есть требуемое значение хеш-функции.

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

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

• Цепное значение (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-битной версии, единственное отличие улучшенной (tweaked) версии от первоначально отправленной на конкурс 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 года, быстродействие на настоящий момент может оказаться лучше.

Ссылки

• Сайт SHAvite-3
• Спецификация SHAvite-3 (Первоначальная версия)
• Спецификация SHAvite-3 (Улучшенная версия)
• Обновления SHAvite-3
• Сайт NIST. Конкурс на алгоритм SHA-3
• Результат первого раунда конкурса на алгоритм SHA-3
• Результат второго раунда конкурса на алгоритм SHA-3