Subject: Re: [T2TRG] [Cfrg] Wi-Fi Alliance Device Provisioning Protocol (DPP) - Draft Released for Public Review and Comments

From: Paul Lambert <[email-masked]>
Date: Wed, 31 Aug 2016 23:55:44 +0000

I¹ve made a short summary of the PKEX protocol below. Comments and
corrections would be appreciated.

Assuming my summary is correct ...

If a third party Carol with P_c knows the MAC address and public key of
Alice (MAC_a and P_a) a MiTM attack is possible.

1) Alice and Bob share a one-time passphrase to bootstrap connectivity and
learn each others associated public keys.
2) Alice
   - calculates Pwe_ab = huntandpeck(passphrase_ab)   # passphrase between
Alice and Bob
   - calculates Q_a = H( MAC_a ) * Pwe_a
   - sends Commit with nonce_a and C_a = P_a + Q_a
3) Carol intercepts Alice¹s Commit and having met Alice, know¹s P_a and
MAC_a
   - calculates  Q_a = (C_a - P_a)
   - creates spoofed commit as
      C¹_a = P_c + Q_a
   - send spoofed commit with nonce_c and C¹_a
4) Carol continues PKEX exchange with Bob using MAC_a
5) At end Bob thinks P_c belongs to MAC_a

Paul

- - - PKEX Summary - - -

For two entities Alice and Bob:
 - subscripts indicate entity (e.g. P_a for Alice public key)
 - operating on additive group
 - with generator G on a 'curve'
 - with hash H()
 - and huntandpeck(Point,curve) as defined in 802.11mc
 - scalars are lower case group element (Points) in upper case

Each peer has a long term public key:
   P_a = s_a * G
   P_b = s_b * G
 and MAC addresses
   MAC_a
   MAC_b

Each peer shares by out-of-band a string 'passphrase'

The following is a view of PKEX processing from Alice's perspective:

Pwe_a = huntandpeck( passphrase, curve ) # a point on the curve
m_a = H( MAC_a )
Q_a = m_a * Pwe_a
C_a = P_a + Q_a
nonce_a = random()

Alice ---> Bob   sendCommit( nonce_a, C_a )  from MAC_a
 
Alice <--- Bob   sendCommit( nonce_b, C_b )  from MAC_b

m_b = H(MAC_b)
Q'_b = m_b * Pwe
P'_b = C_b - Q'_b
k = KDF(s_a*P'_b', nonce_a, nonce_b)

Alice ---> Bob  sendCommit( HMAC-Hash(k, P_a || P'_b || MAC_a || MAC_b) )
Alice <--- Bob  sendCommit( HMAC-Hash(k, P_b || P'_a || MAC_b || MAC_b) )

Alice validates that Bob¹s commit message is correct and if so:
 - Alice has demonstrated ownership of P_a to Bob
 - Bob has demonstrated ownership of P_b to Alice
 - no pair-wise shared key is available

>
>>
>>On 8/31/16 12:03 PM, Paul Lambert wrote:
>>> Yes, PKEX is not SAE, but they share the same underlying PAKE
>>> cryptographic processing
>>
>>   That is not true. They both use a secret group element that is derived
>>from a password but the exchanges are completely different.
>
>Yes - the protocols are very different.
>
>My original point was that it is difficult to fully evaluate PKEX without
>having the text for SAE that includes field definitions and important
>aspects of the cryptographic processing.
>
>Both PKEX and SAE use the identical textual specification that describes
>the hunt-and-peek mapping of a passphrase to a group element.  This
>mapping is a fundamental aspect of the PAKE processing and makes SAE and
>PKEX both members of the class of PAKE algorithms that operate by the
>mapping of a passphrase to a group element (point on ECC curve).
>
>The demonstration of knowledge of this group element is very different for
>the two protocols.
>
>Paul
>
>>
>>   Dan.
>>
>>
>
>_______________________________________________
>T2TRG mailing list
>[email-masked]
>https://www.irtf.org/mailman/listinfo/t2trg

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 31 Aug 2016 17:14:08 -0700

> 5) At end Bob thinks P_c belongs to MAC_a

Nifty!  IMO that's a rather serious problem -- no brute forcing is needed.

I can improve my quadratic attack, too.  Suppose Carol can convince Alice
to run the protocol twice with different passwords pw1 and pw2.  (The two
runs don't even need to be with the same peer.)  Carol learns Q1_a - Q2_a.
With high probability, Carol can now jointly bruteforce pw1 and pw2 without
needing to know P_a.  Now Carol can calculate P_a.

Of course, having done so, Carol can now run your attack to MITM any
further exchanges involving Alice.

So I guess that passive observation of two protocol runs almost completely
breaks PKEX.

--Andy

---

From: Dan Harkins <[email-masked]>
Date: Wed, 31 Aug 2016 17:53:26 -0700

On 8/31/16 5:14 PM, Andy Lutomirski wrote:
>
> On Aug 31, 2016 4:55 PM, "Paul Lambert" <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >
> >
> I can improve my quadratic attack, too.  Suppose Carol can convince 
> Alice to run the protocol twice with different passwords pw1 and pw2.  
> (The two runs don't even need to be with the same peer.)  Carol learns 
> Q1_a - Q2_a.  With high probability, Carol can now jointly bruteforce 
> pw1 and pw2 without needing to know P_a.  Now Carol can calculate P_a.
>
> So I guess that passive observation of two protocol runs almost 
> completely breaks PKEX.
>

   What you both seem to have noticed is what is already mentioned in 
the DPP spec
that you both have quite obviously read. Namely,

   "This bootstrapping technique [PKEX] should never be run multiple 
times with
the  same code. Using this bootstrapping technique more than once with a 
different
code but the same bootstrapping key can enable a dictionary attack."

   There are usage constraints. Go beyond them and your assumptions are not
valid anymore. This is true for all of the boostrapping techniques used in
DPP. The NAN-based method assumes the peers are in close proximity and 
that no
adversaries are. A bold assumption-- when there are no adversaries, the 
exchange
is secure! All security is lost if that's not true-- i.e. it "completely 
breaks".
Yet some people still want to use it because they seem comfortable with 
those
usage constraints.

   These bootstrapping techniques are trying to establish "trust" out of 
whole
cloth, or damn near whole cloth. The usage constraints are being mentioned
honestly so people know how to use them and what they're getting when 
they do.
If you think the usage constraints make a particular bootstrapping 
technique be
effectively worthless that is useful information I guess but that 
doesn't mean
it's completely broken.

   Dan.

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 31 Aug 2016 18:33:05 -0700

>> I can improve my quadratic attack, too.  Suppose Carol can convince
Alice to run the protocol twice with different passwords pw1 and pw2.  (The
two runs don't even need to be with the same peer.)  Carol learns Q1_a -
Q2_a.  With high probability, Carol can now jointly bruteforce pw1 and pw2
without needing to know P_a.  Now Carol can calculate P_a.
completely breaks PKEX.
>
>
>   What you both seem to have noticed is what is already mentioned in the
DPP spec
>   "This bootstrapping technique [PKEX] should never be run multiple times
with
different
> valid anymore.

Then perhaps the design should change to something that doesn't have these
constraints.  This wouldn't be particularly difficult.

I, for one, find it implausible that any real implementation will above by
the constraints.  And I still think it's broken even if you do abide by the
constraints due to the existence of oracles that can test a bootstrapping
public key