[OTR-dev] mpOTR: Todo and Progress

[Matthew Van Gundy]

Thanks for picking up the torch Nadim, I've provided some comments inline...

On Wed, Oct 17, 2012 at 09:31:52PM -0400, Nadim Kobeissi wrote:
> Dear friends,
> Below is a summary of how far we've come with our mpOTR draft, including
> a To Do list (some of the To Dos are inline, the rest are at the end.)
> Your review is appreciated. Thank you!
> 
> 
> 
> ## High-Level Overview
> 
> The mpOTR paper by Ian Goldberg et al. [1] is the basis for the
> cryptography in
> mpOTR. It is lacking in several areas and we felt
> it important to choose specifics for the handwaving parts of the paper
> carefully.  Our implementation is mostly a toy but we believe it is a
> reasonable first stab at creating a simple mpOTR demonstration. With native
> implementations, we believe that mpOTR is a very reasonable encrypted chat
> protocol but our implementation is by no means peer-reviewed and should be
> considered an experiment.
> 
> We have chosen to use elliptic curve cryptography and specifically, we've
> chosen to use (all hail the NSA?) P256, for use with Elliptic curve
> Diffie–Hellman (ECDH) as our ephemeral key agreement protocol,
> Elliptic Curve Digital Signature Algorithm (ECDSA) over P256 as our digital
> signature algorithm (512 bits in length giving 128 bits of security),
> SHA-512 as our hash function (512 bits in length), HMAC as our MAC over
> our hash function (128 bits in length), AES-128 in CTR with a random IV for
> encryption (128 bits of key material, obviously), BASE64 for encoding of
> data,
> keys and HTTP for the transport - we assume HTTPS or Tor Hidden Service and
> consider those details out of scope. These choices should work with other
> protocols such as XMPP as the server is essentially just relaying messages -
> encoding will need to be considered for protocols other than HTTP.
> 
> The original mpOTR paper leaves the group key agreement protocol open.
> We have
> chosen to define the group session key as the hash of secrets from all the
> participants. The secrets are exchanged between each pair of users by using
> Elliptic Curve El Gamal, authenticated by the pair's ephemeral
> signing keys.

These choices all sound good to me.  However, we may want to use a 
full-fleged conference/group key agreement scheme and a better Deniable 
Signature Key Exchange algorithm instead of doing O(n^2) pairwise 
deniable signature key exchanges.  The DSKE we presented in the paper 
was a stop-gap because we didn't have time to fully vet an improved 
version.  The improved version we envisioned went something like [2].  I 
submit it for your criticism.

In other communication, you've complained about performance issues.  Do 
you have any evidence as to where the major performance bottle-neck 
might be?


> Each chat message is encrypted with AES in CTR mode with the group session
> key and signed with the sender's ephemeral ECDSA key.
> 
> Alice, Bob, Mallory, and Eve wish to have a chat using the XMPP
> chat server crypto.cat in the channel '#protocol-spec'.
> 
> Alice generates a long term private/public key pair for verification of her
> identity. She does this once and (optionally) stores it for all time.
> 
> > XXX: TODO: We have not yet implemented persistence of this key or a way to
> >   verify the key.
> >   XXX: TODO: We need to implement binding if we want to bind to specific
> >   servers.
> 
> Currently, any time the list of participants changes, it is necessary to
> re-start the key-agreement protocol. In the future, it may be beneficial to
> periodically re-start the protocol to limit the window in which
> compromise of
> any principal can undermine deniability of messages sent after that
> point.

If the compromised principal is still in the conversation when the new 
session is started, nothing is gained by repeating the key agreement.  
However, periodically closing one session and beginning another can 
protect the confidentiality of messages sent before a compromise (due to 
perfect-forward secrecy).

> At the beginning of the key agreement protocol, each party generates an
> ephemeral ECDSA private/public key pair for the chat session. Each party
> then
> sends its nickname and a random number to the server, which are shared
> by the
> server and used to generate a unique, non-secret session ID which is shared
> between all parties.
> 
> >   XXX: TODO: Enforce binding that each client's value for the channel
> name is
> > consistent. This could be checked in the Assert() message before
> allowing chat.
> 
> Each principal performs a pair-wise deniable authenticated key-exchange,
> multiplexed by the Cryptocat server. Currently, this is an Elliptic Curve
> Diffie-Hellman key exchange authenticated with each principal's
> long-term ECDSA
> key.
> 
> _NOTE: To clarify the above, there are certainly some loopholes with
> plain DH_
> _used by cryptocat. Most notably lack of OTResque SMP thwarting of MITM
> attempts,_
> _which cryptocat does not implement. Therefore, it's highly likely
> Charlie can listen to_
> _and forfeit messages if he owns crypto.cat_
> 
> _mpOTR security derives from the client-to-client channel used for
> exchange of ephemeral keys._
> _-- ezdiy_
> 
> 
> >   XXX: Implement deniability - lucky us, we haven't implemented
> persistence of
> >   identity keys. We get deniability on accident.
> 

What do you mean by "implement deniability"?  Deniability is an inherent 
property due to the choice of key exchange algorithms used in the 
protocol.

> After completing pair-wise key exchange, each party sends messages to
> confirm
> correct receipt of ephemeral keys, as described by the mpOTR protocol.
> 
> Finally, once all users have exchanged ephemeral keys, a group key exchange
> protocol is conducted to derive a group session key. Currently, each party
> generates a 128-bit random value, and exchanges it pairwise with all other
> participants using Elliptic Curve Diffie-Hellman authenticated by each
> principal's ephemeral private key. The group session key is then the hash of
> all principals' random values, arranged lexicographically.

As I mentioned above, it may be more efficient to do a Group Key Agreement 
and Deniable Signature Key Exchange in parallel by augmenting a GKA 
scheme.

> 
> >   XXX: TODO: Prior to chatting, each user must send an Attest() message
> >   committing to the session ID and any other parameters which should
> be globally
> >   agreed upon. This should include in our case the version of the
> protocol, the
> >   timeout (if any), and the name of the chat channel.
> 
> When Alice wishes to send a message to the channel - she encrypts it
> with AES
> in CTR mode using the group session key, signs it with her ephemeral
> ECDSA key,
> and sends it to the server.
> 
> Alice wants to share a message with Bob and so she does...
> 
> >   XXX: File sharing should be documented here
> 
> Alice leaves the chat and sends her private ephemeral signing key to the
> channel. Each party confirms receipt of the key and at that time, the entire
> chat channel re-keys.
> 
> >    XXX: We have not implemented the tear-down steps of the mpOTR paper.

This sounds problematic.  If Alice discloses her ephemeral signing key 
before Bob has learned that she is leaving, a corrupt Mallory in the 
chat session can use Alice's key to impersonate Alice to Bob.  Alice 
should not disclose her key unless she can be assured (either by 
confirmation or timeout via loosely synchronized clocks) that Bob will 
not accept any further messages under her ephemeral signing key.

> Eve is not part of the chat but is able to intercept data sent to and
> from the
> server. Eve is able to learn the nickname of each chat member and to
> watch the
> frequency and size of the messages sent by each party. If she does not
> witness
> the setup phase, she will not learn the participants' nicknames.
> 
> Mallory can use Alice's ephemeral signing key to forge messages that
> appears to
> be from her. Alice can reasonably believe that her ephemeral signing key
> proves
> nothing about her statements after that point.

Technically, even if Alice never publishes her ephemeral signing key, it 
should prove nothing about her statements because her binding to her 
ephemeral signing key is deniable.

> 
> The server is able to learn the nickname, the number of parties, the chat
> channel name, the IP addresses of the client, the timestamps and the size of
> messages.
> 
> > XXX: TODO - Document examples of each part of the protocol and process.
> 
> ***
> 
> 
> ## To Do
> ##### 1. Replay Attack Problem:
> 
> - **Solution:** Every time you send a message, you include the
> "authenticator" of all the messages that have arrived since the last
> time you sent a message. The "authenticator" is a hash chain of the
> messages that lead up to it.
> - The UX will indicate the group confirmation status for each message.
> Messages will instantly be visible but UI will update with confirmation
> status.
> - We need message ordering, for which we can use Byzantine consensus,
> but perhaps we don't need something that strong and we can replace it
> with something weaker.

I think Byzantine consensus is too strong a property here... preventing 
consensus from being reached if even a single participant is temporarily 
unreachable (t, the number of potentially Byzantine participants, is n-2 
in this scenario).  I think that Causal Broadcast is a more appropriate 
solution for interactive conversations.  I've been working on a solution 
for some time, but I've been waiting for it to be published before 
discussing it widely.  I now realize that it may be a while before 
publication, so without further adieu, you can find a working draft of 
the paper at [3].

> ##### 2. setup() / shutdown() issues:
> 
> - Handling potential DoS when Mallory spams joins during the setup phase
> (aka, how to handle new join during session setup)
> - You have to prove that you're allowed to join the chat (via SMP)
> - Overlapping sessions as a potential solution to shutdown()
>   problems

It shouldn't be a problem to transition to a new "active" session even 
if the previous one does not end cleanly.

Cheers,
Matt

[2] http://matt.singlethink.net/projects/mpotr/improved-dske.pdf
[3] http://matt.singlethink.net/projects/mpotr/oldblue-draft.pdf

> - How to decide group membership if different participants disagree (due
> to network issues)
> - Time windows for those in the transport pool (xmpp chat join) but not
> yet in the mpOTR cryptographic chat
> 
> ##### 3. Error cases:
> 
> - We need to know which errors so we can handle them.
> - Authentication, how should it be done?
> - FP verification obviously, but should we support SMP and PSK?
> - Authenticated SMP chats.
> - How does this work in a group context?
> 
> **References**
> > [1] "Multi-party Off-the-Record Messaging", Ian Goldberg, Berkant
> Ustaoglu,
> > Matthew D. Van Gundy, Hao Chen.  CCS '09, November 9-13, 2009,
> Chicago, Illinois.
> > http://www.cypherpunks.ca/~iang/pubs/mpotr.pdf
> > SHA1(mpotr.pdf) = f32d0371d82a295bd5437797f0494071f65342a1
> _______________________________________________
> OTR-dev mailing list
> OTR-dev at lists.cypherpunks.ca
> http://lists.cypherpunks.ca/mailman/listinfo/otr-dev
>