Lift user enumeration text to the OPAQUE AKE stage

[chris-wood]

We might consider standardizing the mechanism by which servers prevent user enumeration attacks.

[crockeea]

I support standardizing a method to prevent user enumeration attacks as part of the OPAQUE specification.

[chris-wood]

After reviewing the text again, I think the response encryption approach is likely the only viable way forward here, if we are to do anything. This requires restructuring the RegistrationResponse and CredentialResponse structures and how clients process them. Let's focus on CredentialResponse to start, which currently looks like so:

struct {
    SerializedElement data;
    opaque server_public_key<1..2^16-1>;
    Envelope envelope;
} CredentialResponse;

If we were to encrypt this using an OPRF-derived key, this might look like the following:

struct {
    SerializedElement data;
    opaque ciphertext<1..2^16-1>; // encryption of server_public_key and envelope
} CredentialResponse;

Clients might process this by doing the following:

1. Derive some key from the OPRF given the client's input (client_identity) and the server-derived OPRF key (oprf_key = f(MK, client_identity)). (This would require the client send two blinded elements -- one for deriving the CredentialResponse decryption key, based only on username, and one for deriving the envelope encryption key, based on the password.)
2. Decrypt CredentialResponse.ciphertext, revealing server_public_key and envelope.
3. Process both of these as normal.

(Maybe there's a way to do this with only a single OPRF evaluation, but I've written the naive interpretation above for discussion.)

Overall, this seems like it wouldn't be too terrible to implement. It also has the benefit of encrypting more information on the wire. But I'd really like to see if we can simplify it, perhaps by minimizing OPRF evaluations done, before writing up and implementing the change.

@hugokraw, do you have any ideas?

cc @kevinlewi for visibility, too.

[hugokraw]

The idea is to compute prk exactly as it is done now with a single OPRF computation and derive from it an additional key for decrypting the envelope. Once the envelope is decrypted, the processing is the same (same keys derived from prk as currently done). Do you a reason this would not work or that you need a separate run of the OPRF? Btw, this covers a kind of second-order user enumeration threat. I was not sure it would be needed but if we specify it, it should be optional, not the main mechanism, I think.

[chris-wood]

Your comment seems to apply to the first type of enumeration attack listed in the appendix, which does not require client changes. I don't see much value in preventing this alone when the other type of enumeration exists, which is why I focused on the variant that requires client changes.

[hugokraw]

My comments refer to the second type. The first one only requires allowing that all contents of the envelope be encrypted but no change on client processing. The second type is the one that needs an additional layer of encryption with an additional key derivation from prk. Makes sense?

[chris-wood]

I'm confused then. There are two OPRF evaluations described in the appendix: F(derived_key, client_identity) and F(kU, client_password). Is that not right?

[hugokraw]

You are confused and for a good reason. I used a terrible notation in that passage of the draft. I had kU and kU' notation for two very different things. The first was indeed an OPRF key but the second was used as rwdU (or what's called prk now). So naturally, you thought of kU' as an OPRF key. In the current text this was translated into oprf_key and oprf_key'. However, if you change oprf_key' into something like prk' then you see how things make sense and that one OPRF key (and a single evaluation) suffices. I'll be glad to clarify further if this is still confusing. Sorry for that.

[chris-wood]

Hmm, I understood that distinction. Here's what not clear to me: To simulate randomized CredentialResponses, the text proposes encrypting these under a key derived from OPRF(derived_key, client_indentity). However, there must also be some key derived from OPRF(kU, password) (as is essential to OPAQUE). (One can't just encrypt the envelope under a key derived from the first OPRF evaluation, as that completely skips the password.)

Are these not two separate OPRF evaluations? If not, what am I missing?

[hugokraw]

To address the attack in the first paragraph of Client Enumeration section (btw, should this be referred as user enumeration?), the server does the following. It holds a regular PRF key K (let's call the PRF by HMAC just to remove any confusion with OPRF). Upon receiving a pair (userid, blind) where userid does not exist in the server's database, S computes: oprf_key=HMAC(K; userid | "fake oprf key") prk = HMAC(K; userid | "fake prk"). Then, it builds an envelope using prk as the key and a string of all zeros as contents.encrypted_creds. In this case, however, we assume that ALL the envelope contents (including pkS) are encrypted. It sends this envelope to the client together with the OPRF response computed as blind^oprf_key.

To address the attack in the second paragraph, the server will need to derive oprf_key=HMAC(K; userid | "oprf key") even for its real users. In addition, the protocol is changed as follows. At registration, everything works the same except that an additional key outer_encrypt_key is derived from prk, and this key is stored at the server. During online session, the server will take the envelope (which will be computed at registration exactly as currently done and stored at the server) and will produce a fresh encryption of envelope (fresh = with fresh random IV) and send the encrypted envelope to the client. Everything else stays the same. At the client, prk and all its derivatives are computed as done currently, but in addition, the key outer_encrypt_key is derived from prk. The client uses it to decrypt the encrypted envelope and then proceeds as usual with the recovered envelope.

With these modifications, the case where the the server receives a pair (userid,blind) for unknown userid, is handled as follows. The server sets oprf_key=HMAC(K; userid | "oprf key") (with the received, unknown userid), sets outer_encrypt_key = HMAC(K; userid | "fake encrypt"), and generates a fresh encryption using outer_encrypt_key of a string of all zeros (same length as a regular envelope).

[chris-wood]

Okay, this is more clear now. This seems somewhat different from what's written currently. There is a technical blocker in that we don't have a deterministic API to generate OPRF keys from the output of a PRF. (The OPRF document currently only specifies a randomized KeyGen API, not a deterministic one.) Assuming we could work through that, we'd then need to define the randomized encryption algorithm for the response. Would the server just choose a random nonce and do XOR-based encryption per usual? Something else?

This seems doable, but it will require some invasive changes.

[hugokraw]

You are right, you need to derive oprf_key deterministically from a PRF. This is easily adaptable from what you have in the OPRF document: Just output a random string of the size you need for the randomized KeyGen. And yes, the randomized encryption can be done with a random nonce and and xor. No need for authentication.

[chris-wood]

I filed this issue to track the deterministic key generation API for the OPRF. Absent such a function, I don't think we can move forward with this change. It's also not clear to me how much additional complexity this introduces without having implemented it, so I'd prefer we table this until after IETF 110.

[kevinlewi]

Regarding the addressing of the attack of the first paragraph:

I think this is a good suggestion for implementers who want this extra security property, and since it does not involve any changes to the OPAQUE protocol itself, I think it does not need to be explicitly standardized in this document.

Regarding the addressing of the attack of the second paragraph:

This is also a nice way to add extra security, but the main downside to me is the fact that the server has to store an extra outer_encrypt_key per user, which adds 32 bytes to the password file. It's hard to speak objectively here, but it feels like the attack is a bit too esoteric to merit adding 32 bytes to the server-side storage, especially since it feels like most applications would not need this extra security property. Therefore, I am leaning towards leaving it also as not standardized in this document, but perhaps a future document could look into standardizing it if it becomes important...

Which then leaves the remaining question: what do we want to do with this text? Leave it as-is? Perhaps add a few modifications to ensure that the terminology used here is in line with the rest of the changes made to the main document?

cc: @chris-wood @hugokraw

[chris-wood]

For what it's worth, I agree with @kevinlewi. I think we need stronger motivation to make username enumeration against an active attacker a property of the core protocol. Perhaps @crockeea has something in mind, here?

Which then leaves the remaining question: what do we want to do with this text? Leave it as-is? Perhaps add a few modifications to ensure that the terminology used here is in line with the rest of the changes made to the main document?

If we go down this route, I think acknowledging this property is necessary. I hesitate to add anything more detailed, as it might be implemented incorrectly and harm interop. There's probably some high-level sketch we can leave for future specifications that might want to more directly address this issue.

[PaulGrandperrin]

I'm building a project making use of https://github.com/novifinancial/opaque-ke.

While I was writing the code to do logins, I was very surprised that I wouldn't be able to easily do the classic

your username OR password is incorrect

like many major websites do to prevent username enumeration. e.g:

• Apple iCloud
• ProtonMail
• Cloudflare
• Github
• Parler
• Twitter
• Reddit
• Steam
• Mega.nz
• Tinder
• OkCupid
• Paypal
• Venmo
• Coinbase
• Binance
• P*rnhub
• Onlyfans
• Hired
• Indeed
• Glassdoor
• ...

While it does indeed not matter for most websites (which is sadly also true for all the other nice properties of OPAQUE..), it will for sure be a showstopper for whole categories of websites: privacy-focus companies, security-oriented companies, free-speech platforms, online-dating, finance and crypto, adult sites and others.

Also, even if many website owners will not individually care about username enumeration, as a whole, if OPAQUE ever become widely deployed in its current implementation, being able to trivially know all websites to which a username/email has registered an account, will greatly help many actors looking to abuse users: hackers, scammers, and in some way, advertisers...

Finally, I fear that if OPAQUE cannot be thought of as a ready-to-use solution good enough for all use cases (including the ones I enumerated above), it might hurt its general attractiveness. When building a new product/website, we never know what new constraints or features we might want or need in the future, so choosing dependencies that are all-around solutions is a major advantage for future-proof peace of mind.

In my experience working at some web companies, 32 bytes of data per user is nothing compared to all the other things usually kept, logged or traced per user. If a company had all 7.5 billion humans registered (almost Facebook), it would add ~250GB of data to their user table, which is very little at that scale.

[kevinlewi]

@PaulGrandperrin, thanks for highlighting those great points in your comment!!

To clarify, there are two types of attacks that are currently being discussed in this issue:

Attack 1: Adversary can tell whether or not a user has been registered based on the OPAQUE response.

(This attack prevents the server from convincingly being able to state "your username OR password is incorrect", as in your comment.)

This attack has a mitigation, and it does not involve changing the OPAQUE protocol in any way. However, you are correct in pointing out that https://github.com/novifinancial/opaque-ke does not have explicit support for this mitigation. It could be added as an extra function to the API, but is currently not there. Feel free to file an issue to that repo for tracking if this is something you think should be added!

Attack 2: Adversary can tell, through repeated queries for a given user, whether or not that user has changed their password / registered, since the last time the adversary made a query.

The mitigation we are discussing for this attack DOES require a change to the OPAQUE protocol, and will add 32 bytes to per-user storage, as mentioned previously (along with a little bit of overall protocol complexity). Given your statement,

32 bytes of data per user is nothing compared to all the other things usually kept, logged or traced per user.

it seems like you would be advocating for changing the OPAQUE protocol to protect against this kind of attack, right? This is the main thing that we are discussing now, and we were not sure if this attack was realistic enough (or a significant worry to practitioners) to merit the extra cost.

[PaulGrandperrin]

@kevinlewi thanks for reminding me of this important subtility I forgot it since I first read about this issue a week ago!

Here are some thoughts (biased from the point of view of working within or with SRE teams most of my professional experience):

• as mentioned above, there is already quite a lot of websites used to not having to worry at all about username/email enumeration. Even though the "attack 2" might objectively be a minor regression for many use-cases, it will still feel like a regression necessitating a security and privacy review about the subtle new implications. Lobbying a new technology that is only strictly superior to the old one is always much easier than having to debate the gains vs losses of the upgrade, even if the losses are small.

• As I mentioned before, business needs evolve unpredictably over time, there's a certain peace of mind knowing that a piece of technology soundly and fully solves an issue. Needing to keep in mind small security/privacy gotchas in case they might become relevant for future use cases is annoying. I guess this is by the same logic that it is now always recommended to use AEADs and never directly symmetric ciphers, even when the authentification property does not feel necessary at first. (some people would even advocate for NRMR key-committing AEAD in all use cases ;-) )

• For some categories of websites "attack 2" would still be a showstopper. In the case of adult sites, for example, one would just need to grab a dump of known emails (on the dark web), try them slowly at random over and over again, and could then blackmail the ones where a password change has been detected (which might also mean an account registration).

• As an SRE, the proposed mitigation for "attack 2" makes me uncomfortable because it does not fail in an obvious and visible way. Teams wanting to be sure that the "password rotation" mitigation is working at all times would need to deploy some kind of non-trivial (because of the randomness of the timing of the rotations) monitoring and alerting on the production systems. Also, choosing the parameters of frequency and distribution of the non-existing user's password changes feels like a very difficult question. I'm pretty confident most SREs would be happy the trade those 32 bytes per-user for not having to worry and deal with those things in production.

• Finally, and this is a question: if the robust solution was not adopted now but was added to a later version, would it be possible for existing users of the first version of OPAQUE to upgrade their databases to the new version? (in an offline way, ie, without waiting for each user to log in one by one)

[chris-wood]

For some categories of websites "attack 2" would still be a showstopper. In the case of adult sites, for example, one would just need to grab a dump of known emails (on the dark web), try them slowly at random over and over again, and could then blackmail the ones where a password change has been detected (which might also mean an account registration).

This is a great point. I suppose this is a realistic attack vector that we ought to consider.

[hugokraw]

@PaulGrandperrin Thank you for your comments. I had some of these hypothetical scenarios in my mind when considering the enumeration attacks but you make it feel real and tangible.

I am not clear about the following comment:

• As an SRE, the proposed mitigation for "attack 2" makes me uncomfortable because it does not fail in an obvious and visible way. Teams wanting to be sure that the "password rotation" mitigation is working at all times would need to deploy some kind of non-trivial (because of the randomness of the timing of the rotations) monitoring and alerting on the production systems. Also, choosing the parameters of frequency and distribution of the non-existing user's password changes feels like a very difficult question. I'm pretty confident most SREs would be happy the trade those 32 bytes per-user for not having to worry and deal with those things in production.

I do not see how the mechanism that is needed to address Attack 2 interacts with password rotation policy or its mechanics.

[kevinlewi]

I am looking into the design that @hugokraw proposed for mitigating Attack #2, and here is what I have come up with so far (note that this is not exactly what was originally suggested, since I made some modifications to hopefully simplify things without affecting security).

Registration Phase

First, we have to modify the registration procedure to derive an outer_encrypt_key from prk:

The client, on input prk, computes something like:

1. outer_encrypt_key = HKDF-Expand(prk, "outer encrypt key", 32)

and then the RegistrationUpload struct is modified from:

struct {
    opaque client_public_key[Npk];
    Envelope envelope;
} RegistrationUpload;

to

struct {
    opaque client_public_key[Npk];
    opaque outer_encrypt_key[32];
    Envelope envelope;
} RegistrationUpload;

Question for @hugokraw: Is it secure for outer_encrypt_key to be sent in plaintext here, along with the envelope? Doesn't this mean that an attacker that has saved the RegistrationUpload message can try to decrypt the "outer encryption" we will provide in CredentialResponse, thereby making the mitigation less effective?

Login Phase

Moving onto the login phase: there are two possibilities for the server to handle: either the user is registered, or the user is not registered:

If the user is registered:

Currently, we have this:

struct {
    SerializedElement data;
    opaque server_public_key[Npk];
    Envelope envelope;
} CredentialResponse;

and the proposal is to modify to something like this:

struct {
    SerializedElement data;
    opaque encryptionNonce[32];
    opaque encryptedResponse[Nr];
} CredentialResponse;

where Nr = Npk + sizeof(Envelope) = Npk + (1 + 32 + Nsk + Nh)

The server, with inputs (data, server_public_key, envelope, outer_encrypt_key), constructs CredentialResponse by doing:

1. Pick a random 32-byte encryptionNonce.
2. Computes encryptionPad = HKDF(outer_encrypt_key, encryptionNonce, Nr) (so that encryptionPad is Nr bytes long)
3. Sets plaintext = server_public_key || envelope
4. Computes encryptedResponse = plaintext xor encryptionPad

And constructs CredentialResponse using (data, encryptionNonce, encryptedResponse).

Question for @hugokraw: Is it OK to do a one-time-pad encryption here with a fresh nonce, rather than rely on an AEAD?

If the user is not registered

Then the server does the following:

1. Pick a random 32-byte encryptionNonce
2. Pick a random Nr-byte encryptionResponse

And constructs CredentialResponse using (data, encryptionNonce, encryptedResponse).

---

Does this sound right? Open to feedback!

[hugokraw]

The outer_encrypt_key needs to be transported under a confidential channel during registration. We are assuming registration is done over an authenticated channel (otherwise how do yo know you are talking to the correct server?) so it is probably also confidential (e.g. TLS).

[If that is not the case, the client could, IN THEORY (I do not suggest actually specifying that), first register without sending outer_encrypt_key, then running an OPAQUE session without that key, establishing an OPAQUE session key and then sending outer_encrypt_key under the protection of that key]

As for encryption of the envelope, as a defense against attack 2, no need for authentication. A simple xor with a pad derived using HKDF would suffice.

@kevinlewi I made some modifications to hopefully simplify things without affecting security

Can you indicate what these modification s were other than adding the specification details? I am asking to make sure I am not missing something.

[kevinlewi]

@hugokraw: Thanks, sounds good! I can go ahead and make a PR with these adjustments.

Regarding the modifications, they are already embedded in the description of the specification that I gave. The two things that I modified (which differed from your original explanation) were:

1. You said, "To address the attack in the second paragraph, the server will need to derive oprf_key=HMAC(K; userid | "oprf key") even for its real users." I did not find this necessary, and did not incorporate it into the specification above.
2. The use of xor-based encryption rather than AEAD for the encryption of the envelope using the outer_encrypt_key -- which you just confirmed would be enough.

[hugokraw]

1. You said, "To address the attack in the second paragraph, the server will need to derive oprf_key=HMAC(K; userid | "oprf key") even for its real users." I did not find this necessary, and did not incorporate it into the specification above.

This is needed for the following reason. The attacker sends hugokraw@service.com, a non-existing userid with service.com, with alpha as its first OPRF message and gets a response beta. Later he does the same and still gets the same response beta. At some point hugokraw joins service.com,. If the OPRF key changes, namely the response beta to alpha changes, the attacker knows that hugokraw now has an account with service.com.
This is not a specification of the protocol in the sense of messages and interoperability but is should be part of the server's actions specification. Also needed is a warning that the server implementation should be careful to avoid side channel leakage (e.g., timing) that differentiates the existent and non-existent user cases. In short, these enumeration issues are a pain, though servers that are not concerned with enumeration can skip these server-side careful operations. They still need to do the re-encryption of the envelope as this becomes part of the basic spec (right?).

[kevinlewi]

I see, this makes sense, thanks! Unfortunately this increases the complexity of the implementation slightly, since now the server must store some persistent K used to derive oprf_keys for each user. But it should be workable.

[kevinlewi]

@hugokraw : One more point which I want to highlight. We will have to revert the change in Issue #120 (PR #126) since that made the prk value dependent on envelope_nonce. If we are to do this above change, we cannot have prk rely on envelope_nonce, since prk is required in order to decrypt the envelope in the first place.

This also raises a question: how should outer_encrypt_key be computed from prk? Is it OK to not require a nonce here, by setting outer_encrypt_key = HKDF-Expand(prk, "outer encrypt key", 32), now that prk will be computed as HKDF-Extract("prk", Harden(y, params)) (which no longer involves envelope_nonce)?

Just wanted to raise this issue in case you see anything wrong with it. Otherwise, I will include a revert of #120 in my upcoming change.

[hugokraw]

This is a good point. The main reason for the nonce was to address the following situation. A user registers with a service using a password pw and a private key sk it chooses. At a later point, the user runs the registration procedure again (e.g, because a company requires periodic registrations or some security event triggers it). This time, the user uses the same password pw but a different private key sk'. Since the service derives the user's OPRF key deterministically from the username, the OPRF key does not change. With the password and OPRF key unchanged, the same pseudorandom_pad is computed in both cases but used to encrypt two different plaintexts, namely, private keys sk and sk'. The nonce in the envelope, chosen afresh with each registration, this weakness is eliminated.

There are two possible ways here. One is to say that the double use of a one-time pad in this case would be relatively rare and since the plaintexts under these encryptions will be independent random keys then there is not much to learn for the attacker (except if it knew the first private key). This would not be totally outrageous but not a good example of cryptographic hygiene. The other solution is to include a nonce in the envelope that is used to derive the pseudorandom_pad as currently done, but the nonce is not used for the derivation of outer_encrypt_key. The latter is computed without the nonce.

[kevinlewi]

@hugokraw Thanks. Based on the PR that I posted (#156), I opted to do the second suggestion you mentioned:

The other solution is to include a nonce in the envelope that is used to derive the pseudorandom_pad as currently done, but the nonce is not used for the derivation of outer_encrypt_key

However, your response made me realize yet another aspect we should probably consider. Right now, the proposal is to do:

oprf_key = HKDF-Expand(oprf_seed, concat("oprf key", cred_identifier), 32)

where cred_identifier is an identifier that acts as the client's username (could be the same as client_identity, but doesn't have to be), and oprf_seed is a random 32-byte value that the server must keep across all clients.

However, this suffers from the downside that if the client were to rerun the registration protocol with the same cred_identifier, this would result in the same oprf_key. Previously, when we were choosing oprf_key as a random bytestring, we did not have this issue, but now we do.

I propose that in the RegistrationRequest message, we ask the client to generate a 32-byte oprf_key_nonce, and then we change the oprf_key derivation to:

oprf_key = HKDF-Expand(oprf_seed, concat("oprf key", oprf_key_nonce, cred_identifier), 32)

so as to mitigate the issue. Of course, oprf_key_nonce will have to be a value that is persisted in the server-stored password file for the user, so that upon login, the server can reconstruct the oprf_key without asking the client to send anything.

Let me know if this sounds good. Unfortunately, this means adding another 32 bytes to the password file, but I think it's for a good cause.

[hugokraw]

I was thinking that cred_identifier should be unique across users, e.g. hugokraw@gmail.com is unique. But if the identifier in use cannot be guaranteed to be unique then what you suggest makes sense, except that why does the client choose it and not the server? The latter may be able to choose shorter strings, e..g., it could use a global counter that is augmented by one with each new user (if saving in storage is important)

[kevinlewi]

On some further reflection, I think that proposed mitigation for Attack #2 causes a regression in another important security property that is desirable for OPAQUE: re-running the registration phase for a user should result in a fresh oprf_key chosen for that user.

Note that in the event of a server compromise, since these oprf_key values for each user are stored in plaintext with each user's credential file, we should assume that they are exposed to the adversary as well. Hence, after the server asks users to re-register in such an event (with the same user identifier), it is important for a fresh oprf_key to be selected.

Between the choice of mitigating Attack #2 versus ensuring that a fresh oprf_key is sampled upon re-registration of a user, I think it would be best if we kept the latter. Unless there is a way to retain both properties with OPAQUE?

Note that we can still address Attack #1, since that does not require any changes to the protocol.

Therefore, I'm in favor of NOT making the proposed change (PR #156) to address Attack #2, and would like to hear everyone's thoughts on this.

cc: @hugokraw

[hugokraw]

If you derive oprf_key as PRF(key=master; concat(userid, nonce)) where nonce is stored in the userid record, then upon a detected compromise of oprf_key for userid, you need to re-register that party without changing userid but changing nonce to get a fresh independent oprf_key. This change can be noticed by an attacker submitting userid before and after the change, but it is something that happens only upon compromise so not enough to ruin the defense to attack #2 in normal circumstances.
I do not like the extra complexity introduced by the defense against attack 2 but @PaulGrandperrin made some good arguments about the importance of such defense, particularly as it is hard to start with a system that does not provide these defense and later upgrade it to one that it does.

[kevinlewi]

This change can be noticed by an attacker submitting userid before and after the change, but it is something that happens only upon compromise so not enough to ruin the defense to attack #2 in normal circumstances.

I think this depends on the application, and when they choose to rotate nonce. I agree with your statement if the only time nonce is rotated is after a server compromise. But, I was initially under the impression that whenever a user wishes to change their password, they will re-run the registration phase, thereby having a new nonce sampled (and hence, a new oprf_key). Otherwise, if we don't choose a new oprf_key, then it seems like we would be somewhat weakening the security guarantees that one might expect to have upon registering a new password for the user. This would then make "Attack #2" more relevant in normal circumstances, unfortunately.

Ultimately, I would like to avoid those complications by just ensuring that the re-registration procedure is as clean as possible.

[hugokraw]

The renewal of the OPRF key is not critical. It is only needed upon compromise. Of course, if it doesn't cost anything to change oprf_key with a re-registration, then better since it addresses the case where you did not know the oprf_key leaked. On the other hand, if the oprf_key leaks, the user's password is open to offline dictionary attack, so you are in trouble anyway. Note that you can also periodically rotate the master key used to derive oprf keys (moving users gradually to a new key) and that will give no information to the attacker. Overall, I do not see this attack scenario to be worth leaving attack 2 undealt with.

[kevinlewi]

Thanks for the clarification. That makes sense to me, and now I am convinced that we do not need to add the extra oprf_key_nonce parameter that I had proposed in https://github.com/cfrg/draft-irtf-cfrg-opaque/issues/22#issuecomment-791261028.

I'm in favor of continuing with the proposed changes in #156

[kevinlewi]

Re-opening to discuss the following:

@hugokraw : The client's static public key is also a part of the password file that the server stores. In the absence of the password file because the user has not been registered, what should the server use in place of the client's static public key in order to generate the "fake" CredentialResponse message?

This will affect the generation of the KE2 message. Would it suffice to pick a uniformly random 32-byte string? Or do we need another PRF evaluation here?

Hope the question is clear!

[stef]

is this possible to implement without having a timing side-channel?

[stef]

i am also wondering if all these computations are proportional and an attacker has more computation to do than a defender, otherwise it might be quite economic do do a resource exhaustion dos against an opaque server, no?

[chris-wood]

Not Hugo, but:

This will affect the generation of the KE2 message. Would it suffice to pick a uniformly random 32-byte string? Or do we need another PRF evaluation here?

Since this is otherwise sent in cleartext in KE2, I think a PRF evaluation is probably necessary.

(I confused myself with ephemeral keys.)

The public keys only affect the handshake secret, which is already ephemeral by virtue of including the server's ephemeral share, so no PRF seems necessary.

[kevinlewi]

In response to @stef:

is this possible to implement without having a timing side-channel?

Yes, the specification of the faked response was written in a way so as to explicitly mitigate timing side-channels (though it will of course depend on the implementation as to whether or not it is done properly). There is text in the draft which mentions that implementations must take care to prevent timing attacks. Also see this comment here: https://github.com/cfrg/draft-irtf-cfrg-opaque/pull/156#issuecomment-793706164

i am also wondering if all these computations are proportional and an attacker has more computation to do than a defender, otherwise it might be quite economic do do a resource exhaustion dos against an opaque server, no?

These operations are actually not super complicated or resource-intensive, so I don't think that there is an opportunity for an attacker to do this. Especially when considering the full registration / login flow, where the client must evaluate a memory-hard function, it looks more like the client has to do the bulk of the work rather than the server!

[hugokraw]

The simplest and universal (i.e., for al key exchange protocols) solution to this issue is to use masking_key to encrypt the whole message from the server, namely, both the envelope and the KE2 message. The client decrypts the whole stream and operates on it as in the regular protocol. In this case, for non-existing userid's the server just sends a stream of random bits (of the same length as the envelope + KE2). If we want to use masking_key only to encrypt the envelope, then the masking of KE2 depends on the protocol. For 3DH and HMQV specified here (it is similar for SIGMA), what the server sends is the server_nonce, server_keyshare, enc_server_info and mac. These can all be simulated with random bits except for server_keyshare that is a group element and would be distinguishable (except for special encodings) from a random string of the same length. Thus, if we do not want to use masking_key to cover KE2, the server will send random bits in place of the nonce, enc_server_info and mac (each such random string of the length of the field it occupies), but will need to send a random group element as server_keyshare. The latter costs an exponentiation operation.
Simulating these replacements while not leaking via timing is delicate. The server would need to deliberately slow-down the sending of its message to simulate the time it would take to compute the keys Ke2 and Km2 with a real user.

[stef]

In response to @stef:

i am also wondering if all these computations are proportional and an attacker has more computation to do than a defender, otherwise it might be quite economic do do a resource exhaustion dos against an opaque server, no?

These operations are actually not super complicated or resource-intensive, so I don't think that there is an opportunity for an attacker to do this. Especially when considering the full registration / login flow, where the client must evaluate a memory-hard function, it looks more like the client has to do the bulk of the work rather than the server!

i was more wondering of the simple case, a DDoS where attackers just send random garbage that is interpreted as a CredentialRequest message, and since we hide the userids - to prohibit enumeration - the attackers can send anything, and we cannot just sleep for x time to not leak time side chan, we have to actually do computation, and so the attacker very cheaply just sends random strings, and the server has to do much more expensive calculations. where if there would be no user enumeration protection, the cred requests that refer to nonexistent userids can simply be dropped, forcing the dos attackers to actually know valid userids, which if only a few are used can be also dropped without processing - even at a firewall already. i know it's a tradeoff, but maybe noteoworthy mentioning in the draft?

[hugokraw]

If you use the technique by which all of the server's message (envelope + KE2 message) are encrypted under masking_key then the only non-trivial cost for the server is the computation of the OPRF response (one var-base exponentiation). If you do not encrypt KE2 under masking_key then the additional cost is a fixed-base exponentiation to compute server_keyshare which is relatively minor in comparison with the var-base exponentiation. All other values in KE2 are replaced with random strings. *Note that the server does not need to compute IKM or any of the derived keys ** The total cost for the server is less than establishing a TLS session with the attacker and in most cases OPAQUE will be run after establishing such channel (e.g., to protect the privacy of userid), so the gain for a DoS attacker from reacting to a fake userid in OPAQUE is not too significant. Of course, if you compare with current password-over-TLS then the attacker always has the opportunity to do a DoS on TLS establishment and when using a real userid, it also forces the server to do the hardening procedure which I assume is significantly more expensive than an exponentiation.

[kevinlewi]

Thanks for the replies. Closing this issue out since the constant-time implementation is certainly doable.