[curves] PAKE use cases

Mon Feb 9 02:47:15 PST 2015

Hi Trevor,

Thanks for the careful read and useful comments. My response is interleaved below.

>-----Original Message-----
>From: Trevor Perrin [mailto:trevp at trevp.net]
>Sent: 08 February 2015 21:49
>To: Feng Hao
>Cc: curves at moderncrypto.org
>Subject: Re: [curves] PAKE use cases
>
>On Sat, Feb 7, 2015 at 5:32 AM, Feng Hao <feng.hao at newcastle.ac.uk> wrote:
>>
>> On the related subject of PAKE user cases, the following is a case that may be
>of interest to some. The case should be new to many people (at least to me). It's
>about applying PAKE in a group setting for bootstrapping secure communication
>among a set of IoT devices.
>[...]
>> http://homepages.cs.ncl.ac.uk/feng.hao/files/gpake-camera-ready.pdf
>
>
>Cool, thanks!
>
>Feng's paper shows how to construct a group PAKE from a 2-party PAKE,
>which raises good questions:
>(a) Are there use cases for group PAKE?
>(b) If so, is constructing group PAKE from 2-party PAKE the right approach?
>(c) If so, what requirements does this add to the 2-party PAKE?
>
>
>Use cases for group PAKE?
>--------------------------
>Feng's paper motivates group PAKE with the "Internet of Things":
>
>"to deploy a set of out-of-the-box smart devices that do not have any
>preinstalled secrets, one just needs to enter a common password onto
>each device to bootstrap the initial secure communication among the
>group of devices over an insecure Internet."
>
>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:
> * short-auth strings are public values instead of secrets, so no risk
>of shoulder-surfing
> * short-auth strings allow visual comparison instead of manual entry

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. Also, the devices may be dispersed in remote locations; in that case, it will make "short auth string" more difficult to implement. It's less a problem for group PAKE. As long as the same code is entered to various devices, the protocol can take over to establish the group key without needing further human involvement.

>SafeSlinger has shown how to generalize SAS to groups [3].
>
>But I'm not sure when you'd want to pair all devices in a group.  I
>could imagine a "hub" device like a Wifi hotspot being paired to
>"spoke" devices.  Maybe the hotspot can't display an SAS but could
>have a password printed on it.  But that's still not a group PAKE,
>just 2-party PAKEs between each spoke and the hub.
>
>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, and kept private from an outside party, say a three-letter (or four-letter) agency. IoT is very similar.

>Constructing group PAKE from pairwise PAKE
>-------------------------------------------
>It's generally straightforward to construct "group" key exchanges out
>of "pairwise" key exchanges, and this holds true in the PAKE setting.
>
>For example, assume:
> - A 2-party DH-based PAKE exists, like SPEKE, DH-EKE, SPAKE2, etc.
>These PAKEs require a single exchange of an ephemeral, DH-like public
>value to establish a pairwise shared secret.
> - We want to establish a single symmetric key between all parties
>that share the password
>
>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. 

>Some research (including Feng's) seeks a more optimized solution by
>combining PAKE with ring-based Group Key Agreement.
>
>Ring-based GKA extends unauthenticated Diffie-Hellman to groups.  The
>communication pattern is similar to above, except parties broadcast a
>single value in each round, instead of sending unique pairwise values:
>
>Round 1) Each party broadcasts a DH public key
>Round 2) Each party broadcasts a public GKA share.  From these shares,
>a group key is computed.
>
>The parties consider themselves in a ring, and only perform the DH
>calculation with their neighbors.  So after round 1 each party has a
>DH secret N with the next party, and P with the previous party.
>
>There are two variants of ring-based GKA: Burmester-Desmedt [4] and
>Kim-Lee-Lee [5].  To be concrete, imagine a 4-party group.  After
>round 1 there are 4 DH secrets in the group, each party knows two of
>them (P and N) but doesn't know the next two (X and Y).  Computation
>of shares and group keys in BD and KLL is as follows:
>
>BD:
> - public share = N/P   (receive X/N, Y/X, P/Y)
> - group key = P^4 * (N/P)^3 * (X/N)^2 * (Y/X) = PNXY
>
>KLL:
> - public share = P xor N   (receive (N xor X), (X xor Y), (Y xor P))
> - group key calculation:
>   X = N xor (N xor X)
>   Y = X xor (X xor Y)
>   group key = Hash(P || N || X || Y)
>
>
>It's tempting to try to integrate the DH-based PAKEs like SPEKE,
>DH-EKE, etc with GKA for greater efficiency than the "naive" group
>PAKE:
> - In ring-based GKA, the DH computation is done only with neighbors,
>not all pairs (and in BD you can divide the round 1 public values
>instead of the shared secrets to compute N/P with a single DH
>computation).
> - In ring-based GKA, each party in each round broadcasts a single
>value instead of pairwise values.  This is less communication if done
>over a broadcast media or central server.
>
>Feng's paper references several proposals for this.  Some proposals
>are broken, but there may be secure approaches like Abdalla et al's
>combination of BD and DH-EKE [6], and Tang and Choo's combination of
>BD with SPEKE [7].
>
>However, it's unclear whether these combinations actually beat the
>naive protocol for efficiency.  In particular, they require 3
>broadcast rounds to agree on a group key, rather than 2.  At least for
>small groups, I would expect the extra round to cost more time than is
>saved by fewer DH computations.
>
>
>Feng's approach in "SPEKE+" is different:
> (a) BD is run in parallel with pairwise PAKE, and in round 2 the
>pairwise PAKE keys MAC the BD public shares.
> (b) The pairwise PAKE is optimized by each party broadcasting a
>single ephemeral PAKE value in round 1, and reusing it for each
>pairwise PAKE.
> (c) Zero-knowledge proofs are included in round 1 and 2 so that each
>party proves it's executing BD correctly.
>
>If the PAKE allows optimization (b) then this optimization could be
>incorporated into the naive scheme as well, at which point Feng's
>proposal would be less efficient (SPEKE+ adds BD and ZKP overhead to
>the pairwise PAKE overhead).
>
>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.

It's the similar reasoning in SPEKE+. To confirm the correctness of the group key, one doesn't have to use the exact group key for key confirmation, as long as the correctness of the group key is logically guaranteed. This is why we add ZKP to the Burmester-Desmedt protocol at the outer ring of the protocol construction to ensure everyone follows the BD protocol faithfully. Without these ZKPs, the logical guarantee on the correctness of the group key won't apply.

>Key confirmation in SPEKE+ seems to mean that each party received
>values from which every other party *could* compute the same group
>key, *if* they also received those values.  This seems different
>enough that comparing the round counts is inaccurate.  So I don't see
>an advantage to SPEKE+ over the naive scheme (and Feng's J-PAKE+ is
>slower and takes an extra round).
>
>In any case, both Feng's schemes and the naive scheme show how to
>construct group PAKE out of pairwise PAKE, so it's worth considering
>if these constructions add extra requirements for the 2-party PAKE:
>
>
>Requirements for 2-party PAKE used in group PAKE
>-------------------------------------------------
>If you're performing pairwise PAKE with a bunch of parties, it would
>be nice if you could broadcast a single first round ephemeral value
>that gets reused within each pairwise PAKE.
>
>So perhaps ephemeral reuse is worth considering as a desiderata for
>2-party PAKE?
>
>
>Conclusions
>------------
>As a use case, I think group PAKE needs more real-world motivation.
>
>If group PAKE is useful, it seems reasonable to construct it out of
>pairwise, 2-party PAKE - it's unclear whether more complex schemes
>have a significant efficiency advantage (though more research should
>be done).
>
>It seems reasonable to consider ephemeral reuse as a desiderata for
>2-party PAKE.
>
>People agree?
>
>
>Trevor
>
>
>[1] https://moderncrypto.org/mail-archive/messaging/2014/000036.html
>[2] https://moderncrypto.org/mail-archive/messaging/2014/000095.html
>[3] http://www.cylab.cmu.edu/safeslinger
>[4] http://link.springer.com/chapter/10.1007%2FBFb0053443
>[5] https://www.iacr.org/archive/asiacrypt2004/33290243/33290243.pdf
>[6] http://link.springer.com/chapter/10.1007%2F11745853_28
>[7] http://eprints.qut.edu.au/3835/1/3835_1.pdf