The long journey from RFC 4357 to RFC 8645 or how to manage encryption keys

As you know, key management is one of the most difficult tasks in cryptography. Just the other day, the document “Re-keying Mechanisms for Symmetric Keys” was published as RFC 8645 . It is the result of two and a half years of work of the CFRG research group, which determines the development and use of cryptography in the IETF, and it was based on many years of research and the experience of Russian specialists. Next, we briefly describe what the essence of this RFC is and why it turned out to be just that.

A little scare ...

In 2016, two French researchers from the Inria Institute published a description of the Sweet32 attack. The idea they used is obscenely simple and based on the so-called "birthday problem" : if we calculate the values ​​of a random mapping $$$f: V_n \ rightarrow V_n$ then in about $$$2 ^ {n / 2}$ tests in the resulting sequence at least two values ​​coincide. From the point of view of cryptography, this means that a block cipher with a block length $$$n$ bit cannot be encrypted on one key anymore $$$2 ^ {n / 2}$ plaintext blocks.







This attack was already considered in detail on Habré ; here we only note that the authors took advantage of the fact that some widely used cryptographic libraries did not change the session key on time. This allowed us to accumulate a lot of data and simply use the specified probabilistic property if the connection used a block cipher with a block length of 64 bits. This immediately gave rise to a serious hysteria in the near-cryptographic environment regarding the need for an urgent rejection of such ciphers.

But is it the length of the block?

Indeed, is it worth ostracizing a cipher just because it has a short block length: what if you change the key periodically? This can be done using the so-called key derivation function ( KDF ). Such functions allow you to get new keys based on old ones, while preserving the randomness property of keys (see, for example, this article ). Such functions, for example, are determined by the Russian standardization recommendations P 1323565.1.022-2018 and P 50.1.113-2016 . However, there is one “but”: these are quite complex and not very fast conversions, built on the basis of hash functions, which will significantly slow down the encryption speed.

Is it possible to do something faster?

Such an attempt was made in 2006 at RFC 4357 , where the CryptoPro Key Meshing mechanism was proposed, which produces a derivative key by encrypting a fixed constant with a block cipher in a simple replacement mode.







It was a very fast algorithm, with practically no effect on the encryption speed and protecting against such ridiculous situations as those used in Sweet32, and also, for example, against attacks on side channels. However, at the 2015 Ruscrypto conference, it was shown that such a transformation reduces the power of the key set, i.e. with each new key change, the number of its possible key selection options decreases. The author noted that this did not have any significant impact on security, but nevertheless it became interesting whether it could be done even better.

It turned out not so simple

Unfortunately, there are no miracles, and it is not possible to offer a fast mechanism comparable to conventional KDFs, however, we can prove the safety of several modified schemes like the specified Key Meshing for each specific encryption mode. It is these mechanisms that were proposed and justified for the widely used CTR gamma mode (CTR-ACPKM, Advance Cryptographic Prolongation of Key Material) and the development of the OMAC simulation insert (OMAC-ACPKM) from the domestic standard GOST R 34.13-2015.



Safety ratings for these modes are obtained using the so-called apparatus. "Provable durability . "



These modes were adopted in Russia as recommendations for standardization of R 1323565.1.017-2018 .



It is this way of working with keys that allows crypto tools that implement the Russian TLS 1.2 crypto sets (defined in the standardization recommendations R 1323565.1.020-2018 ) to meet Russian cryptographic protection requirements for high classes.

Work at the IETF

The developed mechanisms perfectly suited as an answer to the discussion mentioned at the beginning of the article about whether there should be ciphers with a short block length or not.



The development of the corresponding document, which later became RFC 8645, was commissioned by CFRG chairmen Kenny Paterson and Alexei Melnikov by an international group of experts led by Stanislav Smyshlyaev. Contribution to the development of the final document was made by Evgeny Alekseev, Ekaterina Smyshlyaeva and Lilia Akhmetzyanova (CryptoPro), Shay Gueron (University of Haifa), Daniel Fox Franke (Akamai Technologies), as well as IETF former head Russ House (Vigil Security); at various stages, such major specialists as Mihir Bellare (University of California), Scott Flurer (Cisco), Joav Nir (Checkpoint), Dmitry Belyavsky (Cryptocom) and Paul Hoffman (ICANN) joined the work.



Compared with the Russian recommendations, ACPKM mechanisms have been added to this RFC for such modes as CBC, CFB and GCM, which, as you probably already understood, required separate evidence.

Summary

As already noted, despite the fact that the proposed approach is in some ways not universal and requires separate security justifications for each individual regime, we reward high speed, security from attacks like Sweet32 and, not least, attacks from side channels.