[messaging] SafeSlinger's Ephemeral Fingerprint

[Michael Farb]

On Jul 2, 2014, at 11:26 AM, Trevor Perrin <trevp at trevp.net> wrote:

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

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

I think we can expect the availability and interoperability of more local wireless channels to improve over time. I'd love to see WiFi Direct supported in older devices to broaden its market share. The UX design to use all available wireless channels in some sort of massive discovery mode makes me shudder a little, but we need to do something for those who are getting their standard Internet data channels blocked.

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

I'd love to profile the timing of this modification and see where the crossover exists. I'm a mobile applications software generalist who's been lucky enough to work with security researchers on the implementation of SafeSlinger. I'd like to see what my team thinks of this.

What do we think all? Do we lose anything by a single round in the authentication phase?

Cheers,
Mike