Oreko

I haven't read their protocol, but you can easily implement PIR using FHE through polynomial evaluation.

SCRAM seems incredibly insecure. Does anyone have information on how many servers support SCRAM?

Is there a scheme using these principles that isn't known to be insecure? Or one that has a proof of security by reduction to a known (or supposed) hard problem?

A brief look online makes it sound like all provided schemes have extremely adhoc arguments of security or are known to be broken.

Unfortunately, a reasonable source I found is paywalled: https://link.springer.com/chapter/10.1007/978-981-16-6332-1_...

Another confusion on my part, above the protocol Sc00bz writes:

" Client without password has:

      idC = client identity

      P = hashToPoint(p)

      c

      S = s * P

      Reg = reg * G (reg = registration private key)
"

Turns out I misread part of the protocol.

I mixed up "b" stored by the server in the registration phase and the "b" used in the online phase. In that case, the adversary can't compute either b * C or c * B.

This being said, there's a more technical problem with the protocol as-is with how the OPRF is used. Currently, the adversary can malleate the OPRF messages resulting in a valid/invalid session between two honest parties without the simulator being able to distinguish between the two cases. This comes from the perfect blinding property of 2hDH and is discussed in the OPAQUE paper[1].

There may be other problems, but _most_ of the protocol passes a quick smell test.

Sorry for any confusion!

Augmented is a common label for these kind of PAKEs. Generally speaking, asymmetric, verifier-based, and augmented are all three interchangeable.

Sc00bz made this comment[1] on reddit describing what "doubly augmented" means where they succinctly describe it as

"A doubly augmented PAKE is where both sides can store data to authenticate with eachother but not themselves."

This mirrors the definition of aPAKE and makes sense, but this sounds more like the security property provided by CRISP[2]. This doesn't make sense in the context of double BS-SPEKE as the client inputs their password in the clear which can be used to generate the server's storage without any "guessing".

[1] https://old.reddit.com/r/crypto/comments/zy8w3y/what_we_do_i...

[2] CHIP and CRISP: Protecting All Parties Against Compromise through Identity-Binding PAKEs https://eprint.iacr.org/2020/529

Hi, I perform research in the area of PAKEs. I'm not a "foremost expert" but I know a bit. Before I start, I don't believe that it's standard to use the term "doubly augmented PAKEs". Instead, I'll use the more accepted shorthand "saPAKE" for "strong asymmetric PAKE".

I think it's important to note that the provided saPAKE Double BS-SPEKE does not come with a security proof. A proof of a similar protocol is not hard if you believe in the compiler provided in the JKX18 paper[1] and you believe that B-SPEKE is a UC-secure aPAKE but it's important to note that the JKX compiler is not proven secure against the updated functionality from their revisions. Further, I don't believe that B-SPEKE has a security proof in any model let alone the UC model.

But I can say for certain that the currently described protocol is not a secure saPAKE as it doesn't prevent an adversary from impersonating a client after stealing the server's password file.

The adversary learns (B, salt, P, C, s, b, regMAC) and needs to produce (a * P, H(idC, idS, A, B, a * B, c * B, s * A))

a is uniformly sampled, so the adversary knows a * P, A, B, a * B, and s * A. We're missing c * B, but this is just b * C which we know. So the adversary can produce all messages required and arrive at the server's key.

This may not be a security guarantee that you need for your use case, but I cannot recommend Double BS-SPEKE as an saPAKE until we see a formalized analysis of its guarantees.

[1] OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-Computation Attacks https://eprint.iacr.org/2018/163

--- EDIT ---

I just came across the original talk https://www.youtube.com/watch?v=gopo2FI9epw using the term "doubly augmented" and I'll update this post soon.