Subject: [Cfrg] SPM2 -> was Re: SPAKE2+mbDH a PAKE+PKA

From: Paul Lambert <[email-masked]>
Date: Mon, 3 Oct 2016 23:05:15 +0000

Dear Stanislav,

Based on your comments, I’ve made another cut at combining SPAKE2 and mbDH. This should not have the problem you identified in the earlier version. The combination more directly performs the protocols in parallel.

https://mentor.ieee.org/802.11/dcn/16/11-16-1329-00-00ai-pkex-alternatives.ppt

Best Regards,

Paul

From: Paul Lambert <[email-masked]<mailto:[email-masked]>>
Date: Monday, October 3, 2016 at 11:49 AM
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] SPAKE2+mbDH a PAKE+PKA

Dear Stanislav,

Thank you very much for your time and effort to review this proposal. I greatly appreciate your insights.

Thank you for your comments and for the updated version of the slides. Since you agree with my thoughts about the importance of defining "encrypt" properties, let's remember this question.

After another careful reading of the protocol now I have a concern about it that seems very important to me.

In the original SPAKE2 (as well as in SESPAKE and AugPAKE etc) there is an important property (that is even proven for SPAKE2 and SESPAKE) of absence of password leakage problems in the cases when the resulting session keys are revealed (in real life - when the session key is misused and compromised somehow). It is extremely important since session keys often get compromised in real life and no one wants to leak authentication data with them.

I agree with your concerns. The property of preventing password leakage when session keys are exposed may not be applicable to every application, but it’s still an important attribute. Most importantly …   The combining of two security primitives should retain all of the properties of the original two primitives.

And the proposed protocol lacks this property: if sk_AB is compromised, then x_A and P_A are known to adversary too - thus he knows w*M_A and can find short secret pw by dictionary attack.

Thus in the current version any agreed session key compromise would lead to long-term password compromise, that seems to be a really bad property.

I see now that the ephemeral mask in SPAKE2 with the masked public key from mbDH have contradictory requirements. The mbDH requires the subsequent exposure of the mask to prove possession of the public key. SPAKE2 requires that the mask never be exposed even if encrypted under a session key. This type of replacement of terms is a flawed construction technique.

A more direct combination of protocol mechanisms would be to perform them both in parallel without significant modification to either base mechanism. The calculation of the shared key(s) could be performed jointly for some efficiency benefits without impacting the combined security characteristics.

I'll be thankful for your comments on this concern. Please correct me, if I missed something in your description.

No, your concerns are well founded and show that I violated my own design goals for building on existing mechanisms. In my enthusiasm to save a point multiple and a few bytes, the proposed design broke a subtile, but fundamental security property of SPAKE2.

Best Regards,

Paul

Kindest regards,
Stanislav Smyshlyaev
От: Paul Lambert
Отправлено: четверг, 29 сентября 2016 г., 11:54
Кому: Stanislav V. Smyshlyaev
Копия: [email-masked]<mailto:[email-masked]>
Тема: Re: [Cfrg] SPAKE2+mbDH a PAKE+PKA

Dear Stanislav,

Thank you for these links – they give a slightly new viewpoint on PAKEs applications (I think the most discussed question will be "for which applications will combining public keys and passwords be most useful?").
Yes … it may be useful as a type of ‘introduction’ process.

An editorial comment on the description of the protocol in the slides: it seemts that after the second message A should check that "R_B - w*M_B == x_B * P_B", not "R_B == x_B * P_B" as it is shown now. Similarly with the B's check.

And a tiny remark: there is a misprint in the plaintext that A encrypts on sk_AB for the third message: "(x_A, P_A)" should be there, not "(m_A, P_A)".

Many thanks for catching my errors!

I’ve updated the figures and reposted: https://mentor.ieee.org/802.11/dcn/16/11-16-1142-06-00ai-cryptographic-review-and-pkex.ppt

About the protocol itself, I'll try my best to give you our opinion today or tomorrow.

At a glance, it seems to be useful to add some specific requirements for the used "encrypt" functions now or some concrete cipher modes (e.g. GCM or CTR + HMAC)

Yes, this is not clear. The notation slide mentions  AEAD encryption but could say more on requirements. The ‘additional data’ is not being used, so AEAD is not strictly required. For concrete examples, I’m considering AES-SIV or GCM-SIV or something similar.

due to the words "decrypt is successful" (is it a real data authentication or just some padding check?). EMVco used to check PIN-blocks just by correctness of ECB decryption of IUN, so we should have more details here.

Yes, exactly.  The decryption provides the validity check for the password based authentication and does need a better description.

Best Regards,

Paul

Kindest regards,
Stanislav

2016-09-29 4:25 GMT+03:00 Paul Lambert <[email-masked]<mailto:[email-masked]>>:

The PKEX protocol ( https://tools.ietf.org/html/draft-harkins-pkex-00 )
provides PAKE functionality (with SPAKE2) and adds public key
authentication (PAKE+PKA).

In looking at alternatives to PKEX, combining an existing and evaluated
authenticated public key exchange with a PAKE seems like an interesting
design path. To this end, the SPAKE2 protocol (
https://tools.ietf.org/html/draft-irtf-cfrg-spake2-03 ) combines nicely
with mutually blinded Diffie-Hellman (mbDH). Blinded DH (bDH) is described
in https://www.emvco.com/specifications.aspx?id=285

A brief description of the resulting SPAKE2+mbDH protocol is contained in
slides 13 to 18 of:

        https://mentor.ieee.org/802.11/dcn/16/11-16-1142-04-00ai-cryptographic-rev
iew-and-pkex.ppt

Comments would be appreciated.

If this protocol seems useful an RFC could be developed.

Paul

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 4 Oct 2016 09:05:05 +0300

Dear Paul,

Thank you for the new version!

I'll try to review it and reply in a couple of days.

Kindest regards,
Stanislav

2016-10-04 2:05 GMT+03:00 Paul Lambert <[email-masked]>:

> Dear Stanislav,
>
> Based on your comments, I’ve made another cut at combining SPAKE2 and
> mbDH. This should not have the problem you identified in the earlier
> version. The combination more directly performs the protocols in parallel.
>
> From: Paul Lambert <[email-masked]>
> To: "[email-masked]" <[email-masked]>
> Cc: "[email-masked]" <[email-masked]>
> Thank you for your comments and for the updated version of the slides.
> Since you agree with my thoughts about the importance of defining "encrypt"
> properties, let's remember this question.
>
> In the original SPAKE2 (as well as in SESPAKE and AugPAKE etc) there is an
> important property (that is even proven for SPAKE2 and SESPAKE) of absence
> of password leakage problems in the cases when the resulting session keys
> are revealed (in real life - when the session key is misused and
> compromised somehow). It is extremely important since session keys often
> get compromised in real life and no one wants to leak authentication data
> with them.
>
>
> I agree with your concerns. The property of preventing password leakage
> when session keys are exposed may not be applicable to every application,
> but it’s still an important attribute. Most importantly …   The combining
> of two security primitives should retain all of the properties of the
> original two primitives.
>
>
> And the proposed protocol lacks this property: if sk_AB is compromised,
> then x_A and P_A are known to adversary too - thus he knows w*M_A and can
> find short secret pw by dictionary attack.
>
> Thus in the current version any agreed session key compromise would lead
> to long-term password compromise, that seems to be a really bad property.
>
>
> I see now that the ephemeral mask in SPAKE2 with the masked public key
> from mbDH have contradictory requirements. The mbDH requires the subsequent
> exposure of the mask to prove possession of the public key. SPAKE2 requires
> that the mask never be exposed even if encrypted under a session key. This
> type of replacement of terms is a flawed construction technique.
>
> A more direct combination of protocol mechanisms would be to perform them
> both in parallel without significant modification to either base mechanism.
> The calculation of the shared key(s) could be performed jointly for some
> efficiency benefits without impacting the combined security
> characteristics.
>
>
> No, your concerns are well founded and show that I violated my own design
> goals for building on existing mechanisms. In my enthusiasm to save a point
> multiple and a few bytes, the proposed design broke a subtile, but
> fundamental security property of SPAKE2.
>
> Best Regards,
>
> Paul
>
>
> Kindest regards,
> Stanislav Smyshlyaev
> *От: *Paul Lambert
> *Отправлено: *четверг, 29 сентября 2016 г., 11:54
> *Кому: *Stanislav V. Smyshlyaev
> *Копия: [email-masked]
> *Тема: *Re: [Cfrg] SPAKE2+mbDH a PAKE+PKA
>
>
> Dear Stanislav,
>
>
> Thank you for these links – they give a slightly new viewpoint on PAKEs
> applications (I think the most discussed question will be "for which
> applications will combining public keys and passwords be most useful?").
>
> An editorial comment on the description of the protocol in the slides: it
> seemts that after the second message A should check that "R_B - w*M_B ==
> x_B * P_B", not "R_B == x_B * P_B" as it is shown now. Similarly with the
> B's check.
>
>
> And a tiny remark: there is a misprint in the plaintext that A encrypts on
> sk_AB for the third message: "(x_A, P_A)" should be there, not "(m_A, P_A)".
>
>
> I’ve updated the figures and reposted: https://mentor.ieee.
> org/802.11/dcn/16/11-16-1142-06-00ai-cryptographic-review-and-pkex.ppt
>
>
> At a glance, it seems to be useful to add some specific requirements for
> the used "encrypt" functions now or some concrete cipher modes (e.g. GCM or
> CTR + HMAC)
>
>
> Yes, this is not clear. The notation slide mentions  AEAD encryption but
> could say more on requirements. The ‘additional data’ is not being used, so
> AEAD is not strictly required. For concrete examples, I’m considering
> AES-SIV or GCM-SIV or something similar.
>
>
> due to the words "decrypt is successful" (is it a real data authentication
> or just some padding check?). EMVco used to check PIN-blocks just by
> correctness of ECB decryption of IUN, so we should have more details here.
>
>
> Yes, exactly.  The decryption provides the validity check for the password
> based authentication and does need a better description.
>
> Best Regards,
>
> Paul
>
>
> Kindest regards,
> Stanislav
>
>
>
> 2016-09-29 4:25 GMT+03:00 Paul Lambert <[email-masked]>:
>
>>
>> <https://mentor.ieee.org/802.11/dcn/16/11-16-1142-04-00ai-cryptographic-review-and-pkex.ppt>
>>
>> [email-masked]

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 4 Oct 2016 09:45:12 +0300

Dear Paul,

Just a small remark: I'm sure that in the second message you wanted to send
"encrypt( key=sk_BA, ((y_B, P_B), ...) )", not "encrypt( key=sk_BA, ((x_B,
P_B), ...) )" (and "y_A, P_A" correspondigly). Otherwise you would obtain
exactly the same problem as before.

Best regards,
Stanislav

2016-10-04 9:05 GMT+03:00 Stanislav V. Smyshlyaev <[email-masked]>:

>> In the original SPAKE2 (as well as in SESPAKE and AugPAKE etc) there is
>> an important property (that is even proven for SPAKE2 and SESPAKE) of
>> absence of password leakage problems in the cases when the resulting
>> session keys are revealed (in real life - when the session key is misused
>> and compromised somehow). It is extremely important since session keys
>> often get compromised in real life and no one wants to leak authentication
>> data with them.
>>
>>
>> And a tiny remark: there is a misprint in the plaintext that A encrypts
>> on sk_AB for the third message: "(x_A, P_A)" should be there, not "(m_A,
>> P_A)".
>>
>>
>> due to the words "decrypt is successful" (is it a real data
>> authentication or just some padding check?). EMVco used to check PIN-blocks
>> just by correctness of ECB decryption of IUN, so we should have more
>> details here.
>>
>>
>> Yes, exactly.  The decryption provides the validity check for the
>> password based authentication and does need a better description.
>>
>> Best Regards,
>>
>> Paul
>>
>>
>> Kindest regards,
>> Stanislav
>>
>>
>>

---

From: Paul Lambert <[email-masked]>
Date: Tue, 4 Oct 2016 07:44:37 +0000

Dear Stanislav,

Just a small remark: I'm sure that in the second message you wanted to send "encrypt( key=sk_BA, ((y_B, P_B), ...) )", not "encrypt( key=sk_BA, ((x_B, P_B), ...) )" (and "y_A, P_A" correspondigly). Otherwise you would obtain exactly the same problem as before.

Thanks! I missed making this variable change … appreciate your catching this error.

This update also made the shared key calculation more exactly match the SPAKE2 RFC and I missed changing the terms in this hash in a couple places.

These are now fixed in: https://mentor.ieee.org/802.11/dcn/16/11-16-1329-01-00ai-pkex-alternatives.ppt

Best Regards,

Paul

Best regards,
Stanislav

2016-10-04 9:05 GMT+03:00 Stanislav V. Smyshlyaev <[email-masked]<mailto:[email-masked]>>:
Dear Paul,

Kindest regards,
Stanislav

2016-10-04 2:05 GMT+03:00 Paul Lambert <[email-masked]<mailto:[email-masked]>>:
Dear Stanislav,

Best Regards,

Paul

Dear Stanislav,

Best Regards,

Paul

Kindest regards,
Stanislav Smyshlyaev
От: Paul Lambert

Dear Stanislav,

Best Regards,

Paul

Kindest regards,
Stanislav

        https://mentor.ieee.org/802.11/dcn/16/11-16-1142-04-00ai-cryptographic-rev
iew-and-pkex.ppt<https://mentor.ieee.org/802.11/dcn/16/11-16-1142-04-00ai-cryptographic-review-and-pkex.ppt>

Paul

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 5 Oct 2016 07:56:06 +0300

Dear Paul!

Thank you very much for the corrections.

I. In the sense of PAKE everything seems to be OK now: now the proposed
protocol is at least as strong as SPAKE2 itself – since  SPAKE2 + mbDH for
certain values of parameters is reduced to SPAKE2. Since the first part of
SPAKE2 (key agreement itself) is proven to be secure, we may say that SPM2
should be a secure PAKE. Nevertheless a separate accurate proof would be
interesting anyway – but I think this is not the thing we should care now
about SPM2, there seems to be a lot more important problem.

II. The problem is SPM2 in the case of known password seems to be less
secure than mbDH (it seems to be unsecure at all in this case).

Consider the following attack (thanks to my colleague Liliya Ahmetzyanova for
the description)

Let the adversary who tries to impersonate himself as B, knows password w,
but doesn't possess private key s_B and wants to make honest party A
believe that he does it for some fixed value of P_B.

1.       A sends the values R_A, Y_A, where

R_A = x_A * G + w * M_A;  (according to the protocol description)

Y_A = y_A * P_A = y_A * s_A * G; (according to the protocol description)

2.       The adversary calculates for random x_B and y_B the values

Y_B = y_B * P_B;

R_B = x_B * G + w * M_B *– Y_B*;

K = x_B * (R_A – w * M_A) + x_B * Y_A       (     =     x_B * (x_A * G) +
x_B * (y_A * s_A * G));

Then all actions are made according to the protocol.

3.       A calculates K according to the protocol:

K = (x_A + y_A * s_A)(R_B – w * M_B + Y_B)    (    =    (x_A + y_A *
s_A)(x_B * G)  );

The key K is equal to the key of adversary = > decryption will be correct
=> the check

assert Y_B == y_B * P_B will be successful;

Thus SPM2 is not secure in the same case as mbDH is – it loses all
private-key-related security when the password is known.

Again, Paul, please correct me if I missed something.

Best regards,
Stanislav Smyshlyaev

2016-10-04 10:44 GMT+03:00 Paul Lambert <[email-masked]>:

>
>
>
> Dear Stanislav,
>
>
> Just a small remark: I'm sure that in the second message you wanted to
> send "encrypt( key=sk_BA, ((y_B, P_B), ...) )", not "encrypt( key=sk_BA,
> ((x_B, P_B), ...) )" (and "y_A, P_A" correspondigly). Otherwise you would
> obtain exactly the same problem as before.
>
>
> This update also made the shared key calculation more exactly match the
> SPAKE2 RFC and I missed changing the terms in this hash in a couple places.
>
> These are now fixed in: https://mentor.ieee.org/
> 802.11/dcn/16/11-16-1329-01-00ai-pkex-alternatives.ppt
>
> Best Regards,
>
> Paul
>

---

From: Dan Harkins <[email-masked]>
Date: Tue, 4 Oct 2016 22:45:16 -0700

Privyet Stanislav,

On 10/4/16 9:56 PM, Stanislav V. Smyshlyaev wrote:
> I. In the sense of PAKE everything seems to be OK now: now the 
> proposed protocol is at least as strong as SPAKE2 itself – since 
>  SPAKE2 + mbDH for certain values of parameters is reduced toSPAKE2. 
> Since the first part of SPAKE2 (key agreement itself) is proven to be 
> secure, we may say that SPM2 should be a secure PAKE. Nevertheless a 
> separate accurate proof would be interesting anyway – but I think this 
> is not the thing we should care now about SPM2, there seems to be a 
> lot more important problem.
>

   What security properties do you believe mbDH has beyond simple DH-- i.e.
unauthenticated key agreement?

   Dan.

>
> Consider the following attack (thanks to my colleague Liliya 
> Ahmetzyanova for the description)
>
> Let the adversary who tries to impersonate himself as B, knows 
> password w, but doesn't possess private key s_B and wants to make 
> honest party A believe that he does it for some fixed value of P_B.
>
>
>
> 1.A sends the valuesR_A, Y_A, where
>
> 2.The adversary calculates for random x_B andy_Bthe values
>
> Y_B = y_B * P_B;
>
> K = x_B * (R_A – w * M_A) + x_B * Y_A       (     =     x_B * (x_A * 
> G) + x_B * (y_A * s_A * G));
>
> 3.A calculates Kaccording to the protocol:
>
> The key Kis equal to the key of adversary = > decryption will be 
> correct => the check
>
> assertY_B == y_B * P_Bwill be successful;
>
>
> 2016-10-04 10:44 GMT+03:00 Paul Lambert <[email-masked] 
> <mailto:[email-masked]>>:
>
>
>
>
>     Dear Stanislav,
>
>
>         Just a small remark: I'm sure that in the second message you
>         wanted to send "encrypt( key=sk_BA, ((y_B, P_B), ...) )", not
>         "encrypt( key=sk_BA, ((x_B, P_B), ...) )" (and "y_A, P_A"
>         correspondigly). Otherwise you would obtain exactly the same
>         problem as before.
>
>
>     This update also made the shared key calculation more exactly
>     match the SPAKE2 RFC and I missed changing the terms in this hash
>     in a couple places.
>
>     These are now fixed in:
>     https://mentor.ieee.org/802.11/dcn/16/11-16-1329-01-00ai-pkex-alternatives.ppt
>     <https://mentor.ieee.org/802.11/dcn/16/11-16-1329-01-00ai-pkex-alternatives.ppt>
>
>
>     Best Regards,
>
>     Paul
>
>
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 5 Oct 2016 08:55:32 +0300

Hello, Dan!

mbDH (without modifications to SPM2) allows mutual authentication by
private keys s_A and s_B in case the parties obtain trusted (i.e. obtained
by a well-authenticated channel before the mbDH itself, of course) P_A and
P_B – as well as ordinary authenticated DH.

The thing I am talking about is that SPM2 seems not to provide it – Alice,
who has a valid Bob's P_B, can be tricked by an adversary who doesn't have
a correct s_B and has only the password.

Regards,
Stanislav

2016-10-05 8:45 GMT+03:00 Dan Harkins <[email-masked]>:

> certain values of parameters is reduced to SPAKE2. Since the first part
> of SPAKE2 (key agreement itself) is proven to be secure, we may say that
> SPM2 should be a secure PAKE. Nevertheless a separate accurate proof would
> be interesting anyway – but I think this is not the thing we should care
> now about SPM2, there seems to be a lot more important problem.
>
>
>
>> These are now fixed in: https://mentor.ieee.org/80
>> 2.11/dcn/16/11-16-1329-01-00ai-pkex-alternatives.ppt
>>
>> Best Regards,
>>
>> Paul
>>
>
>
> Cfrg mailing [email-masked]://www.irtf.org/mailman/listinfo/cfrg
>
>
>

---

From: Dan Harkins <[email-masked]>
Date: Tue, 4 Oct 2016 23:09:20 -0700

Hello Stanislav,

On 10/4/16 10:55 PM, Stanislav V. Smyshlyaev wrote:
> private keys s_A and s_B in case the parties obtain trusted (i.e. 
> obtained by a well-authenticated channel before the mbDH itself, of 
> course) P_A and P_B – as well as ordinary authenticated DH.

So the parties must have some pre-existing authenticated channel through 
which
they exchanged and obtained trust in P_A and P_B? And if not, then mbDH 
provides
no authentication whatsoever. Correct?

>
> The thing I am talking about is that SPM2 seems not to provide it – 
> Alice, who has a valid Bob's P_B, can be tricked by an adversary who 
> doesn't have a correct s_B and has only the password.

   That does seem to void one of the goals of SPM2.

   regards,

   Dan.

>
>
> Regards,
> Stanislav
>
>
>
> 2016-10-05 8:45 GMT+03:00 Dan Harkins <[email-masked] 
> <mailto:[email-masked]>>:
>
>
>       Privyet Stanislav,
>
>>      SPAKE2 + mbDH for certain values of parameters is reduced
>>     toSPAKE2. Since the first part of SPAKE2 (key agreement itself)
>>     is proven to be secure, we may say that SPM2 should be a secure
>>     PAKE. Nevertheless a separate accurate proof would be interesting
>>     anyway – but I think this is not the thing we should care now
>>     II. The problem is SPM2 in the case of known password seems to be
>>     less secure than mbDH (it seems to be unsecure at all in this case).
>>
>
>>     K = x_B * (R_A – w * M_A) + x_B * Y_A       (     =     x_B *
>>     (x_A * G) + x_B * (y_A * s_A * G));
>>
>>     3.A calculates K according to the protocol:
>>
>>     K = (x_A + y_A * s_A)(R_B – w * M_B + Y_B)    (    =    (x_A +
>>     y_A * s_A)(x_B * G)  );
>>
>>     Thus SPM2 is not secure in the same case as mbDH is – it loses
>>     all private-key-related security when the password is known.
>>
>>             Just a small remark: I'm sure that in the second message
>>             you wanted to send "encrypt( key=sk_BA, ((y_B, P_B), ...)
>>             )", not "encrypt( key=sk_BA, ((x_B, P_B), ...) )" (and
>>             "y_A, P_A" correspondigly). Otherwise you would obtain
>>         match the SPAKE2 RFC and I missed changing the terms in this
>>         hash in a couple places.
>>
>>         These are now fixed in:
>>     [email-masked] <mailto:[email-masked]>
>>     <https://www.irtf.org/mailman/listinfo/cfrg>
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 5 Oct 2016 09:27:17 +0300

Of course.

This is the goal that is achieved by mbDH – if Alice has Bob's P_B, she can
be sure that the no one without having s_B can make her think that he
obtains s_B. If we add password authentication to mbDH, it is reasonable to
hope at least to keep the existing security properties. Otherwise, what
sense can be in SPM2? SPAKE2 and SESPAKE provide secure password-based
authentication and protected key exchange themselves.

Regards,
Stanislav

2016-10-05 9:09 GMT+03:00 Dan Harkins <[email-masked]>:

>   So the parties must have some pre-existing authenticated channel
> through which
>> Let the adversary who tries to impersonate himself as B, knows password
>> w, but doesn't possess private key s_B and wants to make honest party A
>> The key K is equal to the key of adversary = > decryption will be
>> correct => the check
>>

---

From: Paul Lambert <[email-masked]>
Date: Fri, 7 Oct 2016 22:39:49 +0000

Dear Stanislav,

Thank you so much for your time to review and break my proposed protocol :-)

This is an important result as it also breaks another draft specification – DPP.

II. The problem is SPM2 in the case of known password seems to be less secure than mbDH (it seems to be unsecure at all in this case).

Consider the following attack (thanks to my colleague Liliya Ahmetzyanova for the description)
Let the adversary who tries to impersonate himself as B, knows password w, but doesn't possess private key s_B and wants to make honest party A believe that he does it for some fixed value of P_B.

Y_B = y_B * P_B;

R_B = x_B * G + w * M_B – Y_B;

K = x_B * (R_A – w * M_A) + x_B * Y_A       (     =     x_B * (x_A * G) + x_B * (y_A * s_A * G));

K = (x_A + y_A * s_A)(R_B – w * M_B + Y_B)    (    =    (x_A + y_A * s_A)(x_B * G)  );

The key K is equal to the key of adversary = > decryption will be correct => the check

Thus SPM2 is not secure in the same case as mbDH is – it loses all private-key-related security when the password is known.
Again, Paul, please correct me if I missed something.
No – this is clearly a problem with SPM2 and the “DPP Authentication” protocol.

For background, I’ve been working on fixing 'Wi-Fi setup’. The current technology is old and quite broken:
https://www.wi-fi.org/download.php?file=/sites/default/files/private/members/Wi-Fi_Simple_Configuration_Technical_Specification_v2.0.5.pdf
The current work for new ‘setup’ within the Wi-Fi community is called Device Provisioning Protocol (DPP):
https://www.wi-fi.org/downloads-registered-guest/Wi-Fi_DPP_Tech_Spec_v0_0_23.pdf/31255
    and
https://groups.wi-fi.org/apps/org/workgroup/dpp_ttg/download.php/74822/latest/Explanation%20of%20DPP%20Authentication%20Protocol%20for%20Security%20Review.pdf

This specification contains PKEX 1.0 and there is now a rush to replace this broken functionality … this is the reason we have multiple PKEX and SPM proposals.  Rushing to provide an exact replacement for the PKEX functionality may be a mistake (IMHO) as it is a good opportunity to look at the broader implications and system design given the now identified issues with it’s accompanying ‘DPP Auth’ protocol.

On DPP … in SPM2 I borrowed the  "additive joint key proof-of-possesion” from DPP (draft .23 section 6.2). Here it describes ‘mutual authentication’ as:
    Initiator with: P_I = p_I*G       # Initiator long-term public key
                             B_I = b_I*G       # Initiator ephemeral ‘bootstrap’ public key (exchanged out-of-band, e.g QR code)
   Responder with: P_R = p_R*G       # Responder long-term public key
                                 B_R = b_R*G       # Responder ephemeral ‘bootstrap’ public key (exchanged out-of-band, e.g QR code)
   Secret key calculation:
       S = (p_R + b_R) * (p_I + b_I) * G
     = (p_R + b_R) * (P_I + B_I)[by Responder]
   = (p_I + b_I) * (P_R + B_R)               [by Initiator]

The “DPP Authentication” protocol is in short form the following:

—> B_I
                <— B_R
I_nonce = rand()
K1= H1(p_I * B_R)
—> H(B_R), H(B_I), P_I, { I_nonce, … }K1
                K1=H1(p_R*B_I)
                decrypt { I_nonce, … }K1
                R_nonce=rand()
                S2= (b_R + p_R) * (P_I + B_I)
                K2=H2(I_nonce | R_nonce, “DPP Key”, S2)
                R_auth = H(I_nonce | R_nonce | P_I.x | P_R.x |  [ B_I.x | ] B_R.x | 0)
                <— SHA256(B_R), [ SHA256(B_I), ] P_R, { R_nonce | I_nonce | R-capabilities | { R_auth }K2 }K1
S2=(p_I + b_I)  * (B_R + P_R)
K2 = H2(I_nonce | R_nonce, “DPP Key”, S2)
Decrypt { R_nonce | I_nonce | R-capabilities | { R-auth }K2 }K1
Decrypt { R_auth }K2
assert R_auth == R_auth = H(I_nonce | R_nonce | P_I.x | P_R.x |  [ B_I.x | ] B_R.x | 0)
I_auth = H(R-nonce | I-nonce | PR.x | PI.x | BR.x | [ BI.x | ] 1)
—> SHA256(B_R), [ SHA256(B_I), ] { I_auth }K2
              Decrypt { I_auth }K2
              assert I_auth == H(R-nonce | I-nonce | PR.x | PI.x | BR.x | [ BI.x | ] 1)

Your ‘break’ of SPM2 then applies to B_R where the responder could present any public key (P_R) as their own without having the associated private key by:

…
                <— B_R= b_R*G – P_R
…
                S2= (b_R ) * (P_I + B_I)  # ownership of private key p_R not required!

This being the exact attack you identified with SPM2!

I have several other issues with “DPP Authentication” - for example, why are P_I and P_R both sent openly? This clearly breaks any opportunity for privacy/unlinkability. This is a questionable design choice given that both keys could readily be sent encrypted.

On SPM3 … :-)
It’s clear now that ownership of each private key must be individually validated. Both protocols (SPAKE2 and mbDH) would be more completely preserved by:
    K1 = x_B * (R_A – w*M_A+ Y_A)
    K2 = y_B * s_B*Y_A
    sk_BA = H( “R” || len(id_A)|| id_A || len(id_B) || id_B || len(R_A) || R_A ||
                                len(R_B) || R_B || len(w) || w || len(K) || K1 || len(K2) || K2)

Best Regards,

Paul

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 7 Oct 2016 15:57:20 -0700

On Fri, Oct 7, 2016 at 3:39 PM, Paul Lambert <[email-masked]> wrote:
> but doesn't possess private key s_B and wants to make honest party A believe
> that he does it for some fixed value of P_B.
>
>
>
> This specification contains PKEX 1.0 and there is now a rush to replace this
> broken functionality … this is the reason we have multiple PKEX and SPM
> proposals.  Rushing to provide an exact replacement for the PKEX
> functionality may be a mistake (IMHO) as it is a good opportunity to look at
> the broader implications and system design given the now identified issues
> with it’s accompanying ‘DPP Auth’ protocol.
>
> On DPP … in SPM2 I borrowed the  "additive joint key proof-of-possesion”
> from DPP (draft .23 section 6.2). Here it describes ‘mutual authentication’
> as:
>                              B_I = b_I*G       # Initiator ephemeral
> ‘bootstrap’ public key (exchanged out-of-band, e.g QR code)
>                                  B_R = b_R*G       # Responder ephemeral
> ‘bootstrap’ public key (exchanged out-of-band, e.g QR code)
>    Secret key calculation:

What's the need for this fanciness?  Why not create a secure channel
using your favorite authenticated DH protocol using just the bootstrap
keys and then exchange long-term public keys over that channel?  This
all seems to be doing something like Signal's [or whatever it's called
these days] "triple DH" protocol, except that triple DH uses genuinely
unauthenticated ephemeral points and triple DH hashes everything
together instead of using EC addition.

I guess what I'm really asking, though, is: what's the point of having
separate bootstrap and long-term keys?

--Andy

---

From: Paul Lambert <[email-masked]>
Date: Thu, 13 Oct 2016 23:24:36 +0000

Hi Andy,

>> Œbootstrap¹ public key (exchanged out-of-band, e.g QR code)
>>    Secret key calculation:
>keys and then exchange long-term public keys over that channel?

Yes Š this does become a little silly - especially when you look at the
end result of all the combined protocols. Specifically for DPP, PKEX is
always run first and then another 3-step authentication protocol is run to
exchange the long-term keys.

> This

Yes, the EC addition trick is bad. The Triple DH looks like one
alternative for the simultaneous demonstration of ownership of two keys.

On this type of integration of authenticated DH and a PAKE, it makes more
sense to me to put an optional PAKE ³inside" a authenticated DH exchange.

This way you get:
 - an ephemeral key exchange
 - the long-term keys encrypted under the ephemeral key (privacy from
third party observation)
 - a PAKE optionally within the encrypted exchange
 - the ability to securely exchange info related to the PAKE identities
and process

For:
    R_A and R_B are ephemeral public keys

    {} indicting AEAD encryption with key derived from ephemeral exchange
    P_A and P_B are long-term keys
    ... Ellipsis indicate protecte fields outside the scope of this
discussion
    [x] brackets indicate an optional field

    R_A --->
    <--- R_B, { (proof, P_B) ... }
    { (proof, P_A) ... } --->

    <--- { ... }

Here I¹m ignoring the math to better discuss the structure of the protocol.
The Œproof¹ would be some technique (like the Triple DH) to strongly
demonstrate the joint ownership of the ephemeral

This has some interesting properties if you make the long-term key and
proof optional:

    R_A --->
    <--- R_B, {[(proof, P_B)] ... }
    {[(proof, P_A)] ... } --->
    <--- { ... }

The same exchange would then support one-sided, mutual or no
authentication to a long-term key.
The protocol could support some negotiation of which device goes first
exposing their long-term key.

    R_A --->
    <--- R_B, { Œyou first' ... }
    { (proof, P_A) ... } --->
    <--- { (proof, P_B) ... }

If there is a need to bind this exchange to human validation of a string
it could be extended to support a SAS and associated human interaction:

    R_A --->
    <--- R_B, {[(proof, P_B)] ... }
Display SAS
    {[(proof, P_A)] ... } --->
                            Display SAS
    <--- { ... }
Confirm

Integration of a PAKE would look like:
    R_A --->
    <--- R_B, {(proof, P_B), pake_m1  ... }
    {(proof, P_A), pake_m2 ... } --->
    <‹ {pake_m3 ... }

First, I proposing that any PAKE should be able to be mapped into three
messages: pkae_1, pake_2 and pake_3

So ...one protocol structure could support multiple types of
authentication (none/owe, one-sided, mutual) and provide optional support
for short authentication strings or user input passphrases.

>separate bootstrap and long-term keys?

For an in-line exchange there is no benefit.

If you look at how a static QR code might contain a key it becomes more
complicated and this printed key might be called a "bootstrap key² if it
is not the long-term key.

On this type of bootstrapping, there are several different use cases with
very different requirements:
 - a static unchanging key associated directly with a device
   (a QR code printed on a device where the QR code data is associated
with a long-term key)
 - a dynamic key that is used once to introduce devices
   (e.g. A one-time QR code displayed on a TV screen where the QR code
data is associated with a long-term key)

Given the above, and working to avoid the term Œbootstrap¹, there are
three types of public keys required:
 - ephemeral keys that are used only once
 - long-term identity keys that are used for access control and
authorization
 - long-term hardware keys that are bound to a physical device

The latter two key types should not be the same key for most consumer
devices. The hardware oriented key is fixed and not reset when devices are
reset. An Œidentity¹ key should be reset as it is used by other systems to
determine access control and authorization decisions.

This implies that devices may need to support and demonstrate ownership of
multiple long-term keys. For example:

    R_A --->
    <--- R_B, { (proof, P_B), (proof, P_hw_B) ... }
    { (proof, P_A), (proof, P_hw_A) ... } --->
    <--- { Š }

Regards,

Paul

---

From: Dan Harkins <[email-masked]>
Date: Fri, 14 Oct 2016 14:42:08 -0700

Hi Paul,

> exchange the long-term keys.

   Correct me if I'm wrong but isn't PKEX an _optional_ bootstrapping
method of which there are several others? So it's not, necessarily,
always run first. It's just that some bootstrapping technique is run
to obtain some modicum of trust in the bootstrapped keys and *then*
those keys are used in DPP to do authentication.

>   - the long-term keys encrypted under the ephemeral key (privacy from

   Except that sending a "long-term key" encrypted using a key derived from
an unauthenticated exchange of ephemeral keys buys you nothing. These
"long-term keys" are public after all and anyone can encrypt anyone else's
public key by the result of another unauthenticated Diffie-Hellman. Are
there any useful properties to such an exchange? I can't see them.

>   - a PAKE optionally within the encrypted exchange

   Why do "an optional PAKE 'inside' an authenticated DH exchange"? If
the DH is authenticated then the PAKE buys you nothing. Anything that
calls itself a PAKE should not need to be run "inside" an authenticated
channel.

>      { (proof, P_A) ... } --->

   But "the math" is crucial, you can't ignore it. You do AEAD encryption
"with key derived from ephemeral exchange"... of what? "proof" is proof
of what? If it's just of knowledge of the private analogs to R_A and R_B
then you don't get authentication since R_A and R_B are ephemeral.

>      {[(proof, P_A)] ... } --->

   Only if an unauthenticated Diffie-Hellman has "interesting properties".
I don't think it does. Key agreement is not authentication. And if you
exclude the long-term keys and whatever "proof" is then you have an
unauthenticated Diffie-Hellman.

>      {[(proof, P_A)] ... } --->

   Without an explanation of what "proof" means and what "{...}"
is performed with then this is just a bunch of hand-waving.

> for short authentication strings or user input passphrases.

   Requiring an authenticated key exchange to conform to the message
requirements of a different protocol seems bassackwards.
> is not the long-term key.

   Are you saying that "bootstrap key" cannot be "long-term key"? Is that
part of DPP?
>      { (proof, P_A), (proof, P_hw_A) ... } --->

   Now the intricacies of the math compound due to you sending multiple
public keys under protection of... well not sure. It's impossible to
analyze this.

   regards,

   Dan.