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

[Stefan Santesson <[e-mail]>]

I just have to post a correction.

That experimental test I posted is not correct. There is no reason to 
reveal through the Y value if you succeeded on an odd or even attempt.

The correct version of the algorithm we tested was:

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

  test and increment {

      compressed (y,x) = hkdf(hash(pw), counter)

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

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

   }

   save first valid point

}

/Stefan




On 2024-04-03 23:36, Stefan Santesson wrote:
>
> 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
>>
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://mailman.irtf.org/mailman/listinfo/cfrg