It's really easy to blind a variable time modular inverse, assuming you have a random number generator handy: you want the inverse of x, compute instead the inverse of x*r, then multiply the result with r.
So I wonder if some things using the same chip/library are not actually vulnerable because they blinded the operation?
It's *better* to use a constant time algorithm, but that's harder to do in a curve generic way and has a pretty significant performance impact (particular before the safegcd paper).
> It's better to use a constant time algorithm, but that's harder to do in a curve generic way and has a pretty significant performance impact (particular before the safegcd paper).
Crypto noob here, but isn't modular inverse the same as modular exponentiation through Fermat's little theorem? I.e., x^-1 mod n is the same as computing x^{n - 2} mod n which we know how to do in a constant-time way with a Montgomery ladder.
Or is that too slow?
The powering ladder is unfortunately quite slow compared to the obvious vartime algorithm which is what temps these things to have a vartime algorithim in the first place, though too slow depends on the application. It doesn't help that these chips are underpowered to begin with.
Aside, for the FLT powering ladder n need needs to be prime, but it isn't when there is a cofactor, though there is a generalization that needs phi(n)... I probably shouldn't have made a comment on the issue of being curve specific since the problem is worse for sqrt().
So I wonder if some things using the same chip/library are not actually vulnerable because they blinded the operation?
It's *better* to use a constant time algorithm, but that's harder to do in a curve generic way and has a pretty significant performance impact (particular before the safegcd paper).