AEAD-режим блочного шифрования

AEAD-режимы блочного шифрования (англ. Authenticated Encryption with Associated Data, «аутентифицированное шифрование с присоединёнными данными») — класс блочных режимов шифрования, при котором часть сообщения шифруется, часть остается открытой, и всё сообщение целиком аутентифицировано. Впервые идея такого класса шифрования была предложена Charanjit Jutla в 2000 году^[1]. В настоящее время предложено несколько AEAD-режимов шифрования: OCB mode (с версии OCB2), CCM mode, EAX mode, CWC mode, и GCM mode. Последний с 2007 года является стандартом NIST^[2].

Возникновение проблемыПравить

Существуют алгоритмы, позволяющие осуществить аутентификацию и шифрование — authenticated encryption (далее AE), однако в них не предусмотрена возможность прикреплять открытый текст (associated data), которая возникает, в частности, при необходимости прикрепить к сообщению IP-адрес. Вообще, часто незашифрованные данные требуются для передачи заголовков, адресов, портов, версий протокола и других данных, необходимых для принятия решения о том, как должен обрабатываться или пересылаться зашифрованный текст. Часто эти данные должны быть аутентифицированы, в то же время оставаясь открытыми, чтобы устройства обработки могли оперировать с данными сообщениями должным образом. Возникает желание модифицировать AE-схему, добавив к ней имитовставку (MAC) для аутентификации открытых данных, и «задешево» получить AEAD-схему. Однако очевидные «наивные» решения, примеры которых рассмотрим ниже, оказываются неэффективными.

Пусть, например, нужно передать сообщение M, открытый заголовок H, выбран какой-либо AE-режим шифрования E и функция MAC. Тогда, если передавать E(M) и H, то H окажется не аутентифицированным. Если же передать E(M||H) и H, длина передаваемого сообщения окажется длиннее исходного (так как будет выполнена ненужная в данной задаче операция шифрования H), то же можно сказать и для случая передачи H, E(M), MAC(H||E(M)) (так как E(M) уже аутентифицированно и использование MAC требует расхода лишних ресурсов).

Важно, что и AE-схемы, и AEAD-схемы требуют использования nonce. Это необходимо для обеспечения семантической безопасности (невозможность злоумышленника при многократном использовании схемы под одним и тем же ключом получить отношения между сегментами зашифрованных сообщений), а также для защиты от атаки повторного воспроизведения, при которой злоумышленник под видом легального пользователя повторно отправляет сообщение. Генерация nonce и использование его только единожды ложится на ответственность отправителя. Для этого можно использовать, например, счетчик.

Методы реализацииПравить

Encrypt-then-mac (AEAD)

Существуют два принципиально разных пути реализации AEAD-режима шифрования. Первый предполагает использование блочного режима шифрования и имитовставки. В этом случаем разработчик AEAD-схемы может выбирать любой блочный алгоритм шифрования и функцию получения имитовставки, при этом так же необходимо использовать nonce. Второй способ — какое-либо преобразование AE-схемы. Требования к последнему методу остаются прежними: схема не должна значительно замедляться, также в ней не должно появляться новых уязвимостей. Безопасность и надежность данных подходов была доказана в статье Charanjit S. Jutla «Encryption Modes with Almost Free Message Integrity» при условии, что nonce не используется повторно и хеш-функция H является криптографически стойкой.

Методы реализации AEAD-режима с помощью блочного шифра и имитовставкиПравить

Получить AEAD-режим с помощью блочного шифра и имитовставки возможно двумя способами: сначала шифруя сообщение, затем аутентифицируя (encrypt-then-mac), или же в обратном порядке (mac-then-encrypt).

Encrypt-then-macПравить

В данном варианте сначала шифруется сообщение M с использованием nonce N, затем заголовок H и зашифрованное сообщение аутентифицируются с помощью MAC с тем же nonce.

Mac-then-encryptПравить

Mac-then-encrypt (AEAD)

Аналогично предыдущему, но в обратном порядке: сначала создается имитовставка MAC от заголовка H, nonce N и открытого текста M, а затем шифруется сообщение M с полученной имитовставкой с использованием того же nonce N.

Методы реализации AEAD-режима с помощью AE-схемыПравить

Как было показано выше, эффективно прикрепить аутентифицированный открытый текст к построенному с помощью AE-схемы сообщению примитивными способами невозможно. Однако было предложено^[1] два следующих метода.

Nonce stealingПравить

Пусть имеется AE-схема, использующая nonce размером n бит, а приложению, использующему данную схему, достаточно использовать лишь n2 бит (n2 < n). Тогда свободные h = n − n2 бит могут быть использованы для хранения открытых данных. Данная схема имеет ограничение на размер открытых данных, однако часто этого достаточно. Пусть алгоритм имеет nonce размером 128 бит, а приложение использует лишь 16, тогда для открытых данных остается 112 бит, которых часто вполне достаточно (например, для адреса в протоколе IPv4 требуется 32 бита).

Ciphertext translationПравить

Данный метод приведения AE-схемы к AEAD-схеме основан на операции логического сложения (XOR) $\text{[math]}$ $\text{[math]}$ $\oplus$ , при этом, если производится операция над строками разной длины, то более короткая дополняется не значимыми нулями, например: $\text{[math]}$ $\text{[math]}$ $11101001\oplus 101=11101100$ .

Данный метод включает в себя следующие операции: используется AE-схема для шифрования сообщения с ключом K и получения промежуточного шифртекста CT, далее применяется хеш-функция $\text{[math]}$ $\text{[math]}$ $F_{K'}$ для получения сдвига Δ, и наконец, финальный шифртекст получается в результате применения операции логического сложения Δ к последним битам CT. Заметим, что если заголовок является пустой строкой, полученная AEAD-схема переходит в исходную AE-схему шифрования. Если заголовок остается неизменным в течение сессии, то сдвиг Δ может быть вычислен заранее, что положительно сказывается на времени шифрования — оставшаяся операция логического сложения легко реализуема (в том числе и аппаратно).

Определим получаемую AEAD-схему более строго следующим образом:

$\text{[math]}$ $\text{[math]}$ ${\ddot {E}}_{K,K'}^{N,H}(M)=E_{K}^{N}(M)\oplus F_{K'}(H)$

$\text{[math]}$ $\text{[math]}$ ${\ddot {D}}_{K,K'}^{N,H}(C)=D_{K}^{N}(C\oplus F_{K'}(H))$

То есть, предполагая, что $\text{[math]}$ $\text{[math]}$ $H\neq 0$ , вычисляем $\text{[math]}$ $\text{[math]}$ $F_{K'}(H)=$ Δ длиной в τ бит, зашифровываем M и производим операцию логического сложения последних τ бит с Δ.

Данный метод имеет следующие преимущества:

применим к любой AE-схеме;
если не нужно прикреплять незашифрованные данные H, исходный AE-метод не усложняется;
если заголовок H не меняется с течением времени, $\text{[math]}$ $\text{[math]}$ $F_{K'}(H)$ может быть заранее вычислена.

Однако недостаток метода состоит в необходимости использования двух ключей K и K’.

AEAD-алгоритмыПравить

Для примера опишем некоторые AEAD-алгоритмы. Два из них основаны на AES GCM, два из них — на AES CCM. Один из алгоритмов в каждой паре использует 128-битный ключ, другой — 256 битный.

AEAD AES 128 GCMПравить

Данный алгоритм использует AES-128 в качестве алгоритма блочного шифрования, используя ключ, nonce, сообщение и заголовок в качестве входных данных. Длина заголовка — 16 байт. Зашифрованный текст формируется добавлением аутентификационного тега к промежуточному зашифрованному тексту, полученному в качестве выходных данных GCM-шифрования. Требования к размерам входных и выходных данных следующие:

размер nonce — 12 байт;
длина ключа — 16 байт;
максимальный размер сообщения $\text{[math]}$ $\text{[math]}$ $2^{36}$ − 31 байт;
максимальный размер заголовка $\text{[math]}$ $\text{[math]}$ $2^{61}$ − 1 байт;
максимальный размер зашифрованного сообщения $\text{[math]}$ $\text{[math]}$ $2^{36}$ − 15 байт.

Таким образом, шифртекст на 16 байт длиннее исходного открытого сообщения.

AEAD AES 256 GCMПравить

Алгоритм полностью аналогичен предыдущему, за исключением использования ключа размером 32 байт и AES-256 GCM.

AEAD AES 128 CCMПравить

Аналогично предыдущему, за исключением использования CCM режима вместо GCM, при этом:

размер nonce 12 байт;
длина ключа 16 байт;
максимальный размер сообщения $\text{[math]}$ $\text{[math]}$ $2^{24}$ − 1 байт;
максимальный размер заголовка $\text{[math]}$ $\text{[math]}$ $2^{64}$ − 1 байт;
максимальный размер зашифрованного сообщения $\text{[math]}$ $\text{[math]}$ $2^{24}$ + 15 байт.

Как и при использовании GCM, размер шифртекста на 16 байт длиннее исходного сообщения.

AEAD AES 256 CCMПравить

Алгоритм полностью аналогичен предыдущему, за исключением использования ключа размером 32 байта и AES-256 GCM.

ПримечанияПравить

↑ ¹ ² Jutla, Charanjit S. (2000-08-01) «Encryption Modes with Almost Free Message Integrity» Архивная копия от 19 августа 2012 на Wayback Machine. Cryptology ePrint Archive: Report 2000/039. IACR. Retrieved 2013-03-16
↑ NIST Special Publication 800-38D Архивная копия от 5 августа 2011 на Wayback Machine, November, 2007, Recommendation for BlockCipher Modes of Operation:Galois/Counter Mode (GCM) and GMAC.

СсылкиПравить

OCB homepage (недоступная ссылка)
NIST homepage Архивная копия от 25 апреля 2012 на Wayback Machine
An Interface and Algorithms for Authenticated Encryption Specifies

[autogenerated1-1] ¹ ² Jutla, Charanjit S. (2000-08-01) «Encryption Modes with Almost Free Message Integrity» Архивная копия от 19 августа 2012 на Wayback Machine. Cryptology ePrint Archive: Report 2000/039. IACR. Retrieved 2013-03-16

[2] NIST Special Publication 800-38D Архивная копия от 5 августа 2011 на Wayback Machine, November, 2007, Recommendation for BlockCipher Modes of Operation:Galois/Counter Mode (GCM) and GMAC.

[1]

[2]