Rabbit

Схема работы алгоритма

Rabbit — высокоскоростной поточный шифр впервые представленный в феврале 2003 года на 10-м симпозиуме FSE. В мае 2005, он был отправлен на конкурс eStream, целью которого было создание европейских стандартов для поточных систем шифрования.

Разработчиками Rabbit являются Martin Boesgaard, Mette Vesterager, Thomas Pedersen, Jesper Christiansen и Ove Scavenius.

Rabbit используют 128-битный ключ и 64-битный инициализирующий вектор. Шифр был разработан с целью использования в программном обеспечении, как обладающий высокой скоростью шифрования. При этом скорость шифрования могла достигать 3.7 циклов в байт(CPB) для процессора Pentium 3 и 10.5 циклов в байт для ARM7. Тем не менее, шифр также оказался быстрым и компактным при реализации в аппаратном обеспечении.

Основным компонентом шифра является генератор битового потока, который шифрует 128 битов сообщения за итерацию. Достоинство шифра в тщательном перемешивании его внутренних состояний между двумя последовательными итерациями. Функция перемешивания полностью основана на арифметических операциях, доступных на современных процессорах, то есть S-блоки подстановок и поисковые таблицы не нужны для реализации шифра.

Авторы шифра предоставили полный набор технических описаний на домашней странице Cryptico. Шифр также описан в RFC 4503. Cryptico обладала патентом на шифр, и многие годы для использования шифра в коммерческих целях требовалась лицензия. Однако, 6 октября 2008 шифр разрешили использовать для любых целей бесплатно.

Rabbit и eStream

Конкурс eStream

Поточные симметричные шифры проекта eSTREAM составляют два профиля. В Профиль 1 входят шифры, ориентированные на программную реализацию, а в Профиль 2 — шифры, ориентированные на аппаратную реализацию.

Лучшие шифры проекта:

Профиль 1	Профиль 2
HC-128	F-FCSR-H v2
Rabbit	Grain v1
Salsa20/12	MICKEY v2
Sosemanuk	Trivium

В Профиль 1 вошли поточные симметричные шифры с хорошей программной реализацией. Настолько хорошей, что должны были превосходить по скоростным показателям блочный симметричный алгоритм шифрования AES в режимах генерации гаммы. Основным требованием к этому профилю было обеспечение уровня безопасности в 128 бит.

Достоинства и недостатки шифра Rabbit

Rabbit является одной из старейших конструкций проекта eSTREAM. Данный поточный шифр не был подвержен каким-либо модификациям или дополнениям. Его спецификация оставалась неизменной с 2003 года и по данный момент. Шифр пережил все три этапа проекта и ни на одном не был подвержен криптоаналитическим атакам. Кроме всего прочего, данный алгоритм очень хорошо реализуется на новых процессорах семейства Intel. Как недостаток можно заметить тот факт, что шифр Rabbit обеспечивает уровень безопасности только в 128 бит.

Результаты заключительного голосования проекта eSTREAM по Профилю 1.

Профиль 1	очки
Rabbit	2.80
Salsa20	2.80
Sosemanuk	1.20
HC-128	0.60
NLS v2	−0.60
LEX v2	−1.20
CryptMT v3	−1.40
Dragon	−1.60

Алгоритм

Внутреннее состояние поточного шифра содержит 513 битов. 512 из них поделены на восемь 32-битных переменных состояний $x_{j,i}$ и восемь 32-битных счётчиков $c_{j,i}$, где $x_{j,i}$ — переменная состояния подсистемы $j$ при итерации $i$, а $c_{j,i}$ — обозначает соответствующий счётчик переменных. 513-й бит — бит переноса $\phi _{7,i}$, который необходимо хранить между итерациями. Этот бит инициализируется нулём. 8 переменных состояний и 8 счётчиков зависят от ключа при инициализации.

Схема установки состояния

Алгоритм инициализируется расширением 128-битного ключа на 8 переменных состояния и 8 счётчиков так, что существует взаимно однозначное соответствие между ключом, начальными переменными состояний, $x_{j,0}$, и начальными счётчиками, $c_{j,0}$. Ключ $K^{[127..0]}$ поделён на 8 подключей: $k_{0}^{[15..0]}$, $k_{1}^{[31..16]}$, … , $k_{7}^{[127..112]}$, переменные состояний и счётчики инициализируются при помощи подключей

$x_{j,0}={\begin{cases}k_{(j+1\mod 8)}\diamond k_{j},&{\text{for even}}\ j,\\k_{(j+5\mod 8)}\diamond k_{(j+4\mod 8)},&{\text{for odd}}\ j,\\\end{cases}}$

$c_{j,0}={\begin{cases}k_{(j+4\mod 8)}\diamond k_{(j+5\mod 8)},&{\text{for even}}\ j,\\k_{j}\diamond k_{(j+1\mod 8)},&{\text{for odd}}\ j,\\\end{cases}}$

где $\diamond$ — операция конкатенации.

Система прогоняется 4 раза согласно функции следующего состояния, определённой ниже, чтобы понизить корреляцию между битами ключа и битами переменных внутреннего состояния. В конце счётчики реинициализируются следующим образом:

$c_{j,4}=c_{j,4}\oplus x_{(j+4mod8),4}$

для предотвращения восстановления ключа путём инверсии системы счётчиков.

Функция следующего состояния

$x_{0,i+1}=g_{0,i}+(g_{7,i}\lll 16)+(g_{6,i}\lll 16)$

$x_{1,i+1}=g_{1,i}+(g_{0,i}\lll 8)+g_{7,i}$

$x_{2,i+1}=g_{2,i}+(g_{1,i}\lll 16)+(g_{0,i}\lll 16)$

$x_{3,i+1}=g_{3,i}+(g_{2,i}\lll 8)+g_{1,i}$

$x_{4,i+1}=g_{4,i}+(g_{3,i}\lll 16)+(g_{2,i}\lll 16)$

$x_{5,i+1}=g_{5,i}+(g_{4,i}\lll 8)+g_{3,i}$

$x_{6,i+1}=g_{6,i}+(g_{5,i}\lll 16)+(g_{4,i}\lll 16)$

$x_{7,i+1}=g_{7,i}+(g_{6,i}\lll 8)+g_{5,i}$

$g_{j,i}=\operatorname {LSW} ((x_{j,i}+c_{j,i})^{2})\oplus \operatorname {MSW} ((x_{j,i}+c_{j,i})^{2})$

Здесь все сложения по модулю 2³². Функции $\operatorname {LSW} (x)$ и $\operatorname {MSW} (x)$ возвращают, соответственно, младшие и старшие четыре байта 64-разрядного числа $x$, $\lll$ — циклический сдвиг влево.

Система счетчиков

Уравнения, задающие изменение системы счетчиков:

$c_{0,i+1}=c_{0,i}+a_{0}+\phi _{7,i}\mod 2^{32}$

$c_{1,i+1}=c_{1,i}+a_{1}+\phi _{0,i+1}\mod 2^{32}$

$c_{2,i+1}=c_{2,i}+a_{2}+\phi _{1,i+1}\mod 2^{32}$

$c_{3,i+1}=c_{3,i}+a_{3}+\phi _{2,i+1}\mod 2^{32}$

$c_{4,i+1}=c_{4,i}+a_{4}+\phi _{3,i+1}\mod 2^{32}$

$c_{5,i+1}=c_{5,i}+a_{5}+\phi _{4,i+1}\mod 2^{32}$

$c_{6,i+1}=c_{6,i}+a_{6}+\phi _{5,i+1}\mod 2^{32}$

$c_{7,i+1}=c_{7,i}+a_{7}+\phi _{6,i+1}\mod 2^{32}$

где счетчик бита переноса $\phi _{j,i+1}$ задаётся как

$\phi _{j,i+1}={\begin{cases}1,&{\text{if}}\ c_{0,i}+a_{0}+\phi _{7,i}\geqslant 2^{32}\wedge j=0,\\1,&{\text{if}}\ c_{j,i}+a_{j}+\phi _{j-1,i+1}\geqslant 2^{32}\wedge j>0,\\0,&{\text{otherwise}}.\end{cases}}$

Кроме того, константы $a_{j}$ определяются как

$a_{0}={\mathtt {0x4D34D34D}},\quad a_{1}={\mathtt {0xD34D34D3}},$

$a_{2}={\mathtt {0x34D34D34}},\quad a_{3}={\mathtt {0x4D34D34D}},$

$a_{4}={\mathtt {0xD34D34D3}},\quad a_{5}={\mathtt {0x34D34D34}},$

$a_{6}={\mathtt {0x4D34D34D}},\quad a_{7}={\mathtt {0xD34D34D3}}.$

Схема извлечения

После каждой итерации 128 битов выхода генерируется по следующим формулам:

$s_{i}^{[15..0]}=x_{0,i}^{[15..0]}\oplus x_{5,i}^{[31..16]}$

$s_{i}^{[31..16]}=x_{0,i}^{[31..16]}\oplus x_{3,i}^{[15..0]}$

$s_{i}^{[47..32]}=x_{2,i}^{[15..0]}\oplus x_{7,i}^{[31..16]}$

$s_{i}^{[63..48]}=x_{2,i}^{[31..16]}\oplus x_{5,i}^{[15..0]}$

$s_{i}^{[79..64]}=x_{4,i}^{[15..0]}\oplus x_{1,i}^{[31..16]}$

$s_{i}^{[95..80]}=x_{4,i}^{[31..16]}\oplus x_{7,i}^{[15..0]}$

$s_{i}^{[111..96]}=x_{6,i}^{[15..0]}\oplus x_{3,i}^{[31..16]}$

$s_{i}^{[127..112]}=x_{6,i}^{[31..16]}\oplus x_{1,i}^{[15..0]}$

где $s_{i}$ — 128-битный блок шифрующего потока на $i$-й итерации.

Схема шифрования и расшифрования

Выполняется операция XOR между извлеченными битами и текстом/шифротекстом для шифрования/дешифрования.

$c_{i}=p_{i}\oplus s_{i},$

$p_{i}=c_{i}\oplus s_{i},$

где $c_{i}$ и $p_{i}$ обозначают $i$-й блок шифротекста и текста соответственно.

Свойства схемы установки ключа

Установку ключа можно разделить на три этапа: расширение ключа, система итераций, модификация счетчика.

• Этап расширения ключа гарантирует взаимно однозначное соответствие между ключом состояния и ключом счётчика, который предотвращает избыток ключей. Он также распределяет биты ключа оптимальным образом для итераций.
• Система итераций гарантирует, что после одной итерации функции следующего состояния каждый бит ключа повлияет на все восемь переменных состояния. Это также гарантирует, что после второй итерации функции следующего состояния все биты ключа повлияют на все биты состояния с вероятностью 0,5. Для надёжности шифрования итерацию проделывают четыре раза.
• Даже если счетчики будут известны злоумышленнику, модификация счётчика сильно усложняет восстановление ключа путём инвертирования счётчика системы, так как потребуются сведения о переменных состояния, также это нарушает взаимно однозначное соотношение между ключом и счетчиком.

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

Rabbit предоставляет 128-битную защиту против атакующих, чья цель — один уникальный ключ. Если же атака происходит на несколько ключей за раз, и всё равно, который из них взломают, то защищённость снижается до 96 бит.

Атаки на функцию установления ключа

После того, как ключ задан, биты счётчика и состояния строго и очень нелинейно зависят от бит ключа. Это усложняет взлом для атак на основе угадывания части ключа, даже если биты счётчика были известны после модификации счётчика. Конечно, знание счётчиков делает другие виды взломов легче.

Атака, основанная на коллизии

В шифре Rabbit используется неоднозначное отображение, разные ключи потенциально могут привести к той же гамме. Эта проблема в основном сводится к вопросу о том, что разные ключи приводят к одним и тем же значениям счётчика, так как различные значения счётчика почти наверняка приведут к разным генерациям гаммы. Надо обратить внимание, что расширение ключа и система итераций были разработаны таким образом, что каждый ключ приводит к уникальным значениям счетчика. Тем не менее, модификация счётчика может привести к равным значениям счетчика для двух различных ключей. Полагая, что после четырёх начальных итераций внутреннее состояние, по существу, случайное и не коррелирует с системой счётчиков, вероятность коллизий задается «парадоксом дней рождения», то есть для всех $2^{128}$ ключей одна коллизия ожидается в 256-битным счетчиком^{[уточнить]}. Таким образом, коллизия системы счетчиков не должна вызывать проблем на практике.

Атака со связанным ключом

Атака основана на использовании свойств симметрии в функциях следующего состояния и установки ключа. Рассмотрим, например, два ключа $K$ и ${\tilde {K}}$ связанные соотношением $K^{[i]}={\tilde {K}}^{[i+2]}$ для всех $i$. Это приводит к соотношению $x_{j,0}={\tilde {x}}_{j+2,0}$ и $c_{j,0}={\tilde {c}}_{j+2,0}$. Теперь рассмотрим, когда $K$ и ${\tilde {K}}$ — один и тот же ключ. Если условие $a_{j,0}={\tilde {a}}_{j+2,0}$ выполнено, то функция следующего состояния сохранила бы свойство симметрии. Но можно легко проверить, что константы $a_{j}$, выбраны так, что $a_{j,0}\neq {\tilde {a}}_{j+2,0}$. Таким образом, функция следующего состояния не подвержена атаке на основе связанного ключа.

Атака на основе частичного угадывания ключа

Guess-and-Verify Attack

Такая атака станет возможной, если выходные биты можно будет предсказать с помощью небольшого набора битов внутреннего состояния. Злоумышленник должен отгадать соответствующую часть переменных состояния, предсказать выходные биты и сравнить их с непосредственно наблюдаемыми битами на выходе, чтобы удостовериться в правильности своей догадки. Злоумышленник должен угадать, по крайней мере, 2*12 входных байт для различных g-функций для проверки в отношении одного байта. Это равносильно угадыванию 192 битов, что сложнее, чем полный перебор всех ключей.

Guess-and-Determine Attack

Суть этого метода заключается в том, что надо угадать несколько неизвестных переменных шифра и, используя их, вывести оставшиеся неизвестные. После этого систему прогоняют несколько раз, и то что получилось на выходе сравнивают с реальным выходными данными шифра для проверки предположения. Злоумышленник пытается воссоздать 512 бит внутреннего состояния, то есть он наблюдает 4 последовательных 128-битных данных на выходе шифра и делает следующее:

1. Разделяет 32-битный счётчик и 32-битную переменную состояния на 8-битовые переменные.
2. Составляет систему уравнений, которая моделирует изменение счётчиков и переменных состояния, и выходные данные. В итоге получается 160 уравнений и 160 неизвестных.
3. Решает эту систему, угадывая как можно больше неизвестных.

Эффективность такого подхода зависит от количества угаданных переменных. Это количество ограниченно снизу 8-битовой подсистемой с наименьшим количеством входных переменных. Если пренебречь счетчиками, каждый байт функции следующего состояния зависит от 12 входных байт. Если учитывать счётчики, каждый байт на выходе подсистемы зависит уже от 24 входных байт. Следовательно, злоумышленник должен угадать более чем 128 бит, таким образом, делая нападение невыполнимым.

Алгебраические атаки

Алгебраически нормальная форма(АНФ) g-функции

Дана Булева функция $f:(0,1)^{n}\rightarrow (0,1)$ , АНФ является представлением $f$ как многомерного полинома(то есть сумма одночленов от входных переменных). Большое количество одночленов и их хорошее распределение по степеням — важные свойства нелинейных блоков в шифре.

Для случайной Булевой функции в 32 переменных среднее число одночленов равняется $2^{31}$, а среднее число одночленов, включающие все данные переменные — $2^{30}$. Если мы рассмотрим 32 такие функции, выбранные случайным образом, то среднее число одночленов, которых нет ни в одной из 32 функций, равно 1, и соответствующая дисперсия также равна 1.

Для g-функции в шифре Rabbit, АНФ для 32 булевых подфункций имеют, по крайней мере, степень 30. Число одночленов варьируется от $2^{24.5}$ до $2^{30.9}$, где для случайной функции оно должно быть $2^{31}$. Распределение одночленов как функции степени представлено на рисунке. В идеале, основная часть должна была находиться промежутке между пунктирными линиями, которые показывают отклонения от среднего для идеальной случайной функции. Некоторые Булевы функции значительно расходятся с результатами для случайной функции, однако, все они имеют большое число одночленов высокой степени.

К тому же, исследовалось частичное совпадение 32 функций. Общее число одночленов, которые встречаются один раз, равно $2^{26.03}$, в то время как число одночленов, которые не встречаются вовсе — $2^{26.2}$. Если сравнить со случайной функцией, то это довольно большие отклонения. Эта информация может быть полезна для анализа шифра в будущем.

Алгебраически нормальная форма(АНФ) для полного шифра

Практически невозможно рассчитать АНФ для всех битов на выходе для полного шифра. Но уменьшение размера ключа с 128 бит до 32 бит делает это возможным для изучения 32 булевых функций на выходе как функцию от 32 битного ключа.

Для урезанной версии шифра Rabbit была исследована функция установки для различного числа итераций. АНФ определяется после 0, 1, 2, 3, 4 итераций и одной дополнительной в схеме извлечения. Для 0+1 итераций число одночленов было примерно равно 2^31, как предполагалось для случайной функции. Но после двух итераций результат стабилизировался. Это означает, что больше нет колебаний на выходе. Количество отсутствующих полиномов 0, 1, 2, 3, 1 в итерациях (0+1), …, (4+1) соответственно. Очевидно, что эти данные соответствуют результатам для случайных функций.

Корреляционные атаки

Линейная аппроксимация

Линейная атака подразумевает нахождение лучшего линейного приближения между битами на входе функции следующего состояния и битами на выходе схемы извлечения. Для этого используют Преобразование Уолша — Адамара, полагая, что все входные данные линейно независимы. Было установлено, что наилучшая линейная корреляция имеет коэффициент корреляции порядка $2^{-57.8}$, что подразумевает генерацию выходных данных от $2^{114}$ итераций, чтобы сравнить со случайной функцией.

Аппроксимация второго порядка

Отсекание из АНФ для g-функции членов выше второго порядка значительно улучшает аппроксимацию при правильных условиях.

Обозначим через $f^{[j]}$ аппроксимацию второго порядка АНФ для $g^{[j]}$. По результатам эксперимента коэффициент корреляции между $f$ и $g$ составляет менее $2^{-9.5}$, а коэффициент корреляции между $f^{[j]}\oplus f^{[j+1]}$ и $g^{[j]}\oplus g^{[j+1]}$ примерно равен $2^{-2.72}$. Это означает, что некоторые члены более высокой степени отсекаются при сложении по модулю 2 двух соседних битов. Построение по этим данным шифра со вторым порядком аппроксимации дает, в лучшем случае, коэффициент корреляции порядка $2^{-26.4}$. Данное значение коэффициента корреляции является недостаточным для атаки. Если ещё учитывать счетчики, то анализ намного усложняется.

Ссылки

• Cryptico homepage Архивная копия от 28 января 2011 на Wayback Machine
• Rabbit RFC Архивная копия от 24 мая 2011 на Wayback Machine
• eSTREAM page on Rabbit Архивная копия от 17 августа 2010 на Wayback Machine
• Сравнительный анализ шифров проекта eSTREAM