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

[Hubert Kario <[e-mail]>]

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) ...
>> 
>
>
>

-- 
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