[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,
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'  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
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.
More information about the Standards