1
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Z123
    Jun 10, 2023 at 19:44
  • 1
    $\begingroup$ @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 $\endgroup$
    – poncho
    Jun 10, 2023 at 21:52
0
$\begingroup$

In general, if statements implemented with conditional branches will have execution time depending on the sequence of branches taken. Even if we used a 256 bit vector where it is known that exactly 128 bits are set, and therefore exactly 128 branches taken and 128 not taken, the exact sequence would most likely make a difference.

On the instruction level, basically every processor allows you to evaluate both sides of the branch, which will be constant time since you always evaluate the same two expressions, and then select one of the results in constant time, based on a condition, using some specialised instructions.

So using “if” is usually fine if you can guarantee that the if statement is evaluated using constant time selection of two expressions.

You might run into trouble if a future processor has an instruction “select(condition, expr1, expr2) which doesn’t wait for both expressions to be evaluated but executes when the selected expression is ready.

You might also run into trouble if a “clever” compiler replaced the code with branches. Nowadays there are ARM based Macs that translate Intel to arm instructions. If that translator translates conditional selection into branches, you might also be in trouble. We would hope that Apple doesn’t do that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.