Re: [Standards] OMEMO Key Agreement
Thanks, I that clears some things up for me, not so worrisome after all, I now believe that the users are properly authenticated. I have thought about the Matrix protocol with seperated DH/signing keys some more and discussed it with a colleague and we believe it is fine. A very minor points springs to my mind, but I think you can judge for yourself if you think this is an acceptable risk: Eve can impersonate Bob when she compromises a private Curve25519 key that is signed by Bob's Ed25519 key without compromising the Ed25519 private key itself. This should not be possible under normal circumstances, but I can think of two scenario's: (1) Eve tricks Bob into signing a Curve25519 key generated by her. This should never happen as long as the only thing that Bob signs is his own locally generated public keys; (2) Bob's random number generator is weak during some identity-key generation, so Eve can guess/bruteforce his private Curve25519 key. Compare this to X3DH where a RNG failure results in the loss of security for a session, not an identity. I don't know how likely either scenario is in your context: you can better judge that for yourself. On 6 June 2017 at 09:14, Richard van der Hoff 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. > > 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 Ed255
Re: [Standards] OMEMO Key Agreement
On 3 June 2017 at 06:49, Dave Cridland wrote: > On 2 June 2017 at 21:18, Sebastian Verschoor > wrote: > > Dave Cridland on June 2nd: > >> > >> So: > >> > >> Encryption Interop: Don't care (negotiable at runtime) > > > > Be careful, this stuff is non-trivial [8] > > [8]: https://www.imperialviolet.org/2016/05/16/agility.html > > Yes, indeed, and moreover I don't think we can solve any form of > downgrade attack conclusively. > > Nevertheless, this happens to be the area I'm most comfortable we can > address properly. > > Cool, sounds like you would be able to address this way better than I could. > Incidentally, the agility issues need to be addressed anyway - DJB is > not a god, and the Edwards curve based around the prime number 25519 > may prove to be weak somehow, or perhaps EdDSA as a whole might be. > > In addition, OMEMO as a whole addresses a specific threat model which, > while well-suited to the "consumer in the cloud", isn't well suited at > all to enterprise, and that suggests an overall model where we'll have > to negotiate between OMEMO and some other model (such as MIKEY-SAKKE > or something). > > Dave. > ___ > Standards mailing list > Info: https://mail.jabber.org/mailman/listinfo/standards > Unsubscribe: standards-unsubscr...@xmpp.org > ___ > ___ Standards mailing list Info: https://mail.jabber.org/mailman/listinfo/standards Unsubscribe: standards-unsubscr...@xmpp.org ___
Re: [Standards] OMEMO Key Agreement
Hi Remko, On 3 June 2017 at 05:29, Remko Tronçon wrote: > Hi Sebastian, > > Thanks for your feedback, it's insightful. > > > Remko, generally speaking there are some issues with your proposal. > > I think we ended up agreeing that the way I was looking for compromises > wasn't ideal for future-proofness. Apparently, it also has cryptographical > problems. I don't think we should dig into this further or try to fix it. > > > 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). > > Right, I wasn't saying it wasn't. I was saying that breaking fingerprints > to get to a protocol where we are all comfortable with would be suboptimal, > but maybe wasn't a dealbreaker. Even Signal changed their fingerprints > AFAIK [1] (although perhaps in a way that people who really wanted to could > decompose the new format and still reuse their fingerprints) > > As a sidenote, "crafted for printing" depends how you look at it. Signal > fingerprints are per-conversation. From [1], I understand that to get > something to put on a business card, you need to split the fingerprint, > figure out which half is yours, and the other party needs to know how to > interpret this and do the same. So it's not really part of the flow they're > trying to push, but it can be done if you really wanted to. > I think you are right here, the blogpost mentions how unintended publishing of the (old style) fingerprints was hurting users privacy. > > This confuses me. > > This is not just a difference of terminology, but these are > cryptographically different operations. > > The terminology comes from an Olm document. My point (and others pointed > this out to me as well) was indeed that this terminology was confusing, and > probably needs to change. > > I also didn't mean to say that X3DH and 3DH are the same of course. My > point in that mail was to point out that I think that modifying libsignal > to do Olm's 3DH doesn't require a full rewrite of all clients. But I get > that reusing the identity key only for signing but not for 3DH might have > issues (and another upgrade path might need to be found). > > > 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. > > Just introduce a fourth DH in your initial handshake and you get the > best of both worlds. > > Am I understanding you correctly that using Olm as it is defined today > (combined with separate keys for signing and DH, and signing the DH key) > can work, but that the key agreement can be improved (i.e. add a 4th DH) to > get the extra properties that Signal gives you? > 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). > 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 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... In X3DH, there are four DH computations ( https://whispersystems.org/docs/specifications/x3dh/#sending-the-initial-message ): - DH(IK_A, SPK_B) authenticates Alice - DH(EK_A, IK_B) authenticates Bob - DH(EK_A, OPK_B) adds forward secrecy for honest parties - DH(EK_A, SPK_B) adds forward secrecy with dishonest parties Imagine the last DH (and thus Bob's signature on his prekey) is missing. Then Eve can impersonate Bob by publishing a prekeybundle with her own one-time prekeys and Bob's public key. When Alice sends her messages to Eve (thinking she is sending a message to Bob), Eve collects and stores the ciphertext, which she can't decrypt yet. Later, she compromises Bob's device and with his long-term private key, she can decrypt the collected messages. This attack thus breaks the forward-secrecy of the initial messages. The signed prekey prevents this attack, because Eve can no longer publish a prekey bundle impersonating Bob (as that would require forging a signature). > > thanks! > Remko > > [1] https://www.whispersystems.org/blog/safety-number-updates/ > > ___ > Standards mailing list > Info: https://mail.jabber.org/mailman/listinfo/standards > Unsubscribe: standards-unsubscr...@xmpp.org > ___ > >
Re: [Standards] OMEMO Key Agreement
On 3 June 2017 at 04:10, VanitasVitae wrote: > Hi Sebastian! > > As a cryptographic expert, what would be your advise for future > development of the protocol? > > As you may have read, the reason of this discussion is the fact that there > are concerns that it is not trivial to implement OMEMO in non-GPL apps due > to the lack of a permissive XEdDSA implementation. Thats also the reason > why OMEMO was (prematurely) specified based on Olm instead of libsignal. > > Would you rather suggest to put the efforts into a permissive XEdDSA > implementation or what would be your advice? > I was going to suggest using seperate key-pairs: one for signing and one for DH. However, upon closer inspection it seems that the X3DH-specification requires XEdDSA signatures ( https://whispersystems.org/docs/specifications/x3dh/#cryptographic-notation), so if you did that you would no longer follow the open specs, which I believe (from previous discussions) is not desirable. So the other option is to implement XEdDSA. The specs aren't super complicated, so I think I could do that, based on the public domain Curve25519 code in supercop. It would be a public domain implementation in C (I believe most languages can call C through an FFI?) > > Greetings Vanitasvitae > -- > Diese Nachricht wurde von meinem Android-Mobiltelefon mit K-9 Mail > gesendet. > ___ > Standards mailing list > Info: https://mail.jabber.org/mailman/listinfo/standards > Unsubscribe: standards-unsubscr...@xmpp.org > ___ > > ___ Standards mailing list Info: https://mail.jabber.org/mailman/listinfo/standards Unsubscribe: standards-unsubscr...@xmpp.org ___
Re: [Standards] OMEMO Key Agreement
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' (l
Re: [Standards] Proposed XMPP Extension: OMEMO Encryption
Hi Daniel, Thanks for the fast response. On 31 October 2016 at 12:58, Daniel Gultsch wrote: > Hi Sebastian, > > you should be acknowledged in the acknowledge section of the XEP. > However 'Section 7' didn't change between the audit and now. It > remained the same ever since the original version of the XEP. > > However credit is definitely due if only for the GCM auth tag thing. > (Actually could you look over how this is handled right now and if > this addresses the issues voiced in the audit?). > I believe that encrypting and authenticating the tag/key-tuple within the Olm session as described in Section 4.5 of the XEP fixes the issue described in Section 2.2.3 (message authentication) of the audit: adding the tag to the Olm payload disables the attacker to authenticate arbitrary messages. However, Section 4.6 of the XEP (Sending a key) also includes a tag in the payload. I am not sure where the tag comes from? In fact, I believe that this tag can simply be left out: the randomly generated key *is* the full message content and is already authenticated by the Olm session. > > Section 6 only talks about the library level though. The very next > sentence says that OMEMO should do it's own trust model. > > cheers > Daniel > Cheers, Sebastian > > 2016-10-31 17:36 GMT+01:00 Sebastian Verschoor < > sebastian.versch...@gmail.com>: > > Dear editors, > > > > I have a question regarding Section 6, which states: > > "it may be desirable to have the library consider all keys trusted, > > effectively disabling its trust management" > > The paragraph right below (in Section 7) then describes an attack that > can > > occur if a device simply trusts all devices. These paragraphs appear to > > contradict each other. > > > > Furthermore, the attack described in the first paragraph of Section 7 is > > precisely the attack that was described in the security audit of the > OMEMO > > protocol (See Section 2.2.3 of https://conversations.im/omemo/audit.pdf). > I > > believe that a reference to that audit (or another form of > acknowledgement) > > is in order here. > > > > Best regards, > > Sebastian > > > > ps. Full disclaimer: I am the author of the mentioned security audit. > > > > > > On 31 October 2016 at 11:24, XMPP Extensions Editor > wrote: > >> > >> The XMPP Extensions Editor has received a proposal for a new XEP. > >> > >> Title: OMEMO Encryption > >> > >> Abstract: This specification defines a protocol for end-to-end > encryption > >> in one-on-one chats that may have multiple clients per account. > >> > >> URL: http://xmpp.org/extensions/inbox/omemo.html > >> > >> The council will decide in the next two weeks whether to accept this > >> proposal as an official XEP. > >> > >> ___ > >> Standards mailing list > >> Info: https://mail.jabber.org/mailman/listinfo/standards > >> Unsubscribe: standards-unsubscr...@xmpp.org > >> ___ > > > > > > > > ___ > > Standards mailing list > > Info: https://mail.jabber.org/mailman/listinfo/standards > > Unsubscribe: standards-unsubscr...@xmpp.org > > ___ > > > ___ > Standards mailing list > Info: https://mail.jabber.org/mailman/listinfo/standards > Unsubscribe: standards-unsubscr...@xmpp.org > ___ > ___ Standards mailing list Info: https://mail.jabber.org/mailman/listinfo/standards Unsubscribe: standards-unsubscr...@xmpp.org ___
Re: [Standards] Proposed XMPP Extension: OMEMO Encryption
Dear editors, I have a question regarding Section 6, which states: "it may be desirable to have the library consider all keys trusted, effectively disabling its trust management" The paragraph right below (in Section 7) then describes an attack that can occur if a device simply trusts all devices. These paragraphs appear to contradict each other. Furthermore, the attack described in the first paragraph of Section 7 is precisely the attack that was described in the security audit of the OMEMO protocol (See Section 2.2.3 of https://conversations.im/omemo/audit.pdf). I believe that a reference to that audit (or another form of acknowledgement) is in order here. Best regards, Sebastian ps. Full disclaimer: I am the author of the mentioned security audit. On 31 October 2016 at 11:24, XMPP Extensions Editor wrote: > The XMPP Extensions Editor has received a proposal for a new XEP. > > Title: OMEMO Encryption > > Abstract: This specification defines a protocol for end-to-end encryption > in one-on-one chats that may have multiple clients per account. > > URL: http://xmpp.org/extensions/inbox/omemo.html > > The council will decide in the next two weeks whether to accept this > proposal as an official XEP. > > ___ > Standards mailing list > Info: https://mail.jabber.org/mailman/listinfo/standards > Unsubscribe: standards-unsubscr...@xmpp.org > ___ > ___ Standards mailing list Info: https://mail.jabber.org/mailman/listinfo/standards Unsubscribe: standards-unsubscr...@xmpp.org ___