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

zhou.sujing@zte.com.cn Mon, 28 May 2012 05:34 UTC

Return-Path: <zhou.sujing@zte.com.cn>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 625AA21F845D for <cfrg@ietfa.amsl.com>; Sun, 27 May 2012 22:34:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -100.637
X-Spam-Level:
X-Spam-Status: No, score=-100.637 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, J_CHICKENPOX_22=0.6, J_CHICKENPOX_81=0.6, OBSCURED_EMAIL=0.001, RCVD_DOUBLE_IP_LOOSE=0.76, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id c47ZtgJMnxLj for <cfrg@ietfa.amsl.com>; Sun, 27 May 2012 22:34:50 -0700 (PDT)
Received: from mx5.zte.com.cn (mx5.zte.com.cn [63.217.80.70]) by ietfa.amsl.com (Postfix) with ESMTP id F1B0721F845C for <cfrg@irtf.org>; Sun, 27 May 2012 22:34:49 -0700 (PDT)
Received: from [10.30.17.100] by mx5.zte.com.cn with surfront esmtp id 62129344249031; Mon, 28 May 2012 13:29:36 +0800 (CST)
Received: from [10.30.3.20] by [192.168.168.16] with StormMail ESMTP id 93892.1065689647; Mon, 28 May 2012 13:34:43 +0800 (CST)
Received: from notes_smtp.zte.com.cn ([10.30.1.239]) by mse01.zte.com.cn with ESMTP id q4S5Yf2W094954; Mon, 28 May 2012 13:34:41 +0800 (GMT-8) (envelope-from zhou.sujing@zte.com.cn)
In-Reply-To: <a43e20169b5eb6135fbb4e8a5418ae00.squirrel@www.trepanning.net>
To: Dan Harkins <dharkins@lounge.org>
MIME-Version: 1.0
X-Mailer: Lotus Notes Release 6.5.6 March 06, 2007
Message-ID: <OF370FB4B5.1DE6804A-ON48257A0C.001C2358-48257A0C.001EADBE@zte.com.cn>
From: zhou.sujing@zte.com.cn
Date: Mon, 28 May 2012 13:34:40 +0800
X-MIMETrack: Serialize by Router on notes_smtp/zte_ltd(Release 8.5.1FP4|July 25, 2010) at 2012-05-28 13:34:42, Serialize complete at 2012-05-28 13:34:42
Content-Type: multipart/alternative; boundary="=_alternative 001EADBE48257A0C_="
X-MAIL: mse01.zte.com.cn q4S5Yf2W094954
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] password-based key exchange,revisited
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 28 May 2012 05:34:51 -0000

Regards~~~

-Sujing Zhou

"Dan Harkins" <dharkins@lounge.org> 写于 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, zhou.sujing@zte.com.cn 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.