Введение
Поточный шифр
Trivium — это синхронный поточный шифр, разработанный для обеспечения гибкого баланса между скоростью и количеством логических элементов в аппаратной реализации, а также достаточно эффективной программной реализации. Trivium был представлен авторами, Кристофом Де Каньером и Бартом Пренелем, в Profile II (аппаратное обеспечение) конкурса eSTREAM и был выбран проектом eSTREAM в качестве части портфеля аппаратных шифров с минимальной площадью (Profile 2). Он не запатентован и был стандартизирован как международный стандарт в соответствии с ISO/IEC 29192-3. Он генерирует до 264 бит выходных данных из 80-битного ключа и 80-битного вектора инициализации (IV). Это самый простой участник конкурса eSTREAM; несмотря на замечательную устойчивость к криптоанализу, обусловленную его простотой и производительностью, недавние атаки указывают на довольно небольшой запас прочности.
Описание
288-битное внутреннее состояние Trivium состоит из трех регистров сдвига разной длины. В каждом раунде бит сдвигается в каждый из трех регистров сдвига, используя нелинейную комбинацию точек отбора из этого и еще одного регистра; при этом генерируется один бит выходных данных. Для инициализации шифра ключ и IV записываются в два регистра сдвига, а остальные биты инициализируются фиксированным шаблоном; затем состояние шифра обновляется 4 × 288 = 1152 раза, так что каждый бит внутреннего состояния зависит от каждого бита ключа и IV сложным нелинейным образом. На первых 65 битах каждого регистра сдвига точки отбора отсутствуют, поэтому каждый новый бит состояния не используется в течение как минимум 65 раундов после его генерации. Это обеспечивает высокую производительность Trivium в программном обеспечении и гибкость при аппаратной реализации.
Выступление
Простая аппаратная реализация Trivium потребует 3488 логических элементов и будет генерировать один бит за такт. Однако, поскольку каждый бит состояния не используется как минимум в течение 64 раундов, 64 бита состояния могут генерироваться параллельно, что потребует немного больше аппаратных ресурсов – 5504 элемента. Возможны и другие компромиссы между скоростью и занимаемой площадью. Это же свойство позволяет эффективно реализовать алгоритм побитово в программном обеспечении; тестирование производительности, проведенное eSTREAM, показало скорость пакетного шифрования около 4 циклов/байт на некоторых платформах x86, что сравнимо с 19 циклами/байт эталонной реализации AES на той же платформе.
Безопасность
По состоянию на 2015 год не известно криптоаналитических атак, превосходящих атаку полным перебором, однако существует несколько атак, близких к этому. Атака на кубик требует 268 шагов для взлома варианта Trivium, в котором число раундов инициализации сокращено до 799. Ранее другие авторы предполагали, что эти методы могут привести к взлому 1100 раундов инициализации или, "возможно, даже исходного шифра". Это основано на атаке Майкла Вильхабера, которая взламывает 576 раундов инициализации всего за 212,3 шага. Другая атака восстанавливает внутреннее состояние (и, следовательно, ключ) полного шифра примерно за 289,5 шагов (где каждый шаг приблизительно соответствует стоимости одной попытки при полном переборе). Урезанные варианты Trivium, использующие те же принципы проектирования, были взломаны с применением метода решения уравнений. Эти атаки улучшают хорошо известную атаку, основанную на компромиссе между временем и памятью, для потоковых шифров, которая в случае 288-битного внутреннего состояния Trivium потребовала бы 2144 шага, и показывают, что вариант Trivium, который не вносил никаких изменений, кроме увеличения длины ключа сверх 80 бит, установленных профилем eSTREAM 2, был бы небезопасен. Используя оптимизированную стратегию решения, можно дополнительно снизить сложность восстановления состояния до 2132 шагов. Подробное обоснование конструкции Trivium приведено в статье "Конструкция потокового шифра, вдохновленная принципами проектирования блочных шифров".