[curves] PAKE use cases

[Trevor Perrin]

On Mon, Feb 9, 2015 at 2:47 AM, Feng Hao <feng.hao at newcastle.ac.uk> wrote:
>>From: Trevor Perrin [mailto:trevp at trevp.net]
>>
>>This sounds like a "device pairing" protocol.  If the devices are
>>nearby and have displays I think "short auth strings" [1,2] are often
>>better than PAKE:
[...]
>
> Yes, it can be used for device pairing -- not the conventional paring for two devices, but for a group of devices in one go. It doesn't rely on the manual checking, so it should be easier to operate than "short auth string", I think.

If devices are nearby and have displays I think SAS is easier (and safer):
 * Easier since SAS allows manual entry or visual comparison, whereas
a password requires manual entry
 * Safer because the SAS is not confidential nor user-chosen


> Also, the devices may be dispersed in remote locations; in that case, it will make "short auth string" more difficult to implement.

If devices are remote then things might change.  But I'm not sure what
use case that is.


>>So are there real use cases for group PAKE?
>
> That's a good question. We can't be too sure until it's actually implemented and used. But if we have a group of people in a conference room and use laptops/tablets/smart phones to exchange data that is sent over the Internet, a group PAKE can be useful in allowing them to set up a conference key, so all the transmitted data are encrypted within the group

That's the use case SafeSlinger (multiparty SAS) was designed for [1,2].

For reasons above I'd prefer SAS over PAKE here.  For UI consistency
I'd prefer fingerprints over SAS.

I'm not saying group PAKE is a bad idea.  But it was work to find
"real" use cases for 2-party PAKE [3].

With group PAKE we don't know the use cases, so we don't know the
requirements - what group sizes should be considered? what are the
communication and computation constraints? what features are needed
(e.g. efficient membership add? group merge? subgroup?), etc.


>>Here's a naive 2-round protocol:
>>
>>Round 1) Each party sends a PAKE ephemeral DH value to all other parties
>>Round 2) Each party generates a secret random "group key share", and
>>uses the pairwise shared secrets to encrypt their share to all other
>>parties.  The shares are hashed to form the group key.
>>
>
> We thought about something similar. I wouldn't call it naïve, as it certainly looks reasonable : ) It shares the similar idea with ours on using broadcast to get the best possible round efficiency. This is however not the common approach in the past work though - if you read Abdalla et al and others' papers, each participant usually only interacts with only the left/right two neighbours.

In real protocols I think the common approach to groups is the most
naive one - encrypt communications pairwise (e.g. PGP).  My proposal
was a simple optimization (send a secret share that gets hashed to a
group key).  A similar optimization is to send a secret key that gets
used for future encryptions from the sender ("sender keys").

But you're right most academic work assumes some ring or tree-based
GKA, without bothering to benchmark against simpler but often superior
approaches.  See my comment on the SafeSlinger GKA [4] for example, or
see George Danezis' lament [5].


>>Feng argues that (c) accomplishes "key confirmation" without needing
>>an extra round.  So when key confirmation is considered, Feng claims
>>his proposal takes 2 rounds compared to 4 for Abdalla and Tang/Choo
>>(and presumably 3 for the naive scheme).
>>
>>However "key confirmation" in Abdalla and Tang/Choo means that each
>>party received a confirmation from every other party that the same
>>group key was computed.
>
> Thanks for raising this good observation.
>
> We need to consider the essential meaning of "key confirmation" in a bit boarder sense.
>
> For example, in two-party authenticated key exchange protocols (based on passwords or PKI), it is typically advised that one should use a different key for key confirmation other than the session key. That is: given a computed raw key material as K, the key-confirmation key may be defined as K1= H(K, 'KC'), while the session key may be defined as K2= H(K, 'ENC').
>
> When one uses K1 to do key confirmation, the success of that operation guarantees the correctness of K1, but K1 is not the actual session key. However, the guarantee logically extends to the correctness of K2 for obvious reasons. This is the approach people have been taking and accepting all along.

Yes, but a confirmation message using K1 confirms K and K2 in the
sense that the sender must have received all messages needed to derive
them.  The confirmation messages in Abdalla or Tang/Choo confirm the
group key in that sense.

After round 2 in your protocol, you've confirmed the pairwise keys but
not the group key - if some party received a wrong round 2 message,
you wouldn't know.

So I think it's accurate to say your protocol achieves some degree of
confirmation earlier than Abdalla (as does the naive approach), but to
confirm the group key would require an extra round.


Trevor


[1] https://www.cylab.cmu.edu/safeslinger/
[2] https://moderncrypto.org/mail-archive/messaging/2014/000483.html
[3] https://moderncrypto.org/mail-archive/curves/2014/000294.html
[4] https://moderncrypto.org/mail-archive/messaging/2014/000499.html
[5] https://conspicuouschatter.wordpress.com/2014/06/28/should-group-key-agreement-be-symmetric-and-contributory/