Skein

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

Skein

Создан

2008

Опубликован

2008

Размер хеша

переменный, 0<d≤264-1

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

переменное, 72 для 256/512-бит выхода, 80 - для 1024 бит

Тип

хеш-функция

Skein (англ. Skein) — алгоритм хеширования переменной разрядности, разработанный группой авторов во главе с Брюсом Шнайером. Хэш-функция Skein выполнена как универсальный криптографический примитив, на основе блочного шифра Threefish, работающего в режиме UBI-хэширования.[1] Основные требования, предъявлявшиеся при разработке — оптимизация под минимальное использование памяти, криптографически безопасное хэширование небольших сообщений, устойчивость ко всем существующим атакам на хэш-функции, оптимизация под 64-разрядные процессоры и активное использование обращений к таблицам.

История[править | править исходный текст]

Skein была создана в 2008 году группой авторов во главе с Брюсом Шнайером и вошла в пятерку финалистов конкурса SHA-3, однако в 2012 в финале победителем был выбран алгоритм Keccak, наиболее производительный и нечувствительный к уязвимостям SHA-2[2] . Название хэш-функции Skein означает «моток пряжи».

Алгоритм[править | править исходный текст]

Threefish Block[править | править исходный текст]

Threefish — это настраиваемый блочный шифр, определенный для блоков размером 256, 512 и 1024 бит. Шифр реализован в виде подстановочно-перестановочной сети. В основе шифра лежит простая функция MIX, принимающая на вход два 64-битных слова и состоящая из блоков сложения, циклического сдвига на константу, и сложения по модулю 2(XOR). Используется 72 раунда для 256-битного и 512-битного шифра, и 80 раундов для 1024-битного шифра. Между раундами происходит перестановка слов, а каждые четыре раунда добавляется ключ, за счет чего появляется нелинейность.

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

Threefish в Skein используется в режиме UBI(Unique Block Iteration) хэширования. Режим UBI — это разновидность режима Matyas-Meyer-Oseas.[1] Каждое звено UBI комбинирует входные сообщения с предыдущего звена цепи с последовательностью произвольной длины и устанавливает на выходе значение фиксированного размера. Сообщение, передающееся между звеньями(твик), содержит информацию о том, сколько байт было обработано, флаги начала и конца цепочки, и поле типа данных, которое позволяет различать сферы применения UBI. UBI гарантирует невоспроизводимость результата хэширования одного и того же сообщения и дополнительную защиту за счет того, что на вход хэш-функции и шифра попадают одни и те же сообщения. UBI устроен следующим образом. Каждое звено цепи — это функция f(G,M,T_s)

G — начальное N_b-байтное значение
M — сообщение, представленное строкой байт(длина этой строки может быть произвольной, но максимум 2:99 - 8)
T_s — стартовое значение твика типа Integer(128 бит).

Твик содержит следующие поля:

  • Position — количество уже обработанных байт.
  • Reserved — зарезервированные нулевые биты
  • TreeLevel — позиция в дереве хэширования, либо ноль, если этот способ хэширования не применяется.
  • BitPad — флаг, который поднимается в случае, если в блоке обрабатывался последний байт входного сообщения, которое содержит не целое число байт. В остальных случаях поле имеет значение 0.
  • Type тип вызова UBI. Возможные значения см.ниже.
  • First — флаг начала цепочки.
  • Final — флаг конца цепочки.

Вычисления происходят следующим образом. Если количество бит M делится на 8, то положим B = 0 и M' = M. Если количество бит M не делится на 8, то дополним последний(неполный)байт следующим образом: старшему неиспользуемому биту присвоим значение 1, остальным 0 положим B = 1 и M' = M с учетом дополненного байта. Далее дополним M' нулями так, чтобы количество бит M' ,было кратно N_b и назовем полученный результат M'' Разобьем M'' на k блоков по N_b бит каждый. Значение UBI вычисляется так:

H_0 = G
H_i = E(Hi; ToBytes(Ts + min(N_M;(i + 1)N_b) + a_i2^{126} + b_i(B2^{119} + 2^{127}); 16); M_i) \bigoplus Mi,

где E — функция вычисления блочного шифра, a_0 = b_{k-1} = 1, остальные a_i = b_i = 0

Твик вычисляется по формуле:

Ts + min(N_M;(i + 1)N_b) + a_i2^{126} + b_i(B2^{119} + 2^{127})

Первое слагаемое определяет поля TreeLevel и Type, второе — поле Position, третье — выставляет флаг First, четвёртое — флаги Final и BitPad.

Дополнительные аргументы[править | править исходный текст]

В поле Type путем присвоения соответствующего значения T_s могут быть заданы следующие параметры

  • Key(Ключ). Используется в случае, если Skein работает как MAC или KDF. Вызов UBI с этим параметром происходит первым, чтобы использовать дополнительные возможности защиты.
  • Configuration (Конфигурация). Используется всегда. Задает размер выходного значения и параметры для поддержки дерева хэширования.
  • Personalisation (Персонализация). Параметр, который используется, если для разных пользователей требуются разные функции.
  • Public Key (Открытый ключ). Используется для хэширования открытого ключа для подписи сообщения.
  • Key Derivation Identifer.
  • Nonce. Используется для работы в режиме потокового шифра
  • Message (Сообщение). Сообщение для хэширования
  • Output (Выход). Используется всегда, указывает на выходное преобразование.

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

В окончательном варианте вычисление Skein происходит следующим образом. Skein имеет следующие входные аргументы:

  • N_b Внутренний размер в байтах. Может принимать значения 32, 64, or 128.
  • N_0 Размер выходного значения в битах.
  • K Ключ длиной N_k байт. Может быть пустой строкой.
  • Y_l Размер листа дерева хэширования.
  • Y_f Коэффициент разветвления дерева.
  • Y_m Максимальная высота дерева
  • L Список из t наборов (T_i, M_i) где T_i — значение поля Type, M_i — строка байт.

Сначала генерируется ключ K'. Если K — пустая строка, то начальное значение :K' = 0^{N_b}. Если нет, то K' вычисляется так:

K' = UBI(0^{N_b}, K, T_{cfg}2^{120})

Далее вычисления происходят по следующей схеме:

G_0 = UBI(K', C, T_{cfg}2^{120})

Здесь C — конфигурационная строка, которая содержит идентификатор(он нужен, чтобы различать разные функции, созданные на основе UBI), информацию о версии, длине выходного значения, параметрах дерева.

G_{i+1} = UBI(G_i, M_i, T_{i}2^{120})

Окончательный результат определяется так называемой функцией Output(G_t,N_0), которая определяется, как ведущие N_0/8 байт выражения

UBI (G, ToBytes(0, 8), T_{out}2^{120}\|\|UBI (G, ToBytes(1, 8), T_{out}2^{120}\|\|...

Если параметры Y_l, Y_f, Y_m ненулевые, то вычисления производятся иначе. Определяется размер листа дерева как N_l = N_b2^{Y_l} и размер узла как N_n = N_b2^{Y_f}.

Сообщение l-го уровня M_l делится на блоки M_{li} размером 8N_l и вычисляется следующий уровень дерева, как слияние по всем i\in(0,k-1)

M_{1+1} = UBI(G, M_{li}, iNn + (l + 1)2^{112} + T_{msg}2^{120})

Если же длина M_l равна N_b, то хэширование окончено и его результат G_0 = M_l . Если длина M_l больше N_b, но l = Y_m-1, достигнута максимальная высота дерево, и в этом случае результат хэширования G_0 = UBI(G, M_l, Y_m2^{112} + T_{msg}2^{120}).

Также существует упрощенная версия Skein с аргументами N_b, N_0, M. Поле Type может принимать только значения Cfg и Msg

Криптоанализ[править | править исходный текст]

В 2009 году коллектив авторов[3] исследовал Threefish, как важную часть Skein, на криптоустойчивость. Совокупно с исследованиями создателей[1] , они пришли результату, указанному в таблице.

Кол-во раундов Время Память Вид криптоанализа
8 1 - 511-битная псевдоколлизия
16 26 - 459-битная псевдоколлизия
17 224 - 434-битная псевдоколлизия
17 28,6 - Related-key distinguisher
21 23.4 - Related-key distinguisher
21 - - Related-key impossible differential
25  ? - Related-key key recovery (conjectured)
25 2416.6 - Related-key key recovery
26 2507.8 - Related-key key recovery
32 2312 271 Related-key boomerang key recovery
34 2398 - Related-key boomerang distinguisher
35 2478 - Known-related-key boomerang distinguisher

Кроме того, ещё один коллектив авторов[4] в 2010 году показал, что используя циклический криптоанализ, можно провести атаку на основе подобранного ключа на Threefish, но только если используется 53/57 раундов вместо 72. Для атаки на Skein этого недостаточно, поэтому предлагается совмещать циклический криптоанализ с дифференциальным.

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

Существуют реализации Skein для трех вариантов значения внутреннего состояния: 256, 512 и 1024 бит. Основным вариантом считается Skein-512, который может безопасно использован для всех криптографических приложений в обозримом будущем. 1024-битный с малым объёмом памяти, вариант ещё более безопасен, и в существующих аппаратных реализациях работает в два раза быстрее. Skein-256 — оптимальный вариант для использования в устройствах с малым объёмом памяти(например в смарт-картах), так как требует только 100 байт RAM, в отличие от Skein-512, требующей 200 байт. В связи с устройством Threefish, Skein работает быстрее всего на 64-битных процессорах. В таблице ниже приведена сравнительная характеристика быстродействия Skein и алгоритмов SHA. В таблице показана скорость(в тактах на байт)реализации на С на 64-битном процессоре.

Алгоритм/Длина сообщения(байт) 1 10 100 1000 10000 100000
Skein-256 774 77 16.6 9.8 9.2 9.2
Skein-512 1086 110 15.6 7.3 6.6 6.5
Skein-1024 3295 330 33.2 14.2 12.3 12.3
SHA-1 677 74.2 14.0 10.4 10.0 10.0
SHA-224 1379 143.1 27.4 20.7 20.1 20.0
SHA-256 1405 145.7 77.6 20.7 20.1 20.0
SHA-384 1821 187.3 19.6 13.7 13.4 13.3
SHA-512 1899 192.5 20.6 13.8 13.4 13.3

Как видно из таблицы, Skein работает в два раза быстрее, чем SHA-512.

Применение[править | править исходный текст]

Область применения Skein достаточно широка. Используя сообщение и ключ в качестве соответствующих входов, можно вычислить MAC. Возможно использование в качестве хэш-функции для вычисления HMAC. При помощи аргумента Nonce использовать Skein в режиме поточного шифра. Также возможно применение в качестве генератора псевдослучайных чисел, например, в алгоритмах Fortuna и Yarrow, в качестве Key Derivation Function и Password-Based Key Derivation Function(используя аргументы Key и Key Derivation Identifer ), в качестве хэш-функции для вычисления электронной подписи(подразумевается использование аргумента Public Key).

При помощи аргумента Personalisation все приложения Skein могут быть персонифицированы для конкретного пользователя. Например для приложения FOO строка персонализации в UTF8 Unicode может выглядеть так

20081031 somebody@example.com FOO/bar,

где bar — персонификация внутри приложения.

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

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

  1. 1 2 Документация Skein, Версия 1.3 (2010-10-01)
  2. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. Проверено 2 октября 2012.
  3. Jean-Philippe Aumasson1, C¸ a˘gda¸s C¸ alık, Willi Meier1, Onur Ozen, Raphael C.-W. and Kerem Varıcı, (2009). «Improved Cryptanalysis of Skein» (University of Luxembourg).
  4. Dmitry Khovratovich and Ivica Nikolić (2010). «Rotational Cryptanalysis of ARX» (University of Luxembourg).