[Standards] Review of XEP-0384: OMEMO Encryption

Sofía Celi cherenkov at riseup.net
Mon May 11 23:20:05 UTC 2020

Hi, list!

Thanks so much for all the nice conversations that occur daily over here
is super nice reading them.

I briefly read the XEP-0384: OMEMO Encryption and I have some comments
that might help the document. Apologies if this have been already
discussed or if I did not understand something correctly. It is really
nice to read the specification of this protocol and I'm happy that work
on this has happened ;)

The notion of:

- "Perfect forward secrecy: Compromised key material does not compromise
previous or future message exchanges."

is not completely correct. This definition is now referred a Forward
Secrecy only. Forward secrecy refers to the fact that 'if the state of a
party is leaked, none of the previous messages should get compromised
(assuming they are erased from the state, of course).' It only deals
with previous exchanged messages but not to future ones.

The property that might protect future exchange of messages is
'Post-compromise security (PCS) (aka channel healing), which is defined
as 'once the exposure of the party’s state ends, security is restored
after a few communication rounds.'

Currently, there is no way to give perfect backwards secrecy (fully
protecting future message exchange), but rather  protecting them for a
window of time. This is what is referred as post-compromise security,
and it is what the double ratchet algorithm gives. You can read a review
of the properties of the double ratchet algorithm here [1].

Furthermore, as it has been demonstrated in some literature [2], X3DH
provides weak forward secrecy (it protects the session key only when
both parties complete the exchange).

- Immutability: Every peer can ensure that a message was not changed by
any intermediate node.

I think this definition is actually called 'Integrity'.

- 'Plausible deniability: No participant can prove who created a
specific message.'

Plausible deniability is a legal definition, as far as I'm aware of [3].
The notion of deniability in cryptography depends on which type wants to
be given, as it is possible to deny authorship of a message (it is not
possible to deny 'creation' in this terms) or participation in a whole
conversation. Furthermore, the current notions of deniability in the
literature also define it in terms of offline and online. X3DH is weakly
offline deniable and provides no online deniability, as far as the
research shows [3].

- 'An attacker has permanent access to your device. Temporary access is
covered by perfect forward secrecy.'

I think that if an attacker have access to a device, there is no real
forward secrecy, as this attacker have access to the log/screen of the
device. Other protocols have taken further steps to enhance this by
providing, for example, a 'Disappearing messages' option from a UI
perspective. I don't know if this is something that applications that
implement OMEMO use.

- 'Implementations must use the birational map between the curves
Curve25519 and Ed25519 to convert the public part of the IdentityKey
whenever required, as defined in RFC 7748 [11] (on page 5).'

This is very interesting and quite possible. But I was wondering if
there is a mechanism used to correctly handle the cofactor in this both
cases, or a correct generation of the keys.

- 'deletion policy for skipped message keys
Skipped message keys MUST be stored until MAX_SKIP message keys are
stored. At that point, keys are discarded on a FIFO basis to make space
for new message keys. Implementations SHOULD not keep skipped message
keys around forever, but discard old keys on a different
implementation-defined policy. It is RECOMMENDED to base this policy on
deterministic events rather than time.'

While this is nice idea, I think an attack might happen if it is
implemented. As the Signal specification for the double ratchet
algorithm states [4], 'a malicious sender could induce recipients to
store large numbers of skipped message keys, possibly causing
denial-of-service due to consuming storage space.', so it is a wise idea
to have a MAX_SKIP parameter. But, if an attacker knows that after this
limit is reached keys will start to get deleted, the attacker can induce
to keep sending fake messages so authentic keys get deleted. I think a
mitigation against this is jut to delete skipped message keys after an
appropriate interval.

- 'HKDF-SHA-256 using the rk as HKDF salt, dh_out as HKDF input material
and "OMEMO Root Chain" as HKDF info.', 'HMAC-SHA-256 using ck as the
HMAC key, a single byte constant 0x01 as HMAC input to produce the next
message key and a single byte constant 0x02 as HMAC input to produce the
next chain key.'

I think probably what 'rk' and what 'ck' is should be defined previously
(or pointing out to the specific place on the double ratchet
specification). It can get confusing ;)

The same for 'mk'.

- 'Generate 32 bytes of cryptographically secure random data, called key
in the remainder of this algorithm.'

It will be good to point out what is 'cryptographically secure random
data'. Usually, linking to RF4086 is enough [5].

- Multi-device synchronization

I think this is a nice way to do multi-device synchronization, but I
don't know if these two cases have been taken into account:

Alice can try to start a conversation from device 1. Bob will receive
this request on device 1 and ask for the list of devices from himself
and from Alice (on device 1). Bob on device 1 will try to start the
appropriate session with each of Alice's devices (and with his own). At
the same time, Alice can try to start a conversation from device 2 with
Bob on device 1, which will trigger device 1 from Bob to ask for the
list of devices again. I'm not sure how this is handled.

More difficult to solve is the situation when Alice tries to start a
conversation from device 2 with Bob on device 2, when there is already a
request from Alice on device 1 to Bob on device 1. What can happen in
this case is that two sets of 'multi-device synchronized' sessions

- The double ratchet algorithm has an interesting case for when both
parties start it at the same time. This is briefly covered on [6]:

"(This assumes Alice begins sending messages first, and Bob doesn't send
messages until he has received one of Alice's messages. To allow Bob to
send messages immediately after initialization Bob's sending chain key
and Alice's receiving chain key could be initialized to a shared secret.
For the sake of simplicity we won't consider this further.)

I'm not sure if this has been considered and if any solution has been

Apologies if any of this is already resolved ;) I did not review neither
the group chat details nor the SCE Profile ones.

Hope this is helpful!


1. https://eprint.iacr.org/2018/1037.pdf
2. https://www.cypherpunks.ca/~iang/pubs/dakez-popets18.pdf
3. https://en.wikipedia.org/wiki/Plausible_deniability
5. https://tools.ietf.org/html/rfc4086
6. https://signal.org/docs/specifications/doubleratchet/#double-ratchet-1

Sofía Celi
Cryptographic research and implementation at Cloudflare and many places
FAB9 3EDC 7CDD 1198 DCFD  4558 91BB 6B45 6F44 2D02

More information about the Standards mailing list