Montgomery Powering Ladder and Side Channel Attacks: Is it practically (im-)possible to analyze where intermediate values are stored? The Montgomery Powering Ladder performs an exponentiation with the operations square and multiply (called double and add in the case of elliptic curves). To my knowledge the order and kind of operations involved are independent from the exponent, which prevents side channel attacks if the exponent is a secret key.

But of course the computation does depend on the exponent: Each bit of the exponent decides where intermediate results are stored. More concretely, the exponent is processed bit by bit and in each step, two intermediate values, say R and S, are updated. If the exponent bit is zero then one of the values, say R, is overwritten with the product of R and S and S is squared. If * denotes the underlying group operation then this can be written as

R &lt;- R*S
S &lt;- S*S


If the exponent bit is one then it is the other way round: 

S &lt;- R*S
R &lt;- R*R


So if one could determine which value is squared then this would reveal the respective exponent bit. I guess that this is not possible in practice since otherwise there would have been exploits. 

Could someone explain to me why this is difficult in practice? I am an absolute beginner in embedded devices, microcontrollers etc. I am particularly interested in the case where the Montgomery powering is done on an embedded device (not a particular one).
Each bit of the exponent decides where intermediate results are stored.


Not necessarily.

One approach is to use a primitive known as a (constant access) conditional swap.  This primitive takes the values R and S, and swaps them if the bit in the exponent is 1, and leaves them alone if they are 0.  Naturally, this is done with constant accesses (even if the bit is 0, you still read and write R and S) and constant time; it's pretty straight-forward to implement (and is considerably quicker than the Bignum operations the rest of the algorithm uses)

With this primitive, the pseudocode looks like:

CSWAP R, S
R &lt;- R*S
S &lt;- S*S
CSWAP R, S


If the exponent bit is 0, we can ignore the CSWAP's, and this is exactly the Montgomery Ladder 'bit 0' logic.

If the exponent bit is 1, then we effectively do this logic:

R' = S, S' = R   /* First CSWAP */
R' &lt;- R'*S'
S' &lt;- S'*S'
R = S', S = R'   /* Second CSWAP */


Renaming variables, this simplifies to:

S &lt;- S*R
R &lt;- R*R


Which is the 'bit 1' Montgomery logic (as * is commutative).

Hence, we've implemented both sides of the ladder with constant memory accesses.

If we write out the full ladder, we'll see that there are adjacent CSWAPs based on different bits of the exponent; it's obvious how those could be combined to further simplify things.