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

[Trevor Perrin]

Hi Ximin,

I think this has worse forward-secrecy than Axolotl [1].

Suppose Alice sends a stream of messages (M1, M2, M3) to Bob.  With
Axolotl, Bob destroys the key for each message immediately after
decrypting the message.

With your ratchet, Bob cannot do this, since (M1, M2, M3) are all
encrypted to Bob's same secret keys.

As far as using a TripleDH instead of a single DH for each ratchet
message: we decided against that, since it makes key rollover harder.
Alice might periodically wish to destroy her old identity key and
introduce a new one, and it seemed better for this not to interrupt
all of Alice's conversations.

Trevor

[1] https://github.com/trevp/axolotl/wiki



On Sat, Dec 28, 2013 at 2:49 PM, Ximin Luo <infinity0 at gmx.com> wrote:
> 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
>
>
> _______________________________________________
> OTR-dev mailing list
> OTR-dev at lists.cypherpunks.ca
> http://lists.cypherpunks.ca/mailman/listinfo/otr-dev
>