[Standards] OMEMO Key Agreement

Sebastian Verschoor sebastian.verschoor at gmail.com
Fri Jun 2 20:18:08 UTC 2017


Hi all,

My attention has been brought to the recent (sometimes quite heated)
discussion regarding OMEMO.  To be honest, I haven't followed much of the
development since I did the audit [0], but some things have happened/been
said that I felt I needed to respond to. Here they are* (in no particular
order):

   1. I note that the specs [1] have changes from using the Signal protocol
   to using Olm. I see [2] that Olm is using plain 3DH, not X3DH and is thus
   vulnerable to a weak forward secrecy attack [3].
   2. I noted that much of the discussion revolved around XEdDSA, which I
   find strange since Olm doesn't need signatures, meaning you don't need
   XEdDSA [4]:

>    XEdDSA enables use of a single key pair format for both elliptic curve
>    Diffie-Hellman and signatures. In some situations it enables using the same
>    key pair for both algorithms.

   3. Remko Tronçon on May 31st:

>    Here's a proposal for the OMEMO key exchange that requires *no*
>    changes to libsignal: Public Identity keys are Ed25519 keys with the
>    highest bit (sign bit) 0.

   Be careful there! The sign bit refers to the sign of the x-coordinate of
   the point on the curve on the and is not the same as the sign bit of an
   integer in two's complement. I believe that Ed25519 encodes this bit at the
   end of the public key.
   4. Remko Tronçon on March 31st:

>    The fingerprints would change, but those are typically only used in a
>    short-lived scenarios anyway?

   The fingerprints of the Signal protocol have been crafted such that you
   can publish your fingerprint on long-term media (on your business-card
   would be a typical scenario). You can (and you should!) use those
   fingerprints to verify the identity of the other party in every session.
   5. Matthew Hodgson on March 31st:

>    For libolm, we deliberately didn't follow Signal's behaviour of trying
>    to share identity & signing keys: it seemed overengineered and of
>    questionable value to add complexity in exchange for tracking one key
>    rather than two.  So we just maintain two, and don't bother with all the
>    additional complexity X3DH complexity which results.  It's possible that
>    we're missing some subtlety.

   I don't think you are missing anything here. As long as you tie your
   keys together (for example, by signing your DH-key with your signing key)
   this sounds fine.  The reason to introduce XEdDSA is not having to change
   the key fingerprint, a usability point.

>    It looks like elsewhere in the thread folks are conflating the
>    question of signing one-time keys with the X25519 issue.  As i understand
>    it, the two are unrelated: libolm leaves the question of whether to sign
>    pre-keys up to the application layer; if you want stronger PFS semantics at
>    the expense of reduced deniability, go for it.  This is nothing to do with
>    whether you use X3DH or 3DH for key exchange.
>
>    http://matrix.org/docs/olm_signing.html attempts to describe this
>    trade-off.

   This document is worrysome! It does not address the actual signing that
   is happening in the Signal protocol (which is to introduce a medium-term
   presigned key), but instead suggests signing the one-time use prekeys. You
   never need to do that! Just introduce a fourth DH in your initial handshake
   and you get the best of both worlds.
   6. Andreas Straub on May 24th:

>    Yes, it's true that there's currently no such thing for XEdDSA, but is
>    this actually a concrete problem for anyone? As far as I'm aware, this has
>    always been a purely hypothetical debate. If I'm wrong here, please speak
>    up! In any case, when it comes down to it, implementing this yourself
>    really isn't that complex. You can re-use existing EdDSA code, all you need
>    to do is write the key conversion code yourself, for which there is
>    pseudo-code in the standard, which maps fairly directly to well-known
>    mathematical primitives, for which you can also re-use existing code. The
>    main novel idea in XEdDSA is resolving an ambiguity in the conversion by
>    forcing a sign bit to 0, and that's about it. Your code doesn't have to be
>    constant-time and if you do it wrong, the signature just won't verify.

   Constant-time is an issue for the implementation, see [6].
   7. Sam Whited on May 27th:

>    CMov is an operation that copies data if some condition is true, but
>    without actually branching, which makes things a lot faster).

   It might be faster, but (probably) more importantly it avoids branching
   on secret data which might introduce timing side-channels.
   8. Matthew Hodgson on May 27th:

>    The main differences are:
>     * [...]
>     * the audit (libolm's audit is public, unlike libsignal's)

   There is [7], which was based on the libsignal code.
   9. Remko Tronçon on June 2nd:

>    What Olm (and the PR) calls the 'fingerprint key' and 'identity key'
>    correspond in libSignal terms to 'identity key' (long-standing key,
>    authenticated, never changes) and 'signed prekey' (a key that is signed by
>    the authenticated key, and changed from time to time).

   This confuses me. A fingerprint key is not a term I have ever seen in
   cryptographic literature and some alarm bells are going off in my head
   right now. From what I understand, the Olm protocol only has a three DH
   operations in the handshake, not four as in X3DH. This is not just a
   difference of terminology, but these are cryptographically different
   operations.
   10. Dave Cridland on June 2nd:

>    So:
>
>    Encryption Interop: Don't care (negotiable at runtime)

   Be careful, this stuff is non-trivial [8]

Remko, generally speaking there are some issues with your proposal. What
you are trying to do is to find an easy way in which you can use the
current keys you have and make signatures with them as well. You propose to
implement the first half of XEdDSA (namely fixing the DH public key sign
bit at zero) but you don't follow through with the rest (see security
considerations: random secret inputs and key reuse [6]).  I believe that if
you want to do this (one key for both DH and signging), then XEdDSA is the
minimal solution that remains secure.  Any other solution would require
careful analysis to see if they have any cryptographic issues (for example
with key reuse).

I also noted that although Olm has been audited [9], the scope of the audit
only concerns the double ratchet. Given that Olm differs from Signal only
in the handshake, I find this strange. Has the handshake not been audited?
Am I missing something?

This turned out to be much lengthier than I intended, anyway, I hope it was
helpful.

*) Upon closer inspection, I see that my first two points are not relevant,
Olm was never implemented... Ugh! This whole thing is confusing...
[0]: https://conversations.im/omemo/audit.pdf
[1]: https://xmpp.org/extensions/xep-0384.html
[2]: https://matrix.org/git/olm/about/docs/olm.rst
[3]: https://whispersystems.org/docs/specifications/x3dh/#signatures
[4]: https://whispersystems.org/docs/specifications/xeddsa/#introduction
[5]: https://ed25519.cr.yp.to/python/ed25519.py (encodepoint function)
[6]:
https://whispersystems.org/docs/specifications/xeddsa/#security-considerations
[7]: https://eprint.iacr.org/2016/1013 (and to a lesser extent:
https://eprint.iacr.org/2014/904)
[8]: https://www.imperialviolet.org/2016/05/16/agility.html
[9]:
https://www.nccgroup.trust/us/our-research/matrix-olm-cryptographic-review/

Best regards,
Sebastian

On 2 June 2017 at 08:12, Florian Schmaus <flo at geekplace.eu> wrote:

> On 02.06.2017 13:48, Kevin Smith wrote:
> >
> >> On 2 Jun 2017, at 11:57, Daniel Gultsch <daniel at gultsch.de> wrote:
> >>
> >> 2017-06-01 13:12 GMT+02:00 Kevin Smith <kevin.smith at isode.com>:
> >>> On 1 Jun 2017, at 11:22, Daniel Gultsch <daniel at gultsch.de> wrote:
> >>>> I went ahead an created a PR for XEP-0384 to match what is actually
> >>>> implemented in the wild.
> >>>> ...
> >>>> I changed the track from Standards to Historical.
> >>>> I checked: Track changes have happened before and are apparently
> >>>> possible if Council agrees.
> >>>> I think this is the best way forward given that developers and users
> >>>> who are *currently* looking for the OMEMO spec are probably looking
> >>>> for this XEP and not OMEMO-NEXT.
> >>>> Also we don't have to assign a new author as it would be the case if
> >>>> XEP-0384 would become OMEMO-NEXT.
> >>>
> >>> I think that, while someone interested in implementing OMEMO-SIACS
> might find it convenient for 384 to be changed in this way, what the XSF
> wants is to push people towards Standards Track XEPs and in this case, 384
> seems to be the logical place.
> >>>
> >>> Conceptually, changing 384 to historical and changing the content is
> very odd
> >>
> >> If it is easier 'conceptually' I'm also fine with leaving it in the
> >> Standards track and marking it as deprecated.
> >>
> >> The point is that OMEMO in its current form is extremely popular. How
> >> many XEPs have Wikipedia and online news media (LWN, Golem) articles
> >> written about them?
> >
> > I think that’s a significant argument for why 384 needs to remain the
> location of the XSF’s ongoing work on this. Many people are, as you note,
> interested that the XSF is working on a standard here, so saying “We’ve
> stopped working on it” would be misleading and unhelpful.
>
> Nobody wants the XEP-0384 to say "We've stopped working on OMEMO", that
> is why we add put a big notice with an link to OMEMO-NEXT on top.
>
> - Florian
>
>
> _______________________________________________
> 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/20170602/4f6077fb/attachment-0001.html>


More information about the Standards mailing list