SOBER-t32

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

${\displaystyle {\vec {S_{t}}}=(s_{t},s_{t+1},s_{t+2},...s_{t+16})=(r_{0},r_{1},r_{2},...r_{16})}$

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

${\displaystyle s_{t+17}=s_{t+15}\oplus s_{t+4}\oplus \alpha \cdot s_{t}}$[14]

где ${\displaystyle \alpha =C2DB2AA3_{x}}$, ${\displaystyle \oplus }$ — исключающее или (XOR).

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

${\displaystyle v_{t}=((f(s_{t}\boxplus s_{t+16})\boxplus s_{t+1}\boxplus s_{t+6})\oplus K)\boxplus s_{t+13}}$[16]

где:

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

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

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

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

${\displaystyle f(a)=SBOX(a_{msb})\oplus (0\parallel a_{r})}$[19]

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

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

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

Здесь ${\displaystyle C=6996C53A_{x}}$, а ${\displaystyle C^{'}}$ — побитовое дополнение ${\displaystyle C}$.

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

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

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

${\displaystyle v_{t}=(((SBOX(s_{t,MSB}\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}}$

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

${\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}}}$

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

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

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

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

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

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

${\displaystyle 33\cdot k+1\geq 24\cdot (17+k)+1\Longleftrightarrow k\geq 45.33}$

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

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

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

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

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

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

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

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

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

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

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

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

${\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}}$[28]

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

${\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}$

где ${\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}$.

После этого считается XOR между соседними битами в потоке ${\displaystyle v_{t}}$:

${\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]}$ Затем рассчитывается распределение ${\displaystyle F[i]}$ для значений ${\displaystyle w_{t}[i]\oplus w_{t}[i+1]}$. Согласно результатам моделирования это распределение достаточно смещено. Наибольшее смещение было обнаружено у значений, получаемых на 29-ом и 30-ом битах. Смещение зависит от соответствующих битов ${\displaystyle K}$ и для битов 29 и 30 составляет не менее ${\displaystyle \epsilon _{30}=0.0052}$[30]

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

${\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}}$

где сумма всех ${\displaystyle \Omega _{j}}$ по определению равна нулю. Таким образом, данное выражение может быть переписано в следующем виде:

${\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 _{j=0}^{5}w_{t+\tau _{j}}}$

Обозначим левую часть верхнего выражения как ${\displaystyle V_{t}}$, а правую — ${\displaystyle W_{t}}$. Теперь возможно рассчитать следующую вероятность:

${\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 _{i}^{6}}$

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

${\displaystyle P_{0}=P(V_{t}[30]\oplus V_{t}[29]=0)=12+2^{5}\cdot (0.0052)^{6}\thickapprox 12+2^{-40.5}}$

Для того чтобы отличить данное неравномерное распределение ${\displaystyle P_{0}}$ от равномерного источника ${\displaystyle P_{u}}$, между двумя распределениями вычисляется информация Чернова[31]:

${\displaystyle C(P_{0},P_{U})=-{\underset {0\leq \lambda \leq 1}{\min }}\log _{2}\sum _{x}P_{0}^{\lambda }(x)\cdot P_{U}^{1-\lambda }(x)\approx 2^{-81.5}}$

Чтобы получить вероятность ошибки ${\displaystyle P_{e}=2^{-32}}$, необходимо ${\displaystyle N=286.5}$ выборок из ключевого потока. Каждая выборка состоит из ${\displaystyle \tau _{5}=17\cdot 2^{32}\approx 2^{36}}$ бит, поэтому всего необходимо ${\displaystyle N+\tau _{5}\leq 2^{87}}$ слов из потока НФ, чтобы отличить SOBER-t32 (без блока задержки) от остального потока из единого источника.

Данная версия основывается на знании слов ${\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}}$ из потока НФ. Необходимо отыскать эти слова в потоке ключей ${\displaystyle z_{j}}$, то есть уже после прохождения блока задержки. Прежде всего высчитывается вероятность того, что конкретное слово будет найдено в своей наиболее вероятной позиции в потоке ключей. Берётся слово ${\displaystyle z_{i}}$ из потока ключей, которое происходит от конкретного слова ${\displaystyle v_{t}}$ из потока НФ. Затем вычисляется вероятность того, что последующие слова появятся в своих наиболее вероятных положениях в ключевом потоке.

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

${\displaystyle E[position(v_{n})]={\frac {n-\left\lfloor {\frac {n}{25}}\right\rfloor }{2}}}$[33]

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

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

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

${\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}}}}$

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

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

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

${\displaystyle P(position(v_{n})={\frac {n-\left\lfloor {\frac {n}{25}}\right\rfloor }{2}})={\frac {\lambda }{\sqrt {\frac {8\pi n}{25}}}}}$

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

Используя данную формулу, можно рассчитать вероятности для слов ${\displaystyle v_{4\cdot 2^{32}-4},v_{15\cdot 2^{32}-4},v_{17\cdot 2^{32}-4}}$. Они — при условии, что предыдущие слова находятся в ключевом потоке в их наиболее вероятном положении — равны ${\displaystyle 2^{-17.3},2^{-18.0},2^{-16.8}}$ соответственно. Таким образом, слова ${\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}}$ присутствуют в итоговом потоке ключе в своих наиболее вероятных позициях равна:

${\displaystyle P_{0}=0.217\cdot 0.198\cdot 2^{-17.3}\cdot 2^{-18.0}\cdot 2^{-16.8}=2^{-56}}$

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

${\displaystyle C(P_{Y},P_{U})\approx P_{0}^{2}\cdot C(P_{W},P_{U})=2^{2\cdot -56.6}\cdot 2^{-81.5}=2^{-194.7}}$

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