Related-key attacks security?

[jedisct1]

Is RKA security something we may want to include in the security properties?

Relevant paper: https://eprint.iacr.org/2022/140

[jedisct1]

An example AEAD that provides RKA security is the SPONGEWRAP construction, as proven in https://link.springer.com/chapter/10.1007/978-981-99-8742-9_8

[AndAlBo]

This is an interesting property. I considered adding it in the earliest version of the draft, but don't remember why I didn't =) I will consider including it in the next version since I want to publish the current one today for the RG to start reviewing.

[yt-nakano]

This property is indeed interesting but not many algorithms claim the related key security. Do you have suggestions for a scenario where this threat can be practical and the example algorithms which claim related-key security? The SpongeWrap construction, on which Ascon is based, is proven to be secure against related-key attack but it is not claimed in https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8454.pdf or https://competitions.cr.yp.to/round3/asconv12.pdf. All TLS 1.3 cipher suite algorithms (AES-GCM, AES-CCM and ChaCha20-Poly1305) do not explicitly claim either.

[jedisct1]

For TLS, it doesn't matter much because TLS keys are HKDF outputs, so they are assumed to be uniformly sampled.

But it wouldn't be far fetched to imagine that some applications design their own key format, such as <secret> || <customer id>, especially with a 256-bit key space. Using a KDF would be the sane thing to do, but RKA falls in the "misuse-resistance" category.

[yt-nakano]

Thank you for clarifying the scenario. Then how about merging the RKA and nonce misuse into misuse-resistance, and putting a NOTE to mention the importance of the key generation?

[jedisct1]

https://eprint.iacr.org/2022/140.pdf cites a couple scenarios.

• Device-related keys ("Rather than generating a fresh key for each device, it derives the key from the master key and some device id – for instance XORing the two") - This is the same scenario as the above one, and falls in the misuse category.
• Key updates. Sure, if K'=H(K), there's a relation between these keys. Or, as recently analyzed in TLS, the keys can been seen as the output of a stream cipher. Still, outside misuse ("bad key updates"), I can't think of any scenarios where that could be exploited.
• Partial key leaks (side channels, fault attacks). That one is more interesting and does not fall in the misuse category, rather in the leakage-resistance category.

[AndAlBo]

Frank, and Yuto, thank you for the discussion!

There are two main reasons I didn’t add it before:

1. RKA security is generally discussed in the context of primitives. Primitive-based AEADs usually provide RKA security if the primitive is RKA secure. However, since some AEADs are primitives themselves, it might be relevant.

2. RKA security is only achievable for restricted families of related-key functions. For ideal ciphers, collision-resistant and output-unpredictable function families are the target [BK03]. At the same time, proving the security of real-life constructions without IC or RO assumptions, even for some simple families is challenging. Additionally, cryptanalysis usually only considers some particular small families. However, something similar can be said about leakage resistance as well.

But it wouldn't be far fetched to imagine that some applications design their own key format ... RKA falls in the "misuse-resistance" category

I really like that argument. Overall, I agree it would be beneficial to add it, with some notes on item 2 from my list.

Then how about merging the RKA and nonce misuse into misuse-resistance, and putting a NOTE to mention the importance of the key generation?

It might be a little confusing for a reader since these two properties are well-known and usually studied separately. However, putting such a note in the RKA security section is a nice idea.

[AndAlBo]

https://eprint.iacr.org/2022/140.pdf cites a couple scenarios.

Thanks!