Accordion: Nonce Hiding, Replay Protection, and APIs

[John Preuß Mattsson]

Hi,

Nonce hiding [1] is an interesting feature that has recently seen broad adoption in modern security protocols such as TLS 1.3 [2], DTLS 1.3 [3], and QUIC [4]. The are several potential security problems with sending nonces in the clear along with the ciphertext. If the nonce is a sequence number, this enables tracking and potentially identification of the sender and the receiver. If the nonce is a random number it might reveal information to an attacker that has backdoored the PRNG. We have not looked into how nonce hiding would affect the accodion or derived AEAD constructions, but a nonce hiding feature simplifying sequence number encryption in security protocols like DTLS 1.3 and QUIC would be welcome. It would not only simplify nonce hiding in new protocols but also enable easy nonce hiding when the AEAD is used on its own.

In TLS 1.3 [2], the nonce is implicit and not sent in the packet. In DTLS 1.3 [3] and QUIC [4], the nonce is a combination of an implicit IV not sent in the packet and an explicit sequence number sent in the package. The sequence number is DTLS 1.3 and QUIC is encrypted using a second pass with the first pass ciphertext as input.

The nonce-hiding API would need to be able to only hide the explicit part of the nonce (the sequence number). The API would also need to output the explicit part of the nonce (the sequence number) as that is not only used for decryption but also replay protection. Alternatively the nonce hiding AEAD would need to handle the replay protection similar to the AERO AEAD construction [5]. We think NIST should standardize an AERO mode based on the accordion cipher. An AERO API offers several advantages over other methods: it is simpler to use, encourages the use of replay protection, and has more compact messages. AERO can be considered a stateful and self-synchronizing authenticated encryption method that provides protection from replay attacks. The interface is:

Init(K)
C = Enc(P, A)
P = Dec(C, A)

The parameters T, W, V [5] can be part of the algorithm or part of the initialization. We have in the past seen a lot of practical and serious vulnerabilities due to weak or missing replay protection. Higher layer protocols are very often designed based on the assumption of strong replay protection in lower layers. Missing or weak replay protection in the lower layer typically compromises confidentiality, integrity, and availability at higher layers, i.e. the whole CIA triad. Many integrity algorithms are not secure without replay protection guaranteeing unique nonces in the decryption function [6-8]. Replay protection should be a mandatory requirement in all modern security protocols. Understanding of the importance of replay protection is however often severely lacking even among people working with security. It would therefore be very welcome if NIST increases its recommendations regarding replay-protection and standardizes easy to use replay protection.

Cheers,

John Preuß Mattsson

Expert Cryptographic Algorithms and Security Protocols, Ericsson Research

[1] Nonces Are Noticed: AEAD Revisited
https://eprint.iacr.org/2019/624.pdf

[2] The Transport Layer Security (TLS) Protocol Version 1.3
https://datatracker.ietf.org/doc/html/rfc8446

[3] The Datagram Transport Layer Security (DTLS) Protocol Version 1.3
https://datatracker.ietf.org/doc/rfc9147

[4] Using TLS to Secure QUIC
https://datatracker.ietf.org/doc/rfc9001

[5] “Authenticated Encryption with Replay prOtection (AERO)”
https://datatracker.ietf.org/doc/html/draft-mcgrew-aero

[6] “Universal Forgery with Birthday Paradox: Application to Blockcipher-based Message Authentication Codes and Authenticated Encryptions”
https://eprint.iacr.org/2017/653.pdf

[7] “[CFRG] Comment on AES-GCM-SST”
https://mailarchive.ietf.org/arch/msg/cfrg/51ZYKcZQDKF2RkzRFtMcH4xCy6E/

[8] Key-Recovery Attacks on Universal Hash Function based MAC Algorithms
https://www.esat.kuleuven.be/cosic/publications/article-1150.pdf