[messaging] Key exchange and DuplexWrap-like protocols

[Michael Hamburg]

Hello Messaging,

I was reading over the Keyak submission to Caesar, and I had a hopefully-interesting idea regarding key exchange.  It needs some fleshing out, particularly regarding concurrency, but here goes.

The DuplexWrap design (used in Keyak) supports the following interface:

DuplexWrap.init()
(ciphertext, tag) = DuplexWrap.wrap(header, body, tag length)
body = DulpexWrap.unwrap(header, ciphertext, tag)
DuplexWrap.forget()

The DuplexWrap object is stateful.  It treats a successful unwrap() call the same as a wrap() call with the same parameters, and an unsuccessful unwrap() call destroys the object.  The header, body, ciphertext and tag may be empty.  The forget() call is a forward security barrier.

The security claim is that unwrap will only succeed if the entire history of the duplex object is the same on the sending and receiving sides, and (ciphertext, tag) was the output of wrap(header,body,tag length).  The exception is that tag lengths are kind of fuzzy: the DuplexWrap object only remembers the number of blocks used in the tag.  We’re going to use fixed-length tags so it doesn’t matter.  Effectively, the headers act as keys and/or authenticated data, and the bodies are plaintext.

OK, onto the idea.

Suppose Alice and Bob are talking with a strictly non-concurrent protocol, i.e. one in which only one party has permission to talk at a time.  This is the case for many key exchange protocols, and also for a fair number of protocols on the general Internet.  Both Alice and Bob start with an empty DuplexWrap object.  To send a message to Bob, Alice wraps the message with DuplexWrap, possibly with a header, possibly prepends length information, and sends it.  Then Bob unwraps the object.

So what?  Well, this results in a really simple private key exchange protocol, comparable to Noise.  Each party uses a tag length of 0 except at the end of their flow, when they use a fixed (eg 128-bit) tag length.  Alice’s first flow doesn’t use a tag.

Alice: Body(g^x).
Bob: Body(g^y).  Header(g^xy), Body(Bob’s cert on g^B).  Header(g^Bx).
Alice: Body(Alice’s cert on g^A).  Header(g^Ay).  Body(false-start data).
Bob, Alice: More messages.

This has the same security properties as Noise, but only uses ECC and Keccak.  That is, Bob’s certificate is hidden from a passive attacker, and Alice’s certificate is hidden from an active attacker, and both sides can repudiate the conversation.

If Alice is authenticating with a password, she can just throw its hash into a Header at some point.  You could also use this structure for a PAKE protocol.  It would work like other PAKE protocols, except that it’s very clear how to perform it under an ephemeral DH session to protect the user name.

Once the handshake is complete, Alice and Bob will want to communicate concurrently.  Probably the easiest way to do this is to clone the duplex object, and toss in a header “Alice to Bob” on one side and a header “Bob to Alice” on the other.  Once the connections are set up, you can ratchet them at will, either in a simple way (using forget()) or by incorporating new DH ephemerals as in Axlotl.

Thoughts?

— Mike