Unhandled zero scalars and identity elements

[daxpedda]

This is a list of functions that contain group operations that might produce zero scalars or identity elements. I don't actually know if this is a problem or not in some of the cases, I'm going to leave that to actual cryptographers to figure out.

• GenerateProof can return a zero scalar because of s = (r - c * k) mod p.

• ComputeComposites and ComputeCompositesFast use HashToScalar, which can return a zero scalar, which is then used in M = di * Cs[i] + M and Z = di * Ds[i] + Z. Adding M, prevents producing an identity point, so it might not be a problem.

• POPRF's Finalize uses HashToScalar, which can return a zero scalar, which is then used in T = ScalarBaseMult(m), which would produce the identity point. Afterwards, in U = T + pkS, adding a non-identity point would prevent U from becoming an identity point, so it might not be a problem.

[daxpedda]

I updated this to the current master, which resolved a lot of issues.

[chris-wood]

@armfazh did some analysis and concluded that the only place where we need to be concerned with distinguished scalars is in the Blind() step. Fortunately, Blind uses RandomScalar to produce a scalar, which returns a non-zero scalar. Thus, the only way for Blind to produce the identity element is for HashToGroup to produce the identity element, and since that is entirely determined by the input to Blind, the only thing the function can do is raise an error.

[hugokraw]

Chris asked me to take a look at this. The 2HashDH OPRF needs to specify the bind factor to be different than 0 since otherwise the de-blinding would not work. Pathological cases such as getting 0 when a random field value is chosen or getting the identity element when hashing into a curve (and possibly other cases like this) need to be handled as a severe error. Indeed, since the probability that this will happen by chance is essentially zero, such an output indicates a serious bug.

Btw, OPAQUE also requires checking DH values to be in the prime group but this is irrelevant for the OPRF spec.

[daxpedda]

Thus, the only way for Blind to produce the identity element is for HashToGroup to produce the identity element, and since that is entirely determined by the input to Blind, the only thing the function can do is raise an error.

This is a problem for OPAQUE, which uses the Blind function with the input being the user password. This means that there is a user password out there that can't be used with OPAQUE.

That said, the chances are extremely low for that to happen and it ideally people should use a password manager ... I would still prefer this to not be fallible if at all possible.

[chris-wood]

Chris asked me to take a look at this. The 2HashDH OPRF needs to specify the bind factor to be different than 0 since otherwise the de-blinding would not work. Pathological cases such as getting 0 when a random field value is chosen or getting the identity element when hashing into a curve (and possibly other cases like this) need to be handled as a severe error. Indeed, since the probability that this will happen by chance is essentially zero, such an output indicates a serious bug.

Thanks @hugokraw! This is already handled by the spec. The scalar returned is guaranteed to be non-zero (unless an implementation does this wrong, of course).

[chris-wood]

This is a problem for OPAQUE, which uses the Blind function with the input being the user password. This means that there is a user password out there that can't be used with OPAQUE.

@hugokraw this is the more important comment, I think. In the context of OPAQUE, if the user's password maps to the identity element of the group, then indeed they cannot use that password with OPAQUE.

[chris-wood]

@daxpedda here's my take on HashToScalar outputting zero in the cases identified:

• ComputeComposites (computing d_i): A zero value does not invalidate the resulting (M, Z) output, so no special handling is needed here.
• Proof generation and verification (computing c): A zero value does not invalidate the proof, since the private key is still perfectly blinded by r.
• POPRF Finalize: Clients will not reach this step if servers appropriately abort when they can't find the multiplicative inverse of skS + t. If servers don't abort and somehow send garbage back to the client, then the proof verification will fail.

All in all, I don't think we need to do any additional special handling here. @armfazh, what do you think?

[daxpedda]

• POPRF Finalize: Clients will not reach this step if servers appropriately abort when they can't find the multiplicative inverse of skS + t. If servers don't abort and somehow send garbage back to the client, then the proof verification will fail.

Thank you for the explanation! This comes back then to the issue that the protocol can simply fail at POPRFs Evaluate and has to be restarted, which is less then ideal I would argue.

With the concerns resolved here, I don't have much of a stake in this anymore, I came here from the OPAQUE protocol. As far as I understand the OPAQUE protocol doesn't intend to use POPRF but plain OPRF.
I would like to avoid failing the protocol and having to start it over for OPAQUE, but I can't argue for POPRF because I don't know the use-cases involved.

Happy to provide feedback of course 😃.

[chris-wood]

Thank you for the explanation! This comes back then to the issue that the protocol can simply fail at POPRFs Evaluate and has to be restarted, which is less then ideal I would argue.

Fair point. We can likely make this fail earlier, in Blind. I'll send a PR to do that.

[hugokraw]

This is a problem for OPAQUE, which uses the Blind function with the input being the user password. This means that there is a user password out there that can't be used with OPAQUE.

@hugokraw this is the more important comment, I think. In the context of OPAQUE, if the user's password maps to the identity element of the group, then indeed they cannot use that password with OPAQUE.

Even with a password dictionary with entropy of 256 bits, the probability of this happening is 2^{-256}. There are worse things happening at that probability level including guessing OPRF keys, discrete logarithms, signature and encryption keys, multiple collisions, etc. If you get such a case there is a billions of times higher probability that this is due to a programming bug or the break of the underlying hash function. This is why I recommend that if a program finds such a case (a password hashed to the identity element), you output a HUGE ERROR message.

By the way, in the case of OPAQUE with 2HashDH, even if the password is mapped to the identity (a fact that is learned by a passive adversary by seeing H(pw)^r), the attacker (including an active one or even the server itself) needs to run a dictionary attack on the password because the password is hashed together with the group identity. With a 256-bit entropy password this will take 2^255 time. So you could keep running OPAQUE with this password.

Can these good discussions be linked from the OPAQUE github? They can be useful for future reference.

[chris-wood]

Even with a password dictionary with entropy of 256 bits, the probability of this happening is 2^{-256}. There are worse things happening at that probability level including guessing OPRF keys, discrete logarithms, signature and encryption keys, multiple collisions, etc. If you get such a case there is a billions of times higher probability that this is due to a programming bug or the break of the underlying hash function. This is why I recommend that if a program finds such a case (a password hashed to the identity element), you output a HUGE ERROR message.

This is true, and I don't think we have any security considerations text describing this case. I'll file an issue against the OPAQUE draft to add it.

Can these good discussions be linked from the OPAQUE github? They can be useful for future reference.

Yep =)

[daxpedda]

Even with a password dictionary with entropy of 256 bits, the probability of this happening is 2^{-256}. There are worse things happening at that probability level including guessing OPRF keys, discrete logarithms, signature and encryption keys, multiple collisions, etc. If you get such a case there is a billions of times higher probability that this is due to a programming bug or the break of the underlying hash function. This is why I recommend that if a program finds such a case (a password hashed to the identity element), you output a HUGE ERROR message.

As an implementer I'm still unsure what to do. Sure I can return an error message, but there is still passwords out there that correctly map to the identity point, so if this ever happens, there is no action I can take.

By the way, in the case of OPAQUE with 2HashDH, even if the password is mapped to the identity (a fact that is learned by a passive adversary by seeing H(pw)^r), the attacker (including an active one or even the server itself) needs to run a dictionary attack on the password because the password is hashed together with the group identity. With a 256-bit entropy password this will take 2^255 time. So you could keep running OPAQUE with this password.

For this to happen OPAQUE has to rely on a special version of Blind that doesn't return an error on an identity element.

---

This could be easily solved in OPAQUE by making sure the input to Blind is not simply the password but add a counter to it like was done in DeriveKeyPair.

I would like to understand though, why a non-fallible solution like using the reduction mod n-1 plus one method is undesired. It was mentioned before that it's undesirable to require HashToScalar or HashToGroup to not be able to return a zero scalar or identity element. If that is the problem, HashToNonZeroScalar and HashToNonIdentityPoint could be introduced for example. But the mod n-1 plus could also simply be added after using HashToScalar for example.

I understand that there is not a high motivation to address this as the chances of it occurring are astronomically low.