SOBER-t32 () — cинхронный аддитивный потоковый шифр из семейства SOBER. Авторами являются Филип Хаукес и Грегори Роуз (Австралия).
Историческая справка SOBER — семейство потоковых шифров, широко используемых во встроенных системах, предложенное Г. Роузом в 1998 году. На данный момент семейство включает в себя шифры SOBER, SOBER-II, S16, S32, SOBER-t8, SOBER-t16, SOBER-t32 и SOBER-128.
Первый программный потоковый шифр из семейства был разработан с целью удовлетворения основных требований встроенных приложений, которые накладывают жёсткие ограничения на объём вычислительной мощности, программного пространства и памяти, доступной для программных алгоритмов шифрования. Шифрование речи для беспроводной телефонии — одна из первых и главных сфер применения шифров SOBER. Так как большинство используемых мобильных телефонов представляют собой микропроцессор и память, быстрый программный потоковый шифр, использующий небольшое количество памяти, является наиболее подходящим вариантом для таких приложений. Многие методы генерации потока псевдослучайных битов основаны на регистрах сдвига с линейной обратной связью (РСЛОС) над конечным полем Галуа порядка 2. Такие шифры неэффективно использовать на ЦПУ. Шифры семейства SOBER обходят данную проблему, используя РСЛОС над полем и ряд методов, позволяющих значительно увеличить скорость генерации псевдослучайной последовательности в программном обеспечении на микропроцессоре.
Стремление усилить безопасность и использовать шифр в 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 между зашифрованным текстом и потоком ключей.
Основными элементами шифрообразующего устройства являются:
Регистр сдвига с линейной обратной связью (РСЛОС), который использует рекуррентное соотношение для создания последовательности состояний (слов) . Нелинейный фильтр (НФ) — создаёт поток из , создавая нелинейную комбинацию из полученных слов. Блок «задержки», или «усечения» (БЗ) — генерирует поток ключей , прорежая НФ-поток нерегулярным образом.
Элементы представлены над полем Галуа с использованием базиса . Если , то представим как , где . Работа шифра основана на 32-битных операциях над по модулю полинома вида:
Сложение двух элементов в представляется как сложение соответствующих полиномов с приведением коэффициентов по модулю два. Умножение двух элементов в представляется как умножение соответствующих полиномов с приведением коэффициентов полиномов по модулю два. Результат умножения затем приводится по модулю неприводимого полинома .
Регистр сдвига с линейной обратной связью (РСЛОС) РСЛОС — сдвиговый регистр длины 17, где каждая ячейка содержит одно 32-разрядное слово. Таким образом, полная внутренняя память составляет 544 бит. Состояние РСЛОС в момент времени задаётся вектором:
Следующее состояние РСЛОС получается путём сдвига предыдущего состояния на один шаг. Новое слово вычисляется как линейная комбинация слов, содержащихся в РСЛОС, по следующему правилу:
где , — исключающее или (XOR).
Нелинейный фильтр (НФ) Нелинейный фильтр предназначен для уменьшения вероятности успешного криптоанализа шифра. Основная цель НФ — скрыть линейность выходного потока регистра. В каждый момент времени нелинейный фильтр берёт из РСЛОС пять слов и вычисляет значение, обозначаемое :
где:
— сложение по модулю . константа — слово, которое определяется во время инициализации РСЛОС и сохраняется до конца сеанса. задаёт некоторую нелинейную функцию.
Функция используется для достижения нескольких целей. Во-первых, она скрывает линейность в младшем значащем бите (eng. Least Significant Byte или LSB) и добавляет значительную нелинейность в оставшиеся биты. Во-вторых, она гарантирует, что результат сложения и не коммутирует с результатом сложения и . В-третьих, обеспечивает, чтобы каждый бит вывода НФ зависел от каждого бита и . Операция XOR с константой в рассматриваемой формуле используется для двух целей. В первую очередь данное действие увеличивает сложность любой атаки (исключая полный перебор), поскольку имеется 216 возможных функций НФ. Вдобавок, добавляется к выражению через XOR для того, чтобы снизить вероятность коммутации прибавления и сложения и . Несмотря на это, все ещё существует небольшая вероятность того, что операции будут коммутировать. Однако, эта вероятность мала и зависит от значения .
Внутри функции слово разбивается на старший значащий байт (eng. Most Significant Byte или MSB) и три оставшихся байта. MSB подаётся на вход блока замещения(eng. Substitution Box or S-box), который генерирует 32 бита. В этом 32-битном выходе MSB совпадает с MSB исходного слова, а операция XOR между тремя оставшимися байтами и аналогичной частью исходного слова формирует оставшуюся часть выходного слова. Таким образом, функция представима в виде:
где — старший значащий байт слова , а представляет собой оставшуюся часть входного слова.
Блок задержки (БЗ) Блок задержки нерегулярно «прореживает» поток, идущий из НФ, чтобы затруднить восстановление состояния шифрообразующего устройства, например, путём корреляционной атаки. Суть заключается в том, что случайные слова из нелинейного вывода используются для определения включения других слов в выходной поток. Первое 32-разрядное слово на выходе НФ является первой командой управления усечением (eng. Stutter Control Word или SCW). Каждый бит данного управляющего слова разбивается на пары бит, называемые дибитами. Наборы дибитов предоставляют шифру различные инструкции — сколько циклических проходов по РСЛОС необходимо сделать, подавать ли вывод НФ на выход, как вставить этот вывод в конечный ключевой поток. После использования всех дибитов новое SCW берётся из вывода НФ. Правила определены следующим образом:
00 — следующее слово будет исключено из потока ключей; 01 — в поток ключей идёт результат операции XOR между следующим словом и константой , последующее слово удаляется из потока ключей; 10 — следующее слово исключается, а слово за ним попадает в ключевой поток; 11 — в поток ключей идёт результат операции XOR между следующим словом и константой .
Здесь , а — побитовое дополнение .
Использование данного механизма позволяет пропустить в ключевой поток только около 48 % слов потока НФ.
Атаки на SOBER-t32
«Предполагай и определяй» атака на SOBER-t32 без блока задержки В стандартной атаке «Предполагай и определяй» (англ. Guess and determine attack) угадываются некоторые слова регистра РСЛОС, а оставшиеся слова определяются путём использования уравнений на РСЛОС и НФ. Данная атака может быть успешна проведена только в том случае, если шифрообразующее устройство не содержит блок задержки. Он предотвращает атаку — не столько из-за неопределённости, которую он вносит, сколько из-за того, что последовательные слова не появляются в конечном ключевом потоке.
Упрощённая схема: биты переноса известны В данной секции рассмотрен упрощённый вид атаки, в котором биты переноса известны заранее. Распишем выражение для выхода НФ с учётом явного вида функции , рассматривая старший значащий байт и остальные байты отдельно:
где обозначает бит переноса, идущий к MSB. Предполагая, что MSB константы равен нулю, это уравнение можно разбить на две отдельные части: В данной системе SBOX1 представляет собой старший значащий байт выходного сигнала блока замещения, а SBOX2 — три оставшихся байта этого выхода. обозначает биты переноса представленных операций сложения. Наиболее интересным является первое выражение представленной системы. Зная старшие значащие биты слов , потока ключей и значения битов переноса и , появляется возможность рассчитать старший значащий бит слова .
В данной подсекции рассматривается случай, когда биты переноса не учитываются. Таким образом, на первом этапе атаки необходимо угадать только старшие значащие биты первых 16 слов РСЛОС (, , …, ) — в общей сложности 128 бит. Зная их и поток ключей , можно вычислить MSB для следующих слов , , и т. д. Остаётся предсказать младшие 24 бита каждого слова, которые появляются в РСЛОС. Их можно извлечь из системы линейных уравнений, получаемых после каждой итерации работы шифратора:
32 линейных уравнения на основании вывода нового слова из РСЛОС. Дополнительное линейное уравнение на младший значащий бит. Так как входные данные для S-box известны, то для младшего значащего бита имеет место следующее выражение: Таким образом, после срабатываний РСЛОС генерируется линейных уравнения, в которых неизвестными являются:
24 младших значащих бита изначальной последовательности , , …, . значение младшего значащего бита константы . 24 младших значащих бита нового слова на каждой последующей итерации.
Всего неизвестных. Для того чтобы система была разрешима, число переменных не должно превышать число уравнений, то есть:
Важно отметить, что атака восстанавливает полное состояние шифра, за исключением 23 оставшихся бит константы . Однако после завершения атаки эти биты легко восстанавливаются из второго уравнения системы.
Для оценки сложности атаки необходимо знать число бит, которые требуется угадать. В данной версии, следующие биты должны быть угаданы:
MSB первых 16 слов РСЛОС — 128 бит. MSB константы K — 8 бит.
В общей сложности для успешной атаки необходимо угадать 136 бит, что подразумевает сложность . В следующем разделе будет представлена сложность полной атаки, учитывающей также и биты переноса.
Полная атака Предыдущий раздел базируется на упрощении, что биты переноса известны заранее. В действительности их также необходимо угадывать. При этом биты переноса не являются чисто случайными, распределение их значений неравномерно. Этим можно воспользоваться при атаке — вначале попытаться угадать наиболее вероятные значения. Среднее число угадываний хорошо аппроксимируется энтропией, поскольку она равна количеству информации, которая присутствует в битах переноса. Энтропии битов переноса и могут быть получены теоретически — равны 1 и 1.65 соответственно.
Для совершения атаки необходимо угадать:
136 бит — из предыдущего раздела. Биты переноса — всего бит.
Таким образом, сложность полной атаки есть
Атака-различитель