Method for increasing the degree of protection of message encryption based on an algorithm for a constant component in time
DOI:
https://doi.org/10.34185/1562-9945-2-139-2022-01Keywords:
time attack, lattice, reverse module, constant time, algorithm, cryptosystemAbstract
Currently, asymmetric cryptosystems are used everywhere, in document management for cryptocurrencies, providing a high level of protection to end users, relying on the mathematical complexity of calculating a discrete algorithm. But, it is possible to make a cryptocurrency attack on the so-called ephemeral key, which is an auxiliary key when creating a signature. Recent works have shown examples of cryptocurrencies on the random number generator, processor cache, timing attacks. However, these attacks do not work when the numerical value of the bits is unknown. Also, recent work shows the main vulnerability in the case signature, namely the inverse module calculation algorithm that is vulnerable to timing attacks. The article considers the damage of cryptosystems such as DSA and ECDSA before the attack based on the analysis of the variable time of signing the message. A mathematical model has been developed to test this type of lesion, based on lattice attacks. It is shown that if there are enough signatures with the same signing time, it is possible to identify the presence of common bits of ephemeral keys, which will restore the sender's private key. It is proved that the cause of the lesion is the lack of execution of the operation of calculating the inverse module of the time variable, which provides ephemeral key data to the attacker. To solve this problem, an extended Euclidean algorithm for calculating the inverse module for a fixed time is proposed. In this paper, the advanced Euclidean algorithm for calculating the inverse module is improved, namely, its constant time execution is achieved, which prevents timed attacks.
References
Menezes A.J., Van Oorschot P.C., Vanstone S.A. Handbook of applied cryptography // Handbook of Applied Cryptography. 1996.
Ubaidullah M., Makki Q. A Review on Symmetric Key Encryption Techniques in Cryptography // Int. J. Comput. Appl. 2016. Vol. 147, № 10.
Elgamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Trans. Inf. Theory. 1985. Vol. 31, № 4.
Liu M., Chen J., Li H. Partially known nonces and fault injection attacks on SM2 signature algorithm // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2014. Vol. 8567.
Fouque P. A., Tibouchi M., Zapalowicz J.C. Recovering private keys generated with weak prngs // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2013. Vol. 8308 LNCS.
Boneh D., Venkatesan R. Hardness of computing the most significant bits of secret keys in diffie-hellman and related schemes // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1996. Vol. 1109.
Howgrave-Graham N.A., Smart N.P. Lattice Attacks on Digital Signature Schemes // Des. Codes, Cryptogr. 2001. Vol. 23, № 3.
Moghimi D. et al. TPM-FAIL: TPM meets timing and lattice attacks // Proceedings of the 29th USENIX Security Symposium. 2020.
Gallagher P.D., Romine C. FIPS PUB 186-4 Digital Signature Standard (DSS) // Encycl. Cryptogr. Secur. 2013. № July.
Nguyen P.Q., Nguyen P.Q. Public-key Cryptanalysis. 2008.
Kaliski B.S. The Montgomery Inverse and Its Applications // IEEE Trans. Comput. 1995. Vol. 44, № 8.
