# "Dave Check" for a tweakable P-256 ECDH KDF

I have two devices with hardware tokens that contain P-256 private keys, and which allow me to compute ECDH shared secrets with arbitrary public keys. I need to build a tweakable key derivation function, which deterministically allows both sides to generate the same key given their partner's P-256 public key and a tweak value. The construction must have the property that computing the key for a new tweak value requires an operation on the hardware token, even if token outputs for many other tweak values are known.

I've come up with the following pseudocode:

// NIST recommended way to generate a private key
l = 2^256 − 432420386565659656852420866394968145599
P256Priv(ikm): (HKDF_expand(40, ikm) % (l - 1)) + 1

// point multiplication with g as the P-256 generator
P256Pub(p): g * p

// different function instances for different tokens
tokenECDH(inPub): ECDH(tokenPriv, inPub)

// Using XOR because it makes both sides symmetrical
TweakableKDF(tokenECDH, peerPub, tweak, numBytes):
Epriv = P256Priv(tweak)
Epub = P256Pub(Epriv)
HKDF_expand(numBytes, tokenECDH(Epub) ^ ECDH(Epriv, peerPub))


It looks to me like this would be secure, but I don't want to be a Dave. (Also, I can't help but wonder if there's something standard out there that does this already; I looked briefly and was surprised I didn't find much.)

• Hmm, can your HW store an arbitrary amount of ECDH secrets? So e.g. two private keys?
– SEJPM
Aug 12 '19 at 12:44
• @SEJPM Yep. There's a limit, IDK off the top of my head, but call it 8. Aug 12 '19 at 14:48

This is broken, because possession of Epriv (a function of the public tweak value) allows calculation of the output of tokenECDH(Epub) given knowledge of tokenPub (another public value).
To see this, let's formalize things a bit: You have an oracle (the HW token) $$T(Q)=[x]Q$$ which computes a scalar product of any given input point with a secret scalar. You have an integer (or a byte sequence) $$t$$ - the tweak - and you have a public point $$Q'$$ from your partner as well as of course a standard point for the curve $$G$$.
Now the question asks to find a KDF $$K_T(t,Q')$$ such that every change in the known input tuple $$(t,Q')$$ yields a completly unpredictable value. However your only ressource for that is the $$T$$ oracle and so if you compute it's input as $$T(f(t,G))$$ then you need to find a deterministic $$f$$ such that the discrete logarithm problem between $$f(t,G)$$ and $$G$$ is hard even if one knows $$t$$. Otherwise of course you can use your solution to just take $$T(G)$$ and apply the found discrete logarithm to that.