Subject: Re: [Cfrg] password-based key exchange,revisited

From: [email-masked]
Date: Mon, 28 May 2012 13:53:42 +0800

"Dan Harkins" <[email-masked]>  2012-05-28 12:35:40:

> 
>   Hello,
> 
>   Thank you very much for your analysis of my protocol.
> 
> On Thu, May 24, 2012 6:39 pm, [email-masked] wrote:
> > As in the calculation of "K = PE^(peer_rand*local_rand) mod p"
> > K can be reduced to PE^(peer_scalar*local_scalar+local_mask*peer_mask)
> > *(peer_element)^(local_scalar)*(local_element)^(peer_scalar) mod p
> >
> > K = PE^(peer_rand*local_rand) mod p
> >    =PE^[( peer_scalar-peer_mask)*(local_scalar-local_mask)] mod p
> >
> > =PE^(peer_scalar*local_scalar-peer_mask*local_scalar-
> local_mask*peer_scalar+local_mask*peer_mask)
> > mod p
> >    =PE^(peer_scalar*local_scalar+local_mask*peer_mask)
> > *(peer_element)^(local_scalar)*(local_element)^(peer_scalar) mod p
> >
> > Because  (peer_element)^(local_scalar)*(local_element)^(peer_scalar) 
can
> > be calculated directly from the key exchange message,
> > the effective part of K is
> > PE^(peer_scalar*local_scalar+local_mask*peer_mask), has nothing to do 
with
> >  local_rand and peer_rand,
> > so the password based key exchange is essentially equal with the 
following
> > "exchange"￡o
> 
>   The problem with this is that peer_mask is unknown so it is not 
possible
> to reduce computation of K in this manner.

I mean the key in your protocol K can be taken into two parts,
one part is  PE^(SaSb+MaMa)   let Sa=peer_scalar, Sb=local_scalar; 
Ma=peer_mask,Mb=local_mask 
the other part is Eb^(Sa)Ea^(Sb)  let Eb=local_element  Ea=peer_element
and the second part can be calculated directly from Eb Sa Sb Ea which are 
exchanged in plaintext
so the second part has little contribution in the secrecy of K.
so, your protocol can be reduced to the following one as I have described:

in computation of K, their complexity are the same; but 
just need to exchange local_element instead of both local_element and 
local_scalar
and do not need calculate local_scalar.
> 
> > 2'. generate 2 random numbers between 0 and the order of the group, q:
> >
> >    0 < local_mask,local_scalar < q
> >
> > 3'. compute an element:
> >    local_element = 1/(PE^local_mask) mod p
> >
> >    where p is the prime and q is the order. Send local_scalar and
> >    local_element to other side
> >
> > 4'. receive peer_scalar and peer_element from other side
> >
> > 5'. compute shared key, K
> >
> >    K =PE^(peer_scalar*local_scalar)* (peer_element)^(-local_mask) mod 
p
> >      =PE^(peer_scalar*local_scalar+local_mask*peer_mask) mod p
> >
> > It is simpler and less computation invloved, and hopefully easier to
> > analysis the security.
> 
>   PE^(peer_scalar*local_scalar) is completely extraneous. This is just
> a standard diffie-hellman with peer_mask and local_mask as the private
> contributions using, presumably, a password-derived generator (you
> don't actually say). The exchange above has received quite a bit of
> analysis already: it's the SPEKE protocol.

The reduced protocol is not exactly SPEKE, and of course they are similar.
It is a good news that your protocol can be reduced to as secure as SPEKE 
protocol,I think.
I am not sure about the usage of  PE^(peer_scalar*local_scalar) in the K，
because only person who knows PE can
calculate it.

In my opinion, for a key agreement protocol, the simpler the better, both 
for analysis and for security.
To go around patented protocol is another topic.

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 28 May 2012 01:09:53 -0700 (PDT)

Hello again,

On Sun, May 27, 2012 10:53 pm, [email-masked] wrote:
>> > K can be reduced to
>> PE^(peer_scalar*local_scalar+local_mask*peer_mask)
>> > "exchange"¡êo

  Part of your reduction requires knowledge of information that you cannot
have
so it doesn't work.

  What you are describing below is a *different* protocol.

> I am not sure about the usage of  PE^(peer_scalar*local_scalar) in the
> K£¬

  Not exactly SPEKE? It's SPEKE with extraneous computation which do
not add anything to the security of the exchange.

  Also, it is an open question whether "my protocol can be reduced to as
secure as SPEKE." That is what is prompting my request for help in this
forum. As Dr. Katz noted, it doesn't seem likely that the protocol can be
proven secure in the Random Oracle model, and I believe SPEKE can be
proven secure in the Random Oracle model.

> To go around patented protocol is another topic.

  If you believe the simpler the better then do away with the extraneous
elements
in the exchange you describe above. The secret information is "local_mask"
and "peer_mask". You are exchanging elements in the group using a secret
generator exponentiated to each side's respective secret information and
doing
a diffie-hellman exchange. Having each side multiply the result of the
diffie-hellman
by additional information-- 1, 8738, PE^8738 or
PE^(peer_scalar*local_scalar)--
doesn't really contribute anything to the security of the exchange.

  regards,

  Dan.

---

From: [email-masked]
Date: Mon, 28 May 2012 16:34:17 +0800

"Dan Harkins" <[email-masked]> 写于 2012-05-28 16:09:53:

>   Part of your reduction requires knowledge of information that you 
cannot
I have corrected the part of computation comparison in another email.
Yes, you are right, the computation saving is little, 
but you can save the exchange message. 

>   What you are describing below is a *different* protocol.
It looks different, but actually the same, I just take away the part
which can be directly calculated from the exchanged plain message.

> proven secure in the Random Oracle model.

even a little difference can lead to provable or un-provable. 
the original version of SPEKE  actually not have a proof of security,later 

a proof security is given on a slight variant of SPEKE , and not using 
ROM, but
using Shoup's simulation model.

And it is not clear if the "extraneous computation" can help the proof of 
security.

> doesn't really contribute anything to the security of the exchange.

It is not a new protocol I put forward, just a reduced version of your 
protocol,
PE^(Sa*Sb) alone is not safe, but in combination of PE^(Ma*Mb),maybe it 
can help the 
proof.

I have not done security proof for a long time, just hope this reduced 
version can 
help other people analysing your protocol.

---

From: [email-masked]
Date: Mon, 28 May 2012 17:08:30 +0800

>   What you are describing below is a *different* protocol.
You can call it a different new protocol, but it has the same security as 
your protocol and simpler.

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 28 May 2012 02:19:39 -0700 (PDT)

On Mon, May 28, 2012 1:34 am, [email-masked] wrote:
[snip[
> PE^(Sa*Sb) alone is not safe, but in combination of PE^(Ma*Mb),maybe it

  Let me repeat: you CANNOT do this "reduction" because it requires
knowledge of unknown variables, namely "Ma" and "Mb". You CANNOT
compute PE^(Ma*Mb) so this doesn't work!

  You have not "reduced" my protocol, you have just "rediscovered" a
different protocol and added some extraneous and frivolous computation
to it that serve no purpose  whatsoever.

> help other people analysing your protocol.

  I would ask anyone who is thinking of analyzing my protocol to please
just look at my protocol.

  Dan.

---

From: [email-masked]
Date: Mon, 28 May 2012 17:25:36 +0800

> compute PE^(Ma*Mb) so this doesn't work!

I don't have to know Ma Mb to compute PE^(Ma*Mb)
PE^(Ma*Mb)=(peer_element)^(-local_mask)

> just look at my protocol.
OK, then anyone trying to do this job may find themselvs this simpler 
version.