Re: [CFRG] HPKE and Key Wrapping

[John Mattsson <[e-mail]>]

Hi Chris,

I think the model in [1] does not map directly to HPKE as [1] discusses a deterministic one-layer symmetric key wrap method and HPKE is a randomized two-layer asymmetric key wrap method. As stated in [1] "So key-wrap’s raison d’ˆetre is to remove AE’s reliance on a nonce or random bits" and by NIST [2] "consideration of additional circumstances (e.g., resilience to operator error, low-quality random number generators)". My high-level summary of the key wrap attack model would be that the attacker can control all inputs but that the attacker does not know the outer secret key used in the key wrap.

- The input to AES-SIV used for key wrap would be:

ct = SIV-ENCRYPT(key, aad, pt)
pt = SIV-DECRYPT(key, aad, ct)

where pt is the key to be wrapped. Nonce and random bits are not even taken as input. This construction is secure under the assumption that the attacker does not know “key”.

- The input to RSAES-OAEP + AES-KWP [3] is

ct = RSAES-OAEP+AES-KWP-encrypt(pkR, random bits, pt)
pt = RSAES-OAEP+AES-KWP-dencrypt(skR, ct)

where “random bits” are used to generate the mask. My understanding is that this construction is secure under the assumption that the attacker does not know skR.

- The input to single-shot HPKE used for key wrap would be

ct = HPKE-single-shot-encrypt(pkR, random bits, aad, pt)
pt = HPKE-single-shot-decrypt(skR, aad, ct)

where “random bits” are used in GenerateKeyPair(). With AES-GCM this is not secure at all under the assumption that the attacker controls “random bits”. With AES-SIV I think the construction is secure under the same assumption.

Unless necessary, I would be very hesitant to move to a key wrap mechanism that relies heavily on the trust in the random number generator. Using AES-GCM might be ok for key transport in some circumstances, but I would like to also see a HPKE key wrap mode that removes the reliance on “random bits”.

Cheers,
John

[1] https://www.iacr.org/archive/eurocrypt2006/40040377/40040377.pdf
[2] https://en.wikipedia.org/wiki/Key_wrap
[3] https://cloud.google.com/kms/docs/key-wrapping

From: Christopher Wood <[e-mail]>
Date: Wednesday, 30 March 2022 at 17:18
To: John Mattsson <[e-mail]>
Cc: Taylor R Campbell <[e-mail]>, IRTF CFRG <[e-mail]>
Subject: Re: [CFRG] HPKE and Key Wrapping
Apologies if I’m misunderstanding something here, but this threat model seems somewhat convoluted. In particular, it assumes an adversary that controls the RNG, and therefore key schedule state as well. The AEAD key and nonce are both derived from this state. However, the DAE security model from [1] assumes the attacker controls the message header and message itself, but not the key. (For MRAE, it assumes the attacker also controls the nonce/IV.) So it’s not clear to me why SIV or similar modes would offer meaningful improvements over the existing HPKE AEADs under the assumption that the attacker controls the nonce and key. Can someone help clarify what I’m missing?

Thanks,
Chris

[1] https://web.cs.ucdavis.edu/~rogaway/papers/keywrap.html

> On Mar 30, 2022, at 4:46 AM, John Mattsson <john.mattsson=[e-mail]> wrote:
>
> Thanks Taylor!
>
> Then it seems to me that AES-256-SIV and AES-512-SIV are the AES-based modes that should be added to HPKE to enable key wrapping security independent of the RNG. These are exactly the two AEADs suggested by draft-harkins-cfrg-dnhpke-01. Key wrapping mechanisms have in the past aimed to provide security even in the case of compromised RNG but it would be interesting to hear if someone think that property is needed in this case.
>
> Cheers,
> John
>
> From: Taylor R Campbell <[e-mail]> on behalf of Taylor R Campbell <[e-mail]>
> Date: Wednesday, 30 March 2022 at 12:29
> To: John Mattsson <[e-mail]>
> Cc: Dan Harkins <[e-mail]>, IRTF CFRG <[e-mail]>
> Subject: Re: [CFRG] HPKE and Key Wrapping
>
> > Date: Wed, 30 Mar 2022 08:51:44 +0000
> > From: John Mattsson <john.mattsson=[e-mail]>
> >
> > How does AES-SIV (RFC 5297) compare with AES-GCM-SIV (RFC 8452)? Do
> > we need both algorithms in the future? Does AES-GCM-SIV with a fixed
> > nonce provide the same properties as nonce-less AES-SIV or is there
> > a difference?
>
> There is a fairly substantial difference.  In the Daence paper I drew
> a table of advantage bounds for AES-SIV and AES-GCM-SIV, using the
> best formulae I could find (with the function/permutation-switching
> lemma of https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-a129ecc550c2c3ad&q=1&e=117ce771-01cf-4d9c-aa89-a8b4b42eab86&u=https%3A%2F%2Fcr.yp.to%2Fpapers.html%23permutations that gives better
> bounds than the conventional q*(q - 1)/2 used in most papers):
>
> https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-fc96309953b1fcfb&q=1&e=117ce771-01cf-4d9c-aa89-a8b4b42eab86&u=https%3A%2F%2Feprint.iacr.org%2F2020%2F067.pdf%23page%3D5
>
> Smaller advantage bounds, i.e., larger values of n in the 2^-n terms,
> are better.  1 means no advantage bound has been proven at all for
> these parameters.
>
> This table was computed using the logic at
>
> https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-ab6fc8eec24511fa&q=1&e=117ce771-01cf-4d9c-aa89-a8b4b42eab86&u=https%3A%2F%2Fgithub.com%2Friastradh%2Fdaence%2Fblob%2Fmaster%2Fadv.py
>
> which cites the sources in the literature I used for the formulae.
> You can reuse the same logic to recompute bounds for different message
> sizes/numbers if what you're looking for isn't in the table, of
> course.
>
> It may be worth noting that the security advertisment in RFC 8452 for
> AES-GCM-SIV explicitly discourages nonce reuse even between different
> users (different keys), which means you should even avoid the policy
> of sequential message numbers that, e.g., TLS 1.3 uses with AES-GCM to
> rule out a class of attacks:
>
> https://datatracker.ietf.org/doc/html/rfc8452#page-12
>
> The bottom line is that AES-GCM-SIV is designed for randomized nonces,
> with some level of protection if your RNG fails.  In contrast, AES-SIV
> is designed for security without nonces at all, and is particularly
> well-suited to key-wrap, which should come as no surprise since that's
> what it was designed for originally, as sung in Appendix F of:
>
> https://web.cs.ucdavis.edu/~rogaway/papers/keywrap.html
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-40f7d10cf9eb7c69&q=1&e=4d15d9d4-caaf-4057-bff5-ccea9b384b51&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg