Skein

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

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

История

Skein была создана в 2008 году группой авторов во главе с Брюсом Шнайером и вошла в пятёрку финалистов конкурса SHA-3, однако в 2012 в финале победителем был выбран алгоритм Keccak, наиболее производительный и нечувствительный к уязвимостям SHA-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 — это разновидность режима .[1] Каждое звено UBI комбинирует входные сообщения с предыдущего звена цепи с последовательностью произвольной длины и устанавливает на выходе значение фиксированного размера. Сообщение, передающееся между звеньями (твик), содержит информацию о том, сколько байт было обработано, флаги начала и конца цепочки, и поле типа данных, которое позволяет различать сферы применения UBI. UBI гарантирует невоспроизводимость результата хеширования одного и того же сообщения и дополнительную защиту за счёт того, что на вход хеш-функции и шифра попадают одни и те же сообщения. UBI устроен следующим образом. Каждое звено цепи — это функция ${\displaystyle f(G,M,T_{s})}$

${\displaystyle G}$ — начальное ${\displaystyle N_{b}}$-байтное значение

${\displaystyle M}$ — сообщение, представленное строкой байт (длина этой строки может быть произвольной, но максимум ${\displaystyle 2^{99}-8}$ бит)

${\displaystyle T_{s}}$ — стартовое значение твика целочисленного типа (128 бит).

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

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

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

${\displaystyle H_{0}=G}$

${\displaystyle 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}}$,

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

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

${\displaystyle 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 путём присвоения соответствующего значения ${\displaystyle T_{s}}$ могут быть заданы следующие параметры

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

Skein

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

• ${\displaystyle N_{b}}$ Внутренний размер в байтах. Может принимать значения 32, 64, or 128.
• ${\displaystyle N_{0}}$ Размер выходного значения в битах.
• ${\displaystyle K}$ Ключ длиной ${\displaystyle N_{k}}$ байт. Может быть пустой строкой.
• ${\displaystyle Y_{l}}$ Размер листа дерева хеширования.
• ${\displaystyle Y_{f}}$ Коэффициент разветвления дерева.
• ${\displaystyle Y_{m}}$ Максимальная высота дерева
• ${\displaystyle L}$ Список из ${\displaystyle t}$ наборов (${\displaystyle T_{i}}$, ${\displaystyle M_{i}}$) где ${\displaystyle T_{i}}$ — значение поля Type, ${\displaystyle M_{i}}$ — строка байт.

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

${\displaystyle K'=UBI(0^{N_{b}},K,T_{cfg}2^{120})}$

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

${\displaystyle G_{0}=UBI(K',C,T_{cfg}2^{120})}$

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

${\displaystyle G_{i+1}=UBI(G_{i},M_{i},T_{i}2^{120})}$

Окончательный результат определяется так называемой функцией ${\displaystyle Output(G_{t},N_{0})}$, которая определяется, как ведущие ${\displaystyle N_{0}/8}$ байт выражения

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

Если параметры ${\displaystyle Y_{l}}$, ${\displaystyle Y_{f}}$, ${\displaystyle Y_{m}}$ ненулевые, то вычисления производятся иначе. Определяется размер листа дерева как ${\displaystyle N_{l}=N_{b}2^{Y_{l}}}$ и размер узла как ${\displaystyle N_{n}=N_{b}2^{Y_{f}}}$.

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

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

Если же длина ${\displaystyle M_{l}}$ равна ${\displaystyle N_{b}}$, то хеширование окончено и его результат ${\displaystyle G_{0}=M_{l}}$. Если длина ${\displaystyle M_{l}}$ больше ${\displaystyle N_{b}}$, но ${\displaystyle l=Y_{m}-1}$, достигнута максимальная высота дерево, и в этом случае результат хеширования ${\displaystyle G_{0}=UBI(G,M_{l},Y_{m}2^{112}+T_{msg}2^{120})}$.

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

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

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

Кол-во раундов	Время	Память	Вид криптоанализа
8	1	-	511-битная псевдоколлизия
16	2^6	-	459-битная псевдоколлизия
17	2^24	-	434-битная псевдоколлизия
17	2^8,6	-	(Related-key) distinguisher
21	2^3.4	-	Related-key distinguisher
21	-	-	Related-key impossible differential
25	?	-	Related-key key recovery (conjectured)
25	2^416.6	-	Related-key key recovery
26	2^507.8	-	Related-key key recovery
32	2^312	2^71	Related-key boomerang key recovery
34	2^398	-	Related-key boomerang distinguisher
35	2^478	-	Known-related-key boomerang distinguisher

Кроме того, ещё один коллектив авторов в 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 [e-mail] 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

Примечания

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 года.