ETSI TR 103 570-2017 CYBER Quantum-Safe Key Exchanges (V1 1 1).pdf

1、 ETSI TR 103 570 V1.1.1 (2017-10) CYBER; Quantum-Safe Key Exchanges TECHNICAL REPORT ETSI ETSI TR 103 570 V1.1.1 (2017-10) 2 Reference DTR/CYBER-QSC-007 Keywords algorithm, confidentiality, quantum cryptography, security ETSI 650 Route des Lucioles F-06921 Sophia Antipolis Cedex - FRANCE Tel.: +33 4

2、 92 94 42 00 Fax: +33 4 93 65 47 16 Siret N 348 623 562 00017 - NAF 742 C Association but non lucratif enregistre la Sous-Prfecture de Grasse (06) N 7803/88 Important notice The present document can be downloaded from: http:/www.etsi.org/standards-search The present document may be made available in

3、 electronic versions and/or in print. The content of any electronic and/or print versions of the present document shall not be modified without the prior written authorization of ETSI. In case of any existing or perceived difference in contents between such versions and/or in print, the only prevail

4、ing document is the print of the Portable Document Format (PDF) version kept on a specific network drive within ETSI Secretariat. Users of the present document should be aware that the document may be subject to revision or change of status. Information on the current status of this and other ETSI d

5、ocuments is available at https:/portal.etsi.org/TB/ETSIDeliverableStatus.aspx If you find errors in the present document, please send your comment to one of the following services: https:/portal.etsi.org/People/CommiteeSupportStaff.aspx Copyright Notification No part may be reproduced or utilized in

6、 any form or by any means, electronic or mechanical, including photocopying and microfilm except as authorized by written permission of ETSI. The content of the PDF version shall not be modified without the written authorization of ETSI. The copyright and the foregoing restriction extend to reproduc

7、tion in all media. ETSI 2017. All rights reserved. DECTTM, PLUGTESTSTM, UMTSTMand the ETSI logo are trademarks of ETSI registered for the benefit of its Members. 3GPPTM and LTE are trademarks of ETSI registered for the benefit of its Members and of the 3GPP Organizational Partners. oneM2M logo is pr

8、otected for the benefit of its Members. GSM and the GSM logo are trademarks registered and owned by the GSM Association. ETSI ETSI TR 103 570 V1.1.1 (2017-10) 3 Contents Intellectual Property Rights 6g3Foreword . 6g3Modal verbs terminology 6g31 Scope 7g32 References 7g32.1 Normative references . 7g3

9、2.2 Informative references 7g33 Abbreviations . 13g34 Quantum-safe key exchanges . 13g34.1 Introduction 13g34.2 Use cases 14g34.2.1 General comments 14g34.2.2 Network security. 14g34.2.3 Internet of Things . 14g34.3 Candidate primitives. 14g35 Implementation considerations . 15g35.1 Introduction 15g

10、35.2 Active security 15g35.2.1 Invalid key attacks 15g35.2.2 Key validation . 15g35.2.3 Performance impact 16g35.3 Side-channel protection 16g35.3.1 Side-channel vulnerabilities 16g35.3.2 Side-channel mitigations . 16g35.3.3 Performance impact 16g36 Learning with Errors 17g36.1 Introduction 17g36.2

11、LWE key exchange 17g36.2.1 Overview 17g36.2.2 Public parameters 18g36.2.3 Key generation 18g36.2.4 Key extraction . 18g36.2.5 Reconciliation . 19g36.3 Ring-LWE key exchange . 19g36.3.1 Overview 19g36.3.2 Public parameters 20g36.3.3 Key generation 21g36.3.4 Key extraction . 21g36.3.5 Reconciliation .

12、 21g36.4 Implementation considerations . 22g36.4.1 Active security 22g36.4.2 Side-channel protection 22g36.5 Parameter selection. 22g36.5.1 LWE proposed parameters 22g36.5.2 Ring-LWE proposed parameters . 23g36.5.3 Security estimates . 23g36.6 Performance . 23g36.6.1 Performance on a 64-bit processo

13、r . 23g36.6.2 Performance on a 32-bit embedded processor 24g36.6.3 Performance on 32-bit microcontrollers . 24g36.7 Summary 25g37 Supersingular isogenies 25g3ETSI ETSI TR 103 570 V1.1.1 (2017-10) 4 7.1 Introduction 25g37.2 SIDH key exchange 25g37.2.1 Overview 25g37.2.2 Public parameters 26g37.2.3 Ke

14、y generation 26g37.2.4 Key exchange 27g37.3 Implementation considerations . 27g37.3.1 Static key exchanges . 27g37.3.2 Side-channel protection 28g37.4 Parameter selection. 28g37.4.1 Proposed parameters . 28g37.4.2 Security estimates . 28g37.5 Performance . 28g37.5.1 Performance on a 64-bit desktop p

15、rocessor 28g37.5.2 Performance on a 64-bit embedded processor 29g37.5.3 Performance on a 32-bit embedded processor 29g37.6 Summary 29g38 Key exchanges from key transport mechanisms 29g38.1 General construction. 29g38.2 Niederreiter. 30g38.2.1 Introduction. 30g38.2.2 Niederreiter key exchange 30g38.2

16、.2.1 Overview . 30g38.2.2.2 Public parameters 31g38.2.2.3 Key generation 31g38.2.2.4 Decryption . 32g38.2.3 Implementation considerations . 32g38.2.3.1 Active attacks 32g38.2.3.2 Side-channel attacks 32g38.2.4 Parameter selection . 32g38.2.4.1 Proposed parameters . 32g38.2.4.2 Security estimates . 3

17、3g38.2.5 Performance 33g38.2.5.1 Performance on a 64-bit server processor . 33g38.2.5.2 Performance on a 64-bit desktop processor 33g38.2.5.3 Performance on an 8-bit microcontroller 33g38.2.6 Summary . 34g38.3 NTRU . 34g38.3.1 Introduction. 34g38.3.2 NTRU key exchange . 34g38.3.2.1 Overview . 34g38.

18、3.2.2 Public parameters 35g38.3.2.3 Decryption . 35g38.3.3 Implementation considerations . 35g38.3.3.1 Static key exchange . 35g38.3.3.2 Side channel attacks 35g38.3.4 Parameter selection . 36g38.3.4.1 Proposed parameters . 36g38.3.4.2 Security estimates . 36g38.3.5 Performance 36g38.3.5.1 Performan

19、ce on a 64-bit desktop processor 36g38.3.5.2 Performance on a 32-bit embedded processor. 36g38.3.5.3 Performance on a 32-bit microcontroller 37g38.3.6 Summary . 37g39 Conclusions 37g3Annex A: LWE design and security considerations 39g3A.1 LWE and Ring-LWE variants 39g3A.1.1 Rings 39g3A.1.2 Distribut

20、ions . 39g3ETSI ETSI TR 103 570 V1.1.1 (2017-10) 5 A.1.2.1 Discrete Gaussians 39g3A.1.2.2 Approximate Gaussians 39g3A.1.2.3 Small distributions 40g3A.1.2.4 Learning with Rounding . 40g3A.1.3 Varying g4 . 40g3A.1.4 Reconciliation mechanisms 41g3A.1.5 Key transport 41g3A.2 Security considerations. 42g

21、3A.2.1 Provable security 42g3A.2.2 Passive security 42g3A.2.3 Active security 43g3Annex B: SIDH background and security considerations 44g3B.1 Mathematical background 44g3B.1.1 Isogenies . 44g3B.1.2 Parameter generation 44g3B.1.3 Public key compression 45g3B.2 Security. 45g3B.2.1 Provable security 4

22、5g3B.2.2 Passive security 46g3B.2.3 Active security 46g3Annex C: Open Quantum-Safe benchmarks . 48g3C.1 Open Quantum-Safe . 48g3C.2 Benchmarks 48g3C.2.1 Performance on a 64-bit desktop processor 48g3C.2.2 Performance on a 64-bit laptop processor 49g3C.2.3 Performance on a 32-bit embedded processor 4

23、9g3C.3 Discussion 49g3History 50g3ETSI ETSI TR 103 570 V1.1.1 (2017-10) 6 Intellectual Property Rights Essential patents IPRs essential or potentially essential to the present document may have been declared to ETSI. The information pertaining to these essential IPRs, if any, is publicly available f

24、or ETSI members and non-members, and can be found in ETSI SR 000 314: “Intellectual Property Rights (IPRs); Essential, or potentially Essential, IPRs notified to ETSI in respect of ETSI standards“, which is available from the ETSI Secretariat. Latest updates are available on the ETSI Web server (htt

25、ps:/ipr.etsi.org/). Pursuant to the ETSI IPR Policy, no investigation, including IPR searches, has been carried out by ETSI. No guarantee can be given as to the existence of other IPRs not referenced in ETSI SR 000 314 (or the updates on the ETSI Web server) which are, or may be, or may become, esse

26、ntial to the present document. Trademarks The present document may include trademarks and/or tradenames which are asserted and/or registered by their owners. ETSI claims no ownership of these except for any which are indicated as being the property of ETSI, and conveys no right to use or reproduce a

27、ny trademark and/or tradename. Mention of those trademarks in the present document does not constitute an endorsement by ETSI of products, services or organizations associated with those trademarks. Foreword This Technical Report (TR) has been produced by ETSI Technical Committee Cyber Security (CYB

28、ER). Modal verbs terminology In the present document “should“, “should not“, “may“, “need not“, “will“, “will not“, “can“ and “cannot“ are to be interpreted as described in clause 3.2 of the ETSI Drafting Rules (Verbal forms for the expression of provisions). “must“ and “must not“ are NOT allowed in

29、 ETSI deliverables except when used in direct citation. ETSI ETSI TR 103 570 V1.1.1 (2017-10) 7 1 Scope The present document compares a selection of proposals for quantum-safe key exchanges taken from the academic literature. In particular, it includes key exchanges based on the Learning with Errors

30、 (LWE), Ring-LWE and Supersingular Isogeny Diffie-Hellman (SIDH) problems, as well as key exchanges constructed from the Niederreiter and NTRU key transport schemes. The present document gives an overview of each key exchange, lists proposed parameters and gives software performance estimates on a r

31、ange of processors. It also discusses various security and implementation considerations such as active attacks and side-channel vulnerabilities. 2 References 2.1 Normative references Normative references are not applicable in the present document. 2.2 Informative references References are either sp

32、ecific (identified by date of publication and/or edition number or version number) or non-specific. For specific references, only the cited version applies. For non-specific references, the latest version of the referenced document (including any amendments) applies. NOTE: While any hyperlinks inclu

33、ded in this clause were valid at the time of publication ETSI cannot guarantee their long term validity. The following referenced documents are not necessary for the application of the present document but they assist the user with regard to a particular subject area. user with regard to a particula

34、r subject area. i.1 ETSI QKD GS 002: “Quantum Key Distribution (QKD); Use cases“. i.2 ETSI GR QSC 001: “Quantum-Safe Cryptography (QSC); Quantum-safe algorithmic framework“. i.3 IETF draft-ietf-tls-tls13-19: “The Transport Layer Security (TLS) protocol version 1.3“, 10 March 2017. i.4 IETF RFC 7296:

35、 “Internet Key Exchange protocol version 2 (IKEv2)“, October 2014. i.5 ETSI GR QSC 003: “Quantum Safe Cryptography; Case Studies and Deployment Scenarios“. i.6 I. Biehl, B. Meyer and V. Mller: “Differential fault attacks on elliptic curve cryptosystems“ in CRYPTO, 2000. i.7 E. Fujisaki and T. Okamot

36、o: “Secure integration of asymmetric and symmetric encryption schemes“ in CRYPTO, 1999. i.8 E. E. Targhi and D. Unruh: “Post-quantum security of the Fujisaki-Okamoto and OAEP transforms“ in TCC, 2016. i.9 P. Kocher: “Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems“ in

37、 CRYPTO, 1996. i.10 P. Kocher, J. Jaffe and B. Jun: “Differential power analysis“ in CRYPTO, 1999. i.11 D. Brumley and D. Boneh: “Remote timing attacks are practical“ Computer Networks, vol. 48, no. 5, pp. 701-716, 2005. ETSI ETSI TR 103 570 V1.1.1 (2017-10) 8 i.12 J. Groschdl, E. Oswald, D. Page an

38、d M. Tunstall: “Side-channel analysis of cryptographic software via early-terminating multiplications“ in ISIC, 2009. i.13 S. Mangard, E. Oswald and T. Popp: “Power analysis attacks: Revealing the secrets of smart cards“, New York: Springer Science J. Pipher, J. M. Schanck, J. H. Silverman, W. Whyte

39、 and Z. Zhang: “Choosing parameters for NTRUEncrypt“ in CT-RSA, 2017. i.80 . Jaulmes and A. Joux: “A chosen-ciphertext attack against NTRU“ in CRYPTO, 2000. i.81 N. Howgrave-Graham, P. Nguyen, D. Pointcheval, J. Proos, J. Silverman and A. Singer: “The impact of decryption failures on the security of

40、 NTRU encryption“ in CRYPTO, 2003. i.82 N. Gama and P. Q. Nguyen: “New chosen-ciphertext attacks on NTRU“ in PKC, 2007. i.83 A. Hlsing, J. Rijnveld, J. Schanck and P. Schwabe: “High-speed key encapsulation from NTRU“, IACR ePrint Archive 2017/667, 2017. i.84 N. Howgrave-Graham, J. Silverman, A. Sing

41、er and W. Whyte: “NAEP: Provable security in the presence of decryption failures“, IACR ePrint Archive 2003/172, 2003. i.85 M. Stam: “A key encapsulation mechanism for NTRU“ in Cryptography and Coding, 2005. i.86 J. H. Silverman and W. Whyte: “Timing attacks on NTRUEncrypt via variation in the numbe

42、r of hash calls“ in CT-RSA, 2007. i.87 A. Atici, L. Batina, B. Grierlichs and I. Verbauwhede: “Power analysis on NTRU implementations for RFIDs: First results“ in RFIDSec, 2008. i.88 A. Wang, X. Zheng and Z. Wang: “Power analysis attacks and countermeasures on NTRU-based wireless body area networks“

43、, KSII Transactions on Internet and Information Systems, vol. 7, no. 5, pp. 1094-1107, 2013. i.89 X. Zheng, A. Wang and W. Wei: “First-order collision attack on protected NTRU cryptosystem“, Microprocessors and Microsystems, vol. 37, pp. 601-609, 2013. i.90 N. Howgrave-Graham: “A hybrid lattice-redu

44、ction and meet-in-the-middle attack against NTRU“ in CRYPTO, 2007. i.91 O. M. Guillen, T. Pppelmann, J. M. B. Mera, E. F. Bongenaar, G. Sigl and J. Sepulveda: “Towards post-quantum security for IoT endpoints with NTRU“ in DATE, 2017. i.92 J. H. Cheon, J. Jeong and C. Lee: “An algorithm for NTRU prob

45、lems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero“ in ANTS-XII, 2016. i.93 M. Albrecht, S. Bai and L. Ducas: “A subfield lattice attack on overstretched NTRU assumptions“ in CRYPTO, 2016. i.94 D. J. Bernstein, C. Chuengsatiansup, T. Lange and C. van Vredendaal: “

46、NTRU Prime“, IACR ePrint Archive 2016/461, 2016. i.95 P. Kirchner and P.-A. Fouque: “Comparison between subfield and straightforward attacks on NTRU“, IACR ePrint Archive 2016/717, 2016. i.96 B. Applebaum, D. Cash, C. Peikert and A. Sahai: “Fast cryptographic primitives and circular-secure encryptio

47、n based on hard learning problems“ in CRYPTO, 2009. i.97 L. Ducas and A. Durmus: “Ring-LWE in polynomial rings“ in PKC, 2012. i.98 C. Peikert: “How (not) to instantiate Ring-LWE“ in SCN, 2016. i.99 J. H. Cheon, K. Han, J. Kim, C. Lee and Y. Son: “A practical post-quantum public-key cryptosystem base

48、d on spLWE“ in ICISC, 2016. i.100 L. Ducas, V. Lyubashevsky and T. Prest: “Efficient identity-based encryption over NTRU lattices“ in ASIACRYPT, 2014. i.101 J. Fan and F. Vercauteren: “Somewhat practical fully homomorphic encryption“, IACR ePrint Archive 2012/144, 2012. i.102 D. Micciancio and C. Pe

49、ikert: “Hardness of SIS and LWE with small parameters“ in CRYPTO, 2013. ETSI ETSI TR 103 570 V1.1.1 (2017-10) 12 i.103 J. Buchmann, E. Gopfert, R. Player and T. Wunderer: “On the hardness of LWE with binary error: Revisiting the hybrid lattice-reduction and meet-in-the-middle attack“ in AFRICACRYPT, 2016. i.104 M. Albrecht: “On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL“ in EUROCRYPT, 2017. i.105 A. Banerjee, C. Peikert and A. Rosen: “Pseudorandom func