AEAD Block Encryption

AEAD modes of block encryption ( Eng. Authenticated Encryption with Associated Data , "authenticated encryption with attached data") - a class of block encryption modes in which part of the message is encrypted, part remains open, and the entire message is fully authenticated . The idea of this class of encryption was first proposed by Charanjit Jutla in 2000 ^[1] . Currently, several AEAD encryption modes are proposed: OCB mode (from version OCB2), CCM mode , EAX mode , CWC mode , and GCM mode . The last since 2007 is the NIST standard ^[2] .

Content

Issue

There are algorithms that allow authentication and encryption - authenticated encryption (hereinafter AE), but they do not provide the ability to attach plain text (associated data), which occurs, in particular, if necessary, attach an IP address to the message. In general, often unencrypted data is required to transmit headers, addresses, ports, protocol versions, and other data necessary to decide how the encrypted text should be processed or sent. Often this data must be authenticated while remaining open so that the processing devices can handle the data messages properly. There is a desire to modify the AE-scheme, adding to it an imitation insert (MAC) for authentication of open data, and "cheaply" get an AEAD-scheme. However, the obvious “naive” solutions, examples of which are discussed below, are ineffective.

Suppose, for example, you need to send a message M , an open header H , some AE encryption mode E and a MAC function are selected. Then, if we pass E (M) and H , then H will be unauthenticated. If you pass E (M || H) and H , the length of the transmitted message will be longer than the original (since the encryption operation H unnecessary in this task will be performed), the same can be said for the case of transmission H , E (M) , MAC ( H || E (M)) (since E (M) is already authenticated and using MAC requires the consumption of extra resources).

It is important that both AE schemes and AEAD schemes require the use of nonce . This is necessary to ensure semantic security (the inability of an attacker to re-establish the relationship between segments of encrypted messages under the same key when reusing the scheme), as well as to protect against a replay attack , in which the attacker, in the guise of a legitimate user, resends the message. Generating nonce and using it only once is the responsibility of the sender. For this, you can use, for example, a counter.

Implementation Methods

Encrypt-then-mac (AEAD)

There are two fundamentally different ways to implement the AEAD encryption mode. The first involves the use of block mode encryption and simulations. In this case, the developer of the AEAD-scheme can choose any block encryption algorithm and the function of receiving the imitation, while it is also necessary to use nonce. The second way is some kind of transformation of the AE scheme. The requirements for the latter method remain the same: the scheme should not slow down significantly, nor should new vulnerabilities appear in it. The security and reliability of these approaches was proved in Charanjit S. Jutla's article “Encryption Modes with Almost Free Message Integrity”, provided that nonce is not reused and the hash function H is cryptographically strong.

Methods for implementing the AEAD mode using a block cipher and imitation

There are two ways to get the AEAD mode using the block cipher and the simulator: first encrypt the message, then authenticate (encrypt-then-mac), or in reverse order (mac-then-encrypt).

Encrypt-then-mac

In this embodiment, the message M is first encrypted using nonce N, then the header H and the encrypted message are authenticated using the MAC with the same nonce.

Mac-then-encrypt

Mac-then-encrypt (AEAD)

Similar to the previous one, but in the reverse order: first, an MAC insert is created from the header H, nonce N and plaintext M, and then the message M is encrypted with the received insert using the same nonce N.

AEAD Mode Implementation Methods Using the AE Scheme

As shown above, it is impossible to attach authenticated plaintext to a message constructed using the AE scheme in primitive ways. However, the following two methods were proposed ^[1] .

Nonce stealing

Let there be an AE-scheme using nonce of size n bits, and for an application using this scheme, it is enough to use only n2 bits (n2 <n). Then free h = n - n2 bits can be used to store open data. This scheme has a limit on the size of open data, but often this is enough. Let the algorithm have 128 bits nonce and the application uses only 16, then 112 bits remain for open data, which is often quite enough (for example, 32 bits are required for an IPv4 address).

Ciphertext translation

This method of reducing an AE scheme to an AEAD scheme is based on the logical addition operation (XOR) $\oplus$ ${\ displaystyle \ oplus}$ , in this case, if an operation is performed on strings of different lengths, the shorter one is supplemented with insignificant zeros, for example: $11101001\oplus 101=11101100$ ${\ displaystyle 11101001 \ oplus 101 = 11101100}$ .

This method includes the following operations: an AE scheme is used to encrypt a message with key K and obtain an intermediate CT ciphertext, then a hash function is used $F_{K'}$ ${\ displaystyle F_ {K '}}$ to obtain the shift Δ, and finally, the final ciphertext is obtained by applying the logical addition operation Δ to the last bits of CT. Note that if the header is an empty string, the resulting AEAD scheme goes to the original AE encryption scheme. If the header remains unchanged during the session, then the shift Δ can be calculated in advance, which positively affects the encryption time - the remaining logical addition operation is easily implemented (including hardware).

We define the resulting AEAD scheme more strictly as follows:

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

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

That is, assuming that $H\neq 0$ ${\ displaystyle H \ neq 0}$ calculate $F_{K'}(H)=$ ${\ displaystyle F_ {K '} (H) =}$ Δ with a length of τ bits, encrypt M and perform the operation of logical addition of the last τ bits with Δ.

This method has the following advantages:

applicable to any AE scheme;
if you do not need to attach unencrypted data H, the original AE method is not complicated;
if the heading H does not change over time, $F_{K'}(H)$ ${\ displaystyle F_ {K '} (H)}$ can be pre-calculated.

However, the disadvantage of this method is the need to use two keys K and K '.

AEAD Algorithms

For example, we describe some AEAD algorithms. Two of them are based on AES GCM, two of them are based on AES CCM. One of the algorithms in each pair uses a 128-bit key, the other uses 256-bit.

AEAD AES 128 GCM

This algorithm uses AES-128 as a block cipher algorithm, using key, nonce, message and header as input. The length of the header is 16 bytes. The ciphertext is generated by adding an authentication tag to the intermediate ciphertext received as the output of the GCM encryption. The requirements for input and output data sizes are as follows:

nonce size - 12 bytes;
key length - 16 bytes;
maximum message size $2^{36}$ ${\ displaystyle 2 ^ {36}}$ - 31 bytes;
maximum header size $2^{61}$ ${\ displaystyle 2 ^ {61}}$ - 1 byte;
maximum encrypted message size $2^{36}$ ${\ displaystyle 2 ^ {36}}$ - 15 bytes.

Thus, the ciphertext is 16 bytes longer than the original open message.

AEAD AES 256 GCM

The algorithm is completely similar to the previous one, except for the use of a 32-byte key and AES-256 GCM.

AEAD AES 128 CCM

Similar to the previous, except for using CCM mode instead of GCM, with:

nonce size 12 bytes;
key length 16 bytes;
maximum message size $2^{24}$ ${\ displaystyle 2 ^ {24}}$ - 1 byte;
maximum header size $2^{64}$ ${\ displaystyle 2 ^ {64}}$ - 1 byte;
maximum encrypted message size $2^{24}$ ${\ displaystyle 2 ^ {24}}$ + 15 bytes.

As with GCM, the ciphertext is 16 bytes longer than the original message.

AEAD AES 256 CCM