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

[[e-mail]]

Regards~~~

-Sujing Zhou

"Dan Harkins" <[e-mail]> 写于 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, [e-mail] 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"£º
> 
>   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:

just need to exchange local_element instead of both local_element and 
local_scalar;
in computation of K  (=PE^(peer_scalar*local_scalar+local_mask*peer_mask) 
mod p), only 
one field power multiple instead of  two field power multiple in (K = 
(PE^peer_scalar * peer_element)^local_rand mod p )
(power multiple is the most costly part)

It just needs a simple computation to get to this result.


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