Subject: [Cfrg] “password-based key exchange”revisited

From: [email-masked]
Date: Fri, 25 May 2012 09:39:52 +0800

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

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.

From: "Dan Harkins" <dharkins at lounge.org> 
Date: Tue, 20 Dec 2011 13:38:09 -0800 (PST) 
  Hello,

  I proposed a new TLS ciphersuite using a zero knowledge proof at
IETF 82 in Taipei. The draft is here:

       http://tools.ietf.org/html/draft-harkins-tls-pwd-01

At the TLS WG meeting I was requested to ask people on the CFRG list
with expertise in this field to take a look at it. So here I am, asking.
If someone has some spare cycles this holiday season, if you just gotta
get away from the relatives, or you are just feeling in the giving mood,
please take a look and comment. Any analysis on this would be greatly
appreciated. (I tried to do a formal proof but I cannot, and that's
what's prompting this).

  I can describe the key exchange broadly here. There are subtle
differences in the draft-- like one side keeps a salted version of the
password and communicates the salt during a HELLO message-- that don't
affect the exchange. It is symmetric so I can describe it from one side's
perspective. The side being described is "local" and the other side is
"peer", it goes like this:

Given: local ID, peer ID, password, an agreed-upon set of domain
parameters defining a finite field group (it works will elliptic
curve crypto too) and using two function:

  - E = HashToElement(d) which takes some data, d, and hashes into
    the finite field to return an element, E.
  - x = H(y) returns a random stream, x, given some input, y.

The key exchange works like this:

1. PE = HashToElement(local_ID | peer_ID | password)
   gets a "password element"

   There is an ordering defined in the draft to ensure that the IDs
   are put in the same order on each side.

2. generate 2 random numbers between 0 and the order of the group, q:

   0 < local_rand, local_mask < q

3. compute a scalar and an element:
   local_scalar = (local_rand + local_mask) mod q
   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 * peer_element)^local_rand mod p =
       (PE^(peer_rand + peer_mask) * PE^(-peer_mask))^local_rand mod p =
       PE^(peer_rand*local_rand) mod p

6. compute a confirmation

   local_confirm = H(K, local_scalar | local_element |
                     peer_scalar | peer_element)

   send confirmation to peer

7. receive peer's confirmation, calculate verifier

   verifier = H(K, peer_scalar | peer_element | local_scalar |
                local_element)

   if verifier equals peer's confirmation the peer is authenticated.

The peer does the same thing but from its perspective it is "local"
and the side described above is "peer".

  Thank you in advance for any analysis that can be provided on this
exchange.

  regards,

Regards~~~

-Sujing Zhou

---

From: "Dan Harkins" <[email-masked]>
Date: Sun, 27 May 2012 21:35:40 -0700 (PDT)

Hello,

  Thank you very much for your analysis of my protocol.

On Thu, May 24, 2012 6:39 pm, [email-masked] wrote:
> "exchange"£º

  The problem with this is that peer_mask is unknown so it is not possible
to reduce computation of K in this manner.

> It is simpler and less computation invloved, and hopefully easier to

  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.

  regards,

  Dan.

---

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

Regards~~~

-Sujing Zhou

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

> > =PE^(peer_scalar*local_scalar-peer_mask*local_scalar-
> local_mask*peer_scalar+local_mask*peer_mask)
> > mod p

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.

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