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

From: Paul Lambert <[email-masked]>
Date: Thu, 1 Sep 2016 13:46:05 +0000

Dan,

The PKEX protocol exchange is completely broken from the perspective of it’s original purpose and requirements documented in IEEE 802.11ai.

>
> 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
>

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.

  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."

The IEEE 802.11ai specification (Draft P802.11ai_D10.0) makes no mention of ‘bootstrapping’ and expresses no limitation on the number of times a public key should be used.

The intent of the IEEE 802.11ai specification use of PKEX (Section 12.7.12.1) is to provide an alternative to PKI based trusted third parties. The text explicitly describes that the ‘trust' provided by PKEX in the ownership of a public key will be used to will be used subsequently as part of signature validation for authentication.

The  protocol was intended to prove ownership of a ‘long-term public key’ that would have meaningful use as a means to represent the entity.

Nowhere in IEEE 802.11ai are the usage constraints of this mechanism described and quite the opposite, the intention of the specification is to prove ownership of a key that will be used multiple times.

PKEX is broken and should be removed or completely replaced in IEEE 802.11ai.

Paul

  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: Dan Harkins <[email-masked]>
Date: Wed, 31 Aug 2016 16:38:47 -0700

On 8/31/16 3:50 PM, Andy Lutomirski wrote:
> On Wed, Aug 31, 2016 at 2:27 PM, Dan Harkins <[email-masked]> wrote:
>>    What is the security flaw in PKEX that makes other protocols "much
>> more secure"?
> Since I still haven't read a full description of PKEX, here are my
> guesses.  None of them depend on the details of the mapping from
> (passphrase, cleartext group element) -> (ciphertext).  If that
> mapping were biased, then additional attacks would be possible.

   Oh, I didn't realize you were making these statements without
actually having seen the protocol.

   See the attached.

   Dan.

> 1. An attacker who has once legitimately paired with one of the
> devices in question and thus knows the public key can apparently
> passively capture a PKEX exchange and brute-force the password.  This
> seems like a rather serious weakness.
>
> 2. I think there's a quadratic brute-force attack if passwords are not
> reused.  Suppose there are N possible passwords.  An attacker can wait
> for a PKEX exchange attempt, capture the messages, and also block the
> messages so it fails.  Then the attacker captures a second PKEX
> attempt between the same two parties.  There are N^2 possible pairs of
> passwords for the first and second attempts.  Since, in general, we
> can expect N^2 << sqrt(2^256) or so (especially if the passwords are,
> say, six-digit numbers, and using six-digit or even four-digit numbers
> for an exchange like this is entirely reasonable if the crypto is
> good), the attacker can simply try all N^2 possibilities to find one
> for which the recovered public keys match.  With high probability, the
> attacker will have recovered both keys and the public key.  You seem
> to be treating the public key as somewhat secret, this already breaks
> it.  If the attacker has full MITM capabilities, the attacker can now
> edit the exchanged messages in the second exchange to substitute his
> or her own keys.
>
> This attack seems complicated, but I can imagine it being fast enough
> to run in real time and hijack a connection.
>
> 3. You have no forward protection against brute-forcing.  A leak of a
> potential long-term secret (the *public bootstrapping key*, since this
> protocol really does seem to think that the public key is secret)
> allows brute-forcing the exchange after the fact.  Real PAKE protocols
> don't have this problem -- the information that needs to be protected
> is ephemeral.
>
> 4. I suspect that, once a PKEX exchange succeeds in the context of
> DPP, a passive eavesdropper will be able to capture enough information
> to be able to evaluate whether a given guess of a party's public key
> is correct.  This enables a full off-line attack on the password.
>
> 5. The really, really easy attack: in the real world, I suspect that a
> lot of PKEX-supporting devices will be things like APs and will also
> have QR codes.  So an attacker can simply read the QR code, learn the
> AP's public key, and then brute force all subsequent PKEX exchanges.
>
> This whole protocol doesn't have a coherent description of exactly who
> does what and what the security properties are supposed to be, which
> makes it very unlikely that provable security is possible.  I wouldn't
> be terribly surprised if I or others could break it further if anyone
> cared to.
>
> If an implementation really never reuses a bootstrapping public key,
> then #1, #2, and #5 don't work.  I find it implausible that devices
> will actually use ephemeral bootstrapping keys, if for no other reason
> than that it would significantly complicate the rest of the protocol.
> And if devices do use ephemeral bootstrapping keys, then evaluating
> whether #4 is a problem cannot be done by simply analyzing PKEX.  One
> would also need to analyze the DPP Authentication protocol to
> determine whether it leaked enough information (to a passive or active
> attacker) to allow checking whether a guess of the bootstrap key is
> correct.  This is, in my book, sufficient reason to reject the entire
> PKEX primitive.  A primitive should be secure on its own without
> regard to the context in which it's used.
>
> 6.2.3 says: The Responder receives the DPP Authentication Request
> message and checks whether a SHA256 hash of the DER encoded ASN.1
> SubjectPublicKeyInfo of its public bootstrapping key is in the
> message. If not, it discards the message and returns to its quiescent
> state. If a hash of its key is in the message, ...
>
> That looks like it could give a clear indication of whether a guessed
> bootstrap key is correct.
>
>
> On another note, this looks like a potential vulnerability;
>
> 6.2.3 further says: If a hash of its key is in the message, it next
> checks whether it has a copy of the Initiator’s public bootstrapping
> key (whose SHA256 hash matches that in the message). If so, and the
> Responder wishes to do mutual authentication, it will perform mutual
> authentication, otherwise it will not perform mutual authentication.
>
> This looks like it might be a way to force a downgrade that prevents
> mutual authentication.
>
>>>
>>> The 802.11 folks already screwed up WPA Personal by failing to use a
>>> real PAKE for silly reasons.  Please don't screw up DPP as well.
>>
>>    SAE is the PAKE in 802.11. But as I said to Paul, PKEX is not SAE.
>>
>>    I would like to understand what you mean by "screw up DPP as well."
>> How is DPP being screwed up by the inclusion of PKEX?
>>>>     The properties listed in in the 802.11ai amendment for PKEX are:
>>>>
>>>>     - the protocol will result in the exchange of trusted public
>>>>       keys or it will fail;
>>>>     - a passive adversary is unable to subvert the exchange, insert
>>>>       any different public keys, learn the public keys, or learn the
>>>>       key/code/word/phrase shared by the two peers;
>>>>     - an active adversary that does not know the shared key/code/word/
>>>>       phrase cannot successfully complete the exchange; and,
>>>>     - an attacker is not able to perform an off-line dictionary attack
>>>>       against PKEX in order to determine wither the public keys or
>>>>       determine the shared key/code/word/phrase.
>>> You aren't actually providing this last property AFAICT.
>>
>>    Why not? If you mean that reusing the same public key with a different
>> key/code/word/phrase then see the quote at the top of this email that
>> started this thread. That is an acknowledged security consideration already.
> Saying it's "an acknowledged security consideration" doesn't make it
> magically stop being a violation of the intended security properties.
>
>>    Please explain how the _protocol_ itself is not providing this property
>> because it's not clear to me what you mean.
> A protocol with a big nasty gotcha like this that's already known when
> the protocol is proposed is unacceptable in my book.  Also, it seems
> considerably more broken than just this gotcha -- see above.
>
> But why oh why is the 802.11 group inventing its own crypto?  It's not
> the 1990s any more.  Use a real primitive.
>
> --Andy