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.)

Any Questions? Comments? Snide remarks?

  • $\begingroup$ Hmm, can your HW store an arbitrary amount of ECDH secrets? So e.g. two private keys? $\endgroup$
    – SEJPM
    Aug 12 '19 at 12:44
  • $\begingroup$ @SEJPM Yep. There's a limit, IDK off the top of my head, but call it 8. $\endgroup$ 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).

This is stupid obvious now, but it took several days to figure it out.


I think what you are looking for is impossible.

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.

  • $\begingroup$ Aha, but I think I solved this yesterday! Specifically, there's no reason you need f to be a function of G. All you need it to do is turn t into a curve point: preferably in a "nothing-up-my-sleeve" manner that makes it clear that t' such that t'G = f(t) is unknown, perhaps by hashing it and massaging the bits somewhat. Call your partner's public key Y = yG; then T(f(t)) * Y = x * f(t) * yG = y * f(t) * xG. In short, ECDH(Ypriv, ECDH(Xpriv, f(t))) = ECDH(Xpriv, ECDH(Ypriv, f(t))). $\endgroup$ Aug 12 '19 at 15:36
  • $\begingroup$ Of course, I'm just now realizing I've violated my own requirement for no communication. You need to get y * f(t) from your partner to make it work. Luckily, my application can handle a single message like that. $\endgroup$ Aug 12 '19 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.