logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 3: 032111(2018) https://doi.org/10.1007/s11432-017-9210-3

Similar operation template attack on RSA-CRT as a case study

More info
  • ReceivedMay 13, 2017
  • AcceptedJul 19, 2017
  • PublishedJan 18, 2018

Abstract

A template attack, the most powerful side-channel attack methods, usually first builds the leakage profiles from a controlled profiling device, and then uses these profiles to recover the secret of the target device. It is based on the fact that the profiling device shares similar leakage characteristics with the target device. In this study, we focus on the similar operations in a single device and propose a new variant of the template attack, called the similar operation template attack (SOTA). SOTA builds the models on public variables (e.g., input/output) and recovers the values of the secret variables that leak similar to the public variables. SOTAs advantage is that it can avoid the requirement of an additional profiling device. In this study, the proposed SOTA method is applied to a straightforward RSA-CRT implementation. Because the leakage is (almost) the same in similar operations, we reduce the security of RSA-CRT to a hidden multiplier problem (HMP) over ${\rm~GF}(q)$, which can be solved byte-wise using our proposed heuristic algorithm. The effectiveness of our proposed method is verified as an entire prime recovery procedure in a practical leakage scenario.


Acknowledgment

This work was supported by Major State Basic Research Development Program (973 Program) (Grant No. 2013CB338004), National Natural Science Foundation of China (Grant Nos. U1536103, 61402286, 61472249, 61602239, 61572192, 61472250), Minhang District Cooperation Plan (Grant No. 2016MH310), and Natural Science Foundation of Jiangsu Province (Grant No. BK20160808).


References

[1] Kocher P C, Jaffe J, Jun B. Differential power analysis. In: Advances in Cryptology — CRYPTO99. Berlin: Springer, 1999. 15--19. Google Scholar

[2] Brier E, Clavier C, Olivier F. Correlation power analysis with a leakage model. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2004. 16--29. Google Scholar

[3] Gierlichs B, Batina L, Tuyls P. Mutual information analysis. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2008. 426--442. Google Scholar

[4] Batina L, Gierlichs B, Lemke-Rust K. Differential cluster analysis. In: Cryptographic Hardware and Embedded Systems--CHE 2009 Lausanne. Berlin: Springer, 2009. 112--127. Google Scholar

[5] Chari S, Rao J R, Rohatgi P. Template attacks. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2002. 13--28. Google Scholar

[6] Amiel F, Feix B, Villegas K. Power analysis for secret recovering and reverse engineering of public key algorithms. In: Proceedings of International Workshop on Selected Areas in Cryptography. Berlin: Springer, 2007. 110--125. Google Scholar

[7] Balasch J, Gierlichs B, Reparaz O, et al. DPA, bitslicing and masking at 1 GHz. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2015. 599--619. Google Scholar

[8] Tang M, Qiu Z L, Peng H B, et al. Toward reverse engineering on secret S-boxes in block ciphers. Sci China Inf Sci, 2014, 57: 032208. Google Scholar

[9] Genkin D, Adi Shamir A, Tromer E. RSA Key Extraction via low-bandwidth acoustic cryptanalysis. In: Proceedings of Advances in Cryptology — CRYPTO 2014. Berlin: Springer, 2014. 444--461. Google Scholar

[10] Genkin D, Pipman I, Tromer E. Get your hands off my laptop: physical side-channel key-extraction attacks on PCs. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2014. 242--260. Google Scholar

[11] Genkin D, Pachmanov L, Pipman I, et al. Stealing keys from PCs using a radio: cheap electromagnetic attacks on windowed exponentiation. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2015. 207--228. Google Scholar

[12] Genkin D, Pachmanov L, Pipman I, et al. ECDSA key extraction from mobile devices via nonintrusive physical side channels. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, 2016. 1626--1638. Google Scholar

[13] Belgarric P, Fouque P A, Macario-Rat G, et al. Side-channel analysis of Weierstrass and Koblitz curve ECDSA on Android smartphones. In: Proceedings of the Cryptographers Track at the RSA Conference 2016. Cham: Springer, 2016. 236--252. Google Scholar

[14] Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J Cryptol, 1997, 10: 233--260. Google Scholar

[15] Joye M, Yen S M. The montgomery powering ladder. In: Proceedings of Cryptographic Hardware and Embedded Systems, Redwood Shores, 2002. 291--302. Google Scholar

[16] Chevallier-Mames B, Ciet M, Joye M. Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity. IEEE Trans Comp, 2004, 53: 760--768. Google Scholar

[17] Brier E Joye M. Weierstraß Elliptic curves and side-channel attacks. In: Proceedings of International Workshop on Public Key Cryptography. Berlin: Springer, 2002. 2274: 335--345. Google Scholar

[18] Sinha Roy S, Jarvinen K, Verbauwhede I. Lightweight coprocessor for Koblitz curves: 283-Bit ECC including scalar conversion with only 4300 gates. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2015. 102--122. Google Scholar

[19] Witteman M. A DPA attack on RSA in CRT mode. Riscure Technical Report, 2009. https://www.riscure.com/archive/DPA_attack_on_RSA_in_CRT_mode.pdf. Google Scholar

[20] Aldaya A C, Sarmiento A J C, Sanchez-Solano S. SPA vulnerabilities of the binary extended Euclidean algorithm. J Cryp Eng, 2016, 7: 273--285. Google Scholar

[21] Walter C D. Sliding windows succumbs to big Mac attack. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2001. 286--299. Google Scholar

[22] Montminy D P, Baldwin R O, Temple M A, et al. Improving cross-device attacks using zero-mean unit-variance normalization. J Cryp Eng, 2013, 3: 99--110. Google Scholar

[23] Standaert F X, Archambeau C. Using subspace-based template attacks to compare and combine power and electromagnetic information leakages. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2008. 411--425. Google Scholar

[24] Archambeau C, Peeters E, Standaert F X, et al. Template attacks in principal subspaces. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2006. 1--14. Google Scholar

[25] Hospodar G, Gierlichs B, De Mulder E, et al. Machine learning in side-channel analysis: a first study. J Cryp Eng, 2011, 1: 293--305. Google Scholar

[26] Lerman L, Bontempi G, Markowitch O, et al. Power analysis attack: an approach based on machine learning. Int J Appl Cryp, 2014, 3: 97--115. Google Scholar

[27] Choudary O, Kuhn M G. Template attacks on different devices. In: Proceedings of International Workshop on Constructive Side-Channel Analysis and Secure Design. Cham: Springer, 2014. 179--198. Google Scholar

[28] Whitnall C, Oswald E. Robust profiling for DPA-style attacks. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2015. 3--21. Google Scholar

[29] Rivest R L, Shamir A, Adleman L M. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM 1983, 21: 96--99. Google Scholar

[30] Quisquater J J. Fast decipherment algorithm for RSA public-key cryptosystem. Electron Lett, 2007, 18: 905--907. Google Scholar

[31] Choudary O, Kuhn M G. Efficient template attacks. In: Proceedings of International Conference on Smart Card Research and Advanced Applications. Cham: Springer, 2013. 253--270. Google Scholar

[32] Belaıd S, Fouque P A, Gerard B. Side-channel analysis of multiplications in ${\rm~~GF}(2^{128}$)-application to AES-GCM. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014. 306--325. Google Scholar

[33] Belaıd S, Coron J S, Fouque P A, et al. Improved side-channel analysis of finite-field multiplication. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2015. 395--415. Google Scholar

[34] Merino Del Pozo S, Standaert F X. Blind source separation from single measurements using singular spectrum analysis. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems, Saint-Malo, 2015. 42--59. Google Scholar

[35] Renauld M, Standaert F X, Veyrat-Charvillon N, et al. A formal study of power variability issues and side-channel attacks for nanoscale devices. In: Advances in Cryptology — EUROCRYPT 2011. Berlin: Springer, 2011. 109--128. Google Scholar

  • Figure 1

    (Color online) Similar operations in the RSA-CRT combination phase.

  • Figure 2

    (Color online) Byte-wise multiplication from the most significant byte.

  • Figure 3

    (Color online) Prime byte filtered procedure.

  • Figure 4

    (Color online) Details of carry reduction procedure.

  • Figure 5

    (Color online) Power traces of targeted RSA-CRT implementation. (a) Combination phase overview; (b) public and secret leakage overview; (c) public and secret leakage details; (d) leakage characteristics.

  • Figure 6

    (Color online) Raw power traces before and after preprocessing. (a) Template; (b) leakage; (c) template after zero-mean; (d) leakage after zero-mean.

  • Figure 9

    (Color online) Two most significant prime bytes recovery results. (a) First prime byte recovery results; (b) second prime byte recovery results.

  • Figure 10

    (Color online) First two prime byte recovery results. Pink curve indicates the second byte results based on correct first byte. Gray curves indicate the second byte results based on incorrect first byte.

  • Figure 11

    (Color online) Results of 2nd–8th prime byte recovery.

  • Figure 12

    (Color online) During these recovery experiments, the results show the two options of the previous prime bytes. All the left-hand sides of all the figures show the correct previous prime bytes. (a) 9–16 prime byte recovery results; (b) 17–24 prime byte recovery results; (c) 25–32 prime byte recovery results; (d) 33–40 prime byte recovery results; (e) 41–48 prime byte recovery results; (f) 49–56 prime byte recovery results; (g) 57–64 prime byte recovery results.

  • Figure 13

    (Color online) First and second prime byte recovery results with different noisy inputs. When recovering the second prime byte, we give two options of the first prime byte. The left part shows the correct one. (a) First prime byte results with noisy inputs; (b) second prime byte results with noisy inputs.

  •   

    Algorithm 1 RSA-CRT implementation

    Require:Secret key $d$, secret primes $p$ and $q$ message $M$;

    Output:$C$=$M^d$ textmdmod $N$;

    $d_p$=$d$ textmdmod $p$, $d_q$=$d$ textmdmod $q$;

    $K$=$p^{-1}$ textmdmod $q$;

    $M_p$=$M$ textmdmod $p$, $M_q$=$M$ textmdmod $q$;

    $C_p$=$M_p^{d_p}$ textmdmod $p$;

    $C_q$=$M_q^{d_q}$ textmdmod $q$;

    $C$=$(((C_q-C_p)\times~K)~\text{mod}~q)\times~p+C_p$;

    Return $C$.

  •   

    Algorithm 2 Byte choice algorithm of 16-bit intermediate value

    Require:index $i$ $j$, attack index BytePosition, 16-bit Intermediate value TempResult;

    Output:PreviousByte, CurrentByte, NextByte=ByteChoice(TempResult);

    if $i+j~==$ BytePosition-2 then

    PreviousByte $\Leftarrow$ TempResult & 0xFF;

    CurrentByte $\Leftarrow$ 0;

    NextByte $\Leftarrow$ 0;ELSIF $~i+j~==$ BytePosition-1

    PreviousByte $\Leftarrow$ TempResult$>>$8 & 0xFF;

    CurrentByte $\Leftarrow$ TempResult & 0xFF;

    NextByte $\Leftarrow$ 0;ELSIF $i+j$ = BytePosition

    PreviousByte $\Leftarrow$ 0;

    CurrentByte $\Leftarrow$ TempResult$>>8$ & 0xFF;

    NextByte $\Leftarrow~$ TempResult & 0xFF;ELSIF $i+j$ = BytePosition+1

    PreviousByte $\Leftarrow~0~$;

    CurrentByte $\Leftarrow~0$;

    NextByte $\Leftarrow$ TempResult$>>8$ & 0xFF;

    else

    PreviousByte $\Leftarrow$ 0;

    CurrentByte $\Leftarrow$ 0;

    NextByte $\Leftarrow$ 0;

    end if

  •   

    Algorithm 3 Single prime byte recovery algorithm

    Require:$x^t=\{x_{n-1}^t,x_{n-2}^t,\ldots,x_{i}^t,x_{i-1}^t~\}$,$~~\text{where}~x_{i}^t\in~\mathcal{I}^t_0$$~\text{and}~x_{i-1}^t\in~\mathcal{I}^t_1$,$~~~p=\{p_{n-1},~p_{n-2},\ldots,p_{i+1}\}$, previous prime byte set $S_{\text{pre}}$ where $p_{i+1}\in~S_{\text{pre}}$, result $r^t=\{r_{2n-1}^t,\ldots,r_{n}^t\}$.

    Output:$S_{p_{i+1},p_{i}}$.

    for $t=0$ to $n$

    for all $p_{i+1}\in~S_{\text{pre}}$

    for prime = 0 to 255

    Index$\Leftarrow~1$; $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\vartriangleright$ flag

    $p=\{p_{n-1},~p_{n-2},\ldots,p_{i+1},\text{prime}\}$;

    for all $x_{i}^t\in~\mathcal{I}^t_0$

    for all $x_{i-1}^t\in~\mathcal{I}^t_1$

    $x^t=\{x_{n-1}^t,x_{n-2}^t,\ldots,x_{i}^t,x_{i-1}^t,x_{i}^t,x_{i-1}^t~\}$; $~~~~~~~~~~~~~~~~\vartriangleright$ obtain previous input bytes

    TempResult=$g(x,p,C_{2n-i-1})$; $~~~~~~~~~~~~~~~\vartriangleright$ obtain TempResult

    PreviousByte,CurrentByte,NextByte=ByteChoice(TempResult); $\vartriangleright$ obtain intermediate value

    if CurrentByte$\leq~r^{t}_{2n-i}-1$ && PreviousByte$\equiv~r^{t}_{2n-i+1}$ && Index then

    $A[p_{i+1}][\text{prime}]+=1$; $~~~~~~~~~~~~\vartriangleright$ compare intermediate value and $r^t$, count all possible prime byte

    Index$\Leftarrow$ 0;

    end if

    end for

    end for

    end for

    end for

    end for

    $S_{p_{i+1},p_{i}}\Leftarrow~\text{max}(A_{p_{i+1}}~^{\text{prime}})$. $~~~~~~~~~~~~~~~~\vartriangleright$ obtain prime byte results

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1