Поточный шифр SNOW

Зима. Время валяться в сугробах и играть в снежки. Или почитать статью о поточных шифрах. Кому что больше нравится.

Данная статья является обзорной. Мы поговорим о принципе работы 1 версии SNOW 1.0, ^[1] вкратце о различных, совершенных на шифр атаках и о применении его модификаций.

Основная информация

И самая важная, на мой взгляд.

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

У него есть 3 модификации. Причем одна из них — SNOW 3G, используется для передачи мобильных данных. Последняя версия SNOW-V была разработана для 5G сетей, но пока не используется.

Немного про историю

SNOW 1.0 ^[1], первоначально просто SNOW, был разработан в 2000 году в Лундском университете (Швеция).

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

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

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

Принцип работы нарисован на картинке. Подробности описаны ниже.

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

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

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

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

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

$p (x)=x^{16} + x^{13} + x^{7} + alpha^{-1}$

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

$pi (x)=x^{32} + x^{29} + x^{20} + x^{15} + x^{10} + x + 1,$

над $mathbb{F}_{2}$ , pi (alpha)=0 .

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

$FSM_{out}=(s(1) boxplus R1) oplus R2,$

где boxplus целочисленное сложение по $mod2^{32}$ .

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

$running key=FSM_{out} oplus s(16),$

где oplus сложение по mod 2.

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

$newR1=((FSM_{out}boxplus R2) lll 7) oplus R1,$

где lll - циклический сдвиг влево,

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

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

Более подробно описан алгоритм шифрования здесь ^[1].

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

В феврале 2002 года Филипп Хоукс и Грегори Роуз описали атаку «Guess and determine attack» ^[6] на SNOW 1.0, в котором используются в основном два свойства, чтобы снизить сложность атаки ниже исчерпывающего поиска ключей. Во-первых, тот факт, что автомат имеет только один вход s(1). Это позволяет злоумышленнику инвертировать операции в конечном автомате и получать больше неизвестных только из нескольких предположений. Второе свойство — неудачный выбор полинома обратной связи в SNOW 1.0.
В августе 2003 года Ватанабе, Бирюков и Канньер описали атаку ^[7] на SNOW 2.0 методом линейной маскировки. Эта атака использует $2^{230}$ битов потока и $2^{215}$ анализа, что быстрее, чем исчерпывающий поиск 256-битного ключа.
В 2010 году был описан ^[8] механизм ресинхронизации SNOW 3G и аналогичного шифра SNOW 3G ⊕ с использованием атак с коллизией нескольких наборов. В алгоритме описано полное восстановление ключа выбранных атак ресинхронизации IV для 18 из 33 раундов инициализации SNOW3G ⊕ со сложностью $2^{57}$ для генерации данных и $2^{53}$ этапами анализа.
В 2020 Lin Jiao, Yongqiang Li и Yonglin Hao совершили атаку ^[9] на SNOW-V под названием «Guess and determine attack». Хмм.. Такое же название атаки, как и на SNOW 1.0. Мы, кажется, зациклились. Или нет?

Теперь о применении

SNOW 2.0 — один из потоковых шифров, вошедших в стандарт шифрования ISO/IEC 18033-4 ^[10], который определяет функции вывода для объединения ключевого потока с открытым текстом, генераторы ключевого потока для создания ключевого потока и идентификаторы объектов.
SNOW 3Gвыбран в качестве генератора потоковых ключей для алгоритмов шифрования 3GPP UEA2 и UIA3 ^[11].
SNOW-V пока не используется, но всё возможно!

Еще есть шифр потоковый STRUMOK ^[12] (стандартизирован в Украине: ДСТУ 8845:2019 "Струмок" ^[13]), у которого генератор ключевого потока в своей концептуальной схеме подобен SNOW 2.0.

(Разница в длине секретного ключа и вектора инициализации. Так же SNOW 2.0 ориентирован на на использование в 32-разрядных вычислительных систем, а STRUMOK в 64-разрядных).

Небольшой итог

Данный шифр, конечно, не идеальный.. А кто идеален? Но он современный и, я думаю, у него есть будущее. Проблема безопасной передачи данных как была актуальной, так и является до сих пор!

Автор: silent_rebel

Источник ^[14]

Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/news/359668

Ссылки в тексте:

[1] SNOW 1.0,: https://www.semanticscholar.org/paper/SNOW-A-new-stream-cipher-Ekdahl-Johansson/900e081fa7ba0d0b45e36185e327e1081bf55d28?p2df

[2] SNOW 2.0: https://link.springer.com/chapter/10.1007/3-540-36492-7_5

[3] ETSI SAGE: https://www.etsi.org/technologies/security-algorithms

[4] SNOW 3G: https://link.springer.com/chapter/10.1007/978-3-319-01854-6_51

[5] SNOW-V: https://tosc.iacr.org/index.php/ToSC/article/view/8356

[6] «Guess and determine attack»: https://link.springer.com/chapter/10.1007/3-540-36492-7_4

[7] атаку: https://link.springer.com/chapter/10.1007/978-3-540-24654-1_16

[8] описан: https://link.springer.com/chapter/10.103GPP%20UEA2%20%D0%B8%20UIA207/978-3-642-13708-2_9

[9] атаку: https://watermark.silverchair.com/bxaa003.pdf?token=AQECAHi208BE49Ooan9kkhW_Ercy7Dm3ZL_9Cf3qfKAc485ysgAAAuowggLmBgkqhkiG9w0BBwagggLXMIIC0wIBADCCAswGCSqGSIb3DQEHATAeBglghkgBZQMEAS4wEQQMl0b_yQmm38IhrYSiAgEQgIICnQaYLTHJGtS55UgMFr-SfqUb87sR14QHefIwGSwgUatIJYGTvwvPIcSDp-2lkKZIjRg4O-TGue78gSOohf9ulx8UVPirYVAuuv7V7b8THoZWp7vmHYkChPn1cXXls89Yui6CIPv_0CvE4P_wOUoHWNJ-a7KVRiMcwhaXGE3ffg1F0o4hxDLne6sXNHp53kQ1QvGYwC_LOzBMhqYBGhU5lH31NzwlZ_gYR0REjD_n1X-3obXPCMLgPE3dAhuFdiWDjmF9Wo1Sz7LETvHp_bRVteJxyPFGLEQPyxknDIrNvP_gvlc2E-WuCYc_i4dJq2J3fD0tQmdyDGlAYDNPacplyYaxklcU5rhMVSqJpuZzhZL0DbsJ0mDRmuDQk8soTU6DyhxOpsTBB21K5DOSO6RGgBaW8FkcQNTWn161MEn-Z6-550PdLH5n9WS42hnP1gWz2aQEWgneusLM3qQe1AazJUobU3fNRHvnAbD6vzlla9smQ88sGbSv3eH3ceiz4j68Orv8qjkN5M0TDq9tFEkMu78EXXWKHxg_1mrbsahbCVRBLkEHRwcLET_4-LLUfpKBQZrKGqR3_nFceb3hieTUVYhev-Sh6kef_6ZYynf87v7TgxzPrUbXZlh4POJgNjit3_d7gUZxEEzrON-yU8zzRMREzlyOLp7zJks7Dv2uGB_TdtPJ8Zmf749lR1jUIBXNikAkWPiUfI6kFispMaXvzKugTRqyKDtI8ILJlEAyPfTFGhrCWJxms5nGj6xShn25wShj75sp8Arigbn7E9Umi8gURVVPpZE3jJFSDRoPptoo6I3pT9GvowWlH3Ml0UPE13y2S5900lbyguowsENQ7TzWxaChVTHsK3P3U6C6VPb3Gia9AKWsfHNyBLjSAA

[10] ISO/IEC 18033-4: https://www.iso.org/standard/54532.html

[11] 3GPP UEA2 и UIA3: https://www.gsma.com/aboutus/wp-content/uploads/2014/12/uea2uia2d1v21.pdf

[12] STRUMOK: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7905335&tag=1

[13] ДСТУ 8845:2019 "Струмок": https://budstandart.com/normativ-document.html?id_doc=82494

[14] Источник: https://habr.com/ru/post/532476/?utm_source=habrahabr&utm_medium=rss&utm_campaign=532476

Нажмите здесь для печати.