Trivium (шифр)

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

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

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

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

Описание

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

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

Алгоритм

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

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

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

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

<math>(s_1, s_2,..., s_{93}) \leftarrow (K_1,..., K_{80}, 0,..., 0)</math>

<math>(s_{94}, s_{95},..., s_{177}) \leftarrow (IV_1,..., IV_{80}, 0,..., 0)</math>

<math>(s_{178}, s_{179},..., s_{288}) \leftarrow (0,...0, 1, 1, 1) </math>

<math>\mbox{for}\ i = 1\ \mbox{to}\ 4\cdot 288\ \mbox{do} </math>

<math> t_1 \leftarrow s_{66} + s_{91}\cdot s_{92}+ s_{93}+s_{171} </math>

<math> t_2 \leftarrow s_{162} + s_{175}\cdot s_{176}+ s_{177} + s_{264} </math>

<math> t_3 \leftarrow s_{243}+ s_{286}\cdot s_{287} + s_{288}+ s_{69}</math>

 

<math>(s_1, s_2,..., s_{93})\leftarrow (t_3, s_1,..., s_{92})</math>

<math>(s_{94}, s_{95},..., s_{177})\leftarrow (t_1, s_{94},..., s_{176})</math>

<math>(s_{178}, s_{179},..., s_{288}) \leftarrow (t_2, s_{178},..., s_{287})</math>

<math>\mbox{end for}</math>

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

Первые 128 байт ключевого потока, сгенерированные от нулевых K и IV в 16тиричной системе счисления

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

Как можно заметить, после 4х циклов инициализации единицы, записанные в ячейки <math>s_{286}</math>, <math>s_{287}</math> и <math>s_{288}</math> повлияли на все остальные биты начального состояния, и, таким образом, даже при простейших и одинаковых ключах каждый байт сообщения будет изменен в результате работы алгоритма шифрования.

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

Генератор потока использует 15 бит из 288битного начального состояния для изменения 3х бит состояния и вычисления 1 бита ключевого потока <math>z_i</math>. В результате работы алгоритма может быть получено до <math>N\le 2^{64}</math> бит ключевого потока. Алгоритм может быть описан следующим псевдокодом.

<math>\mbox{for}\ i=1\ \mbox{to}\ N\ \mbox{do}</math>

<math>t_1\leftarrow s_{66}+s_{93}</math>

<math>t_2\leftarrow s_{162}+s_{177}</math>

<math>t_3\leftarrow s_{243}+s_{288}</math>

 

<math>z_i\leftarrow t_1+t_2+t_3</math>

 

<math> t_1 \leftarrow s_{66} + s_{91}\cdot s_{92}+ s_{93}+s_{171} </math>

<math> t_2 \leftarrow s_{162} + s_{175}\cdot s_{176}+ s_{177} + s_{264} </math>

<math> t_3 \leftarrow s_{243}+ s_{286}\cdot s_{287} + s_{288}+ s_{69}</math>

 

<math>(s_1, s_2,..., s_{93})\leftarrow (t_3, s_1,..., s_{92})</math>

<math>(s_{94}, s_{95},..., s_{177})\leftarrow (t_1, s_{94},..., s_{176})</math>

<math>(s_{178}, s_{179},..., s_{288}) \leftarrow (t_2, s_{178},..., s_{287})</math>

<math>\mbox{end for}</math>

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

Период

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

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

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

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

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

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

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

В данный момент не известно никаких методов атаки на данный алгоритм, которые были бы эффективнее последовательного перебора (или брутфорса (англ. brute force)). Сложность проведения данной атаки зависит от длины сообщения и составляет порядка <math>2^{120}</math>.

Существуют исследования методов атак (например кубическая атака), которые близки по эффективности к перебору. Кроме того, существует метод атаки, позволяющий восстановить K из IV и ключевого потока. Сложность данной атаки равна <math>2^{135}</math> и незначительно уменьшается при увеличении количества инициализирующих векторов, использовавшихся с одним ключом. Возможны также атаки с исследованием псевдослучайной последовательности ключевого потока с целью нахождения закономерностей и предсказания последующих бит потока, но данные атаки требуют решения сложных нелинейных уравнений. Наименьшая полученная сложность такой атаки составляет <math>2^{164}</math>

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

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

Ссылки

• [www.ecrypt.eu.org/stream/triviumpf.html Trivium на странице проекта eSTREAM ]
• [www.ecrypt.eu.org/stream/svn/viewcvs.cgi/ecrypt/trunk/submissions/trivium/ Описание алгоритма на странице проекта eSTREAM ]
• [www.ecrypt.eu.org/stream/papersdir/2006/021.pdf Принципы построения потоковых шифров ]

Отрывок, характеризующий Trivium (шифр)

Пьер смотрел то вниз по полю, по которому в нынешнее утро разъездились повозки и верховые, то вдаль за реку, то на собачонку, притворявшуюся, что она не на шутку хочет укусить его, то на свои босые ноги, которые он с удовольствием переставлял в различные положения, пошевеливая грязными, толстыми, большими пальцами. И всякий раз, как он взглядывал на свои босые ноги, на лице его пробегала улыбка оживления и самодовольства. Вид этих босых ног напоминал ему все то, что он пережил и понял за это время, и воспоминание это было ему приятно.
Погода уже несколько дней стояла тихая, ясная, с легкими заморозками по утрам – так называемое бабье лето.
В воздухе, на солнце, было тепло, и тепло это с крепительной свежестью утреннего заморозка, еще чувствовавшегося в воздухе, было особенно приятно.
На всем, и на дальних и на ближних предметах, лежал тот волшебно хрустальный блеск, который бывает только в эту пору осени. Вдалеке виднелись Воробьевы горы, с деревнею, церковью и большим белым домом. И оголенные деревья, и песок, и камни, и крыши домов, и зеленый шпиль церкви, и углы дальнего белого дома – все это неестественно отчетливо, тончайшими линиями вырезалось в прозрачном воздухе. Вблизи виднелись знакомые развалины полуобгорелого барского дома, занимаемого французами, с темно зелеными еще кустами сирени, росшими по ограде. И даже этот разваленный и загаженный дом, отталкивающий своим безобразием в пасмурную погоду, теперь, в ярком, неподвижном блеске, казался чем то успокоительно прекрасным.
Французский капрал, по домашнему расстегнутый, в колпаке, с коротенькой трубкой в зубах, вышел из за угла балагана и, дружески подмигнув, подошел к Пьеру.
– Quel soleil, hein, monsieur Kiril? (так звали Пьера все французы). On dirait le printemps. [Каково солнце, а, господин Кирил? Точно весна.] – И капрал прислонился к двери и предложил Пьеру трубку, несмотря на то, что всегда он ее предлагал и всегда Пьер отказывался.
– Si l'on marchait par un temps comme celui la… [В такую бы погоду в поход идти…] – начал он.
Пьер расспросил его, что слышно о выступлении, и капрал рассказал, что почти все войска выступают и что нынче должен быть приказ и о пленных. В балагане, в котором был Пьер, один из солдат, Соколов, был при смерти болен, и Пьер сказал капралу, что надо распорядиться этим солдатом. Капрал сказал, что Пьер может быть спокоен, что на это есть подвижной и постоянный госпитали, и что о больных будет распоряжение, и что вообще все, что только может случиться, все предвидено начальством.
– Et puis, monsieur Kiril, vous n'avez qu'a dire un mot au capitaine, vous savez. Oh, c'est un… qui n'oublie jamais rien. Dites au capitaine quand il fera sa tournee, il fera tout pour vous… [И потом, господин Кирил, вам стоит сказать слово капитану, вы знаете… Это такой… ничего не забывает. Скажите капитану, когда он будет делать обход; он все для вас сделает…]
Капитан, про которого говорил капрал, почасту и подолгу беседовал с Пьером и оказывал ему всякого рода снисхождения.
– Vois tu, St. Thomas, qu'il me disait l'autre jour: Kiril c'est un homme qui a de l'instruction, qui parle francais; c'est un seigneur russe, qui a eu des malheurs, mais c'est un homme. Et il s'y entend le… S'il demande quelque chose, qu'il me dise, il n'y a pas de refus. Quand on a fait ses etudes, voyez vous, on aime l'instruction et les gens comme il faut. C'est pour vous, que je dis cela, monsieur Kiril. Dans l'affaire de l'autre jour si ce n'etait grace a vous, ca aurait fini mal. [Вот, клянусь святым Фомою, он мне говорил однажды: Кирил – это человек образованный, говорит по французски; это русский барин, с которым случилось несчастие, но он человек. Он знает толк… Если ему что нужно, отказа нет. Когда учился кой чему, то любишь просвещение и людей благовоспитанных. Это я про вас говорю, господин Кирил. Намедни, если бы не вы, то худо бы кончилось.]
И, поболтав еще несколько времени, капрал ушел. (Дело, случившееся намедни, о котором упоминал капрал, была драка между пленными и французами, в которой Пьеру удалось усмирить своих товарищей.) Несколько человек пленных слушали разговор Пьера с капралом и тотчас же стали спрашивать, что он сказал. В то время как Пьер рассказывал своим товарищам то, что капрал сказал о выступлении, к двери балагана подошел худощавый, желтый и оборванный французский солдат. Быстрым и робким движением приподняв пальцы ко лбу в знак поклона, он обратился к Пьеру и спросил его, в этом ли балагане солдат Platoche, которому он отдал шить рубаху.
С неделю тому назад французы получили сапожный товар и полотно и роздали шить сапоги и рубахи пленным солдатам.
– Готово, готово, соколик! – сказал Каратаев, выходя с аккуратно сложенной рубахой.
Каратаев, по случаю тепла и для удобства работы, был в одних портках и в черной, как земля, продранной рубашке. Волоса его, как это делают мастеровые, были обвязаны мочалочкой, и круглое лицо его казалось еще круглее и миловиднее.
– Уговорец – делу родной братец. Как сказал к пятнице, так и сделал, – говорил Платон, улыбаясь и развертывая сшитую им рубашку.
Француз беспокойно оглянулся и, как будто преодолев сомнение, быстро скинул мундир и надел рубаху. Под мундиром на французе не было рубахи, а на голое, желтое, худое тело был надет длинный, засаленный, шелковый с цветочками жилет. Француз, видимо, боялся, чтобы пленные, смотревшие на него, не засмеялись, и поспешно сунул голову в рубашку. Никто из пленных не сказал ни слова.
– Вишь, в самый раз, – приговаривал Платон, обдергивая рубаху. Француз, просунув голову и руки, не поднимая глаз, оглядывал на себе рубашку и рассматривал шов.
– Что ж, соколик, ведь это не швальня, и струмента настоящего нет; а сказано: без снасти и вша не убьешь, – говорил Платон, кругло улыбаясь и, видимо, сам радуясь на свою работу.
– C'est bien, c'est bien, merci, mais vous devez avoir de la toile de reste? [Хорошо, хорошо, спасибо, а полотно где, что осталось?] – сказал француз.
– Она еще ладнее будет, как ты на тело то наденешь, – говорил Каратаев, продолжая радоваться на свое произведение. – Вот и хорошо и приятно будет.
– Merci, merci, mon vieux, le reste?.. – повторил француз, улыбаясь, и, достав ассигнацию, дал Каратаеву, – mais le reste… [Спасибо, спасибо, любезный, а остаток то где?.. Остаток то давай.]
Пьер видел, что Платон не хотел понимать того, что говорил француз, и, не вмешиваясь, смотрел на них. Каратаев поблагодарил за деньги и продолжал любоваться своею работой. Француз настаивал на остатках и попросил Пьера перевести то, что он говорил.
– На что же ему остатки то? – сказал Каратаев. – Нам подверточки то важные бы вышли. Ну, да бог с ним. – И Каратаев с вдруг изменившимся, грустным лицом достал из за пазухи сверточек обрезков и, не глядя на него, подал французу. – Эхма! – проговорил Каратаев и пошел назад. Француз поглядел на полотно, задумался, взглянул вопросительно на Пьера, и как будто взгляд Пьера что то сказал ему.
– Platoche, dites donc, Platoche, – вдруг покраснев, крикнул француз пискливым голосом. – Gardez pour vous, [Платош, а Платош. Возьми себе.] – сказал он, подавая обрезки, повернулся и ушел.
– Вот поди ты, – сказал Каратаев, покачивая головой. – Говорят, нехристи, а тоже душа есть. То то старички говаривали: потная рука торовата, сухая неподатлива. Сам голый, а вот отдал же. – Каратаев, задумчиво улыбаясь и глядя на обрезки, помолчал несколько времени. – А подверточки, дружок, важнеющие выдут, – сказал он и вернулся в балаган.


Прошло четыре недели с тех пор, как Пьер был в плену. Несмотря на то, что французы предлагали перевести его из солдатского балагана в офицерский, он остался в том балагане, в который поступил с первого дня.
В разоренной и сожженной Москве Пьер испытал почти крайние пределы лишений, которые может переносить человек; но, благодаря своему сильному сложению и здоровью, которого он не сознавал до сих пор, и в особенности благодаря тому, что эти лишения подходили так незаметно, что нельзя было сказать, когда они начались, он переносил не только легко, но и радостно свое положение. И именно в это то самое время он получил то спокойствие и довольство собой, к которым он тщетно стремился прежде. Он долго в своей жизни искал с разных сторон этого успокоения, согласия с самим собою, того, что так поразило его в солдатах в Бородинском сражении, – он искал этого в филантропии, в масонстве, в рассеянии светской жизни, в вине, в геройском подвиге самопожертвования, в романтической любви к Наташе; он искал этого путем мысли, и все эти искания и попытки все обманули его. И он, сам не думая о том, получил это успокоение и это согласие с самим собою только через ужас смерти, через лишения и через то, что он понял в Каратаеве. Те страшные минуты, которые он пережил во время казни, как будто смыли навсегда из его воображения и воспоминания тревожные мысли и чувства, прежде казавшиеся ему важными. Ему не приходило и мысли ни о России, ни о войне, ни о политике, ни о Наполеоне. Ему очевидно было, что все это не касалось его, что он не призван был и потому не мог судить обо всем этом. «России да лету – союзу нету», – повторял он слова Каратаева, и эти слова странно успокоивали его. Ему казалось теперь непонятным и даже смешным его намерение убить Наполеона и его вычисления о кабалистическом числе и звере Апокалипсиса. Озлобление его против жены и тревога о том, чтобы не было посрамлено его имя, теперь казались ему не только ничтожны, но забавны. Что ему было за дело до того, что эта женщина вела там где то ту жизнь, которая ей нравилась? Кому, в особенности ему, какое дело было до того, что узнают или не узнают, что имя их пленного было граф Безухов?