Threefish

Threefish — в криптографии симметричный блочный криптоалгоритм, разработанный группой специалистов во главе с автором Blowfish и Twofish, американским криптографом Брюсом Шнайером в 2008 году для использования в хеш-функции Skein и в качестве универсальной замены существующим блочным шифрам. Основными принципами разработки шифра были: минимальное использование памяти, необходимая для использования в хеш-функции устойчивость к атакам, простота реализации и оптимизация под 64-разрядные процессоры.

Threefish
Создатель	Группа специалистов во главе с Брюсом Шнайером
Создан	2008 г.
Опубликован	2008 г.
Размер ключа	256/512/1024 бит
Размер блока	256/512/1024 бит
Число раундов	72 (80 при ключе 1024 бит)
Тип	Подстановочно-перестановочная сеть

Структура алгоритмаПравить

Threefish имеет очень простую структуру и может быть использован для замены алгоритмов блочного шифрования, будучи быстрым и гибким шифром, работающим в произвольном режиме шифрования. Threefish S-блоки не использует, основан на комбинации инструкций исключающего или, сложения и циклического сдвига.

Как и AES, шифр реализован в виде подстановочно-перестановочной сети на обратимых операциях, не являясь шифром сети Фейстеля.

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

Как результат мнения авторов, что несколько сложных раундов зачастую хуже применения большого числа простых раундов, алгоритм имеет нетрадиционно большое число раундов — 72 или 80 при ключе 1024 бит, однако, по заявлению создателей, его скоростные характеристики опережают AES примерно в два раза. Стоит заметить, что по причине 64-битной структуры шифра, данное заявление имеет место лишь на 64-разрядной архитектуре. Поэтому Threefish, как и Skein, основанный на нём, на 32-разрядных процессорах показывает значительно худшие результаты, чем на «родном» оборудовании.

Ядром шифра является простая функция «MIX», преобразующая два 64-битных беззнаковых числа, в процессе которой происходит сложение, циклический сдвиг (ROL/ROR), и сложение по модулю 2 (XOR).

 

Функция Mix

ОпределенияПравить

Threefish является блочным алгоритмом симметричного шифрования с дополнительным параметром настройки (tweak-значение). Размер блока данных, с которым работает алгоритм — 256, 512 или 1024 бит. Длина ключа равна выбранному размеру блока. Размер tweak-значения для любого из размеров блока — 128 бит.

Определим функцию шифрования $E(K,T,P)$$E(K, T, P)$ , где:

• $K$$K$  — ключ шифрования, строка длиной 32, 64, или 128 байт (256, 512, или 1024 бит).
• $T$$T$  — tweak-значение, строка длиной 16 байт (128 бит).
• $P$$P$  — открытый текст для шифрования, строка длиной равной размеру блока.

Для обработки блока данные представляются в виде массива 64-битных слов (целых чисел от $0$$0$  до $2^{64}-<!--\; -\; -->1$$2^{64} - 1$ ). Определим $N_w$$N_w$  как число 64-битных слов в ключе (и в блоке), тогда:

• Ключ шифрования $K\Rightarrow <!--\; \Rightarrow \; -->(k_0,k_1,\dots <!--\; \dots \; -->,k_{N_w-<!--\; -\; -->1})$$K \Rightarrow (k_0, k_1, \dots, k_{N_w-1})$ 
• Tweak-значение $T\Rightarrow <!--\; \Rightarrow \; -->(t_0,t_1)$$T \Rightarrow (t_0, t_1)$ 
• Открытый текст $P\Rightarrow <!--\; \Rightarrow \; -->(p_0,p_1,\dots <!--\; \dots \; -->,p_{N_w-<!--\; -\; -->1})$$P \Rightarrow (p_0, p_1, \dots, p_{N_w-1})$ 

Количество раундов, $N_r$$N_r$  для алгоритма Threefish определяется следующим образом:

Длина ключа/блока	$N_w$$N_w$	$N_r$$N_r$
256 бит	4	72
512 бит	8	72
1024 бит	16	80

Расписание ключейПравить

Алгоритм использует $\frac{N_r}{4}+1$$\frac{N_r}{4} + 1$  раундовых ключей. Дополним основной ключ и tweak-значение двумя 64-битными словами:

$k_{N_w}=C_{240}\oplus <!--\; \oplus \; -->k_0\oplus <!--\; \oplus \; -->k_1\oplus <!--\; \oplus \; -->\cdots <!--\; \cdots \; -->\oplus <!--\; \oplus \; -->k_{N_w-<!--\; -\; -->1}$$k_{N_w} = C_{240} \oplus k_0 \oplus k_1 \oplus \dots \oplus k_{N_w-1}$ ,  где   $C_{240}=\text{0x1bd11bdaa9fc1a22}$$C_{240} = \text{0x1bd11bdaa9fc1a22}$ 

$t_2=t_0\oplus <!--\; \oplus \; -->t_1$$t_2 = t_0 \oplus t_1$ 

Определим подключ $s$$s$  как $(k_{s,0},k_{s,1},\dots <!--\; \dots \; -->,k_{s,N_w-<!--\; -\; -->1})$$(k_{s,0}, k_{s,1}, \dots, k_{s,N_w-1})$ .
Все операции сложения выполняются по модулю $2^{64}$$2^{64}$ .

$k_{s, i} = \begin{cases} k_{(s+i) \bmod (N_w + 1)} & i = 0, \dots, N_w - 4 \\ k_{(s+i) \bmod (N_w + 1)} + t_{s \bmod 3} & i = N_w - 3 \\ k_{(s+i) \bmod (N_w + 1)} + t_{(s + 1) \bmod 3} & i = N_w - 2 \\ k_{(s+i) \bmod (N_w + 1)} + s & i = N_w - 1 \end{cases}$ 

Где $s=0,1,...,N_r/4$$s=0,1,...,N_{r}/4$ 

Функция MIXПравить

Нелинейная функция смешивания и перестановки ${\text{MIX}}_{d,j}$$\text{MIX}_{d,j}$  принимает на вход два аргумента $(x_0,x_1)$$(x_0, x_1)$  и возвращает $(y_0,y_1)$$(y_0, y_1)$ :

$y_0=(x_0+x_1)\mathrm{mod}{2}^{64}$$y_0 = (x_0 + x_1) \mod 2^{64}$ 

$y_1=(x_1⋘<!--\; ⋘\; -->R_{(dmod8),j})\oplus <!--\; \oplus \; -->y_0$$y_1 = (x_1 \lll R_{(d \bmod 8), j}) \oplus y_0$ 

Где   $⋘<!--\; ⋘\; -->$$\lll$    — оператор побитового циклического сдвига влево, а константа $R_{d,j}$$R_{d,j}$  определяется из таблицы:

$N_w$$N_w$	4	8	16
${}_d{\setminus <!--\; \setminus \; -->}^j$$_d \setminus ^j$	0	1	0	1	2	3	0	1	2	3	4	5	6	7
0	14	16	46	36	19	37	24	13	8	47	8	17	22	37
1	52	57	33	27	14	42	38	19	10	55	49	18	23	52
2	23	40	17	49	36	39	33	4	51	13	34	41	59	17
3	5	37	44	9	54	56	5	20	48	41	47	28	16	25
4	25	33	39	30	34	24	41	9	37	31	12	47	44	30
5	46	12	13	50	10	17	16	34	56	51	4	53	42	41
6	58	22	25	29	39	43	31	44	47	46	19	42	44	25
7	32	32	8	35	56	22	9	48	35	52	23	31	37	20

ЗашифрованиеПравить

Обозначим $V_{d,i},i=0,1,\dots <!--\; \dots \; -->,N_{w-<!--\; -\; -->1}$$V_{d,i}, i = 0,1,\dots,N_{w-1}$  внутреннее состояние алгоритма для раунда $d=0,1,\dots <!--\; \dots \; -->,N_r-<!--\; -\; -->1$$d = 0,1,\dots,N_r-1$ .
Начальное внутреннее состояние $V_{0,i}\Rightarrow <!--\; \Rightarrow \; -->(p_0,p_1,\dots <!--\; \dots \; -->,N_w-<!--\; -\; -->1)$$V_{0,i} \Rightarrow (p_0,p_1,\dots,N_w-1)$ .

Каждый раунд состоит из нескольких этапов. На первом этапе раунда к внутреннему состоянию добавляется раундовый ключ $k_{s,i}$$k_{s,i}$  как указанно ниже:

$e_{d,i}=(V_{d,i}+k_{d/4,i})\mathrm{mod}{2}^{64}$$e_{d, i} = (V_{d,i} + k_{d/4,i}) \mod 2^{64}$ ,   если   $d\mathrm{mod}4=0$$d \mod 4 = 0$ 

$e_{d,i}=V_{d,i}$$e_{d, i} = V_{d,i}$ ,   если   $d\mathrm{mod}4\ne <!--\; \ne \; -->0$$d \mod 4 \ne 0$ 

На следующем этапе раунда используется нелинейная функция ${\text{MIX}}_{d,j}$$\text{MIX}_{d,j}$ :

$(f_{d,2j},f_{d,2j+1})={\text{MIX}}_{d,j}(e_{d,2j},e_{d,2j+1})$$(f_{d,2j}, f_{d,2j+1}) = \text{MIX}_{d,j} (e_{d,2j}, e_{d,2j+1})$ ,    для    $j=0,1,\dots <!--\; \dots \; -->,\frac{N_w}{2}-<!--\; -\; -->1$$j = 0,1,\dots, \frac{N_w}{2}-1$ 

Следующее внутреннее состояние определяется как:

$V_{d+1,i}=f_{d,p(i)}$$V_{d+1,i} = f_{d,p(i)}$  ,    для    $i=0,1,\dots <!--\; \dots \; -->,N_w-<!--\; -\; -->1$$i = 0,1,\dots, N_w-1$ 

Функция перестановки 64-битных слов $p(i)$$p(i)$  определена в таблице ниже:

${}_{N_w}{\setminus <!--\; \setminus \; -->}^i$$_{N_w} \setminus ^i$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
4	0	3	2	1
8	2	1	4	7	6	5	0	3
16	0	9	2	13	6	11	4	15	10	7	12	3	14	5	8	1

После выполнения всех раундов выходом алгоритма является шифротекст $c_i$$c_{i}$ :

$c_i\Rightarrow <!--\; \Rightarrow \; -->(V_{N_r,i}+k_{N_r/4,i})\mathrm{mod}{2}^{64}$$c_i \Rightarrow (V_{N_r, i} + k_{N_r/4, i}) \mod 2^{64}$  , для  $i=0,1,\dots <!--\; \dots \; -->,N_w-<!--\; -\; -->1$$i = 0,1,\dots,N_w-1$ 

РасшифрованиеПравить

Для алгоритма Threefish процедура расшифрования обратна процедуре шифрования. Раундовые ключи используются в обратном порядке, и каждый раунд состоит из обратных операций. Вместо функции ${\text{MIX}}_{d,j}$$\text{MIX}_{d,j}$  используется функция ${\text{deMIX}}_{d,j}$$\text{deMIX}_{d,j}$ , которая выполняет операции вычитания по модулю $2^{64}$$2^{64}$  и побитовый циклический сдвиг вправо. Этапы каждого раунда расшифрования также выполняются в обратном порядке.

БезопасностьПравить

По заявлению авторов, алгоритм имеет более высокий уровень безопасности, чем AES. Существует атака на 25 из 72 раундов Threefish, в то время как для AES — на 6 из 10. Threefish имеет показатель фактора безопасности 2,9, в свою очередь, AES - всего 1,7

Для достижения полной диффузии шифру Threefish-256 достаточно 9 раундов, Threefish-512 — 10 раундов и Threefish-1024 — 11 раундов. Исходя из этого, 72 и 80 раундов, соответственно, в среднем, обеспечат лучшие результаты, чем существующие шифры.

В то же время алгоритм имеет гораздо более простую структуру и функцию преобразования, однако выполнение 72-80 раундов, по мнению исследователей, обеспечивает необходимую стойкость. Применяемый размер ключа от 256 до 1024 бит сводит на нет возможность полного перебора паролей при так называемой атаке грубой силой (brute force attack) на современном оборудовании.

СсылкиПравить

• Официальная страница Skein и Threefish (англ.)
• Информация по шифру Threefish
• Исходный код алгоритма Threefish-512 на языках C и Delphi
• Официальная спецификация алгоритмов Skein и Threefish (англ.)

См. такжеПравить

Skein — хеш-функция, основанная на Threefish