# On the Security of Practical Mail User Agents against Cache Side-Channel Attacks +
## 2 Preliminary
### Cryptographic Implementation  
The efficient implementation of cryptographic algorithms is of great importance in many cryptographic libraries such as OpenSSL and GnuPG. Therefore, many optimization techniques have been adopted to accelerate encryption or decryption operations in these libraries (for example, the square-and-multiply algorithm for RSA decryption). Unfortunately, these techniques can lead to unexpected vulnerabilities against side-channel attacks, such as FLUSH+RELOAD, as a side effect. **RSA implementation in GnuPG**. GnuPG supports the RSA public-key algorithm for signature generation verification or data encryption/decryption in full support of OpenPGP. Because RSA decryption requires a significant number of exponentiation calculations, GnuPG adopts the optimization techniques CRT-RSA and square-and-multiply for efficient decryption in its implementation. **CRT-RSA**. CRT-RSA is an optimization technique for rapid RSA decryption based on the Chinese Remainder Theorem (CRT). The general RSA algorithm proceeds as follows:  
1. Randomly select two large prime numbers \(p\) and \(q\). 2. Calculate \(n\ =\ pq\). 3. Select \(e\) such that \(1<e<((p\ -\ 1)(q\ -\ 1)\ -\ 1)\) and \(gcd(e,\ (p-1)(q-1))\ =\ 1\), where \(gcd(a,b)\) returns the greatest common divisor of \(a\) and \(b\). 4. Calculate \(d\ =\ e^{-1}\bmod(p-1)(q-1)\). 5. Set _public key_ as \((n,\,e)\), and _private key_ as \((d,\,n)\). RSA encryption and decryption are performed by \(Enc(m):c\gets m^{e}\bmod n\) and \(Dec(c):m\gets c^{d}\mod n\), respectively. In CRT-RSA, the secret key \(d\) is split into two parts: \(d_{p}\ =\ d\bmod(p-1)\) and \(d_{q}\ =\ d\bmod(q-1)\). The secret parameters would then be _private key_\(=\ (d_{p},\,d_{q},\,p,\,q)\). The decryption function of CRT-RSA is described in Algorithm 1. ```
decryption\((c,\,d_{p},\,d_{q},\,p,\,q)\) \(m_{p}\gets c^{d_{p}}\bmod p\) \(m_{q}\gets c^{d_{q}}\bmod q\) \(h\leftarrow(m_{p}-m_{q})\ (q^{-1}\bmod p)\ (\bmod p)\) \(m\gets m_{q}+hq\) return\(m\)
```  
**Algorithm 1**CRT-RSA decryption  
**Square-and-multiply algorithm**. The square-and-multiply algorithm is used to reduce the number of exponent operations required for encryption and decryption. As shown in Algorithm 2, the square-and-multiply algorithm computes the exponentiation with a square-multiply operation if the bit of the binary representation of the exponent is 1 and computes it with a square operation otherwise. For example, for \(a^{13}\), the exponent 13 can be denoted as \(1101_{2}\). The operation sequence for the exponent would then be \((Square-Multiply,\,Square,\,Square-Multiply)\), each followed by a Modulo Reduce, instead of performing all exponentiation calculations, such as multiplying \(a\) 13 times. Because each iteration of the square and square-multiply operations exactly corresponds to each bit of the binary exponent, the execution flow contains all of the information about the exponents, which is the secret key in CRT-RSA. ```
// \(d_{p}\) is the binary representation of an exponent. // \(n\) is the length of the \(d_{p}\) : (\(d_{n}\), \(d_{n-1}\),..., \(d_{0}\)). // (\(d_{p}\))\({}_{i}\) is the \(i^{th}\) bit of the \(d_{p}\). square and multiply(\(c\), \(d_{p}\), \(p\)) \(m\gets 1\) for\(i=n-1\) down to \(0\)do \(m\gets m^{2}\) (mod \(p\)) if\((d_{p})_{i}==1\)then \(m\gets mc\) (mod \(p\))  end if end return\(m_{p}\)
```  
**Algorithm 2**Square-and-Multiply  
Because decryption in CRT-RSA involves two exponents, acquiring the execution flow for the square-and-multiply algorithm in GnuPG allows the two elements \(d_{p}\) and \(d_{q}\) to be restored, which subsequently permits the full recovery of the victim's private key \(d\). [PERSON] [17] describes how the attacker is able to perform a FLUSH+RELOAD attack and collect the secret information of the private key when the victim performs RSA decryption in a virtualized desktop environment with GnuPG 1.4.13.