Rabbit

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)

Ссылки



Wikimedia Foundation. 2010.

Поможем с написанием учебной работы

Полезное


Смотреть что такое "Rabbit" в других словарях:

  • Rabbit — Rab bit (r[a^]b b[i^]t), n. [OE. rabet, akin to OD. robbe, robbeken.] (Zo[ o]l.) Any of the smaller species of the genus Lepus, especially the common European species ({Lepus cuniculus}), which is often kept as a pet, and has been introduced into …   The Collaborative International Dictionary of English

  • Rabbit — (englisch für Kaninchen) ist die Bezeichnung für: Rabbit (Algorithmus), eine Stromverschlüsselung Rabbit (Film), einen animierten Kurzfilm Rabbit Junk, eine US amerikanischen Band den VW Golf der ersten Generation in den Vereinigten Staaten… …   Deutsch Wikipedia

  • rabbit — (n.) late 14c., young of the coney, from French dialect (Cf. Walloon robète), dim. of Flemish or M.Du. robbe rabbit, of unknown origin. A Germanic noun with a French suffix [Liberman]. The adult was a CONEY (Cf. coney) (q.v.) until 18c.… …   Etymology dictionary

  • rabbit — • (rabbit and pork) • Rhyming Slang for talk . Used in it s short form. Popularized by the classic(?) Chas & Dave song Rabbit rabbit(?) . The phrase You ve got more rabbit than Sainsbury s also comes from the song. Normally applied to someone who …   Londonisms dictionary

  • rabbit — [rab′it] n. pl. rabbits or rabbit [ME rabette, young of the cony, prob. < MFr dial. rabotte < MDu robbe, Fl robbe] 1. any of various swift, burrowing mammals (order Lagomorpha), smaller than most hares and characterized by soft fur, long… …   English World dictionary

  • Rabbit — (Аджерола,Италия) Категория отеля: Адрес: Via S. Lorenzo I° Trav. 8/B, 80051 Аджерола, Италия …   Каталог отелей

  • Rabbit — est le nom d un robot développé par le CNRS dans le cadre du projet ROBEA, qui s arrêta en novembre 2004. Rabbit fut conçu pour étudier les problèmes suivants : Rôle de la gravité dans la marche Effet des impacts avec le sol Commutation des… …   Wikipédia en Français

  • rabbit — ► NOUN 1) a burrowing plant eating mammal, with long ears and a short tail. 2) N. Amer. a hare. 3) the fur of the rabbit. 4) informal a poor performer in a sport or game. ► VERB (rabbited, rabbiting) 1) …   English terms dictionary

  • Rabbit — (engl.), s. Welsh rabbit …   Meyers Großes Konversations-Lexikon

  • rabbit — The verb (= hunt rabbits or, usually as rabbit on = talk excessively) has inflected forms rabbited, rabbiting …   Modern English usage

  • rabbit — см. Приложение 1 (Oryctolagus cuniculus). (Источник: «Англо русский толковый словарь генетических терминов». Арефьев В.А., Лисовенко Л.А., Москва: Изд во ВНИРО, 1995 г.) …   Молекулярная биология и генетика. Толковый словарь.

Книги

Другие книги по запросу «Rabbit» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»