RSA Timing Attack on "Extra" Montgomery Reduction

Question

In "A practical implementation of the timing attack", the authors take advantage of a timing difference that stems from "extra reductions" that occur when multiplying numbers in the Montgomery form. After implementing a toy example of this attack, I thought I understood it. I created two sets of messages, one set containing messages $m$ where $m^3$ did not require an extra reduction ($M1$) and another set where $m^3$ did require an extra reduction ($M2$). I then augmented a square-and-multiply algorithm to take advantage of Montgomery multiplication while tracking the number of extra reductions that took place over the course of the exponentiation.

This quick experiment did appear to show that the set in which $m^3$ did not require an extra reduction ($M1$) on average would have less extra reductions than the other set. However, the difference in the two averages would be much larger than one. Most of the paper seems to suggest the timing attack they exploited relied on the timing difference a single extra reduction (e.g. section 7.1).

I believe I see an attack here, but its not the exact situation that the authors describe. It sounds like the authors are suggesting that a square-and-multiply exponentiation algorithm that relied on Montgomery multiplication would use $n$ extra reductions for messages in the set $M1$ and $n+1$ extra reductions for messages in the set $M2$ which does not make sense to me intuitively. Am I misunderstanding this attack?

Edit: After comparing my attack code with others, it turns out I understood the attack just fine and my experiment was different. The difference between my results and the results from the original paper was due to my selection of the Montgomery parameters. The value of $R$ used to put numbers in Montgomery form can have a major effect on the number of reductions required per multiplication.

Answer 1

Montgomery multiplication

Theorem (Montgomery, 1985). For any odd integer $N$ and any integer $0 \le T < 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} < 2N\end{cases}$$

The last 2 properties show that $R:=T2^{-k} \bmod{N}$ can be computed in two steps as:

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

Montgomery arithmetic represents an integer $0\le x <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$.

1. $R_0 \gets \tilde{1}$; $R_1 \gets \tilde{m}$
2. for $i=\ell-1$ downto $0$ do
3. $\quad R_0 \gets R_0 \otimes R_0$
4. $\quad$if $d_i = 1$ then $R_0 \gets R_0 \otimes R_1$
5. endfor
6. 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$.

Answer 2

What a coincidence, I implemented this attack yesterday!

I'm executing it right now and I can tell you that the difference at each step is around 1 reduction (as the paper suggests). See for example my logs for bits 6 to 8 of a 96-bit key:

 bit 6: avg M2 (#111)= 1.2072072072072073, avg M1 (#99889)= 0.1684369650311846
[1, 1, 1, 1, 1, 1, 1]
 bit 7: avg M2 (#99)= 0.18181818181818182, avg M1 (#99901)= 0.16957788210328226
[1, 1, 1, 1, 1, 1, 1, 0]
 bit 8: avg M2 (#98)= 1.1938775510204083, avg M1 (#99902)= 0.16858521350923905
[1, 1, 1, 1, 1, 1, 1, 0, 1]

As you can see, in bits 6 and 8, which are set to 1, the average of M2 and M1 differs in approximately 1 reduction (my proof-of-concept measures reductions for the moment, not time), while in bit 5, which is set to 0, there is almost no difference.

As far as I understand, the idea of the attack is that on each step (i.e., on each bit guess) the attacker partitions the samples in those that needed a reduction on that particular step (M2), and those that didn't (M1). You seem to think that this implies that messages in M2 would tend to have more reductions apart from the one that is isolated in the current step. However, from the numbers I got, that doesn't seem to be the case: at each step, only the 0.1% of all the samples needed a reduction (e.g., in bit 6, only 111 out of 100000 samples), which indicates that reductions are actually very rare, so most samples will have 0, 1 or perhaps 2 reductions for the whole exponentiation.

The trick is that if you are capable of identifying the moments where reductions occur (which in the attack is achieved by computing all the square-and-multiply operations for each sample, for each step), then you have a criterion for telling the samples apart. As a result, the most probable result is that the difference between M2 and M1 is due only to the presence of a reduction for the current step.