Reccomended deterministic encryption construction suceptible to chosen plaintext attacks

[koraa]

In that scenario, nonces can be constructed as follows: Hk(message_counter||len(ad)||ad||message), with message_counter having a fixed length.

I read that to be in it's complete form:

def AEAD_Det.enc(k, n, ad, pt):
    syn = Hk(n || len(ad) || ad || pt)
    return syn || AEAD.enc(k, syn, ad, pt)

In a chosen plaintext attack as modeled by0, the adversary gets to choose the messages; the oracle chooses one plaintext at random to encrypt. To win the game, the adversary needs to identify which of the messages was chosen for encryption.

To win the game 100% of times, the adversary can choose pt ∈ {{0}, {1}} (one and zero). For both values of pt, the value of syn can be computed by the adversary because n and ad are known to them. This fact is used to build a lookup table from syn to pt. This lookup table is valid across keys.

This can be remedied by using the encryption key during the nonce derivation step. (If you meant this all along, it should be spelled out explicitly ;) ).

def AEAD_Det.enc(k, n, ad, pt):
    syn = Hk(k, n || len(ad) || ad || pt)
    return syn || AEAD.enc(k, syn, ad, pt)

The key reuse here is probably fine, but I presume there exist examples of a secure KDF/AEAD combo that is insecure under this specific mode of key reuse. To remedy this:

def AEAD_Det.enc(k, n, ad, pt):
    k_aead, k_syn = Hk(k)
    syn = Hk(k_sym, n || len(ad) || ad || pt)
    return syn || AEAD.enc(k_aead, syn, ad, pt)

[jedisct1]

The next line says:

Hk is a secure PRF or a keyed hash function safe against length-extension attacks, such as the one provided by crypto_generichash().

But thanks for pointing out that this is confusing. I'm going to clarify that Hk is non-deterministic.

[jedisct1]

The documentation has been updated to make the key requirement more explicit. Thanks again!

You may also want to consider https://github.com/jedisct1/libsodium-xchacha20-siv as an alternative.

[koraa]

I seriously think you should just show a specific scheme in the docs and let experienced crypto alternatives substitute alternatives such as xchacha20-siv.

The version for dummies would be KDF <- HMAC-blake2b; syn <- KDF(KDF(KDF(KDF(key, 0), nonce), ad), message); syn || AEAD(KDF(key, 1), syn, ad, message).

It might be a lot of PRF invocations but at least it's secure and doesn't pull in assumptions such as the counter being fixed length. It doesn't rely on users reading top the point where it says 'non-null key' and users coming up with their own domain separation scheme or lack thereof 0.

Are there any analyses of xchacha-siv? I might be interested in using it…I am assuming the security proof will be analogous to the proof for aes-gcm-siv but has anybody done it?

[mouse07410]

Why do you assume that Blake2b, which was one of SHA-3 candidates and conforms to it's requirements, would benefit from HMAC?

[jedisct1]

What is being proposed here is in the context of libsodium and not meant to document generic constructions. crypto_generichash parameters already include a key and, for context separation, a personalization string and a salt.

I'm not aware of any analysis of xchacha-siv, but it is an instantiation of the generalised SIV proposal and the security proof is analogous to the one of AES-SIV.

[enkore]

I seriously think you should just show a specific scheme in the docs and let experienced crypto alternatives substitute alternatives such as xchacha20-siv.

The entire page feels a bit off to me (https://doc.libsodium.org/secret-key_cryptography/encrypted-messages for readers). The general thrust of libsodium is to offer a set of usable "protocols" instead of a bag of primitives to assemble protocols with (like most other crypto libraries), and that page is mostly describing how to glue stuff together from the library. The section you found in particular strikes me as something that hands a non-experienced dev just enough rope to hang themselves with.

Disclaimer: I'm having a migraine right now so I might be missing something.

[jedisct1]

Section removed.

[koraa]

Why do you assume that Blake2b, which was one of SHA-3 candidates and conforms to it's requirements, would benefit from HMAC?

blake2b is designed to be resistant to length extension attacks assumed to be secure enough for use as a KDF according to the author's paper0. I trust that assessment. Still, it is often combined with HMAC as a best practice for key derivation. E.g. in noise1 and noise based protocols such as wireguard.

The entire page feels a bit off to me

Good point!

Section removed.

Thank you!

I'm not aware of any analysis of xchacha-siv, but it is an instantiation of the generalised SIV proposal and the security proof is analogous to the one of AES-SIV.

Thank you for the reference and for the info!

[mouse07410]

Still, it is often combined with HMAC as a best practice for key derivation

It is not the best practice (for SHA-3), but a rudiment from the times of MD5. Engineers leaving understanding and afraid to touch what was "blessed" three decades ago - despite that everything changed.

Cryptographically unnecessary, and wasteful performance-wise.