Apply nonce bit-length mitigation to stop timing leakage.

[J08nY]

This should fix the timing leakage allowing a Minerva-style attack. See https://minerva.crocs.fi.muni.cz for more info.

[DavidEGrayson]

Hey, thanks for the contribution! Before I spend much time on this, how important is it to you that I merge it in? I bet there are lots of other places where timing attacks or side-channel attacks could be done. I never looked at the assembly code generated for the Ruby large integer operations. If you don't mind me asking, are you using this gem in something important? Are you actually using this code in a hostile environment where someone could be timing it accurately?

[J08nY]

Hi, I am not using this gem in any way. I am a co-author of the above disclosure which discovered similar vulnerabilities in many implementations.

I believe this fix is important because the vulnerability it fixes is very easily exploitable and leads to full key recovery. Of course, even after this is fixed, the implementation would not be constant time and details of variable timing integer arithmetic would leak something, yet that would be much much harder to exploit, and generally lost in noise. This leakage is so large that it could be exploitable even remotely, compared to much smaller leaks somewhere in integer arithmetic.

Even if for example the Hamming Weight of the random nonce were leaked, one would have a hard time exploiting it, as it doesn't map to a HNP-like problem easily (as bit-length leakage does).

Putting a note somewhere that a particular piece of cryptographic code is not constant-time will not keep people from using it in a vulnerable way.