SNOW (шифр)

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
У слова «Snow» есть и другие значения: см. Snow (значения).

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

История

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

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

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

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

Общая схема работы

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

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

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

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

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

[math]\displaystyle{ p (x) = x^{16} + x^{13} + x^{7} + \alpha^{-1}, }[/math]

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

[math]\displaystyle{ \pi (x) = x^{32} + x^{29} + x^{20} + x^{15} + x^{10} + x + 1 }[/math],

над [math]\displaystyle{ \mathbb{F}_{2} }[/math] и [math]\displaystyle{ \pi (\alpha) = 0 }[/math].

Выход КА назовем [math]\displaystyle{ FSM_{out} }[/math]. Он рассчитывается по следующей формуле:

[math]\displaystyle{ FSM{out} = (s(1) \boxplus R1) \oplus R2 }[/math],

где [math]\displaystyle{ \boxplus }[/math] — целочисленное сложение по[math]\displaystyle{ \mod2^{32} }[/math].

Выход конечного автомата [math]\displaystyle{ FSM_{out} }[/math] сравнивается с [math]\displaystyle{ s(16) }[/math] по модулю 2 для формирования потокового ключа, то есть

[math]\displaystyle{ running key = FSM{out} \oplus s(16) }[/math],

где [math]\displaystyle{ \oplus }[/math] — сложение по[math]\displaystyle{ \mod2 }[/math].

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

[math]\displaystyle{ newR1 = ((FSM{out}\boxplus R2) \lll 7) \oplus R1 }[/math],

где [math]\displaystyle{ \lll }[/math] — циклический сдвиг влево

[math]\displaystyle{ R2=S(R1) }[/math]
[math]\displaystyle{ R1=newR1 }[/math]

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

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

Известные атаки

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

Применение

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

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

Примечания

  1. ↑ 1,0 1,1 Patrik Ekdahl, Thomas Johansson. SNOW-a new stream cipher : [англ.] // Proceedings of first open NESSIE workshop, KU-Leuven. — 2000. — 13 November. — P. 167—168.
  2. ↑ 2,0 2,1 Patrik Ekdahl, Thomas Johansson. A New Version of the Stream Cipher SNOW : [англ.] // Springer. — 2003. — Vol. 2595. — P. 47—61. — ISSN 0302-9743.
  3. ↑ O. Billet, H. Gilbert. Resistance of SNOW 2.0 Against Algebraic Attacks : [англ.] // Springer. — 2005. — Vol. 3376. — P. 19—28. — doi:10.1007/978-3-540-30574-3_3.
  4. ↑ Security algorithms. Дата обращения: 25 ноября 2020. Архивировано 26 июля 2020 года.
  5. ↑ UEA2 Design and Evaluation Report (англ.) (6 сентября 2006). Дата обращения: 20 октября 2020. Архивировано 29 октября 2020 года.
  6. ↑ 6,0 6,1 J. Molina-Gil, Caballero-Gil, Caballero-Gil, Amparo Fúster-Sabater. Analysis and Implementation of the SNOW 3G Generator Used in 4G/LTE Systems : [англ.] // Springer. — 2013. — Vol. 239. — P. 499—508. — ISBN 978-3-319-01854-6. — doi:10.1007/978-3-319-01854-6_51.
  7. ↑ P.Ekdahl, T.Johansson, A.Maximov, J.Yang. A new SNOW stream cipher called SNOW-V : [англ.] // ToSC. — 2019. — Vol. 2019, no. 3. — P. 1—42. — doi:10.13154/tosc.v2019.i3.1-42.
  8. ↑ Philip Hawkes, Gregory G. Rose. Guess-and-determine attacks on SNOW : [англ.] // Springer. — 2002. — Vol. 2595. — P. 37–46. — doi:10.1007/3-540-36492-7\_4.
  9. ↑ Dai Watanabe, Alex Biryukov, Christophe De Cannière. A Distinguishing Attack of SNOW 2.0 with Linear Masking Method : [англ.] // Springer. — 2003. — Vol. 3006. — P. 222—233.
  10. ↑ ISO/IEC 18033-4:2011 : Information technology — Security techniques — Encryption algorithms — Part 4: Stream ciphers : [англ.]. — 2. — International Organization for Standardization (ISO), 2011. — 92 p.
  11. ↑ UEA2 & UIA2 Specification (англ.) (16 марта 2009). Дата обращения: 13 ноября 2020. Архивировано 19 января 2022 года.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=SNOW_(шифр)&oldid=5905669