[OTR-dev] 1-step 3DH ratchet, no handshakes, useable for small-scale mpOTR

[Ximin Luo]

I realise how this must sound; I am sure I made a mistake somewhere. :)

I *have* spotted one irregularity which *potentially* could lead to a side-channel attack; please read on.

But if I got everything right, it does provide deniability and forward-secrecy.

## 2-party case

No key agreement - I am not trolling! (But note #1 talks about initialisation, a special case.)

Transmitter T sends a message M with msgID i to receiver R.
M = (g^ephem_sec_of_T, P = parents of M, AuthEnc[k](P, plaintext)); i = hash(M)

- A new random ephem_sec_of_T is generated for each message, and is stored until as described in note #3.
- k is generated via 3DH as below.
- The parents point to the last non-replied-to messages that T knows about, similar to OldBlue[3] and git.
  - This lets us reduce the 2-step Axolotl ratchet[2] to a 1-step 3DH[1] ratchet; the recipient can infer k too.
  - In the 2-party case, there is only one parent; I say parents because this generalises to mpOTR - see later.
- plaintext P is a potential problem, even though it is also under AuthEnc
  - P must be plaintext to infer k in the first place
  - P must also be AuthEnc, since multiple P can lead to the same k
  - would be good to prove this is safe

R executes the following, to verify-decrypt the ciphertext:

1. In the 2-party case, P contains one single ID, sent by R. Find the message with this ID, it contains an g^ephem_sec_of_R.
2. Find ephem_sec_of_R, stored from earlier.
3. Generate k using 3DH[1]:
   k = KDF ( g^ephem_sec_of_T ^ ID_KEY_of_R,
             g^ephem_sec_of_R ^ ID_KEY_of_T,
             g^ephem_sec_of_T ^ ephem_sec_of_R )
   assuming all public ID_KEYs are validated, this protects against MitM
4. Verify-decrypt using k.

Non-rigorous justification ("pseudo-proof") for security:
- auth/conf from AuthEnc[k] - k is known only to R, T
  - assuming plaintext P is OK
- fwd-sec from per-message g^ephem_sec_of_T, plus forgetting keys as per note #3
- deniability from 3DH, all values are forgeable, no signatures anywhere
- no "initial key agreement" necessary (but see note #1)

3DH, OldBlue and Axolotl work together to protect against MITM, provide den, fwd-sec, and auth/conf.

## Multi-party case

- Naive extension: T needs to generate a k for each recipient, and AuthEnc for each. This is not as efficient as we'd like.
  - also, probably better to let i = hash(g^ephem_sec_of_T, P, plaintext)
- each R finds the correct ephem_sec_of_R by following P's ancestors until it finds a message authored by itself.
  - This message is unique, even when each message may have multiple parents, due to the consistency properties of OldBlue DAG transcripts - messages from one single author are totally-ordered, it is the full transcript that is only partially-ordered.
- pairwise keys only, no group handshake

## Notes

1. To ensure there is always a "last-sent-message", we can start a convo with everyone announcing their first g^ephem_sec. This means we need to wait for everyone before the conversation can begin; this potentially can be improved.
2. As-described, there is no concept of "a conversation", so you can't have 2 separate conversations with the same set of participants. We can easily add a channel-id for each message, though. This can be picked by the conversation initiator.
3. T needs to keep each ephem_sec_of_T until they know that all recipients have received and verified his message, in case he must resend it. This can be done by waiting until (r sends a message with M as an ancestor, for all r).

## Story

- George Danezis asked me how Paxos worked. I asked why he was asking the question (since nobody solves byzantine just for the sake of it :p) and he mentioned mpOTR.
- I remembered the previous otr-dev discussion about consistency, and how the DAG transcript turns consistency into a non-byzantine problem. "I don't need to rely on others to act myself."
- We need a 1-step ratchet to turn key agreement into a non-byzantine problem. I started reading up on the Axolotl algorithm.
- An initial misunderstanding had me modelling that protocol with a 3DH ratchet rather than a DH ratchet.
- I eventually realised it could be turned into the above algorithm.

[1] https://whispersystems.org/blog/simplifying-otr-deniability/
[2] https://whispersystems.org/blog/advanced-ratcheting/
[3] http://matt.singlethink.net/projects/mpotr/oldblue-draft.pdf

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 897 bytes
Desc: OpenPGP digital signature
URL: <http://lists.cypherpunks.ca/pipermail/otr-dev/attachments/20131228/d3ce5df1/attachment.pgp>