Keccak

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

Keccak

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

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

Создан

2008

Опубликован

2008

Размер хэша

224, 256, 384, 512 (переменный, 0<d≤264-1)

Число раундов

24 (по умолчанию)

Тип

хеш-функция

Keccak (произносится как «кечак») — алгоритм хеширования переменной разрядности, разработанный группой авторов во главе с Йоаном Дайменом, соавтором Rijndael, автором шифров MMB, SHARK, Noekeon, SQUARE и BaseKing. 2 октября 2012 года Keccak стал победителем конкурса криптографических алгоритмов, проводимым Национальным институтом стандартов и технологий США (en:NIST hash function competition).[1] В аппаратных реализациях Keccak проявил себя намного быстрее, чем все другие финалисты. Авторы заявляют о 12,5 циклах на байт при выполнении на ПК с процессором Intel Core 2.

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

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

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

Раунд алгоритма Keccak

Основой функции сжатия алгоритма является функция 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 — временные массивы, содержащие по 5 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.[2][3][4]

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

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

Keccak-224("")
0x f71837502ba8e10837bdd8d365adb85591895602fc552b48b7390abd
Keccak-256("")
0x c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
Keccak-384("")
0x 2c23146a63a29acf99e73b88f8c24eaa7dc60aa771780ccc006afbfa8fe2479b2dd2b21362337441ac12b515911957ff
Keccak-512("")
0x 0eab42de4c3ceb9235fc91acffe746b29c29a8c366b7c60e4e67c466f36a4304c00fa9caf9d87976ba469bcbe06713b435f091ef2769fb160cdab33d3670680e

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

Keccak-224("The quick brown fox jumps over the lazy dog")
0x 310aee6b30c47350576ac2873fa89fd190cdc488442f3ef654cf23fe
Keccak-224("The quick brown fox jumps over the lazy dog.")
0x c59d4eaeac728671c635ff645014e2afa935bebffdb5fbd207ffdeab

Keccak-256("The quick brown fox jumps over the lazy dog")
0x 4d741b6f1eb29cb2a9b9911c82f56fa8d73b04959d3d9d222895df6c0b28aa15
Keccak-256("The quick brown fox jumps over the lazy dog.")
0x 578951e24efd62a3d63a86f7cd19aaa53c898fe287d2552133220370240b572d

Keccak-384("The quick brown fox jumps over the lazy dog")
0x 283990fa9d5fb731d786c5bbee94ea4db4910f18c62c03d173fc0a5e494422e8a0b3da7574dae7fa0baf005e504063b3
Keccak-384("The quick brown fox jumps over the lazy dog.")
0x 9ad8e17325408eddb6edee6147f13856ad819bb7532668b605a24a2d958f88bd5c169e56dc4b2f89ffd325f6006d820b

Keccak-512("The quick brown fox jumps over the lazy dog")
0x d135bb84d0439dbac432247ee573a23ea7d3c9deb2a968eb31d47c4fb45f1ef4422d6c531b5b9bd6f449ebcc449ea94d0a8f05f62130fda612da53c79659f609
Keccak-512("The quick brown fox jumps over the lazy dog.")
0x ab7192d2b11f51c7dd744e7b3441febf397ca07bf812cceae122ca4ded6387889064f8db9230f173f6d1ab6e24b6e50f065b039f799f5592360a6558eb52d760

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

  1. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition
  2. Will Keccak = SHA-3? (October 1, 2013). Проверено 20 декабря 2013.
  3. What the heck is going on with NIST’s cryptographic standard, SHA-3?  (англ.) (September 24, 2013). Проверено 20 декабря 2013.
  4. Yes, this is Keccak! (4 October 2013). Проверено 20 декабря 2013. — ответное заявление от авторов Keccak

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

Реализации: