Галуа/Режим счетчика

В криптографии . режим Галуа/счетчика ( GCM ) — это режим работы криптографических с симметричным ключом , блочных шифров который широко применяется благодаря своей производительности. Пропускная способность GCM для современных высокоскоростных каналов связи может быть достигнута с использованием недорогих аппаратных ресурсов.

Алгоритм GCM обеспечивает как аутентичность (целостность), так и конфиденциальность данных и относится к классу методов аутентифицированного шифрования со связанными данными (AEAD) . Это означает, что в качестве входных данных он принимает ключ K, некоторый открытый текст P и некоторые связанные с ним данные AD; затем он шифрует открытый текст с использованием ключа для создания зашифрованного текста C и вычисляет тег аутентификации T на основе зашифрованного текста и связанных с ним данных (которые остаются незашифрованными). Получатель, знающий K, после получения AD, C и T может расшифровать зашифрованный текст, чтобы восстановить открытый текст P, и может проверить тег T, чтобы убедиться, что ни зашифрованный текст, ни связанные с ним данные не были подделаны.

GCM использует блочный шифр с размером блока 128 бит (обычно AES-128 ), работающий в режиме счетчика для шифрования, и использует арифметику в поле Галуа GF(2 ¹²⁸ ) для вычисления тега аутентификации; отсюда и название.

Код аутентификации сообщения Галуа ( GMAC ) — это вариант GCM, предназначенный только для аутентификации, который может формировать инкрементный код аутентификации сообщения . И GCM, и GMAC могут принимать векторы инициализации произвольной длины.

Различные режимы работы блочного шифра могут иметь существенно разные характеристики производительности и эффективности, даже если они используются с одним и тем же блочным шифром. GCM может в полной мере воспользоваться преимуществами параллельной обработки , а реализация GCM может эффективно использовать конвейер инструкций или аппаратный конвейер. Напротив, цепочки блоков шифра режим работы (CBC) вызывает остановки конвейера , которые снижают его эффективность и производительность.

Основная операция

Как и в обычном режиме счетчика , блоки нумеруются последовательно, а затем этот номер блока объединяется с вектором инициализации (IV) и шифруется блочным шифром E , обычно AES . Результат этого шифрования затем подвергается операции XOR с открытым текстом для получения зашифрованного текста . Как и все режимы счетчика, это по существу потоковый шифр , поэтому важно, чтобы для каждого зашифрованного потока использовался другой IV.

Блоки зашифрованного текста считаются коэффициентами многочлена , который затем оценивается в зависящей от ключа точке H с использованием арифметики конечных полей . Затем результат шифруется, создавая тег аутентификации , который можно использовать для проверки целостности данных. Зашифрованный текст затем содержит IV, зашифрованный текст и тег аутентификации.

Работа ГКМ. Для простоты показан случай только с одним блоком дополнительных аутентифицированных данных (с меткой «Данные аутентификации 1») и двумя блоками открытого текста.
Шифрование: серия 128-битных счетчиков шифруется с использованием блочного шифра E с ключом K; это может происходить параллельно. Результаты объединяются с помощью побитового XOR с 128-битными блоками открытого текста, создавая серию блоков зашифрованного текста.
Аутентификация: дополнительные данные и эти блоки зашифрованного текста объединяются с помощью умножения с зависящей от ключа константой H в поле Галуа GF(2 ¹²⁸ ) для создания тега аутентификации.

Математическая основа

GCM сочетает в себе хорошо известный режим шифрования с новым режимом аутентификации Галуа. Ключевой особенностью является простота параллельного вычисления умножения поля Галуа , используемого для аутентификации. Эта функция обеспечивает более высокую пропускную способность, чем алгоритмы шифрования, такие как CBC , которые используют режимы цепочки. ГФ(2 ¹²⁸ ) используемое поле определяется полиномом

$x^{128}+x^{7}+x^{2}+x+1$

Тег аутентификации создается путем подачи блоков данных в функцию GHASH и шифрования результата. Эта функция GHASH определяется

$\operatorname {GHASH} (H,A,C)=X_{m+n+1}$

где H = E _k (0 ¹²⁸ ) — хэш-ключ , строка из 128 нулевых бит, зашифрованная с использованием блочного шифра , A — данные, которые только аутентифицированы (не зашифрованы), C — зашифрованный текст , m — количество 128-битных блоков в A (округлено вверх) , n — количество 128-битных блоков в C (округлено вверх), а переменная X _i для i = 0,..., m + n + 1 определена ниже.

Во-первых, аутентифицированный текст и зашифрованный текст по отдельности дополняются нулями до кратных 128 бит и объединяются в одно сообщение S _i :

$S_{i}={\begin{cases}A_{i}&{\text{for }}i=1,\ldots ,m-1\\A_{m}^{*}\parallel 0^{128-v}&{\text{for }}i=m\\C_{i-m}&{\text{for }}i=m+1,\ldots ,m+n-1\\C_{n}^{*}\parallel 0^{128-u}&{\text{for }}i=m+n\\\operatorname {len} (A)\parallel \operatorname {len} (C)&{\text{for }}i=m+n+1\end{cases}}$

где len( A ) и len( C ) — 64-битные представления битовых длин A и C соответственно, v = len( A ) mod 128 — битовая длина последнего блока A , u = len( C ) mod 128 — это длина последнего блока C в битах , и $\parallel$ обозначает объединение битовых строк.

Тогда X _i определяется как:

$X_{i}=\sum _{j=1}^{i}S_{j}\cdot H^{i-j+1}={\begin{cases}0&{\text{for }}i=0\\\left(X_{i-1}\oplus S_{i}\right)\cdot H&{\text{for }}i=1,\ldots ,m+n+1\end{cases}}$

Вторая форма представляет собой эффективный итерационный алгоритм (каждый X _i зависит от X _{i −1} ), созданный путем применения метода Хорнера к первой. только последнее X _{m + n +1} Выходом остается .

Если необходимо распараллелить вычисление хэша, это можно сделать путем чередования k раз:

${\begin{aligned}X_{i}^{'}&={\begin{cases}0&{\text{for }}i\leq 0\\\left(X_{i-k}^{'}\oplus S_{i}\right)\cdot H^{k}&{\text{for }}i=1,\ldots ,m+n+1-k\\\end{cases}}\\[6pt]X_{i}&=\sum _{j=1}^{k}\left(X_{i+j-2k}^{'}\oplus S_{i+j-k}\right)\cdot H^{k-j+1}\end{aligned}}$

Если длина IV не равна 96, функция GHASH используется для расчета счетчика 0 :

$\mathrm {Counter0} ={\begin{cases}IV\parallel 0^{31}\parallel 1&{\text{for }}\operatorname {len} (IV)=96\\\operatorname {GHASH} \left(IV\parallel 0^{s}\parallel 0^{64}\parallel \operatorname {len} _{64}(IV)\right){\text{ with }}s=128-\operatorname {len} (IV)\mod 128&{\text{otherwise}}\end{cases}}$

GCM был разработан Джоном Виегой и Дэвидом А. МакГрю как улучшение режима счетчика Картера – Вегмана (режим CWC).

В ноябре 2007 года NIST объявил о выпуске специальной публикации NIST 800-38D «Рекомендации по режимам работы блочного шифрования: режим Галуа/счетчика (GCM) и GMAC, сделавшие GCM и GMAC официальными стандартами.

Использовать

Режим GCM используется в протоколе безопасности Ethernet IEEE 802.1AE (MACsec), WPA3-Enterprise протоколе безопасности Wi-Fi, IEEE 802.11ad (также называемом WiGig ANSI ( INCITS ) Fibre Channel , протоколах безопасности IEEE P1619.1 ) (FC-SP), ленте . хранилище, стандарты IETF IPsec , СШ , ТЛС 1.2 и ТЛС 1.3. AES-GCM включен в криптографический пакет NSA Suite B и его последнюю замену в пакете коммерческих алгоритмов национальной безопасности (CNSA) 2018 года . Режим GCM используется на сервере и клиенте SoftEther VPN , а также OpenVPN начиная с версии 2.4.

Производительность

GCM требует одной операции блочного шифрования и одного 128-битного умножения в поле Галуа на каждый блок (128 бит) зашифрованных и аутентифицированных данных. Операции блочного шифрования легко конвейеризируются или распараллеливаются; операции умножения легко конвейеризируются и могут быть распараллелены с некоторыми скромными усилиями (либо путем распараллеливания фактической операции, либо путем адаптации метода Хорнера к исходному представлению NIST, либо и тем, и другим).

Intel добавила инструкцию PCLMULQDQ , подчеркнув ее использование для GCM. В 2011 году SPARC добавил инструкции XMULX и XMULXHI, которые также выполняют умножение без переноса размером 64 × 64 бита . В 2015 году SPARC добавил инструкцию XMPMUL, которая выполняет умножение XOR гораздо больших значений, вплоть до входных значений размером 2048 × 2048 бит, что дает 4096-битный результат. Эти инструкции обеспечивают быстрое умножение по GF(2 ^н ) и может использоваться с любым представлением поля.

Впечатляющие результаты производительности опубликованы для GCM на ряде платформ. Кеспер и Швабе описали «более быстрый и устойчивый к временным атакам AES-GCM». который обеспечивает 10,68 циклов на байт шифрования с проверкой подлинности AES-GCM на 64-битных процессорах Intel. Дай и др. сообщают о 3,5 циклах на байт для того же алгоритма при использовании инструкций Intel AES-NI и PCLMULQDQ. Шей Герон и Влад Краснов достигли 2,47 тактов на байт на процессорах Intel 3-го поколения. Подготовлены соответствующие патчи для библиотек OpenSSL и NSS .

Когда для сообщения необходимо выполнить как аутентификацию, так и шифрование, программная реализация может добиться увеличения скорости за счет перекрытия выполнения этих операций. Производительность повышается за счет использования параллелизма на уровне команд путем чередования операций. Этот процесс называется функциональной сшивкой. и хотя в принципе его можно применять к любой комбинации криптографических алгоритмов, GCM особенно подходит. Мэнли и Грегг покажите простоту оптимизации при использовании сшивания функций с помощью GCM. Они представляют генератор программ, который использует аннотированную версию криптографического алгоритма C и генерирует код, который хорошо работает на целевом процессоре.

GCM подвергался критике в мире встроенных систем (например, со стороны Silicon Labs), поскольку параллельная обработка не подходит для эффективного использования криптографических аппаратных механизмов. В результате GCM снижает производительность шифрования для некоторых наиболее чувствительных к производительности устройств. Специализированные аппаратные ускорители для ChaCha20-Poly1305 менее сложны по сравнению с ускорителями AES.

Патенты

По утверждению авторов, GCM не обременен патентами.

Безопасность

GCM доказал свою безопасность в конкретной модели безопасности . Он безопасен, когда используется с блочным шифром, неотличимым от случайной перестановки; однако безопасность зависит от выбора уникального вектора инициализации для каждого шифрования, выполняемого с одним и тем же ключом ( см. атаку потокового шифрования ). Для любого данного ключа GCM ограничен шифрованием 2 ³⁹ − 256 бит обычного текста (64 ГиБ). Специальная публикация NIST 800-38D включает рекомендации по выбору вектора инициализации.

Уровень аутентификации зависит от длины тега аутентификации, как и в случае со всеми кодами аутентификации симметричных сообщений. Использование более коротких тегов аутентификации с GCM не рекомендуется. Разрядность тега, обозначаемая t , является параметром безопасности. В общем, t может быть любым из следующих пяти значений: 128, 120, 112, 104 или 96. Для некоторых приложений t может быть 64 или 32, но использование этих двух длин тегов ограничивает длину входных данных. данные и срок действия ключа. Приложение C в NIST SP 800-38D содержит рекомендации по этим ограничениям (например, если t = 32 и максимальный размер пакета равен 2 ¹⁰ байт, функция дешифрования аутентификации должна вызываться не более чем на 2 ¹¹ раз; если t = 64 и максимальный размер пакета равен 2 ¹⁵ байт, функция дешифрования аутентификации должна вызываться не более чем на 2 ³² раз).

Как и в случае с любым кодом аутентификации сообщения, если злоумышленник выбирает t -битный тег случайным образом, ожидается, что он будет правильным для данных данных с мерой вероятности 2. ^{− т} . Однако с помощью GCM злоумышленник может увеличить вероятность успеха, выбрав теги с n словами (общая длина зашифрованного текста плюс любые дополнительные аутентифицированные данные (AAD)) – с мерой вероятности 2. ^{− т} раз в n . Однако следует иметь в виду, что над этими оптимальными тегами по-прежнему доминирует мера выживания алгоритма 1 − n ⋅2. ^{− т} для сколь угодно большого t . Более того, GCM не подходит ни для использования с очень короткими тегами, ни с очень длинными сообщениями.

Фергюсон и Сааринен независимо друг от друга описали, как злоумышленник может выполнить оптимальные атаки на аутентификацию GCM, которая соответствует нижнему пределу безопасности. Фергюсон показал, что если n обозначает общее количество блоков в кодировке (входные данные для функции GHASH), то существует метод построения целевой подделки зашифрованного текста, который, как ожидается, будет успешным с вероятностью примерно n ⋅2. ^{− т} . Если длина тега t ​​короче 128, то каждая успешная подделка в этой атаке увеличивает вероятность успеха последующих целевых подделок и приводит к утечке информации о хеш-подключе H . В конце концов, H может быть полностью скомпрометирован, и гарантия аутентификации будет полностью потеряна.

Независимо от этой атаки злоумышленник может попытаться систематически угадывать множество различных тегов для заданных входных данных для аутентифицированного дешифрования и тем самым увеличить вероятность того, что один (или несколько) из них в конечном итоге будут считаться действительными. По этой причине система или протокол, реализующие GCM, должны отслеживать и, при необходимости, ограничивать количество неудачных попыток проверки для каждого ключа.

Сааринен описал слабые ключи GCM . Эта работа дает ценную информацию о том, как работает аутентификация на основе полиномиального хэша. Точнее, эта работа описывает конкретный способ подделки сообщения GCM при наличии действительного сообщения GCM, который работает с вероятностью около n ⋅2. ⁻¹²⁸ для сообщений длиной n × 128 бит. Однако эта работа не демонстрирует более эффективной атаки, чем было известно ранее; вероятность успеха в наблюдении 1 этой статьи соответствует вероятности успеха в лемме 2 из анализа INDOCRYPT 2004 (установка w = 128 и l = n × 128 ). Сааринен также описал вариант GCM Режим счетчика Софи Жермен (SGCM), основанный на простых числах Софи Жермен .

См. также

• Аутентифицированное шифрование
• Режим работы блочного шифрования
• AES-GCM-SIV

Внешние ссылки

• Специальная публикация NIST SP800-38D, определяющая GCM и GMAC
• RFC 4106 : Использование режима Галуа/счетчика (GCM) в инкапсуляции полезных данных безопасности IPsec (ESP)
• RFC 4543 : Использование кода аутентификации сообщения Галуа (GMAC) в IPsec ESP и AH.
• RFC 5288 : Наборы шифров AES Galois Counter Mode (GCM) для TLS
• RFC 6367 : добавление наборов шифров Camellia к безопасности транспортного уровня (TLS)
• IEEE 802.1AE – безопасность управления доступом к среде передачи (MAC)
• Рабочая группа IEEE Security in Storage разработала стандарт P1619.1.
• Технический комитет INCITS T11 работает над Fibre Channel – протоколы безопасности . проектом
• Шифрование с проверкой подлинности AES-GCM и AES-CCM в безопасном RTP (SRTP)

• Режим работы Галуа/Счетчика (GCM)