2
$\begingroup$

I'm trying to implement X3DH (extended triple Diffie-Hellman) in a network of mine.

The way I understand it, a bundle (IPKb,SPKb,OTKb) is retrieved by Alice from Bob, through the server, and using her own public keys IPKa and EPKa she calculates:

DH(IPKa,SPKb)

and some others.

What I do not understand is: what are these public parameters used for in DH? Isn't Diffie-Hellman constructed with private keys, and 2 pre-determined public numbers? Should I treat these 2 keys as those pre-determined numbers?

Also, Diffie-Hellman requires key exchanges and communications between Alice and Bob; why can't Bob compute the key at the same time as Alice? Why does Alice need to return a bundle of her own IPK and EPK for Bob to do the calculations from scratch? I'm confused.

Sorry for the naive question but I can't seem to find an explanation on what these passed keys are supposed to be doing anywhere.

$\endgroup$
1
  • $\begingroup$ Classic (aka integer, modp, finite-field) DH uses 2 or 3 integers as parameters (p, g, optional q) and a keypair is two integers, commonly x and y with $y=g^x \mod p$. X3DH uses elliptic-curve DH which uses a parameter set commonly called a curve (X3DH uses X25519 or X448) and a keypair is an integer k and the encoded point $[k]G$ on $E(Fp)$. See crypto.stackexchange.com/questions/47744/… and signal.org/docs/specifications/x3dh which latter also explains the purposes of the different keys. $\endgroup$ Apr 15 at 0:55
3
$\begingroup$

As X3DH uses elliptic curve Diffie-Hellman, I'll write things in elliptic curve notation thus if we have a curve $E$ with $q$ points and a base point $G$ we might see Alice choose a private key $a\pmod q$ and create a public key $A=aG$. It should be easy to convert to multiplicative notation if you need to.

Regular Diffie-Hellman
In the regular form of the Diffie-Hellman, Alice and Bob each choose a single private value $a$ and $b$ respectively, and generate public keys $A=aG$ and $B=bG$ which they then exchange. In the notation of the question $$\mathrm{DH}(A,B)=aB=bA=abG$$ is the shared secret value. Although it is written as a function of $A$ and $B$ this is in a mathematical rather than a computational sense. It should be infeasible to compute $\mathrm{DH}(A,B)$ without knowledge of one of the private values. This notation can be frustrating.

People talk about static Diffie-Hellman and ephemeral Diffie-Hellman depending on whether the same values are used over multiple exchanges or whether new values are generated for each exchange. Static Diffie-Hellman gives some assurance that you are communicating with the same person in both exchanges. Ephemeral Diffie-Hellman prevents the same key being generated and provides forward security which is the assurance that if a private key becomes known, it only jeopardises a single message rather than any previous ones.

X3DH
X3DH tries to create keys with the benefit of both the static and ephemeral versions. It has Alice and Bob choose multiple secret values and public values, say $a_0$, $a_1$ etc. and perform multiple DH computations to combine the results. In particular, they both create long term identity keys $IK_A=ik_AG$, $IK_B=ik_bG$; they create medium term signed keys $SPK_A=spk_AG$ and $SPK_B=spk_bG$ which change from time-to-time but are digitally signed so that users can be assured that they are only used by the claimed user; they create several one-time-keys. In particular then $$\mathrm{DH}(IK_A,SPK_B)=ik_ASPK_B=spk_BIK_A=ik_Aspk_BG$$ and $$\mathrm{DH}(EK_A,IK_B)=ek_AIK_B=ik_BEK_A=ek_Aik_BG$$ Thus there is a measure of both identity assurance and separation of key values.

The X3DH protocol is designed so that Alice can initiate communications even when Bob is offline and so it makes sense for Alice to perform her half of the computation and send it even if Bob is not present. Bob can then complete his half of the transaction when he comes online and deals with Alice's message.

$\endgroup$
1
  • $\begingroup$ @idk: 1. Yes, that's right. Alice can generate the master secret and send Bob messages even when he is not online. That's a major motivation for the design. 2. Yes, X3DH should be secure in any group where the Diffie-Hellman problem is hard. Elliptic curves are used in practice as they are the most efficient option. $\endgroup$
    – Daniel S
    Apr 15 at 19:14

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.