2 in 1: encryption with security protection

The classic tasks that are solved by cryptographic methods are to ensure confidentiality and ensure the authenticity / immitability of stored and transmitted data. Earlier (until about the mid-2000s), encryption (confidentiality) and the functions of generating an insert / authentication code (imitation resistance) were used to solve such problems. At the same time, the encryption and the function of generating the insert were implemented by separate cryptographic mechanisms, which caused a lot of problems. First of all, this is related to the management of key information: when using one key for encryption and security, a number of schemes, for example, AES-CBC + AES-CBC-MAC, are completely unstable. In order to make such constructions safe, it is necessary to generate additional keys using, for example, the derivative key generation functions (KDF). This, in turn, leads to a significant complication of cryptographic protocols using similar schemes. In addition, the consistent use of two mechanisms is not always the fastest solution in terms of performance.

Since the beginning of the 21st century, attempts have begun to create encryption mechanisms with imitation protection (sometimes the term “authenticated encryption” can be found from the English Authenticated Encryption), which would solve both of these tasks at once.

The next stage in the development of such mechanisms can be considered encryption mechanisms with security and associated data (from the English. AEAD - Authenticated Encryption with Associated Data). A feature of AEAD mechanisms is that they can simultaneously process two types of data: data for which it is necessary to ensure confidentiality and security (for example, IP packet data), and data for which it is necessary to ensure only security without privacy - they are also called " additionally protected data ”(“ associated data ”,“ additionally authenticated data ”- this may be the IP packet header). One of the most popular applications for AEAD mechanisms is various cryptographic data protection protocols, for example, the recently adopted IETF TLS 1.3 RFC 8446about what already wrote on Habré . So, this RFC 8446 considers authenticated encryption algorithms used in the protocol (you can read about the principles underlying the TLS 1.3 protocol here ).

AEAD mechanisms can be built on the basis of various designs: stream and block ciphers, compression mappings (hash functions), now popular constructions of the “sponge” type (from the English “sponge”). A variety of options can be seen, in particular, on the CAESAR competition website and in various reviews about this competition, see for example here and here. By the way, the contest itself was organized in 2013 just to determine the best AEAD mechanism instead of the widely used AES-GCM (GCM mode was standardized by NIST in 2007), for which at that time a number of attacks were proposed ( here and there ). At the same time, additional functional requirements were presented to the CAESAR contestants, such as the ability to work “online”, the possibility of parallelization, freedom from inversions, protection against incorrect use of initialization and one-time vectors, the presence of precalculations, data incrementation, intermediate simulations, reuse of fixed associated data. We explain in more detail.

Work "online": often in order to ensure confidentiality / imitation resistance, it is first necessary to form completely the entire data packet that will be processed, and only then begin the processing procedure. Mechanisms that allow the operation of "online" do not require this; they can work with the incoming real-time data stream, processing it "on the fly." By parallelizing AEAD mechanisms, we mean the possibility of distributing computing between several processors. Freedom from inversions means the use in the AEAD mechanism of only the encryption function or only the decryption function. This characteristic is important from the point of view of implementation: for some ciphers (such as Grasshopper, AES), encryption and decryption are implemented using different transformations, respectively,freedom from inversions means a smaller chip area in hardware implementations or less software in software. With precomputations, everything is simple - this is an opportunity, after choosing a key, to carry out a number of preliminary calculations that will further accelerate the processing of incoming data.

The increment of data and the reuse of fixed associated data in a sense can also be attributed to precalculations. By incrementation is meant the ability to quickly recalculate the insert, in the event that we have added some additional data to the already processed data, without re-processing all the data. The use of fixed associated data is the ability to perform precomputations for frequently encountered data so that each time they appear, they are not processed again. The last property (intermediate imitation inserts) is, in a sense, also work "on the fly", i.e. the ability to verify on the receiving side the correctness of the data during processing, without waiting for the end of the transfer. Thus, if the verification of the intermediate simulation insert fails,all subsequent data stream does not need to be processed, and this saves time and resources.

As it turned out, creating an AEAD mechanism that simultaneously satisfies such a wide range of requirements is extremely difficult. This led to the CAESAR contest being repeatedly prolonged, deadlines being postponed because the jury could not choose a winner - all participants had different sets of properties - and the competition ended only in the spring of 2019 by selecting several participants with different properties.

The prototype of the domestic AEAD mode, later called MGM (Multi Linear Galois Mode), was first introducedin 2017, MGM is a block cipher mode of operation. The mode consists of two parts, each of which is based on its own counter. The first counter is used to generate a sequence, which is then used for encryption. The principle of operation is similar to the counter of the CTR mode (see GOST R 34.13-2015 or ISO / IEC 10116), but it has a significant difference: the initial value of the counter is obtained using encryption from a unique initialization vector (nonce). The second counter is used to build a multilinear function, on the basis of which an imitation insert is generated. The first and second counters work differently, the first increments the right half of the block, and the second increments the left. The mode of operation is shown in the figure.



Here$$$E_k$ - arbitrary block cipher with block length$$$n$ bits$$$A_1,...,A_h^*$ are blocks of associated data,$$$P_1,...,P_q^*$ are blocks of plaintext,$$$nonce$ - unique length initialization vector$$$n-1$ bit$$$\oplus$ - operation of bitwise addition,$$$\otimes$ - operation of multiplication in the field$$$GF(2^{128})$ ,$$$MSB_S$ - truncation of a block of length to length$$$S$ ,$$$len(A)||len(C)$ is the bit length of the associated data and ciphertext, respectively,$$$inc_r,inc_l$ - increment functions.

In thereportand in thearticle,you can find a detailed description of the principles of building the MGM mode. In short, the following problem was solved during development: to create a functional and well-parallelized mode of operation for block ciphers that would not be susceptible to known attacks, in particular, attacks successfully applied to the GCM mode. The following features of the mode are shown in the mentioned report:

• ,
• ,
• ,
• (.. , MGM ),
• ,
• ( ()),
• .

Unlike many of the currently used modes, MGM managed to obtain a formal justification of durability in the model of the so-called provable security , which can be summarized in the form of two theorems that evaluate the safe number of plaintext blocks that can be processed using the mode MGM without key change. We regret the readers and give here only their wording, those who want to see the full proof and to thoroughly melt the brains can refer to the original publication. The first theorem says about ensuring the confidentiality of information.


The second is about the security of data authentication (its imitation resistance).


Note that when using the “provable persistence” approach, the question always arises of the accuracy of the estimates obtained (that is, how much they actually correspond to reality and are adequate to practice). So in this case, they turned out to be accurate, which confirmed the results of a work in which theoretical attacks for the MGM mode are indicated if the volume of material does not satisfy the above theorems.

The table below presents a comparison of the developed regime with the finalists of the CAESAR contest according to the above characteristics.



In the table, BC - block cipher, SC - stream cipher, Dedic - original design (does not use the cipher), Sponge - uses a sponge, are indicated as the primitive used.

As you can see, it was possible to develop a regime that satisfies a sufficiently large set of operational requirements, and, which is extremely important, to obtain a formal justification for its durability.

In September last year, Rosstandart approved the MGM regime in recommendations for standardization R 1323565.1.026–2019 “Information technology. Cryptographic information security. Block cipher modes that implement authenticated encryption . ” In addition, at the beginning of this year, the IANA organization allocated identifiers , and Rosstandart adopted recommendations for standardization of R 1323565.1.030-2020 “Information technology. Cryptographic information security. The use of cryptographic algorithms in the transport layer security protocol (TLS 1.3) " to use Russian cryptographic algorithms in the TLS 1.3 protocol, - and just using the MGM mode.