Proof of possession of a x25519 private key

stsch

9/20/23, 1:13 PM

In this question one way is shown how to prove the possession of a private x25519 key. Would the following protocol also be suitable to prevent someone from using the client as a decryption Oracle?

Server generates some 'nonce' and an ephemeral x25519 key pair. The sever sends the nonce and the public x25519 key to the client.
The client derives with his private x25519 key and the public x25519 key of the server a shared key. The client signs the nonce with HMAC using the shared key. The client sends the signature to the server.
The server derives the shared key and validates the HMAC signature.

0 + 0

x25519

zugzwang

9/20/23, 2:37 PM

What is wrong with a good old discrete-log zero-knowledge proof? E.g. for private key $x$, Prover publishes $Y=G^x$, then samples an integer $x'$ computes $T=G^{x'}$, then computes $c = hash(G, Y, T)$ and sends $c, -cx+x'$. Verifier reconstructs $T$ by doing $G^{-cx+x'}Y^c$, and checking that $c = hash(G, Y, T)$.

knaccc

9/20/23, 2:49 PM

You're already going to need to do something to prevent man-in-the-middle attacks that will involve signatures to prove the server's identity to the client. So why not just use that same mechanism to prove the client's identity to the server?

stsch

9/20/23, 8:32 PM

@zugzwang Thank you for your idea. But i think one problem is that $-cx+x'$ is not "clamped". If for example libsodium is used, you cannot use standard functions

zugzwang

9/21/23, 9:34 AM

Just for the record, my idea is not original at all. It is the basic zk proof of knowledge (if you want to see nice extensions, I encourage you to check the Camenisch-Stadler 97 paper). Now, this argument applies to any group. In particular, to Curve25519. The clamping is only an implementation trick to avoid the small subgroup of order 8. So of course this argument works in Curve 25519. The elegance of it is that it depends only on ECDLP, instead of signing algorithms such as Ed25519.

stsch

9/23/23, 5:38 AM

@knaccc Good idea. Thank you.

zugzwang

9/23/23, 9:25 AM

The drawbacks on @knaccc 's idea are that (a) it depends on the existencial unforgeability on the signature scheme, rather that on possesion of a secret value, as was the ask, and (b) such a protocol will probably be interactive (unless Fiat-Shamir trick is applied somehow, potentially introducing more security assumptions).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Proof of possession of a x25519 private key

TH: Proof of possession of a x25519 private key

RO: Proof of possession of a x25519 private key

RU: Proof of possession of a x25519 private key

VI: Proof of possession of a x25519 private key

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.