Subject: [Cfrg] aPAKE Analysis

From: [email-masked]
Date: Tue, 17 Sep 2019 01:21:08 -0500 (CDT)

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]

---

From: Jonathan Hoyland <[email-masked]>
Date: Tue, 17 Sep 2019 13:14:07 +0100

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, <[email-masked]> 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).
> 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
> ** 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:
> 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.
> 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+.
>
> 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.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Björn Haase <[email-masked]>
Date: Tue, 17 Sep 2019 19:12:32 +0200

Hi Jonathan,

> adding two round trips, but I'm sure the issues aren't insurmountable.
The question that is in my opinion not yet really answered is, how far
we aim at supporting the "human-user" login support for TLS. Once you
are dealing with passwords you *have* to answer also questions such as

- How does the application trigger a re-authentication?

- How would the user be changing his passwords?

- How would we be adding users?

In my opinion, there should be some "security subsystem" clearly
separated from the normal "application" that handles the "functional
code". My main job is design of explosion-protected intrinsically safe
electronics. There we make a clear distinction between the "functional
subsystem" and the "intrinsic safety subsystem" which we try to keep as
separate as possible in order to avoid the risk of accidental hazards.

I think such type of a concept would be also very helpful for an
application with security needs.

For handling passwords, I see the need for the "security subsystem" to
arrange for all of the rather complex configuration topics (password
changes, user management, re-authentication, change-privileges, etc.). 
A comprehensive solution (where PAKE is nothing but one important
building block) will need far more than what we would be willing or able
to offer by the TLS component.

For this reason, I am advocating to rather design TLS to be one
important but rather small building block which provides interfaces to
other components which in its entity would provide the "security
subsystem". For this reason, I am rather suggesting to do two things

- Integrate a balanced PAKE such as CPace into TLS

- At the same time provide the necessary interfaces to TLS such that we
could build up an augmented and pre-computation-attack resistant PAKE on
top of CPace. This is essentially, what I am suggesting to do with
AuCPace. The "Au"-Part would end up in components such as Linux's PAM
(server side) and password managers (client side) and the "CPace" part
would become integral part of TLS.

This would also solve the round-trip problem in my opinion. Note that
the fact that AuCPace could also run in a conventional
non-precomputation-attack-resistant mode, would make it possible to use
it with today's form of PAM-style user credential databases. If PAM gets
upgraded one day, one could also offer pre-computation-attack resistance
in a second step.

Yours,

Björn.

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 17 Sep 2019 16:18:54 -0400

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 <[email-masked]>
wrote:

> An attacker is still limited to one DLP solve per user, but after that
> it's classically brute-forcible.
>
> BSPAKE is very similar to OPAQUE in structure so it's probably do-able
> with some thought.
>
>> 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
>> * "number of total trips" ("number of trips to client can
>> encrypt"/"number of trips to server can encrypt")
>> 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
>> 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.
>>
>> 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.
>>

---

From: Jonathan Hoyland <[email-masked]>
Date: Wed, 18 Sep 2019 11:09:50 +0100

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 <[email-masked]> wrote:

> On Tue, Sep 17, 2019 at 8:15 AM Jonathan Hoyland <
> [email-masked]> wrote:
>
>> Hi Steve,
>>
>>> * 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).
>>> ** 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:

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 19 Sep 2019 02:06:19 -0400

Hi Uri,

On Wed, Sep 18, 2019 at 6:25 AM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> 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 <[email-masked]>
> 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.
>>
>> 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).
>>
>>>> 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
>>>> 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").
>>>>
>>>> VTBPEKE is not quantum annoying because you only need to solve 2 DLPs
>>>> to get offline classical computer password guessing.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 18 Sep 2019 10:25:10 +0000

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

Regards,
Uri

Sent from my iPhone

> On Sep 18, 2019, at 06:10, Jonathan Hoyland <[email-masked]> 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.
> 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
> 
>> 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 <[email-masked]> wrote:
>>> Hi Steve, 
>>> 
>>> 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
>>>

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 19 Sep 2019 02:05:18 -0400

Hi Jonathan, see below.

On Wed, Sep 18, 2019 at 6:10 AM Jonathan Hoyland <[email-masked]>
wrote:

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

---

From: Björn Haase <[email-masked]>
Date: Sun, 22 Sep 2019 21:03:44 +0200

Dear Jonathan,

Am 18.09.2019 um 12:09 schrieb Jonathan Hoyland:
> 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 understand your concerns but still I am convinced that this is a
problem that we will be having anyway. In my perception we will have to
face the situation that the method for authentication to use is up to
the choice of the server within the most important application settings.

In my perception we will be having at least the settings
1.) "Password over certificate-authenticated TLS"
2.) "aPAKE authenticated TLS"
3.) "aPAKE + 2FA TLS".

Depending on the actual setting of the server, which the HMI client will
not be knowing beforehand (at least for the case of the https://
web-server) the client side will not be able to provide all of the
required information in the first client hello.

As pointed out in my slides

https://github.com/BjoernMHaase/fe25519/blob/master/Concept_For_Modularized_PAKE_integration_into_TLS_20190726.pdf

on page 22, I also don't see any performance issue for the HMI interface.

My suggestion on what could best be implemented is the following approach.

The Client tries a conventional Web-PKI-based TLS connection attempt as
usual with its ClientHello. In this ClientHellow it informs the server
that it also supports "aPAKE" and "aPAKE with 2FA".

In case of today's webservers, the server replies with a ServerHello as
normal. In case of a "aPAKE" or "aPAKE with 2FA" requirement by the
server, the server responds with a "HelloRetry" message in which he
answers which variant of aPAKE it needs. This first round could also be
used for establishing an ephemeral session ID on both sides by using the
random fields.

Then the "aPAKE" or "aPAKE with 2FA"  authentication protocol is started
and exchanges one ore more message rounds. (For identifying the
sessions, one could use the session ID as established beforehand.) For
this purpose, we need an extension to TLS for tunneling these protocol
messages, which are completely ignored by the TLS layer but transferred
as opaque payload. In case of "aPAKE with 2FA", the data required for
the second factor is also transmitted in addition to the messages needed
by the aPAKE sub-component.

At some spot the external layers will come up with a "PRS" string. In
the case of the "aPAKE with 2FA", this PRS string will also include data
from the second factor. Once this value is there, one could resume the
TLS operation by sending a "ClientHello" with the appropriate SID and
PRS information.

- We keep the TLS state machine as simple as it is today.
- We handle the case of balanced and augmented PAKE with the same
feature set
- We allow for extensability and flexibility (e.g. 2FA) without blowing
up the TLS complexity
- We keep the notoriously complex user-interface components out of TLS

Note that once we have this "tunnel mechanism" that could exchange data
between both sides for implementing use-cases such as password-changes,
etc. .

> implement and deploy, will probably have unacceptable performance,

I don't quite see where you identify a performance problem. Do you
consider the same application context as I did on slide 22 (as mentioned
above?)

> and leaks the username, which is a far more serious vulnerability than
> lack of quantum annoyingness.

Note that the username is leaked in clear text in *all* nominations to
an adversary impersonating the server! There is nothing I see that we
can do against it. At least for the case of an industrial plant, in my
assessment this is the far more critical case and easier to mount than a
passive adversary which is eavesdropping on the network. In this light,
I personally don't see a very significant advantage of using PAKE over
an un-authenticated but encrypted link.

> 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.
Unfortunately, doing so will make it impossible (IMO) to use memory-hard
password hashing without rainbow tables :-(.

---

From: Jonathan Hoyland <[email-masked]>
Date: Mon, 23 Sep 2019 11:19:15 +0100

Hi Björn,

A second round trip is a fairly large performance hit, especially as this
is before the site even begins to load.
If we want to see adoption we have to make sure we don't harm the metrics
website operators care about (for example time to first byte, or document
load).
You write on slide 22 that the user expects the dialogue immediately on the
Hello Retry, but very few users will be familiar with that flow.
They expect to see a fully rendered page with two boxes in which they are
to type their username and password, not an undecorated pop-up.
Because the site has not authenticated itself at this point, the browser
cannot add any site specific rendering (or rather, doing so would require
some complex SXG-style magic, with requires the user to verify the cert
chain at least twice and would immediately leak the site the user is
visiting).

Training users in this system will also make them more vulnerable to
malicious sites that render a blank page and throw a pop-up asking for a
username and password.

The flow for OPAQUE with EAs is much closer to what we see currently.
OPAQUE + EAs performs user authentication _after_ the TLS handshake is
complete, and uses the exporter key interface to bind the authentication to
the underlying channel.

>From a user's perspective,  they go to a website that renders normally, and
then they then login using a username and password box.
If you wanted to, you could switch to OPAQUE + EAs without making the user
aware of the change.
This setup also gives you a major advantage in username leakage, because
impersonating the server requires the attacker to compromise the site's
certificate, which is a reasonably high bar.
Because the site is authenticated to the user before the user sends their
username impersonating a site is much harder.
Further, because of the binding of EAs to the underlying connection you can
also prevent an attacker from MITMing the login.

OPAQUE + EAs:
The system is easy to make memory-hard with protection from rainbow tables.
There are no obvious obstacles for using EAs to perform 2FA based
authentication.
There is also plenty of scope for arranging password changes by binding EAs
to each other, as well as the underlying TLS connection.
There is no change to the TLS state machine.
There is no blow-up in TLS complexity.
The UI elements are kept even further from TLS than under AuCPace.

Regards,

Jonathan

---

From: Björn Haase <[email-masked]>
Date: Mon, 23 Sep 2019 11:46:41 +0000

Hi Jonathan,

we seem to have very different use-cases.

>You write on slide 22 that the user expects the dialogue immediately on the Hello Retry,
>but very few users will be familiar with that flow.
>They expect to see a fully rendered page with two boxes in which they are to type their
>username and password, not an undecorated pop-up.

Indeed what I am suggesting is to have this login page displayed as part of browser controls or even better by OS or a password manager’s controls and not by the remote server’s html.

I could imagine that one possibly could add some small SVG icon on the login screen (that’s what we do for our E+H Bluetooth app) but indeed the login window might be rather un-decorated, as it is part of the browser GUI/skin. Making it part of a window external to the https:// main application region could also be considered a security feature. The end-user could more easily distinguish a control from the browser/OS from what is shown in the browser application.

A user might even choose his own skin (unknown to the adversary) of the window, making phishing attacks more difficult. The attacker would have to find out, how the specific user’s login window looks like.

In our setting this would be perfectly suitable from a usability point of view.

Also one of our main problems is that we could not expect the server to have any valid Web-Certificate installed! Thus, for some IoT device for which a web certificate was not bought and maintained, we would just not have the option to establish any https:// connection through the normal WEB-PKI certificate process! A well-configured browser would just not allow for a connection!

>Training users in this system will also make them more vulnerable to malicious sites that render a >blank page and throw a pop-up asking for a username and password.

I don’t see that there would be any need for “user training” for the “login window in browser” feature. Moreover a site screen should (IMO) not be considered to provide *any* security feature. Any “reasonable” attacker would make his fishing web page look just like the honest server!

>From a user's perspective,  they go to a website that renders normally, and then they then login using >a username and password box.

As mentioned before this approach mandatorily requires a valid Web-PKI certificate in the first place. Secondly this approach would allow an attacker to just use a normal http:// GUI control for standard un-protected text for fishing the password. How would the user be able to distinguish a web page that sends the clear-text password directly to the server from a page that uses a secure aPAKE?

In my opinion a solution using a specific browser or OS-based GUI window for the login could be made more secure. A small site icon might be fine, but this could possibly even be sent by the server in its HelloRetry when using an appropriate compression format such as SVG.

The main problem that I see with your suggestion is that it works only, if the server has a valid trusted Web-PKI certificate *in addition* to the aPAKE solution.

This might be the case for some “conventional” Web-Applications, but not the case for de-centralized Web servers in IoT devices (e.g. a control valve in an industry installation or some household IoT equipment).

Yours,

Björn.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware
Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 377 | Fax: +49 7156 209 221
[email-masked] |  www.conducta.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.

---

From: Jonathan Hoyland <[email-masked]>
Date: Mon, 23 Sep 2019 14:21:34 +0100

Hi Björn,

I agree that OPAQUE + EAs is a Web-PKI specific mechanism, but that is not
the only method for using OPAQUE with TLS.
Specifically when you are doing website login then you should use a
mechanism adapted for website login, but for non-Web-PKI scenarios you
would use one of the other modes, for example OPAQUE-3DH or OPAQUE-Sign,
etc.

More precisely, in a scenario where you are using the Web-PKI, you need to
carefully make sure that what the Web-PKI is telling you is consistent with
what the PAKE is telling you.
aPAKEs are at their core authentication protocols, and when they are used
with other authentication protocols you need to make sure the combined
guarantees are precise and in line with what people expect.
If you aren't using the Web-PKI then obviously this isn't a concern, but if
you are it has to be addressed.

Defining browser chrome that indicates you are using an aPAKE would be
great, especially if it integrated well with password managers, but that
doesn't preclude using OPAQUE, it would make it even better.

Irrespective of the security of how the page looks, consider the UX for
AuCPace when used with a website as proposed.
Imagine I go to, for example, https://nytimes.com, where I sometimes leave
a comment.
Before I can even see the headlines I have to decide whether or not to log
in.
If I decide not to log in and then change my mind, I have to tear down my
TLS connection, start a new TLS session with a full HRR handshake, and
reveal my username to even passive adversaries.

For OPAQUE + EAs the flow is virtually indistinguishable from what we have
now, perhaps with some nice browser chrome to indicate that an aPAKE is in
use.

If you are using TLS on a non-Web-PKI site, for example some IoT device
configuration portal, then OPAQUE-Sign would have the same UI as AuCPace
but wouldn't require the HRR, fitting into the standard TLS flow.

To my mind, OPAQUE is better than AuCPace for use with TLS when interacting
with the Web-PKI, which will (hopefully) be a major use-case.
That's not to say that AuCPace wouldn't be workable, but obviously I'd
prefer to use the best available option.

What do you think are the most significant advantages of AuCPace over
OPAQUE-Sign for IoT / non-Web-PKI use-cases?

Regards,

Jonathan

On Mon, 23 Sep 2019 at 12:46, Björn Haase <[email-masked]> wrote:

> to type their
> Indeed what I am suggesting is to have this login page displayed as part
> of browser controls or even better by OS or a password manager’s controls
> and not by the remote server’s html.
>
>
>
> I could imagine that one possibly could add some small SVG icon on the
> login screen (that’s what we do for our E+H Bluetooth app) but indeed the
> login window might be rather un-decorated, as it is part of the browser
> GUI/skin. Making it part of a window external to the https:// main
> application region could also be considered a security feature. The
> end-user could more easily distinguish a control from the browser/OS from
> what is shown in the browser application.
>
>
>
> A user might even choose his own skin (unknown to the adversary) of the
> window, making phishing attacks more difficult. The attacker would have to
> find out, how the specific user’s login window looks like.
>
>
>
> Also one of our main problems is that we could not expect the server to
> have any valid Web-Certificate installed! Thus, for some IoT device for
> which a web certificate was not bought and maintained, we would just not
> have the option to establish any https:// connection through the normal
> WEB-PKI certificate process! A well-configured browser would just not allow
> for a connection!
>
>
>
> malicious sites that render a >blank page and throw a pop-up asking for a
> username and password.
>
>
>
> I don’t see that there would be any need for “user training” for the
> “login window in browser” feature. Moreover a site screen should (IMO) not
> be considered to provide **any** security feature. Any “reasonable”
> attacker would make his fishing web page look just like the honest server!
>
>
>
> >From a user's perspective,  they go to a website that renders normally,
> and then they then login using >a username and password box.
>
>
>
> As mentioned before this approach mandatorily requires a valid Web-PKI
> certificate in the first place. Secondly this approach would allow an
> attacker to just use a normal http:// GUI control for standard
> un-protected text for fishing the password. How would the user be able to
> distinguish a web page that sends the clear-text password directly to the
> server from a page that uses a secure aPAKE?
>
>
>
> In my opinion a solution using a specific browser or OS-based GUI window
> for the login could be made more secure. A small site icon might be fine,
> but this could possibly even be sent by the server in its HelloRetry when
> using an appropriate compression format such as SVG.
>
>
>
> The main problem that I see with your suggestion is that it works only, if
> the server has a valid trusted Web-PKI certificate **in addition** to the
> aPAKE solution.
>
>
>
> This might be the case for some “conventional” Web-Applications, but not
> the case for de-centralized Web servers in IoT devices (e.g. a control
> valve in an industry installation or some household IoT equipment).
>
>
>
> Yours,
>
>
>
> Björn.
>
>
> ------------------------------
> ------------------------------
>
> ------------------------------
>
> Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu
> informieren, wenn wir personenbezogene Daten von Ihnen erheben.
>
> Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis
> <https://www.de.endress.com/de/cookies-endress+hauser-website> nach.
> ------------------------------
>
>
>
> Disclaimer:
>
> The information transmitted is intended only for the person or entity to
> which it is addressed and may contain confidential, proprietary, and/or
> privileged
> material. Any review, retransmission, dissemination or other use of, or
> taking of any action in reliance upon, this information by persons or
> entities
> other than the intended recipient is prohibited. If you receive this in
> error, please contact the sender and delete the material from any computer.
> This e-mail does not constitute a contract offer, a contract amendment, or
> an acceptance of a contract offer unless explicitly and conspicuously
> designated or stated as such.
>
>
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 19 Sep 2019 20:56:16 +0000

Yes you can (using KEM and Digital Signature) - but it's not the same, particularly efficiency-wise, as if you had a "real" AKE. And I don't know if the proofs in that case would follow trivially or not.

Regards,
Uri

Sent from my iPhone

> On Sep 19, 2019, at 02:07, Hugo Krawczyk <[email-masked]> wrote:
> 
> Hi Uri,
> 
>> On Wed, Sep 18, 2019 at 6:25 AM Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
> 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
>>