[Cfrg] Review of draft-irtf-cfrg-re-keying-08

[Yaron Sheffer <[e-mail]>]

Summary

I think the document is not ready to be published yet, for the following reasons:

First, it is very heavy reading, with important details buried between mountains of pseudo-code and analysis. I would recommend to add a 2-page summary at the top of the document, describing the proposed solutions and their applicability. Maybe Sec. 4 could be tweaked into this form if you added forward references to the specific proposed mechanisms, but then the section would still be very long.

Second, this document is a problematic hybrid of common techniques for "external" re-keying, and original cryptography for "internal" re-keying (where a reference to the work/proof is definitely needed). Readers who approach the document expecting a survey because of the very generic title will be surprised. Assuming this is intended to be a survey of related techniques, references to the literature are needed, and I would expect additional techniques to be mentioned, even if briefly.

Lastly, I would expect more clarity on the interaction of the re-keying mechanisms with security protocols and operating systems. Security protocols and operating systems both allow to refresh keys with new entropy. In addition, HSMs (and related technologies, such as security enclaves) can help to achieve better forward secrecy using asymmetric cryptography than the techniques described here. I would also suggest to mention another important use case for symmetric key re-keying: encryption of data at rest.

Please note that this document includes original cryptography, and, not being a cryptographer, I am unable to comment on its security.

This review was written at the request of the CFRG Crypto Panel. I have benefited from a lengthy discussion with the draft's author, Stanislav Smyshlyaev, and I would like to thank him for that.

Details

* Abstract: you use the terms "internal" and "external" which are neither defined here nor very common, so I don't think they belong in the abstract.
* "Key lifetime" often means something else, the actual time (e.g. months) after which the user is procedurally obliged to replace a key. So let's say that this is/our/definition of the term.
* 2^(n/2) where n is?
* "the total size of the processed plaintext" - often the limitation is on the number of encryptions (e.g. number of packets encrypted) rather than total size, e.g. because of nonce reuse. And this is the exact opposite of the rectangle analogy, which implies that the fixed value is the total number.
* Introduction: please mention if these solutions also apply to encryption of data at rest, in addition to network protocols.
* Also, your threat model does not include what is possibly the most important threat for many Internet-connected systems: a time-limited but complete breach of the system. If these approaches are useless under this threat and only external renegotiation with forward secrecy is effective, fine, but we should say so.
* Introduction: I suggest that you mention who is the target audience: protocol developers? Implementers? Are there cases where these mechanisms can be used with no protocol-level changes and therefore can be used directly by implementers?
* Basic Terms: for some of these definitions, an informal explanation would help. E.g. Int_s is the interpretation of the string as a binary integer.
* Terms: "section" is a strange name, but I don't have a better alternative.
* "For protocols which allow out-of-order delivery and lost records" - these protocols typically include a sequence number which can be used for internal rekeying.
* The "summing up" section includes several assertions that have not been explained yet at this point, e.g. about tree-based, hash-based re-keying.
* Serial (external) constructions: it is unclear to me what are the use cases where the serial mechanisms may be preferred.
* While a proof does not belong in an RFC, the document should referencehttps://eprint.iacr.org/2017/697.pdf  which contains security proofs, at least for some variants of ACPKM.
* 6.2.1: you lost me in the arithmetic. Are we assuming a certain block size for the cipher here?
* "It allows to prevent collisions of block cipher permutation inputs in cases of key transformation and message processing" - this text is extremely opaque.
* 6.2.3: as far as I remember, GCM is defined even when the last block is not a multiple of 16 bytes. So I think this mode should also handle this case. At least GHASH appears not to do that. And I think the same applies to the CTR mode above.
* I'm not sure I understand the notion of a "master key" in this context, and maybe it is not explained well. ISTM that the difference between ACPKM and ACPKM-Master is that one is serial (K is used for the first section, and then repeatedly processed to produce a sequence of keys) whereas the other one is "parallel", and does not use K directly. But K is obtained the same way from the network protocol, so it doesn't make sense to me to call it "master key" only in the parallel case.