Score:0

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

kz flag

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
my flag

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.

Z123 avatar
kz flag
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).
poncho avatar
my flag
@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:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.