Score:1

Signal protocol: X3DH

ru flag

I've been trying to get a grasp of how the Signal protocol works. According to the spec, DH is done on four keys: IK_A, SPK_B, EK_A and IK_B:

If the bundle does not contain a one-time prekey, she calculates:

    DH1 = DH(IK_A, SPK_B)
    DH2 = DH(EK_A, IK_B)
    DH3 = DH(EK_A, SPK_B)
    SK = KDF(DH1 || DH2 || DH3)

Given that all these four keys are public keys and are announced through untrusted channels, couldn't a nefarious player compute the shared secret SK?

Ievgeni avatar
cn flag
Why do you say DH1, DH2, and DH3 are "announced through untrusted channels". As far as I understood Alice deletes the data after she computed.
John M. avatar
ru flag
@Ievgeni I mean the public keys are. The DH's appear to be calculated using public keys which wouldn't make much sense.
Ievgeni avatar
cn flag
I think that this documentation is fuzzy. To compute DH, Alice uses the discrete logarithm of IK_A and EK_A known only by herself.
Score:0
cn flag

In fact $DH1, DH2$ and $DH3$ are not "announced through untrusted channels".

I think that this documentation is fuzzy. To compute DH, Alice uses the discrete logarithm of IK_A and EK_A known only by herself.

To be more concrete, if IK_A = g^{sk_A}, and SPK_B=g^{sk_B}, with $sk_A$ a secrete value already known by Alice.

Then she could compute DH(IK_A, SPK_P) by computing $(SPK_B)^{sk_A}$.

And Bob could compute DH(IK_A, SPK_P) by computing $(EK_A)^{sk_B}$.

This protocol is secure under the computational Diffie-Hellman assumption :

https://en.wikipedia.org/wiki/Computational_Diffie%E2%80%93Hellman_assumption

Marc Ilunga avatar
tr flag
Do you have a claim for the security under CDH? Indeed, without CDH the protocol is broken but, in this analysis of x3dh https://eprint.iacr.org/2016/1013. They had to rely on the GapDH. Now one could argue this is an artifact of the model, but at the same time these Bellare-Rogaway model for AKE seem highly reasonable. Hence, the attacker has more power than a CDH adversary and we need stronger assumptions.
Ievgeni avatar
cn flag
I was answering to the specific part asked by John not about the whole protocol (I will edit in my answer to precise). Maybe you should ask a new question more precise.
Marc Ilunga avatar
tr flag
I was mainly curious whether there was a new result on x3dh that directly proves security under CDH only, and did require additional assumption. Maybe it's good to indicate that CDH is okay taken isolated, but the overall protocol is likely to need more assumptions in common security models.
mangohost

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.