Эта статья входит в число добротных статей

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-3256 и SHAvite-3512[1].

Название[править | править код]

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

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

История[править | править код]

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

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

Особенности дизайна[править | править код]

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

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

Алгоритм[править | править код]

Раунд AES[править | править код]

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

HAIFA[править | править код]

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

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

Дополнение сообщения[править | править код]

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

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

Разновидности алгоритма[править | править код]

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

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

Генерация дайджеста[править | править код]

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

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

Функции и [править | править код]

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

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

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

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

Функция [править | править код]

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

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

Функция [править | править код]

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

Генерация ключей для [править | править код]

Для вычисления функции требуется по три 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[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 варианта — наличие операций побитового отрицания «~» счетчика. Отрицание было добавлено, чтобы увеличить криптографическую стойкость хеш-функции. Наличие таких операций дает гарантию, что по крайней мере 4 из 8 байт счетчика будут ненулевыми[2].

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

Функция [править | править код]

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

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

Функция [править | править код]

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

Генерация ключей для [править | править код]

Для вычисления функции требуется по восемь 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[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 байт счетчика будут ненулевыми[2].

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

Быстродействие[править | править код]

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

Алгоритм Скорость (тактов/байт)
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 года, быстродействие на настоящий момент может оказаться лучше[1].

Примечания[править | править код]

  1. 1 2 3 4 5 6 7 8 9 Eli Biham, Orr Dunkelman. The SHAvite-3 Hash Function. cs.technion.ac.il. Computer Science Department, Technion (31 октября 2008).
  2. 1 2 3 4 Eli Biham, Orr Dunkelman. The SHAvite-3 Hash Function. Tweaked Version. cs.technion.ac.il. Computer Science Department, Technion (23 ноября 2009).
  3. Richard F. Kayser Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family (англ.) // Federal Register. — 2007. — 2 November (vol. 72, no. 212). — P. 62212—62220. — ISSN 0097-6326.
  4. Thomas Peyrin. Сообщение в рассылке NIST о найденной уязвимости. NIST mailing list. NIST Computer Security Resource Center (19 января 2009).
  5. Paul Souradyuti. OFFICIAL COMMENT: SHAvite-3. NIST mailing list. NIST Computer Security Resource Center (16 июня 2009).
  6. 1 2 Eli Biham, Orr Dunkelman. Updates on SHAvite-3. cs.technion.ac.il. Computer Science Department, Technion (23 августа 2010).
  7. Mridul Nandi, Souradyuti Paul. Сообщение в рассылке NIST о найденной уязвимости. NIST mailing list. NIST Computer Security Resource Center (18 июня 2009).
  8. Gauravaram P., Leurent G., Mendel F. et al. Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3-512 // Progress in Cryptology — AFRICACRYPT 2010: Third International Conference on Cryptology in Africa, Stellenbosch, South Africa, May 3-6, 2010. Proceedings / D. J. Bernstein, T. LangeSpringer Berlin Heidelberg, 2010. — P. 419–436. — (Lecture Notes in Computer Science; Vol. 6055) — ISBN 978-3-642-12677-2 — ISSN 0302-9743doi:10.1007/978-3-642-12678-9_25
  9. Bouillaguet C., Dunkelman O., Leurent G. et al. Attacks on Hash Functions Based on Generalized Feistel: Application to Reduced-Round Lesamnta and SHAvite-3₅₁₂ // Selected Areas in Cryptography: 17th International Workshop, SAC 2010, Waterloo, Ontario, Canada, August 12-13, 2010, Revised Selected Papers / A. Biryukov, G. Gong, D. R. StinsonSpringer-Verlag Berlin Heidelberg, 2011. — P. 18–35. — 411 p. — (Lecture Notes in Computer Science; Vol. 6544) — ISBN 978-3-642-19573-0 — ISSN 0302-9743doi:10.1007/978-3-642-19574-7
  10. Meltem Sönmez Turan et al. Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition. csrc.nist.gov. NIST Computer Security Resource Center (2011).

Ссылки[править | править код]