Threefish

Threefish

General
Designers	Брюс Шнайер, Нильс Фергюсон, Стефан Лакс, Дуг Уайтинг, Михир Белларе, Тадаёши Коно, Джон Каллас, Джесси Уокер
Впервые опубликовано	2008
Относится к	Blowfish, Twofish
Сведения о шифре
Размеры ключа	256, 512 или 1024 бит. (размер ключа равен размеру блока)
Размеры блока	256, 512 или 1024 бит
Округление	72 (80 для размера блока 1024-бит)
Скорость	6.1 cpb на Core 2.

Threefish - это symmetric-key настраиваемый блочный шифр, разработанный как часть th e Хэш-функция Skein, запись в NIST hash function Competition. Threefish не использует S-блоки или другие таблицы поиска, чтобы избежать атак на время кэша ; его нелинейность возникает из-за чередования сложений с исключающим ИЛИ. В этом отношении он аналогичен Salsa20, TEA и кандидатам SHA-3 CubeHash и BLAKE.

Threefish и хеш Skein. функции были разработаны Брюсом Шнайером, Нильсом Фергюсоном, Стефаном Лаксом, Дугом Уайтингом, Михиром Белларе, Тадаёши Коно, Джоном Каллас и Джесси Уокер.

• 1 Описание шифра
  • 1.1 Ключевое расписание
  • 1.2 Функция смешивания
  • 1.3 Перестановка
  • 1.4 Полный раунд Threefish
  • 1.5 Заключительные операции
• 2 Безопасность
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

Threefish работает со словами из 64 бит (без знака Little endian целые числа ). $N\; w\; \in \; \{4,\; 8,\; 16\}\; \{\backslash \; displaystyle\; N\_\; \{w\}\; \backslash \; in\; \backslash \; \{4,8,16\; \backslash \}\}$- количество слов открытого текста, а также ключевых слов. Твик состоит из двух слов. Все сложения и вычитания определены по модулю $2\; 64\; \{\backslash \; displaystyle\; 2\; ^\; \{64\}\}$.

Ключевое расписание

Threefish использует $N\; r\; 4\; +\; 1\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{N\_\; \{r\}\}\; \{4\}\}\; +\; 1\}$различные клавиши раундов ($N\; r\; \{\backslash \; displaystyle\; N\_\; \{r\}\}$: количество раундов). Для вычисления этих ключей к исходным ключевым словам $k\; 0,\; k\; 1,\dots ,\; k\; добавляется\; дополнительное\; ключевое\; слово$ k\; N\; w\; \{\backslash \; displaystyle\; k\_\; \{N\_\; \{w\}\}\}$$. N w - 1 {\ displaystyle k_ {0}, k_ {1}, \ dots, k_ {N_ {w} -1}}. Дополнительное слово настройки $t\; 2\; \{\backslash \; displaystyle\; t\_\; \{2\}\}$также добавляется к словам настройки $t\; 0,\; t\; 1\; \{\backslash \; displaystyle\; t\_\; \{0\},\; t\_\; \{1\}\; \}$.

$k\; N\; w\; =\; C\; 240\; k\; 0\; \oplus \; k\; 1\; \oplus \; \cdots \; \oplus \; k\; N\; w\; -\; 1;\; C\; 240\; знак\; равно\; 0x1BD11BDAA9FC1A22\; \{\backslash \; displaystyle\; k\_\; \{N\_\; \{w\}\}\; =\; C\_\; \{240\}\; \backslash \; oplus\; k\_\; \{0\}\; \backslash \; oplus\; k\_\; \{1\}\; \backslash \; oplus\; \backslash \; dots\; \backslash \; oplus\; k\_\; \{N\_\; \{w\}\; -1\};\; \backslash \; quad\; C\_\; \{240\}\; =\; \{\backslash \; text\; \{0x1BD11BDAA9FC1A22\}\}\}$

$t\; 2\; =\; t\; 0\; \oplus \; t\; 1\; \{\backslash \; displaystyle\; t\_\; \{2\}\; =\; t\_\; \{0\}\; \backslash \; oplus\; t\_\; \{1\}\}$

Цель, казалось бы, произвольная константа $C\; 240\; \{\backslash \; displaystyle\; C\_\; \{240\}\}$предназначена для предотвращения некоторых атак, которые используют взаимосвязь между $k\; N\; w\; \{\backslash \; displaystyle\; k\_\; \{N\_\; \{w\}\}\}$и другие ключевые слова.

Круглые ключевые слова $ks,\; i\; \{\backslash \; displaystyle\; k\_\; \{s,\; i\}\}$теперь определены следующим образом:

$ks,\; i\; =\; \{k\; (s\; +\; i)\; mod\; (N\; w\; +\; 1)\; i\; =\; 0,\dots ,\; N\; w\; -\; 4\; k\; (s\; +\; i)\; mod\; (N\; w\; +\; 1)\; +\; ts\; mod\; 3\; i\; =\; N\; w\; -\; 3\; k\; (s\; +\; i)\; mod\; (\; N\; вес\; +\; 1)\; +\; T\; (s\; +\; 1)\; модуль\; 3\; я\; знак\; равно\; N\; вес\; -\; 2\; к\; (s\; +\; я)\; модуль\; (N\; вес\; +\; 1)\; +\; si\; =\; N\; вес\; -\; 1\; \{\backslash \; Displaystyle\; к\_\; \{s,\; я\}\; =\; \{\backslash \; begin\; \{case\}\; k\; \_\; \{(s\; +\; i)\; \{\backslash \; bmod\; \{(\}\}\; N\_\; \{w\}\; +1)\}\; i\; =\; 0,\; \backslash \; dots,\; N\_\; \{w\}\; -4\; \backslash \backslash \; k\; \_\; \{(s\; +\; i)\; \{\backslash \; bmod\; \{(\}\}\; N\_\; \{w\}\; +1)\}\; +\; t\_\; \{s\; \{\backslash \; bmod\; \{3\}\}\}\; i\; =\; N\_\; \{w\}\; -3\; \backslash \backslash \; k\; \_\; \{(s\; +\; i)\; \{\backslash \; bmod\; \{(\}\; \}\; N\_\; \{w\}\; +1)\}\; +\; t\; \_\; \{(s\; +\; 1)\; \{\backslash \; bmod\; \{3\}\}\}\; i\; =\; N\_\; \{w\}\; -2\; \backslash \backslash \; k\; \_\; \{(s\; +\; i)\; \{\backslash \; bmod\; \{(\}\}\; N\_\; \{w\}\; +1)\}\; +\; s\; i\; =\; N\_\; \{w\}\; -1\; \backslash \; end\; \{cases\}\}\}$

Здесь $s\; =\; 0,\; 1,\dots ,\; N\; r\; /\; 4\; \{\backslash \; displaystyle\; s\; =\; 0,1,\; \backslash \; dots,\; N\_\; \{r\}\; /\; 4\}$и $4\; s\; \{\backslash \; displaystyle\; 4s\}$- номер раунда, в котором используется ключ раунда.

Функция смешивания

Функция смешивания принимает кортеж слов $(x\; 0,\; x\; 1)\; \{\backslash \; displaystyle\; (x\_\; \{0\},\; x\_\; \{1\})\}$и возвращает другой кортеж слов $(y\; 0,\; y\; 1)\; \{\backslash \; displaystyle\; (y\_\; \{0\},\; y\_\; \{1\})\}$. Функция определяется следующим образом:

$y\; 0\; =\; x\; 0\; +\; x\; 1\; mod\; 2\; 64\; \{\backslash \; displaystyle\; y\_\; \{0\}\; =\; x\_\; \{0\}\; +\; x\_\; \{1\}\; \backslash \; mod\; 2\; ^\; \{64\}\}$

$y\; 1\; знак\; равно\; (Икс\; 1\; ⋘\; R\; (d\; mod\; 8),\; j)\; \oplus \; Y\; 0\; \{\backslash \; displaystyle\; y\_\; \{1\}\; =\; (x\_\; \{1\}\; \backslash \; lll\; R\; \_\; \{(d\; \{\backslash \; bmod\; \{8\}\}),\; j\})\; \backslash \; oplus\; y\_\; \{0\}\}$

$R\; d,\; j\; \{\backslash \; displaystyle\; R\_\; \{d,\; j\}\}$- фиксированный набор констант вращения, выбранный для достижения быстрого диффузии.

Перестановка

Шаг перестановки меняет местами слова в соответствии с постоянным шаблоном. Перестановка битового уровня не достигается на этом шаге, но в этом нет необходимости, поскольку функции MIX обеспечивают перестановки битового уровня в форме побитового вращения. Константы шага перестановки и вращения в функциях MIX выбираются таким образом, чтобы общий эффект был полным рассеиванием всех битов в блоке данных.

Поскольку эта перестановка фиксирована и не зависит от ключа, время, необходимое для вычисления, не дает информации о ключе или открытом тексте. Это важно, потому что на большинстве современных микропроцессоров оптимизация производительности может сделать время, необходимое для вычисления операции с массивом, зависимым от того, где данные хранятся в памяти. В шифрах, где поиск по массиву зависит либо от ключа, либо от открытого текста (как в случае шага подстановки в AES), он может сделать шифр уязвимым для временных атак, исследуя время, необходимое для шифрования. Таким образом, перестановка преднамеренно разработана таким образом, чтобы гарантировать, что она должна выполняться одним и тем же способом независимо от используемого ключа или зашифрованных данных.

Полный раунд Threefish

• , если $d\; mod\; 4\; =\; 0\; \{\; \backslash \; displaystyle\; d\; \backslash ;\; \{\backslash \; bmod\; \{\backslash ;\}\}\; 4\; =\; 0\}$круглый ключ $kd\; /\; 4,\; i\; \{\backslash \; displaystyle\; k\_\; \{d\; /\; 4,\; i\}\}$добавляется к слову $i\; \{\backslash \; displaystyle\; i\}$
• , функция смешивания применяется к последовательным словам, ширина поворота зависит от $d\; \{\backslash \; displaystyle\; d\}$и слова число
• слова переставляются с помощью перестановки, не зависящей от числа раунда.

Threefisdiv class="ht"56 и Threefish512 применяют этот раунд 72 раза ($d\; =\; 0,\; 1,\dots ,\; 71\; \{\backslash \; displaystyle\; d\; =\; 0,\; 1,\; \backslash \; точки,\; 71\}$). Threefish1024 применяет его 80 раз ($d\; =\; 0,\; 1,\dots ,\; 79\; \{\backslash \; displaystyle\; d\; =\; 0,1,\; \backslash \; dots,\; 79\}$).

Заключительные операции

После применения всех циклов к словам добавляется последний ключ цикла, и слова преобразуются обратно в строку байтов.

В октябре 2010 года была опубликована атака, которая сочетает в себе ротационный криптоанализ с атакой обратного ответа. Атака устанавливает распознающий ключ против 53 из 72 раундов в Threefish-256 и 57 из 72 раундов в Threefish-512. Это также влияет на хэш-функцию Skein. Это продолжение более ранней атаки, опубликованной в феврале, которая прерывает 39 и 42 раунда соответственно. В ответ на эту атаку команда Skein изменила константы вращения, используемые в Threefish, и, таким образом, константы расписания ключей для раунда 3 конкурса хэш-функций NIST.

В 2009 году связанный ключ Атака бумерангом против уменьшенной версии Threefish. Для версии с 32 раундами сложность времени составляет $2\; 226\; \{\backslash \; displaystyle\; 2\; ^\; \{226\}\}$, а сложность памяти составляет $2\; 12\; \{\backslash \; displaystyle\; 2\; ^\; \{12\}\}.$; для версии с 33 раундами сложность времени составляет $2\; 352.17\; \{\backslash \; displaystyle\; 2\; ^\; \{352.17\}\}$с незначительным использованием памяти. Атаки также работают против измененной версии Threefish: для 32-раундовой версии временная сложность составляет $2\; 222\; \{\backslash \; displaystyle\; 2\; ^\; \{222\}\}$, а сложность памяти составляет $2\; 12\; \{\backslash \; displaystyle\; 2\; ^\; \{12\}\}$; для версии из 33 раундов сложность времени составляет $2\; 355,5\; \{\backslash \; displaystyle\; 2\; ^\; \{355.5\}\}$с незначительным использованием памяти.

• Twofish
• Blowfish (шифр)

• «Семейство хеш-функций Skein» Домашняя страница семейства функций Skein-хеширования.