Trivium (шифр)

Перейти к навигацииПерейти к поиску
Структура шифра Trivium

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

Шифр был представлен в декабре 2008 года как часть портфолио европейского проекта eSTREAM, по профилю 2 (аппаратно ориентированные шифры). Авторами шифра являются Кристоф Де Канньер и Барт Пренел.

Данный потоковый шифр генерирует вплоть до бит выходного потока из 80 бит ключа и 80 бит IV (вектора инициализации). Это — самый простой шифр проекта eSTREAМ, который показывает отличные результаты по криптоустойчивости.

Trivium включен в стандарт ISO/IEC 29192-3 в качестве легковесного потокового шифра.

Описание

Изначальное состояние Trivium представляет собой 3 сдвиговых регистра суммарной длины в 288 бит. Каждый такт происходит изменение битов в регистрах сдвига путём нелинейной комбинации прямой и обратной связи. Для инициализации шифра ключ K и инициализирующий вектор IV записываются в 2 из 3х регистров и происходит исполнение алгоритма в течение 4х288 = 1152 раз, что гарантирует зависимость каждого бита начального состояния от каждого бита ключа и каждого бита инициализирующего вектора.

После прохождения стадии инициализации каждый такт генерируется новый член ключевого потока Z, который проходит процедуру XOR с следующим членом текста. Процедура расшифровки происходит в обратном порядке — каждый член шифротекста проходит процедуру XOR с каждым членом ключевого потока Z.[1]

Алгоритм

Потоковые шифры

Trivium генерирует последовательность Z, так называемый ключевой поток, длинной вплоть до бит. Для шифровки сообщения необходимо провести операцию XOR от сообщения и ключевого потока. Расшифровка производится аналогичным образом, выполняется операция XOR от шифротекста и ключевого потока.

Инициализация

Алгоритм инициализируется загрузкой 80битного ключа и 80битного инициализирующего вектора в 288битное начальное состояние. Инициализация может быть описана следующим псевдокодом.

Процедура инициализации гарантирует то, что каждый бит начального состояния зависит от каждого бита ключа и каждого бита инициализирующего вектора. Данный эффект достигается уже после 2х полных проходов (2*288 выполнений цикла). Ещё 2 прохода предназначены для усложнения битовых взаимосвязей. Для примера первые 128 байт ключевого потока Z, полученного от нулевых ключа и инициализирующего вектора, имеют примерно одинаковое количество равномерно распределённых 1 и 0. Даже при простейших и одинаковых ключах алгоритм Trivium выдает последовательность чисел, близкую к случайной.

Работа алгоритма

Генератор потока использует 15 бит из 288битного начального состояния для изменения 3х бит состояния и вычисления 1 бита ключевого потока . В результате работы алгоритма может быть получено до бит ключевого потока. Алгоритм может быть описан следующим псевдокодом.

В данном псевдокоде все вычисления производятся по модулю 2. То есть операции сложения и умножения являются операциями XOR и AND.

Период

Период ключевого потока сложно определить, из-за нелинейного характера изменений начального состояния. Даже если открыть все триггеры AND, что приведёт к полностью линейной схеме, можно показать, что любая пара ключа и инициализирующего вектора приведёт к генерации ключевого потока с периодом порядка (что уже превосходит требуемую длину ключевого потока ).

Если же предположить, что Trivium начинает генерировать случайный ключевой поток, после небольшого количества итераций, то все сгенерированные последовательности, длинной до будут равновероятны. А также вероятность того, что пара ключ/инициализирующий вектор сгенерируют ключевой поток с периодом меньше, чем будет порядка [2].

Шифры семейства Trivium

Модификации данного шифра отличаются количеством регистров сдвига и их длинами.

Univium

Поточный шифр Univium состоит из одного сдвигового регистра, для кодирования необходим только ключ длиной, не превышающий длину регистра.[1]

Bivium

Вместе с Trivium его авторы предложили шифр Bivium, в котором реализованы только 2 сдвиговых регистра суммарной длины в 177 бит. Процесс инициализации аналогичен Trivium. Каждый такт изменяются 2 бита состояния и формируется новый бит ключевого потока. По генерации ключевого потока Z различают 2 версии: Bivium-A и Bivium-B(Bivium). В Bivium-A реализована прямая зависимость нового члена Z от изменённого бита состояния , от отличии от неё в Bivium-B (Bivium) .[3]

Trivium-toy и Bivium-toy

Toy-версии были получены путём уменьшения длин регистров, что позволило снизить вычислительную сложность алгоритма, при этом сохраняя все математические свойства. Длина каждого регистра сокращалась в 3 раза, причем Bivium-toy также состояла только из двух регистров.

Каждая модификация шифра Trivium создана для упрощения его математического описания, что имеет больше учебную цель, нежели цель применить их в средствах защиты информации.[4]

Производительность

Стандартная аппаратная реализация алгоритма требует наличия 3488 логических элементов и производит 1 бит ключевого потока за 1 такт. Но, так как каждое новое состояние бита не изменяется по крайней мере в течение 64 раундов, то ещё 64 состояния могут быть сгенерированы параллельно при увеличении количества логических элементов до 5504. Также возможны различные вариации производительности в зависимости от количества использованных элементов.

Программная интерпретация данного алгоритма также достаточно эффективна. Реализация Trivium на языке C на процессоре AthlonXP 1600+ позволяет получить скорость шифрования более 2,4Мбит/с

Защищенность

В отличие от ранних потоковых шифров, как например RC4, алгоритм Trivium, кроме закрытого ключа (K) также имеет инициализирующий вектор (IV), который является открытым ключом. Применение IV позволяет проводить множество независимых сеансов шифровки/расшифровки используя всего лишь 1 ключ и несколько инициализирующих векторов (по одному для каждого сеанса). Также можно использовать несколько инициализирующих векторов для одного сеанса, используя для каждого нового сообщения новый IV

В данный момент не известно никаких методов атаки на данный алгоритм, которые были бы эффективнее последовательного перебора. Сложность проведения данной атаки зависит от длины сообщения и составляет порядка .

Существуют исследования методов атак (например кубическая атака[5]), которые близки по эффективности к перебору. Кроме того, существует метод атаки, позволяющий восстановить K из IV и ключевого потока. Сложность данной атаки равна и незначительно уменьшается при увеличении количества инициализирующих векторов, использовавшихся с одним ключом. Возможны также атаки с исследованием псевдослучайной последовательности ключевого потока с целью нахождения закономерностей и предсказания последующих бит потока, но данные атаки требуют решения сложных нелинейных уравнений. Наименьшая полученная сложность такой атаки составляет [6][7]

Методы исследования

Практически все достижения в области взлома Trivium представляют собой попытки применить атаки, удачно проведенные на усеченных версиях алгоритма[1]. Зачастую, в качестве исследуемого используется версия алгоритма Bivium, в котором используется всего 2 сдвиговых регистра суммарной длины 192 бита[1].

Примечания

  1. 1 2 3 4 Архивированная копия. Дата обращения: 23 декабря 2009. Архивировано 25 сентября 2018 года.
  2. Архивированная копия. Дата обращения: 23 декабря 2009. Архивировано 20 октября 2016 года.
  3. Two Trivial Attacks on Trivium | SpringerLink. Дата обращения: 27 июля 2018. Архивировано 27 июля 2018 года.
  4. Архивированная копия. Дата обращения: 10 марта 2017. Архивировано 12 марта 2017 года.
  5. Архивированная копия. Дата обращения: 23 декабря 2009. Архивировано 17 мая 2017 года.
  6. Архивированная копия. Дата обращения: 23 декабря 2009. Архивировано 26 августа 2016 года.
  7. Архивированная копия. Дата обращения: 23 декабря 2009. Архивировано 30 июля 2016 года.

Ссылки