Re: [Cfrg] aPAKE Analysis

Wang Guilin <Wang.Guilin@huawei.com> Thu, 19 September 2019 08:49 UTC

Return-Path: <Wang.Guilin@huawei.com>
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 D5CC61200B8 for <cfrg@ietfa.amsl.com>; Thu, 19 Sep 2019 01:49:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Level:
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vLLqyB4BGiTw for <cfrg@ietfa.amsl.com>; Thu, 19 Sep 2019 01:48:57 -0700 (PDT)
Received: from huawei.com (szxga02-in.huawei.com [45.249.212.188]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0A91B120048 for <cfrg@irtf.org>; Thu, 19 Sep 2019 01:48:57 -0700 (PDT)
Received: from DGGEMM405-HUB.china.huawei.com (unknown [172.30.72.57]) by Forcepoint Email with ESMTP id 9EA9E1EFE4672E90442F for <cfrg@irtf.org>; Thu, 19 Sep 2019 16:48:53 +0800 (CST)
Received: from sineml705-chm.china.huawei.com (10.223.161.112) by DGGEMM405-HUB.china.huawei.com (10.3.20.213) with Microsoft SMTP Server (TLS) id 14.3.439.0; Thu, 19 Sep 2019 16:48:52 +0800
Received: from sineml702-chm.china.huawei.com (10.223.161.109) by sineml705-chm.china.huawei.com (10.223.161.112) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1713.5; Thu, 19 Sep 2019 16:48:51 +0800
Received: from sineml702-chm.china.huawei.com ([10.223.161.109]) by sineml702-chm.china.huawei.com ([10.223.161.109]) with mapi id 15.01.1713.004; Thu, 19 Sep 2019 16:48:51 +0800
From: Wang Guilin <Wang.Guilin@huawei.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
CC: Wang Guilin <Wang.Guilin@huawei.com>
Thread-Topic: aPAKE Analysis
Thread-Index: AdVuwAhoxNiBA9DERQ+ymg1OlONdoQ==
Date: Thu, 19 Sep 2019 08:48:51 +0000
Message-ID: <37dbbed959ff4e7891868bea1de0065d@huawei.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.215.37.186]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-CFilter-Loop: Reflected
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/zb_pAg2Xpy5R-vspT08LXXhH0VI>
Subject: Re: [Cfrg] aPAKE Analysis
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 19 Sep 2019 08:49:02 -0000

Dear Jonathan, Uri, Hugo, 

It is interesting to see your discussions on PQ PAKE in the following message 3. I have two further comments here. 

1) Asking PQ PAKE may be too much for this round of PAKE Selection in CFRG, as this has not been listed as one requirement / target for this selection. In fact, none of the eight candidates of 8 PAKE schemes are claimed to be PQ safe by the authors/nominators, if I am not wrong. Yes, PQ PAKE is very interesting but it seems that there are no too much research yet [1]. Also, though there are quite some progress in building quantum computers and standardizing QP algorithms in NIST, it is still not clear when quantum attacks will become a real threat. Due to this, it may sound reasonable if CFRG postpones PQ PAKE for consideration in the future. 

In this aspect, I do agree with Jonathan on his comments: Constructing "quantum-annoying" PAKE "would be valuable". 

2) Is OPAQUE PQ ready? Not sure, I think. As Hugo mentioned below, a good feature of OPAQUE is its generic composition. Therefore, a combination of PQ OPRF and PQ AKE may generate a PQ  OPAQUE. However, this may be just an intuitive construction, as the security proof of  OPAQUE [2] is analyzed in classic adversary model rather than in quantum adversary model and the security proofs in these two models can be very different. So, before strict security analysis is done, it is hard to say if such an intuitive construction is a PQ PAKE or not, without mentioning other issues like efficiency, as Hugo pointed out. 

References: 
[1] https://arxiv.org/abs/1904.01526 
[2] https://eprint.iacr.org/2018/163.pdf

Cheers,

Guilin

-----Original Message-----
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of cfrg-request@irtf.org
Sent: Thursday, September 19, 2019 2:07 PM
To: cfrg@irtf.org
Subject: Cfrg Digest, Vol 173, Issue 35

Send Cfrg mailing list submissions to
	cfrg@irtf.org

To subscribe or unsubscribe via the World Wide Web, visit
	https://www.irtf.org/mailman/listinfo/cfrg
or, via email, send a message with subject or body 'help' to
	cfrg-request@irtf.org

You can reach the person managing the list at
	cfrg-owner@irtf.org

When replying, please edit your Subject line so it is more specific than "Re: Contents of Cfrg digest..."


Today's Topics:

   1. Re: Call for adoption: draft-hdevalence-cfrg-ristretto-01
      (Christopher Wood)
   2. Re: Call for adoption: draft-hdevalence-cfrg-ristretto-01
      (Christopher Wood)
   3. Re: aPAKE Analysis (Hugo Krawczyk)


----------------------------------------------------------------------

Message: 1
Date: Wed, 18 Sep 2019 15:36:15 -0700
From: "Christopher Wood" <caw@heapingbits.net>
To: cfrg@irtf.org
Subject: Re: [Cfrg] Call for adoption:
	draft-hdevalence-cfrg-ristretto-01
Message-ID: <161fc653-2cab-4c6d-812b-92d2e426719d@www.fastmail.com>
Content-Type: text/plain

I'm in favor of adoption as well, though am curious to know where folks stand on the issues discussed in [1] and earlier messages. What is the plan for reconciling this with the hash-to-curve draft? Of the three options Filippo outlines in [2], the third seems the most appealing and probably the most workable, though does muddy the "curve" focus of hash-to-curve.

Best,
Chris

[1] https://mailarchive.ietf.org/arch/msg/cfrg/w91AdGVdLWccafiPub862MObk5c
[2] https://mailarchive.ietf.org/arch/msg/cfrg/p_r53FtGcaNSB_HwIV0J9FSgYbg

On Wed, Sep 18, 2019, at 10:38 AM, Richard Barnes wrote:
> I am not in a position to evaluate the mathematics of this proposal, 
> but the idea of a curve that files down some of the unnecessary "sharp 
> edges" of Curve25519 is welcome.
>
> As has been discussed previously on this list, it is helpful in some 
> contexts to have DH groups in which scalar multiplication commutes 
> with the private-to-public-key map, since this allows public keys to 
> be transformed in a way that the corresponding transformations on 
> private keys are clear. This is the case for the traditional NIST ECDH 
> curves, but not for Curve25519, due to the "clamping" it requires. If 
> I understand correctly, Ristretto would have this property, and so 
> would in some cases effectively be a more useful version of Curve25519.
> 
> --RLB
> 
> On Wed, Sep 18, 2019 at 12:45 PM Alexey Melnikov 
> <alexey.melnikov@isode.com> wrote:
> > Dear CFRG participants,
> > 
> >  This email commences a 2-week call for adoption for
> >  draft-hdevalence-cfrg-ristretto-01 that will end on October 2nd 2019:
> > 
> > https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/
> > 
> >  Please give your views on whether this document should be adopted 
> > as a  CFRG draft, and if so, whether you'd be willing to help work 
> > on  it/review it. Please reply to this email (or in exceptional  
> > circumstances you can email CFRG chairs directly at cfrg-chairs@ietf.org).
> > 
> >  Thank you,
> >  Alexey (for the chairs)
> > 
> >  _______________________________________________
> >  Cfrg mailing list
> > Cfrg@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>



------------------------------

Message: 2
Date: Wed, 18 Sep 2019 16:27:07 -0700
From: "Christopher Wood" <caw@heapingbits.net>
To: cfrg@irtf.org
Subject: Re: [Cfrg] Call for adoption:
	draft-hdevalence-cfrg-ristretto-01
Message-ID: <1ac02093-aac8-4235-842f-57059cc9cd8a@www.fastmail.com>
Content-Type: text/plain

On Wed, Sep 18, 2019, at 3:36 PM, Christopher Wood wrote:
> I'm in favor of adoption as well, though am curious to know where 
> folks stand on the issues discussed in [1] and earlier messages. What 
> is the plan for reconciling this with the hash-to-curve draft? Of the 
> three options Filippo outlines in [2], the third seems the most 
> appealing and probably the most workable, though does muddy the 
> "curve" focus of hash-to-curve.

Of course, if we're willing to budge on the API, there's also option #4 wherein FROM_UNIFORM_BYTES is replaced with FROM_BYTES that, internally, invokes hash-to-curve as needed. 

Best,
Chris

> [1] 
> https://mailarchive.ietf.org/arch/msg/cfrg/w91AdGVdLWccafiPub862MObk5c
> [2] 
> https://mailarchive.ietf.org/arch/msg/cfrg/p_r53FtGcaNSB_HwIV0J9FSgYbg
> 
> On Wed, Sep 18, 2019, at 10:38 AM, Richard Barnes wrote:
> > I am not in a position to evaluate the mathematics of this proposal, 
> > but the idea of a curve that files down some of the unnecessary 
> > "sharp edges" of Curve25519 is welcome.
> >
> > As has been discussed previously on this list, it is helpful in some 
> > contexts to have DH groups in which scalar multiplication commutes 
> > with the private-to-public-key map, since this allows public keys to 
> > be transformed in a way that the corresponding transformations on 
> > private keys are clear. This is the case for the traditional NIST 
> > ECDH curves, but not for Curve25519, due to the "clamping" it 
> > requires. If I understand correctly, Ristretto would have this 
> > property, and so would in some cases effectively be a more useful version of Curve25519.
> > 
> > --RLB
> > 
> > On Wed, Sep 18, 2019 at 12:45 PM Alexey Melnikov 
> > <alexey.melnikov@isode.com> wrote:
> > > Dear CFRG participants,
> > > 
> > >  This email commences a 2-week call for adoption for
> > >  draft-hdevalence-cfrg-ristretto-01 that will end on October 2nd 2019:
> > > 
> > > https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/
> > > 
> > >  Please give your views on whether this document should be adopted 
> > > as a  CFRG draft, and if so, whether you'd be willing to help work 
> > > on  it/review it. Please reply to this email (or in exceptional  
> > > circumstances you can email CFRG chairs directly at cfrg-chairs@ietf.org).
> > > 
> > >  Thank you,
> > >  Alexey (for the chairs)
> > > 
> > >  _______________________________________________
> > >  Cfrg mailing list
> > > Cfrg@irtf.org
> > > https://www.irtf.org/mailman/listinfo/cfrg
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg
> >
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>



------------------------------

Message: 3
Date: Thu, 19 Sep 2019 02:06:19 -0400
From: Hugo Krawczyk <hugo@ee.technion.ac.il>
To: "Blumenthal, Uri - 0553 - MITLL" <uri@ll.mit.edu>
Cc: Jonathan Hoyland <jonathan.hoyland@gmail.com>,
	"bjoern.m.haase@web.de" <bjoern.m.haase@web.de>, cfrg <cfrg@irtf.org>
Subject: Re: [Cfrg] aPAKE Analysis
Message-ID:
	<CADi0yUM7TLnuaaqN4XShpBYnQQC1gtjXi0jyRmKToG4ppWrPdg@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"

Hi Uri,

On Wed, Sep 18, 2019 at 6:25 AM Blumenthal, Uri - 0553 - MITLL < uri@ll.mit.edu> wrote:

> One naive question in the PQ context.
>
> Hugo mentioned a possible PQ AKE, as in NIST competition. I don't 
> recall any submission that included AKE. What did I miss?
>

You can build AKEs from the modules NIST standardizes: KEMs, public key encryption, etc. So, I expect that when you have these modules you have PQ AKE.


> Regards,
> Uri
>
> Sent from my iPhone
>
> On Sep 18, 2019, at 06:10, Jonathan Hoyland 
> <jonathan.hoyland@gmail.com>
> wrote:
>
> Bj?rn: The specific issue I have with AuCPace is that the AuCPace 
> substep has to happen before the CPace substep, which means that you 
> need to have a roundtrip before you start TLS.
> I think that the pre-TLS phase is going to be difficult to actually 
> implement and deploy, will probably have unacceptable performance, and 
> leaks the username, which is a far more serious vulnerability than 
> lack of quantum annoyingness.
> I think if there was a construction that let you use a balanced PAKE 
> first and then do an augmentation step second, then simply integrating 
> a balanced PAKE into TLS might be an acceptable solution.
> The other option is to run the AuCPace and CPace substeps over a TLS 
> connection, once it has been established, and do some sort of channel 
> binding on top, which adds two roundtrips.
> I'll specifically address the subsystem question in the other thread.
>
> Hugo: I agree that you could describe OPAQUE as post-quantum ready, 
> but I rather suspect that before this process is through we'll have 
> taken the best pieces of each PAKE and mashed them together. If we 
> could make OPAQUE quantum-annoying by construction I think that would 
> be valuable. Especially if we can do it in such a way that the proofs 
> still hold / can be easily tweaked.
>
> Regards,
>
> Jonathan
>
> On Tue, 17 Sep 2019 at 21:19, Hugo Krawczyk <hugo@ee.technion.ac.il>
> wrote:
>
>> Jonathan, I have not looked into making OPAQUE quantum annoying. I 
>> assume that one can do it with some password-based blinding but then 
>> it would be a different protocol.  But OPAQUE is better in other 
>> important ways, both with respect to a quantum future and present reality.
>>
>> A main point in OPAQUE design (in addition to being secure against 
>> pre-computation attacks and efficient) is its modularity. Namely, the 
>> generic composition of *any* OPRF with *any* KCI authenticated key 
>> exchange
>> (AKE) protocol. In particular, it means that you can implement it 
>> with a PQ AKE (as in NIST competition) and a PQ OPRF.
>>
>> The latter seems to be missing from our current PQ arsenal but one 
>> will be built much before quantum becomes a reality (more precisely 
>> we do have PQ OPRFs, based on 2-party computation, but I am talking 
>> about more efficient ones).
>>
>> Once we have the PQ OPRF, OPAQUE is quantum READY (not sure you can 
>> say that for other proposals, at least without specialized components 
>> and analysis).
>>
>> As for the task of building a PQ OPRF note that we do not really need 
>> an Oblivious PRF but rather an Oblivious Weak Unpredictable function. 
>> That is, a function whose output is hard to guess when computed on random inputs.
>> This is a much weaker primitive than full fledged PRF (the reason 
>> this suffices for our purposes is that both input and output are 
>> processed by a random oracle).
>>
>> Hugo
>>
>> On Tue, Sep 17, 2019 at 8:15 AM Jonathan Hoyland < 
>> jonathan.hoyland@gmail.com> wrote:
>>
>>> Hi Steve,
>>>
>>> It's interesting what you say about OPAQUE not being quantum annoying.
>>> I initially thought it would be easy to tweak OPAQUE to make it so, 
>>> but even after a some thought it's unclear to me that you can make 
>>> OPAQUE quantum-annoying / quantum secure without substantive changes.
>>>
>>> Because of the AEAD/key committing requirement of the Envelope you 
>>> can always verify a guess if you can derive the salt.
>>>
>>> I'm also not aware of any quantum alternatives to current OPRF 
>>> constructions, so it's not obvious that you could just compile a 
>>> quantum-secure variant.
>>>
>>> An attacker is still limited to one DLP solve per user, but after 
>>> that it's classically brute-forcible.
>>>
>>> I'd be very interested what other people think of ways to make 
>>> OPAQUE quantum annoying.
>>>
>>> BSPAKE is very similar to OPAQUE in structure so it's probably 
>>> do-able with some thought.
>>>
>>> The issue with AuCPace is that it's complicated to bind to TLS 
>>> without adding two round trips, but I'm sure the issues aren't insurmountable.
>>>
>>> Regards,
>>>
>>> Jonathan
>>>
>>> On Tue, 17 Sep 2019 at 07:21, <steve@tobtu.com> wrote:
>>>
>>>> TL;DR AuCPace (with blind salt) is the best submitted algorithm, 
>>>> but B-SPEKE (with blind salt), which was not submitted, might be 
>>>> better. Also OPAQUE and VTBPEKE should not be used due to having 
>>>> bad properties and/or not having good properties.
>>>>
>>>>
>>>> Good properties in an aPAKE: low complexity, low cost, not fragile, 
>>>> prevents precomputation, quantum annoying, and minimal trips.
>>>>
>>>> * Fragile is you give an attacker offline password guessing if 
>>>> there is a minor error in the implementation of ECC (CVE-2017-8932, 
>>>> Dragonblood, timing attacks, etc).
>>>> * Quantum annoying is an attacker with a quantum computer needs to 
>>>> solve a DLP per password guess.
>>>>
>>>> Hmm I found another property "forward secrecy" from a VTBPEKE 
>>>> paper, but I can't find their definition. It's obviously not actual 
>>>> forward secrecy since I know SPAKE2, SPEKE, SRP6a, and SPAKE2+ 
>>>> don't leak the session key if the password is later known. Never 
>>>> mind found their definition and their comparison chart is just 
>>>> wrong. Oh I think they by "no" they mean it wasn't proven to have 
>>>> forward secrecy as part of the security proof.
>>>>
>>>> Augmented PAKE summary
>>>> Name    | PQ-ish | Trips*  | Precomp** | Fragile
>>>> --------+--------+---------+-----------+---------
>>>> AuCPace | Good   | 4 (2/3) | Bad       | Good
>>>> BSPAKE  | Good   | 4 (2/3) | Good      | Good
>>>> OPAQUE  | Bad    | 3 (2/1) | Good      | Bad
>>>> VTBPEKE | Bad    | 4 (2/3) | Bad       | Good
>>>>
>>>> Augmented PAKE summary (continued)
>>>> Name    | Client Cost          | Server Cost
>>>> --------+----------------------|------------------
>>>> AuCPace | ff*iH**[ii]          | **[ii]H*if*i
>>>> BSPAKE  | H*iffI*i*H+H-**[iii] | f**+[ii]f-**[ii]
>>>> OPAQUE  | H**[ii]ffI*ix*+*i    | ff**x*+*[iii]
>>>> VTBPEKE | *if*+**[iii]x        | *if*idi
>>>>
>>>> * "number of total trips" ("number of trips to client can 
>>>> encrypt"/"number of trips to server can encrypt")
>>>> ** Preventing precomputation is a minor change. All you need to do 
>>>> is add blind salt. AuCPace and VTBPEKE can add blind salt without 
>>>> any extra trips. Also I just read that AuCPace has this as an option in a paper.
>>>>
>>>> Cost:
>>>> d: Double scalar point multiple and add "a * B + c * D"
>>>> *: Scalar point multiple
>>>> H: Hash to point
>>>> i: Field invert
>>>> I: Scalar invert
>>>> f: From bytes (field square root or free for Montgomery curves)
>>>> -: Point subtraction
>>>> +: Point addition
>>>> x: Field multiplication
>>>> [ii...]: Field inverts that can be combined. Cost is 1 field invert 
>>>> and
>>>> 3*(n-1) field multiplications.
>>>>
>>>> Note that trips for client/server to be authenticated is one more 
>>>> than when they can encrypt because at that point they can also 
>>>> authenticate but haven't.
>>>>
>>>> OPAQUE is fragile and not quantum annoying and thus the worst of 
>>>> the four. Only good part is it needs fewer trips for the server to 
>>>> authenticate and/or send encrypted data.
>>>>
>>>> OPAQUE (as stated in https://eprint.iacr.org/2018/163 figures 9 and
>>>> 10) is fragile because all you need is the salt value from the 
>>>> server ("k_s" or "k" depending on which part of the paper you are 
>>>> reading). You can send the server any valid point and receive the 
>>>> salt applied to it which could be recovered by CVE-2017-8932. Once 
>>>> you have the salt, you can make offline password guesses by trying 
>>>> to decrypt the user encrypted data ("c").
>>>>
>>>> OPAQUE is not quantum annoying because you only need to solve 1 DLP 
>>>> to get offline classical computer password guessing. Also it 
>>>> suffers from a weaker form as an attacker does not need to observe 
>>>> a successful exchange to start their attack. With AuCPace, BSPAKE, 
>>>> and VTBPEKE an attacker needs to observe a successful exchange or 
>>>> masquerade as the server to start an attack.
>>>>
>>>> VTBPEKE is not quantum annoying because you only need to solve 2 
>>>> DLPs to get offline classical computer password guessing.
>>>> Solve DLP to get u: U = u * V
>>>> Given X: X = x * G where G = U + pw * V X = x * (U + pw * V) X = x 
>>>> * (u * V + pw * V) X = (x * (u + pw)) * V Solve DLP to get z: X = z 
>>>> * V Now guess a password to get assumed x (x' = z / (u + pw)) test 
>>>> if x' is correct.
>>>>
>>>> -----------------------------------------------------------
>>>>
>>>> After looking at all the submissions. The best two are AuCPace and 
>>>> BSPAKE. If you add blind salt to AuCPace then I would say that's 
>>>> the best as it's less complex and lower cost than BSPAKE. Also 
>>>> AuCPace doesn't require point addition so it can use Montgomery 
>>>> curves (like X25519). For hash to point X25519 is faster than 
>>>> Ed25519 because with Elligator you generate a X25519 point then 
>>>> convert to Ed25519. Which costs a field invert and square root.
>>>>
>>>> What I'd really like to know is which is better AuCPace or B-SPEKE 
>>>> (or B-SPEKE' "modified B-SPEKE"). B-SPEKE (or B-SPEKE') was not 
>>>> submitted but has all the desired properties (like AuCPace) but is 
>>>> less complex/cost than AuCPace. Also B-SPEKE can use Montgomery 
>>>> curves, like AuCPace, which means "from bytes" is free. I want to 
>>>> say B-SPEKE' (with blind salt) is the best due to low server costs 
>>>> because HSMs are expensive and slow. I understand why CPace added 
>>>> the "s" and "t" random values to SPEKE, but I don't think this adds 
>>>> value to AuCPace vs B-SPEKE (or B-SPEKE'). One last thing B-SPEKE' 
>>>> is a modified version of B-SPEKE that I came up with. Thus it might 
>>>> be broken and obviously invalidates any proofs. It's just SPEKE 
>>>> with an extra term "b * v * P" (b: server ephemeral key, v: derived 
>>>> from password, P: hash to point from password). This is basically the change from SPAKE2 to SPAKE2+.
>>>>
>>>> Name     | Client Cost | Server Cost
>>>> ---------+-------------|---------------
>>>> AuCPace  | ff*iH**[ii] | **[ii]H*if*i B-SPEKE  | ffH***[iii] | 
>>>> **[ii]f**[ii] B-SPEKE' | fH***[iii]  | *if**[ii]
>>>>
>>>> Note to add blind salt to each of these it adds the same cost: 
>>>> client
>>>> (H*ifI*i) and server (f*[i]). The server field invert is combined 
>>>> to other field invert(s) thus it costs 3 field multiples.
>>>>
>>>> -----------------------------------------------------------
>>>> -----------------------------------------------------------
>>>>
>>>> ****************
>>>> ** Algorithms **
>>>> ****************
>>>>
>>>> Note these might not be accurate. If something above is wrong it 
>>>> might stem from an error below.
>>>>
>>>> AuCPace
>>>> Both have:
>>>>       G = generator
>>>> Client has:
>>>>       idC = client identity
>>>> Server has these for "idC":
>>>>       salt
>>>>       settings
>>>>       W = w * G
>>>>
>>>> C:    t = random()
>>>> C->S: idC, t
>>>>    S: s = random()
>>>>    S: ssid = H(s, t)
>>>>    S: x = random()
>>>>    S: X = x * G
>>>>    S: a = random()
>>>>    S: A = a * hashToPoint(H(ssid, x * W, idC))
>>>> C<-S: s, X, A, salt, settings
>>>> C:    w = pwKdf(pw, salt, settings)
>>>> C:    ssid = H(s, t)
>>>> C:    b = random()
>>>> C:    B = b * hashToPoint(H(ssid, w * X, idC))
>>>> C:    K = H(ssid, b * A)
>>>> C->S: B, verifier_C[, encryptedData_C]
>>>>    S: K = H(ssid, a * B)
>>>> C<-S: verifier_S[, encryptedData_S]
>>>>
>>>> -----------------------------------------------------------
>>>>
>>>> B-SPEKE
>>>> Both have:
>>>>       G = generator
>>>> Client has:
>>>>       idC = client identity
>>>> Server has these for "idC":
>>>>       salt
>>>>       settings
>>>>       P = hashToPoint(p)
>>>>       V = v * G
>>>>
>>>> C->S: idC
>>>>    S: b = random()
>>>>    S: B = b * P
>>>>    S: x = random()
>>>>    S: X = x * G
>>>> C<-S: B, X, salt, settings
>>>> C:    p, v = pwKdf(pw, salt, settings)
>>>> C:    P = hashToPoint(p)
>>>> C:    a = random()
>>>> C:    A = a * P
>>>> C:    K = H(idC, idS, A, B, a * B, v * X)
>>>> C->S: A, verifier_C[, encryptedData_C]
>>>>    S: K = H(idC, idS, A, B, b * A, x * V)
>>>> C<-S: verifier_S[, encryptedData_S]
>>>>
>>>> -----------------------------------------------------------
>>>>
>>>> B-SPEKE'
>>>> Client has:
>>>>       idC = client identity
>>>> Server has these for "idC":
>>>>       salt
>>>>       settings
>>>>       P = hashToPoint(p)
>>>>       V = v * P
>>>>
>>>> C->S: idC
>>>>    S: b = random()
>>>>    S: B = b * P
>>>> C<-S: B, salt, settings
>>>> C:    p, v = pwKdf(pw, salt, settings)
>>>> C:    P = hashToPoint(p)
>>>> C:    a = random()
>>>> C:    A = a * P
>>>> C:    K = H(idC, idS, A, B, a * B, v * B)
>>>> C->S: A, verifier_C[, encryptedData_C]
>>>>    S: K = H(idC, idS, A, B, b * A, b * V)
>>>> C<-S: verifier_S[, encryptedData_S]
>>>>
>>>> -----------------------------------------------------------
>>>>
>>>> BSPAKE
>>>> Both have:
>>>>       G = generator
>>>>       idS = server identity
>>>> Client has:
>>>>       idC = client identity
>>>> Server has these for "idC":
>>>>       salt
>>>>       settings
>>>>       BlindC = hashToPoint(clientBlind)
>>>>       BlindS = hashToPoint(serverBlind)
>>>>       k3
>>>>       V = v * G
>>>>
>>>> C:    r = random()
>>>> C:    R = r * hashToPoint(H(password, idC, idS))
>>>> C->S: idC, R
>>>>    S: b = random()
>>>>    S: B = b * G + BlindS
>>>>    S: R' = H(salt) * R
>>>> C<-S: B, R', settings
>>>> C:    BlindSalt = (1/r) * R'
>>>> C:    clientBlind || serverBlind || k3 || v
>>>>           = pwKdf(password, BlindSalt, idC, idS, settings)
>>>> C:    a = random()
>>>> C:    A = a * G + hashToPoint(clientBlind)
>>>> C:    B' = B - hashToPoint(serverBlind)
>>>> C:    K = H(idC, idS, A, B, a * B', k3, v * B')
>>>> C->S: A, verifier_C[, encryptedData_C]
>>>>    S: A' = A - BlindC
>>>>    S: K = H(idC, idS, A, B, b * A', k3, b * V)
>>>> C<-S: verifier_S[, encryptedData_S]
>>>>
>>>> -----------------------------------------------------------
>>>>
>>>> OPAQUE
>>>> Both have:
>>>>       G = generator
>>>> Client has:
>>>>       idC = client identity
>>>> Server has these for "idC":
>>>>       salt
>>>>       settings
>>>>       ct = AuthEnc(k, c, C, S)
>>>>       s = random()
>>>>       S = s * G
>>>>       C = c * G
>>>>
>>>> C:    r = random()
>>>> C:    R = r * hashToPoint(H(pw))
>>>> C:    a = random()
>>>> C:    A = a * G
>>>> C->S: idC, A, R
>>>>    S: R' = H(salt) * R
>>>>    S: b = random()
>>>>    S: B = b * G
>>>>    S: K = H((b + H(B, idC) * s) * (A + H(A, idS) * C))
>>>> C<-S: B, R', ct, settings, verifier_S[, encryptedData_S]
>>>> C:    BlindSalt = (1/r) * R'
>>>> C:    k = pwKdf(pw, BlindSalt, settings)
>>>> C:    c, C, S = AuthEnc(k, ct)
>>>> C:    K = H((a + H(A, idS) * c) * (B + H(B, idC) * S))
>>>> C->S: verifier_C[, encryptedData_C]
>>>>
>>>> -----------------------------------------------------------
>>>>
>>>> VTBPEKE
>>>> Both have:
>>>>       V = generator
>>>>       U = generator
>>>>       idS = server identity
>>>> Client has:
>>>>       idC = client identity
>>>> Server has these for "idC":
>>>>       salt
>>>>       settings
>>>>       G = U + p * V
>>>>
>>>> C:    a   = random()
>>>> C:    R   = a * V
>>>> C:    R'  = H(11, R)
>>>> C->S: idC, R'
>>>>    S: y   = random()
>>>>    S: Y   = y * G
>>>>    S: e   = random()
>>>> C<-S: Y, e, salt, settings
>>>> C:    p   = pwKdf(pw, salt, settings)
>>>> C:    V'  = p * V
>>>> C:    G   = U + V'
>>>> C:    x   = random()
>>>> C:    X   = x * G
>>>> C:    Z   = x * Y
>>>> C:    K_e = H(01, idC, idS, G, X, Y, Z, R', salt, e)
>>>> C:    p'  = a + e * p
>>>> C:    o   = enc(K_e, p')
>>>> C:    K   = H(00, idC, idS, G, X, Y, Z, R', salt, e, o)
>>>> C->S: X, o[, encryptedData_C]
>>>>    S: Z   = y * X
>>>>    S: K_e = H(01, idC, idS, G, X, Y, Z, R', salt, e)
>>>>    S: p'  = dec(K_e, o)
>>>>    S: R   = p' * V - e * V'
>>>>    S: R' == H(11, R)
>>>>    S: K   = H(00, idC, idS, G, X, Y, Z, R', salt, e, o)
>>>> C<-S: verifier_S[, encryptedData_S]
>>>>
>>>> _______________________________________________
>>>> Cfrg mailing list
>>>> Cfrg@irtf.org
>>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> Cfrg@irtf.org
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>
>> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailarchive.ietf.org/arch/browse/cfrg/attachments/20190919/eee9a6c3/attachment.html>

------------------------------

Subject: Digest Footer

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg


------------------------------

End of Cfrg Digest, Vol 173, Issue 35
*************************************