[OTR-dev] 1-step 3DH ratchet, no handshakes, useable for small-scale mpOTR
infinity0 at gmx.com
Sat Dec 28 17:49:45 EST 2013
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 and git.
- This lets us reduce the 2-step Axolotl ratchet to a 1-step 3DH 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:
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
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).
- 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 897 bytes
Desc: OpenPGP digital signature
More information about the OTR-dev