Re: [CFRG] Does OPRF/OPAQUE require full implementation of RFC 9380

[Mike Hamburg <[e-mail]>]

Hello Stefan,

Yes, I believe that if you used the Java code implementing

NOPRF(x) := g^(hash(x) * k)

then this would directly lead to a complete failure in the security goals of both OPRF and OPAQUE.  (I’m calling it NOPRF because the problem is it’s not a PRF.)  This is because one of OPRF’s security goals is that it cannot be evaluated offline without the server’s key, and this goal is violated for NOPRF once a single interaction has taken place (leading to the recovery of g^k).  That goal is in turn required for OPAQUE; if the PRF were weak and could be evaluated offline, then a malicious client could brute-force the password offline after one interaction with the server.

This is because, when using OPRF, the client’s first message commits to a guess of the password, and then the server’s first message gives enough information to check that guess.  With NOPRF, the client's first message does not commit to a guess of the password, so the client can then use the server’s first message to check any guess (i.e. to brute-force the password offline).  That said, while I have worked on similar PAKEs in the past, I have not studied the issue in detail for OPAQUE, so I might be missing something.


Regarding “constant-time” behavior of try-and-increment, it is generally considered poor practice to try to plaster over non-constant-time behavior by setting min/max timers, because this usually doesn’t hide the timing as well as you want (the timers aren’t as precise as you want; the number of iterations still affects system load which affects timing of other tasks; etc).  Best practices in this area require a more disciplined approach where secrets do not affect branches, memory addresses, arguments to certain instructions (such as division), etc.  This difficulty was a significant part of the motivation for developing the existing hashToCurve methods: those methods were developed in order to be simpler to implement in constant time than try-and-increment.

Unlike using NOPRF, having a non-constant-time hash won’t immediately and catastrophically break the system: it will be a meaningful vulnerability, but one which requires effort to exploit, instead of simply trying one login and then brute-forcing the password.  Leaking even a small amount of information about a password (through timing) is a problem, because the whole point of PAKE is that passwords don’t have much entropy.

Regards,
— Mike

> On Apr 2, 2024, at 2:36 AM, Stefan Santesson <[e-mail]> wrote:
> 
> Thanks Jack,
> 
> Your answer is very helpful.
> 
> To clarify, my questions here are hypothetical questions to help understand exactly where the boundaries are. My sample code is the worst possible way to do it and nothing we plan to use. But I'm still curious about whether it would work.
> 
> I fully understand the problem of deriving a point from an input scalar and I can see many situations where that would be catastrophic. But AFAIK that catastrophic failure is as far as I understand related to one of two events:
> 
> 1) You actually do an operation with the input scalar as a private key
> 
> 2) The derivation process can be reproduced by an adversary
> 
> It seems to me that in OPRF neither of these are the case when a password is hashed to a point and then blinded. Because of the blinding, the point is never known and the input scalar is never used.
> 
> That's why I'm curious if there is any explicit known threat here, rather than this is considered good practice (which I fully agree with).
> 
> 
> 
> Regarding the "try-and-increment", I have also experimented with constant time variants of this working simply like:
> 
>   - Make attempts and increment until you reached minimum constant time, then take first successful result
> 
> A variant  of this is:
> 
>  - Find the first working point by "try-and-increment" and return result after constant time has passed:
> 
> The former seems better as it would require a more uniform workload, but the precision of the constant time is better with the latter.
> 
> 
> 
> Again. Thanks for the replies. I personally plan to implement the standard RFC9380, but these questions are helpful to internal debates on whether you could do this simpler with a good security result.
> 
> /Stefan
> 
> 
> 
> 
> 
> 
> 
> On 2024-03-30 21:01, Jack Grigg wrote:
>> Hi all,
>> 
>> On Sat, Mar 30, 2024 at 6:56 AM Stefan Santesson <[e-mail] <mailto:[e-mail]>> wrote:
>>> Section 2.1 in OPR (RFC 9497) states:
>>> "HashToGroup(x):  Deterministically maps an array of bytes x to an element of Group.  The map must ensure that, for any adversary receiving R = HashToGroup(x), it is computationally difficult to reverse the mapping."
>>> 
>>> [..]
>>> It continues to say that "Security properties of this function are described in [RFC9380]".
>>> 
>>> [..]
>>> I would really appreciate help. Has this been discussed already to any detail. Is there any guidance available?
>>> 
>> As Mike Hamburg alludes to in another message in this thread, the security property of HashToGroup relied upon here is that the output of the function must be a uniformly random element of the group, with no easily-determined relation to any canonical generator of the group (more precisely, HashToGroup should be indifferentiable from a random oracle; see Sections 2.2.3 and 10.1 of RFC 9380). The proposed approach in your email makes inputScalar a known quantity, which directly breaks this property (inputScalar is the easily-determined relation to the canonical generator, because outputElement = [inputScalar] G).
>> 
>> Regardless of RFC 9497 using "must" instead of "MUST" when describing it, its reliance on this security property is clear; see Sections 2.1, 4.6, and 7.2.1 of RFC 9497 for further details.
>>> If this is not good enough. Can you take any simpler path than full RFC 9380 implementation?
>>> 
>> If you use ristretto255 or decaf448, then most of the work should already be done by the libraries implementing the group (see below). See Section 4.1 of RFC 9497 for an OPRF ciphersuite instantiated over ristretto255 and SHA-512.
>> 
>> For other groups (such as elliptic curves), there are other approaches like "try-and-increment", but these are not constant-time and may have other side-channel vulnerabilities in your setting; you would need to consult a cryptographer.
>> 
>> On Sat, Mar 30, 2024 at 7:37 AM stef <[e-mail] <mailto:[e-mail]>> wrote:
>>> tbh i also think this is overkill since for some groups, like ristretto255 for
>>> example there is a widely used hashtogroup available in most big
>>> implementations (like crypto_scalarmult_ed25519 and
>>> crypto_core_ristretto255_from_hash in libsodium).
>>  
>> Just to clarify here for wider benefit: RFC 9496 (which specifies ristretto255, as well as decaf448) includes an Element Derivation function (in Section 4.3.4), which when paired with a hash function can be used to build a hash-to-group operation (which I believe is what library functions like crypto_core_ristretto255_from_hash in libsodium provide). Appendix B of RFC 9380 documents precisely how this should be done to be compatible with it (specifically using an expand_message function that conforms to Section 5.3 of RFC 9380).
>> 
>> Cheers,
>> Jack
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://mailman.irtf.org/mailman/listinfo/cfrg