NIST Special Publication 800-38D NIST Special Publication 800-38D
November, 2007 Ноября 2007
Recommendation for Block Рекомендация для блока
Cipher Modes of Operation: Cipher Режимы работы:
Galois/Counter Mode (GCM) Галуа Режим / Счетчик (GCM)
and GMAC и GMAC
Morris Dworkin Моррис Дворкин
COMPUTERSECURITY COMPUTERSECURITY
Recommendation for Block Рекомендация для блока
Cipher Modes of Operation: Cipher Режимы работы:
Galois/Counter Mode (GCM) Галуа Режим / Счетчик (GCM)
and GMAC и GMAC
Morris Dworkin Моррис Дворкин
NIST Special Publication 800-38D NIST Special Publication 800-38D
COMPUTERSECURITY COMPUTERSECURITY
Computer Security Division Отдел компьютерной безопасности
Information Technology Laboratory Лаборатория информационных технологий
National Institute of Standards and Technology Национальный институт стандартов и технологий
Gaithersburg, MD 20899-8930 Gaithersburg, MD 20899-8930
November 2007 Ноябрь 2007
US Department of Commerce Министерство торговли США
Carlos M. Gutierrez, Secretary Карлос Гутьеррес, секретарь
National Institute of Standards and Technology Национальный институт стандартов и технологий
James M. Turner, Acting Director Джеймс М. Тернер, исполняющий обязанности директора
NIST Special Publication 800-38D NIST Special Publication 800-38D
Reports on Information Security Technology Отчеты о безопасности информационных технологий
The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology Техническая лаборатория Информация (ITL) в Национальном институте стандартов и технологий
(NIST) promotes the US economy and public welfare by providing technical leadership for the Nation's (NIST) способствует американскую экономику и общественное благосостояние путем предоставления технической лидерство для страны
measurement and standards infrastructure. инфраструктура измерения и стандартов. ITL develops tests, test methods, reference data, proof of ITL разрабатывает тесты, методы испытаний, справочные данные, доказательство
concept implementations, and technical analyses to advance the development and productive use of Концепция реализации, и технический анализ для продвижения развития и продуктивного использования
information technology. информационные технологии. ITL's responsibilities include the development of technical, physical, Обязанности ITL включают разработку технической, физической,
administrative, and management standards and guidelines for the cost-effective security and privacy of административные и управленческие стандарты и руководящие принципы для рентабельной безопасности и конфиденциальности
sensitive unclassified information in Federal computer systems. чувствительны несекретные сведения в федеральных компьютерных систем. This Special Publication 800-series Это Special Publication 800-серия
reports on ITL's research, guidance, and outreach efforts in computer security, and its collaborative отчеты о научно-исследовательских, руководство, и информационно-пропагандистской деятельности ITL в области компьютерной безопасности, и его совместная
activities with industry, government, and academic organizations. деятельность с промышленностью, правительством и научными организациями.
Certain commercial entities, equipment, or materials may be identified in this document in order Некоторые коммерческие организации, оборудование или материалы могут быть идентифицированы в данном документе для того,
to describe an experimental procedure or concept adequately. описать экспериментальный порядок или понятие адекватно. Such identification is not intended Такая идентификация не предназначен
to imply recommendation or endorsement by the National Institute of Standards and Technology, подразумевает рекомендацию или одобрение со стороны Национального института стандартов и технологий,
nor is it intended to imply that the entities, materials, or equipment are necessarily the best а также не подразумевает, что лица, материалы или оборудование обязательно лучшим
available for the purpose. средства для этой цели.
National Institute of Standards and Technology Special Publication 800-38D Национальный институт стандартов и технологии Special Publication 800-38D
Natl. Natl. Inst. Ин-т. Stand. Стенд. Technol. Technol. Spec. Spec. Publ. Изд. 800-38D 37 pages (November 2007) 800-38D 37 страниц (ноябрь 2007 г.)
CODEN: NSPUE2 CODEN: NSPUE2
ii II
NIST Special Publication 800-38D NIST Special Publication 800-38D
Acknowledgements Благодарности
The author wishes to thank David McGrew, who co-invented GCM and submitted it to NIST, and also the Автор хотел бы поблагодарить Дэвида Мак-Гру, который стал одним из изобретенный GCM и представил его NIST, а также
author's colleagues who reviewed drafts of this document and contributed to its development, especially коллеги автора, которые отзывы проектов настоящего документа и вклад в его развитие, особенно
Elaine Barker, John Kelsey, Allen Roginsky, Donna Dodson, Tim Polk, and Bill Burr. Элейн Баркер, Джон Келси, Аллен Рогинский, Донна Додсон, Тим Полк, и Билл Берр. The author also Автор также
gratefully acknowledges the many comments from the public and private sectors to improve the quality с благодарностью отмечает много комментариев от государственного и частного секторов по улучшению качества
and usefulness of this publication. и полезность данной публикации.
iii III
NIST Special Publication 800-38D NIST Special Publication 800-38D
Abstract Аннотация
This Recommendation specifies the Galois/Counter Mode (GCM), an algorithm for Эта Рекомендация определяет режим Галуа / Счетчик (GCM), алгоритм
authenticated encryption with associated data, and its specialization, GMAC, for generating a подлинности шифрования с связанных данных, и его специализация, GMAC, для генерации
message authentication code (MAC) on data that is not encrypted. код аутентификации сообщения (MAC), на данных, которые не зашифрован. GCM and GMAC are modes GCM и GMAC являются режимы
of operation for an underlying approved symmetric key block cipher. работы для исходной утвержденной симметричным ключом блочного шифра.
KEY WORDS: authenticated encryption; КЛЮЧЕВЫЕ СЛОВА: аутентификацию шифрования; authentication; аутентификации; block cipher; блочный шифр; confidentiality, конфиденциальность,
cryptography; криптография; encryption; шифрование; information security; информационная безопасность; mode of operation. режим работы.
iv IV
NIST Special Publication 800-38D NIST Special Publication 800-38D
Table of Contents Содержание
EFINITIONS AND ПРЕДЕЛЕНИЯ И BBREVIATIONS BBREVIATIONS PERATIONS AND PERATIONS И PERATION ON Значение звукового ПО LGORITHM FOR THE LGORITHM ДЛЯ UTHENTICATED UTHENTICATED LGORITHM FOR THE LGORITHM ДЛЯ UTHENTICATED UTHENTICATED STABLISHMENT STABLISHMENT ONSTRUCTIONS ONSTRUCTIONS ONSTRAINTS ON THE ONSTRAINTS ПО v V
NIST Special Publication 800-38D NIST Special Publication 800-38D
vi VI
List of Figures Список иллюстраций
................................................................................. 13 .................................................. ............................... 13 ..................................................... 14 .................................................. 14 ... List of Tables Список таблиц
NIST Special Publication 800-38D NIST Special Publication 800-38D
1 Purpose 1 Цель
This publication is the fourth Part in a series of Recommendations regarding modes of operation Эта публикация является четвертым участие в серии Рекомендаций о режимах работы
of symmetric key block ciphers. симметричных ключевых блочных шифров.
2 Authority 2 Орган
This document has been developed by the National Institute of Standards and Technology Этот документ был разработан Национальным институтом стандартов и технологии
(NIST) in furtherance of its statutory responsibilities under the Federal Information Security (NIST) в реализации его уставных обязанностей в соответствии с Федеральным информационной безопасности
Management Act (FISMA) of 2002, Public Law 107-347. Закон об управлении (FISMA) 2002, Public Law 107-347.
NIST is responsible for developing standards and guidelines, including minimum requirements, NIST отвечает за разработку стандартов и руководящих принципов, включая минимальные требования,
for providing adequate information security for all agency operations and assets, but such для обеспечения надлежащей информационной безопасности для всех операций агентств и средств, но такие
standards and guidelines shall not apply to national security systems. стандарты и руководящие принципы не применяются к системам национальной безопасности. This guideline is consistent Это руководство согласуется
with the requirements of the Office of Management and Budget (OMB) Circular A-130, Section с требованиями Управления и бюджета (OMB) циркуляр-130, раздел
8b(3), Securing Agency Information Systems, as analyzed in A-130, Appendix IV: Analysis of 8b (3), Обеспечение Агентство информационных систем, как было проанализировано в A-130, Приложение IV: Анализ
Key Sections. Основные разделы. Supplemental information is provided in A-130, Appendix III. Справочная информация предоставляется в A-130, Приложение III.
This Recommendation has been prepared for use by federal agencies. Эта Рекомендация была подготовлена для использования федеральными органами. It may be used by Это может быть использовано
nongovernmental organizations on a voluntary basis and is not subject to copyright. неправительственные организации на добровольной основе и не охраняется авторским правом. (Attribution (Attribution
would be appreciated by NIST.) будет понятно NIST.)
Nothing in this document should be taken to contradict standards and guidelines made Ничто в этом документе не должны быть приняты, чтобы противоречить стандартов и руководящих принципов, сделанные
mandatory and binding on federal agencies by the Secretary of Commerce under statutory обязательный для исполнения на федеральных агентств секретарем Торгово под законом
authority. орган. Nor should these guidelines be interpreted as altering or superseding the existing Не следует эти руководящие принципы можно интерпретировать как изменение или заменяющий существующий
authorities of the Secretary of Commerce, Director of the OMB, or any other federal official. Власти министра торговли, директор Административно-бюджетное управление, или любой другой федеральный чиновник.
Conformance testing for implementations of the mode of operation that is specified in this Part Аттестационного тестирования для реализаций режима работы, указанного в настоящей части
of the Recommendation will be conducted within the framework of the Cryptographic Module Рекомендации будут проводиться в рамках криптографического модуля
Validation Program (CMVP), a joint effort of NIST and the Communications Security Проверка программы (CMVP), совместными усилиями NIST и безопасности коммуникаций
Establishment of the Government of Canada. Создание правительства Канады. An implementation of a mode of operation must Реализация режима работы должны
adhere to the requirements in this Recommendation in order to be validated under the CMVP. придерживаться требований в данной Рекомендации для того, чтобы быть подтверждено под CMVP.
The requirements of this Recommendation are indicated by the word “shall.” Требования данной Рекомендации обозначается словом «должны».
3 Introduction 3 Введение
This Recommendation specifies an algorithm called Galois/Counter Mode (GCM) for В настоящей Рекомендации определяется алгоритм, называемый Галуа / Режим Счетчик (GCM) для
authenticated encryption with associated data. подлинности шифрования с связанных данных. GCM is constructed from an approved symmetric GCM строится из одобренного симметричных
key block cipher with a block size of 128 bits, such as the Advanced Encryption Standard (AES) Ключ блочный шифр с размером блока 128 бит, таких как Advanced Encryption Standard (AES)
algorithm that is specified in Federal Information Processing Standard (FIPS) Pub. Алгоритм, который указан в Federal Information Processing Standard (FIPS) Pub. 197 [ 2]. 197 [ 2]. Thus, GCM is a mode of operation of the AES algorithm. Таким образом, GCM является режим работы алгоритма AES.
GCM provides assurance of the confidentiality of data using a variation of the Counter mode of GCM обеспечивает уверенность в конфиденциальности данных, используя вариацию режиме счетчик
operation for encryption. Работа для шифрования. GCM provides assurance of the authenticity of the confidential data GCM обеспечивает уверенность в подлинности конфиденциальных данных
(up to about 64 gigabytes per invocation) using a universal hash function that is defined over a (Примерно до 64 гигабайт в вызове), используя универсальный хэш-функцию, которая определена по
1 1
NIST Special Publication 800-38D NIST Special Publication 800-38D
binary Galois (ie, finite) field. двоичный Галуа (т.е. конечное) поле. GCM can also provide authentication assurance for additional GCM может также обеспечить уверенность аутентификации для дополнительного
data (of practically unlimited length per invocation) that is not encrypted. данные (из практически неограниченной длины в вызове), который не зашифрован.
If the GCM input is restricted to data that is not to be encrypted, the resulting specialization of Если вход GCM ограничивается данными, которые не должны быть зашифрованы, в результате специализации
GCM, called GMAC, is simply an authentication mode on the input data. GCM, называется GMAC, просто режим аутентификации от входных данных. In the rest of this В остальной части этого
document, statements about GCM also apply to GMAC. документ, заявления о ГКМ также применяются к GMAC.
GCM provides stronger authentication assurance than a (non-cryptographic) checksum or error GCM обеспечивает надежные гарантии подлинности, чем (не криптографической контрольной суммой) или ошибок
detecting code; обнаружения код; in particular, GCM can detect both 1) accidental modifications of the data and 2) в частности, GCM может обнаруживать как 1) случайные модификации данных и 2)
intentional, unauthorized modifications. преднамеренные, несанкционированных модификаций.
The two functions of GCM are called authenticated encryption and authenticated decryption. Эти две функции из GCM называются подлинности шифрование и аутентификацию расшифровки.
Each of these functions is relatively efficient and parallelizable; Каждая из этих функций является относительно эффективным и параллелизуемое; consequently, high-throughput следовательно, высокой пропускной
implementations are possible in both hardware and software. реализации возможны в аппаратного и программного обеспечения. GCM has several other useful GCM имеет несколько другая полезная
characteristics, including the following: характеристики, в том числе следующие:
• The GCM functions are “online” in the sense that the lengths of the confidential data • Функции GCM являются "онлайн" в том смысле, что длины конфиденциальных данных
and the additional, non-confidential data are not required in advance; и дополнительные, не-конфиденциальные данные не требуется заранее; instead, the Вместо этого
lengths can be calculated as the data arrives and is processed. длина может быть вычислена как данные поступают и обрабатываются.
• The GCM functions require only the forward direction of the underlying block cipher • Функции GCM требуют только прямое направление основного блочного шифра
(ie, the inverse direction is not required). (Т.е. обратная направление не требуется).
• The authenticity of the protected data can be verified independently from the recovery • Подлинность защищенных данных может быть проверена независимо от восстановления
of the confidential data from its encrypted form. конфиденциальных данных его зашифрованном виде.
• If the unique initialization string is predictable, and the length of the confidential data is • Если уникальная строка инициализации является предсказуемым, а длина конфиденциальных данных является
known, then the block cipher invocations within the GCM encryption mechanism can известны, то блочный шифр вызовы внутри механизма шифрования GCM может
be pre-computed. быть предварительно вычислены.
• If some or all of the additional, non-confidential data is fixed, then the corresponding • Если все или некоторые из дополнительного, не-конфиденциальных данных фиксируется, то соответствующий
elements of the GCM authentication mechanism can be pre-computed. Элементы механизма аутентификации ГКМ может быть предварительно вычислены.
An important caution to the use of GCM is that a breach of the requirement in Sec. Важное предостережение для использования GCM является то, что нарушения требований в гл. 8 8 for the для uniqueness of the initialization strings may compromise the security assurance almost entirely, as Уникальность строк инициализации может поставить под угрозу гарантии безопасности почти полностью, как
detailed in Ref. [5 ] and summarized in Appendix A. Therefore, this mode of operation should подробно описаны в работе. [5 ] и приведены в Приложении А. Поэтому этот режим работы должен not be deployed unless compliance with this uniqueness requirement is ensured. не будут развернуты, если соблюдение этого уникальности требование не обеспечивается. Some of the Некоторые из
practical considerations are discussed further in Secs. 9.1 and 9.2. практические соображения обсуждаются в сек. 9,1 и 9,2. The designers of GCM are McGrew and Viega. Дизайнеры GCM являются McGrew и Viega. They submitted GCM to NIST in Ref. Они утверждали, GCM к NIST в работе. [ 6], and [ 6], и they discuss in detail its security and performance in Ref. они подробно обсудить ее безопасность и производительность в работе. [ 7]. [ 7]. 4 Definitions, Abbreviations, and Symbols 4 Определения, аббревиатуры и символы
4.1 Definitions and Abbreviations 4.1 Определения и сокращения
2 2
NIST Special Publication 800-38D NIST Special Publication 800-38D
AAD AAD
Additional Authenticated Data Дополнительная проверкой подлинности данных
Additional Дополнительная
Authenticated Data Прошедшие проверку данных
The input data to the authenticated encryption function that is Входные данные аутентифицированному функции шифрования, которая
authenticated but not encrypted. аутентификацию, но не шифруются.
AES AES
Advanced Encryption Standard. Advanced Encryption Standard.
Approved Утверждено
FIPS approved or NIST recommended: an algorithm or technique that FIPS утверждены или NIST рекомендуется: алгоритм или метод, который
is either 1) specified in a FIPS or a NIST Recommendation, or 2) либо 1), указанных в ФИПС или рекомендацией NIST, или 2)
adopted in a FIPS or a NIST Recommendation. принят в ФИПС или рекомендацией NIST.
Authenticated Прошедшие проверку
Decryption Расшифровка
The function of GCM in which the ciphertext is decrypted into the Функция ГКМ, в котором зашифрованный текст расшифрованы в
plaintext, and the authenticity of the ciphertext and the AAD is открытого текста, и подлинность зашифрованного текста и AAD является
verified. проверено.
Authenticated Прошедшие проверку
Encryption Шифрование
The function of GCM in which the plaintext is encrypted into the Функция ГКМ, в котором открытого текста шифруется в
ciphertext, and an authentication tag is generated on the AAD and the зашифрованный текст, и тег аутентификации генерируется на ПВО и
ciphertext. зашифрованный текст.
Authentication Tag Аутентификация тегов
(Tag) (Tag)
A cryptographic checksum on data that is designed to reveal both Криптографическая контрольная сумма данных, которая предназначена для выявления и
accidental errors and the intentional modification of the data. случайные ошибки и преднамеренное изменение данных.
Authenticity Подлинность
The property that data originated from its purported source. Имущество, что данные собраны с его предполагаемой источника.
Bit Бит
A binary digit: 0 or 1 . Двоичная цифра: 0 или 1.
Bit String Бит Строка
A finite, ordered sequence of bits. Конечное, упорядоченная последовательность битов.
Block Блок
For a given block cipher, a bit string whose length is the block size of Для данного блочного шифра, битовая строка, длина которой является размер блока
the block cipher. блочный шифр.
Block Cipher Блочный шифр
A parameterized family of permutations on bit strings of a fixed Параметризованный семья перестановок на битовых строк из фиксированного
length; длина; the parameter that determines the permutation is a bit string параметр, который определяет перестановку немного строка
called the key. называют ключом.
Block Size Размер блока
For a given block cipher and key, the fixed length of the input (or Для данного блочного шифра и ключа, фиксированной длины входа (или
output) bit strings. выход) битовые строки.
Byte Байт
A sequence of 8 bits. Последовательность из 8 битов.
Byte String Байт Строка
A finite, ordered sequence of bytes. Конечное, упорядоченная последовательность байт.
Ciphertext Зашифрованный текст
The encrypted form of the plaintext. Зашифрованном виде открытого текста.
3 3
NIST Special Publication 800-38D NIST Special Publication 800-38D
Direct Random String Прямая Случайная Строка
In the RBG-based construction of IVs, an output string of an RBG В RBG основе строительства капельницы, выходной строки в RBG
that is used as the random field for an IV. который используется в качестве случайного поля для IV.
Exclusive-OR Исключающее ИЛИ
The bitwise addition, modulo 2, of two bit strings of equal length. Побитовое сложение по модулю 2, из двух битовых строк равной длины.
FIPS FIPS
Federal Information Processing Standard. Федеральный стандарт обработки информации.
Fixed Field Исправлена поле
In the deterministic construction of IVs, the field that identifies the В детерминированном строительства капельницы, области, которая идентифицирует
device or context for the instance of the authenticated encryption устройство или контекст для экземпляра, прошедшего проверку подлинности шифрования
function. Функция.
Forward Cipher Форвард Cipher
Function Функция
A permutation on blocks that is determined by the choice of a key for Перестановка на блоки, которые определяется выбора ключа для
a given block cipher. учитывая блочный шифр.
Free Field Свободное поле
In the RBG-based construction of IVs, the field whose contents are В RBG основе строительства капельницы, поле, содержимое которого
not restricted. не ограничивается.
Fresh Свежий
For a newly generated key, the property of being unequal to any Для вновь сгенерированный ключ, свойства быть равно любому
previously used key. раньше ключ.
GCM GCM
Galois/Counter Mode Галуа Режим / Счетчик
ICB ICB
Initial Counter Block Начальная Счетчик Блок
Initialization Vector Вектор инициализации
A nonce that is associated with an invocation of authenticated Одноразовый номер, который связан с вызовом подлинности
encryption on a particular plaintext and AAD. шифрования на определенном открытого текста и ПВО.
Inverse Cipher Function The function that is the inverse of the forward cipher function for a Обратная Cipher Функция Функция, которая является инверсией переднего шифра функции для
given key. учитывая ключ.
Invocation Field Вызов поле
In the deterministic construction of IVs, the field that identifies the В детерминированном строительства капельницы, области, которая идентифицирует
sets of inputs to the authenticated encryption function in a particular наборы входов в подлинности функции шифрования в частности
device or context. устройство или контекст.
IT IT
Information Technology Информационные технологии
IV IV
Initialization Vector Вектор инициализации
Key Ключ
The parameter of the block cipher that determines the selection of the Параметр блочного шифра, который определяет выбор
forward cipher function from the family of permutations. направить шифрования функцию из семейства перестановок.
Least Significant Bit(s) Младший значащий бит (ы)
The right-most bit(s) of a bit string. Самый правый бит (ы) битовой строки.
Mode of Operation Режим работы
(Mode) (Режим)
An algorithm for the cryptographic transformation of data that is Алгоритм криптографического преобразования данных, что является
based on a block cipher. на основе блочного шифра.
4 4
NIST Special Publication 800-38D NIST Special Publication 800-38D
Most Significant Bit(s) Наиболее значащий бит (ы)
The left-most bit(s) of a bit string. Левый бит (ы) битовой строки.
NIST NIST
National Institute of Standards and Technology. Национальный институт стандартов и технологий.
Nonce Nonce
A value that is used only once within a specified context. Значение, которое используется только один раз в течение определенного контекста.
Permutation Перестановка
An invertible function. Обратимая функция.
Plaintext Открытым текстом
The input data to the authenticated encryption function that is both Входные данные аутентифицированному функции шифрования, который является одновременно
authenticated and encrypted. проверку подлинности и шифруется.
Random Field Случайного поля
In the RBG-based construction of IVs, either a direct random string В RBG основе строительства капельницы, либо прямой случайной строки
or one of its successors. или один из его преемников.
RBG RBG
Random Bit Generator Генератор случайных бит
Successor Преемник
In the RBG-based construction of IVs, the result of one or more В RBG основе строительства капельницы, в результате одной или нескольких
applications of the appropriate incrementing function to a direct применение соответствующей функции увеличивающимся к прямой
random string. случайная последовательность.
XOR XOR
Exclusive-OR. Исключающее ИЛИ.
4.2 Symbols 4.2 Символы
4.2.1 Variables 4.2.1 Переменные
A
The additional authenticated data Дополнительное подлинности данных
C C
The ciphertext. Зашифрованный текст.
H H
The hash subkey. Хэш подраздел.
ICB ICB
The initial counter block Начальная счетчик блок
IV IV
The initialization vector. Вектор инициализации.
K K
The block cipher key. Ключ блочный шифр.
P P
The plaintext. Открытый текст.
R R
The constant within the algorithm for the block multiplication operation. Постоянной в пределах алгоритма работы блока умножения.
T Т
The authentication tag. Тег аутентификации.
t т
The bit length of the authentication tag. Немного длина тега аутентификации.
5 5
NIST Special Publication 800-38D NIST Special Publication 800-38D
4.2.2 Operations and Functions 4.2.2 Операции и функции
0 0
s с
The bit string that consists of s ' 0 ' bits. Битовая строка, которая состоит из S '0 "бит.
CIPH CIPH
K K
( X ) (Х)
The output of the forward cipher function of the block cipher under the Выход вперед шифра функции блочного шифра под
key K applied to the block X . ключ К для мозаичных X.
GCTR GCTR
K K
( ICB , X ) (ICB, X)
The output of the GCTR function for a given block cipher with key K Выход функции GCTR для данного блочного шифра с ключом K
applied to the bit string X with an initial counter block ICB . применяется к битовой строки X с начальной счетчик блока ICB.
GHASH GHASH
H H
( X ) (Х)
The output of the GHASH function under the hash subkey H applied to Выход функции GHASH под хэш-подраздел Н, приложенного к
the bit string X . битовая строка х.
inc вкл
s с
( X ) (Х)
The output of incrementing the right-most s bits of the bit string X , Выход увеличивая самый правый с биты битовой строки X,
regarded as the binary representation of an integer, by 1 modulo 2 рассматривать как двоичного представления целого числа, по 1 модулю 2
s с
. .
int( X ) Int (X)
The integer for which the bit string X is a binary representation. Целое число, для которых при этом битовая строка Х представляет собой двоичное представление.
len( X ) Лен (X)
The bit length of the bit string X . Немного длина битовой строки X.
LSB LSB
s с
( X ) (Х)
The bit string consisting of the s right-most bits of the bit string X . Битовая строка, состоящая из с самых правых битов битовой строки X.
MSB MSB
s с
( X ) (Х)
The bit string consisting of the s left-most bits of the bit string X . Битовая строка, состоящая из с левой большинство биты битовой строки X.
⎡ x ⎤ ⎡ х ⎤
The least integer that is not less than the real number x . Наименьшее целое, что является не менее реальной числа х.
[ x ] [X]
s с
The binary representation of the non-negative integer x as a string of s bits, Двоичным представлением целого неотрицательного х в виде строки из сек бит,
where x <2 где х <2
s с
. .
X >> 1 X >> 1
The bit string that results from discarding the rightmost bit of the bit string Битовая строка, которая возникает в результате отбрасывания самый правый бит в битовой строке
X and prepending a ' 0 ' bit on the left. X и предваряя "0" немного слева.
X || Y X || Y
The concatenation of two bit strings X and Y . Объединение двух битовых строк X и Y.
X ⊕ Y X ⊕ Y
The bitwise exclusive-OR of two bit strings X and Y of the same length. Побитовое исключающее ИЛИ двух битовых строк х и у той же длины.
X • Y X • Y
The product of two blocks, X and Y , regarded as elements of a certain Произведение двух блоков, X и Y, рассматривать как элементы определенный
binary Galois field. двоичное поле Галуа.
X X
i я
For a positive integer i , the i th power of X under the product '•'. Для натурального Я, I-й степени Х под продукт "• '.
x · y х • у
The product of two integers, x and y . Произведение двух целых чисел, х и у.
6 6
NIST Special Publication 800-38D NIST Special Publication 800-38D
5 Elements of GCM 5 Элементы GCM
The elements of GCM and the associated notation and requirements are introduced in the three Элементы ГКМ и ассоциированной нотации и требований вводятся в трех
sections below. разделах. The underlying block cipher and key are discussed in Sec. 5.1 . Основной блок шифрования и ключ обсуждаются в разделе. 5.1 . The data Данные elements of the authenticated encryption and authenticated decryption functions of GCM are элементы подлинности шифрования и дешифрования, прошедшие проверку подлинности функции ГКМ являются
discussed in Sec. 5.2 . обсуждается в гл. 5.2 . The cryptographic primitives for confidentiality and authentication within Криптографические примитивы для конфиденциальности и аутентификации в these two functions are discussed in Sec. эти две функции обсуждаются в разделе. 5 .3. 5 0,3. 5.1 Block Cipher 5.1 блочный шифр
The operations of GCM depend on the choice of an underlying symmetric key block cipher and Операции ГКМ зависеть от выбора подстилающей симметричным ключом блочного шифра и
thus can be considered a mode of operation (mode, for short) of the block cipher. Таким образом, можно считать режим работы (режим, для краткости) из блочного шифра. The GCM key Ключ GCM
is the block cipher key (the key, for short). является ключевым блочный шифр (ключ, для краткости).
For any given key, the underlying block cipher of the mode consists of two functions that are Для любого данного ключа, лежащий в основе блочного шифра в режиме состоит из двух функций, которые
inverses of each other. обратными друг другу. The choice of the block cipher includes the designation of one of the two Выбор блочного шифра включает в себя назначение одного из двух
functions of the block cipher as the forward cipher function, as in the specification of the AES функции блочного шифра в прямом шифра функции, как в спецификации AES
algorithm in Ref. [2] . Алгоритм в работе. [2] . GCM does not employ the inverse cipher function. GCM не использует функцию обратного шифрования. The forward cipher function is a permutation on bit strings of a fixed length; Вперед шифр функция является перестановкой на битовых строк фиксированной длины; the strings are струны
called blocks. называемые блоки. The length of a block is called the block size. Длина блока называется размер блока. The key is denoted K , and the Ключ обозначается K, и
resulting forward cipher function of the block cipher is denoted CIPH в результате вперед шифр функции блочного шифра обозначается CIPH
K K
. .
The underlying block cipher shall be approved, the block size shall be 128 bits, and the key size Лежащая в основе блочный шифр утверждается, размер блока должен быть 128 бит, и размер ключа
shall be at least 128 bits. должна быть не менее 128 бит. The key shall be generated uniformly at random, or close to uniformly Ключ должен генерироваться равномерно случайным образом, или близко к равномерно
at random, ie, so that each possible key is (nearly) equally likely to be generated. случайным образом, то есть, так что каждый ключ можно (почти) в равной степени может быть сгенерирован.
Consequently, the key will be fresh, ie, unequal to any previous key, with high probability. Следовательно, ключ будет свежим, то есть, не равно любому предыдущему ключа, с высокой вероятностью. The
key shall be secret and shall be used exclusively for GCM with the chosen block cipher. Ключ является тайным и должны использоваться исключительно для GCM с выбранным блочного шифра.
Additional requirements on the establishment and management of keys are discussed in Sec. Дополнительные требования к созданию и управлению ключами, обсуждаются в гл. 8 .1. 8 0,1. 5.2 Two GCM Functions 5.2 Два GCM Функции
The two functions that comprise GCM are called authenticated encryption and authenticated Эти две функции, которые включают GCM называются проверкой подлинности шифрование и аутентификацию
decryption. расшифровки. The authenticated encryption function encrypts the confidential data and computes Аутентифицированный функция шифрования шифрует конфиденциальные данные и вычисляет
an authentication tag on both the confidential data and any additional, non-confidential data. тег аутентификации на обоих конфиденциальных данных и любых дополнительных, не-конфиденциальных данных. The
authenticated decryption function decrypts the confidential data, contingent on the verification of аутентификацию функция расшифровки расшифровывает конфиденциальные данные, условных на проверки
the tag. тег.
An implementation may restrict the input to the non-confidential data, ie, without any Реализация может ограничить ввод неконфиденциальный данных, т.е., без всяких
confidential data. конфиденциальные данные. The resulting variant of GCM is called GMAC. Полученную вариант GCM называется GMAC. For GMAC, the authenticated Для GMAC, проверку подлинности
encryption and decryption functions become the functions for generating and verifying an шифрования и дешифрования функции становятся функции для генерации и проверки
authentication tag on the non-confidential data. тег аутентификации на неконфиденциальных данных.
The requirements and notation for the input and output data of these functions are discussed in Требования и обозначения для входных и выходных данных этих функций обсуждаются в
Secs. 5.2.1 and 5.2.2. Сек. 5.2.1 и 5.2.2. Algorithms for computing these functions are given in Sec. Алгоритмы вычисления этих функций приведены в гл. 7. 7. 7 7
NIST Special Publication 800-38D NIST Special Publication 800-38D
5.2.1 Authenticated Encryption Function 5.2.1 проверкой подлинности Шифрование Функция
5.2.1.1 Input Data 5.2.1.1 Ввод данных
Given the selection of an approved block cipher and key, there are three input strings to the Учитывая выбор утвержденного блочного шифра и ключа, есть три входные строки в
authenticated encryption function: аутентификацию функция шифрования:
• a plaintext, denoted P ; • открытый текст, обозначается P;
• additional authenticated data (AAD), denoted A ; • дополнительные проверку подлинности данных (AAD), обозначается; and и
• an initialization vector (IV), denoted IV . • вектор инициализации (IV), обозначается IV.
The plaintext and the AAD are the two categories of data that GCM protects. Открытый текст и AAD являются две категории данных, которые GCM защищает. GCM protects the GCM защищает
authenticity of the plaintext and the AAD; Подлинность текста и AAD; GCM also protects the confidentiality of the plaintext, GCM также защищает конфиденциальность открытого текста,
while the AAD is left in the clear. в то время как AAD остается в открытом виде. For example, within a network protocol, the AAD might Например, в сетевой протокол, ААР мощь
include addresses, ports, sequence numbers, protocol version numbers, and other fields that включают адреса, порты, порядковые номера, номера версий протокола и других областях, что
indicate how the plaintext should be treated. свидетельствуют о том, как открытый текст должен быть обработан.
The IV is essentially a nonce, ie, a value that is unique within the specified context, which IV является по существу одноразовый, то есть, значение, которое является уникальным в пределах определенного контекста, который
determines an invocation of the authenticated encryption function on the input data to be определяет вызов аутентифицированному функции шифрования от входных данных, чтобы быть
protected. защищены. The uniqueness requirement on the IVs (and keys) is stated precisely in Sec. 8 , and Уникальность требование на капельницы (и ключи) говорится именно в гл. 8 , и two frameworks for constructing IVs are given in Sec. две рамки для построения ИВС приведены в гл. 8. 2. Practical considerations in assuring 8. 2. Практические соображения в обеспечении the requirement are discussed in Secs. 9.1 and 9.2. требование обсуждаются в сек. 9,1 и 9,2. The critical importance of the uniqueness of Решающее значение уникальности the IVs is detailed in Ref . IVs подробно в работе . [ 5] and summarized in Appendix A. [ 5] и приведены в Приложении А. The bit lengths of the input strings to the authenticated encryption function shall meet the Битовые длины входных строк аутентифицированному функции шифрования должны соответствовать
following requirements: следующим требованиям:
• len( P ) ≤ 2 • Лен (P) ≤ 2
39 39
-256; -256;
• len( A ) ≤ 2 • Лен () ≤ 2
64 64
-1; -1;
• 1 ≤ len( IV ) ≤ 2 • 1 ≤ LEN (IV) ≤ 2
64 64
-1. -1.
Although GCM is defined on bit strings, the bit lengths of the plaintext, the AAD, and the IV Хотя GCM определяется на битовых строк, битовые длины открытого текста, САД и IV
shall all be multiples of 8, so that these values are byte strings. должны все быть кратны 8, так что эти значения байт строки.
An implementation may further restrict the bit lengths of these inputs, consistent with the above Реализация может еще больше ограничить битовых длин этих входов, в соответствии с выше
requirements; требования; for example, an implementation may establish smaller maximum values. Например, реализация может установить меньшие значения максимальной. The bit Немного
lengths that an implementation allows are called the supported bit lengths. длины, что реализация позволяет называются поддерживаемые длины битные. A single set of Один набор
supported bit lengths for each of the three inputs should be established for the entire поддерживаемые длины бит для каждого из трех входов должны быть установлены для всей
implementation, independent of the key. Реализация, зависит от ключа.
For IVs, it is recommended that implementations restrict support to the length of 96 bits, to Для капельницы, рекомендуется реализации ограничивают поддержку длины 96 бит, чтобы
promote interoperability, efficiency, and simplicity of design. обеспечения интероперабельности, эффективности и простоту конструкции.
5.2.1.2 Output Data 5.2.1.2 Выходные данные
The following two bit strings comprise the output data of the authenticated encryption function: Следующие два битовых строк содержат выходные данные авторизованного функции шифрования:
8 8
NIST Special Publication 800-38D NIST Special Publication 800-38D
• A ciphertext, denoted C , whose bit length is the same as that of the plaintext. • зашифрованный текст, обозначенный С, которого немного длина такой же, как и у открытого текста.
• An authentication tag, or tag, for short, denoted T . • тега аутентификации, или тег, для краткости, обозначать T.
The bit length of the tag, denoted t , is a security parameter, as discussed in Appendix B . In Немного длина тега, обозначенной т, является параметром безопасности, как описано в приложении B. В
general, t may be any one of the following five values: 128, 120, 112, 104, or 96. For certain Вообще, т может быть любой из следующих пяти значений: 128, 120, 112, 104 или 96. Для некоторых
applications, t may be 64 or 32; приложений, т может быть 64 или 32; guidance for the use of these two tag lengths, including руководство по использованию этих двух длин тегов, в том числе
requirements on the length of the input data and the lifetime of the key in these cases, is given in требования к длине входных данных и время жизни ключа в этих случаях, дается в
Appendix C. Приложение C.
An implementation shall not support values for t that are different from the seven choices in the Реализация не поддерживает значения т, которые отличаются от семи вариантов в
preceding paragraph. Предыдущий пункт. An implementation may restrict its support to as few as one of these Реализация может ограничить свою поддержку, как мало, как один из них
values. значения. A single, fixed value for t from among the supported choices shall be associated with Один, фиксированное значение для т из числа поддерживаемых вариантов должны быть связаны с
each key. каждый ключ.
5.2.2 Authenticated Decryption Function 5.2.2 проверкой подлинности Расшифровка Функция
Given the selection of an approved block cipher, key, and an associated tag length, the inputs to Учитывая выбор утвержденного блочного шифра, ключевой, и связано длина тега, входы в
the authenticated decryption function are values for IV , A , C , and T , as described in Sec. 5.2.1 аутентификацию функция дешифрование значения IV, А, С, и Т, как описано в гл. 5.2.1 above. выше. The output is one of the following: Выход одно из следующих действий:
• the plaintext P that corresponds to the ciphertext C , or • открытого текста Р, что соответствует зашифрованного текста C или
• a special error code, denoted FAIL in this document. • специальный код ошибки, обозначается неудачу в данном документе.
The output P indicates that T is the correct authentication tag for IV , A , and C ; Выход P указывает на то, что Т является правильным тег аутентификации для IV, А, В и С; otherwise, the в противном случае,
output is FAIL . выход из строя. The authentication assurance that can be inferred in each case is discussed in Обеспечение аутентификации, которые могут быть выведены в каждом случае обсуждается в
Appendix B. Приложение B.
The values for len( C ), len ( A ), and len( IV ) that an implementation supports for the authenticated Значения для Len (C), длина (A), и Лен (IV), что реализация поддерживает для проверки подлинности
decryption function shall be the same as the values for len( P ), len ( A ), and len( IV ) that the Функция расшифровки должны быть такими же, как значения для Len (P), Лен (A), и лен (IV), что
implementation supports for the authenticated encryption function. реализация поддерживает для авторизованного функции шифрования.
5.3 Primitives for Confidentiality and Authentication 5.3 Примитивы для конфиденциальности и аутентификации
The mechanism for the confidentiality of the plaintext within GCM is a variation of the Counter Механизм конфиденциальности открытого текста в МОЦ является вариацией на счетчик
mode [ 10], with a particular incrementing function, denoted inc Режим [ 10], с той или иной функции увеличивающимся, обозначается включая 32 32
, for generating the necessary , Для генерации необходимости
sequence of counter blocks. последовательность встречных блоков. The first counter block for the plaintext encryption is generated by Первый счетчик блоков открытого текста для шифрования генерируется
incrementing a block that is generated from the IV. увеличивая блок, который создается с IV.
The authentication mechanism within GCM is based on a hash function, called GHASH Механизм аутентификации в ГКМ на основе хэш-функции, называют GHASH
, that , Которые
features multiplication by a fixed parameter, called the hash subkey, within a binary Galois field. имеет умножение на фиксированный параметр, называемый хэш подраздел, в бинарном поле Галуа.
1 1
The designers of GCM define GHASH somewhat differently, appending encodings of the lengths of its two Дизайнеры GCM определить GHASH несколько иначе, добавляя кодировки длин его два
arguments. аргументы. In this Recommendation, these encodings are incorporated instead into the definitions of the В данной Рекомендации, эти кодировки включены вместо в определениях
authenticated encryption/decryption functions. прошедшие проверку функции шифрования / дешифрования. The specifications of the authenticated encryption/decryption Характеристики аутентифицированному шифрования / дешифрования
functions are ultimately equivalent, but the simplified version of GHASH in this Recommendation does not obtain функции в конечном счете, эквивалентны, но упрощенная версия GHASH в данной Рекомендации не получить
all of the properties that are shown for the designers' definition of GHASH in Ref. все свойства, которые показаны для определения дизайнеров из GHASH в работе. [7]. [7].
9 9
NIST Special Publication 800-38D NIST Special Publication 800-38D
The hash subkey, denoted H , is generated by applying the block cipher to the “zero” block. Хэш подраздел, обозначается H, генерируется путем применения блочного шифра к «нулевой» блока. The
resulting instance of this hash function, denoted GHASH в результате экземпляр этого хэш-функции, обозначается GHASH
H H
, is used to compress an encoding of , Используется для сжатия кодирование
the AAD and the ciphertext into a single block, which is then encrypted to produce the ААР и зашифрованный текст в единый блок, который затем шифруется с получением
authentication tag. аутентификации тег.
GHASH is a keyed hash function but not, on its own, a cryptographic hash function. GHASH является ключом хэш-функция, но не сам по себе, криптографический хэш-функция. This Это
Recommendation only approves GHASH for use within the context of GCM. Рекомендация только утверждает GHASH для использования в контексте ГКМ.
The intermediate values in the execution of the GCM functions shall be secret. Промежуточные значения в исполнении функций GCM является тайным. In particular, this В частности, это
requirement precludes a system in which GCM is implemented using the hash subkey publicly требование исключает систему, в которой GCM реализован с использованием хэш-подраздел публично
for some other purpose, for example, as an unpredictable value or as an integrity check value on для других целей, например, в качестве непредсказуемым значением, или в качестве значения проверки целостности
the key. Ключ.
6 Mathematical Components of GCM 6 Математическое Компоненты GCM
This section presents the mathematical components that appear in the specifications of the В этом разделе представлены математические компоненты, которые появляются в спецификациях
authenticated encryption and authenticated decryption functions in Sec. подлинности шифрование и проверку подлинности расшифровки функции в гл. 7 below. 7 ниже. Examples of Примеры the basic operations and functions on bit strings are given in Sec. 6. 1. основные операции и функции на битовых строк приведены в гл. 6. 1. The incrementing function Увеличивая функция is defined in Sec. 6. 2. определен в гл. 6. 2. Algorithm 1 for “multiplying” blocks is defined in Sec. Алгоритм 1 для "умножения" блоков определяется в гл. 6.3. 6.3. Algorithm 2 Алгоритм 2 for the GHASH function that is constructed from this multiplication is defined in Sec 6 .4. для функции GHASH что строится из этого умножения определяется в § 6 0,4. Algorithm 3 for the GCTR function is defined in Sec. Алгоритм 3 для функции GCTR определен в гл. 6 .5. 6 0,5. The specifications of Algorithms 1-3 include the inputs, the outputs, the steps of the algorithm, Характеристики алгоритмов 1-3 включают входы, выходы, этапы алгоритма,
diagrams, and summaries. диаграммы, и резюме. Equivalent sets of steps that produce the correct output are permitted. Эквивалентные набора шагов, которые производят правильный вывод разрешается.
The inputs that are typically fixed across many invocations of the function are called the Входы, которые обычно фиксированные во многих вызовах функции называются
prerequisites, although they may also be regarded as (varying) inputs. предпосылки, хотя они могут также рассматриваться как (разной) входов.
6.1 Examples of Basic Operations and Functions on Strings 6.1 Примеры основные операции и функции на струнных
In this document, the ' 0 ' bit and the ' 1 ' bit are indicated in the new courier font to help В этом документе, «0» немного и «1» бит указаны в новом шрифта курьерской помочь
distinguish them from the integers 0 and 1. отличить их от целых чисел 0 и 1.
Given a real number x , the ceiling function, denoted ⎡ x ⎤, is the least integer that is not less than x . Учитывая действительное число х, функцию потолка, обозначаемый ⎡ х ⎤, является наименее целое число, которое не меньше, чем х.
For example, ⎡2.1⎤ = 3, and ⎡4⎤ = 4. Например, ⎡2.1⎤ = 3, и ⎡4⎤ = 4.
Given a positive integer s , 0 Учитывая положительное целое число с, 0
s с
denotes the string that consists of s ' 0 ' bits. обозначает строку, состоящую из S '0 "бит. For example, 0 Например, 0
8 8
= =
00000000 . 00000000.
The concatenation operation on bit strings is denoted ||; Операция конгатенации битовых строк обозначается ||; for example, 001 || 10111 = например, 001 || 10111 =
00110111 . 00110111.
Given bit strings of equal length, the exclusive-OR (XOR) operation, denoted ⊕, specifies the Учитывая битовые строки равной длины, исключающее ИЛИ операция (XOR), обозначается ⊕, указывает
addition, modulo 2, of the bits in each bit position, ie, without carries. Кроме того, по модулю 2, из битов в позиции каждого бита, то есть, без переносов. For example, 10011 ⊕ Например, 10011 ⊕
10101 = 00110 . 10101 = 00110.
10 10
NIST Special Publication 800-38D NIST Special Publication 800-38D
Given a bit string X , the bit length of X is denoted len( X ). С учетом битовую строку X, немного длина X обозначается LEN (X). For example, len( 00010 )=5. Например, Len (00010) = 5.
Given a bit string X and a non-negative integer s such that len( X )≥ s , the functions LSB Учитывая битовую строку X и неотрицательное целое с такой, что LEN (X) ≥ S, функции LSB
s с
( X ) and (Х) и
MSB MSB
s с
( X ) return the s least significant (ie, right-most) bits and the s most significant (ie, left- (X) возвращает сек младший (т.е. самый правый) бит и с самым значительным (т.е. левой
most) bits, respectively, of X . большинство) биты, соответственно, X.
For example, LSB Например, LSB
3 3
( 111011010 ) = 010 , and (111011010) = 010, и
MSB MSB
4 4
( 111011010 ) = 1110 . (111011010) = 1110.
Given a bit string X , the (single) right-shift function, denoted X >> 1, is MSB Учитывая битовую строку X, (единственная) функция правой кнопкой переключения, обозначается X >> 1, является MSB
len( X ) Лен (X)
( 0 || X ). (0 || X). For Для
example, 0110111 >> 1 = 0011011 . пример, 0110111 >> 1 = 0011011.
Given a positive integer s and a non-negative integer x that is less than 2 Учитывая положительное целое с и неотрицательное целое х, которое меньше 2
s с
, the integer-to-string , Строка целое к
function, denoted [ x ] Функция, обозначается [X]
s с
, is the binary representation of x as a string of bit length s with the least , Является двоичным представлением х в виде строки из длина немного с с наименее
significant bit on the right. старший бит справа. For example, for the (base 10) integer 39, the binary representation Например, для (основание 10) 39 целого числа, двоичное представление
(base 2) is 100111 , so [39] (Основание 2) 100111, так [39]
8 8
= 00100111 . = 00100111.
Given a (non-empty) bit string X , the string-to-integer function, denoted int( X ), is the integer x Учитывая (непустое) немного строки X, функцию Строка-целого, обозначается Int (X), является целое х
such that [ x ] такие, что [х]
len( X ) Лен (X)
= X . = X. In other words, int( X ) is the non-negative integer less than 2 Другими словами, Int (X) является неотрицательное целое меньше 2
len( X ) Лен (X)
whose которого
binary representation is X . двоичным представлением является X. For example, int( 00011010 ) = 26. Например, Int (00011010) = 26.
6.2 Incrementing Function 6.2 Увеличение номера Функция
For a positive integer s and a bit string X such that len( X )≥ s , let the s -bit incrementing function, Для таких, что LEN (X) ≥ с, пусть функция с -bit увеличивающимся натурального ы и немного строка X,
denoted inc обозначаемое включая
s с
( X ), be defined as follows: (Х), можно определить следующим образом:
inc вкл
s с
( X )=MSB (X) = MSB
len( X )- s LEN (X) - с
( X ) || [int(LSB (X) || [Int (LSB
s с
( X ))+1 mod 2 (Х)) + 1 по модулю 2
s с
] ]
s с
In other words, the function increments the right-most s bits of the string, regarded as the binary Другими словами, функция увеличивает самая правая с биты строки, рассматриваемые как бинарный файл
representation of an integer, modulo 2 представление целого числа, по модулю 2
s с
; ; the remaining, left-most len( X )- s bits remain unchanged. остальные, крайний слева лен (X) - с биты остаются неизменными.
6.3 Multiplication Operation on Blocks 6.3 Умножение Операция по блокам
Let R be the bit string 11100001 || 0 Пусть Я битовая строка 11100001 || 0
120 120
. . Given two blocks X and Y , Algorithm 1 below Учитывая два блока X и Y, Алгоритм 1 ниже
computes a “product” block, denoted X • Y : вычисляет "продукт" блок, обозначается X • Y:
Algorithm 1: X • Y Алгоритм 1: X • Y
Input : Вход:
blocks X , Y . блоки X, Y.
Output : Выход:
block X • Y . Блок X • Y.
Steps : Шаги:
1. 1.
Let x Пусть х
0 0
x х
1 1
...x ... Х
127 127
denote the sequence of bits in X . Обозначим последовательность битов в X.
2. 2.
Let Z Пусть Z
0 0
= 0 = 0
128 128
and V и V
0 0
= Y . = Y.
3. 3.
For i = 0 to 127, calculate blocks Z Для = 0 до 127, вычислить блоки Z
i +1 я 1
and V и V
i +1 я 1
as follows: следующим образом:
11 11
NIST Special Publication 800-38D NIST Special Publication 800-38D
12 12
Z Z
i +1 я 1
= =
Z Z
i я
if x если х
i я
= 0; = 0;
Z Z
i я
⊕ V ⊕ V
i я
if x если х
i я
=1. = 1.
⎧ ⎧
⎨ ⎨
⎩ ⎩
V V
i +1 я 1
= =
V V
i я
>>1 >> 1
if LSB если LSB
1 1
( V (В
i я
) = 0; ) = 0;
V V
i я
>>1 >> 1
( (
) )
⊕ R ⊕ R
if LSB если LSB
1 1
( V (В
i я
) =1. ) = 1.
⎧ ⎧
⎨ ⎨
⎩ ⎩
4. 4.
Return Z Вернуться Z
128 128
. .
The • operation on (pairs of) the 2 • работа на (пар) в 2
128 128
possible blocks corresponds to the multiplication operation возможные блоки соответствует операции умножения
for the binary Galois (finite) field of 2 для бинарного Галуа (конечной) области 2
128 128
elements. элементы. The fixed block, R , determines a Неподвижный блок, R, определяет
representation of this field as the modular multiplication of binary polynomials of degree less представление этой области в качестве составной умножения двоичных многочленов степени меньше
than 128. The convention for interpreting strings as polynomials is “little endian”: ie, if u is чем 128. Конвенция для интерпретации строки как многочленов "обратным порядком байтов": то есть, если и
the variable of the polynomial, then the block x переменная многочлена, то блок х
0 0
x х
1 1
...x ... Х
127 127
corresponds to the polynomial x соответствует многочлена х
0 0
+ x + Х
1 1
u + и +
x х
2 2
u у
2 2
+ ... + x + ... + Х
127 127
u у
127 127
. . The XOR operation is used to add coefficients of “like” terms during the Операция XOR используется для добавления коэффициенты ", как" точки во время
multiplication. умножение. The reduction modulus is the polynomial of degree 128 that corresponds to R || 1. Модуль сокращение многочлен степени 128, что соответствует R || 1.
Ref. [6] discusses this field in detail. Ссылка. [6] обсуждает это поле подробно. For a positive integer i , the i th power of a block X with this multiplication operation is denoted Для натурального I, я-й степени блок X с этой операцией умножения обозначается
X X
i я
. . For example, H Например, Н
2 2
= H • H , H = H • H, H
3 3
= H • H • H , etc. = H • H • H, и т.д.
6.4 GHASH Function 6.4 GHASH Функция
Algorithm 2 below specifies the GHASH function: Алгоритм 2 ниже определяет функцию GHASH:
Algorithm 2: GHASH Алгоритм 2: GHASH
H H
( X ) (Х)
Prerequisites : Необходимые условия:
block H , the hash subkey. блок Н, хэш подраздел.
Input : Вход:
bit string X such that len( X ) = 128 m for some positive integer m . битовая строка X, таких, что лен (X) = 128 м в течение некоторого натурального т.
Output : Выход:
block GHASH Блок GHASH
H H
( X ). (Х).
Steps : Шаги:
1. Let X 1 Пусть X
1 1
, X , Х
2 2
, ... , X , ..., X
m -1 м -1
, X , Х
m м
denote the unique sequence of blocks such that X = X обозначать уникальную последовательность блоков таких, что X = X
1 1
|| X || X
2 2
|| ||
... || X ... || X
m -1 м -1
|| X || X
m м
. .
2. Let Y 2. Пусть Y
0 0
be the “zero block,” 0 быть "нулевой блок," 0
128 128
. .
3. For i = 1, ..., m , let Y 3 Для я = 1, ..., т, пусть Y
i я
= ( Y = (Y
i -1 я -1
⊕ X ⊕ X
i я
) • H . ) • H.
4. Return Y 4 Вернуться Y
m м
. .
In effect, the GHASH function calculates X По сути, функция GHASH вычисляет X
1 1
• H • H
m м
⊕ X ⊕ X
2 2
• H • H
m -1 м -1
⊕ ... ⊕ X ⊕ ... ⊕ X
m -1 м -1
• H • H
2 2
⊕ X ⊕ X
m м
• H . • H. Ref. [6] Ссылка. [6] describes methods for optimizing implementations of GHASH in both hardware and software. описываются методы оптимизации реализации GHASH в аппаратного и программного обеспечения.
The GHASH function is illustrated in F igure 1 below, without the zero block, Y Функция GHASH показано на F igure 1 ниже, без нулевой блок, Y 0 0
, whose , Чьи
exclusive-OR with X исключающее ИЛИ с X
1 1
does not change X не меняется X
1 1
. .
NIST Special Publication 800-38D NIST Special Publication 800-38D
Figure 1: GHASH Рисунок 1: GHASH
H H
( X (Х
1 1
|| X || X
2 2
|| ... || X || ... || X
m м
) = Y ) = Y
m м
. .
6.5 GCTR Function 6.5 GCTR Функция
Algorithm 3 below specifies the GCTR function. Алгоритм 3 ниже определяет функцию GCTR. The suggested notation does not indicate the Предложил обозначения не указывает
choice of the underlying block cipher. Выбор основного блочного шифра.
Algorithm 3: GCTR Алгоритм 3: GCTR
K K
( ICB , X ) (ICB, X)
Prerequisites : Необходимые условия:
approved block cipher CIPH with a 128-bit block size; утвержден блочный шифр CIPH с 128-битным размером блока;
key K . ключ К.
Input : Вход:
initial counter block ICB ; начальная счетчик блок ICB;
bit string X , of arbitrary length. битовая строка X, произвольной длины.
Output : Выход:
bit string Y of bit length len( X ). битовая строка Y длины немного LEN (X).
Steps : Шаги:
1. If X is the empty string, then return the empty string as Y .
2. Let
( ) ()
⎡
⎤
128 128
len X
n =
. .
3. Let X
1 1
, X
2 2
, ... , X
n -1
, X
n н
* *
denote the unique sequence of bit strings such that
∗ *
− -
= =
n н
n н
X X
X X
X X
X X
X X
||
||
... ...
||
||
1 1
2 2
1 1
; ;
X X
1 1
, X
2 2
,..., X
n -1
are complete blocks.
4. Let
ICB ICB
CB =
1 1
. .
5. For i = 2 to n , let CB
i я
= inc
32 32
( CB
i -1
). ).
6. For
( ) ()
i я
K K
i я
i я
CB
X X
Y Y
n н
i я
CIPH
let
,1
to в
1 1
⊕
= =
− -
= =
. .
7. Let
( ) ()
( ) ()
( (
) )
n н
K K
X X
n н
CB
X X
Y Y
n н
n н
CIPH
MSB MSB
len
∗ *
⊕
= =
∗ *
∗ *
. .
... ...
X X
X X
X X
1 1
• •
m м
2 2
2 2
Consequently, X
n н
* *
is either a complete block or a nonempty partial block, and if 1 ≤ len( X ) ≤128, then X = X
1 1
* *
. .
H H
Y Y
1 1
⊕
⊕
•H
Y Y
2 2
•H
Y Y
m м
13 13
NIST Special Publication 800-38D
8. Let
∗ *
. .
= =
n н
Y Y
Y Y
Y Y
Y Y
||
... ...
||
||
2 2
1 1
9. Return Y .
In Steps 1 and 2, the input string of arbitrary length is partitioned into a sequence of blocks to the
greatest extent possible, so that only the rightmost string in the sequence may be a “partial”
block. In Steps 3 and 4, the 32-bit incrementing function is iterated on the initial counter block
input to generate a sequence of counter blocks; the input block is the first block of the sequence.
In Steps 5 and 6, the block cipher is applied to the counter blocks and the results are XORed with
the corresponding blocks (or partial block) of the partition of the input string. In Step 7, the
sequence of results is concatenated to form the output.
Figure 2 below illustrates the GCTR function.
CIPH
K K
⊕
X X
2 2
Y Y
2 2
CIPH
K K
CB
n -1
⊕
X X
n -1
Y Y
n -1
CIPH
K K
⊕
X X
n н
* *
Y Y
n н
* *
ICB ICB
CIPH
K K
⊕
X X
1 1
Y Y
1 1
inc
… ...
… ...
CB
2 2
CB
n н
inc
Figure 2: GCTR
K K
( ICB , X
1 1
|| X
2 2
|| ... || X
n н
* *
) = Y
1 1
|| Y
2 2
|| ... || Y
n н
* *
. .
7 GCM Specification
Algorithms 4 and 5 for the authenticated encryption and authenticated decryption functions of
GCM are specified in Secs. 7 .1 a nd 7.2 below. The specifications include the inputs, the outputs,
the steps of the algorithm, diagrams, and summaries. The suggested notation does not indicate
the choice of the underlying block cipher. The inputs that are typically fixed across many
invocations of the function are called the prerequisites; however, some of the prerequisites may
also be regarded as (varying) input. The prerequisites and the other inputs shall meet the
For both algorithms, equivalent sets of steps that produce the correct output are permitted. For Для
example, in Algorithm 5, the verification of the tag may precede the computation of the
plaintext.
7.1 Algorithm for the Authenticated Encryption Function
Algorithm 4 below specifies the authenticated encryption function:
14 14
NIST Special Publication 800-38D
Algorithm 4: GCM-AE
K K
( IV , P , A )
Prerequisites :
approved block cipher CIPH with a 128-bit block size;
key K ;
definitions of supported input-output lengths;
supported tag length t associated with the key.
Input :
initialization vector IV (whose length is supported);
plaintext P (whose length is supported);
additional authenticated data A (whose length is supported).
Output :
ciphertext C ;
authentication tag T .
Steps :
1. Let H = CIPH
K K
( 0
128 128
). ).
2. Define a block, J
0 0
, as follows:
If len( IV )=96, then let J
0 0
= IV || 0
31 31
||1.
If len( IV ) ≠ 96, then let s = 128 ⎡len( IV )/128⎤-len( IV ), and let
J J
0 0
=GHASH
H H
( IV ||0
s +64
||[len( IV )]
64 64
). ).
3. Let C =GCTR
K K
(inc
32 32
( J
0 0
), P ).
4. Let
( ) ()
⎡
⎤
( ) ()
C C
C C
u у
len
128 128
len
128 128
− -
⋅
= =
and let
( ) ()
⎡
⎤
( ) ()
A
A
v V
len
128 128
len
128 128
− -
⋅
= =
. .
5. Define a block, S , as follows:
S = GHASH
H H
( A || 0
v V
|| C || 0
u у
|| [len( A )]
64 64
|| [len( C )]
64 64
). ).
6. Let
( (
) )
S S
J J
T Т
K K
, ,
0 0
. .
( (
) )
t т
GCTR
MSB MSB
= =
7. Return ( C , T ).
In Step 1, the hash subkey for the GHASH function is generated by applying the block cipher to
the “zero” block. In Step 2, the pre-counter block ( J
0 0
) is generated from the IV. In particular,
when the length of the IV is 96 bits, then the padding string 0
31 31
||1 is appended to the IV to form
the pre-counter block. Otherwise, the IV is padded with the minimum number of '0' bits,
possibly none, so that the length of the resulting string is a multiple of 128 bits (the block size);
this string in turn is appended with 64 additional '0' bits, followed by the 64-bit representation of
the length of the IV, and the GHASH function is applied to the resulting string to form the pre-
counter block. In Step 3, the 32-bit incrementing function is applied to the pre-counter block to
produce the initial counter block for an invocation of the GCTR function on the plaintext. The
output of this invocation of the GCTR function is the ciphertext.
In Steps 4 and 5, the AAD and the ciphertext are each appended with the minimum number of
' 0 ' bits, possibly none, so that the bit lengths of the resulting strings are multiples of the block
size. The concatenation of these strings is appended with the 64-bit representations of the
lengths of the AAD and the ciphertext, and the GHASH function is applied to the result to
produce a single output block. In Step 6, this output block is encrypted using the GCTR function
15 15
NIST Special Publication 800-38D
with the pre-counter block that was generated in Step 2, and the result is truncated to the
specified tag length to form the authentication tag. The ciphertext and the tag are returned as the
output in Step 7.
P P
C C
A
GHASH
H H
0 0
v V
0 0
u у
[len( A )]
64 64
[len( C )]
64 64
CIPH
K K
J J
0 0
GCTR
K K
GCTR
K K
MSB MSB
t т
H H
inc
32 32
0 0
128 128
T Т
IV IV
Figure 3: GCM-AE
K K
( IV , P , A ) = ( C , T ).
The authenticated encryption function is illustrated in Figure 3 above. The determination of
J 0 0
from IV (Step 2) is not depicted.
7.2 Algorithm for the Authenticated Decryption Function
Algorithm 5 below specifies the authenticated decryption function:
Algorithm 5: GCM-AD
K K
( IV , C , A , T )
Prerequisites :
approved block cipher CIPH with a 128-bit block size;
key K ;
definitions of supported input-output lengths;
supported tag length t associated with the key.
Input :
initialization vector IV ;
ciphertext C ;
16 16
NIST Special Publication 800-38D
additional authenticated data A ;
authentication tag T .
Output :
plaintext P or indication of inauthenticity FAIL .
Steps :
1. If the bit lengths of IV , A or C are not supported, or if len( T ) ≠ t , then return FAIL.
2. Let H = CIPH
K K
( 0
128 128
). ).
3. Define a block, J
0 0
, as follows:
If len( IV )=96, then J
0 0
= IV || 0
31 31
||1.
If len( IV ) ≠ 96, then let s = 128 ⎡len( IV )/128⎤-len( IV ), and
J J
0 0
=GHASH
H H
( IV ||0
s +64
||[len( IV )]
64 64
). ).
4. Let P =GCTR
K K
(inc
32 32
( J
0 0
), C ).
5. Let
( ) ()
⎡
⎤
( ) ()
C C
C C
u у
len
128 128
len
128 128
− -
⋅
= =
and let
( ) ()
⎡
⎤
( ) ()
A
A
v V
len
128 128
len
128 128
− -
⋅
= =
. .
6. Define a block, S , as follows:
S = GHASH
H H
( A || 0
v V
|| C || 0
u у
|| [len( A )]
64 64
|| [len( C )]
64 64
) )
7. Let
( (
) )
. .
( (
) )
S S
J J
T Т
K K
t т
, ,
GCTR
MSB MSB
0 0
=′
8. If
T Т
T Т
′
= , then return P ; else return FAIL .
In Step 1, the implementation's support for the lengths of the IV, the ciphertext, the AAD, and
the authentication tag is verified. In Step 2, the hash subkey for the GHASH function is
generated by applying the block cipher to the “zero” block. In Step 3, the pre-counter block ( J
0 0
) )
is formed as for the authenticated encryption function (Step 2 of Section 7 .1) . In Step 4, the 32-
bit incrementing function is applied to the pre-counter block to produce the initial counter block
for an invocation of the GCTR function on the ciphertext. The output of this invocation of the
GCTR function is the plaintext that corresponds to the ciphertext for the given IV.
In Steps 5 and 6, the AAD and the ciphertext are each appended with the minimum number of
' 0 ' bits, possibly none, so that the bit lengths of the resulting strings are multiples of the block
size. The concatenation of these strings is appended with 64-bit representations of the lengths of
the AAD and the ciphertext, and the GHASH function is applied to the result to produce a single
output block. In Step 7, this output block is encrypted using the GCTR function with the pre-
counter block that was generated in Step 3, and the result is truncated to the specified tag length
to form the authentication tag. In Step 8, the result of Step 7 is compared with the authentication
tag that was received as an input: if they are identical, then the plaintext is returned; otherwise,
FAIL is returned.
Equivalent sets of steps that produce the correct output are permitted. In particular, the В частности,
verification of the tag may precede the computation of the plaintext.
The authenticated decryption function is illustrated in Figure 4 below. The determination of
J 0 0
from IV (Step 3) is not depicted.
17 17
NIST Special Publication 800-38D
P P
C C
A
GHASH
H H
0 0
v V
0 0
u у
[len( A )]
64 64
[len( C )]
64 64
inc
32 32
CIPH
K K
J J
0 0
GCTR
K K
GCTR
K K
MSB MSB
t т
0 0
128 128
H H
T Т
′
if ≠
FAIL
T Т
IV IV
Figure 4: GCM-AD
K K
( IV , C , A , T ) = P or FAIL .
8 Uniqueness Requirement on IVs and Keys
The IVs in GCM must fulfill the following “uniqueness” requirement:
The probability that the authenticated encryption function ever will be invoked with the
same IV and the same key on two (or more) distinct sets of input data shall be no greater
than 2
-32 -32
. .
Compliance with this requirement is crucial to the security of GCM. Across all instances of the
authenticated encryption function with a given key, if even one IV is ever repeated, then the
implementation may be vulnerable to the forgery attacks that are described in Ref [5 ] and
summarized in Appendix A. In practice, this requirement is almost as important as the secrecy
of the key.
The role of key establishment in supporting this requirement is discussed in Sec. 8.1 . The two
allowed IV constructions for satisfying this requirement are given in Sec. 8 .2. Constraints on the
number of invocations of the authenticated encryption function are given in Sec. 8.3. 8.3.
18 18
NIST Special Publication 800-38D
8.1 Key Establishment
The following requirement, which is the norm for secret key cryptographic algorithms in general,
takes on explicit importance for GCM to support the uniqueness requirement in Sec. 8: Any GCM key that is established among its intended users shall, with high probability, be
fresh.
In practice, the requirements in Sec. 5.1 should ensure that a key is fresh when it is generated, if
the generation mechanism is resistant to tampering. Achieving such resistance usually imposes
requirements on the management of the key generation mechanism.
In particular, if the key generation mechanism is deterministic, then the management of the
mechanism shall provide strong assurance that no outside entity can induce the repetition of a
previous set of inputs to the mechanism, or otherwise cause the repetition of a previous output.
For example, GCM keys may be established using the key derivation functions of the following
protocols as allowed in [9 ]: Transport Layer Security, Internet Key Exchange v1 and v2, and
Secure Shell.
Similarly, if a new key must be transported to its intended recipient(s), the method of
transport/distribution shall provide strong assurance against “replay,” so that no party can induce
the substitution of a previous key for the intended key.
GCM keys should be established within the framework of an approved key management
structure to assure their freshness, as well as their confidentiality and authenticity; the details of
such structures are outside the scope of this Recommendation.
8.2 IV Constructions
This Recommendation provides two frameworks for constructing IVs. The first construction,
described in Sec. 8.2.1 , relies on deterministic elements to achieve the uniqueness requirement in
Sec. 8 ; the second construction, described in Sec. 8.2.2, relies on a sufficiently long output string
from an approved RBG with a sufficient security strength.
For any supported IV length that is strictly less than 96 bits, the construction in Sec. 8 .2.1, shall
be used, across all instances of the authenticated encryption function with the given key.
For any supported IV length that is 96 bits or greater, exactly one of the constructions, but not
both, shall be used, across all instances of the authenticated encryption function with the given
key. ключ.
For example, suppose that an implementation supports IV lengths of 64 bits, 96 bits, 128 bits,
and 160 bits. For 64-bit IVs the only choice is the construction in Sec. 8 .2.1. For the other three
IV lengths, one possible combination of choices is the construction in Sec. 8 .2.1 for 96-bit IVs
and the construction in Sec. 8.2.2 for 128-bit and 160-bit IVs.
19 19
NIST Special Publication 800-38D
8.2.1 Deterministic Construction
In the deterministic construction, the IV is the concatenation of two fields, called the fixed field
and the invocation field. The fixed field shall identify the device, or, more generally, the context
for the instance of the authenticated encryption function. The invocation field shall identify the
sets of inputs to the authenticated encryption function in that particular device.
For any given key, no two distinct devices shall share the same fixed field, and no two distinct
sets of inputs to any single device shall share the same invocation field. Compliance with these
two requirements implies compliance with the uniqueness requirement on IVs in Sec. 8 . If desired, the fixed field itself may be constructed from two or more smaller fields. Moreover, Кроме того,
one of those smaller fields could consist of bits that are arbitrary (ie, not necessarily
deterministic nor unique to the device), as long as the remaining bits ensure that the fixed field is
not repeated in its entirety for some other device with the same key.
Similarly, the entire fixed field may consist of arbitrary bits when there is only one context to
identify, such as when a fresh key is limited to a single session of a communications protocol. In В
this case, if different participants in the session share a common fixed field, then the protocol
shall ensure that the invocation fields are distinct for distinct data inputs.
The invocation field typically is either 1) an integer counter or 2) a linear feedback shift register
that is driven by a primitive polynomial to ensure a maximal cycle length. In either case, the
invocation field increments upon each invocation of the authenticated encryption function.
The lengths and positions of the fixed field and the invocation field shall be fixed for each
supported IV length for the life of the key. In order to promote interoperability for the default IV
length of 96 bits, this Recommendation suggests, but does not require, that the leading (ie,
leftmost) 32 bits of the IV hold the fixed field; and that the trailing (ie, rightmost) 64 bits hold
the invocation field.
8.2.2 RBG-based Construction
In the RBG-based construction, the IV is the concatenation of two fields, called the random field
and the free field. For each IV length that is supported by the implementation and used with the
RBG-based construction, the lengths of these fields shall be fixed for the life of the key.
Moreover, the length of the random field shall be at least 96 bits; the free field may be empty.
If i is a supported IV length that is associated to the RBG-based construction, then let r ( i ) denote
the bit length of the random field. The random field shall either consist of 1) an output string of
r ( i ) bits from an approved RBG with a sufficient security strength, or 2) the result of applying the
r ( i )–bit incrementing function to the random field of the preceding IV for the given key. The
r ( i )–bit output string from the RBG is called a direct random string, and the random fields that
result from applying the r ( i )–bit incrementing function are called its successors.
20 20
NIST Special Publication 800-38D
There are no requirements on the bits in the free field. For example, they may identify the
device, similar to the fixed field of the deterministic construction, except within the RBG-based
construction these identifiers are not required to be distinct for each device. For any IV length
that is associated to the RBG-construction, the free field is recommended to be empty, so that the
random field is the entire IV .
The instantiations of the RBGs in any two distinct devices shall be independent, so that the
distribution of direct random strings across all of the RBG instantiations is expected to be
uniform. For example, if the initialization of the RBG instantiations depends only on a secret
seed, then each instantiation shall be initialized with a distinct seed.
8.3 Constraints on the Number of Invocations
The following requirement applies to all implementations that use either 1) the deterministic
construction with IVs whose length is not 96, or 2) the RBG-based construction, for IVs of any
length. In other words, unless an implementation only uses 96-bit IVs that are generated by the
deterministic construction:
The total number of invocations of the authenticated encryption function shall not exceed
2 2
32 32
, including all IV lengths and all instances of the authenticated encryption function with
the given key.
This is a “global” requirement that can be achieved by appropriate “local” limits on each
instance of the authenticated encryption function with a given key. For example, suppose an
implementation consists of 2
10 10
devices that only support 64-bit, 96-bit, and 128-bit IVs. One Один
way to satisfy the above requirement would be to limit each device to 2
20 20
invocations with 64-bit
IVs, 2
21 21
invocations with 96-bit IVs, and 2
20 20
invocations with 128-bit IVs.
For the RBG-based construction of IVs, the above requirement, in conjunction with the
requirement that r (
i )≥96, is sufficient to ensure the uniqueness requirement in Sec.
8, as follows
from the discussion in Ref. [ 4]. For the deterministic construction, the lengths of the two fields imply two additional operational
constraints. These constraints apply to any supported IV length, including 96 bits:
• The bit length of the invocation field limits the number of invocations of the
authenticated encryption function with any given fixed field and key. In particular, if s
denotes the number of bits in the invocation field, then the authenticated encryption
function cannot be invoked on more than 2
s с
distinct input sets without violating the
uniqueness requirement.
• Similarly, an s -bit fixed field implies a limit of 2
s с
on the number of distinct
devices/contexts that can implement the authenticated encryption function for the given
key, with IVs of the given length.
21 21
NIST Special Publication 800-38D
9 Practical Considerations for Validating Implementations
Both the designer of a GCM implementation and the information technology (IT) professional
who deploys and maintains it within a particular system have important roles in meeting the
uniqueness requirement in Sec. 8, as discussed in Secs. 9.1 and 9.2 below.
The additional requirements in these two sections are provided for the purpose of demonstrating
compliance with the uniqueness requirement in Sec. 8 w ithin a validation program.
Specifically, В частности, analogous to the requirements in Ref. [9] , the requirements in these two sections apply to
implementations that are validated against the requirements of FIPS Pub. 140-2 (Ref. [ 3]) , or any
superseding version of FIPS 140.
Implementations that are not validated against the requirements of FIPS Pub. 140-2 may interpret
the requirements in Secs. 9. 1 and 9.2 as recommendations.
9.1 Design Considerations
In order to inhibit an unauthorized party from controlling or influencing the generation of IVs,
GCM shall be implemented only within a cryptographic module that meets the requirements of
FIPS Pub. 140-2. In particular, the cryptographic boundary of the module shall contain a
“generation unit” that produces IVs according to one of the constructions in Sec. 8.2 above.
The documentation of the module for its validation against the requirements of FIPS 140-2 shall
describe how the module complies with the uniqueness requirement on IVs. At a minimum, the
documentation shall address the considerations in this section, and clearly document the
responsibilities of the IT professional who configures, deploys, and maintains the GCM
implementations within a larger system.
The following are three important design considerations for GCM modules:
1. The freshness of keys shall be assured, as discussed in Sec. 8 .1. 2. The IV shall be a critical security parameter as defined in FIPS Pub. 140-2 until the
authenticated encryption function is invoked with the IV. Prior to this invocation, the IV
shall be provided the same protection as other critical security parameters in a module
that is validated to the requirements in FIPS Pub. 140-2.
3. A loss of power to the module shall not cause the repetition of IVs. If the generation unit
cannot recover from a loss of power, then the authenticated encryption function shall
enter a failure state until a fresh key can be established.
The IV construction that is implemented from Sec. 8 .2 above affects the options for recovery
from a loss of power. For the deterministic construction, all of the deterministic elements that
are necessary to construct the IV would have to be available when power is restored. For Для
example, these elements could be stored in non-volatile memory.
22 22
NIST Special Publication 800-38D
When power is restored, neither the preceding IV nor any other previous IV shall immediately be
repeated for the key. One way to avoid such a repetition would be to ensure that the invocation
field value that is periodically stored in the non-volatile memory is always one or more values
ahead of the operational value in the sequence.
One potential advantage of the RBG-based construction is that the RBG may be designed to
recover from a loss of power in a straightforward manner, ie, without requiring action from the
IT professional that maintains the system. For example, the RBG may incorporate a non-
deterministic source of bits that would automatically be available to the RBG when power is
restored.
Alternatively, the entire state of the RBG may be stored periodically in non-volatile memory. In В
this case, similar to the deterministic construction, when power is restored, the design shall
ensure that the RBG shall not output strings for use within new IVs until the state of the RBG is
advanced beyond the state that generated the last IV for the key. In other words, the direct
random string for the first new IV shall be, with high probability, different than the direct
random string in any IV that was generated before the loss of power.
Even if the process is not automatic, the IT professional who maintains the system may simply
reinitialize the RBG when power is restored, for example, with a fresh seed. In this case, either
the design of the module or the IT professional that maintains the system shall ensure that
compliance is maintained with the independence condition on the RBGs in Sec. 8 .2.2. 9.2 Operational Considerations
Compliance with the uniqueness requirement on IVs, and hence the security of GCM, ultimately
depends on the IT professional who configures, deploys, and maintains the GCM modules within
a particular system. The documentation for a GCM module shall give the IT professional
detailed instructions that are tailored to the particular design of the module.
The following are some typical operational considerations for the uniqueness requirement:
• Is the configuration of any GCM module, or any operational value, vulnerable to control
or influence from any unauthorized party?
• For any given key, how are configuration choices enforced across all modules that ever
implement the authenticated encryption function?
• How is the freshness of keys assured, as discussed in Sec. 8.1 ?
• If an implementation does not exclusively use 96-bit IVs that are generated by the
deterministic construction, how is the requirement in Sec 8. 3 on the number of
invocations ensured?
• As discussed in Sec. 9 .1, how does IV generation within the modules recover from a loss
of power without violating the uniqueness requirement on IVs?
23 23
NIST Special Publication 800-38D
24 24
The following considerations are specific to the deterministic construction:
• How are the device identifiers installed into the fixed field so that compliance with the
requirements on the fixed field in Sec. 8 .2.1 is ensured, both for the initially deployed
modules and for any subsequent deployed modules?
• Is the length of the invocation field sufficient to support all of the invocations that can
occur in any module during the lifetime of any key, as discussed in the first bullet in Sec.
• For any given key and IV length, is the length of the fixed field sufficient to support the
number of modules that will implement authenticated encryption, as discussed in the
second bullet in Sec. 8.3 ?
• If the default setting for the lengths of the fixed field and the invocation field can be
altered, then how is the choice enforced across all modules with any given key?
The following consideration is specific to the RBG-based construction:
• How are the RBGs for IV generation initialized so that compliance is ensured with the
independence requirement in Sec. 8 .2.2, for the initially deployed modules and for any
subsequent deployed modules?
10 Conformance
The two categories of implementations that may claim conformance with this Recommendation
are GCM and GMAC.
Implementations may restrict the bit lengths of the plaintext, AAD, IVs, and authentication tags
that it supports, as discussed in Secs. 5.2.1. 1 and 5.2.1.2 above. Although such restrictions may
affect interoperability, only the elimination of the plaintext altogether, ie, GMAC, is considered
as a distinct category of implementation.
For every algorithm that is specified in this Recommendation, a conforming implementation may
replace the given set of steps with any mathematically equivalent sets of steps. In other words,
different procedures that produce the correct output for any input are permitted.
NIST Special Publication 800-38D
Appendix A: Importance of the Uniqueness Requirement on IVs
Sec. 8 contains a uniqueness requirement for the IVs of GCM, across all implementations of the
authenticated encryption function with any given key. This appendix summarizes why this
requirement is crucial to the security of GCM, as first described in Ref. [ 5]. The secure operation of a cryptographic algorithm depends not only on the proper
implementation of the steps of the algorithm, but also on the adherence to the associated
requirements. требования. An obvious example for any symmetric key algorithm is that the key needs to be
kept secret. For GCM, the requirement in Sec. 5 .2.1 for the uniqueness of the IVs is almost as
important, although not as obvious.
Consider first the example of the Counter mode requirement in Ref. [ 10] for the counter blocks
to be unique. If this requirement is breached, then the Counter mode encryption function may
fail to provide the expected confidentiality for the data blocks that correspond to the repeating
counter blocks, although the other data blocks are not affected.
The Counter mode decryption function has a vulnerability that is arguably more serious.
Counter-mode ciphertext is “malleable” in the sense that flipping any of its bits will induce the
corresponding bits of the plaintext to flip upon decryption. Therefore, if an adversary knows a
plaintext-ciphertext pair and can induce the decryption function to use the counter blocks from
the known pair, then, by choosing which bits to flip in the known ciphertext, the adversary can
control the result of decryption, up to the length of the known plaintext.
This vulnerability motivates combining the Counter mode encryption mechanism with an
authentication mechanism, such as occurs in GCM. The idea is to prevent the adversary’s
altered ciphertext from being accepted as valid. However, as detailed in Ref. [ 5], the
authentication assurance in GCM crucially depends on the uniqueness of the IVs.
In particular, if IVs are ever repeated for the GCM authenticated encryption function for a given
key, then it is likely that an adversary will be able to determine the hash subkey from the
resulting ciphertexts. The adversary then could easily construct a ciphertext forgery. In В
particular, given the ciphertext and tag outputs for an invocation of the authenticated encryption
function, along with the associated IV and AAD inputs, the adversary could substitute any
ciphertext and AAD strings and use the subkey to generate the valid substitute tag. Although Хотя
this forgery would use the same IV, in most cases it will not be feasible for the authenticated
decryption function to detect the repetition. Thus, the authentication assurance essentially is lost.
Worse, the loss of authentication means that GCM inherits the problematic malleability of its
Counter mode ciphertext. In the above scenario, knowing the original plaintext that corresponds
to the given ciphertext, the adversary can construct the substitute ciphertext in such a way as to
correspond to any desired plaintext of the same length. In other words, the adversary essentially
could control the plaintext output of the authenticated decryption function.
25 25
NIST Special Publication 800-38D
Appendix B: Authentication Assurance
The creation of an authentication tag by the authenticated encryption function provides the
mechanism whereby assurance of the authenticity of the plaintext and AAD (and IV) can be
obtained upon the execution of the authenticated decryption function. The nature of this
assurance depends on the output of the authenticated decryption function:
• If the output is the plaintext, then the design of the mode provides strong, but not
absolute, assurance that the purported source of the data created the tag, ie, that the
plaintext and the AAD (and the IV and the tag) are authentic. Consequently, the mode
also provides strong assurance that this information was not subsequently altered, either
intentionally or unintentionally.
• If the output is FAIL , then it is certain that at least one of the given inputs (ie, the
ciphertext, the AAD, the IV, or the tag) is not authentic.
In the first case, the assurance is not absolute because forgeries are possible, in principle. In В
other words, an adversary, ie, a party without access to the key or to the authenticated
encryption function, may be able to produce the correct tag for some triple of ciphertext, AAD,
and IV.
As with any tag-based authentication mechanism, if the adversary chooses a t -bit tag at random,
it is expected to be correct for given data with probability 1/2
t т
. . With GCM, however, an
adversary can choose tags that increase this probability, proportional to the total length of the
ciphertext and AAD. Consequently, GCM is not well-suited for use with short tag lengths or
very long messages.
In particular, if n denotes the total number of blocks in the encoding (ie, the input to the
GHASH function in the definition of S in Secs.
7. 1 and 7.2 above) of the ciphertext and AAD,
then there is a method of constructing a “targeted” ciphertext forgery that is expected to succeed
with a probability of approximately n /2
t т
. . Moreover, each successful forgery in this attack 1)
increases the probability that subsequent targeted forgeries will succeed, and 2) leaks
information about the hash subkey, H . Eventually, H may be compromised entirely, with
consequences as described at the end of Appendix A: the authentication assurance is completely
lost.
Ref. [1] describes the attack, and Ref. [7] gives a detailed treatment of the security properties of
GCM. Appendix C gives guidance and requirements for the use of the two shortest tags sizes, 32
and 64 bits.
Independent of this attack, an adversary may attempt to systematically guess many different tags
for a given input to authenticated decryption, and thereby increase the probability that one (or
more) of them, eventually, will be accepted as valid. For this reason, the system or protocol that
implements GCM should monitor and, if necessary, limit the number of unsuccessful verification
attempts for each key.
26 26
NIST Special Publication 800-38D
Moreover, as with most block cipher modes of operation, the security assurance of GCM
degrades as more data is processed with a single key. Therefore, the total number of blocks of
plaintext and AAD that are protected by invocations of the authenticated encryption function
during the lifetime of the key should be limited. A reasonable limit for most applications would
be 2
64 64
, consistent with the requirement on the number of invocations in Sec. 8 .3. 27 27
NIST Special Publication 800-38D
Appendix C: Requirements and Guidelines for Using Short Tags
For some voice or video applications, short authentication tags can be appropriate. The forgery
of some fraction of the individual authenticated “packets” may be tolerable, because each packet
of data in a large stream may carry very little of the overall meaning.
However, even for voice and video applications, short tags can be problematic for GCM, due to
the targeted forgery attack that is summarized in Appendix B and detailed in Ref. [1] . Absent
the requirements and guidelines in this appendix, it may be practical for the attack to produce the
hash subkey, H , after which the authentication assurance is completely lost. Nevertheless, this
Recommendation does not preclude short tags entirely, because knowledgeable security
professionals should be able to manage the risks in connection with this attack, and its potential
improvement. улучшение.
The following guidelines implicitly describe the special circumstances that may be appropriate
for short tags. A packet in this context is a set of inputs to the authenticated decryption function.
1. Packets that fail the integrity check within the authenticated decryption function should
be silently discarded. In other words, the controlling protocol/system over which packets
are received should not provide an ACK/NACK response regarding the integrity of
individual packets. However, the receiver should log authentication errors internally—in
a way which is undetectable from side-channel information—and terminate the
connection or notify the user if the percentage of errors exceeds what would be
considered normal. This is standard security practice with any protocol/system and any
algorithm choice.
2. The AAD within packets should be limited to the necessary header information and
should not contain messages to be authenticated along with the encrypted data.
3. The substance or meaning of the overall message that is comprised of a large number of
packets should not be lost or compromised by the forgery of a single, arbitrary packet.
For example, packets could carry a sequence of snippets of voice or visual data, but an
individual packet should not carry a .txt or .doc file. Ideally, the plaintext data
underlying the encryption should not be so stereotypical as to be guessable.
4. The controlling protocol/system should establish a new GCM key—and thus a new hash
subkey, H —frequently, depending on the maximum combined length of the ciphertext
and AAD that can occur within a single packet. Moreover, for 32-bit tags, this combined
length should be very small—on the order of tens or hundreds of bytes; 64-bit tags extend
the maximum combined length into the millions of bytes.
An example of a protocol that meets these guidelines is Secure Real-time Transport Protocol
carrying Voice over Internet Protocol, running over User Datagram Protocol.
28 28
NIST Special Publication 800-38D
Tables 1 and 2 below quantify the recommendations in Item 4 above, for 32-bit and 64-bit tags,
respectively. соответственно. Each row has two entries: 1) a maximum combined length for the ciphertext and
the AAD in a single packet, in bytes, and 2) a corresponding maximum number of invocations of
the authenticated decryption function, across all instances of the GCM with the given key.
For any implementation that supports 32-bit or 64-bit tags, one of the rows in Table 1 or Table 2,
respectively, shall be enforced. In particular, the supported lengths for the plaintext/ciphertext
and the AAD shall ensure that every valid packet satisfies the length restriction in the row, and
the controlling protocol/system shall ensure that the key is changed before the authenticated
decryption function is invoked more than the maximum that is given in the row. A smaller
maximum may also be enforced.
Table 1: Constraints with 32-bit Tags
Maximum Combined Length
of the Ciphertext and AAD
In a Single Packet (bytes)
Maximum Invocations of the
Authenticated Decryption Function
2 2
5 5
2 2
22 22
2 2
6 6
2 2
20 20
2 2
7 7
2 2
18 18
2 2
8 8
2 2
15 15
2 2
9 9
2 2
13 13
2 2
10 10
2 2
11 11
Table 2: Constraints with 64-bit Tags
Maximum Combined Length
of the Ciphertext and AAD
In a Single Packet (bytes)
Maximum Invocations of the
Authenticated Decryption Function
2 2
15 15
2 2
32 32
2 2
17 17
2 2
29 29
2 2
19 19
2 2
26 26
2 2
21 21
2 2
23 23
2 2
23 23
2 2
20 20
2 2
25 25
2 2
17 17
29 29
NIST Special Publication 800-38D
Appendix D: Protection Against Replay of Messages
As described in Appendix B, the successful verification of the tag within the authenticated
decryption function gives assurance of the authenticity of the data; however, the party that
presents the input data to the authenticated decryption function may not be the original source of
the plaintext and AAD. In other words, GCM, like many other authentication mechanisms, does
not inherently prevent an adversary from intercepting the output of an invocation of
authenticated encryption and “replaying” it for authenticated decryption at a later time, for
example, in an attempt to impersonate a party that has access to the key. In some protocols an
adversary may even be able to use data that the verifier itself generated earlier in the protocol.
The controlling system or protocol may protect against such an event by monitoring for any
duplication of the IVs that are presented for authenticated decryption. Alternatively, certain
identifying information can be incorporated into the AAD. Examples of such information
include a sequential message number or a timestamp. Upon successful verification of
authenticity, this information may provide a means for the detection of replayed messages, out-
of-sequence messages, or missing messages.
30 30
NIST Special Publication 800-38D
31 31
Appendix E: Bibliography
[1] [1]
Ferguson, N., Authentication Weaknesses in GCM, Natl. Inst. Ин-т. Stand. Technol.
[Web page], http://www.csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/
CWC-GCM/Ferguson2.pdf, May 20, 2005.
[2] [2]
FIPS Publication 197, The Advanced Encryption Standard (AES), US DoC/NIST,
November 26, 2001.
[3] [3]
FIPS Publication 140-2, Security Requirements for Cryptographic Modules, US
DoC/NIST, May 25, 2001.
[4] [4]
IEEE P1619.1™/D23, Draft Standard for Authenticated Encryption with Length
Expansion for Storage Devices.
[5]
A. Joux, Authentication Failures in NIST version of GCM, Natl. Inst. Ин-т. Stand. Technol.
[Web page], http://www.csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/800-
38_Series-Drafts/GCM/Joux_comments.pdf.
[6] [6]
D. McGrew, J. Viega, The Galois/Counter Mode of Operation (GCM), Natl. Inst. Ин-т. Stand.
Technol. [Web page] , http://www.csrc.nist.gov/groups/ST/toolkit/BCM/documents/
proposedmodes/gcm/gcm-revised-spec.pdf, May 31, 2005.
[7]
D. McGrew and J. Viega. The Security and Performance of the Galois/Counter Mode
(GCM) of Operation. Proceedings of INDOCRYPT '04, Springer-Verlag, 2004. Full
paper available from the IACR Cryptology ePrint Archive: Report 2004/193, [Web
page], http://eprint.iacr.org/2004/193/, October 7, 2004.
[9]
National Institute of Standards and Technology and Communications Security
Establishment, Implementation Guidance for FIPS Pub. 140-2 and the Cryptographic
Module Validation Program, Natl. Inst. Ин-т. Stand. Technol. [Web page], http://csrc.nist.gov/
groups/STM/cmvp/documents/fips140-2/FIPS1402IG.pdf.
[10] NIST Special Publication 800-38A, 2001 ED, Version 1, Recommendation for Block
Cipher Modes of Operation—Methods and Techniques, December 2001, Natl. Inst. Ин-т.
Stand. Technol. [Web page] , http://www.csrc.nist.gov/publications/nistpubs/800-38a/
sp800-38a.pdf.