Accordion: MRAE, DAE, Key wrap, and RAE

[John Preuß Mattsson]

Hi,

I strongly agree with NIST that “if the AEAD takes a nonce as one of the inputs, then nonce-misuse resistance is an important property”. As NIST writes, nonce-resistance follows from the definition of the accordion mode as long as the nonce is encoded as part of the tweak. I assume the exact property is Misuse-Resistant AE (MRAE) security [1]. I think MRAE security should be a priotized goal.

Another property that seems to also follow from the definition of the accordion is Robust Authenticated Encryption (RAE) [2].  REA is described in [3] as “being able to find one or more forgeries should not increase the adversary’s ability to make further forgeries”. This seems like a very good property to have and I think it should be a prioritized goal.

In Section 3.3, NIST described Deterministic Authenticated Encryption (DAE) as a derived function. I am not sure that a DEA mode is needed or even desired. The key-wrap problem as described in [1][4] is to provide confidentiality and integrity protection without the use of nonces and without relying on strong random number generators. A key wrap encryption function KW(K, P) takes as input a key and a plaintext and outputs a ciphertext. One solution to the key wrapping problem is deterministic authenticated-encryption (DAE). It is often stated in key wrap literature that DAE is OK since the plaintext (key), is random, but this is not true as encrypting the same key several times (which is very common) leaks significant information to an attacker.

Now that NIST is standardizing misuse-resistant AE, I don’t think DEA is needed anymore. A better solution to the key wrapping problem using the same interface is to build a hedged key wrap encryption function as a derived function of a Misuse-Resistant AE (MRAE) encryption function:

Hedged-KW(K, P):

  1. Let N be a random nonce. Let A be the empty string.

  2. C’ = MRAE(K, N, P, A)

  3. Return C = N || C’

This provides strictly better security properties than DAE at the expense of slightly more message expansion. Even with a very bad random number generator (RNG), this hedged construction gives IND-CCA2 security with DAE security as a worst case. The addition of randomness likely also increases security against side-channel attacks and fault attacks. While not basing security on a strong RNG is a requirement to key wrap, we don’t think determinism is a requirement, it just happened to be a feature of the solutions. Hedged key wrap might also be implemented with a nonce-hiding MRAE. We think NIST should specify an accordion-based MRAE instead of a DAE. If a dedicated key wrap function is needed, we think the Hedged-KW described above is preferred over a DAE.

Also for key wrap it would be good if the key wrap algorithm optionally allows the user to specify the amount of padding to hide the length of the key.
https://groups.google.com/a/list.nist.gov/g/ciphermodes-forum/c/63sK8oIl674

Cheers,

John Preuß Mattsson

Expert Cryptographic Algorithms and Security Protocols, Ericsson Research

[1] “Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem”
https://eprint.iacr.org/2006/221.pdf

[2] “Robust Authenticated-Encryption AEZ and the Problem that it Solves”
https://eprint.iacr.org/2014/793.pdf

[3] “Tweakable Ciphers: Constructions and Applications”
https://pdxscholar.library.pdx.edu/cgi/viewcontent.cgi?article=3489&context=open_access_etds

[4] “Request for Review of Key Wrap Algorithms”
https://eprint.iacr.org/2004/340.pdf