SNOW (шифр)

SNOW — словоориентированный синхронный поточный шифр, разработанный Лундском университете (Швеция). На данный момент у него существует 3 модификации: SNOW 2.0, SNOW 3G, SNOW-V. SNOW 3G используется для безопасной передачи мобильных данных.

ИсторияПравить

SNOW 1.0, первоначально просто SNOW, был разработан в 2000 году. Шифр работает с 32-битными словами и поддерживает как 128-, так и 256-битные ключи. Шифр состоит из комбинации регистра сдвига с линейной обратной связью (РСЛОС) и конечного автомата (КА).

В первой версии были обнаружены слабые места, и в результате SNOW не был включен в набор алгоритмов NESSIE. В 2003 году авторы разработали новую версию шифра SNOW 2.0, в которой устранили недостатки и улучшили производительность. Во время оценки группой экспертов по безопасным алгоритмам (англ. SAGE) из Европейского института телекоммуникационных стандартов(англ. ETSI) алгоритм шифрования был дополнительно изменён, чтобы повысить его устойчивость к алгебраическим атакам. Результатом таких улучшений в 2006 году стала модификация шифра SNOW 3G.

В 2019 году Ericsson Research совместно с Лундским университетом пересмотрели алгоритм SNOW 3G и обновили его до нового, более быстрого шифра под названием SNOW-V, который может быть использован для безопасной передачи данных в новом поколении связи 5G.

Схема работы SNOWПравить

Общая схема работыПравить

 

Схема работы SNOW 1.0

Генератор состоит из регистра сдвига с линейной обратной связью длины 16 над полем ${\mathbb{F}}_{2^{32}}$$\mathbb{F}_{2^{32}}$ . Выход регистра подается на вход конечного автомата. КА состоит из двух 32-битных регистров, называемых R1 и R2, а также некоторых операций для вычисления вывода и следующего состояния (следующего значения R1 и R2). Работа шифра выглядит следующим образом. Сначала выполняется инициализация ключа. Эта процедура обеспечивает начальные значения для РСЛОС, а также для регистров R1, R2 в конечном автомате. Затем первые 32 бита ключевого потока вычисляются путем поразрядного сложения выходных данных КА и последней записи РСЛОС. После этого весь процесс синхронизируется, и следующие 32 бита ключевого потока вычисляются путем ещё одного побитового сложения выходных данных конечного автомата и последней записи РСЛОС. Мы снова синхронизируем и продолжаем в том же духе.

Детальная схема работыПравить

В начальный момент времени t = 0 происходит инициализация регистра сдвига 32-битными значениями $s(1),s(2),...,s(16)$$s(1),s(2),...,s(16)$ , которые задаются при помощи сгенерированного ключа.

Функция обратной связи для регистра задается многочленом:

$p(x)=x^{16}+x^{13}+x^7+{\mathrm{\alpha <!--\; \alpha \; -->}}^{-<!--\; -\; -->1},$$p(x)=x^{16}+x^{13}+x^{7}+\alpha ^{-1},$ 

где ${\mathbb{F}}_{2^{32}}$$\mathbb{F}_{2^{32}}$  задаётся неприводимым многочленом

$\mathrm{\pi <!--\; \pi \; -->}(x)=x^{32}+x^{29}+x^{20}+x^{15}+x^{10}+x+1$$\pi (x)=x^{32}+x^{29}+x^{20}+x^{15}+x^{10}+x+1$ ,

над ${\mathbb{F}}_2$$\mathbb {F} _{2}$  и $\mathrm{\pi <!--\; \pi \; -->}(\mathrm{\alpha <!--\; \alpha \; -->})=0$$\pi (\alpha )=0$ .

Выход КА назовем $FS{M}_{out}$$FSM_{out}$ . Он рассчитывается по следующей формуле:

$FSMout=(s(1)⊞<!--\; ⊞\; -->R1)\oplus <!--\; \oplus \; -->R2$$FSM{out}=(s(1)\boxplus R1)\oplus R2$ ,

где $⊞<!--\; ⊞\; -->$$\boxplus$  — целочисленное сложение по$\mathrm{mod}{2}^{32}$$\mod 2^{32}$ .

Выход конечного автомата $FS{M}_{out}$$FSM_{out}$  сравнивается с $s(16)$$s(16)$  по модулю 2 для формирования потокового ключа, то есть

$runningkey=FSMout\oplus <!--\; \oplus \; -->s(16)$$runningkey=FSM{out}\oplus s(16)$ ,

где $\oplus <!--\; \oplus \; -->$$\oplus$  — сложение по$\mathrm{mod}2$$\mod 2$ .

Внутри конечного автомата новые значения для R1 и R2 присваиваются по следующим формулам:

$newR1=((FSMout⊞<!--\; ⊞\; -->R2)⋘<!--\; ⋘\; -->7)\oplus <!--\; \oplus \; -->R1$$newR1=((FSM{out}\boxplus R2)\lll 7)\oplus R1$ ,

где $⋘<!--\; ⋘\; -->$$\lll$  — циклический сдвиг влево

$R2=S(R1)$$R2=S(R1)$ 

$R1=newR1$$R1=newR1$ 

Наконец, S-блок, обозначаемый $S(x)$$S(x)$ , состоит из четырёх идентичных битовых S-блоков 8×8 и перестановки полученных битов. Входные данные разделены на 4 байта, каждый байт входит в нелинейное отображение от 8 бит до 8 бит. После этого отображения биты в результирующем слове переставляются, чтобы сформировать окончательный результат S-блока.

Для конечного формирования шифртекста потоковый ключ сравнивается с открытым текстом по модулю 2.

Известные атакиПравить

• В феврале 2002 года Филипп Хоукс и Грегори Роуз описали атаку «Предполагай и определяй» (англ.  англ. Guess and determine attack) на SNOW 1.0, в котором используются в основном два свойства, чтобы снизить сложность атаки ниже исчерпывающего поиска ключей. Во-первых, тот факт, что автомат имеет только один вход s(1). Это позволяет злоумышленнику инвертировать операции в конечном автомате и получать больше неизвестных только из нескольких предположений. Второе свойство — неудачный выбор полинома обратной связи в SNOW 1.0.
• В августе 2003 года Даи Ватанабе, Алекс Бирюков и Кристоф Де Канньер описали атаку на SNOW 2.0 методом линейной маскировки. Эта атака использует $2^{230}$$2^{230}$  битов потока и $2^{225}$$2^{225}$  шагов анализа, что быстрее, чем исчерпывающий поиск 256-битного ключа.

ПрименениеПравить

SNOW 2.0 — один из потоковых шифров, вошедших в стандарт шифрования ISO/IEC ISO/IEC 18033-4, который определяет функции вывода для объединения ключевого потока с открытым текстом, генераторы ключевого потока для создания ключевого потока и идентификаторы объектов, назначенные выделенным генераторам ключевого потока в соответствии с ISO/IEC 9834 для поточных шифров.

SNOW 3Gвыбран в качестве генератора потоковых ключей для алгоритмов шифрования 3GPP UEA2 и UIA2.