Prepare to add ECDH

[marsella]

We want to have a version of elliptic-curve Diffie-Hellman, as standardized in NIST SP 800-56A revision 3. There are several versions (not sure yet how all the models are different; one thing is key durability but maybe others):

• section 5.7.1.2 is the basic primitive
• section 6.1.1.2 is the "full unified model"
• section 6.1.2.2 is the "ephemeral unified model"
• section 6.2.1.2 is the "one-pass unified model"
• section 6.2.2.2 is the "one-pass dh"
• section 6.3.2 is the "static unified model"

Some initial poking around suggests that this might need to be broken into multiple issues / PRs: one to set up key management (association with curves, distinguishing between ephemeral and static keys, maybe generation?), one to implement other preliminaries and the ECDH primitive, and maybe a third to do all the different models.

• [x] Determine what other portions of that spec need to be in the ECDH implementation (preliminaries, etc.)
• [x] In particular, 5.7.1.2 takes public and private keys as input. Consider formalizing an association of key -> curve and maybe generation of keys
• [x] Determine if & how to support ephemeral vs static keys
• [x] Determine which of the models we want to support for starters
• [x] Write follow-up issues with further details for implementation

[kiniry]

I provided my input on this topic in today's MTV meeting, but we should also get input from @weaversa as well.

[weaversa]

I provided my input on this topic in today's MTV meeting, but we should also get input from @weaversa as well.

I've only ever attempted 186-5. This is new territory for me. Let me suggest you keep the CAVP and KASVS specific to 800-56A in mind, ensuring that the invariants laid out are adhered to (when possible) and documented regardless. Also, providing interfaces to the provided test suites will be beneficial.

[marsella]

I read through most of the spec (800-56A). Here are my notes:

• The ECDH parts of SP 800-56A r3 is based on ANSI X9.63. Confirm that we want to use the NIST spec as our baseline?
• "The destruction of any potentially sensitive locally stored data is an obligation of all implementations"
• Each key is associated with: domain parameters (and must be valid for the given params); identifier - any string, at least for static keys; values (e.g. the actual key)
  • Design thought: This is similar to ECDSA keys but in general we don't want a single key type that's reused between these, because we don't want people to use the same keys for ECDH and ECDSA. If we made a key type we would want it to be some kind of submodule / tied to ECDH.
• Method for assurance that the other party actually has the relevant private key (5.6.2.2.3)
• Methods for validation of the other party's public key (e.g. make sure it's on the curve)
• Approved hash function is required (see #98)
• Approved MAC is required (HMAC, AES-CMAC, KMAC). We have a version of HMAC in the repo for now. Ideally we'd have a MAC interface. But the ECDH primitive itself doesn't use MACs so this is not high priority.
• Assumption: RNG must support targeted security strength.
• There are some assumptions about nonces but not in the ECDH primitive
• Domain parameters: they need to be approved. For some of the models with multiple keys, all the keys need to use the same parameters. The approved curves include the P-curves we have.
• I'm going to skip reading most of the key generation stuff because Cryptol can't model that well.
  • 5.6.2.1: can probably make an is_valid function for each of public & private keys to check this?
  • 5.6.2.3.3 full public key validation - definitely need this. It assumes validated domain parameters.
• The shared secret generated from the primitive must be used with a key derivation method -- shouldn't be used directly. Do we want to implement this? It's a different spec.
• There's an algorithm for key confirmation so one or both parties can confirm they got the same secret (this is where MACs are used; also requires key derivation)
• Section 6 is key agreement schemes that use all the primitives above. They were determined to be out of scope for this first pass.
• Section 7 is rationale for selecting a specific scheme; not encodable.
• Section 8 is about key recovery and describes which keys can be saved for recovery.
• Section 9 points to CAVP and CMVP for validating implementations. This actually has a bit of an MVP recommendation that we can use (domain param selection & validation, key pair generation, public key validation, key-agreement)

---

Per offline discussion, we decided on the following priorities:

• The basic ECDH primitive (5.7.1.2) is top priority.
• That primitive needs keys as input, but building a full model of keys-with-context is lower priority.
• The models in section 6 are lower priority.
• We did not discuss key derivation or confirmation.

I'll write a follow-up issue to handle the ECDH primitive and basic key representation and leave the rest here for now.

[marsella]

Closing this as we don't have concrete plans to continue adding the key agreement schemes or any other items right now. Can reopen if / when we decide to do so.