Strengthening crypto_box_seal

[thaidn]

Hi!

I'm working on https://github.com/google/tink. We want Tink to be compatible with libsodium as much as possible, but we ran into a couple of issues that we want to bring to your attention.

libsodium's crypto_box_seal provides what we call hybrid encryption. The format of a sealed box is

ephemeral_pk ‖ box(m, recipient_pk, ephemeral_sk, nonce=blake2b(ephemeral_pk ‖ recipient_pk))

where box could be ChaCha20Poly1305.

There are two things that we don't like about this format:

• It is using Blake2b. This hash function hasn't got enough analysis and is weaker than Blake. We agree that Blake2b is faster, but we're not sure the speed of the hash function matters much in this context.

• Instead of generating a random nonce, it is using a nonce derived from the ephemeral public key and the recipient public key. This is dangerous because if users ever reuse ephemeral keys they immediately lose confidentiality (and maybe integrity too). Of course users should not reuse ephemeral keys, but we believe APIs should be fail-safe.

A couple of things that we want to discuss with the libsodium team:

1/ How's about Blake512(x25519_shared_secret || ephemeral_public_key)?

Perhaps let's forget about Blake and just use HKDF with HMAC-SHA256, like we did with EciesAeadHkdfHybridEncrypt. What I don’t like about HKDF is that it needs salt and info, which could be confusing. Some users might also prefer Blake to anything made by the NSA.

Should recipient_public_key be added as an input to the KDF? I don’t see any security issues with or without it, I prefer not adding for simplicity sake, but I can be convinced otherwise.

2/ Should the input to the KDF include a context_info? I think yes because it helps bind the encryption to some context. Overall the input to the KDF should look like as follows

x25519_shared_secret || ephemeral_public_key || context_info

3/ We're thinking about writing an RFC that defines how to do hybrid encryption with X25519 and AEAD.

This would take some work but it’d hopefully foster interoperability. Are you interested in working with us on this?

Thank you!

[mimoo]

For issue 1, there is also SHAKE (or cSHAKE) if you want to use one function instead of three (HKDF+HMAC+SHA-256). It's also a NIST standard.

[jedisct1]

Hi,

While BLAKE predates BLAKE2, it hasn't received much adoption. BLAKE2 has many implementations in all languages, and is probably the most popular hash function today after MD5, SHA1 and SHA2, at least in opensource projects. It relies on the same core as BLAKE, has been reused in other constructions such as Argon2, and overall, BLAKE2 is very likely to have received more scrutiny than the original BLAKE.
Even if speed is not a concern in this particular use case, replacing BLAKE2 with BLAKE would only be a barrier to adoption.

As suggested by David, in the context of a standard, SHAKE/cSHAKE may be a better alternative.

Random nonces were initially considered. However, in virtually all applications, the same PRNG would be used to generate these nonces and ephemeral keys. If it generates nothing but a stream of zeros, using it for the nonces would not help.

Synthetic nonces, including the message itself, would be safe against reused ephemeral keys. This is not free, though, and it would be incompatible with a streaming API.

Following NaCl, libsodium assumes that the PRNG can be trusted. In this context, a random nonce would not have any practical benefits over deterministic nonces.

Since the target is different, libhydrogen assumes the exact opposite. But libsodium's plan is to keep misuse-resistance (or rather broken PRNG-resistance) optional, and provide a generic API to derive a subkey and a nonce from a master key, a message and a context, in order to support broken PRNG-resistance when required.

Contexts are useful when a key could be reused for different purposes. If keys are assumed to be unique, they don't have much value.

But the API plays an important role here. crypto_box_seal() does not allow applications to provide the ephemeral key pair. The function is responsible for generating it. If we assume that the PRNG can be trusted, a context is thus not needed. If we don't assume that the PRNG can be trusted, the context can be useful. But in libsodium's case, it will be part of the generic subkey/synthetic nonce API.

An RFC defining how to do hybrid encryption with X25519 + ChaCha20Poly1305 could be very useful, if only for interoperability purposes, and I'd be glad to work with you on this.

crypto_box_seal() construction in libsodium cannot be changed at this point. There are reimplementations in other languages and libraries, and it is already used by quite a few applications. An additional API would not be a problem, though.

[trevp]

Hi all,

if you're not constrained by compatibility the Noise framework is an option. Either of these would do what you want (including HKDF):

Noise_N_25519_ChaChaPoly_BLAKE2s
Noise_N_25519_ChaChaPoly_SHA256

https://noiseprotocol.org/