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

Режим аутентифицированного шифрования для блочных шифров

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

Алгоритм 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, шифротекст и тег аутентификации.

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

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

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

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

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

${\displaystyle \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 определена ниже. ^[3]

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

${\displaystyle 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 и обозначает конкатенацию строк битов. ${\displaystyle \parallel }$

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

${\displaystyle 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 раз:

${\displaystyle {\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, для вычисления Счетчика 0 используется функция GHASH :

${\displaystyle \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). ^[4]

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

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

Режим GCM используется в стандарте безопасности Ethernet IEEE 802.1AE (MACsec), протоколе безопасности Wi-Fi WPA3-Enterprise , IEEE 802.11ad (также называемом WiGig ), протоколах безопасности Fibre Channel ANSI ( INCITS ) (FC-SP), ленточном хранилище IEEE P1619 .1, стандартах IETF IPsec , ^{[6] [7]} SSH , ^[8] TLS 1.2 ^{[9] [10]} и TLS 1.3. ^[11] AES-GCM включен в криптографию NSA Suite B и его последнюю замену в наборе Commercial National Security Algorithm (CNSA) 2018 года . ^[12] Режим GCM используется в сервере и клиенте SoftEther VPN , ^[13] а также в OpenVPN с версии 2.4.

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

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

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

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

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

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

Патенты

По заявлению авторов, GCM не обременен патентами. ^[21]

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

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

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

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

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

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

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

Смотрите также

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

Ссылки

1. RFC 256 AES Galois Counter Mode (GCM) Наборы шифров для TLS
2. Lemsitzer, S.; Wolkerstorfer, J.; Felber, N.; Braendli, M. (2007). Paillier, P.; Verbauwhede, I. (ред.). Криптографическое оборудование и встраиваемые системы - CHES 2007. Архитектура GCM-AES, оптимизированная для FPGA . Lecture Notes in Computer Science. Vol. 4727. Springer. pp. 227–238. doi :10.1007/978-3-540-74735-2_16. ISBN 978-3-540-74734-5.
3. МакГрю, Дэвид А.; Виега, Джон (2005). «Режим работы Галуа/Счетчика (GCM)» (PDF) . стр. 5 . Получено 20 июля 2013 г. . Обратите внимание, что в формулах статьи есть опечатка.
4. Kohno, Tadayoshi; Viega, John; Whiting, Doug (2004). "CWC: Высокопроизводительный режим обычного аутентифицированного шифрования". В Roy, Bimal; Meier, Willi (ред.). Быстрое программное шифрование . Конспект лекций по информатике. Том 3017. Берлин, Гейдельберг: Springer. стр. 408–426. doi :10.1007/978-3-540-25937-4_26. ISBN 978-3-540-25937-4.
5. Dworkin, Morris (2007–2011). Рекомендации по режимам работы блочного шифра: режим Галуа/счетчика (GCM) и GMAC (PDF) (технический отчет). NIST. 800-38D . Получено 18 августа 2015 г.
6. RFC 4106 Использование режима Галуа/счетчика (GCM) в IPsec, инкапсулирующем полезную нагрузку безопасности (ESP)
7. RFC 4543 Использование кода аутентификации сообщений Галуа (GMAC) в IPsec ESP и AH
8. RFC 5647 Режим счетчика Галуа AES для протокола транспортного уровня Secure Shell
9. RFC 5288 AES Galois Counter Mode (GCM) Наборы шифров для TLS
10. RFC 6367 Добавление наборов шифров Camellia к протоколу безопасности транспортного уровня (TLS)
11. RFC 8446 Протокол безопасности транспортного уровня версии 1.3
12. "Регистрация алгоритма - Реестр объектов компьютерной безопасности | CSRC | CSRC". 24 мая 2016 г.
13. «Почему SoftEther VPN – Проект SoftEther VPN».
14. Gueron, Shay; Kounavis, Michael (апрель 2014 г.). "Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode (Revision 2.02)" (PDF) . Получено 01.09.2023 .
15. Käsper, E.; Schwabe, P. (2009). "Быстрее и устойчивее к временным атакам AES-GCM". В Clavier, C.; Gaj, K. (ред.). Криптографическое оборудование и встраиваемые системы - CHES 2009. Конспект лекций по информатике. Том 5747. Springer. стр. 1–17. doi :10.1007/978-3-642-04138-9_1. ISBN 978-3-642-04138-9.
16. Герон, Шей. «AES-GCM для эффективного аутентифицированного шифрования – окончание правления HMAC-SHA-1?» (PDF) . Семинар по реальной криптографии . Получено 8 февраля 2013 г. .
17. Гопал, В., Фегали, В., Гилфорд, Дж., Озтурк, Э., Вольрич, Г., Диксон, М., Локтюхин, М., Перминов, М. «Быстрые криптографические вычисления на архитектуре Intel с помощью сшивания функций» Intel Corp. (2010)
18. Мэнли, Рэймонд; Грегг, Дэвид (2010). "Генератор программ для инструкций Intel AES-NI". В Гонг, Г.; Гупта, К.С. (ред.). Прогресс в криптологии - INDOCRYPT 2010. Конспект лекций по информатике. Том 6498. Springer. стр. 311–327. doi :10.1007/978-3-642-17401-8_22. ISBN 978-3-642-17400-1.
19. "Безопасность IoT, часть 6: режим счетчика Галуа". 2016-05-06 . Получено 2023-10-17 .
20. Пфау, Йоханнес; Рейтер, Максимилиан; Харбаум, Таня; Хофманн, Клаус; Беккер, Юрген (сентябрь 2019 г.). «Аппаратный взгляд на шифры ChaCha: масштабируемые реализации Chacha8/12/20 в диапазоне от 476 фрагментов до битрейтов 175 Гбит/с»: 294–299. doi :10.1109/SOCC46988.2019.1570548289. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
21. МакГрю, Дэвид А.; Виега, Джон. «Заявление об интеллектуальной собственности режима работы Галуа/счетчика (GCM)» (PDF) . Центр ресурсов компьютерной безопасности, NIST.
22. МакГрю, Дэвид А.; Виега, Джон (2004). «Безопасность и производительность режима Галуа/счетчика (GCM) операций». Труды INDOCRYPT 2004. Конспект лекций по информатике. Том 3348. Springer. CiteSeerX 10.1.1.1.4591 . doi :10.1007/978-3-540-30556-9_27. ISBN  978-3-540-30556-9.
23. Нильс Фергюсон, Слабые стороны аутентификации в GCM, 2005-05-20
24. Маркку-Юхани О. Сааринен (2011-04-20). «Циклические атаки на GCM, GHASH и другие полиномиальные MAC и хэши». Архив Cryptology ePrint . FSE 2012.

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

• Специальная публикация 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 по безопасности в хранилищах разработала стандарт P1619.1
• Технический комитет INCITS T11 работает над проектом Fibre Channel – Security Protocols.
• Аутентичное шифрование AES-GCM и AES-CCM в безопасном RTP (SRTP)

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