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

[Stefan Santesson <[e-mail]>]

Point taken

Thanks!

On 2024-04-04 18:30, Hubert Kario wrote:
> On Thursday, 4 April 2024 17:25:35 CEST, Stefan Santesson wrote:
>> 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.
>
> My wider point is that a cryptographic algorithm that is very
> hard to implement in side-channel way, or worse still, algorithm
> that inherently leaks information useful to the attacker outside
> the cryptographic library boundary is a very bad cryptographic
> algorithm. That's precisely why RSAES-PKCS#1-v1.5 is a very bad
> algorithm.
>
> But yes, as long as the reason why the ultimately chosen value
> was accepted doesn't leak through timing, then try-and-increment schemes
> aren't inherently vulnerable to side-channel attacks.
> I know at least of one RFC6979 implementation that I'm comfortable
> claiming is side-channel secure.
>
>> 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.
>
> I don't think that being vulnerable only to persistent attackers
> is much of a consolation to the people that got hacked.
>
> So, unless the number of samples necessary isn't specified using
> exponents of two at least three digits long, then it's not
> really any protection.
>
>> /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) ...
>>>
>>
>>
>>
>