Skein

Skein
Skein
Создан	2008
Опубликован	2008
Размер хеша	переменный, 0<d≤264-1
Число раундов	переменное, 72 для 256/512-бит выхода, 80 - для 1024 бит
Тип	хеш-функция

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}

— стартовое значение твика целочисленного типа (128 бит).

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

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

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

H_{0}=G

H_{i+1}=E(H_{i};ToBytes(T_{s}+min(N_{M};(i+1)N_{b})+a_{i}2^{126}+b_{i}(B2^{119}+2^{127});16);M_{i})\bigoplus M_{i}

,

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

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

T_{s}+min(N_{M};(i+1)N_{b})+a_{i}2^{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_{b}2^{Y_{l}}$ и размер узла как $N_{n}=N_{b}2^{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_{m}2^{112}+T_{msg}2^{120})$ .

Также существует упрощённая версия Skein с аргументами $N_{b}$ , $N_{0}$ , $M$ . Поле Type может принимать только значения Cfg и Msg

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

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

Кол-во раундов	Время	Память	Вид криптоанализа
8	1	-	511-битная псевдоколлизия
16	2⁶	-	459-битная псевдоколлизия
17	2²⁴	-	434-битная псевдоколлизия
17	2^8,6	-	Related-key distinguisher
21	2^3.4	-	Related-key distinguisher
21	-	-	Related-key impossible diﬀerential
25	?	-	Related-key key recovery (conjectured)
25	2^416.6	-	Related-key key recovery
26	2^507.8	-	Related-key key recovery
32	2³¹²	2⁷¹	Related-key boomerang key recovery
34	2³⁹⁸	-	Related-key boomerang distinguisher
35	2⁴⁷⁸	-	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

Ссылки

Официальная страница Skein

Примечания

↑ ¹ ² Документация Skein, Версия 1.3 (2010-10-01) (неопр.). Дата обращения: 17 декабря 2013. Архивировано 24 августа 2014 года.
↑ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition (неопр.). NIST. Дата обращения: 2 октября 2012. Архивировано 5 октября 2012 года.
↑ 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. Архивировано 10 мая 2012 года.
↑ Dmitry Khovratovich and Ivica Nikolić. Rotational Cryptanalysis of ARX (неопр.). — University of Luxembourg, 2010. Архивировано 26 января 2013 года.

[autogenerated1-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. Архивировано 10 мая 2012 года.

[4] Dmitry Khovratovich and Ivica Nikolić. Rotational Cryptanalysis of ARX (неопр.). — University of Luxembourg, 2010. Архивировано 26 января 2013 года.

[1]

[2]

[3]

[4]