Smart Cards, IPv6 Packets, and the Future of Post-Quantum Security

Table of Links

Abstract and 1 Introduction

2. Scenario and Requirements

3. History and Related Work

4. Concept of Cramer-Shoup with Elliptic Curve and 4.1 Prerequisite

   4.2 Public Key Generation by Receiver

   4.3 Encryption by Sender

   4.4 Decryption by Receiver

5. Evaluation and 5.1 Proof of Correctness

   5.2 Preliminary Performance Comparison

6. Proof: Secure against adaptive-chosen ciphertext attacks

   6.1 DDH Assumption and 6.2 CCA Assumption

   6.3 IND-CCA 1 - non-adaptive Security

   6.4 IND-CCA 2 - adaptive Security (Validity Checking Failure)

7. Security discussion: Post-Quantum Cryptography

8. Summary, References, and Authors

7 Security discussion: Post-Quantum Cryptography

Peter Shor developed a polynomial time quantum computer algorithm to solve integer factorization problem and DLP [58]. Cryptographic schemes based on pure EC might be not be secure for future, due to the rapid development of quantum technology and data storing possibilities. What cannot be cracked today can be stored for later decryption [59]. urrently, a quantum computer needs for breaking an ECC with 256 bit keys (128 bit security level) about 2330 qbits and 126 billion Toffoli gates [60]. This exceeds any current quantum computing approach of currently less than 400 Qbits and appears to be more than a decade in the future. According to NIST and the German BSI, a key length of 256 bit in ECC provide security beyond the year 2030 [61,62]. Additionally, our approach can be made polymorphic in the sense of a variable usage of the underlying EC and the flexible choice of the starting points. This further complicates a cryptographic analysis and enlarges the possible space of cryptograms.

These isogeny approaches are promising and based on complex problems, which are also resistant in the post-quantum computing era, like SIDE and SIKE. Although, these new mathematical construction is not the mainstream research for post-quantum cryptography, it offers promising possibilities. The key sizes are significantly smaller in relation to other schemes. With key-compression techniques, the transmit information with coefficients defining the EC and two EC points is < 517 Bytes [54]. So this fits easily in the payload of one IPv4 or v6 network packet. It is especially favorable for smart cards and low bandwidth communication as stated in ISO/IEC 7816-8.

8 Summary

Although there are not yet sufficiently powerful quantum computers to break the publickey methods currently in use, this could be the case in the distant future. Therefore, research is already being conducted on secure schemes in many different aspects. Our approach follows the transformation to EC and supersingular isgoeny EC like DH over ECDH to SIDH and SIKE. This paper adapt and enhances the cryptographic strong procedure of Cramer-Soup to the base of EC. In relation to other suggested crypto system, we focus on Lightweight Cryptography. The main advantage of our system is the comparable higher security than RSA or other approaches by small key size and linear key scaling. So, our schema can be used in mobile systems with limited bandwidth or less capacity like smart cards or RFID. Our public-key encryption schema is provable secure IND-CCA 2 without malleability to prevent attacks like from Bleichenbacher from the beginning. In the future, we will adapt our encryption system to supersingular isogeny EC to foster resist quantum computing capabilities.

References

1. Bleichenbacher, D.: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. In: Proceedings of the International Cryptology Conference on Advances in Cryptology (CRYPTO). pp. 1–12. Springer, London, UK (1998), http://dl.acm.org/citation.cfm?id=646763.706320

2. Bellare, M., Rogaway, P.: Optimal Asymmetric Encryption How to Encrypt with RSA. Advances in Cryptology - Eurocrypt (1994)

3. Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP Is Secure under the RSA Assumption.Journal of Cryptology 17(2), 81–104 (Mar 2004

4. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557–594 (Jul 2004)

5. Paillier, P., Villar, J.L.: Trading One-Wayness Against Chosen-Ciphertext Security in Factoring-Based Encryption. In: Lai, X., Chen, K. (eds.) Advances in Cryptology – ASIACRYPT. pp. 252–266. Springer Berlin Heidelberg, Berlin, Heidelberg (2006)

6. Brown, D.R.L.: What hashes make rsa-oaep secure? (2007)

7. B¨ock, H., Somorovsky, J., Young, C.: Return Of Bleichenbacher’s Oracle Threat (ROBOT). In: USENIX Security Symposium. pp. 817–849. USENIX Association, Baltimore, MD (2018), https://www.usenix.org/conference/usenixsecurity18/presentation/bock

8. Manger, J.: A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0. In: International Association for Cryptologic Research (IACR), Proceedings of the International Cryptology Conference on Advances in Cryptology (CRYPTO). vol. 2139, pp. 260–274. Springer (2001), lecture Notes in Computer Science

9. Ronen, E., Gillham, R., Genkin, D., Shamir, A., Wong, D., Yarom, Y.: The 9 Lives of Bleichenbacher’s CAT:New Cache ATtacks on TLS Implementations. Real World Crypto 2020 and IEEE Symposium on Security and Privacy (2019)

10. Heiland, E., Hillmann, P.: (B)LOCKBOX – Secure Software Architecture with Blockchain Verification. The European Multidisciplinary Society for Modelling and Simulation Technology (EUROSIS) (2022)

11. Cramer, R., Shoup, V.: Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack. Aarhus University, New York University (2003)

12. Hillmann, P., Kn¨upfer, M., Guggemos, T., Streit, K.: CAKE: An Efficient Group Key Management for Dynamic Groups. INFOCOMP Journal of Computer Science 18(2) (2019)

13. Shannon, C.E.: A Mathematical Theory of Cryptography. Communication Theory of Secrecy Systems (1946)

14. Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. Springer, Advances in Cryptology (CRYPTO) (1998)

15. Bernstein, D.J.: The libpqcryptosoftware library forpost-quantum cryptography (2018), https://cryp.to/talks/2018.05.09/slides-djb-20180509-libpqcrypto-4x3.pdf

16. Pfitzmann, A.: Security in IT Networks: Multilateral Security in Distributed and by Distributed Systems (2006)

17. Merkle, R.C.: Secure Communications Over Insecure Channels. In: Communications of the ACM. 21. pp. 294–299 (1978)

18. Communications Electronics Security Group: The Possibility of Secure Non-Secret Digital Encryption. Research Report No. 3006 (1970), https://www.gchq.gov.uk/sites/default/files/documentfiles/CESG_Research_Report_No_3006_0.pdf

19. Diffie, W., Hellmann, M.E.: New Directions in Cryptography. IEEE Transactions on Information Theory (1976)

20. Rivest, R.L., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM (1978)

21. Merkle, R., Hellman, M.: Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory 24(5), 525–530 (1978)

22. Shamir, A.: A polynomial-time algorithm for breaking the basic merkle - hellman cryptosystem. IEEE Transactions on Information Theory 30(5), 699–704 (1984)

23. McEliece, R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory. Deep Space Network Progress Report pp. 114–116 (1978)

24. Rabin, M.O.: Digitalized signatures and public-key functions as intractable as factorization. MIT-LCSTR 212, MIT Laboratory for Computer Science (1979)

25. Chor, B., Rivest, R.L.: A Knapsack Type Public Key CryptosystemBased On Arithmetic in FiniteFields. Advancesin Cryptology: Proceedings of CRYPTO, Springer pp. 54–65 (1984)

26. ElGamal, T.: A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory pp. 469–472 (1985)

27. Hoffstein, J., Pipher, J., Silverman, J.: NTRU: A Ring-Based Public Key Cryptosystem. International Algorithmic Number Theory Symposium (1998)

28. Paillier, P.: Cryptosystems Based on Composite Residuosity (1999), Ecole Nationale Sup´erieure des ´ T´el´ecommunication

29. National Institute of Standards and Technology: NIST Announces First Four QuantumResistant Cryptographic Algorithms (2022), https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

30. The European Union Agency for Cybersecurity (ENISA): Post-Quantum Cryptography - Integration study (2022), https://www.enisa.europa.eu/publications/post-quantum-cryptography-integration-study/@@download/fullReport

31. Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Smith-Tone, D., Liu, Y.K.: Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. NISTIR 8413 (2022)

32. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. ACM symposium on Theory of computing (STOC) (2005)

33. Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., Stehle, D.: CRYSTALS-Kyber. IEEE European Symposium on Security and Privacy (EuroS&P) (2018), https://pq-crystals.org/kyber/resources.shtml

34. Dubrova, E., Ngo, K., G¨artner, J.: Breaking a fifth-order masked implementation of crystals-kyber by copy-paste. Cryptology ePrint Archive, Paper 2022/1713 (2022), https://eprint.iacr.org/2022/1713, https://eprint.iacr.org/2022/1713

35. Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Paper 2006/291 (2006), https://eprint.iacr.org/2006/291, https://eprint.iacr.org/2006/291

36. Rostovtsev, A., Stolbunov, A.: Public-Key Cryptosystem based on Isogenies (2006)

37. Feo, L.D., Jao, D., Plut, J.: Towards Quantum-Resistant Cryptosystems from Supersingulare Elliptic Curve Isogenies. PQCrypto, Springer (2011)

38. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. Cryptology ePrint Archive (2022), https://eprint.iacr.org/2022/975, https://eprint.iacr.org/2022/975

39. Azarderakhsh, R., Koziel, B., Campagna, M., LaMacchia, B., Costello, C., Longa, P., Feo, L.D., Naehrig, M., Hess, B., Renes, J., Jalali, R.A., Soukharev, V., Jao, D., Urbanik, D.: Supersingular Isogeny Key Encapsulation. NIST PQCrypto candidates (2018), https://csrc.nist.gov/CSRC/media/Presentations/SIKE/images-media/SIKE-April2018.pdf

40. Steven D. Galbraith, Christophe Petit, Barak Shani, Yan Bo Ti: On the security of supersingular isogeny cryptosystems. IACR Cryptol. ePrint Arch. (2016)

41. National Institute of Standards and Technology: NIST Issues First Call for Lightweight Cryptography to Protect Small Electronics (2018), https://www.nist.gov/news-events/news/2018/04/nist-issues-first-call-lightweight-cryptography-protect-small-electronics

42. Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against-adaptive chosen ciphertext attack. Advaces in Cryptology (Crypto), LNCS Springer 1462, 13–25 (1998)

43. Zhu, H.: A Practical Elliptic Curve Public Key Encryption Scheme Provably Secure Against Adaptive Chosen-message Attack. Cryptology ePrint Archive, Paper 2003/087 (2003), https://eprint.iacr.org/2003/087, https://eprint.iacr.org/2003/087

44. Giry, D.: Cryptographic Key Length Recommendation. BlueKrypt (2023), https://www.keylength.com/en/4/

45. Miller, V.S.: Use of elliptic curves in cryptography. Lecture Notes in Computer Science 218, 417–426 (1986)

46. Koblitz, N.: Elliptic curve cryptosystems. Mathemathic Computation 48, 203–209 (1987)

47. Seet, M.Z.: Elliptic Curve Cryptography: Improving the Pollard-Rho Algorithm. Ph.D. thesis (2007)

48. Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: The Keccak reference (2011)

49. Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The Skein Hash Function Family (2010)

50. Brown, D.R.L.: SEC 2: Recommended Elliptic Curve Domain Parameters. Standards for efficient Cryptography 2 (SEC 2), Certicom Research (2010), http://www.secg.org/sec2-v2.pdf

51. Langley, A., Hamburg, M., Turner, S.: Elliptic Curves for Security (RFC 7748). Internet Research Task Force (IRTF) (2016), https://www.ietf.org/rfc/rfc7748.txt

52. Bernstein, D.J., Lange, T.: SafeCurves: choosing safe curves for elliptic-curve cryptography. Rigidity (2013), http://safecurves.cr.yp.to/rigid.html

53. Roy, M., Deb, N., Kumar, A.J.: Point Generation And Base Point Selection In ECC: An Overview. International Journal of Advanced Research in Computer and Communication Engineering (IJARCCE) 3, 6711–6713 (2014)

54. Costello, C., Jao, D., Longa, P., Naehrig, M., Renes, J., Urbanik, D.: Efficient compression of SIDH public keys. Cryptology ePrint Archive: Report 2016/963 (2016)

55. Hastad, J.: A Provably Secure Public-Key Cryptosystem. Seminars in Theoretical Computer Science at NADA, KTH (2003)

56. D., S., Galbraith, Petit, C., Shani, B., Ti, Y.B.: On the security of supersingular isogeny cryptosystem. IACR (2016)

57. Chen, R.: Cramer-Shoup Encryption. University of Wollongong (2014)

58. Peter Wiliston Shor: Algorithms for quantum computation: Discrete logarithms and factoring. Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press pp. 124–134 (1994)

59. Burr, T.: Shhh . . . NSA’s Utah Data Center may be open already (2013), https://archive.sltrib.com/article.php?id=56915018&itype=CMSID

60. Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.: Quantum resource estimates for computing elliptic curve discrete logarithms. Quantum Physics (2017)

61. National Institute of Standards and Technology: Recommendation forKey Managem. NIST Special Publication 8 (2020)

62. Federal Office for Information Security: Cryptographic Mechanisms:Recommendations and Key Length. BSI Technical Guide, BSI TR-02102 (2023), https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf?__blob= publicationFile

63. Jao, D., Feo, L.D.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: International Workshop on Post Quantum Cryptography. pp. 19–34 (2011)

64. Feo, L.D., Jao, D., Plˆut, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, pp. 209–247 (2014)

65. Velu, J.: Isogenies entre courbes elliptiques. Comptesrendus de la Academie des Sciences (1971)

66. Montgomery, P.L.: Speeding the pollard and elliptic curve methods of factorization. Mathematics of computation 48, 243–264 (1987)

67. Biasse, J.F., Jao, D., Sankar, A.: A quantum algorithm for computing isogenies between supersingular elliptic curves. CACR (2014)

68. Tani, S.: Claw finding algorithms using quantum walk. Theoretical Computer Science (2009)

69. Adj, G., Cervantes-Vzquez, D., Chi-Domnguez, J.J., Menezes, A., Rodrguez-Henrquez, F.: On the cost of computing isogenies between supersingular elliptic curves. Cryptology ePrint Archive, Report 313 (2018)

Authors

Peter Hillmann is a postdoctoral researcher and scientific in computer science. He received a M.Sc. in Information-System-Technology from Dresden University of Technology (2011) and a Dr. rer. nat. (Ph.D. in science) degree in Computer Science (2018) from the Universit¨at der Bundeswehr M¨unchen. He provides expert reports for national and international organizations. His research interests include system and network security with focus on cryptography and IP geolocation as well as middleware technologies and enterprise architecture.