[curves] PAKE use cases

Sun Feb 8 13:48:43 PST 2015

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

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?

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.

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.

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