RSA Timing Attack on "Extra" Montgomery Reduction
Montgomery multiplication
Theorem (Montgomery, 1985). For any odd integer $N$ and any integer $0 \le T &lt; N2^k$, one has: $$T 2^{-k} \equiv \frac{T + UN}{2^k} \pmod N$$ where $U = T N' \bmod 2^k$ and $N' =  -N^{-1} \bmod 2^k$.  Further, one has: $$\begin{cases} T+UN \propto 2^k\\ 0\le \frac{T + UN}{2^k} &lt; 2N\end{cases}$$
The last 2 properties show that $R:=T2^{-k} \bmod{N}$ can be computed in two steps as:

$R \gets \frac{T+UN}{2^k}$
If $R \ge N$ then $R \gets R - N\qquad$ (extra subtraction)

Montgomery arithmetic represents an integer $0\le x &lt;N$ as $\tilde{x} = x2^k \bmod N$.  It defines the Montgomery multiplication of two representatives $\tilde{x}$ and $\tilde{y}$ as $$\tilde{x} \otimes \tilde{y} := (\tilde{x}\cdot\tilde{y})2^{-k} \bmod N\tag{*}$$  Observe that letting $z= x\cdot y \bmod N$, one has $\tilde{z} \equiv (x\cdot y)2^k \equiv (\tilde{x}\cdot \tilde{y})2^{-k} \equiv \tilde{x} \otimes \tilde{y}\pmod N$.
Timing attack
Suppose that each Montgomery multiplication, cf. Eq. ($^*$), is done using the above two-step process.  We see that depending on $\tilde{x}$ and $\tilde{y}$, there may be an extra subtraction to get the result $\tilde{z}$ in the range $[0, N)$.
To fix ideas, suppose that the computation of $S = m^d \bmod N$ is carried out with the square-and-multiply algorithm.  The attack can easily be adapted to other exponentiation algorithm. The algorithm takes as input a message $m$ and private exponent $d = (d_{\ell-1}, \dots, d_0)_2$.


$R_0 \gets \tilde{1}$; $R_1 \gets \tilde{m}$
for $i=\ell-1$ downto $0$ do
$\quad R_0 \gets R_0 \otimes R_0$
$\quad$if $d_i = 1$ then $R_0 \gets R_0 \otimes R_1$
endfor
return $\tilde{R_0}$


The goal of the attacker is to recover the value of $d$.  Observe that the square-and-multiply algorithm processes the bits of $d$ from the left to the right.

Let $d = (d_{\ell-1}, \dots, d_0)_2$
At step $j$, the attacker

 already knows bits $d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1}$
 guesses that next bit is $d_j=1$
 chooses $T$ random messages $m_1, \dots, m_T$ and computes $$X_t = m_t^{(d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1},1)_2} \bmod N\quad\text{for $1\le t \le T$}$$
 prepares two sets $$\mathcal{S}_0 = \{m_t \mid \text{subtraction}\}\quad\text{and}\quad \mathcal{S}_0 = \{m_t \mid \text{no subtraction}\}$$
plays all messages in set $\mathcal{S}_0$ and obtains the average running time $\tau(\mathcal{S}_0)$ for an exponentiation; does the same for $\mathcal{S}_1$ and obtains $\tau(\mathcal{S}_1)$
if $\tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \not\approx 0$ then $d_j=1$ (the guess was correct); if  $\tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \approx 0$ then $d_j=0$ (the guess was incorrect)

Iterate the attack to find $d_{j-1},\dots$

In the above description, set $\mathcal{S}_0$ denotes the set of messages such that there is an extra subtraction at iteration $i=j$ in Step 4 of the square-and-multiply algorithm (i.e., Montgomery multiplication $R_0 \otimes R_1$) for the computation of $X_t$; set $\mathcal{S}_0$ denotes the set of messages such that there is no extra subtraction at iteration $i=j$ for the computation of $X_t$.
Note that the attacker can evaluate the exponentiation $X_t$ by herself as she knows $d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1}$.  Further, since $d_j$ is assumed to be $1$, the last operation of this exponentiation $X_t$ will be a Montgomery multiplication $R_0 \otimes R_1$ (i.e., Step 4 is executed at iteration $i=j$).
Correctness
If $d_j=1$ then the average time for an exponentiation for messages in set $\mathcal{S}_0$ will be greater than the average time for an exponentiation for messages in set $\mathcal{S}_1$ because there is always an extra subtraction for $\mathcal{S}_0$.
If $d_j=0$ then the average time for an exponentiation for messages in set $\mathcal{S}_0$ or in set $\mathcal{S}_1$ will be (roughly) the same because the sorting between the two sets looks like random. Remember that the attacker made the guess $d_j = 1$.