SOBER-t32

SOBER-t32
Создатель	Филип Хаукес и Грегори Роуз
Создан	2000 год
Опубликован	2000 год
Размер ключа	256 бит

SOBER-t32 (англ. Seventeen Octet Byte Enabled Register) — cинхронный аддитивный потоковый шифр из семейства SOBER. Авторами являются Филип Хаукес и Грегори Роуз (Австралия).

Историческая справка

SOBER — семейство потоковых шифров, широко используемых во встроенных системах, предложенное Г. Роузом в 1998 году. На данный момент семейство включает в себя шифры SOBER, SOBER-II, S16, S32, SOBER-t8, SOBER-t16, SOBER-t32 и SOBER-128.

Первый программный потоковый шифр из семейства был разработан с целью удовлетворения основных требований встроенных приложений, которые накладывают жёсткие ограничения на объём вычислительной мощности, программного пространства и памяти, доступной для программных алгоритмов шифрования. Шифрование речи для беспроводной телефонии — одна из первых и главных сфер применения шифров SOBER. Так как большинство используемых мобильных телефонов представляют собой микропроцессор и память, быстрый программный потоковый шифр, использующий небольшое количество памяти, является наиболее подходящим вариантом для таких приложений. Многие методы генерации потока псевдослучайных битов основаны на регистрах сдвига с линейной обратной связью (РСЛОС) над конечным полем Галуа порядка 2. Такие шифры неэффективно использовать на ЦПУ. Шифры семейства SOBER обходят данную проблему, используя РСЛОС над полем [math]\displaystyle{ 2^w }[/math] и ряд методов, позволяющих значительно увеличить скорость генерации псевдослучайной последовательности в программном обеспечении на микропроцессоре.

Стремление усилить безопасность и использовать шифр в 16-битных и 32-битных процессорах привело к возникновению нескольких вариантов первоначального шифра SOBER. Однако, когда в нём были обнаружены различные недостатки, он был заменён на SOBER-II и его дополнения — S16 и S32. S16 копирует структуру SOBER II и является расширением данного алгоритма до 16-битной арифметики. В это же время S32 основан на 32-битной арифметике, а структура данного шифра отлична от SOBER-II и S16. Тем не менее, при последующем анализе SOBER-II были обнаружены атаки, которые выявили недостаток всей структуры шифра, а не его отдельных частей. Как итог, на замену существующим шифрам были выпущены три новые версии, основанные на 8-битной, 16-битной и 32-битной арифметике, называемые t-классом шифров SOBER. Синхронные потоковые шифры SOBER-t16 и SOBER-t32 были представлены в программе NESSIE. И хотя оба шифра в итоге были признаны не соответствующими строгим требованиям NESSIE, согласно заключительному отчёту о безопасности, выпущенному NESSIE в феврале 2003 года, на втором этапе отбора были рассмотрены только четыре потоковых шифра: BMGL, SNOW, SOBER-t16 и SOBER-t32.

Описание алгоритма

SOBER-t32 — это 256-битный синхронный потоковый шифр из семейства SOBER. В шифрах данного типа ключи генерируются независимо от открытого текста. Для того чтобы зашифровать открытый текст, отправитель выполняет операцию XOR между открытым текстом и потоком ключей. Если получателю известен секретный ключ, то он может восстановить поток ключей и расшифровать сообщение, выполнив операцию XOR между зашифрованным текстом и потоком ключей.

Основными элементами шифрообразующего устройства являются:

Рис. 1. Структура SOBER-t32

• Регистр сдвига с линейной обратной связью (РСЛОС), который использует рекуррентное соотношение для создания последовательности состояний (слов) [math]\displaystyle{ s_n }[/math].
• Нелинейный фильтр (НФ) — создаёт поток [math]\displaystyle{ v_n }[/math] из [math]\displaystyle{ s_n }[/math], создавая нелинейную комбинацию из полученных слов.
• Блок «задержки», или «усечения» (БЗ) — генерирует поток ключей [math]\displaystyle{ z_j }[/math], прорежая НФ-поток нерегулярным образом.

Элементы представлены над полем Галуа [math]\displaystyle{ GF(2^{32}) }[/math] с использованием базиса [math]\displaystyle{ {a^{31}, a^{30} ... a, 1} }[/math]. Если [math]\displaystyle{ y \in GF(2^{32}) }[/math], то [math]\displaystyle{ y }[/math] представим как [math]\displaystyle{ (y_{31}, y_{30}, ..., y_1, y_0) }[/math], где [math]\displaystyle{ y = y_{31}a^{31} + y_{30}a^{30} + ... + y_1a + y_0 }[/math]. Работа шифра основана на 32-битных операциях над [math]\displaystyle{ GF(2^{32}) }[/math] по модулю полинома вида:

[math]\displaystyle{ A(x) = x^{32} + (x^{24} + x^{16} + x^{8}+ 1)(x^6 + x^5 + x^2 + 1) }[/math]

Сложение двух элементов в [math]\displaystyle{ GF(2^{32}) }[/math] представляется как сложение соответствующих полиномов с приведением коэффициентов по модулю два. Умножение двух элементов в [math]\displaystyle{ GF(2^{32}) }[/math] представляется как умножение соответствующих полиномов с приведением коэффициентов полиномов по модулю два. Результат умножения затем приводится по модулю неприводимого полинома [math]\displaystyle{ A(x) }[/math].

Регистр сдвига с линейной обратной связью (РСЛОС)

РСЛОС — сдвиговый регистр длины 17, где каждая ячейка содержит одно 32-разрядное слово. Таким образом, полная внутренняя память составляет 544 бит. Состояние РСЛОС в момент времени [math]\displaystyle{ t }[/math] задаётся вектором:

[math]\displaystyle{ \vec{S_t} = (s_t, s_{t+1}, s_{t+2} ,...s_{t+16} ) = (r_0, r_1, r_2,...r_{16}) }[/math]

Следующее состояние РСЛОС получается путём сдвига предыдущего состояния на один шаг. Новое слово [math]\displaystyle{ s_{t+17} }[/math] вычисляется как линейная комбинация слов, содержащихся в РСЛОС, по следующему правилу:

[math]\displaystyle{ s_{t + 17} = s_{t+15} \oplus s_{t+4} \oplus \alpha \cdot s_t }[/math]

где [math]\displaystyle{ \alpha = C2DB2AA3_x }[/math], [math]\displaystyle{ \oplus }[/math] — исключающее или (XOR).

Нелинейный фильтр (НФ)

Нелинейный фильтр предназначен для уменьшения вероятности успешного криптоанализа шифра. Основная цель НФ — скрыть линейность выходного потока регистра. В каждый момент времени нелинейный фильтр берёт из РСЛОС пять слов и вычисляет значение, обозначаемое [math]\displaystyle{ v_t }[/math]:

[math]\displaystyle{ v_t= ((f(s_t\boxplus s_{t+16})\boxplus s_{t+1} \boxplus s_{t+6} )\oplus K) \boxplus s_{t+13} }[/math]

где:

• [math]\displaystyle{ \boxplus }[/math] — сложение по модулю [math]\displaystyle{ 2^{32} }[/math].
• константа [math]\displaystyle{ K }[/math] — слово, которое определяется во время инициализации РСЛОС и сохраняется до конца сеанса.
• [math]\displaystyle{ f }[/math] задаёт некоторую нелинейную функцию.

Рис. 2. Структура нелинейной функции [math]\displaystyle{ f }[/math]

Функция [math]\displaystyle{ f }[/math] используется для достижения нескольких целей. Во-первых, она скрывает линейность в младшем значащем бите (eng. Least Significant Byte или LSB) и добавляет значительную нелинейность в оставшиеся биты. Во-вторых, она гарантирует, что результат сложения [math]\displaystyle{ r_0 }[/math] и [math]\displaystyle{ r_{16} }[/math] не коммутирует с результатом сложения [math]\displaystyle{ r_1 }[/math] и [math]\displaystyle{ r_6 }[/math]. В-третьих, [math]\displaystyle{ f }[/math] обеспечивает, чтобы каждый бит вывода НФ зависел от каждого бита [math]\displaystyle{ r_0 }[/math] и [math]\displaystyle{ r_{16} }[/math]. Операция XOR с константой [math]\displaystyle{ K }[/math] в рассматриваемой формуле используется для двух целей. В первую очередь данное действие увеличивает сложность любой атаки (исключая полный перебор), поскольку имеется 216 возможных функций НФ. Вдобавок, [math]\displaystyle{ K }[/math] добавляется к выражению через XOR для того, чтобы снизить вероятность коммутации прибавления [math]\displaystyle{ r_{13} }[/math] и сложения [math]\displaystyle{ r_1 }[/math] и [math]\displaystyle{ r_6 }[/math]. Несмотря на это, все ещё существует небольшая вероятность того, что операции будут коммутировать. Однако, эта вероятность мала и зависит от значения [math]\displaystyle{ K }[/math].

Внутри функции [math]\displaystyle{ f }[/math] слово разбивается на старший значащий байт (eng. Most Significant Byte или MSB) и три оставшихся байта. MSB подаётся на вход блока замещения(eng. Substitution Box or S-box), который генерирует 32 бита. В этом 32-битном выходе MSB совпадает с MSB исходного слова, а операция XOR между тремя оставшимися байтами и аналогичной частью исходного слова формирует оставшуюся часть выходного слова. Таким образом, функция [math]\displaystyle{ f }[/math] представима в виде:

[math]\displaystyle{ f(a) = SBOX(a_{msb}) \oplus (0 \parallel a_r) }[/math]

где [math]\displaystyle{ a_{msb} }[/math] — старший значащий байт слова [math]\displaystyle{ a }[/math], а [math]\displaystyle{ a_r }[/math] представляет собой оставшуюся часть входного слова.

Блок задержки (БЗ)

Блок задержки нерегулярно «прореживает» поток, идущий из НФ, чтобы затруднить восстановление состояния шифрообразующего устройства, например, путём корреляционной атаки. Суть заключается в том, что случайные слова из нелинейного вывода используются для определения включения других слов в выходной поток. Первое 32-разрядное слово на выходе НФ является первой командой управления усечением (eng. Stutter Control Word или SCW). Каждый бит данного управляющего слова разбивается на пары бит, называемые дибитами. Наборы дибитов предоставляют шифру различные инструкции — сколько циклических проходов по РСЛОС необходимо сделать, подавать ли вывод НФ на выход, как вставить этот вывод в конечный ключевой поток. После использования всех дибитов новое SCW берётся из вывода НФ. Правила определены следующим образом:

• 00 — следующее слово будет исключено из потока ключей;
• 01 — в поток ключей идёт результат операции XOR между следующим словом и константой [math]\displaystyle{ C }[/math], последующее слово удаляется из потока ключей;
• 10 — следующее слово исключается, а слово за ним попадает в ключевой поток;
• 11 — в поток ключей идёт результат операции XOR между следующим словом и константой [math]\displaystyle{ C^' }[/math] .

Здесь [math]\displaystyle{ C = 6996C53A_x }[/math], а [math]\displaystyle{ C^' }[/math] — побитовое дополнение [math]\displaystyle{ C }[/math].

Использование данного механизма позволяет пропустить в ключевой поток только около 48 % слов потока НФ.

Атаки на SOBER-t32

«Предполагай и определяй» атака на SOBER-t32 без блока задержки

В стандартной атаке «Предполагай и определяй» (англ. Guess and determine attack) угадываются некоторые слова регистра РСЛОС, а оставшиеся слова определяются путём использования уравнений на РСЛОС и НФ. Данная атака может быть успешна проведена только в том случае, если шифрообразующее устройство не содержит блок задержки. Он предотвращает атаку — не столько из-за неопределённости, которую он вносит, сколько из-за того, что последовательные слова не появляются в конечном ключевом потоке.

Упрощённая схема: биты переноса известны

В данной секции рассмотрен упрощённый вид атаки, в котором биты переноса известны заранее. Распишем выражение для выхода НФ с учётом явного вида функции [math]\displaystyle{ f }[/math], рассматривая старший значащий байт и остальные байты отдельно:

[math]\displaystyle{ v_t=(((SBOX (s_{t,M S B} \boxplus s_{t+16,MSB} \boxplus o_1)\oplus (0 \parallel s_{t,R} \boxplus s_{t+16,R} ))\boxplus s_{t+1} \boxplus s_{t+6})\oplus K) \boxplus s_{t+13} }[/math]

где [math]\displaystyle{ o_1 }[/math] обозначает бит переноса, идущий к MSB. Предполагая, что MSB константы [math]\displaystyle{ K }[/math] равен нулю, это уравнение можно разбить на две отдельные части:

[math]\displaystyle{ \begin{cases} v_{t,MSB} =((SBOX1(s_{t,MSB}\boxplus s_{t+16,MSB}\boxplus o1))\boxplus s_{t+1,MSB}\boxplus s_{t+6,MSB})\boxplus s_{t+13,MSB}\boxplus o2 \\ v_{t,R} =(((SBOX2(s_{t,MSB}\boxplus s_{t+16,MSB}\boxplus o1)\oplus (s_{t,R}\boxplus s_{t+16,R}))\boxplus s_{t+1,R}\boxplus s_{t+6,R})\oplus K_R)\boxplus s_{t+13,R }\end{cases} }[/math]

В данной системе SBOX1 представляет собой старший значащий байт выходного сигнала блока замещения, а SBOX2 — три оставшихся байта этого выхода. [math]\displaystyle{ o_2 }[/math] обозначает биты переноса представленных операций сложения. Наиболее интересным является первое выражение представленной системы. Зная старшие значащие биты слов [math]\displaystyle{ s_t, s_{t+1}, s_{t+6}, s_{t+13} }[/math], потока ключей [math]\displaystyle{ v_t }[/math] и значения битов переноса [math]\displaystyle{ o_1 }[/math] и [math]\displaystyle{ o_2 }[/math], появляется возможность рассчитать старший значащий бит слова [math]\displaystyle{ s_{t+16} }[/math].

В данной подсекции рассматривается случай, когда биты переноса не учитываются. Таким образом, на первом этапе атаки необходимо угадать только старшие значащие биты первых 16 слов РСЛОС ([math]\displaystyle{ s_t }[/math], [math]\displaystyle{ s_{t+1} }[/math], …, [math]\displaystyle{ s_{t+15} }[/math]) — в общей сложности 128 бит. Зная их и поток ключей [math]\displaystyle{ v_t }[/math], можно вычислить MSB для следующих слов [math]\displaystyle{ s_{t+16} }[/math], [math]\displaystyle{ s_{t+17} }[/math], [math]\displaystyle{ s_{t+18} }[/math] и т. д. Остаётся предсказать младшие 24 бита каждого слова, которые появляются в РСЛОС. Их можно извлечь из системы линейных уравнений, получаемых после каждой итерации работы шифратора:

• 32 линейных уравнения на основании вывода нового слова из РСЛОС.
• Дополнительное линейное уравнение на младший значащий бит. Так как входные данные для S-box известны, то для младшего значащего бита имеет место следующее выражение:[math]\displaystyle{ v^0_t = SBOX^0(s_{t,MSB}\boxplus s_{t+16,MSB}\oplus o_1)\oplus s^0_t \oplus s^0_{t+16}\oplus s^0_{t+1} \oplus s^0_{t+6}\oplus K^0\oplus s^0_{t+13} }[/math]

Таким образом, после [math]\displaystyle{ k }[/math] срабатываний РСЛОС генерируется [math]\displaystyle{ 32 \cdot k + k + 1 = 33 \cdot k + 1 }[/math] линейных уравнения, в которых неизвестными являются:

• 24 младших значащих бита изначальной последовательности [math]\displaystyle{ s_t }[/math], [math]\displaystyle{ s_{t+1} }[/math], …, [math]\displaystyle{ s_{t+15} }[/math].
• значение младшего значащего бита константы [math]\displaystyle{ K }[/math].
• 24 младших значащих бита нового слова на каждой последующей итерации.

Всего [math]\displaystyle{ 24 \cdot 17+1+24 \cdot k= 24 \cdot (17 + k) + 1 }[/math] неизвестных. Для того чтобы система была разрешима, число переменных не должно превышать число уравнений, то есть:

[math]\displaystyle{ 33 \cdot k + 1 \geq 24 \cdot (17 + k) + 1 \Longleftrightarrow k \geq 45.33 }[/math]

Важно отметить, что атака восстанавливает полное состояние шифра, за исключением 23 оставшихся бит константы [math]\displaystyle{ K }[/math]. Однако после завершения атаки эти биты легко восстанавливаются из второго уравнения системы.

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

• MSB первых 16 слов РСЛОС — 128 бит.
• MSB константы K — 8 бит.

В общей сложности для успешной атаки необходимо угадать 136 бит, что подразумевает сложность [math]\displaystyle{ 2^{136} }[/math]. В следующем разделе будет представлена сложность полной атаки, учитывающей также и биты переноса.

Полная атака

Предыдущий раздел базируется на упрощении, что биты переноса известны заранее. В действительности их также необходимо угадывать. При этом биты переноса не являются чисто случайными, распределение их значений неравномерно. Этим можно воспользоваться при атаке — вначале попытаться угадать наиболее вероятные значения. Среднее число угадываний хорошо аппроксимируется энтропией, поскольку она равна количеству информации, которая присутствует в битах переноса. Энтропии битов переноса [math]\displaystyle{ o_1 }[/math]и [math]\displaystyle{ o_2 }[/math] могут быть получены теоретически — равны 1 и 1.65 соответственно.

Для совершения атаки необходимо угадать:

• 136 бит — из предыдущего раздела.
• Биты переноса — всего [math]\displaystyle{ 47 \cdot (1 + 1.65) = 124.55 }[/math] бит.

Таким образом, сложность полной атаки есть [math]\displaystyle{ 2^{260.55} }[/math]

Атака-различитель

В криптографии атакой-различителем (eng. Distinguishing attack) называется любая форма криптоанализа некоторых зашифрованных данных, которая позволяет злоумышленнику выделить зашифрованные данные из потока случайных. Современные шифры с симметричным ключом специально разработаны для защиты от таких атак. Другими словами, современные схемы шифрования являются псевдослучайными перестановками и предназначены для «размывания» зашифрованного текста. Если найден алгоритм, который может отличить выходной поток шифра от случайного быстрее, чем полный перебор, то шифр считается взломанным.

Атаки-различители показывают, что блок задержки не может сорвать все атаки, основанные на знании большой части ключевого потока. Однако и сам блок задержки является неимоверно затратным средством, поскольку снижает производительность шифра на 52 %.

На конференции FSE в 2002 году, П. Экдал и Т. Джонсон представили вариант атаки-различителя на SOBER-t32 без блока задержки, который может быть расширен и на полную схему.

Атака на SOBER-t32 без блока задержки

Атака начинается с линеаризации выхода НФ:

[math]\displaystyle{ v_t = [s_t\oplus s_{t+1}\oplus s_{t+6}\oplus s_{t+13}\oplus s_{t+16}]\oplus w_t = \Omega_t\oplus w_t }[/math]

Шум [math]\displaystyle{ w_t }[/math], возникающий вследствие данной аппроксимации, имеет смещённое распределение. Возводя в квадрат выражение для получения нового слова из РСЛОС, получим новое линейное рекуррентное соотношение:

[math]\displaystyle{ s_{t+\tau_5} \oplus s_{t+\tau_4} \oplus s_{t+\tau_3} \oplus s_{t+\tau_2} \oplus s_{t+\tau_1} \oplus s_t = 0 }[/math]

где [math]\displaystyle{ \tau_1 = 11, \tau_2 = 13, \tau_3 = 4 \cdot 2^{32} - 4, \tau_4 = 15 \cdot 2^{32} - 4, \tau_5 = 17 \cdot 2^{32} - 4 }[/math].

После этого считается XOR между соседними битами в потоке [math]\displaystyle{ v_t }[/math]:

[math]\displaystyle{ v_t[i]\oplus v_t[i-1] = \Omega_t[i]\oplus \Omega_t[i-1] \oplus w_t[i]\oplus w_t[i-1] }[/math] Затем рассчитывается распределение [math]\displaystyle{ F[i] }[/math] для значений [math]\displaystyle{ w_t[i] \oplus w_t[i+1] }[/math]. Согласно результатам моделирования это распределение достаточно смещено. Наибольшее смещение было обнаружено у значений, получаемых на 29-ом и 30-ом битах. Смещение зависит от соответствующих битов [math]\displaystyle{ K }[/math] и для битов 29 и 30 составляет не менее [math]\displaystyle{ \epsilon_{30} = 0.0052 }[/math]

Теперь, имея поток из НФ [math]\displaystyle{ v_0, v_1,..., v_{N-1} }[/math], можно воспользоваться введённым ранее рекуррентным выражением для подсчёта:

[math]\displaystyle{ v_{t+\tau_5} \oplus v_{t+\tau_4} \oplus v_{t+\tau_3} \oplus v_{t+\tau_2} \oplus v_{t+\tau_1} \oplus v_t = \Omega_{t+\tau_5} \oplus w_{t+\tau_5} \oplus \Omega_{t+\tau_4} \oplus w_{t+\tau_4} \oplus \Omega_{t+\tau_3} \oplus w_{t+\tau_3} \oplus \Omega_{t+\tau_2} \oplus w_{t+\tau_2} \oplus \Omega_{t+\tau_1} \oplus w_{t+\tau_1} \oplus \Omega_{t} \oplus w_{t} }[/math]

где сумма всех [math]\displaystyle{ \Omega_j }[/math] по определению равна нулю. Таким образом, данное выражение может быть переписано в следующем виде:

[math]\displaystyle{ v_{t+\tau_5} \oplus v_{t+\tau_4} \oplus v_{t+\tau_3} \oplus v_{t+\tau_2} \oplus v_{t+\tau_1} \oplus v_t = \bigoplus^{5}_{j=0}w_{t+\tau_j} }[/math]

Обозначим левую часть верхнего выражения как [math]\displaystyle{ V_t }[/math], а правую — [math]\displaystyle{ W_t }[/math]. Теперь возможно рассчитать следующую вероятность:

[math]\displaystyle{ P(V_t[i] \oplus V_t[i-1] = 0) = P(W_t[i] \oplus W_t[i-1] = 0) = 12 + 2^{5} \cdot \epsilon^{6}_i }[/math]

где [math]\displaystyle{ \epsilon }[/math] обозначает смещение. Используя эту формулу, можно получить финальное значение вероятности корреляции шести независимых позиций в потоковом ключе для [math]\displaystyle{ i = 30 }[/math]:

[math]\displaystyle{ P_0 = P(V_t[30] \oplus V_t[29] = 0) = 12+ 2^5 \cdot (0.0052)^6 \thickapprox 12 + 2^{ - 40.5} }[/math]

Для того чтобы отличить данное неравномерное распределение [math]\displaystyle{ P_0 }[/math] от равномерного источника [math]\displaystyle{ P_u }[/math], между двумя распределениями вычисляется информация Чернова:

[math]\displaystyle{ C(P_0, P_U) = -\underset{0 \leq \lambda \leq 1}\min \log_2\sum _x P^\lambda_0(x)\cdot P^{1 - \lambda}_U(x)\approx 2^{-81.5} }[/math]

Чтобы получить вероятность ошибки [math]\displaystyle{ P_e = 2^{-32} }[/math], необходимо [math]\displaystyle{ N = 286.5 }[/math] выборок из ключевого потока. Каждая выборка состоит из [math]\displaystyle{ \tau_5 = 17\cdot2^{32} \approx 2^{36} }[/math] бит, поэтому всего необходимо [math]\displaystyle{ N + \tau_5 \leq 2^{87} }[/math] слов из потока НФ, чтобы отличить SOBER-t32 (без блока задержки) от остального потока из единого источника.

Атака на полную версию SOBER-t32

Данная версия основывается на знании слов [math]\displaystyle{ v_t, v_{t+11}, v_{t+13}, v_{4 \cdot 2^{32} - 4},v_{15 \cdot 2^{32} - 4}, v_{17 \cdot 2^{32} - 4} }[/math] из потока НФ. Необходимо отыскать эти слова в потоке ключей [math]\displaystyle{ z_j }[/math], то есть уже после прохождения блока задержки. Прежде всего высчитывается вероятность того, что конкретное слово будет найдено в своей наиболее вероятной позиции в потоке ключей. Берётся слово [math]\displaystyle{ z_i }[/math] из потока ключей, которое происходит от конкретного слова [math]\displaystyle{ v_t }[/math] из потока НФ. Затем вычисляется вероятность того, что последующие слова появятся в своих наиболее вероятных положениях в ключевом потоке.

По статистике наиболее вероятной позицией для [math]\displaystyle{ v_{t+11} }[/math] в потоке ключей является [math]\displaystyle{ z_{i+6} }[/math], для [math]\displaystyle{ v_{t+13} }[/math] — [math]\displaystyle{ z_{i+7} }[/math]. Согласно результатам симуляций вероятности найти данные слова в таких положениях в потоке ключей составляют 21,7 % и 19,8 % соответственно. Для остальных трёх слов необходимы более сложные теоретические выкладки. Для [math]\displaystyle{ n }[/math]-го слова, поступающего в блок задержки, можно ожидать, что [math]\displaystyle{ \left \lfloor \frac{n}{25} \right \rfloor }[/math]слов управления задержкой (SCW) использовались ранее. Также ожидается, что из всех оставшихся (не SCW) слов 50 % в конечном счёте попадут в поток ключей. При этом наиболее вероятная позиция для слова [math]\displaystyle{ v_n }[/math]:

[math]\displaystyle{ E[position(v_n)] = \frac{n - \left \lfloor \frac{n}{25} \right \rfloor}{2} }[/math]

Вероятность найти слово [math]\displaystyle{ v_n }[/math] в данной наиболее вероятной позиции рассчитывается, исходя из вероятности того, что [math]\displaystyle{ n }[/math]-ое слово управления задержкой появится в своей наиболее вероятной позиции в потоке НФ. Эту вероятность легче рассчитать теоретически, и легко увидеть, что асимптотическое поведение обоих значений будет одинаковым.

Ранее вводилось, что два дибита — 00 и 11 — определяют, что произойдёт со следующим словом. Два других дибита — 01 и 10 — определяют задержку двух следующих слов. Поскольку каждый дибит появляется с одинаковой вероятностью, ожидается, что один дибит в среднем использует 1.5 слова из потока НФ. SCW выдаёт 16 дибитов и, таким образом, использует в среднем 24 слова. Поскольку SCW также поступает из потока НФ, ожидается, что [math]\displaystyle{ n }[/math]-й SCW находится на [math]\displaystyle{ 25n }[/math] позиции потока НФ. Вероятность того, что данный SCW действительно находится в этой позиции, равна вероятности того, что [math]\displaystyle{ n }[/math] слов управления задержкой определят задержку ровно [math]\displaystyle{ 24n }[/math] слов из потока НФ. Это означает, что половина из [math]\displaystyle{ 16n }[/math] дибитов должна определять задержку одного слова, а другая половина — задержк

у двух слов. Эта вероятность может быть рассчитана следующим образом:

[math]\displaystyle{ P(position(SCW[n]) = 25n) =\left ( \frac{16n}{8n} \right )\left ( \frac{1}{2} \right )^{8n+8n} =\frac{16n!}{(8n!)^2 \cdot 2^{16n}} }[/math]

С помощью формулы Стирлинга [math]\displaystyle{ n! \approx \sqrt{2\pi n} \cdot n^n \cdot e^{-n} }[/math]верхнее выражение упрощается:

[math]\displaystyle{ P(position(SCW[n]) = 25n) \approx \frac{1}{\sqrt{8 \pi n}} }[/math]

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

[math]\displaystyle{ P(position(v_n) = \frac{n - \left \lfloor \frac{n}{25} \right \rfloor}{2}) = \frac{\lambda}{\sqrt{\frac{8 \pi n}{25}}} }[/math]

где [math]\displaystyle{ \lambda\approx 0.84 }[/math] — константа (значение получено экспериментально).

Используя данную формулу, можно рассчитать вероятности для слов [math]\displaystyle{ v_{4 \cdot 2^{32} - 4},v_{15 \cdot 2^{32} - 4}, v_{17 \cdot 2^{32} - 4} }[/math]. Они — при условии, что предыдущие слова находятся в ключевом потоке в их наиболее вероятном положении — равны [math]\displaystyle{ 2^{-17.3}, 2^{-18.0}, 2^{-16.8} }[/math] соответственно. Таким образом, слова [math]\displaystyle{ v_{t+11}, v_{t+13}, v_{4 \cdot 2^{32} - 4},v_{15 \cdot 2^{32} - 4}, v_{17 \cdot 2^{32} - 4} }[/math] присутствуют в итоговом потоке ключе в своих наиболее вероятных позициях равна:

[math]\displaystyle{ P_0 = 0.217 \cdot 0.198 \cdot 2^{-17.3} \cdot 2^{-18.0} \cdot 2^{-16.8} = 2^{-56} }[/math]

Теперь, аналогично предыдущему пункту, можно рассчитать информацию Чернова и количество слов, необходимых для атаки:

[math]\displaystyle{ C(P_Y, P_U) \approx P^2_0 \cdot C(P_W, P_U) = 2^{2 \cdot -56.6} \cdot 2^{-81.5} = 2^{-194.7} }[/math]

где [math]\displaystyle{ P_W }[/math] — распределение НФ-потока. Для достижения ошибки в [math]\displaystyle{ P_e = 2^{-32} }[/math] необходимо [math]\displaystyle{ 32 \cdot 2^{194.7} = 2^{199.7} }[/math] выборок — для атаки потребуется [math]\displaystyle{ 2^{199.7} }[/math] последовательностей из [math]\displaystyle{ 17 \cdot 2^{32} }[/math] слов из потока ключей, всего [math]\displaystyle{ L = 2^{200} \geq 2^{199.7} + 17 \cdot 2^{32} }[/math] слов.

Ссылки

• NESSIE (англ.). — Официальный сайт NESSIE.
• Требования NESSIE (англ.). — Описание основных требований NESSIE.
• Алгоритмы шифрования – участники конкурса NESSIE. Часть 1 (рус.).
• Алгоритмы шифрования – участники конкурса NESSIE. Часть 2 (рус.).
• Алгоритмы шифрования – участники конкурса NESSIE. Часть 3 (рус.).