Discussing XMPP E2E Encryption - Part I

THIS DOCUMENTS REFERS TO A DRAFT VERSION OF THE OMEMO XEP OF LATE AUTUM 2015 THAT IS NOW OUTDATED AND OBSOLETE

THIS DOCUMENTS REFERS TO A DRAFT VERSION OF THE OMEMO XEP OF LATE AUTUM 2015 THAT IS NOW OUTDATED AND OBSOLETE

THIS DOCUMENTS REFERS TO A DRAFT VERSION OF THE OMEMO XEP OF LATE AUTUM 2015 THAT IS NOW OUTDATED AND OBSOLETE

Introduction

In the following series I would like to sketch out a system for end-to-end encrypted messages based on the infrastructure given by the XMPP standard. This is motivated by the recent motion to establish a successor for OTR, which in its current form lacks features like concurrent active devices.

This is meant as a comment on the OMEMO XMPP Extension Protocol (XEP) draft proposed and implemented by the XMPP client project conversations.im[XEP].

Assumptions & Promises

The XEP chooses to use the encryption scheme and data format developed by Whispers Systems and used by their TextSecure application. Their protocol is based on a encryption scheme proposed by the developers at Whisper Systems. The scheme is referred to as Axolotl though there exist many different flavours of it. They released a reference library called libaxolotl supporting all three “protocol” versions used by their software [axolotl].

The Axolotl encryption scheme has been put under public domain and the library is under the GPLv3 license. However to this date there is no proper specification of the reference implementation by Whisper Systems, which makes it hard to discuss the properties and impossible to independently implement the underlying crypto system as well as the XEP draft.

All variations and supposedly the variant used in version 3 of the reference library which the XEP Draft uses give the following promises:

Additionally it is based on the following assumptions on the transport medium:

By specification, XMPP gives us different assurances about the transport of messages:

Supporting out of order messages while maintaining PFS adds significant complexity to decryption and key management and is unnessecary for the use-case of XMPP and thus should be discarded. In the following I will mainly describe a ‘drop-in’ encryption scheme tailored to the XMPP use-case while keeping the security promises.

Encryption Scheme & Cryptographic Primitives

The scheme uses the triple ECDH (3DH) proposed by axolotl. The rest of the system is inspired by both the axolotl rachet and the minimaLT key rollover. [axolotl] [minimalt]

The basic idea is, instead of having one rootkey which derives branches of subkeys, to have two symmetric keys, one for each partner, that are rolled over (hashed) with each message. Additionally each side has a message counter which serves as NONCE and mechanism to handle lost messages. The longterm identity keys are understood as per device as described in the draft.

The proposed cryptographic primitives are SHA256, SHA512, Salsa20 with Poly1305 and ECDH with X25519. Salsa20Poly1305 with a 256-bit key has been recommended in the PQCRYPTO groups initial report [pqgroup] for post-quantum secure sytems. While ECDH is not post-quantum secure these primitives are still preferred to ease upgrading when post-quantum secure replacements for ECDH are available. In future the Supersingular Isogeny Diffie Hellman Key-Exchange [SIDH] could be such a replacement.

Session

Each party stores the following values per session in persistent storage:

Key Exchange

The variables lEH and rEH are per session generated as so called ephemeral keys. It is vital that the emphemeral key material is safely discared after the first chain key is generated. Otherwise the PFS property would be violated.

if lEH < rEH:
	localChainKey,  remoteChainKey = SHA512(ECDH(lID, rEH) || ECDH(lEH, rID) || ECDH(lEH, rEH))
else:
	remoteChainKey, localChainKey  = SHA512(ECDH(rID, lEH) || ECDH(rEH, lID) || ECDH(rEH, lEH))

ZERO(lEH) #this is a MUST not a MAYBE

Encrypt messages 

message = (localCounter, ENCRYPT(plaintext, localCounter, localChainKey))
localCounter = localCounter + 1
localChainKey = SHA256(localChainKey)
return message

Decrypt messages

The variables pCounter and ciphertext are parsed from the incoming message that is to be decrypted.

if pCounter == remoteCounter:
    if not plaintext = DECRYPT(ciphertext, remoteCounter, remoteChainKey):
        return decryption failed
    remoteChainKey = SHA256(remoteChainKey)
    remoteCounter = pCounter
    return plaintext

if pCounter > remoteCounter:
    pChainKey = remoteChainKey
    for i = 0 in pCounter-remoteCounter:
        pChainKey = SHA256(pChainKey)

    if not plaintext = DECRYPT(ciphertext, pCounter, pChainKey)
        return decryption failed

    #The message is authentic thus the session is updated
    remoteChainKey = pChainKey
    remoteCounter = pCounter

    return (plaintext,  message loss)

#The message can be discarded
if pCounter < remoteCounter:
    return out-of-order violating specifications

Issues

Integer overflow & Cylic Hashing

Hashing a key successively many times will eventually lead to a “rho” cycle. There could be cases where a key runs into a even smaller cycle. Setting the counters to a size of 32bit and terminating the session in case of an overflow would reduce the probability for hitting such a case. [inv1] When a overflow occurs the communication partners would establish a new session based on fresh ephemeral key material following the procedure in §5 of the draft. [XEP]

Multi-use of PreKeys

§5 states among others:

Clients SHOULD NOT immediately fetch the bundle and build a session as soon as a new device is announced. Before the first message is exchanged, the contact does not know which PreKey has been used (or, in fact, that any PreKey was used at all). As they have not had a chance to remove the used PreKey from their bundle announcement, this could lead to collisions where both Alice and Bob pick the same PreKey to build a session with a specific device. As each PreKey can only be used once, the party that sends their initial PreKeyWhisperMessage later loses this race condition. This means that they think they have a valid session with the contact, when in reality their messages are ignored by the other end. By postponing building sessions, the chance of such issues occurring can be drastically reduced. It is RECOMMENDED to construct sessions only immediately before sending a message.

Several parties using the same ephemeral key to establish a session is not problematic from a security point of view. Additionally to the recommended behaviour of constructing a session on demand the receiving device could hold onto the removed key until shortly after the bundle update. This would circumvent the problem of several devices concurrently trying to establish a session and losing the message sent by the party that lost the race.

Authentication

Yet to be discussed is the authentication. The draft as well as the here presented encryption scheme assume that the longterm public keys can be trusted. By incorporating them into the 3DHE they authenticate the communication. The draft should offer mechanisms similar to the shared secret authentication used by OTR to authenticate peer devices.

The cross device authentication feature should also be described. This feature enables an already trusted device to announce trusting an untrusted device by signing the untrusted device key and announcing it to the communication partner.

Lost messages

The detection of lost messages could be communicated to the partner.

Changelog

09.10.2015 - Initial publication

References 

XEP:              XEP-XXXX: Proposal for the OMEMO Encryption
                  http://conversations.im/xeps/multi-end.html

                  XEP-0163: Personal Eventing Protocol
                  https://xmpp.org/extensions/xep-0163.html

pqgroup:          Initial recommendations of long-term secure post-quantum systems
                  http://pqcrypto.eu.org/docs/initial-recommendations.pdf

minimalt:         MinimaLT: minimal-latency networking through better security by W. M. Petullo, X. Zhang, J. A. Solworth, D. J. Bernstein, and T. Lange
                  https://dl.acm.org/citation.cfm?doid=2508859.2516737

axolotl:          Public Domain specification of Axolotl
                  https://github.com/trevp/axolotl/wiki

                  Blog Entry explaining the Axolotl Ratchet
                  https://whispersystems.org/blog/advanced-ratcheting/

                  Reference implementation in Java
                  https://github.com/WhisperSystems/libaxolotl-java
SIDH:
                  Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenis by Luca de Feo, David Jao, and Jérôme Plût
                  https://eprint.iacr.org/2011/506.pdf

                  Isogeny-based quantum-resistant undeniable signatures by David Jao and Vladimir Soukharev
                  http://cacr.uwaterloo.ca/techreports/2014/cacr2014-15.pdf

inv1:             Missing sources discussing this for SHA256 and in general.
                  Estimations of rounds for 256bit sized function would be good.
                  StackOverflow source call it dismissable for real world impact.