Перейти к содержанию

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

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 устроен следующим образом. Каждое звено цепи — это функция [math]\displaystyle{ f(G,M,T_s) }[/math]

[math]\displaystyle{ G }[/math] — начальное [math]\displaystyle{ N_b }[/math]-байтное значение
[math]\displaystyle{ M }[/math] — сообщение, представленное строкой байт (длина этой строки может быть произвольной, но максимум [math]\displaystyle{ 2^{99} - 8 }[/math] бит)
[math]\displaystyle{ T_s }[/math] — стартовое значение твика целочисленного типа (128 бит).

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

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

Вычисления происходят следующим образом. Если количество бит [math]\displaystyle{ M }[/math] делится на 8, то положим [math]\displaystyle{ B = 0 }[/math] и [math]\displaystyle{ M' = M }[/math]. Если количество бит [math]\displaystyle{ M }[/math] не делится на 8, то дополним последний (неполный) байт следующим образом: старшему неиспользуемому биту присвоим значение 1, остальным 0 положим [math]\displaystyle{ B = 1 }[/math] и [math]\displaystyle{ M' = M }[/math] с учётом дополненного байта. [math]\displaystyle{ N_M }[/math] — это число байт в [math]\displaystyle{ M' }[/math]. Входное значение ограничено [math]\displaystyle{ N_M \lt 2^{96} }[/math]. Далее дополним [math]\displaystyle{ M' }[/math] нулями так, чтобы количество бит [math]\displaystyle{ M' }[/math], было кратно [math]\displaystyle{ N_b }[/math] и назовём полученный результат [math]\displaystyle{ M'' }[/math]. Разобьём [math]\displaystyle{ M'' }[/math] на [math]\displaystyle{ k }[/math] блоков по [math]\displaystyle{ N_b }[/math] байт каждый. Значение UBI вычисляется так:

[math]\displaystyle{ H_0 = G }[/math]
[math]\displaystyle{ H_{i+1} = E(H_i; ToBytes(T_s + min(N_M;(i + 1)N_b) + a_i2^{126} + b_i(B2^{119} + 2^{127}); 16); M_i) \bigoplus M_i }[/math],

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

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

[math]\displaystyle{ T_s + min(N_M;(i + 1)N_b) + a_i2^{126} + b_i(B2^{119} + 2^{127}) }[/math]

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

Дополнительные аргументы

В поле Type путём присвоения соответствующего значения [math]\displaystyle{ T_s }[/math] могут быть заданы следующие параметры

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

Skein

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

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

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

[math]\displaystyle{ K' = UBI(0^{N_b}, K, T_{cfg}2^{120}) }[/math]

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

[math]\displaystyle{ G_0 = UBI(K', C, T_{cfg}2^{120}) }[/math]

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

[math]\displaystyle{ G_{i+1} = UBI(G_i, M_i, T_{i}2^{120}) }[/math]

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

[math]\displaystyle{ UBI (G, ToBytes(0, 8), T_{out}2^{120})\|UBI (G, ToBytes(1, 8), T_{out}2^{120})\|... }[/math]

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

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

[math]\displaystyle{ M_{1+1} = UBI(G, M_{li}, iNn + (l + 1)2^{112} + T_{msg}2^{120}) }[/math]

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

Также существует упрощённая версия Skein с аргументами [math]\displaystyle{ N_b }[/math], [math]\displaystyle{ N_0 }[/math], [math]\displaystyle{ M }[/math]. Поле 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 байт ОЗУ, в отличие от 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 — персонификация внутри приложения.

Примеры хешей Skein

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

Skein256-224("")
0x 0fadf1fa39e3837a95b3660b4184d9c2f3cfc94b55d8e7a083278bf8


Skein256-256("")
0x c8877087da56e072870daa843f176e9453115929094c3a40c463a196c29bf7ba


Skein512-224("")
0x 1541ae9fc3ebe24eb758ccb1fd60c2c31a9ebfe65b220086e7819e25


Skein512-256("")
0x 39ccc4554a8b31853b9de7a1fe638a24cce6b35a55f2431009e18780335d2621


Skein512-384("")
0x dd5aaf4589dc227bd1eb7bc68771f5baeaa3586ef6c7680167a023ec8ce26980f06c4082c488b4ac9ef313f8cbe70808


Skein512-512("")
0x bc5b4c50925519c290cc634277ae3d6257212395cba733bbad37a4af0fa06af4
   1fca7903d06564fea7a2d3730dbdb80c1f85562dfcc070334ea4d1d9e72cba7a


Skein1024-384("")
0x 1fdb081963b960e89eaa11b87dda55e8a55a3e1066b30e38d8ae2a45242f7dadfaf06d80ca8a73cd8242ce5eab84c164


Skein1024-512("")
0x e2943eb0bc0efabd49503a76edf7cfcf072db25bad94ed44fe537284163f3119
   c47ac6f78699b4272255966e0aba65c75a0a64bd23df6996d1bc3174afd9fa8b


Skein1024-1024("")
0x 0fff9563bb3279289227ac77d319b6fff8d7e9f09da1247b72a0a265cd6d2a62
   645ad547ed8193db48cff847c06494a03f55666d3b47eb4c20456c9373c86297
   d630d5578ebd34cb40991578f9f52b18003efa35d3da6553ff35db91b81ab890
   bec1b189b7f52cb2a783ebb7d823d725b0b4a71f6824e88f68f982eefc6d19c6

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

Skein512-256("The quick brown fox jumps over the lazy dog")
0x b3250457e05d3060b1a4bbc1428bc75a3f525ca389aeab96cfa34638d96e492a


Skein512-256("The quick brown fox jumps over the lazy dog.")
0x 41e829d7fca71c7d7154ed8fc8a069f274dd664ae0ed29d365d919f4e575eebb

Ссылки

Примечания

  1. ↑ 1,0 1,1 Документация Skein, Версия 1.3 (2010-10-01). Дата обращения: 17 декабря 2013. Архивировано 24 августа 2014 года.
  2. ↑ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. Дата обращения: 2 октября 2012. Архивировано 5 октября 2012 года.
  3. ↑ Jean-Philippe Aumasson1, C¸ a˘gda¸s C¸ alık, Willi Meier1, Onur Ozen, Raphael C.-W. and Kerem Varıcı,. Improved Cryptanalysis of Skein (неопр.). — University of Luxembourg, 2009.
  4. ↑ Dmitry Khovratovich and Ivica Nikolić. Rotational Cryptanalysis of ARX (неопр.). — University of Luxembourg, 2010.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Skein&oldid=5905070