Threefish

Threefish — это семейство симметричных блочных шифров, разработанных в 2008 году группой криптографов под руководством Брюса Шнайера, Нильса Фергюсона, Стефана Люкс и Джесси Уокера. Threefish является одним из ключевых компонентов хеш-функции Skein, которая участвовала в финале конкурса SHA-3, организованного Национальным институтом стандартов и технологий США (NIST). Шифр ориентирован на высокую производительность как на 64-битных процессорах, так и на аппаратных реализациях, и отличается простотой конструкции, основанной на многократном применении операций сложения, исключающего ИЛИ (XOR) и циклического сдвига.

История

Разработка Threefish началась в рамках проекта по созданию хеш-функции Skein для конкурса SHA-3 (2007–2012). Команда разработчиков, известная как «The Skein Team», ставила перед собой цель создать не только стойкую хеш-функцию, но и универсальное криптографическое ядро, пригодное для построения различных примитивов. Threefish был спроектирован как блочный шифр с переменным размером блока (256, 512 и 1024 бита) и фиксированным числом раундов (72 для всех вариантов, кроме 256-битного, где используется 72 раунда). В 2009 году Skein прошёл во второй раунд конкурса SHA-3, а в 2010 году — в финал, но уступил победителю Keccak. Тем не менее, Threefish остаётся самостоятельным криптографическим примитивом, используемым в ряде проектов, включая системы шифрования дисков и протоколы аутентификации.

Алгоритм

Threefish относится к классу блочных шифров с сетью Фейстеля, но использует модифицированную структуру, называемую «сбалансированной сетью Фейстеля» с нелинейными преобразованиями на основе MIX-функций. Алгоритм оперирует 64-битными словами и не использует S-блоки, что делает его устойчивым к атакам, основанным на дифференциальном криптоанализе, за счёт высокой диффузии.

Структура раунда

Каждый раунд Threefish состоит из двух основных операций:

1. MIX-функция — нелинейное преобразование пары 64-битных слов с использованием сложения по модулю 2^64 и циклического сдвига. Для каждой пары слов (a, b) выполняется:

• a = a + b (mod 2^64)
• b = (b <<< R) XOR a, где R — фиксированная константа для каждого раунда и варианта шифра.

1. Перестановка слов — после выполнения MIX-функций для всех пар слова перемешиваются по фиксированной схеме, зависящей от размера блока.

Количество раундов фиксировано: 72 для всех размеров блока (256, 512, 1024 бита). После каждых четырёх раундов вставляется операция добавления раундового ключа (XOR с подключами).

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

Ключ шифрования имеет тот же размер, что и блок (256, 512 или 1024 бита). Из него генерируется 64-битное «слово-твик» (tweak), которое используется для модификации расписания ключей, что позволяет реализовать режимы работы с изменяемой длиной блока (например, для хеширования). Расширение ключа происходит по простой схеме: исходный ключ разбивается на 64-битные слова, к которым добавляется контрольное слово, вычисляемое как XOR всех слов ключа с константой. Раундовые подключи формируются путём циклического сдвига слов и добавления номера раунда.

Параметры

Криптостойкость

Threefish разработан с запасом прочности против известных криптоаналитических атак. На момент публикации (2008) авторы заявляли, что шифр обеспечивает стойкость, эквивалентную полному перебору ключа, при условии использования всех 72 раундов. В 2011 году группа исследователей (Дмитрий Ховратович, Кристиан Рехбергер и Алексис Рой) опубликовала работу, в которой показала возможность атаки на 32-раундовую версию Threefish-512 с использованием методов бумеранга и прямоугольного криптоанализа. Однако для полного 72-раундового шифра атаки не найдены. В 2012 году были предложены улучшенные методы дифференциального криптоанализа, позволяющие атаковать до 36 раундов, но они остаются теоретическими и не представляют практической угрозы.

Атаки на сокращённые версии

• 32 раунда: атака бумерангом (2011) — сложность около 2^220 операций.
• 36 раундов: дифференциальная атака (2012) — сложность около 2^240 операций.
• Полные 72 раунда: атак не найдено; стойкость оценивается как 2^512 (для Threefish-512) при полном переборе.

Применение

Threefish используется в основном как компонент хеш-функции Skein, но также применяется самостоятельно в некоторых криптографических системах:

• Шифрование дисков: Threefish-512 реализован в проекте TrueCrypt (в версии 7.0a и более поздних) в качестве одного из алгоритмов шифрования, хотя основным остаётся AES.
• Протоколы аутентификации: в составе Skein используется для построения MAC (код аутентификации сообщения) и PRNG (генератор псевдослучайных чисел).
• Криптографические библиотеки: Threefish поддерживается в библиотеках OpenSSL (с версии 1.1.0), Botan, Crypto++ и других.

Критика

Основные замечания к Threefish связаны с его относительной молодостью и меньшей изученностью по сравнению с AES. Отсутствие S-блоков и зависимость только от арифметических операций вызывают сомнения у части криптоаналитиков в отношении устойчивости к атакам по сторонним каналам (например, по времени выполнения сложения по модулю). Кроме того, фиксированное число раундов (72) для всех размеров блока считается избыточным для 256-битной версии, что снижает производительность на малых блоках. Тем не менее, авторы Skein аргументируют это необходимостью единой архитектуры для всех вариантов.

Интересные факты

• Название «Threefish» происходит от числа 3 (три) и слова «fish» (рыба), что отсылает к трём основным операциям шифра: сложение, XOR и сдвиг.
• Threefish не использует таблицы подстановок (S-блоки), что делает его удобным для реализации на микроконтроллерах с ограниченной памятью.
• В 2011 году в рамках проекта «Skein» была предложена модификация Threefish с увеличенным до 80 раундов числом для повышения запаса прочности, но она не была принята.

Источники

1. Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellovin, S., Kohno, T., Callas, J. (2008). The Skein Hash Function Family. Submission to NIST SHA-3 competition.
2. Khovratovich, D., Rechberger, C., Roy, A. (2011). Boomerang Attacks on BLAKE and Skein. CRYPTO 2011.
3. NIST (2012). SHA-3 Finalists: Skein. NIST IR 7896.
4. Schneier, B. (2009). The Skein Hash Function. IEEE Security & Privacy, 7(5), 78–80.
5. TrueCrypt Foundation (2012). TrueCrypt User’s Guide. Version 7.1a.