Apr 24, 2019

In this particular case they are using bits leaked from the nonce which changes with each execution, but they use lattice reduction after using these bits to generate hidden number problem inequalities[1-3]. They aren't exactly brute forcing the remaining unknown bits here but they do need to try running the lattice reduction multiple times over different samples of their guesses until it works.

In other settings, yes you can still gather leaked bits and use them to reduce the search space until it is small enough to brute force. I've had my own elliptic curve implementation broken through differential power analysis from a leakage due to a conditional branch just like the one in this paper. It leaked only a single bit and it was leaking a bit of the key or a nonce but the least significant bit of an intermediate value in the same way that the LSB was leaked in this paper. All I did was select one of two results, both of which were computed using the same number of operations every time and discarded the other based on whether a result was odd or even. Simply branching is generally enough to leak. After running many operations using the same key on different data you could reduce the search space down to one which could be brute forced in a few minutes. Both the OP's implementation and mine also tried to use some side channel countermeasures, but leaking this single bit was enough. You simply cannot use any conditional branching or memory addressing based on secret information [4-5]. Even being aware of this, it was not obvious how to avoid this conditional branch while implementing the algorithm (the math can be reformulated to avoid it).

We did find that randomized projective coordinates[6] significantly helped in our case (we had already implemented this but was disabled by default). This probably only makes it more difficult to extract the secret but it should be implemented in constant time.

[1] https://www.nccgroup.trust/globalassets/our-research/us/whit...

[2] https://www.youtube.com/watch?v=QCsvBFFLsqE

[3] https://www.nccgroup.trust/us/our-research/return-of-the-hid...

[4] https://cr.yp.to/highspeed/coolnacl-20120725.pdf

[5] https://www.bearssl.org/constanttime.html

[6] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.5...