SHAvite-3

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

Название

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

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

История

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

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

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

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

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

Алгоритм

Раунд AES

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

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

HAIFA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• ${\displaystyle 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 варианта — наличие операций побитового отрицания «~» счетчика${\displaystyle (cnt[0],cnt[1])}$. Отрицание было добавлено, чтобы увеличить криптографическую стойкость хеш-функции. Наличие таких операций дает гарантию, что по крайней мере 4 из 8 байт счетчика будут ненулевыми^[2].

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

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

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

128 бит: ${\displaystyle P=(L_{0},A_{0},B_{0},R_{0})}$. Пересчет выполняется по формуле ${\displaystyle (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 раундов^[6]). ${\displaystyle E^{512}=(L_{14},A_{14},B_{14},R_{14})}$.

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

Принимает на вход 128 бит текста ${\displaystyle x}$ и 512-битный ключ ${\displaystyle k=(k^{0},k^{1},k^{2},k^{3})}$. Вычисляется как 4 раунда AES. ${\displaystyle 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}))))}$.

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

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

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

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

• ${\displaystyle 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 байт счетчика ${\displaystyle (cnt[0],cnt[1],cnt[2],cnt[3])}$ будут ненулевыми^[2].

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

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

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

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

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

Примечания

Ссылки

• 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)