Score:0

# Why is the Montgomery ladder algorithm safe against timing side-channel attacks?

I'm trying to understand the security of the Montgomery ladder algorithm in the context of timing side-channel attacks. I'm looking at the algorithm from wikipedia

While I know that the algorithm ensures a constant number of operations in each branch of the if statement, I'm unsure about its overall safety. The Montgomery ladder iterates over all bits of a secret scalar, which makes me question its vulnerability to timing-based attacks.

I understand that the key insight of the Montgomery ladder is that it performs the same sequence of operations regardless of whether the corresponding bit of the scalar is 0 or 1. This property ensures that the timing behavior of the algorithm does not depend on the value of the secret scalar.

However, constant-time programming advises against using if statements with secret conditions. However, in the case of the Montgomery ladder, we iterate over the bits of the scalar, which is a secret. Doesn't this pose a potential security risk?

Score:0

However, constant-time programming advises against using if statements with secret conditions. However, in the case of the Montgomery ladder, we iterate over the bits of the scalar, which is a secret. Doesn't this pose a potential security risk?

I assume you are asking about the conditional jump that sits at the bottom of the iteration code.

The bits of the scalar is secret; the number of bits in the scalar is not.

That is, we always iterate over the full size of the scalar; if we he can handle scalars up to 256 bits in length, we always iterate 256 times (even if the scalar we are multiplying by happens to be much shorter). That way, the conditional jump at the bottom of the loop is not based on a secret condition; we always take the jump to the top of the loop the first 254 times and not the 255th time. Hence, nothing secret is leaked by that jump.

My question was about the `if di = 0` part. From what I understand, `di` (the i-th bit of the scalar d) is secret, which would make that if statement unsafe (I'm not sure about this part).
@Z123: there, the wikipedia article skips how Montgomery Ladder is done in practice. What we actually do is `CSWAP( di, R0, R1 )` both before and after the point_add/double operations (instead if the conditional if). CSWAP is an operation that works in constant time, and swaps R0, R1 if di is set, and leaves them alone if di is clear
I sit in a Tesla and translated this thread with Ai: