Тривиум (шифр)
Trivium — это синхронный поточный шифр, разработанный для обеспечения гибкого компромисса между скоростью и количеством шлюзов в аппаратном обеспечении, а также достаточно эффективной программной реализации.
Trivium был представлен на Профиль II (аппаратное обеспечение) конкурса eSTREAM его авторами Кристофом Де Каньером и Бартом Пренелем и был выбран как часть портфолио аппаратных шифров малой площади (Профиль 2) проектом eSTREAM. Он не запатентован и указан в качестве международного стандарта согласно ISO/IEC 29192-3. [1]
Он генерирует до 2 64 биты вывода из 80-битного ключа и 80-битного IV . Это самый простой участник eSTREAM; Несмотря на то, что он демонстрирует замечательную устойчивость к криптоанализу из-за своей простоты и производительности, недавние атаки оставляют запас безопасности довольно небольшим.
Описание [ править ]
288-битное внутреннее состояние Trivium состоит из трех сдвиговых регистров разной длины. В каждом раунде бит сдвигается в каждый из трех сдвиговых регистров с использованием нелинейной комбинации отводов из этого и еще одного регистра; производится один бит вывода. Чтобы инициализировать шифр, ключ и IV записываются в два сдвиговых регистра, а остальные биты начинаются по фиксированному шаблону; состояние шифрования затем обновляется 4 × 288 = 1152 раза, так что каждый бит внутреннего состояния зависит от каждого бита ключа и IV сложным нелинейным образом.
Первые 65 бит каждого сдвигового регистра не отображаются, поэтому каждый новый бит состояния не используется до тех пор, пока не пройдет как минимум 65 раундов после его генерации. Это ключ к производительности программного обеспечения Trivium и гибкости аппаратного обеспечения.
Спецификация [ править ]
Тривиум можно очень кратко описать с помощью трех рекурсивных уравнений. [2] Каждая переменная является элементом GF (2); они могут быть представлены в виде битов , где «+» — это XOR , а «•» — AND .
- a i = c i −66 + c i −111 + c i −110 • c i −109 + a i −69
- б я знак равно а я -66 + а я -93 + а я -92 • а я -91 + б я -78
- c я знак равно б я -69 + б я -84 + б я -83 • б я -82 + с я -87
Выходные биты r 0 ... r 2 64 −1 затем генерируются
- р я знак равно с я -66 + с я -111 + а я -66 + а я -93 + б я -69 + б я -84
Учитывая 80-битный ключ k 0 ... k 79 и l -бит IV v 0 ... v l −1 (где 0 ≤ l < 80), Trivium инициализируется следующим образом:
- ( а -1245 ... а -1153 ) знак равно (0, 0 ... 0, k 0 ... k 79 )
- ( б -1236 ... б -1153 ) знак равно (0, 0 ... 0, v 0 ... v л -1 )
- ( с -1263 ... с -1153 ) = (1, 1, 1, 0, 0 ... 0)
Большие отрицательные индексы начальных значений отражают 1152 шага, которые должны быть выполнены, прежде чем будет произведен выпуск продукции.
Чтобы отобразить поток битов r в поток байтов R , мы используем LSb-первое отображение R i = Σ j =0, ..., 7 2 дж р 8 я +j .
Производительность [ править ]
Простая аппаратная реализация Trivium будет использовать 3488 логических элементов и выдавать один бит за такт. Однако, поскольку каждый бит состояния не используется по крайней мере в течение 64 раундов, 64 бита состояния могут быть сгенерированы параллельно с немного большей аппаратной стоимостью в 5504 вентиля. Также возможны различные компромиссы между скоростью и площадью.
Это же свойство обеспечивает эффективную реализацию битовых срезов в программном обеспечении; Тестирование производительности с помощью eSTREAM показало скорость массового шифрования около 4 циклов/байт на некоторых платформах x86 , что хорошо сопоставимо с 19 циклами/байт эталонной реализации AES на той же платформе.
Безопасность [ править ]
[Trivium] был разработан как упражнение по изучению того, насколько можно упростить поточный шифр, не жертвуя при этом его безопасностью, скоростью и гибкостью. Хотя простые конструкции с большей вероятностью будут уязвимы для простых и, возможно, разрушительных атак (именно поэтому мы настоятельно не рекомендуем использовать Trivium на данном этапе), они, безусловно, внушают больше доверия, чем сложные схемы, если они выдерживают длительный период публичного использования. внимание, несмотря на их простоту. [3]
По состоянию на апрель 2015 г. [update] криптоаналитические атаки, превосходящие атаку методом перебора , не известны , но несколько атак близки к этому. Атака кубом требует 2 68 шаги по разрушению варианта Trivium, в котором количество раундов инициализации уменьшено до 799. [4] Ранее другие авторы предполагали, что эти методы могут привести к разрыву на 1100 раундов инициализации или «возможно, даже к исходному шифру». [5] Это основано на атаке Михаэля Вильхабера, которая преодолевает 576 раундов инициализации всего за 2. 12.3 шаги. [6]
Другая атака восстанавливает внутреннее состояние (и, следовательно, ключ) полного шифра примерно за 2 секунды. 89.5 шаги (где каждый шаг примерно равен стоимости одного испытания при исчерпывающем переборе). [7] Уменьшенные варианты Trivium, использующие те же принципы проектирования, были сломаны с помощью метода решения уравнений. [8] Эти атаки совершенствуют хорошо известную атаку на потоковые шифры с компромиссом между временем и пространством, которая с 288-битным внутренним состоянием Trivium займет 2 144 шаги и покажем, что вариант Trivium, в котором не было никаких изменений, кроме увеличения длины ключа сверх 80 бит, предусмотренных профилем eSTREAM 2, не будет безопасным. Используя оптимизированную стратегию решения, можно дополнительно снизить сложность восстановления состояния до 2. 132 шаги. [9]
Подробное обоснование конструкции Trivium приведено в статье «Конструкция потокового шифра, вдохновленная принципами проектирования блочных шифров». [10]
Ссылки [ править ]
- ^ ИСО/МЭК 29192-3:2012.
- ^ Форум eSTREAM, 20 февраля 2006 г.
- ^ Кристоф Де Каньер, Барт Пренель (29 апреля 2005 г.). «Тривиумные характеристики» (PDF) . eSTREAM представил документы. Архивировано из оригинала (PDF) 20 октября 2016 г. Проверено 9 октября 2006 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Фуке, Пьер-Ален; Ваннет, Томас (5 апреля 2015 г.). «Улучшение восстановления ключей до 784 и 799 раундов Trivium с использованием оптимизированных атак куба» (PDF) . Архив электронной печати по криптологии . ePrint 20150406:231124 . Проверено 17 апреля 2015 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Динур, Итай; Шамир, Ади (13 сентября 2008 г.). «Атаки куба на настраиваемые полиномы черного ящика» (PDF) . Архив электронной печати по криптологии . ePrint 20080914:160327 . Проверено 4 декабря 2008 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Михаэль Вильхабер (28 октября 2007 г.). «Взлом ONE.FIVIUM с помощью AIDA и дифференциальная атака Algebraic IV» .
- ^ Александр Максимов, Алексей Бирюков (23 января 2007 г.). «Две тривиальные атаки на тривиум» ( PDF ) . Электронная печать по криптологии.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) (Таблица 6, стр. 11) - ^ Ховард Раддум (27 марта 2006 г.). «Результаты криптоанализа на Trivium» ( PostScript ) . Компания eSTREAM представила документы . Проверено 9 октября 2006 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Павол Заяц (01 августа 2012 г.). «Решение булевых уравнений на основе тривиума методом силлогизмов» . ИОС Пресс.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Кристоф Де Каньер, Барт Пренель (02 января 2006 г.). «Trivium — конструкция потокового шифра, вдохновленная принципами разработки блочных шифров» (PDF) . eSTREAM представил документы. Архивировано из оригинала (PDF) 26 мая 2011 г. Проверено 9 октября 2006 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь )
Внешние ссылки [ править ]
- Страница eSTREAM на Trivium. Архивировано 23 сентября 2015 г. на Wayback Machine.
- Реализация eSTREAM. Архивировано 20 сентября 2015 г. на Wayback Machine.
| |||||||||||||||||||||
