Trivium (шифр)

Trivium генерирует последовательность Z, так называемый ключевой поток, длинной вплоть до ${\displaystyle N\leq 2^{64}}$ бит. Для шифровки сообщения необходимо провести операцию XOR от сообщения и ключевого потока. Расшифровка производится аналогичным образом, выполняется операция XOR от шифротекста и ключевого потока.

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

${\displaystyle (s_{1},s_{2},...,s_{93})\leftarrow (K_{1},...,K_{80},0,...,0)}$

${\displaystyle (s_{94},s_{95},...,s_{177})\leftarrow (IV_{1},...,IV_{80},0,...,0)}$

${\displaystyle (s_{178},s_{179},...,s_{288})\leftarrow (0,...0,1,1,1)}$

${\displaystyle {\mbox{for}}\ i=1\ {\mbox{to}}\ 4\cdot 288\ {\mbox{do}}}$

${\displaystyle t_{1}\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171}}$

${\displaystyle t_{2}\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264}}$

${\displaystyle t_{3}\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69}}$

${\displaystyle (s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})}$

${\displaystyle (s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})}$

${\displaystyle (s_{178},s_{179},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})}$

${\displaystyle {\mbox{end for}}}$

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

0000000 e0 fb 26 bf 59 58 1b 05 7a 51 4e 2e 9f 23 7f c9
0000010 32 56 16 03 07 19 2d cf a8 e7 0f 79 b2 a1 cd e9
0000020 52 f7 03 92 68 02 38 b7 4c 2b 75 1a a2 9a 9a 59
0000030 55 28 98 49 74 6e 59 80 80 03 4c 1a a5 b5 f2 d4
0000040 34 69 bb 86 ca 52 15 b3 ae 80 12 69 73 55 9a 31
0000050 b2 6c 0e f5 16 40 20 d6 30 7f 4e 3f 48 16 dc 24
0000060 25 5c ad c4 10 a1 c9 1b bb e8 01 4e dc fc 2e 27
0000070 9e fa ae 02 a2 48 05 b2 2e fb f4 4f 27 76 56 27
0000080 3e 5e b7 06 4e e6 4a 57 7b ad a2 3a 1c 52 ff 48
0000090 f3 92 f8 87 ff 98 aa 87 e6 bf f6 19 38 3c ff 19
00000a0 3f 0a a5 fd 01 ec d0 d8 fa f0 fa 87 09 a1 4e ee
00000b0 63 29 9f 9b 31 ef 95 a5 c7 76 19 8d c7 e0 df 55
00000c0 1b 0f 50 e9 b8 91 85 ea 06 7b d5 2a ad 2b 77 f4
00000d0 ac 84 9b 6d 3f 2e a9 85 99 d7 04 95 02 33 fd f0
00000e0 b7 f8 5b 6e b7 c8 f0 b4 46 aa 20 cd a0 dd dd 4f

Генератор потока использует 15 бит из 288битного начального состояния для изменения 3х бит состояния и вычисления 1 бита ключевого потока ${\displaystyle z_{i}}$. В результате работы алгоритма может быть получено до ${\displaystyle N\leq 2^{64}}$ бит ключевого потока. Алгоритм может быть описан следующим псевдокодом.

${\displaystyle {\mbox{for}}\ i=1\ {\mbox{to}}\ N\ {\mbox{do}}}$

${\displaystyle t_{1}\leftarrow s_{66}+s_{93}}$

${\displaystyle t_{2}\leftarrow s_{162}+s_{177}}$

${\displaystyle t_{3}\leftarrow s_{243}+s_{288}}$

${\displaystyle z_{i}\leftarrow t_{1}+t_{2}+t_{3}}$

${\displaystyle t_{1}\leftarrow s_{66}+s_{91}\cdot s_{92}+s_{93}+s_{171}}$

${\displaystyle t_{2}\leftarrow s_{162}+s_{175}\cdot s_{176}+s_{177}+s_{264}}$

${\displaystyle t_{3}\leftarrow s_{243}+s_{286}\cdot s_{287}+s_{288}+s_{69}}$

${\displaystyle (s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})}$

${\displaystyle (s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})}$

${\displaystyle (s_{178},s_{179},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})}$

${\displaystyle {\mbox{end for}}}$

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

Период ключевого потока сложно определить, из-за нелинейного характера изменений начального состояния. Даже если открыть все триггеры AND, что приведёт к полностью линейной схеме, можно показать, что любая пара ключа и инициализирующего вектора приведёт к генерации ключевого потока с периодом порядка ${\displaystyle 2^{96-3}-1}$ (что уже превосходит требуемую длину ключевого потока ${\displaystyle 2^{64}}$).

Если же предположить, что Trivium начинает генерировать случайный ключевой поток, после небольшого количества итераций, то все сгенерированные последовательности, длинной до ${\displaystyle 2^{288}}$ будут равновероятны. А также вероятность того, что пара ключ/инициализирующий вектор сгенерируют ключевой поток с периодом меньше, чем ${\displaystyle 2^{80}}$ будет порядка ${\displaystyle 2^{-208}}$[2].

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

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

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

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

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