SHA-3

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Keccak»)
Перейти к: навигация, поиск
Криптографическая
хеш-функция
Название

SHA-3, Keccak

Разработчики

Гвидо Бертони, Йоан Даймен, Микаел Питерс, Жиль Ван Аше

Создан

2008

Опубликован

2008

Размер хеша

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 оказался намного быстрее, чем все другие финалисты.

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

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

Хеширование сообщений произвольной длины[править | править вики-текст]

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

 C[x] = A[x, 0] \oplus A[x, 1] \oplus A[x, 2] \oplus A[x, 3] \oplus A[x, 4], x = 0…4;
 D[x] = C[x — 1] \oplus (С[x + 1] >>> 1), x = 0…4;
 A[x, y] = A[x, y] \oplus 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] \oplus (~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 имеет множество настраиваемых параметров с целью обеспечения оптимального соотношения криптостойкости и быстродействия для определенного применения алгоритма на определенной платформе. Настраиваемыми величинами являются: размер блока данных, размер состояния алгоритма, количество раундов в функции f() и другие.

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

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

Версия алгоритма, принятая в качестве окончательного стандарта SHA-3, имеет несколько незначительных отличий от оригинального предложения Keccak на конкурс. В частности, были ограничены некоторые параметры (отброшены медленные режимы c=768 и c=1024), в том числе для увеличения производительности, а также изменён алгоритм заполнения (padding) на более простой.[4][5][6][7] Также в стандарте были введены «функции с удлинняемым результатом» (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)

Тестовые векторы[править | править вики-текст]

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

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

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

  1. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition
  2. NIST Releases SHA-3 Cryptographic Hash Standard
  3. NIST Manuscript Publication Search
  4. Will Keccak = SHA-3? (October 1, 2013). Проверено 20 декабря 2013.
  5. What the heck is going on with NIST’s cryptographic standard, SHA-3? (англ.) (September 24, 2013). Проверено 20 декабря 2013.
  6. Yes, this is Keccak! (4 October 2013). Проверено 20 декабря 2013. — ответное заявление от авторов Keccak
  7. The Keccak sponge function family (January 17, 2011). Проверено 30 сентября 2015. — изменение алгоритма заполнения в 3-м раунде конкурса

Ссылки[править | править вики-текст]

Реализации: