SHA-3

SHA-3, Keccak
Разработчики Гвидо Бертони, Йоан Даймен, Микаел Питерс, Жиль Ван Аше
Создан 2008
Опубликован 2008
Предшественник SHA-2
Размер хеша 224, 256, 384, 512 (переменный, 0<d≤264-1)
Число раундов 24 (по умолчанию)
Тип хеш-функция

SHA-3 (Keccak — произносится как «кечак») — алгоритм хеширования переменной разрядности, разработанный группой авторов во главе с Йоаном Дайменом, соавтором Rijndael, автором шифров MMB, SHARK, Noekeon, SQUARE и BaseKing. 2 октября 2012 года Keccak стал победителем конкурса криптографических алгоритмов, проводимого Национальным институтом стандартов и технологий США[1]. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202[2][3]. В программной реализации авторы заявляют о 12,5 циклах на байт при выполнении на ПК с процессором Intel Core 2. Однако в аппаратных реализациях Keccak оказался намного быстрее, чем все другие финалисты.[4]

Конструкция функции губки, использованная в хеш-функции. Pi — входные блоки, Zj — выход алгоритма. Размер c («capacity») неиспользуемого для вывода набора битов должен быть значительным для достижения устойчивости к атакам

Алгоритм SHA-3 построен по принципу криптографической губки (данная структура криптографических алгоритмов была предложена авторами алгоритма Keccak ранее)[5].

В 2004—2005 годах несколько алгоритмов хеширования были атакованы, в том числе были опубликованы серьезные атаки против алгоритма SHA-1, утвержденного Национальным институтом стандартов и технологий (NIST). В ответ NIST провел открытые семинары и 2 ноября 2007 года анонсировал конкурс на разработку нового алгоритма хеширования. 2 октября 2012 года победителем конкурса стал алгоритм Keccak и был стандартизован как новый алгоритм SHA-3[6]. 5 августа 2015 года алгоритм утвержден и опубликован в качестве стандарта FIPS 202[2][3].

Алгоритм был разработан Гвидо Бертони[англ.], Йоаном Дайменом, Жилем Ван Аше[англ.] из STMicroelectronics и Микаэлем Питерсом[англ.] из NXP[7].

Алгоритм основан на более ранних хеш-функциях Panama и RadioGatún[8]. Panama был разработан Дайменом и Крейгом Клэппом в 1998 году, RadioGatún был реализован на основе Panama Дайменом, Питерсом и Ван Аше в 2006 году[8].

В ходе конкурса конкурсантам разрешалось вносить изменения в свой алгоритм для исправления обнаруживающихся проблем. Изменения, внесенные в алгоритм Keccak[9][10]:

  • Количество раундов было увеличено с 12 + до 12 + 2
  • Padding был изменён со сложной формы на более простую, описанную ниже
  • Скорость (rate) r была увеличена до предела безопасности (ранее округлялась вниз до ближайшей степени 2)

Хеш-функции семейства SHA-3 построены на основе конструкции криптографической губки[5], в которой данные сначала «впитываются» в губку, при котором исходное сообщение подвергается многораундовым перестановкам , затем результат «отжимается» из губки. На этапе «впитывания» блоки сообщения суммируются по модулю 2 с подмножеством состояния, после чего всё состояние преобразуется с помощью функции перестановки . На этапе «отжимания» выходные блоки считываются из одного и того же подмножества состояния, изменённого функцией перестановок . Размер части состояния, который записывается и считывается, называется «скоростью» (англ. rate) и обозначается , а размер части, которая нетронута вводом / выводом, называется «ёмкостью» (англ. capacity) и обозначается .

Алгоритм получения значения хеш-функции можно разделить на несколько этапов[11]:

  • Исходное сообщение дополняется до строки длины, кратной , с помощью функции дополнения (pad-функции);
  • Строка делится на блоков длины : ;
  • «Впитывание»: каждый блок дополняется нулями до строки длины бит и суммируется по модулю 2 со строкой состояния , где  — строка длины бит ( = + ). Перед началом работы функции все элементы равны нулю. Для каждого следующего блока состояние — строка, полученная применением функции перестановок к результату предыдущего шага;
  • «Отжимание»: пока длина меньше ( — количество бит в результате хеш-функции), к добавляется первых бит состояния , после каждого прибавления к применяется функция перестановок . Затем обрезается до длины бит;
  • Строка длины бит возвращается в качестве результата.

Благодаря тому, что состояние содержит дополнительных бит, алгоритм устойчив к атаке удлинением сообщения, к которой восприимчивы алгоритмы SHA-1 и SHA-2.

В SHA-3 состояние — это массив 5 × 5 слов длиной = 64 бита, всего 5 × 5 × 64 = 1600 бит. Также в Keccak могут использоваться длины , равные меньшим степеням 2 (от = 1 до = 32).

Дополнение

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

Для того, чтобы исходное сообщение M можно было разделить на блоки длины r, необходимо дополнение. В SHA-3 используется паттерн pad10*1[11]: к сообщению добавляется 1, после него — 0 или больше нулевых битов (до r-1), в конце — 1.

r-1 нулевых битов может быть добавлено, когда последний блок сообщения имеет длину r-1 бит. Этот блок дополняется единицей, следующий блок будет состоять из r-1 нулей и единицы.

Два единичных бита добавляются и в том случае, если длина исходного сообщения M делится на r[11]. В этом случае к сообщению добавляется блок, начинающийся и оканчивающийся единицами, между которыми r-2 нулевых битов. Это необходимо для того, чтобы для сообщения, оканчивающегося последовательностью битов как в функции дополнения, и для сообщения без этих битов значения хеш-функции были различны.

Первый единичный бит необходим для того, чтобы результаты хеш-функции от сообщений, различающихся несколькими нулевыми битами в конце, были различны[11].

Функция перестановок

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

Функция перестановок, используемая в SHA-3, включает в себя исключающее «ИЛИ» (XOR), побитовое «И» (AND) и побитовое отрицание (NOT). Функция определена для строк длины-степени 2 . В основной реализации SHA-3 ().

Состояние можно представить в виде трёхмерного массива размером 5 × 5 × . Тогда элемент массива - это бит строки состояния .

Функция содержит несколько шагов: , , , , , которые выполняются несколько раундов[11]. На каждом шаге обозначим входной массив A, выходной массив A'.

Шаг

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

Для всех и , таких, что , , положим

Для всех , таких, что , , ,

Шаг

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

Для всех , таких, что ,

Пусть в начале . Для от 0 до 23:

  1. Для всех , таких, что ,

Шаг

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

Для всех , таких, что , ,

Шаг

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

Для всех , таких, что , ,

Шаг

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

Введем дополнительную функцию , где вход — целое число , а на выходе — бит.

Алгоритм

[править | править код]
  1. Если , то возвращается 1
  2. Пусть
  3. Для i от 1 до t mod 255:
    1. R = 0 || R
  4. Возвращается

Алгоритм

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

 — номер раунда.

  1. Для всех , таких, что , ,
  2. Пусть  — массив длины , заполненный нулями.
  3. Для от 0 до :
  4. Для всех , таких, что ,

Алгоритм перестановок

[править | править код]
  1. Перевод строки в массив
  2. Для от до
  3. Перевод массива в строку длины

Хеширование сообщений произвольной длины

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

Основой функции сжатия алгоритма является функция f, выполняющая перемешивание внутреннего состояния алгоритма. Состояние (обозначим его A) представляется в виде массива 5×5, элементами которого являются 64-битные слова, инициализированные нулевыми битами (то есть, размер состояния составляет 1600 битов). Функция f выполняет 24 раунда, в каждом из которых производятся следующие действия:

 C[x] = A[x, 0]  A[x, 1]  A[x, 2]  A[x, 3]  A[x, 4], x = 0…4;  D[x] = C[x — 1]  (С[x + 1] >>> 1), x = 0…4;  A[x, y] = A[x, y]  D[x], x = 0…4, y = 0…4;  B[y, 2x + 3y] = A[x, y] >>> r[x, y], x = 0…4, y = 0…4;  A[x, y] = B[x, y]  (~B[x + 1, y] & B[x + 2, y]), x = 0…4, y = 0…4,  

Где:

B — временный массив, аналогичный по структуре массиву состояния;
C и D — временные массивы, содержащие по пять 64-битных слов;
r — массив, определяющий величину циклического сдвига для каждого слова состояния;
~x — поразрядное дополнение к x;
и операции с индексами массива выполняются по модулю 5.

Кроме приведенных выше операций, в каждом раунде также выполняется наложение операцией XOR раундовой константы на слово A[0, 0].

Перед выполнением функции сжимания накладывается операция XOR фрагментов исходного сообщения с фрагментами исходного состояния. Результат обрабатывается функцией f. Данное наложение в совокупности с функцией сжимания, выполняемые для каждого блока входных данных, представляют собой «впитывающую» (absorbing) фазу криптографической губки.

Стоит отметить, что функция f использует только операции, стойкие к атакам, использующим утечки данных по побочным каналам.

Результирующее хеш-значение вычисляется в процессе выполнения «выжимающей» (squeezing) фазы криптографической губки, основу которой также составляет описанная выше функция f. Возможные размеры хеш-значений — 224, 256, 384 и 512 бит.

Оригинальный алгоритм Keccak имеет множество настраиваемых параметров[11] с целью обеспечения оптимального соотношения криптостойкости и быстродействия для определённого применения алгоритма на определённой платформе. Настраиваемыми величинами являются: размер блока данных, размер состояния алгоритма, количество раундов в функции f() и другие.

На протяжения конкурса хеширования Национального института стандартов и технологий участники имели право настраивать свои алгоритмы для решения возникших проблем. Так, были внесены некоторые изменения в Keccak: количество раундов было увеличено с 18 до 24 с целью увеличения запаса безопасности.

Авторы Keccak учредили ряд призов за достижения в криптоанализе данного алгоритма.

Версия алгоритма, принятая в качестве окончательного стандарта SHA-3, имеет несколько незначительных отличий от оригинального предложения Keccak на конкурс. В частности, были ограничены некоторые параметры (отброшены медленные режимы c=768 и c=1024), в том числе для увеличения производительности[12][13][14][15]. Также в стандарте были введены «функции с удлиняемым результатом» (XOF, Extendable Output Functions) SHAKE128 и SHAKE256, для чего хешируемое сообщение стало необходимо дополнять «суффиксом» из 2 или 4 бит, в зависимости от типа функции.

Функция Формула
SHA3-224(M) Keccak[448](M||01, 224)
SHA3-256(M) Keccak[512](M||01, 256)
SHA3-384(M) Keccak[768](M||01, 384)
SHA3-512(M) Keccak[1024](M||01, 512)
SHAKE128(M, d) Keccak[256](M||1111, d)
SHAKE256(M, d) Keccak[512](M||1111, d)

Дополнительные функции

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

В декабре 2016 года Национальный институт стандартов и технологий США опубликовал новый документ, NIST SP.800-185[16], описывающий дополнительные функции на основе SHA-3:

Функция Описание
cSHAKE128(X, L, N, S) Параметризованная версия SHAKE
cSHAKE256(X, L, N, S)
KMAC128(K, X, L, S) Имитовставка на основе Keccak
KMAC256(K, X, L, S)
KMACXOF128(K, X, L, S)
KMACXOF256(K, X, L, S)
TupleHash128(X, L, S) Хеширование кортежа строк
TupleHash256(X, L, S)
TupleHashXOF128(X, L, S)
TupleHashXOF256(X, L, S)
ParallelHash128(X, B, L, S) Параллелизуемая хеш-функция на основе Keccak
ParallelHash256(X, B, L, S)
ParallelHashXOF128(X, B, L, S)
ParallelHashXOF256(X, B, L, S)

Тестовые векторы

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

Значения разных вариантов хеша от пустой строки.

SHA3-224("") 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3-256("") a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3-384("") 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3-512("") a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26 SHAKE128("", 256) 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256("", 512) 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be 

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

SHA3-224("The quick brown fox jumps over the lazy dog") d15dadceaa4d5d7bb3b48f446421d542e08ad8887305e28d58335795 SHA3-224("The quick brown fox jumps over the lazy dog.") 2d0708903833afabdd232a20201176e8b58c5be8a6fe74265ac54db0 
SHA3-256("The quick brown fox jumps over the lazy dog") 69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04 SHA3-256("The quick brown fox jumps over the lazy dog.") a80f839cd4f83f6c3dafc87feae470045e4eb0d366397d5c6ce34ba1739f734d 
SHA3-384("The quick brown fox jumps over the lazy dog") 7063465e08a93bce31cd89d2e3ca8f602498696e253592ed26f07bf7e703cf328581e1471a7ba7ab119b1a9ebdf8be41 SHA3-384("The quick brown fox jumps over the lazy dog.") 1a34d81695b622df178bc74df7124fe12fac0f64ba5250b78b99c1273d4b080168e10652894ecad5f1f4d5b965437fb9 
SHA3-512("The quick brown fox jumps over the lazy dog") 01dedd5de4ef14642445ba5f5b97c15e47b9ad931326e4b0727cd94cefc44fff23f07bf543139939b49128caf436dc1bdee54fcb24023a08d9403f9b4bf0d450 SHA3-512("The quick brown fox jumps over the lazy dog.") 18f4f4bd419603f95538837003d9d254c26c23765565162247483f65c50303597bc9ce4d289f21d1c2f1f458828e33dc442100331b35e7eb031b5d38ba6460f8 
SHAKE128("The quick brown fox jumps over the lazy dog", 256) f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e SHAKE128("The quick brown fox jumps over the lazy dof", 256) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c 

Криптоанализ

[править | править код]
Результаты криптоанализа во время конкурса[4].
Цель Тип атаки Выход Вариант CF Call Память
Хеш-функция Коллизия 160 r = {240, 640, 1440},

c = 160,

1, 2 раунда

Хеш-функция Нахождение прообраза 80 r = {240, 640, 1440},

c = 160,

1, 2 раунда

Перестановки Атака-различитель Все 24 раунда
Перестановки Дифференциальное свойство Все 8 раундов
Хеш-функция Атака-различитель 224, 256 4 раунда
Хеш-функция Коллизия 224, 256 2 раунда
Хеш-функция Нахождение второго прообраза 224, 256 2 раунда
Хеш-функция Нахождение второго прообраза 512 6 раундов
Хеш-функция Нахождение второго прообраза 512 7 раундов
Хеш-функция Нахождение второго прообраза 512 8 раундов
Хеш-функция Коллизия 224, 256 4 раунда

Примечания

[править | править код]
  1. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. Дата обращения: 3 октября 2012. Архивировано 5 октября 2012 года.
  2. 1 2 NIST Releases SHA-3 Cryptographic Hash Standard. Дата обращения: 21 января 2016. Архивировано 17 августа 2015 года.
  3. 1 2 NIST Manuscript Publication Search. Дата обращения: 21 января 2016. Архивировано 12 августа 2015 года.
  4. 1 2 Shu-jen Chang, Ray Perlner, William E. Burr, Meltem Sonmez Turan, John M. Kelsey. Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition. — doi:10.6028/nist.ir.7896.
  5. 1 2 Keccak Team (англ.). keccak.team. Дата обращения: 15 декабря 2017. Архивировано 16 декабря 2017 года.
  6. SHA-3 Project - Hash Functions | CSRC. csrc.nist.gov. Дата обращения: 7 ноября 2017. Архивировано 20 ноября 2017 года.
  7. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST (2 октября 2012). Дата обращения: 2 октября 2012. Архивировано 30 апреля 2017 года.
  8. 1 2 Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. The Road from Panama to Keccak via RadioGatún // Symmetric Cryptography / Helena Handschuh, Stefan Lucks, Bart Preneel, Phillip Rogaway. — Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009. Архивировано 22 декабря 2017 года.
  9. Keccak Team (англ.). keccak.team. Дата обращения: 12 ноября 2017. Архивировано 13 ноября 2017 года.
  10. Keccak Team (англ.). keccak.team. Дата обращения: 12 ноября 2017. Архивировано 13 ноября 2017 года.
  11. 1 2 3 4 5 6 Morris J. Dworkin. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. — doi:10.6028/nist.fips.202.
  12. Will Keccak = SHA-3? (1 октября 2013). Дата обращения: 20 декабря 2013. Архивировано 30 января 2014 года.
  13. "What the heck is going on with NIST's cryptographic standard, SHA-3?" (англ.). 2013-09-24. Архивировано 25 января 2014. Дата обращения: 20 декабря 2013.
  14. Yes, this is Keccak! (4 октября 2013). Дата обращения: 20 декабря 2013. Архивировано 8 декабря 2013 года. — ответное заявление от авторов Keccak
  15. The Keccak sponge function family (17 января 2011). Дата обращения: 30 сентября 2015. Архивировано 12 сентября 2015 года. — изменение алгоритма заполнения в 3-м раунде конкурса
  16. SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash. Дата обращения: 31 октября 2017. Архивировано 31 октября 2017 года.

Реализации: