SHAvite-3

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

Название

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

• Shavit переводится с иврита как комета — разработанная хеш-функция является защищённой и быстрой (фр. vite);
• 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 битным числом x {displaystyle x} . Данные 128 бит разбиваются на 16 блоков по 8 бит, после чего блоки записываются в виде матрицы размера 4×4. Каждый элемент матрицы представляет значение в поле GF(28). Раунд состоит из последовательного применения операций SubBytes ( S B {displaystyle SB} ), ShiftRows ( S R {displaystyle SR} ), MixColumns ( M C {displaystyle MC} ) и сложения по модулю 2 с раундовым ключом s u b k e y {displaystyle subkey} .

A E S R o u n d s u b k e y ( x ) = M C ( S R ( S B ( x ) ) ) ⊕ s u b k e y {displaystyle AESRound_{subkey}(x)=MC(SR(SB(x)))oplus subkey}

HAIFA

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

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

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

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

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

• SHAvite-3256 использует функцию сжатия C 256 {displaystyle C_{256}} и позволяет получить хеш длиной до 256 бит;
• SHAvite-3512 использует функцию сжатия C 512 {displaystyle C_{512}} и позволяет получить хеш длиной от 257 до 512 бит.

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

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

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

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

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

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

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

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

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

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

Функция F k 3 ( x ) {displaystyle F_{k}^{3}(x)} принимает на вход 128-битный текст x {displaystyle x} и 384-битный ключ k {displaystyle k} , который получается объединением трех 128-битных ключей k = ( k 0 , k 1 , k 2 ) {displaystyle k=(k^{0},k^{1},k^{2})} . Она заключается в троекратном применении раунда AES: F ( k i 0 , k i 1 , k i 2 ) 3 ( x ) = A E S R o u n d 0 ( A E S R o u n d k i 2 ( A E S R o u n d k i 1 ( x ⊕ k i 0 ) ) ) {displaystyle F_{(k_{i}^{0},k_{i}^{1},k_{i}^{2})}^{3}(x)=AESRound_{0}(AESRound_{k_{i}^{2}}(AESRound_{k_{i}^{1}}(xoplus k_{i}^{0})))} . Входной вектор x {displaystyle x} складывается по модулю 2 с ключом k i 0 {displaystyle k_{i}^{0}} , к результату применяются три раунда AES с разными ключами в следующем порядке: раунд AES с ключом k i 1 {displaystyle k_{i}^{1}} , ещё один раунд AES с ключом k i 2 {displaystyle k_{i}^{2}} , последний раунд с ключом 0 (128 бит).

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

• m s g [ 0 ] , . . . , m s g [ 15 ] {displaystyle msg[0],...,msg[15]} — блок сообщения;
• c n t [ 0 ] , c n t [ 1 ] {displaystyle cnt[0],cnt[1]} — битовый счетчик;
• s a l t [ 0 ] , . . . , s a l t [ 7 ] {displaystyle salt[0],...,salt[7]} — соль.

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

• r k [ 0 ] , . . . , r k [ 143 ] {displaystyle rk[0],...,rk[143]}

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

Ключи R K i = ( k i 0 , k i 1 , k i 2 ) {displaystyle RK_{i}=(k_{i}^{0},k_{i}^{1},k_{i}^{2})} для вычисления функции E 256 {displaystyle E^{256}} получаются из r k [ 0 ] , . . . , r k [ 143 ] {displaystyle rk[0],...,rk[143]} следующим образом: k i j = ( r k [ y i j ] , r k [ y i j + 1 ] , r k [ y i j + 2 ] , r k [ y i j + 3 ] ) {displaystyle 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 {displaystyle y_{i}^{j}=12*i+4*j} , i ∈ [ 0 , 12 ) , j ∈ [ 0 , 2 ) {displaystyle iin [0,12),jin [0,2)} .

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

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

128 бит: P = ( L 0 , A 0 , B 0 , R 0 ) {displaystyle 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 ⊕ F R K 0 , i 4 ( A i ) , A i , B i ⊕ F R K 1 , i 4 ( R i ) ) {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 раундов). E 512 = ( L 14 , A 14 , B 14 , R 14 ) {displaystyle E^{512}=(L_{14},A_{14},B_{14},R_{14})} .

Принимает на вход 128 бит текста x {displaystyle x} и 512-битный ключ k = ( k 0 , k 1 , k 2 , k 3 ) {displaystyle 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 ) = A E S R o u n d 0 ( A E S R o u n d k i 3 ( A E S R o u n d k i 2 ( A E S R o u n d k i 1 ( x ⊕ k i 0 ) ) ) ) {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}}(xoplus k_{i}^{0}))))} .

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

• m s g [ 0 ] , . . . , m s g [ 31 ] {displaystyle msg[0],...,msg[31]} — блок сообщения
• c n t [ 0 ] , . . . , c n t [ 3 ] {displaystyle cnt[0],...,cnt[3]} — битовый счетчик
• s a l t [ 0 ] , . . . , s a l t [ 15 ] {displaystyle salt[0],...,salt[15]} — соль

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

• r k [ 0 ] , . . . , r k [ 447 ] {displaystyle rk[0],...,rk[447]}

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

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

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

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

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

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