Random Oracle Requirements for AKE

[daxpedda]

During #404 a question came up on why a random oracle is required for the NIST and Ristretto ciphersuites but not for Curve25519: #404 (comment).

Currently NIST and Ristretto use the OPRF DeriveKeyPair function: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-voprf-21#name-deterministic-key-generatio. Which is more complicated and also compute intensive then simply using the NIST ECDSA Key Pair Generation by Rejection Sampling.

As far as I can tell, if HashToScalar can be dropped in key generation for the AKE without any security concerns, it would be an overall gain for the specification; reducing complexity and computational requirements.

[kevinlewi]

@chris-wood ^

[OR13]

I don't think you need a kdf for curve25519, but how people get to the seed matters.

You might look at BIP44 and BIP39 and see if there is anything relevant.

[kevinlewi]

Chiming in here -- I also don't think we need to KDF the input seed

Note that the input is already presumed to be a (pseudo)-random output:

seed = Expand(randomized_password, concat(envelope.nonce, "PrivateKey"), Nseed)
(client_private_key, client_public_key) = DeriveDiffieHellmanKeyPair(seed)

I recommend we close this issue without changing anything.

[daxpedda]

I think there might be a misunderstand here, my suggestions is to not use KDF for the input seed.

Specifically we currently do not use DeriveKeyPair for Curve25519. I want to extend not using DeriveKeyPair for the other curves as well.

[kevinlewi]

I think there might be a misunderstand here, my suggestions is to not use KDF for the input seed.

Specifically we currently do not use DeriveKeyPair for Curve25519. I want to extend not using DeriveKeyPair for the other curves as well.

Oh, thanks for the clarification! I think the original message got lost a bit after a small game of telephone, and I perpetrated that, sorry :)

I think we should continue using DeriveKeyPair for the other curves as well. Curve25519 is an exception because you can take a random bytestring and interpret it as a scalar, safely (well, you have to do the Curve25519 clamping operations, but those are efficient and constant-time).

However, ristretto255 and P-256 do need to do HashToScalar in order to be considered secure, and this is done in VOPRF. The VOPRF draft also references the hash-to-curve draft about this, from https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#name-hashing-to-a-finite-field:

Implementors MUST NOT use rejection sampling to generate a uniformly random element of F, to ensure that the hash_to_field function is amenable to constant-time implementation. The reason is that rejection sampling procedures are difficult to implement in constant time, and later well-meaning "optimizations" may silently render an implementation non constant-time. This means that any hash_to_field function based on rejection sampling would be incompatible with constant-time implementation.

So, I believe curve25519 is a unique beast in that respect. But dropping HashToScalar for ristretto255 and P-256 would be a mistake.

[daxpedda]

Ah, thank you, I missed that.

I think that pretty much answers my question and resolves this issue.