[Standards] OMEMO Key Agreement

Richard van der Hoff richard at matrix.org
Tue Jun 6 13:14:01 UTC 2017

At the risk of turning the standards list into a forum discussing the 
finer points of cryptographic key exchange, I thought it might be useful 
weigh in on some of the issues raised, in the hope of clearing up some 

As Matthew has previously said: it's certainly not our intention to 
attempt to railroad the decisions of the XMPP community - just trying to 
make sure that the information on which such decisions are made is sound.

Sebastian Verschoor wrote:

> TBH: I don't know enough about Olm to answer that. From what I read in the
> specs they do 3DH: s = DH(IK_A, OTK_B) || DH(OTK_A, IK_B) || DH(OTK_A,
> OTK_B).

That's correct, as far as it goes. It's worth reiterating that, in the 
libolm implementation, IK_A and IK_B have previously been signed by the 
relevant user's (long-term) Ed25519 key.

We don't consider that part of the core Olm protocol (which assumes you 
are starting with identity keys you trust, and focusses on the triple-DH 
and double ratchet); indeed an alternative implementation is possible in 
which you don't bother with the Ed25519 keys and treat the IKs as 
long-term instead, but since the only implementation of Olm I know of 
uses the Ed25519 key as the long-term key, we may as well forget it.

In Matrix, at least, we also have Bob sign OTK_B which avoids the 
potential loss of forward secrecy if Eve later compromises IK_B, though 
it does come with a trade-off in deniability.

I've tried to explain both of these points at 
https://matrix.org/git/olm/about/docs/signing.rst. (Sebastian previously 
described that document as 'worrisome' [1] but I wonder if that was 
based on some misunderstandings which have since been cleared up. If 
not, I'd be very glad to discuss your worries.)

One other point here: although we refer to Alice's short-term key in 
this exchange as a one-time-key (hence OTK_A here), it is never 
"published" outside the Olm setup, so that makes it analogous to an 
ephemeral key in the Signal terminology. so E_A might be a better symbol 
for it. (In general the Olm spec is, regrettably, somewhat inconsistent 
in the use of the terms 'ephemeral key' vs 'one-time key' vs 'single-use 
key' and tends to treat them all interchangeably.)

>> I don't understand yet what the 4th DH does, though. Given that I_b is
>> signed (and can be replaced from time to time), I was assuming this
>> corresponds to the signed prekey instead of the identity keys from X3DH.

This is a valid analogy.

>> This would mean that Olm's 3DH doesn't use a long-standing identity key in
>> its key agreement (it's only used to sign the prekey), and that Olm's 3DH
>> involves signed prekeys from both parties (does this impact deniability?).
> So there is no long-term key involved in the key agreement? I don't think
> that such a protocol authenticates the other party... If that is true the
> protocol has bigger problems than just deniability...

It's true that such an exchange doesn't identify the other party by 
itself. Assuming you're using a system whereby you use the Ed25519 key 
as the long-term key and periodically rotate the Curve25519 olm 
'identity' key, this works as follows:

1. Alice and Bob exchange and verify each other's public Ed25519 keys 
out-of-band - or exchange them in-band and TOFU.

2. Alice publishes a message including her (current) public Curve25519 
identity key IK_A and signs it with her Ed25519 key. In doing so she is 
claiming control of the private part of IK_A (though there is no 
evidence of this yet). In other words: this signature prevents an 
eavesdropper Eve masquerading as Alice and publishing a key she controls 
in place of Alice's; it does *not* prevent Alice publishing someone 
else's Curve25519 key as her own.

3. Bob downloads Alice's signed key, and likewise publishes his own 
signed key IK_B - again, claiming but not proving control of the private 
part of that key.

4. Alice now downloads Bob's signed key (along with one of his one-time 
keys), and initiates the 3DH exchange. She uses it to encrypt a pre-key 
message which *must* include her public Ed25519 key, as well as Bob's 
user ID.

5. Bob receives the pre-key message, and decrypts it. He must now check 
that the Ed25519 key embedded within the message matches that he has 
verified for Alice. This check prevents Alice publishing someone else's 
Curve25519 key as her own.

(Bob also checks the user ID, to mitigate an unknown key-share attack 
whereby Mallory publishes Bob's IK_B as her own, and Alice thinks she is 
talking to Mallory, but Mallory is forwarding the messages to Bob, and 
Bob thinks the message was intended for him.)

6. Bob replies to the pre-key message including his own Ed25519 key, to 
allow Alice to finally verify that Bob controls IK_B.



[1] https://mail.jabber.org/pipermail/standards/2017-June/032866.html

More information about the Standards mailing list