Survey of Side-channel Attacks and Countermeasures on Post-quantum Cryptography
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61802180); Natural Science Foundation of Jiangsu Province of China (BK20180421); National Cryptography Development Fund (MMJJ20180105); Fundamental Research Funds for the Central Universities (NE2018106)

  • Article
  • | |
  • Metrics
  • |
  • Reference [80]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    To solve the threat of quantum computing to the security of public-key cryptography, post-quantum cryptography has become a frontier focus in the field of cryptography. Post-quantum cryptography guarantees the security of the algorithm through mathematical theories, but it is vulnerable to side-channel attacks in specific implementation and applications, which will seriously threaten the security of post-quantum cryptography. This study is based on the round 2 candidates in the NIST post-quantum cryptography standardization process and the round 2 candidates in the CACR public key cryptography competition in China. First, classification investigations of various post-quantum cryptographic algorithms are conducted, including lattice-based, code-based, hash-based, and multivariate-based cryptographic algorithms. Then, their security status against side-channel attacks and existing protection strategies are analyzed. To analyze the methods of side-channel attack against post-quantum cryptography, it is summarized that the commonly used post-quantum cryptography side-channel attack methods, attack targets, and attack evaluation indexes for various post-quantum cryptography according to the classification of core operators and attack types. Furthermore, following the attack types and attack targets, the existing countermeasures for attack and the costs of defense strategies are sorted out. Finally, in the conclusion part, some security suggestions are put forward according to the attack method, protection means, and protection cost, and also the potential side-channel attack methods and defense strategies in the future are analyzed.

    Reference
    [1] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, Society for Industrial and Applied Mathematics, 1999,41(2):303-332.
    [2] Bindel N, Buchmann J, Krämer J. Lattice-based signature schemes and their sensitivity to fault attacks. In:Proc. of the 2016 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC). 2016. 63-77.
    [3] Khalid A, Rafferty C, Howe J, Brannigan S, Liu W, O'Neill M. Error samplers for lattice-based cryptography-challenges, vulnerabilities and solutions. In:Proc. of the 2018 IEEE Asia Pacific Conf. on Circuits and Systems (APCCAS). 2018. 411-414.
    [4] Khalid A, Oder T, Valencia F, O'Neill M, Güneysu T, Regazzoni F. Physical protection of lattice-based cryptography:Challenges and solutions. In:Proc. of the 2018 on Great Lakes Symp. on VLSI. Chicago:Association for Computing Machinery, 2018. 365-370.
    [5] Roy KS, Kalita HK. A survey on post-quantum cryptography for constrained devices. Int'l Journal of Applied Engineering Research, 2019,14(11):2608-2615.
    [6] Valencia F, Oder T, Güneysu T, Regazzoni F. Exploring the vulnerability of R-LWE encryption to fault attacks. In:Proc. of the 5th Workshop on Cryptography and Security in Computing Systems. Association for Computing Machinery, 2018. 7-12.
    [7] Drăgoi V, Richmond T, Bucerzan D, Legay A. Survey on cryptanalysis of code-based cryptography:From theoretical to physical attacks. In:Proc. of the 7th Int'l Conf. on Computers Communications and Control (ICCCC). 2018. 215-223.
    [8] Nejatollahi H, Dutt N, Ray S, Regazzoni F, Banerjee I, Cammarota R. Post-quantum lattice-based cryptography implementations:A survey. ACM Computing Surveys, 2019,51(6):129:1-129:41.
    [9] Ti YB. Fault attack on supersingular isogeny cryptosystems. In:Lange T, Takagi T, eds. Post-quantum Cryptography. Cham:Springer Int'l Publishing, 2017. 107-122.
    [10] Gélin A, Wesolowski B. Loop-abort faults on supersingular isogeny cryptosystems. In:Lange T, Takagi T, eds. Post-quantum Cryptography. Cham:Springer Int'l Publishing, 2017. 93-106.
    [11] Koziel B, Azarderakhsh R, Jao D. Side-channel attacks on quantum-resistant supersingular isogeny Diffie-Hellman. In:Adams C, Camenisch J, eds. Selected Areas in Cryptography-SAC 2017. Cham:Springer International Publishing, 2018. 64-81.
    [12] Computer Security Division ITL. Round 2 submissions-post-quantum cryptography|csrc. CSRC|NIST, 2017-01-03. (2017-01-03)[2020-05-25]. https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions
    [13] https://sfjs.cacrnet.org.cn/site/term/list_77_1.html
    [14] Kocher PC. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In:Koblitz N, ed. Advances in Cryptology-CRYPTO'96. Berlin, Heidelberg:Springer-Verlag, 1996. 104-113.
    [15] Kocher P, Jaffe J, Jun B. Differential power analysis. In:Wiener M, ed. Proc. of the Advances in Cryptology-CRYPTO'99. Berlin, Heidelberg:Springer-Verlag, 1999. 388-397.
    [16] Brier E, Clavier C, Olivier F. Correlation power analysis with a leakage model. In:Joye M, Quisquater J-J, eds. Proc. of the Cryptographic Hardware and Embedded Systems-CHES 2004. Berlin, Heidelberg:Springer-Verlag, 2004. 16-29.
    [17] Chari S, Rao JR, Rohatgi P. Template attacks. In:Kaliski BS, Koççetin K, Paar C, eds. Proc. of the Cryptographic Hardware and Embedded Systems-CHES 2002. Berlin, Heidelberg:Springer-Verlag, 2003. 13-28.
    [18] Biham E, Shamir A. Differential fault analysis of secret key cryptosystems. In:Kaliski BS, ed. Proc. of the Advances in Cryptology-CRYPTO'97. Berlin, Heidelberg:Springer-Verlag, 1997. 513-525.
    [19] Mathan SA, Koedinger KR. Fostering the intelligent novice:Learning from errors with metacognitive tutoring. Educational Psychologist, Routledge, 2005,40(4):257-265.
    [20] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In:Gilbert H, ed. Proc. of the Advances in Cryptology-EUROCRYPT 2010. Berlin, Heidelberg:Springer-Verlag, 2010. 1-23.
    [21] Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 2015,75(3):565-599.
    [22] Saarinen M-JO. Arithmetic coding and blinding countermeasures for lattice signatures. Journal of Cryptographic Engineering, 2018, 8(1):71-84.
    [23] Pessl P. Analyzing the shuffling side-channel countermeasure for lattice-based signatures. In:Dunkelman O, Sanadhya SK, eds. Proc. of the Progress in Cryptology-INDOCRYPT 2016. Cham:Springer Int'l Publishing, 2016. 153-170.
    [24] Primas R, Pessl P, Mangard S. Single-trace side-channel attacks on masked lattice-based encryption. In:Fischer W, Homma N, eds. Proc. of the Cryptographic Hardware and Embedded Systems-CHES 2017. Cham:Springer Int'l Publishing, 2017. 513-533.
    [25] Kim S, Hong S. Single trace analysis on constant time CDT sampler and its countermeasure. Applied Sciences, Multidisciplinary Digital Publishing Institute, 2018,8(10):1809.
    [26] Pessl P, Primas R. More practical single-trace attacks on the number theoretic transform. In:Schwabe P, Thériault N, eds. Proc. of the Progress in Cryptology-LATINCRYPT 2019. Cham:Springer Int'l Publishing, 2019. 130-149.
    [27] Huang W-L, Chen J-P, Yang B-Y. Power analysis on NTRU prime. IACR Trans. on Cryptographic Hardware and Embedded Systems, 2020, 123-151.
    [28] Ravi P, Roy SS, Chattopadhyay A, Bhasin S. Generic side-channel attacks on CCA-secure lattice-based PKE and KEMS. IACR Trans. on Cryptographic Hardware and Embedded Systems, 2020,2019:307-335.
    [29] Bruinderink LG, Pessl P. Differential fault attacks on deterministic lattice signatures. IACR Trans. on Cryptographic Hardware and Embedded Systems, 2018, 21-43.
    [30] Ravi P, Roy DB, Bhasin S, Chattopadhyay A, Mukhopadhyay D. Number "not used" once-practical fault attack on PQM4 implementations of nist candidates. In:Polian I, Stöttinger M, eds. Proc. of the Constructive Side-channel Analysis and Secure Design. Cham:Springer Int'l Publishing, 2019. 232-250.
    [31] McCarthy S, Howe J, Smyth N, Brannigan S, O'Neill M. BEARZ attack falcon:implementation attacks with countermeasures on the falcon signature scheme. In:Proc. of the SECRYPT. 2019. 61-71.
    [32] Valencia F, Polian I, Regazzoni F. Fault sensitivity analysis of lattice-based post-quantum cryptographic components. In:Pnevmatikatos DN, Pelcat M, Jung M, eds. Proc. of the Embedded Computer Systems:Architectures, Modeling, and Simulation. Cham:Springer Int'l Publishing, 2019. 107-123.
    [33] Albrecht MR, Deo A, Paterson KG. Cold boot attacks on ring and module LWE keys under the NTT. IACR Trans. on Cryptographic Hardware and Embedded Systems, 2018, 173-213.
    [34] D'Anvers J-P, Tiepelt M, Vercauteren F, Verbauwhede I. Timing attacks on error correcting codes in post-quantum secure schemes. IACR Cryptology ePrint Archive, 2019,2019:292.
    [35] Espitau T, Fouque P-A, Gérard B, Tibouchi M. Side-channel attacks on Bliss lattice-based signatures:Exploiting branch tracing against strong swan and electromagnetic emanations in microcontrollers. In:Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security. Dallas:Association for Computing Machinery, 2017. 1857-1874.
    [36] Roy SS, Reparaz O, Vercauteren F, Verbauwhede I. Compact and side channel secure discrete gaussian sampling. IACR Cryptology ePrint Archive, 2014,2014:591.
    [37] Oder T, Schneider T, Pöppelmann T, Güneysu T. Practical CCA2-secure and masked ring-LWE implementation. IACR Trans. on Cryptographic Hardware and Embedded Systems, 2018, 142-174.
    [38] Reparaz O, Sinha Roy S, Vercauteren F, Verbauwhede I. A masked ring-LWE implementation. In:Güneysu T, Handschuh H, eds. Proc. of the Cryptographic Hardware and Embedded Systems-CHES 2015. Berlin, Heidelberg:Springer-Verlag, 2015. 683-702.
    [39] Reparaz O, De Clercq R, Roy SS, Vercauteren F, Verbauwhede I. Additively homomorphic ring-LWE masking. In:Takagi T, ed. Proc. of the Post-quantum Cryptography. Cham:Springer Int'l Publishing, 2016. 233-244.
    [40] Barthe G, Belaïd S, Espitau T, Fouque P-A, Grégoire B, Rossi M, Tibouchi M. Masking the GLP lattice-based signature scheme at any order. In:Nielsen JB, Rijmen V. Proc. of the Advances in Cryptology-EUROCRYPT 2018. Cham:Springer Int'l Publishing, 2018. 354-384.
    [41] Espitau T, Fouque P-A, Gérard B, Tibouchi M. Loop-abort faults on lattice-based Fiat-Shamir and hash-and-sign signatures. In:Avanzi R, Heys H, eds. Proc. of the Selected Areas in Cryptography-SAC 2016. Cham:Springer Int'l Publishing, 2017. 140-158.
    [42] Howe J, Khalid A, Martinoli M, Regazzoni F, Oswald E. Fault attack countermeasures for error samplers in lattice-based cryptography. In:Proc. of the 2019 IEEE Int'l Symp. on Circuits and Systems (ISCAS). 2019. 1-5.
    [43] Khalid A, Howe J, Rafferty C, O'Neill M. Time-independent discrete Gaussian sampling for post-quantum cryptography. In:Proc. of the 2016 Int'l Conf. on Field-Programmable Technology (FPT). 2016. 241-244.
    [44] Micciancio D, Walter M. Gaussian sampling over the integers:Efficient, generic, constant-time. In:Katz J, Shacham H, eds. Proc. of the Advances in Cryptology-CRYPTO 2017. Cham:Springer Int'l Publishing, 2017. 455-485.
    [45] Karmakar A, Roy SS, Reparaz O, Vercauteren F, Verbauwhede I. Constant-time discrete Gaussian sampling. IEEE Trans. on Computers, 2018,67(11):1561-1571.
    [46] Karmakar A, Roy SS, Vercauteren F, Verbauwhede I. Pushing the speed limit of constant-time discrete Gaussian sampling:A case study on the falcon signature scheme. In:Proc. of the 56th Annual Design Automation Conf. 2019. Las Vegas:Association for Computing Machinery, 2019. 1-6.
    [47] Barthe G, Belaïd S, Espitau T, Fouque P-A, Rossi M, Tibouchi M. GALACTICS:Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited. In:Proc. of the 2019 ACM SIGSAC Conf. on Computer and Communications Security. London:Association for Computing Machinery, 2019. 2147-2164.
    [48] Walters M, Roy SS. Constant-time bch error-correcting code. IACR Cryptology ePrint Archive, 2019,2019:155.
    [49] McEliece RJ. A public-key cryptosystem based on algebraic. Coding THV, 1978,4244:114-116.
    [50] Overbeck R, Sendrier N. Code-based cryptography. In:Bernstein DJ, Buchmann J, Dahmen E, eds. Proc. of the Post-quantum Cryptography. Berlin, Heidelberg:Springer-Verlag, 2009. 95-145.
    [51] Huffman WC, Pless V. Fundamentals of ERror-correcting Codes. Cambridge:Cambridge University Press, 2010.
    [52] Von Maurich I, Güneysu T. Towards side-channel resistant implementations of QC-MDPC McEliece encryption on constrained devices. In:Mosca M, ed. Proc. of the Post-quantum Cryptography. Cham:Springer Int'l Publishing, 2014. 266-282.
    [53] Chen C, Eisenbarth T, Von Maurich I, Steinwandt R. Differential power analysis of a McEliece cryptosystem. In:Malkin T, Kolesnikov V, Lewko AB, Polychronakis M, eds. Proc. of the Applied Cryptography and Network Security. Cham:Springer Int'l Publishing, 2015. 538-556.
    [54] Chen C, Eisenbarth T, Von Maurich I, Steinwandt R. Masking large keys in hardware:A masked implementation of McEliece. In:Dunkelman O, Keliher L, eds. Proc. of the Selected Areas in Cryptography-SAC 2015. Cham:Springer Int'l Publishing, 2016. 293-309.
    [55] Chou T. QcBits:Constant-time small-key code-based cryptography. In:Gierlichs B, Poschmann AY, eds. Proc. of the Cryptographic Hardware and Embedded Systems-CHES 2016. Berlin, Heidelberg:Springer-Verlag, 2016. 280-300.
    [56] Rossi M, Hamburg M, Hutter M, Marson ME. A side-channel assisted cryptanalytic attack against QCbits. In:Fischer W, Homma N, eds. Proc. of the Cryptographic Hardware and Embedded Systems-CHES 2017. Cham:Springer Int'l Publishing, 2017. 3-23.
    [57] Sim B-Y, Kwon J, Choi KY, Cho J, Park A, Han D-G. Novel side-channel attacks on quasi-cyclic code-based cryptography. IACR Trans. on Cryptographic Hardware and Embedded Systems, 2019, 180-212.
    [58] Strenzke F, Tews E, Molter HG, Overbeck R, Shoufan A. Side channels in the McEliece PKC. In:Buchmann J, Ding J, eds. Proc. of the Post-quantum Cryptography. Berlin, Heidelberg:Springer-Verlag, 2008. 216-229.
    [59] Eaton E, Lequesne M, Parent A, Sendrier N. QC-MDPC:A timing attack and a CCA2 KEM. In:Lange T, Steinwandt R, eds. Proc. of the Post-quantum Cryptography. Cham:Springer Int'l Publishing, 2018. 47-76.
    [60] Paiva TB, Terada R. A timing attack on the HQC encryption scheme. In:Paterson KG, Stebila D, eds. Proc. of the Selected Areas in Cryptography-SAC 2019. Cham:Springer Int'l Publishing, 2020. 551-573.
    [61] Wafo-Tapa G, Bettaieb S, Bidoux L, Gaborit P. A practicable timing attack against HQC and its countermeasure. Cryptology ePrint Archive, Report, 2019/909, 2019.
    [62] Danner J, Kreuzer M. A fault attack on the niederreiter cryptosystem using binary irreducible GOPPA codes. arXiv:2002.01455[cs, math], 2020.
    [63] Petrvalsky M, Richmond T, Drutarovsky M, Cayrel P-L, Fischer V. Differential power analysis attack on the secure bit permutation in the McEliece cryptosystem. In:Proc. of the 26th Int'l Conf. Radioelektronika (RADIOELEKTRONIKA). 2016. 132-137.
    [64] Chen C, Eisenbarth T, Von Maurich I, Steinwandt R. Horizontal and vertical side channel analysis of a McEliece cryptosystem. IEEE Trans. on Information Forensics and Security, 2016,11(6):1093-1105.
    [65] Lamport L. Constructing digital signatures from a one-way function. Technical Report, CSL-98, SRI Int'l, 1979.
    [66] Buchmann J, Dahmen E, Klintsevich E, Okeya K, Vuillaume C. Merkle signatures with virtually unlimited signature capacity. In:Katz J, Yung M, eds. Proc. of the Applied Cryptography and Network Security. Berlin, Heidelberg:Springer-Verlag, 2007. 31-45.
    [67] Buchmann J, Dahmen E, Hülsing A. XMSS-a practical forward secure signature scheme based on minimal security assumptions. In:Yang B-Y, ed. Proc. of the Post-quantum Cryptography. Berlin, Heidelberg:Springer-Verlag, 2011. 117-129.
    [68] Genet A. Hardware attacks against hash-based cryptographic algorithms. Infoscience, 2017-08-18. (2017-08-18)[2020-05-19]. https://infoscience.epfl.ch/record/253317
    [69] Castelnovi L, Martinelli A, Prest T. Grafting trees:A fault attack against the sphincs framework. In:Lange T, Steinwandt R, eds. Proc. of the Post-quantum Cryptography. Cham:Springer Int'l Publishing, 2018. 165-184.
    [70] Genêt A, Kannwischer MJ, Pelletier H, McLauchlan A. Practical fault injection attacks on sphincs. IACR Cryptology ePrint Archive, 2018,2018:674.
    [71] Kannwischer MJ, Genêt A, Butin D, Krämer J, Buchmann J. Differential power analysis of XMSS and sphincs. In:Fan J, Gierlichs B, eds. Proc. of the Constructive Side-channel Analysis and Secure Design. Cham:Springer Int'l Publishing, 2018. 168-188.
    [72] Mozaffari-Kermani M, Azarderakhsh R, Aghaie A. Fault detection architectures for post-quantum cryptographic stateless hash-based secure signatures benchmarked on asic. ACM Trans. on Embedded Computing Systems, 2016,16(2):59:1-59:19.
    [73] Courtois NT. The security of hidden field equations (HFE). In:Naccache D, ed. Proc. of the Topics in Cryptology-CT-RSA 2001. Berlin, Heidelberg:Springer-Verlag, 2001. 266-281.
    [74] Kipnis A, Patarin J, Goubin L. Unbalanced oil and vinegar signature schemes. In:Stern J, ed. Proc. of the Advances in Cryptology-EUROCRYPT'99. Berlin, Heidelberg:Springer-Verlag, 1999. 206-222.
    [75] Matsumoto T, Imai H. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In:Barstow D, Brauer W, Brinch Hansen P, Gries D, Luckham D, Moler C, Pnueli A, Seegmüller G, Stoer J, Wirth N, Günther C G, eds. Proc. of the Advances in Cryptology-EUROCRYPT'88. Berlin, Heidelberg:Springer-Verlag, 1988. 419-453.
    [76] Patarin J. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88. In:Coppersmith D, ed. Proc. of the Advances in Cryptology-CRYPT0'95. Berlin, Heidelberg:Springer-Verlag, 1995. 248-261.
    [77] Patarin J. The oil and vinegar signature scheme. In:Proc. of the Dagstuhl Workshop on Cryptography. 1997.
    [78] Park A, Shim K-A, Koo N, Han D-G. Side-channel attacks on post-quantum signature schemes based on multivariate quadratic equations:Rainbow and UOV. IACR Trans. on Cryptographic Hardware and Embedded Systems, 2018, 500-523.
    [79] Krämer J, Loiero M. Fault attacks on UOV and rainbow. In:Polian I, Stöttinger M, eds. Proc. of the Constructive Side-channel Analysis and Secure Design. Cham:Springer Int'l Publishing, 2019. 193-214.
    [80] Shim K-A, Koo N. Algebraic fault analysis of UOV and rainbow with the leakage of random vinegar values. IEEE Trans. on Information Forensics and Security, 2020, 1.
    Cited by
Get Citation

吴伟彬,刘哲,杨昊,张吉鹏.后量子密码算法的侧信道攻击与防御综述.软件学报,2021,32(4):1165-1185

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 23,2020
  • Revised:August 14,2020
  • Online: January 22,2021
  • Published: April 06,2021
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063