SNOW 3G¶

SNOW 3G — это поточный шифр, разработанный в рамках европейского проекта NESSIE (New European Schemes for Signatures, Integrity, and Encryption) и впоследствии стандартизированный для использования в сетях мобильной связи 3GPP (3rd Generation Partnership Project). Он предназначен для обеспечения конфиденциальности и целостности данных, передаваемых по радиоканалу между абонентским оборудованием и базовой станцией в сетях UMTS (Universal Mobile Telecommunications System), а также в некоторых других протоколах, таких как LTE (Long-Term Evolution) и 5G NR (New Radio). Шифр SNOW 3G является наследником шифра SNOW 2.0 и представляет собой пример криптосистемы, ориентированной на высокую скорость работы при ограниченных вычислительных ресурсах.

¶История и предпосылки создания

Разработка SNOW 3G была обусловлена необходимостью замены устаревших и уязвимых криптографических алгоритмов в сетях сотовой связи. Предшественник SNOW 3G — шифр A5/1, использовавшийся в стандарте GSM (Global System for Mobile Communications), — имел доказанные уязвимости, позволявшие взламывать его за несколько минут. В связи с этим для сетей UMTS (3G) был разработан новый набор криптографических функций, включающий шифр KASUMI (также известный как A5/3). Однако в 2000-х годах были найдены атаки на KASUMI, что подтолкнуло поиск альтернатив.

В 2006 году 3GPP принял решение о включении в спецификации для UMTS дополнительного набора алгоритмов, известного как UEA2 (UMTS Encryption Algorithm 2) и UIA2 (UMTS Integrity Algorithm 2). В качестве основы для этих алгоритмов был выбран поточный шифр SNOW 2.0, который, в свою очередь, был финалистом проекта NESSIE (2000–2003). Для соответствия требованиям 3GPP (в частности, для обеспечения высокой стойкости и эффективности при аппаратной реализации) SNOW 2.0 был модифицирован, и полученная версия получила название SNOW 3G. Официально алгоритм был опубликован в 2007 году.

¶Устройство и принцип работы

SNOW 3G является поточным шифром, что означает, что он генерирует псевдослучайную последовательность ключевого потока (keystream), которая затем побитово складывается (XOR) с открытым текстом для получения шифротекста. Расшифрование происходит аналогично — путём сложения шифротекста с той же последовательностью ключевого потока.

¶Внутренняя структура

Шифр состоит из двух основных компонентов:

1. Линейный регистр сдвига с обратной связью (LFSR — Linear Feedback Shift Register). В SNOW 3G используется 16-разрядный LFSR, каждый элемент которого представляет собой 32-битное слово. Обратная связь в регистре задана примитивным многочленом над полем GF(2³²), что обеспечивает максимальный период генерируемой последовательности. Состояние LFSR обновляется на каждом такте работы шифра.

1. Конечный автомат (FSM — Finite State Machine). FSM представляет собой нелинейный блок, который принимает на вход три слова из LFSR (R1, R2 и R3) и вычисляет выходное слово ключевого потока. FSM состоит из двух регистров (R1 и R2) и трёх нелинейных функций: S-блоков (замена байтов по таблице), операции умножения в поле Галуа и операции сложения по модулю 2³². Взаимодействие LFSR и FSM обеспечивает высокую криптографическую стойкость.

¶Процесс генерации ключевого потока

Процесс включает три этапа:

1. Инициализация. На основе секретного ключа (128 бит) и вектора инициализации (128 бит) заполняется начальное состояние LFSR и регистров FSM. Затем выполняется определённое количество тактов (обычно 32) без выдачи ключевого потока, чтобы перемешать начальное состояние.
2. Генерация. На каждом такте LFSR сдвигается, FSM обновляется, и на выходе формируется 32-битное слово ключевого потока. Этот процесс продолжается, пока не будет сгенерировано необходимое количество бит для шифрования или проверки целостности.
3. Завершение. После завершения передачи данных генерация прекращается.

¶Применение в стандартах мобильной связи

SNOW 3G используется в двух основных функциях безопасности, определённых 3GPP:

¶UEA2 (UMTS Encryption Algorithm 2)

Это алгоритм шифрования, основанный на SNOW 3G. Он обеспечивает конфиденциальность пользовательских данных и сигнального трафика в сетях UMTS (3G). UEA2 является альтернативой алгоритму KASUMI (UEA1). В сетях LTE (4G) и 5G NR (5G) для шифрования также используется SNOW 3G, но в рамках алгоритмов EEA2 (EPS Encryption Algorithm 2) и NEA2 (NR Encryption Algorithm 2) соответственно.

¶UIA2 (UMTS Integrity Algorithm 2)

Это алгоритм проверки целостности и аутентичности сообщений, также построенный на основе SNOW 3G. Он используется для вычисления кода аутентичности сообщения (MAC — Message Authentication Code), который позволяет получателю убедиться, что данные не были изменены в процессе передачи и что они отправлены легитимным отправителем. UIA2 применяется в UMTS, а его аналоги — EIA2 (EPS Integrity Algorithm 2) и NIA2 (NR Integrity Algorithm 2) — в LTE и 5G.

¶Криптостойкость и атаки

SNOW 3G считается криптографически стойким алгоритмом. На момент внедрения он не имел известных практических атак, позволяющих взломать шифр быстрее, чем полным перебором ключа (2¹²⁸ операций). Однако, как и любой алгоритм, он подвергался криптоанализу.

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

• Атака на основе связанных ключей (2008). Исследователи показали, что при использовании определённых пар ключей и векторов инициализации можно восстановить состояние шифра с меньшей сложностью, чем полный перебор. Однако эта атака не представляла практической угрозы, так как требует специфических условий, не реализуемых в стандартных протоколах.
• Атака на основе линейного криптоанализа (2010). Была предложена теоретическая атака, снижающая сложность взлома до 2¹¹⁹ операций, что всё ещё значительно выше практических возможностей.
• Атака на основе квантовых вычислений (теоретическая). В контексте квантовых компьютеров алгоритм SNOW 3G, как и любой симметричный шифр, может быть взломан с помощью алгоритма Гровера, который сокращает сложность полного перебора до 2⁶⁴ операций. Это делает SNOW 3G потенциально уязвимым для квантовых атак, но на данный момент (2024 год) квантовые компьютеры такой мощности не существуют.

¶Сравнение с другими алгоритмами

В сетях 5G, помимо SNOW 3G, используются и другие алгоритмы: AES (Advanced Encryption Standard) в режиме CTR (Counter) и ZUC (ZUC — поточный шифр, разработанный в Китае). SNOW 3G остаётся обязательным к реализации для обеспечения совместимости с более старыми устройствами, но в новых развёртываниях предпочтение часто отдаётся AES, который считается более изученным и прошедшим более широкий криптоанализ.

¶Реализация и производительность

SNOW 3G разработан для эффективной реализации как в программном, так и в аппаратном обеспечении. В аппаратной реализации (например, в специализированных интегральных схемах — ASIC или программируемых логических интегральных схемах — FPGA) он требует относительно небольшого количества логических элементов (около 10–15 тысяч вентилей) и обеспечивает высокую пропускную способность (до нескольких гигабит в секунду). В программной реализации (например, на процессорах общего назначения) скорость работы также высока, но может уступать более простым алгоритмам, таким как AES-NI (инструкции для аппаратного ускорения AES в современных процессорах).

¶Критика и ограничения

Основные критические замечания в адрес SNOW 3G связаны с его возрастом и ограниченной криптоаналитической базой по сравнению с AES. Хотя алгоритм не был взломан, его конструкция (поточный шифр) менее гибка, чем блочные шифры, в плане режимов работы. Кроме того, в 2010-х годах были выявлены потенциальные уязвимости в реализации SNOW 3G в некоторых коммерческих продуктах, связанные с неправильным использованием векторов инициализации, что могло приводить к утечке ключевого потока. Однако эти проблемы были устранены в обновлениях протоколов.

¶Интересные факты

• Название «SNOW» происходит от фамилий создателей шифра: Томаса Йоханссона (Thomas Johansson) и Патрика Стенстрёма (Patrik Stensson), а также от слова «stream cipher» (поточный шифр). Цифра «3G» указывает на принадлежность к стандарту третьего поколения мобильной связи.
• SNOW 3G является одним из немногих поточных шифров, которые были стандартизированы для использования в критически важных телекоммуникационных системах.
• Алгоритм SNOW 3G был включён в спецификации 3GPP в качестве обязательного для всех устройств, поддерживающих UMTS, и до сих пор используется в миллиардах мобильных телефонов по всему миру.

¶Источники

1. Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2. Document 1: UEA2 and UIA2 Specification. 3GPP TS 35.215.
2. Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2. Document 2: UEA2 and UIA2 Design and Evaluation Report. 3GPP TS 35.216.
3. Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2. Document 3: Implementor's Test Data. 3GPP TS 35.217.
4. Johansson, T., Stensson, P. (2003). "SNOW 2.0: A Fast Stream Cipher". NESSIE Report.
5. Babbage, S., Dodd, M. (2008). "The SNOW 3G Stream Cipher". In: Robshaw, M., Billet, O. (eds) New Stream Cipher Designs. Lecture Notes in Computer Science, vol 4986. Springer, Berlin, Heidelberg.
6. ETSI/SAGE. "Report on the design and evaluation of the 3GPP confidentiality and integrity algorithms UEA2/UIA2". 2006.