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

[Stefan Santesson <[e-mail]>]

Now. Sorry for spamming.

But just in case anyone would be interested in the timing results of 
that test. Here is one example showing the natural fluctuation of CPU 
availability:

The timing results are though surprisingly consistent.


Testing password: sdflkj098234sdf-1
Found a valid point on the curve after 5 attempts
Total valid points = 24
Total invalid points = 40
Hash to point: (Size: 33)
     02 68 2D 15 90 7B 30 9F B1 44
         8E 0F 5B F5 91 F3 D4 FD 13 BF
         B3 9D 0B 13 6B C7 18 A5 47 99
         EB B8 F9
Testing password: sdflkj098234sdf-38
Found a valid point on the curve after 1 attempts
Total valid points = 40
Total invalid points = 24
Hash to point: (Size: 33)
     02 EC 12 54 01 A0 C4 ED B2 DC
         1C 29 29 9C 2E 7F D5 BA 48 37
         DA E5 84 85 BF 32 B1 02 25 F2
         7C 6A E7


Time taken for hashToGroup for sdflkj098234sdf-1: 61 ms - using 100 
itearations
Min time per operation: 585000 ns
Max time per operation: 647333 ns
Mean time per operation: 619125 ns

Time taken for hashToGroup for sdflkj098234sdf-38: 60 ms - using 100 
itearations
Min time per operation: 585583 ns
Max time per operation: 633375 ns
Mean time per operation: 603382 ns

Time taken for hashToGroup for sdflkj098234sdf-1: 598 ms - using 1000 
itearations
Min time per operation: 581833 ns
Max time per operation: 677792 ns
Mean time per operation: 598920 ns

Time taken for hashToGroup for sdflkj098234sdf-38: 600 ms - using 1000 
itearations
Min time per operation: 585458 ns
Max time per operation: 675833 ns
Mean time per operation: 600256 ns


/Stefan



On 2024-04-04 00:01, 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
>>>> _______________________________________________
>>>> CFRG mailing list
>>>> [e-mail]
>>>> https://mailman.irtf.org/mailman/listinfo/cfrg
>>>
>>
>> _______________________________________________
>> CFRG mailing list
>> [e-mail]
>> https://mailman.irtf.org/mailman/listinfo/cfrg
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://mailman.irtf.org/mailman/listinfo/cfrg