Re: [Cfrg] aPAKE Analysis

[Hugo Krawczyk <[e-mail]>]

Hi Uri,

On Wed, Sep 18, 2019 at 6:25 AM Blumenthal, Uri - 0553 - MITLL <
[e-mail]> 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 <[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.
>
> 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
>>>
>> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>