Impact of randomization in VKO mechanisms on overall security level

E. K. Alekseev ; V. D. Nikolaev ; S. V. Smyshlyaev

Prikladnaâ diskretnaâ matematika, no. 4 (2021), pp. 77-93.

Résumé

Multiplier randomization techniques with hashing of the results is one of widely used (especially for semi-trusted environment) countermeasures against attacks on key agreement protocols in practice. This approach is used, for instance, in VKO mechanisms, which are used as building blocks for Russian cipher suites for main cryptographic protocols (including IPsec, TLS, CMS), standardized in Russia. As an important example, shared keys are produced with this technique in TLS 1.2 cipher suites, which are widespread in cryptographic software for citizens of Russia. In this paper, we consider overall security of procedures of shared key computation in the practically significant cases of implementation errors in computations on twisted Edwards elliptic curves and non-constant time of scalar multiplication operations.

Détail

Keywords: models and methods in information security, cryptographic protocols.

Bibliographie

[1] Diffie W., Hellman M., “New directions in cryptography”, IEEE Trans. Inform. Theory, 22:6 (1976), 644–654 | DOI | MR | Zbl

[2] Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, NIST Special Publication 800-56A Revision 3, 2018 | DOI

[3] Rescorla E., The Transport Layer Security (TLS) Protocol Version 1.3, 2018 https://tools.ietf.org/html/rfc8446 | Zbl

[4] GOST R 34.11-2012 “Information Technology. Cryptographic Data Security. Hash Function”, Standartinform, M., 2012 (in Russian)

[5] Popov V., Kurepkin I., Leontiev S., Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms, 2001 https://tools.ietf.org/html/rfc4357

[6] Recommendations for Standardization R 50.1.113–2016 “Information Technology. Cryptographic Data Security. Additional Cryptographic Algorithms for Digital Signature Algorithms and Hash Function”, Standartinform, M., 2016 (in Russian)

[7] GOST R 34.10-2012 “Information Technology. Cryptographic Data Security. Processes of Digital Signature Creation and Verification”, Standartinform, M., 2012 (in Russian)

[8] Smyshlyaev S., Alekseev E., Popov V., Leontiev S., Guidelines on the Cryptographic Algorithms to Accompany the Usage of Standards GOST R 34.10-2012 and GOST R 34.11-2012 https://tools.ietf.org/html/rfc7836

[9] Recommendations for Standardization R 1323565.1.020-2020 “Information Technology. Cryptographic Data Security. Usage of Russian Cryptographic Algorithms in TLS 1.2 Protocol”, Standartinform, M., 2020 (in Russian)

[10] Methodical Recommendations MR 26.2.002-2013 “Usage of GOST 28147-89, GOST R 34.10 and GOST R 34.11 in CMS”, Standartinform, M., 2013 (in Russian)

[11] Technical Specification TS 26.2.001-2015 “Usage of GOST 28147-89, GOST R 34.11-2012 and GOST R 34.10-2001 for Key Agreement in IKE and ISAKMP Protocols”, Standartinform, M., 2015 (in Russian)

[12] Recommendations for Standardization “Information technology. Cryptographic data security. Usage of Russian cryptographic algorithms in Internet key exchange protocol version 2 (IKEv2)”, proekt (in Russian)

[13] Alekseev E. K., Oshkin I. B., Popov V. O., et al., “On the prospects of using twisted Edwards elliptic curves with the GOST R 34.10-2012 standard and the key exchange algorithm based on it”, Problemy Informatsionnoy Bezopasnosti. Komp'yuternye Sistemy, 2014, no. 3, 60–66 (in Russian)

[14] Alekseev E. K., Nikolaev V. D., Smyshlyaev S. V., “On the security properties of Russian standardized elliptic curves”, Matem. Vopr. Kriptogr., 9:3 (2018), 5–32 | MR | Zbl

[15] SafeCurves: Choosing Safe Curves for Elliptic-Curve Cryptography, https://safecurves.cr.yp.to/index.html

[16] Lim C. H., Lee P. J., “A key recovery attack on discrete log-based schemes using a prime order subgroup”, LNCS, 1294, 1997, 249–263 | MR | Zbl

[17] Biehl I., Meyer B., Muller V., “Differential fault attacks on elliptic curve cryptosystems (extended abstract)”, LNCS, 1880, 2000, 131–146 | MR | Zbl

[18] Semaev I. A., Summation Polynomials and the Discrete Logarithm Problem on Elliptic Curves, Cryptology ePrint Archive: Report 2004/031, , 2004 https://eprint.iacr.org/2004/031.pdf

[19] Petit C., Quisquater J.-J., “On polynomial systems arising from a Weil descent”, LNCS, 7658, 2012, 451–466 | MR | Zbl

[20] Semaev I. A., New Algorithm for the Discrete Logarithm Problem on Elliptic Curves, Cryptology ePrint Archive: Report 2015/310, , 2015 https://eprint.iacr.org/2015/310.pdf | Zbl

[21] Courtois N., On Splitting a Point with Summation Polynomials in Binary Elliptic Curves, Cryptology ePrint Archive: Report 2016/003, https://eprint.iacr.org/2016/003.pdf

[22] Petit C., Kosters M., Messeng A., “Algebraic approaches for the elliptic curve discrete logarithm problem over prime fields”, LNCS, 9615, 2016, 3–18 | MR | Zbl

[23] Hankerson D., Menezes A. J., Vanstone S., Guide to Elliptic Curve Cryptography, Springer Verlag, N.Y., 2004 | MR | Zbl

[24] Schnorr C.-P., “Security of blind discrete log signatures against interactive attacks”, LNCS, 2229, 2001, 1–12 | Zbl

[25] Benhamouda F., Lepoint T., Loss J., et al., “On the (in)security of ROS'”, LNCS, 12696, 2021, 33–53 | MR | Zbl

[26] Koblitz N., Menezes A., “Critical perspectives on provable security: Fifteen years of “another look” papers”, Adv. Math. Commun., 13 (2019), 517–558 | DOI | MR | Zbl