[OTR-dev] mpOTR and the road ahead ...?

[Ximin Luo]

On 22/01/14 03:44, Guy K. Kloss wrote:
> Hi Ximin,
> 
> On 22/01/14 15:28, Ximin Luo wrote:
>> Away from the overall mpOTR discussions, I spent a lot of time on
>> the side talking about forward-secrecy ratchets with Trevor. We also
>> talked about the advantages and disadvantages of a pair-based system.
>> (This is opposed to a group-based system that most others are
>> thinking about). We and some others think it would be worth pursuing
>> this further, with the understanding that this would not scale to
>> massive groups. Despite this, the advantages are:
> 
> Personally, I'd take the position here on group-based systems ...
> 
>> - strong security properties (inc. deniability) can be implemented
>> in a much simpler way
>> - there is individual control over group decisions like join/part/expiry
>> - the overhead can be made independent of the message size, so only
>> linear in the number of participants
>> - no need for complex key exchanges, easier to make work for the
>> high-latency case (inc. store-and-forward)
> 
> I can see those advantages, but these are the immediate disadvantages I
> can see:
> 
> * Key agreement, though easier conceptually, involves many more message
>   exchanges. If everyone needs to exchange keys with everyone, we're in
>   an O(n^2) situation. If we'd use (just for simplicity reason) a
>   Group Diffie-Hellman key agreement, we're already in the O(n) range
>   of message exchanges. And I believe that message exchange latencies
>   can play a major role in a secure group chat protocol.
> 

I haven't looked into this area much myself, but the people I talked to so far seem to think a group key exchange in the style of DenAKE would be O(n^2). I'd be interested in hearing more about what you have.

In a pair-based system, the size might be technically O(n^2) but you can group this into O(n) "broadcasts" if it suits the primitives of the underlying protocol. In a typical multiparty conversation, people join at different times anyway, so I think this is acceptable.

In my model, you don't need to re-key on join/part, so each join is a constant number of broadcasts to key-agree with the new joiner (details to be worked out), and each part/expiry is free. There is additionally an n-step broadcast "decision making" step, total size O(n^2); I'm not sure anyone has thought about this yet in the context of a group-based system.

> * There's the need to ensure that all participants will receive *the
>   same* message, when encrypted/signed for each participant
>   individually.
> 

I believe you achieve this for free when you have content-addressed messages, which is what you need to do anyways to implement parent pointers for message partial-ordering. (See the OldBlue paper for details, TL;DR version is it's like the git object model with slightly different semantics for the parent pointers.)

> As for the first point, I've started working on a simple GDH
> implementation, which should be quite suitable for groups in the order
> of magnitude around 10 users, and getting more difficult around 100. To
> keep messages small and computational overhead small, I'm currently
> doing Curve25519-based scalar multiplication chains rather than
> classical DH exponentiation.
> 
> As a logical progression from there Ed25519 ephemeral signatures would
> work well in this scenario as opposed to doing vanilla DSA or RSA.
> Having said that, I think it'd still be a good idea to keep using the
> long term DSA secret of OTR for the initial participant authentication.
> 

Cool, please keep us updated!

>> Additionally, doing work in this area lets us explore issues like
>> transcript consistency and the expiry of participants in more depth,
>> without worrying too much about group key exchanges. The lessons
>> we'll learn will probably be useful for group-based approaches too.
> 
> For sure!
> 
>> To be clear, only a subset of people support this direction, but I
>> think it can lead to somewhere concrete much faster than a
>> fully-generalised mpOTR strategy will.
> 
> Agreed. As I had indicated in an earlier mail, I'm also looking at an
> "evolutionary" approach, which will not do the full mpOTR monty off the
> bat, but start with group encryption first.
> 
>> I've started writing up more technical notes but they're not ready
>> for public consumption yet. The general strategy is to extend a
>> ratchet that is aware of message partial-ordering to multiple parties,
>> then add a join/part/expiry protocol on top of this. Note, I'm not
>> just "going in blind", I have thought about the latter before already
>> , in a way that fits into a partial-ordering model.
> 
> Really looking forward to that.
> 
>> (I'd be happy to talk more technical details over IM; this email
>> address is also an XMPP address.)
> 
> Just added you to my messenger. I'm xemacs at jabber.org.
> 
> Guy
> 

-- 
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/20140122/836e8ccf/attachment.pgp>