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 устроен следующим образом. Каждое звено цепи — это функция
- — начальное -байтное значение
- — сообщение, представленное строкой байт (длина этой строки может быть произвольной, но максимум бит)
- — стартовое значение твика целочисленного типа (128 бит).
Твик содержит следующие поля:
- Position — количество уже обработанных байт.
- Reserved — зарезервированные нулевые биты
- TreeLevel — позиция в дереве хеширования, либо ноль, если этот способ хеширования не применяется.
- BitPad — флаг, который поднимается в случае, если в блоке обрабатывался последний байт входного сообщения, которое содержит не целое число байт. В остальных случаях поле имеет значение 0.
- Type тип вызова UBI. Возможные значения см. ниже.
- First — флаг начала цепочки.
- Final — флаг конца цепочки.
Вычисления происходят следующим образом. Если количество бит делится на 8, то положим и . Если количество бит не делится на 8, то дополним последний (неполный) байт следующим образом: старшему неиспользуемому биту присвоим значение 1, остальным 0 положим и с учётом дополненного байта. — это число байт в . Входное значение ограничено . Далее дополним нулями так, чтобы количество бит , было кратно и назовём полученный результат . Разобьём на блоков по байт каждый. Значение UBI вычисляется так:
- ,
где — функция вычисления блочного шифра, , остальные
Твик вычисляется по формуле:
Первое слагаемое определяет поля TreeLevel и Type, второе — поле Position, третье — выставляет флаг First, четвёртое — флаги Final и BitPad.
Дополнительные аргументы
В поле Type путём присвоения соответствующего значения могут быть заданы следующие параметры
- Key (Ключ). Используется в случае, если Skein работает как MAC или KDF. Вызов UBI с этим параметром происходит первым, чтобы использовать дополнительные возможности защиты.
- Configuration (Конфигурация). Используется всегда. Задаёт размер выходного значения и параметры для поддержки дерева хеширования.
- Personalisation (Персонализация). Параметр, который используется, если для разных пользователей требуются разные функции.
- Public Key (Открытый ключ). Используется для хеширования открытого ключа для подписи сообщения.
- Key Derivation Identifer.
- Nonce. Используется для работы в режиме потокового шифра
- Message (Сообщение). Сообщение для хеширования
- Output (Выход). Используется всегда, указывает на выходное преобразование.
Skein
В окончательном варианте вычисление Skein происходит следующим образом. Skein имеет следующие входные аргументы:
- Внутренний размер в байтах. Может принимать значения 32, 64, or 128.
- Размер выходного значения в битах.
- Ключ длиной байт. Может быть пустой строкой.
- Размер листа дерева хеширования.
- Коэффициент разветвления дерева.
- Максимальная высота дерева
- Список из наборов (, ) где — значение поля Type, — строка байт.
Сначала генерируется ключ . Если — пустая строка, то начальное значение :. Если нет, то вычисляется так:
Далее вычисления происходят по следующей схеме:
Здесь — конфигурационная строка, которая содержит идентификатор (он нужен, чтобы различать разные функции, созданные на основе UBI), информацию о версии, длине выходного значения, параметрах дерева.
Окончательный результат определяется так называемой функцией , которая определяется, как ведущие байт выражения
Если параметры , , ненулевые, то вычисления производятся иначе.
Определяется размер листа дерева как и размер узла как .
Сообщение l-го уровня делится на блоки размером и вычисляется следующий уровень дерева, как слияние по всем
Если же длина равна , то хеширование окончено и его результат . Если длина больше , но , достигнута максимальная высота дерево, и в этом случае результат хеширования .
Также существует упрощённая версия Skein с аргументами , , . Поле 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
Ссылки
Примечания