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

[Stefan Santesson <[e-mail]>]

Hubert,

Fully understood! and I fully agree.

I just want to make clear that this is just a hypothetical discussion 
and not any form of proposal of any kind.

I'm exploring what you could do if side channel attacks of this kind is 
not an issue.

Theoretically. Is there any other reasons why try-and-increment is bad. 
It seems not.

Being "almost perfect" does have some advantage in that it requires more 
samples to draw any conclusions as the information leakage is less, but 
it still leaks.

/Stefan




On 2024-04-04 14:38, Hubert Kario wrote:
> Please note that as Marvin[1] showed, doing "almost" exactly the same 
> amount
> of work doesn't work for side-channel protection. The code needs
> to execute the same instructions, with the same memory accesses, in the
> same order, irrespective of any checks performed.
>
> Differences as small as individual clock cycles are realistically 
> detectable
> even over network, with multiple routers between the victim and the 
> attacker.
>
> 1 - https://people.redhat.com/~hkario/marvin/
>
> On Thursday, 4 April 2024 00:01:54 CEST, Stefan Santesson wrote:
>> 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
>