52 Things: Number 45: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for RSA.
52 Things: Number 45: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for RSA.
52 Things: Number 45: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for RSA.
52件事：第45件：描述RSA文獻中提出的針對側信道攻擊的一些基本（可能無效）防御措施。
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...
這是一系列博客文章中的最新一篇，旨在解決“每個博士生在做密碼學時應該知道的52件事”：這是一組問題，旨在讓博士生在第一年結束時了解他們應該知道什么。本周，我們將考慮如何減輕副通道對RSA實施的威脅。。。
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.
在這篇文章中，為了簡單起見，我們將討論所謂的“香草”RSA（加密中不使用隨機性），并重點介紹少數潛在的側通道攻擊以及對策。
Let's start by recalling the vanilla RSA encryption scheme.
讓我們首先回顧一下普通的RSA加密方案。
Key generation picks a secret pair of odd prime integers, p and q, and computes the modulus N=pq. An integer 3≤e≤?(N), coprime to ?(N), is chosen. Then the public key is the pair (N,e) and the secret key is the unique integer 3≤d≤?(N) such that ed≡1(mod?(N)).
密鑰生成選擇一對秘密的奇數素數 p 和 q ，并計算模 N=pq 。選擇一個與#4互質的整數#3。則公鑰是對 (N,e) ，而密鑰是唯一整數 3≤d≤?(N) ，使得 ed≡1(mod?(N)) 。
To encrypt a message m∈ZN, one computes me(modN).
要加密消息 m∈ZN ，需要計算 me(modN) 。
To decrypt a ciphertext c∈ZN, one computes cd(modN).
為了解密密文 c∈ZN ，計算 cd(modN) 。
An SPA-Style Attack to Determine the Secret Key
一種確定密鑰的SPA式攻擊
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:
我們首先給出了一個關于密鑰 d 的信息如何在解密操作期間被泄露的例子。冪運算的一個典型實現將是一個分支程序，它的行為取決于輸入。例如，考慮平方和乘法算法，該算法有效地計算指數，其中指數以二進制表示：
Say d=∑0≤i≤nbi2i where each bi∈{0,1}. Then,
說出 d=∑0≤i≤nbi2i ，其中每個 bi∈{0,1} 。然后
cd=∏0≤i≤ncbi2i.
Noting that, if we ignore the bits bi, each factor in the product is the square of the previous factor, we can easily compute the product as follows:注意，如果我們忽略比特 bi ，乘積中的每個因子都是前一個因子的平方，我們可以很容易地計算乘積，如下所示：
- ANS←1
- fac←c
- For 0≤i≤n, do 對于 0≤i≤n ，執行
- If bi=1, 如果 bi=1 ，
- ANS←ANS×fac
- fac←fac2
- Else, 其他的
- fac←fac2
- Return ANS. 返回 ANS 。
根據每個 bi 是 0 還是 1 ，算法的行為不同。因此，如果使用該算法來解密RSA密文，則它所花費的時間或其功耗可以揭示每個比特#3的值，從而揭示密鑰#4。這將是SPA式的攻擊，因為只需要一個跟蹤。
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
確定明文的SPA式攻擊
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:
上面顯示了解密中使用的冪運算是如何泄露密鑰的。但攻擊者可能對特定的明文 m 感興趣（畢竟，加密是為了對此類消息保密而設計的）。同樣，如果加密操作是一個取決于 m 值的分支程序，那么在SPA式攻擊中，單個加密的運行時間或功耗可能會泄露有關 m 的信息。特別要注意的是，必須對加密進行模塊化縮減。在大多數實現中，不是在求冪結束時對一個非常大的整數進行單一的縮減，而是在整個求冪算法中進行許多模塊化縮減，以保持所涉及的數字（相對）較小。作為一個略顯做作的例子，假設我們通過以下循環執行模塊化約簡：
- While ANS>N 而 ANS>N
- ANS←ANS?N
由于在加密的情況下指數是已知的，因此根據運行所需的時間和消耗的功率，它會泄露有關基 m 的信息（參見David關于攻擊Montgomery算術的帖子）。
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).
同樣，為了防止這種攻擊，我們必須確保我們的程序花費相同的時間和消耗相同的功率來減少模 N 的中間值，無論它們的大小如何（高達一些上限，這很容易找到，因為我們知道基數的確切指數和值的范圍）。
Preventing DPA-Style Attacks on the Secret Key
防止對密鑰的DPA式攻擊
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.
即使我們掩蓋了解密中依賴于 d 的任何分支，在執行解密的冪運算時執行的操作的精確細節仍將（以不太明顯的方式）取決于冪。因此，在多次解密過程中，解密密鑰與操作的持續時間或功耗之間可能會出現統計關系。因此，我們還需要防止更微妙的DPA式攻擊，即攻擊者在大量跟蹤上使用統計技術來測試對secrect密鑰的假設。
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 Z?(N) such that 3≤d≤?(N), we can add or subtract integer multiples of ?(N) to d and obtain a new inverse. So to decrypt c∈ZN, select a random r∈Z and compute d′=d+r?(N). Then compute the message cd′(modN) which will be the same as directly computing cd(modN). The point is that addition is not usually a branching operation, so adding r?(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.
要做到這一點，我們必須消除secrect鍵和每次執行的計算之間的直接依賴關系。這涉及到盲法，在不影響結果的情況下，將一些隨機噪聲注入冪運算。在解密的情況下，我們在指數中引入隨機性：而 d 是#2中 e 的唯一乘法逆，因此#3，我們可以將#4到 d 的整數倍相加或相減，從而獲得新的逆。因此，要解密 c∈ZN ，請隨機選擇 r∈Z 并計算 d′=d+r?(N) 。然后計算消息 cd′(modN) ，這將與直接計算 cd(modN) 相同。關鍵是加法通常不是分支操作，因此將 r?(N) 添加到 d 不會在單個跟蹤上泄露關于 d 的信息，并且每次解密使用新的隨機 r 可以防止DPA式的攻擊。
Coppersmith's SPA-Style Attack to Determine the Plaintext
Coppersmith的SPA式攻擊確定明文
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 N1/e. Obviously if m happens to be small then one can use this to directly solve the equation me≡c(modN) as required to recover the plaintext. If not, but some of the most significant bits of m are leaked, then we may write m=mk+mu where mk is known and mu is small, obtaining an integer polynomial f(X)=(mk+X)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.
在這篇文章的結尾，我們用一個特殊而有趣的攻擊來確定 m ，這只有在 e 很小的時候才有可能（ e=3 是加密效率的常用指數選擇）。Coppersmith提出了一個定理（見本文），攻擊者可以有效地找到 e 次的整數多項式#4的模 N 的所有“小”整數根，其中小本質上意味著絕對值小于 N1/e 。顯然，如果 m 恰好很小，則可以根據恢復明文的需要使用它來直接求解方程 me≡c(modN) 。如果不是，但是 m 的一些最高有效位被泄露，那么我們可以寫 m=mk+mu ，其中 mk 是已知的， mu 是小的，獲得整數多項式 f(X)=(mk+X)e?c ，其小的根模 N 可以通過Coppersmith方法找到，并且對應于 m 的剩余位。因此，我們需要確保 m 的比特不會被加密操作泄露。
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∈ZN, we select a random r∈ZN, compute rm(modN), then (rm)e(modN) and finally multiply the result by r?(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.
為了對抗這種攻擊，我們再次使用致盲：我們在指數化之前向 m 引入一些隨機性，然后再次將其移除。更準確地說，為了加密 m∈ZN ，我們選擇一個隨機的#2，計算#3，然后計算#4，最后將結果乘以 r?(N)?e （并再次減少模 N ）。顯然，密文與沒有盲法的情況下相同，但冪運算的泄漏現在與 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.
這應該會讓您了解可以安裝在加密方案上的側通道攻擊，以及實現可以避免這些攻擊的方式。
The Working Class Must Lead！
浙公網安備 33010602011771號