Resistance to side-channel attacks (SCA) is especially elusive. While theoretical weaknesses in the cryptographic algorithms are supposed to be prevented by choosing appropriate algorithms, choosing an algorithm that is known to be SCA-resistant does not guarantee much: the SCA-resistance is a property of implementation, not of the algorithm.
Consider Montgomery ladder. Each step in the algorithm is obviously constant-time and thus you may think that the time it takes to do a scalar multiplication of a point by number k should not leak your secrets. This reasoning seems correct until you realize that the number of steps must be constant too. It turns out that even highly-skilled OpenSSL developers can forget about that:
This paper describes a timing attack vulnerability in OpenSSL’s ladder implementation for curves over binary fields. We use this vulnerability to steal the private key of a TLS server where the server authenticates with ECDSA signatures. Using the timing of the exchanged messages, the messages themselves, and the signatures, we mount a lattice attack that recovers the private key.
Ironically, in the end it is the regular execution of the ladder that causes this side-channel vulnerability: for example, a dependency on the weight of k (that might leak from, say, a simple binary scalar multiplication method) seems much more difficult to exploit than that of the length of k that led to full key recovery here.
On the other hand, if we know that the execution time is constant, we can quite easily test. The lesson is obvious: Do not just assume properties of your implementation to be the properties of the algorithm you implement, do test them!
