On Sat, Feb 7, 2015 at 5:32 AM, Feng Hao <[email protected]> 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
