Re: [Cfrg] aPAKE Analysis

[Hugo Krawczyk <[e-mail]>]

Hi Jonathan, see below.

On Wed, Sep 18, 2019 at 6:10 AM Jonathan Hoyland <[e-mail]>
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.
>
> Unfortunately, even with a seemingly simple, modular protocol like OPAQUE,
proofs (and the underlying models) are very challenging.  Adding blinding
elements  to the OPRF would not be a trivial change, and may be a too high
price to pay in complexity and computation. I have trouble imagining that
the value of my password not being found in 20 years is worth trillions of
additional exponentiations in the next 20 years (assuming the protocol is
widely  used in practice, otherwise it makes no difference if it is or it
is not quantum annoying).

Being quantum ready seems more important to me, so  I am glad that you say

>  I agree that you could describe OPAQUE as post-quantum ready

I was thinking of changing the acronym to Oblivious Password Authentication
for the QUantum Era
(just kidding :-)

Hugo


Regards,
>
> Jonathan
>
> On Tue, 17 Sep 2019 at 21:19, Hugo Krawczyk <[e-mail]>
> 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 <
>> [e-mail]> 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, <[e-mail]> 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
>>>> [e-mail]
>>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> [e-mail]
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>
>>