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

Sun Dec 29 00:09:00 EST 2013

On 29/12/13 02:17, Trevor Perrin wrote:
> 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.
> 

Hm, you are right. I originally was only thinking about the derived message key. But a network attacker who has sniffed the traffic, i.e. who has A's per-message ephemeral keys (g^ephemeral secret), and later compromises B's ephemeral secret, can re-derive the message keys for all of M1, M2, M3.

It does have better future-secrecy properties, but this is much less important than forward-secrecy, since real-world compromises presumably have the ability to compromise those future "healed" keys too.

George Kadianakis later mentioned to me that there might have been an impossibility result for 1-step ratchets (he can't remember), does that bring anything to mind for you? (If not, then I might keep trying. :p)

> 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.
> 

OK, I see now. This way, the long term keys are only needed at the start; the security of the rest of the conversation only depends on recent history.

Thanks for the comments! IIRC, there was some confusion on when it's important to destroy the secret - I was originally thinking that we should destroy it vaguely "as soon as possible" after sending the corresponding g^secret, leading to my note #3. But the critical thing for optimal forward-secrecy is to destroy it precisely after using it to decrypt *one* message, and also to convince the other participants to only use g^secret for *one* encryption.

X

> 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
>>

-- 
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/20131229/98b59e3c/attachment.pgp>