Rabbit

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

Rabbit - высокоскоростной поточный шифр впервые представленный ^[1] в феврале 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.^[2]. Шифр также описан в RFC 4503. Cryptico обладала патентом на шифр, и многии годы для использования шифра в коммерческих целях требовалась лицензия. Однако, 6 октября 2008 шифр разрешили использовать для любых целях бесплатно. ^[3]

Rabbit и eStream ^[4]

Конкурс 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 из них поделены на 8-мь 32-битных переменных состояний $x_{j,i}$ и 8-мь 32-битных счетчиков $c_{j,i}$ , где $x_{j,i}$ - переменная состояния подсистемы $j$ при итерации $i$ , а $c_{j,i}$ - обозначает соответствующий счетчик переменных. 513-й бит - бит переноса φ$_{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 , \ \ for \ j \ even\\ k_{(j+5 \mod 8)} \diamond k_{(j+4 \mod 8)}, \ \ for \ j \ odd \\ \end{cases}$

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

(где $\diamond$ - операция конкатенации)

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

$c_{j,4}=c_{j,4} \oplus x_{(j+4 mod 8),4} \quad,$

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

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

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

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

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

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

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

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

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

$x_{7,i+1} = g_{7,i} + (g_{6,i}\lll8) + 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^32. Функции $\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}$

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

$\phi_{j,i+1} = \begin{cases} 1, \ \ if \ c_{0,i} + a_0 + \phi_{7,i} \geqslant 2^{32} \wedge j = 0 \ \\ 1, \ \ if \ c_{j,i} + a_j + \phi_{j-1,i+1} \geqslant 2^{32} \wedge j > 0 \ \\ 0, \ \ otherwise \end{cases}$

Кроме того, константы $a_j$ определяются как:

$a_0 = 0x4D34D34D \ \ a_1 = 0xD34D34D3$

$a_2 = 0x34D34D34 \ \ a_3 = 0x4D34D34D$

$a_4 = 0xD34D34D3 \ \ a_5 = 0x34D34D34$

$a_6 = 0x4D34D34D \ \ a_7 = 0xD34D34D3$

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

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

$s^{[15..0]}_i = x^{[15..0]}_{0,i} \oplus x^{[31..16]}_{5,i}$

$s^{[31..16]}_ i = x^{[31..16] }_{0,i }\oplus x^{[15..0]}_{3,i}$

$s^{[47..32]}_i = x^{[15..0]}_{2,i }\oplus x^{[31..16]}_{7,i }$

$s^{[63..48]}_i = x^{[31..16]}_{2,i} \oplus x^{[15..0]}_{5,i}$

$s^{[79..64]}_i = x^{[15..0]}_{4,i }\oplus x^{[31..16]}_{1,i }$

$s^{[95..80]}_i = x^{[31..16]}_{4,i} \oplus x^{[15..0]}_{7,i}$

$s^{[111..96]}_i = x^{[15..0]}_{6,i }\oplus x^{[31..16]}_{3,i }$

$s^{[127..112]}_i = x^{[31..16]}_{6,i}\oplus x^{[15..0]}_{1,i}$

где $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 бит.^[5].

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

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

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

В шифре 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} \ne \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.

Число одночленов каждой степени в каждой из 32 Булевых функций для g-функции. Толстая сплошная линия и две пунктирные линии показывают среднее значение и отклонения от среднего для идеальной случайной функции

Для 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}$. Данное значение коэффициента корреляции является недостаточным для атаки. Если еще учитывать счетчики, то анализ намного усложняется.

Список литературы

1. ↑ M. Boesgaard, M. Vesterager, T. Pedersen, J. Christiansen, O. Scavenius. Rabbit: A High-Performance Stream Cipher. Proc. FSE 2003. Springer LNCS 2887, pp. 307-329 (PDF)
2. ↑ M. Boesgaard, T. Pedersen, M. Vesterager, E. Zenner. The Rabbit Stream Cipher - Design and Security Analysis. Proc. SASC 2004. (PDF)
3. ↑ Phorum :: ECRYPT forum :: Rabbit becomes public domain
4. ↑ The eSTREAM Portfolio Steve Babbage, Christophe De Canni`ere, Anne Canteaut, Carlos Cid, Henri Gilbert, Thomas Johansson, Matthew Parker, Bart Preneel, Vincent Rijmen and Matthew Robshaw6 (PDF)
5. ↑ Christophe De Cannière, Joseph Lano, and Bart Preneel, "Comments on the Rediscovery of Time Memory Data Tradeoffs", 2005. (PDF)

Ссылки

• Cryptico homepage
• Rabbit RFC
• eSTREAM page on Rabbit
• Сравнительный анализ шифров проекта eSTREAM