[messaging] SafeSlinger's Ephemeral Fingerprint

[Trevor Perrin]

On Wed, Jul 2, 2014 at 4:53 AM, Michael Farb <mwfarb at cmu.edu> wrote:
> I list below an un-scientific
> estimate of the availability of a handful of communication channels for all
> smartphone users (considering current market distribution of all versions of
> iOS, Android, Windows Phone, and Blackberry) to run the protocol which drove
> choosing the use of a server for our first implementation.
[...]
>
> TCP/IP: 100% available, 100% cross-platform, requires an additional out of
> band grouping number, adds network overhead.
> Bluetooth: 100% available, 0% cross-platform (Thanks Apple!), adds some
> discovery time.
> LE Bluetooth: 25% available, 100% cross-platform, adds some discovery time.
> NFC: 25% available, 100% cross-platform, adds some discovery time.
> WiFi Direct: 25% available, 100% cross-platform, adds minimal discovery
> time.

Interesting - I wonder if we can expect this to improve over time?


> After consulting with Adrian (I finally remembered to cc him on this DL)
> about using DH trees, he offers this:
>
> "This paper shows that if communication is slow, then the STR DH tree we are
> using is very efficient:
> https://sparrow.ece.cmu.edu/group/pub/old-pubs/str-toc.pdf
>
> But to scale to larger groups, we should use TGDH:
> https://sparrow.ece.cmu.edu/group/pub/old-pubs/ccs2000.pdf
>
> TGDH should be more efficient than the other options, AFAIK."

This is just optimization, not a big deal.  But I'm not sure the
analysis in those papers is relevant.  I think they assume users are
joining a group one-by-one, which isn't your case.

In your protocol, users have already exchanged ephemeral DH public
keys and Hash(Nm) values with <= 9 other users.  They need to exchange
Nm secrets with confidentiality.

Suppose Alice calculates her DH shared secret (Z) with Bob, and send
Nm to Bob encrypted under a key derived from Z.  Since Nm is already
authenticated by Hash(Nm), a MAC doesn't need to be sent.  So with
Curve25519 this could be a single message from Alice -> Bob of 32
bytes.  To do this with everyone requires a single round where Alice
sends <= 9*32=288 bytes to the server, and then receives <= 288 bytes.

Instead, you're proposing a few rounds of communication to build a
tree of DH secrets and arrive at a group key, followed by everyone
sending their Nm encrypted under the group key.  That seems more
complicated and slower.

Even if the group was several times larger I think it would be slower.
At some point there might be a crossover where the latency costs of
your multiple rounds is more efficient than the bandwidth cost of a
single large round.  But if scaleability to that level is a concern I
would expect a ring-based GKA to be more efficient than a tree-based.
You don't need to support users incrementally joining, so it seems
inefficient to spend several rounds building a tree.

But I'm not an expert on Group Key Agreement, there may be something
I'm missing.


Trevor