Threefish

Поделись знанием:
Перейти к: навигация, поиск
Threefish
Создатель:

Группа специалистов во главе с Брюсом Шнайером

Создан:

2008 г.

Опубликован:

2008 г.

Размер ключа:

256/512/1024 бит

Размер блока:

256/512/1024 бит

Число раундов:

72 (80 при ключе 1024 бит)

Тип:

Подстановочно-перестановочная сеть

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





Структура алгоритма

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

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

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

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

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

Определения

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

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

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

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

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

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

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

Расписание ключей

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

<math> k_{N_w} = C_{240} \oplus k_0 \oplus k_1 \oplus \dots \oplus k_{N_w-1}</math>,  где   <math>C_{240} = \text{0x1bd11bdaa9fc1a22}</math>

<math> t_2 = t_0 \oplus t_1</math>


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

<math> 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} </math>

Функция MIX

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

<math>y_0 = (x_0 + x_1) \mod 2^{64}</math>
<math>y_1 = (x_1 \lll R_{(d \bmod 8), j}) \oplus y_0</math>

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

<math>N_w</math> 4 8 16
<math>_d \setminus ^j</math> 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

Шифрование

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

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

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

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

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

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

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

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

<math>_{N_w} \setminus ^i</math> 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


После выполнения всех раундов выходом алгоритма является шифротекст <math>c_i</math>:

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

Дешифрование

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

Безопасность

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

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

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

Напишите отзыв о статье "Threefish"

Ссылки

  • [www.schneier.com/skein.html Официальная страница Skein и Threefish (англ.)]
  • [www.pgpru.com/novosti/2008/heshfunkcijaskeiniblochnyjjshifrthreefish Информация по шифру Threefish]
  • [cartman-cipher.narod.ru/mirror/threefish512.zip Исходный код алгоритма Threefish-512 на языках C и Delphi]
  • [www.schneier.com/skein.pdf Официальная спецификация алгоритмов Skein и Threefish (англ.)]

См. также

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

Примечания

  1. Skein опережает в два раза SHA-512 и входит в пятерку наиболее быстрых хэш-функций -кандидатов SHA-3 на 64-битной архитектуре
  2. [www.schneier.com/skein.pdf Официальная спецификация алгоритмов Skein и Threefish  (англ.)]
  3. [www.schneier.com/blog/archives/2008/10/the_skein_hash.html Информация по шифру в статье «The Skein Hash Function»]
  4. [www.schneier.com/skein1.1.pdf The Skein Hash Function Family  (англ.)]

Отрывок, характеризующий Threefish

– Как случится, – сказал Ростов.
– Говори ей вы, пожалуйста, я тебе после скажу.
– Да что же?
– Ну я теперь скажу. Ты знаешь, что Соня мой друг, такой друг, что я руку сожгу для нее. Вот посмотри. – Она засучила свой кисейный рукав и показала на своей длинной, худой и нежной ручке под плечом, гораздо выше локтя (в том месте, которое закрыто бывает и бальными платьями) красную метину.
– Это я сожгла, чтобы доказать ей любовь. Просто линейку разожгла на огне, да и прижала.
Сидя в своей прежней классной комнате, на диване с подушечками на ручках, и глядя в эти отчаянно оживленные глаза Наташи, Ростов опять вошел в тот свой семейный, детский мир, который не имел ни для кого никакого смысла, кроме как для него, но который доставлял ему одни из лучших наслаждений в жизни; и сожжение руки линейкой, для показания любви, показалось ему не бесполезно: он понимал и не удивлялся этому.
– Так что же? только? – спросил он.
– Ну так дружны, так дружны! Это что, глупости – линейкой; но мы навсегда друзья. Она кого полюбит, так навсегда; а я этого не понимаю, я забуду сейчас.
– Ну так что же?
– Да, так она любит меня и тебя. – Наташа вдруг покраснела, – ну ты помнишь, перед отъездом… Так она говорит, что ты это всё забудь… Она сказала: я буду любить его всегда, а он пускай будет свободен. Ведь правда, что это отлично, благородно! – Да, да? очень благородно? да? – спрашивала Наташа так серьезно и взволнованно, что видно было, что то, что она говорила теперь, она прежде говорила со слезами.
Ростов задумался.
– Я ни в чем не беру назад своего слова, – сказал он. – И потом, Соня такая прелесть, что какой же дурак станет отказываться от своего счастия?
– Нет, нет, – закричала Наташа. – Мы про это уже с нею говорили. Мы знали, что ты это скажешь. Но это нельзя, потому что, понимаешь, ежели ты так говоришь – считаешь себя связанным словом, то выходит, что она как будто нарочно это сказала. Выходит, что ты всё таки насильно на ней женишься, и выходит совсем не то.
Ростов видел, что всё это было хорошо придумано ими. Соня и вчера поразила его своей красотой. Нынче, увидав ее мельком, она ему показалась еще лучше. Она была прелестная 16 тилетняя девочка, очевидно страстно его любящая (в этом он не сомневался ни на минуту). Отчего же ему было не любить ее теперь, и не жениться даже, думал Ростов, но теперь столько еще других радостей и занятий! «Да, они это прекрасно придумали», подумал он, «надо оставаться свободным».
– Ну и прекрасно, – сказал он, – после поговорим. Ах как я тебе рад! – прибавил он.
– Ну, а что же ты, Борису не изменила? – спросил брат.
– Вот глупости! – смеясь крикнула Наташа. – Ни об нем и ни о ком я не думаю и знать не хочу.
– Вот как! Так ты что же?
– Я? – переспросила Наташа, и счастливая улыбка осветила ее лицо. – Ты видел Duport'a?
– Нет.
– Знаменитого Дюпора, танцовщика не видал? Ну так ты не поймешь. Я вот что такое. – Наташа взяла, округлив руки, свою юбку, как танцуют, отбежала несколько шагов, перевернулась, сделала антраша, побила ножкой об ножку и, став на самые кончики носков, прошла несколько шагов.
– Ведь стою? ведь вот, – говорила она; но не удержалась на цыпочках. – Так вот я что такое! Никогда ни за кого не пойду замуж, а пойду в танцовщицы. Только никому не говори.
Ростов так громко и весело захохотал, что Денисову из своей комнаты стало завидно, и Наташа не могла удержаться, засмеялась с ним вместе. – Нет, ведь хорошо? – всё говорила она.
– Хорошо, за Бориса уже не хочешь выходить замуж?
Наташа вспыхнула. – Я не хочу ни за кого замуж итти. Я ему то же самое скажу, когда увижу.
– Вот как! – сказал Ростов.
– Ну, да, это всё пустяки, – продолжала болтать Наташа. – А что Денисов хороший? – спросила она.
– Хороший.
– Ну и прощай, одевайся. Он страшный, Денисов?
– Отчего страшный? – спросил Nicolas. – Нет. Васька славный.
– Ты его Васькой зовешь – странно. А, что он очень хорош?
– Очень хорош.
– Ну, приходи скорей чай пить. Все вместе.
И Наташа встала на цыпочках и прошлась из комнаты так, как делают танцовщицы, но улыбаясь так, как только улыбаются счастливые 15 летние девочки. Встретившись в гостиной с Соней, Ростов покраснел. Он не знал, как обойтись с ней. Вчера они поцеловались в первую минуту радости свидания, но нынче они чувствовали, что нельзя было этого сделать; он чувствовал, что все, и мать и сестры, смотрели на него вопросительно и от него ожидали, как он поведет себя с нею. Он поцеловал ее руку и назвал ее вы – Соня . Но глаза их, встретившись, сказали друг другу «ты» и нежно поцеловались. Она просила своим взглядом у него прощения за то, что в посольстве Наташи она смела напомнить ему о его обещании и благодарила его за его любовь. Он своим взглядом благодарил ее за предложение свободы и говорил, что так ли, иначе ли, он никогда не перестанет любить ее, потому что нельзя не любить ее.
– Как однако странно, – сказала Вера, выбрав общую минуту молчания, – что Соня с Николенькой теперь встретились на вы и как чужие. – Замечание Веры было справедливо, как и все ее замечания; но как и от большей части ее замечаний всем сделалось неловко, и не только Соня, Николай и Наташа, но и старая графиня, которая боялась этой любви сына к Соне, могущей лишить его блестящей партии, тоже покраснела, как девочка. Денисов, к удивлению Ростова, в новом мундире, напомаженный и надушенный, явился в гостиную таким же щеголем, каким он был в сражениях, и таким любезным с дамами и кавалерами, каким Ростов никак не ожидал его видеть.


Вернувшись в Москву из армии, Николай Ростов был принят домашними как лучший сын, герой и ненаглядный Николушка; родными – как милый, приятный и почтительный молодой человек; знакомыми – как красивый гусарский поручик, ловкий танцор и один из лучших женихов Москвы.
Знакомство у Ростовых была вся Москва; денег в нынешний год у старого графа было достаточно, потому что были перезаложены все имения, и потому Николушка, заведя своего собственного рысака и самые модные рейтузы, особенные, каких ни у кого еще в Москве не было, и сапоги, самые модные, с самыми острыми носками и маленькими серебряными шпорами, проводил время очень весело. Ростов, вернувшись домой, испытал приятное чувство после некоторого промежутка времени примеривания себя к старым условиям жизни. Ему казалось, что он очень возмужал и вырос. Отчаяние за невыдержанный из закона Божьего экзамен, занимание денег у Гаврилы на извозчика, тайные поцелуи с Соней, он про всё это вспоминал, как про ребячество, от которого он неизмеримо был далек теперь. Теперь он – гусарский поручик в серебряном ментике, с солдатским Георгием, готовит своего рысака на бег, вместе с известными охотниками, пожилыми, почтенными. У него знакомая дама на бульваре, к которой он ездит вечером. Он дирижировал мазурку на бале у Архаровых, разговаривал о войне с фельдмаршалом Каменским, бывал в английском клубе, и был на ты с одним сорокалетним полковником, с которым познакомил его Денисов.
Страсть его к государю несколько ослабела в Москве, так как он за это время не видал его. Но он часто рассказывал о государе, о своей любви к нему, давая чувствовать, что он еще не всё рассказывает, что что то еще есть в его чувстве к государю, что не может быть всем понятно; и от всей души разделял общее в то время в Москве чувство обожания к императору Александру Павловичу, которому в Москве в то время было дано наименование ангела во плоти.