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

[Ximin Luo]

(Wrapping up some loose ends, since some stuff I said previously was wrong, and I don't want to confuse anyone that might stumble upon this thread in the future.)

On 29/12/13 05:56, Trevor Perrin wrote:
> On Sat, Dec 28, 2013 at 9:09 PM, Ximin Luo <infinity0 at gmx.com> wrote:
>> 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.
> 
> Agreed that a per-message sender ephemeral key gives more immediate
> "future secrecy".
> 
> We considered adding that to Axolotl, but there's no great option for
> which recipient key to use for the DH:
>  - if you use the recipient's identity key, you have a roll-over
> problem and no "self-healing"
>  - if you use the recipient's ratchet key, then the ratchet key has to
> be kept around for longer, so there's a security trade-off
> 
> So you'd probably have to add another recipient ratchet-type key for
> use with the sender's per-message ephemeral.  It didn't seem worth the
> cost in complexity (and also increases computation and message size).
> 
> 
>> 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)
> 
> I'm not totally sure what you mean by 1-step ratchet, so I'm not sure.
> 

I had to think through my original vague intentions a bit more precisely. By 1-step ratchet, I meant a ratchet whose full security properties are achieved from one single transmission, without waiting for a reply. The SCIMP hash-based ratchet would fall into this category, so I suppose it is indeed possible.

But I also realise now that what I proposed above is not actually 1-step, but still 2-step, since it requires a reply message in order to achieve future-secrecy. And the initial broadcast of ephemeral keys is basically a 2-step handshake. (My original aim was to try to get rid of handshakes completely, because I thought that would make mpOTR much easier. But this is probably impossible; forward secrecy seems to require some session state.)

In the meantime, I've continued to explore per-message ephemeral keys (better future-secrecy), triple-DH ratcheting (less complex protection against MitM), and the parent pointers (better recovery), taking into consideration the problems you brought up. I need to write it up in more detail[1], but I think I'll have something interesting to show by RWC.

> 
>>> 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.
> 
> Right, that's how it's done in TextSecure and Pond.
> 
> 
> Trevor
> 

[1] https://people.torproject.org/~infinity0/res/combo-ratchet.svg

-- 
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/20140109/a429df66/attachment.pgp>