Pomaranch

Pomaranch (Pomaranch версия 3) — поточный шифр, использующий каскадное включение РСЛОС с неравномерным шагом. Шифр участвовал в конкурсе eSTREAM и дошёл до 3 этапа, но, тем не менее, не был выбран для финального портфолио. Шифр был разработан для защиты от атак по сторонним каналам и может быть эффективно реализован в оборудовании для широкого спектра задач.

Разработчикам шифра являются: Тор Хеллесет, Сес Янсен и Александр Колоша.

Pomaranch может использовать 128-битный ключ и инициализирующий вектор длиной от 64 до 162 бит или 80-битный ключ и инициализирующий вектор длиной от 32 до 108 бит.

Введение

Известно, что регистры сдвига с линейной обратной связью (РСЛОС) генерируют последовательности с большим периодом и хорошими статистическими свойствами (если полином обратной связи выбран надлежащим образом). Но из-за линейности, эти последовательности склонны к алгебраическим атакам. Известный способ увеличения линейной сложности, сохраняющий в то же время большой период и хорошие статистические свойства, заключается в применении управления тактированием, то есть нерегулярного прохождения РСЛОС через последовательные состояния. При таком способе тактирования снижается скорость генерации ключей а генераторы становятся уязвимыми к временным, энергетическим и другим атакам по сторонним каналам. По этой причине потоковые шифры SOBER-t16 и SOBER-t32, не прошли оценку безопасности и не были включены в портфолио надёжных криптографических примитивов NESSIE. Использование регистров перехода вместо традиционных регистров позволяет создавать эффективные контрмеры против атак по сторонним каналам, сохраняя при этом все преимущества нерегулярного тактирования.

Описание генератора ключей

Каскадный генератор последовательностей с управляемыми переходами (КГПУП) — генератор двоичных последовательностей с каскадным управлением тактовыми импульсами, который работает в режиме шифрования Initialization vector (IV). Он предназначен для аппаратной реализации в двух версиях с длиной ключа 128 и 80 бит. Они отличаются только количеством секций регистра перехода и временем настройки IV. В 128-битной версии длина IV может быть в диапазоне от 64 до 162 бит. 80-битная версия поддерживает IV длиной от 32 до 108 бит. 128-битная (80-битная) версия КГПУП состоит из 8(5) секций плюс неполная 9(6) секция, которая имеет только регистр перехода (РП). Далее, общее количество секций обозначается как N, таким образом, N = 9, либо N = 6. Секции пронумерованы от 1 до N. Секция с нечётным номером имеет тип 1, а секция с чётным номером — тип 2.

Секционные ключи

В генераторе используется k-битный ключ, $K$. K-битный ключ состоит из 16-битных секционных ключей, $K_{i}~(i=1,\ldots ,N-1)$. Старший бит ключа $K$ соответствует старшему биту $K_{1}$. Младший бит ключа $K$ соответствует младшему биту $K_{N-1}$.

Регистры перехода

Схема регистра перехода

Существует два разных типа регистров перехода (РП), различающихся по конфигурации ячеек. РП реализует конечный автомат (КА), построенный на 18 ячейках памяти. Ячейки могут вести себя как простые сдвиговые регистры (S-ячейки) или ячейки с обратной связью (F-ячейки). Тип ячейки меняется в зависимости от значения сигнала Jump Control (JC). Количество S-ячеек, и количество F-ячеек в РП равно 9. Это означает, что для обоих значений JC-бита в РП есть 9 S-ячеек и 9 F-ячеек . Изначально, когда JC равен нулю, ячейки находятся в начальном режиме. Когда JC равен единице, все ячейки переключаются в противоположный режим. РП нечётных секций является регистром сдвига с обратной связью (РСОС), имеющим ответвления в ячейках 3, 8, 16 и 18. РП чётных секций является РСОС, имеющим ответвления в ячейках 6, 8, 14 и 18.

Карта ключей

9-битные входные векторы для карты ключей состоят из ячеек 1, 2, 4, 5, 6, 7, 9, 10, 11 РП типа 1 и ячеек 1, 2, 3, 4, 5, 7, 9, 10, 11 РП типа 2. Эти 9-битные векторы рассматриваются как числа (обозначаемые как $V$) в диапазоне $[0,2^{9}-1]$, причём младшим является бит из ячейки 1, а старшим из ячейки 11. Далее выполняется операция XOR между 9 младшими битами секционного ключа и вектором $V$. Результат заменяется на 7-битное число используя S-блок. Далее, полученный вектор $W$ используется как входные данные для функции F. На выходе получаем бит, $JC_{0}$, который используется для управления режимами ячеек РСОС.

Режимы работы генератора

Режим генерации ключей

В 128-битной версии поток ключей генерируется с помощью операции XOR над выходами всех 9 секций. В 80-битной версии выходы 1 — 5 секций объединяются и рассматриваются как аргумент булевой функции G. Поток ключей формируется из результатов операции XOR над выходом 6 секции и значением функции G. Выход каждой секции подключён к 17 ячейке РП.

Режим сдвига

Режим используется во время инициализации и настройки IV. Вывод карты ключей $JC_{0}$ каждой секции подключается к входу следующей секции, который используется только в режиме сдвига. Вывод $JC_{0}$ последней секции подключается ко входу первой таким образом «замыкая» большую цепочку. Конфигурация ячеек в РП не изменяется, они работают как будто управляющий бит равен нулю.

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

Установка ключа

Предварительно, все регистры выставляются в значение pi[i]. Где pi[9] = {0x090FD, 0x2A888, 0x168C2, 0x0D313, 0x06628, 0x2E037, 0x01CD1, 0x0A409, 0x0E088}. Затем генератор запускается на 128 шагов в режиме сдвига. Получившиеся 18-битные состояния регистров используются далее при установке IV.

Установка IV

Последовательность действий для установки IV следующая:

1. IV может иметь произвольную длину в диапазоне от 64 для 128-битной версии (32 в 80-битной) до 18N бит. Если длина IV меньше 18N, то увеличить её до 18N, циклически повторяя биты IV.
2. Выполнить XOR 18N-битного IV с вектором инициализации, сохранённым после настройки ключа, и загрузить результат в N регистров перехода.
3. Запустить генератор в режиме сдвига на 108 шагов, если N = 9 (128 битов ключа) или на 88 шагов, если N = 6 (80 битов ключа).
4. Если какой-то из N регистров имеет состояние «все нули», тогда установить его младший значащий бит в единицу.
5. Выполнить запуск генератора на 64 шага, отбрасывая выходные биты.

После запуска КГПУП начинает генерировать поток ключей в режиме генерации ключей. Инициализация КГПУП выполняется только один раз для данного ключа. Следовательно, использование вектора инициализации позволяет добиться быстрого запуска нового сеанса и повторной синхронизации.

Аппаратная реализация

КГПУП идеально подходит для аппаратной реализации, поскольку он требует стандартных компонентов и не имеет сложных схем, вызывающих узкие места синхронизации. 80-битная версия КГПУП состоит из 6 секций, в 5 из которых содержится карта ключей. Часть регистра перехода использует 18 ячеек памяти, каждая из которых имеет XOR-элемент и переключатель. Как правило, это занимает около 225 логических ячеек. S-блок, преобразующий 9-битный вектор в 7-битный, — самый затратный в аппаратной реализации. Следующий по затратности после S-блока — булева функция 7 к 1 и 16 XOR. Реализация этих компонентов путём прямого синтеза булевой схемы оценивается в 1000 вентилей. Для полного проекта получается общая оценка в 6300 вентилей.

Безопасность

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

Метод полного перебора

Поиск по всему пространству ключей даёт сложность 2k с k = 128 и k = 80 для соответствующей длины ключа.

Атаки по сторонним каналам

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

Отличительные атаки

Предполагается, что отличительная атака будет успешной, если злоумышленник сможет отличить поток ключей от чисто случайной последовательности. Разумно предположить, что необходимая длина потока ключей не превышает общее количество ключей для генератора, так как отличительная атака не должна длиться дольше, чем полный поиск ключа. Поток ключей, созданный КГПУП, получается как сумма линейных повторяющихся последовательностей, и это делает маловероятными любые статистические недостатки в потоке ключей.

Дифференциальная атака

Этот тип атак, который был первоначально введён для блочных шифров, также может применяться к потоковым шифрам. Для синхронных потоковых шифров дифференциальные атаки могут использовать известную разницу в значении IV. Более того, обычно предполагается, что атакующий может выбрать IV. С помощью таких атак были обнаружены уязвимости шифра. Атака позволяет восстановить 128-битный ключ со сложностью O(265) или даже быстрее, с O(252), если при инициализации используется функция выхода из состояния с нулевым состоянием. Это стало причиной введения новой процедуры настройки IV в версии 2 шифра, которая обеспечивает хорошую диффузию битов IV.

Литература

• Cascade Jump Controlled Sequence Generator and Pomaranch Stream Cipher (Version 3)
• Cees J.A. Jansen. Stream Cipher Design based on Jumping Finite State Machines
• Поточные криптосистемы
• Muller, F.: Differential attacks and stream ciphers
• ПОТОЧНЫЕ ШИФРЫ Результаты зарубежной открытой криптологии, Москва 1997
• R. Anderson. «Solving a class of stream ciphers», Cryptologia, 14(3):285-288,1990
• Kholosha, A.: Investigations in the Design and Analysis of Key Stream Generators.
• ОСНОВЫ ПОСТРОЕНИЯ ЦИФРОВЫХ ЛОГИЧЕСКИХ УСТРОЙСТВ
• Cid, C., Gilbert, H., Johansson, T.: Cryptanalysis of Pomaranch (недоступная ссылка).