This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we consider what can be done to mitigate the threat of side-channels against RSA implementations...
To keep things simple in this post, we'll talk about so-called "vanilla" RSA (where no randomness is used in encryption) and highlight a small number of potential side-channel attacks along with countermeasures.
Let's start by recalling the vanilla RSA encryption scheme.
Key generation picks a secret pair of odd prime integers, $p$ and $q$, and computes the modulus $N = pq$. An integer $3 \leq e \leq \phi(N)$, coprime to $\phi(N)$, is chosen. Then the public key is the pair $\left(N, e\right)$ and the secret key is the unique integer $3 \leq d \leq \phi(N)$ such that $ed \equiv 1 \: \left( \mathrm{mod} \: \phi(N) \right)$.
To encrypt a message $m \in \mathbb{Z}_N$, one computes $m^e \: \left( \mathrm{mod} \: N \right)$.
To decrypt a ciphertext $c \in \mathbb{Z}_N$, one computes $c^d \: \left( \mathrm{mod} \: N \right)$.
An SPA-Style Attack to Determine the Secret Key
We first give an example of how information about the secret key $d$ could be leaked during the decryption operation. A typical implementation of exponentiation will be a branching program that behaves differently depending on the inputs. Consider, for example, the square and multiply algorithm which efficiently computes an exponentiation where the exponent is expressed in binary:
Say $d = \sum_{0\leq i \leq n} b_i 2^i$ where each $b_i \in \lbrace 0,1 \rbrace$. Then,
\[ c^d = \prod_{0 \leq i \leq n} c^{b_i 2^i }.\] Noting that, if we ignore the bits $b_i$, each factor in the product is the square of the previous factor, we can easily compute the product as follows:
- $ANS \leftarrow 1$
- $fac \leftarrow c$
- For $0 \leq i \leq n$, do
- If $b_i = 1$,
- $ANS \leftarrow ANS \times fac$
- $fac \leftarrow fac^2$
- Else,
- $fac \leftarrow fac^2$
- Return $ANS$.
In order to prevent this kind of attack, one must make the two branches of the algorithm look the same to an attacker, i.e. have both branches of the square and multiply algorithm take the same amount of time to run or consume the same amount of power.
An SPA-Style Attack to Determine the Plaintext
The above shows how the exponentiation operation used in decryption could compromise the secret key. But an attacker may be interested in a particular plaintext, $m$ (after all, encryption is designed to keep such messages secret). Again, if the encryption operation is a branching program which depends on the value of $m$, the runtime or power consumption of a single encryption could leak information about $m$ in an SPA-style attack. In particular, note that one has to perform a modular reduction in encryption. In most implementations, instead of a single reduction of a very large integer at the end of the exponentiation, there will be many modular reductions throughout the exponentiation algorithm in order to keep the numbers involved (relatively) small. As a slightly contrived example, suppose we perform modular reduction via the following loop:
- While $ANS > N$
- $ANS \leftarrow ANS - N$
Again, to prevent this kind of attack we must ensure that our programme takes the same amount of time and consumes the same amount of power to reduce intermediate values modulo $N$, no matter what size they are (up to some upper bound which can easily be found since we know the exact exponent and range of values for the base).
Preventing DPA-Style Attacks on the Secret Key
Even if we obscure any branching in decryption that depends on $d$, the precise details of the operations performed in carrying out the exponentiations for decryption will still depend (in a less obvious way) on the exponent. So, over multiple decryptions, a statistical relationship between the decryption key and the duration or power consumption of the operations may emerge. Therefore we also need to prevent more subtle DPA-style attacks where the attacker uses statistical techniques on a large number of traces to test hypotheses on the secrect key.
To do this, we have to remove the direct dependency between the secrect key and the calculation performed each time. This involves blinding, where some random noise is injected into the exponentiation operation without affecting the result. In the case of decryption, we introduce randomness in the exponent: while $d$ is the unique multiplicative inverse of $e$ in $\mathbb{Z}_{\phi(N)}$ such that $3 \leq d \leq \phi(N)$, we can add or subtract integer multiples of $\phi(N)$ to $d$ and obtain a new inverse. So to decrypt $c \in \mathbb{Z}_N$, select a random $r \in \mathbb{Z}$ and compute $d' = d + r\phi(N)$. Then compute the message $c^{d'} \: \left( \mathrm{mod} \: N \right)$ which will be the same as directly computing $c^d \: \left( \mathrm{mod} \: N \right)$. The point is that addition is not usually a branching operation, so adding $r\phi(N)$ to $d$ will not leak information about $d$ on a single trace, and using a new random $r$ for each decryption prevents DPA-style attacks.
Coppersmith's SPA-Style Attack to Determine the Plaintext
We conclude this post with a special and interesting attack to determine $m$ which is only possible when $e$ is small ($e=3$ is a popular choice of exponent for efficiency of encryption). There is a theorem due to Coppersmith (see this article) that an attacker can efficiently find all 'small' integer roots modulo $N$ of an integer polynomial $f$ of degree $e$, where small essentially means having absolute value less than $N^{1/e}$. Obviously if $m$ happens to be small then one can use this to directly solve the equation $m^e \equiv c \: \left (\mathrm{mod} \: N \right)$ as required to recover the plaintext. If not, but some of the most significant bits of $m$ are leaked, then we may write $m = m_k + m_u$ where $m_k$ is known and $m_u$ is small, obtaining an integer polynomial $f(X) = \left( m_k + X \right)^e - c$ whose small roots modulo $N$ can be found via the Coppersmith method and correspond to the remaining bits of $m$. So we need to make sure that bits of $m$ are not leaked by the encryption operation.
To counter this kind of attack, one again uses blinding: we introduce some randomness to $m$ before exponentiating and remove it again afterwards. More precisely, to encrypt $m \in \mathbb{Z}_N$, we select a random $r \in \mathbb{Z}_N$, compute $rm \: \left( \mathrm{mod} \: N \right) $, then $\left(rm\right)^e \: \left( \mathrm{mod} \: N \right)$ and finally multiply the result by $r^{\phi(N)-e}$ (and reduce modulo $N$ again). Obviously the ciphertext is the same as it would have been without blinding, but the leakage of the exponentiation operation is now independent of $m$.
This should give you a flavour of the kind of side-channel attacks that can be mounted on an encryption scheme and the way implementations can avoid them.
No comments:
Post a Comment