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

[Hubert Kario <[e-mail]>]

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

-- 
Regards,
Hubert Kario
Principal Quality Engineer, RHEL Crypto team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 115, 612 00, Brno, Czech Republic