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

[Guy K. Kloss]

On 23/01/14 02:26, Ximin Luo wrote:
> 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.

Well, yes. As you're also discussing below, that raises the question as
to how one defines big-O in this case. From a client's or overall
perspective. The GDH, that I'm looking at, uses (n - 1) directed
messages and one broadcast, therefore having each client process O(n)
messages, and send O(1), which overall would lead to O(n^2) messages to
process as well, while only having to transport O(n).

From my point of view, the expensive part in these schemes is the
network latency, so the message transports should be viewed
particularly, leading to O(n).

Side note: A Tree-based Group Diffie-Hellman (TGDH) would be still more
efficient, but also more complicated to implement, so I didn't bother
with it, yet. And GDH still seems well suited for the envisioned use
case of around and below 10 users that I'm mostly worried about.

Another potentially expensive part is generating new (private) secrets,
particularly if it is for DSA or RSA. So another factor for
consideration is to minimise the number of secrets that need to be
generated individually. However, this factor can be mitigated by
choosing crypto primitives that put much less load on the system in
terms of number of bytes entropy required and the complexity of
evaluating those secrets (thus my choice of Curve25519 and Ed25519 for
my current considerations, with the additional side benefits of
minimising message size).

Another question raised for me is towards what extent deniability needs
to go. mpOTR can be a complex beast, and with growing group sizes the
chance of all participants being "well behaved" decreases (e. g. when
publishing private signing keys for the session on termination).

I'll have to have a closer look at denAKE again and see how that would
compare. After all, denAKE doesn't *just* do the group key agreement,
but also authentication of the parties. Anyway, as far as I recall,
Goldberg's original mpOTR paper still left the group key agreement
process pretty much unanswered, if I recall correctly.

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

That is very true for the client's perspective, however any type of
infrastructure will still have to handle O(n^2) messages, and clients
have to process O(n^2) incoming messages. Though, this will likely be
more efficient than doing them "on the raw" for the infrastructure, and
the broadcasts don't have to be handled sequentially.

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

That's the same when using GDH. You've got an IKA (initial key
agreement) process to bootstrap your secret group key. With the set of
intermediate keys, you can very easily join or disconnect group members
with very limited effort (1 point-to-point message + 1 broadcast message
to the group).

Guy

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: OpenPGP digital signature
URL: <http://lists.cypherpunks.ca/pipermail/otr-dev/attachments/20140123/ecafc4db/attachment.pgp>