SHAvite-3
—
криптографическая хеш-функция
, разработанная израильскими криптографами
Эли Бихамом
(
англ.
Eli Biham
) и Ором Дункельманом (
англ.
Orr Dunkelman
). Одна из четырнадцати участников второго раунда
конкурса SHA-3
, организованного
NIST
. SHAvite-3 основана на сочетании компонентов
AES
c фреймворком
HAIFA
. Данная хеш-функция использует такие криптографические примитивы, как
сеть Фейстеля
и
конструкцию Девиса-Мейера
. Семейство хеш-функций SHAvite-3 включает в себя два алгоритма — SHAvite-3
256
и SHAvite-3
512
.
Название
Название функции SHAvite-3 произносится как «шавайт шалош» (
ивр.
шавайт три
). Авторы назвали её так по следующим причинам
:
-
Shavit переводится с иврита как
комета
— разработанная хеш-функция является защищённой и быстрой (
фр.
vite
);
-
Shavite — последователь
Шивы
— индусского божества;
-
цифра 3 в названии — существовали две предыдущие версии, которые не были опубликованы.
История
Алгоритм SHAvite-3 был специально разработан для участия в
конкурсе SHA-3
. В числе требований, предъявляемых к хеш-функции, была возможность получения дайджестов длиной 224, 256, 384 и 512 бит для замены семейства криптографических алгоритмов
SHA-2
. Авторы SHAvite-3 разработали две функции: SHAvite-3
256
для генерации дайджеста длиной 224, 256 бит и SHAvite-3
512
для генерации дайджеста длиной 384 и 512 бит. По результатам первого раунда конкурса была обнаружена уязвимость лежащего в основе алгоритма блочного шифра, которая, однако, не привела к компрометации хеш-функции
.
Авторами была предложена модификация к первоначально заявленной на конкурс версии, чтобы повысить защищенность алгоритма. Изменение было названо улучшенной (tweaked) версией и касалось обоих алгоритмов SHAvite-3
256
и SHAvite-3
512
. После этого последовало исправление ошибки в реализации раундовой функции AES и улучшена
криптостойкость
SHAvite-3
512
путём увеличения количества раундов с 14 до 16
. Функция дошла до второго раунда конкурса криптографических функций, но до финала не была допущена за недостаточную защищённость инициализации
S-блоков
, лежащих в основе блочного шифра, что приводило к относительно низкому уровню безопасности 512-разрядной версии
. В то же время, хеш-функция имела относительно низкие показатели пропускной способности
.
Особенности дизайна
Особенностями хеш-функции SHAvite-3 являются
:
-
итерации функций сжатия для получения хеш-функции производятся с помощью алгоритма
HAIFA
;
-
алгоритм позволяет получить хеш произвольной длины, не превышающий 512 бит;
-
поддерживает
соли
;
-
функция сжатия разработана с использованием известных и хорошо изученных компонент:
сети Фейстеля
, раундовых функций
AES
и
регистров сдвига с линейной обратной связью
.
Алгоритм
Раунд AES
В своей основе SHAvite-3 использует раунд AES
. Раунд определяет операции над 128 битным числом
. Данные 128 бит разбиваются на 16 блоков по 8 бит, после чего блоки записываются в виде матрицы размера 4×4. Каждый элемент матрицы представляет значение в
поле
GF(2
8
).
Раунд состоит из последовательного применения операций SubBytes (
), ShiftRows (
), MixColumns (
) и сложения по модулю 2 с раундовым ключом
.
HAIFA
SHAvite-3 построен на режиме итераций для хеш-функций HAIFA
. HAIFA задает правила, по которым выполняется дополнение сообщения до нужной длины, его сжатие со специальной функцией
и сокращение полученного на выходе значения до требуемой длины. Таким образом, вычисление хеш-функции по алгоритму SHAvite-3 заключается в выполнении последовательно нескольких шагов:
-
Дополнения сообщения
до некоторой длины, чтобы его можно было разбить на блоки равного размера. Обозначим дополненное сообщение
;
-
Разбиения дополненного сообщение на
равных по размеру блоков:
;
-
Взятия некоторого начальное значения
, где
— главное начальное значение,
— желаемый размер дайджеста;
-
Вычисления последующего значения согласно формуле
, где
— число захешированных к моменту вычисления
бит сообщения, включая текущий блок. Иначе говоря
— длина
. Параметр
—
соль
. В приложениях, где использование соли не требуется, авторы SHAvite-3 предлагают использовать
, допуская при этом снижение безопасности и увеличение скорости вычислений
;
-
Сокращения конечного значения
до требуемой длины
, это и будет результатом вычисления хеш-функции.
Дополнение сообщения
Если размер исходного сообщения —
, желаемый размер значения хеш-функции —
, а размер блока, с которым работает функция сжатия
, равен
, то дополнение сообщения
, которое имеет длину
, до длины кратной
выполняется в следующем порядке:
-
К сообщению
приписывается в конец один бит со значением 1, получаем
;
-
Приписывается значение
, которое кодируется
битами:
;
-
Приписывается значение
, которое кодируется
битами:
;
-
После бита 1 вставляется минимальное количество нулей, которое необходимо для того, чтобы длина полученного сообщения
стала кратна
:
. Количество нулей можно вычислить по формуле:
.
Разновидности алгоритма
Алгоритм SHAvite-3 имеет две разновидности, различающиеся используемой функцией сжатия
и длиной
дайджеста
:
-
SHAvite-3
256
использует функцию сжатия
и позволяет получить хеш длиной до 256 бит;
-
SHAvite-3
512
использует функцию сжатия
и позволяет получить хеш длиной от 257 до 512 бит.
Генерация дайджеста
Если исходное сообщение —
, и требуется получить дайджест длиной
, выполним следующую последовательность действий:
-
Определим
. Назовем первым случаем
, а вторым —
. В первом случае
, во втором —
.
-
Найдём
, где
;
-
Дополним сообщение до размера, кратного
=512 в первом случае или до
=1024 — во втором. Для этого воспользуемся процедурой, описанной
считая
=64 в первом случае и
=128 — во втором. При этом в обоих случаях
=16;
-
Разобьём дополненное сообщение
на блоки по
бит и вычислим все
, за исключением последних двух. Если длина исходного сообщения такова, что в результате дополнения сообщения в конце образовался блок, который не содержит ни одного бита исходного сообщения, то
,
. В противном случае,
вычисляется по тем же формулам, что и предыдущие
, а
;
-
Возьмём первые
бит
. Это и есть требуемое значение хеш-функции.
Функции
и
Принимают на вход четыре битовых вектора:
-
Цепное значение (chaining value) с размером
=256 бит для
(
бит для
);
-
Блок сообщения с размером
=512 бит для
(
=1024 бита для
);
-
Соль
с размером
=256 бит для
(
=512 бит для
);
-
Битовый счетчик с размером
=64 бита для
(
=128 бит для
).
На выходе получается вектор с размером 256 бит для
(512 бит для
).
Для реализации
и
используется конструкция
|Дэвиса-Мейера
. Это значит, что цепное значение пересчитывается по формулам
и
соответственно
.
Функция
— 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 байт счетчика будут ненулевыми
.
Ключи
для вычисления функции
получаются из
следующим образом:
, где
,
.
Функция
Данная функция реализована по аналогии с
, но принимает на вход 512-битный открытый текст
, который представляется в виде 4 частей по
128 бит:
. Пересчет выполняется по формуле
за 14 раундов (в обновленной версии авторы предложили использовать 16 раундов
).
.
Функция
Принимает на вход 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 байт счетчика
будут ненулевыми
.
Далее ключи
для вычисления функции
получаются из
следующим образом:
, где
,
.
Быстродействие
В таблице представлены сравнительные данные скорости действия алгоритмов
.
Алгоритм
|
Скорость (тактов/байт)
|
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-3
256
(изм.)
|
35.3
|
26.7
|
SHAvite-3
256
(приб.)
|
26.6
|
18.6
|
SHAvite-3
256
(c инстр. AES)
|
< 8
|
< 8
|
SHAvite-3
512
(изм.)
|
55.0
|
38.2
|
SHAvite-3
512
(приб.)
|
35.3
|
28.4
|
SHAvite-3
512
(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.
(неопр.)
.
cs.technion.ac.il
. Computer Science Department, Technion (31 октября 2008). Дата обращения: 2 ноября 2016.
19 августа 2019 года.
-
↑
Eli Biham, Orr Dunkelman.
(неопр.)
.
cs.technion.ac.il
. Computer Science Department, Technion (23 ноября 2009). Дата обращения: 21 декабря 2013.
23 сентября 2015 года.
-
Richard F. Kayser.
(англ.)
// Federal Register. — 2007. — 2 November (
vol. 72
,
no. 212
). —
P. 62212—62220
. —
ISSN
.
31 марта 2011 года.
-
Thomas Peyrin.
(неопр.)
.
NIST mailing list
. NIST Computer Security Resource Center (19 января 2009). Дата обращения: 2 ноября 2016.
25 декабря 2016 года.
-
Paul Souradyuti.
(неопр.)
.
NIST mailing list
. NIST Computer Security Resource Center (16 июня 2009). Дата обращения: 2 ноября 2016.
19 декабря 2016 года.
-
↑
Eli Biham, Orr Dunkelman.
(неопр.)
.
cs.technion.ac.il
. Computer Science Department, Technion (23 августа 2010). Дата обращения: 21 декабря 2013.
23 сентября 2015 года.
-
Mridul Nandi, Souradyuti Paul.
(неопр.)
.
NIST mailing list
. NIST Computer Security Resource Center (18 июня 2009). Дата обращения: 2 ноября 2016.
25 декабря 2016 года.
-
,
,
,
,
,
,
(англ.)
//
:
Third International Conference on Cryptology in Africa, Stellenbosch, South Africa, May 3-6, 2010. Proceedings
/
,
— Berlin, Heidelberg, New York City, London:
, 2010. — P. 419—436. — (
; Vol. 6055) —
ISBN 978-3-642-12677-2
— ISSN
;
—
-
,
,
,
(англ.)
//
:
17th International Workshop, SAC 2010, Waterloo, Ontario, Canada, August 12-13, 2010, Revised Selected Papers
/
A. Biryukov
,
,
— Berlin, Heidelberg, New York City, London:
Springer Science+Business Media
, 2011. — P. 18—35. — 411 p. — (
; Vol. 6544) —
ISBN 978-3-642-19573-0
— ISSN
;
—
-
Meltem Sönmez Turan et al.
(неопр.)
.
csrc.nist.gov
. NIST Computer Security Resource Center (2011). Дата обращения: 21 декабря 2013.
15 февраля 2013 года.
Ссылки
-
Eli Biham, Orr Dunkelman.
от 12 ноября 2013 на
Wayback Machine
(англ.)
cs.technion.ac.il.
Computer Science Department, Technion (проверено 09.12.2016)
-
Eli Biham, Orr Dunkelman.
от 27 ноября 2020 на
Wayback Machine
(англ.)
cs.technion.ac.il.
Computer Science Department, Technion (опубликовано 01.02.2009, проверено 09.12.2016)
-
Eli Biham, Orr Dunkelman.
от 23 сентября 2015 на
Wayback Machine
(англ.)
cs.technion.ac.il.
Computer Science Department, Technion (опубликовано 23.11.09, проверено 09.12.2016)
-
Eli Biham, Orr Dunkelman.
от 23 сентября 2015 на
Wayback Machine
(англ.)
cs.technion.ac.il.
Computer Science Department, Technion (опубликовано 23.08.2010, проверено 09.12.2016)
-
от 5 мая 2010 на
Wayback Machine
(англ.)
csrc.nist.gov. NIST Computer Security Resource Center. (обновлено 14.09.2016, проверено 09.12.2016)
-
Regenscheid A. et al.
от 29 декабря 2009 на
Wayback Machine
(англ.)
csrc.nist.gov. NIST Computer Security Resource Center.
(опубликовано 2009, проверено 09.12.2016)
-
Turan M. S. et al.
от 15 февраля 2013 на
Wayback Machine
(англ.)
csrc.nist.gov. NIST Computer Security Resource Center.
(опубликовано 2011, проверено 09.12.2016)