[Standards] OMEMO Key Agreement

Dave Cridland dave at cridland.net
Tue Jun 6 17:06:31 UTC 2017

On 6 Jun 2017 14:14, "Richard van der Hoff" <richard at matrix.org> wrote:

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

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.

As a matter of general principle, by posting to this list you have
satisfied one of the many possible ways of becoming as much as member of
the XMPP community as anyone else... Please do feel free to post messages
like this, I for one found it very useful.

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/abo
ut/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

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

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

Standards mailing list
Info: https://mail.jabber.org/mailman/listinfo/standards
Unsubscribe: Standards-unsubscribe at xmpp.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.jabber.org/pipermail/standards/attachments/20170606/a79c923a/attachment-0001.html>

More information about the Standards mailing list