Security analysis of kleptographic algorithms

Abstract

Kleptography is the study of stealing the secure data secretly and subliminally. It is the subdivision of crypto-virology. The concept of inserting backdoors was introduced two decades ago by Young and Yung but still it is a serious threat for modern cryptography. The attacker uses asymmetric cryptographic techniques to build the backdoor and later uses his own private key to reconstruct the secret key of the user. Different researches proved that exploiting implementation weakness of cryptographic algorithm needs less effort as compared to attacking its mathematical structure. The SETUP (Secretly Embedded Trapdoor with Universal Protection) attack modifies the standard methods of generating public and private key pairs in such a way that the public information is meaningful for the attacker. Also, calculation of private key of the user in polynomial time is no more a hard problem for the attacker. The information leakage using backdoor does not require separate communication channel for the transmission of secret data. In present days, cryptography is using against the security of cryptosystems instead of protecting it. The user is not able to distinguish the output of an honest or a malicious cryptosystem. This research presented the brief description of the history of backdoor attacks in practical cryptographic systems. Elliptic curve cryptographic concepts are discussed in this research. Then the term Kleptography was introduced, followed by the definition of weak, regular and strong SETUP attacks. It also presents the proposed kleptographic attack strategy on a cryptographic algorithm based on elliptic curves algorithms i.e. Edwards-curve Digital Signature Algorithm, Elliptic curve Diffie-Hellman key exchange scheme, Elliptic curve Digital Signature Algorithm, Elliptic curve Integrated Encryption Scheme, Elliptic curve Menezes-Qu-Vanstone and Elliptic curve Qu-Vanstone implicit certificate scheme. In order to increase the security, the complexity of cryptographic algorithm’s implementation is also enhanced. This makes extremely hard for the user to detect such malicious codes especially when they are introduced, in the code, very innocently. Finally, the strategy of running time analysis is presented in order to detect the presence of such kinds of backdoor attacks. The experimental results shows the successful detection of malicious code in an elliptic curve based protocols. The future work concludes the research work.