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

[Stefan Santesson <[e-mail]>]

Mike,

Thank you very much for this great answer.

Yes, we were looking at that type of attacks where the knowledge of the 
input scalar allows you to reconstruct multiple OPRF responses for 
arbitrary input.

However, in that analysis I didn't consider the client as the adversary. 
But when you do, that attack is quite obvious and a good reason not to 
go there!


I totally agree on the constant-time issue. We made some experimenting, 
just for the fun of it, and we ended up in something like this as our 
best attempt:


loop a fixed amount (e.g. 0 -> 64) {

  test and increment {

      x = hkdf(hash(pw), counter)

      y = counter % 2 == 0 ? 0x02 : 0x03 // compressed

      if (point(y,x) == valid)  also test an invalid point

      if (point(y,x) != valid) also test a valid point

   }

   save first valid point

}


This way we always make almost exactly the same amount of work. For each 
iteration in the loop we test one valid point and one invalid point.

But still I could detect statistically detectable difference over many 
consecutive tests of different passwords. But to detect this you needed 
quite some attempts.

I don't think there is a way to make this perfect. But for simplistic 
implementations where this is not an active threat, it does offer a very 
easy implementation alternative.

One we won't use of course ;)


Once you have hash to curve implemented, making it any other way makes 
no sense.


Thanks again. This was very helpful!

/Stefan


On 2024-04-03 17:39, Mike Hamburg wrote:
> 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]> 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]> 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
>