Enhancing Kleptographic Backdoors in Hash-Based Deterministic Random Bit Generators

Document Type : Research Article

Authors

Faculty of Computer Science and Engineering, Shahid Beheshti University, Tehran, Iran.

10.22042/isecure.2026.241269
Abstract
Deterministic Random Bit Generators (DRBGs) are essential for cryptographic security but remain vulnerable to covert kleptographic attacks that implant backdoors to leak sensitive information. Despite being known for two decades, as demonstrated by incidents such as the Snowden revelations and Dual-EC, these attacks persist in modern protocols, including TLS and post-quantum systems. This paper introduces a novel kleptographic backdoor for hash-based DRBGs, utilising a dual-phase design: secret information is split across two complementary phases, each requiring the other for recovery. This design significantly increases the overall complexity compared with conventional methods. To enhance indistinguishability, we integrate randomness derived from the discrete logarithm problem, ensuring statistical conformity. By leveraging ElGamal encryption to ensure compatibility with our approach, we develop a highly covert backdoor. Rigorous validation via the NIST Statistical Test Suite (STS) and neural network-based anomaly detection confirms the backdoor passes all NIST tests while evading machine learning detection, maintaining statistical integrity and structural consistency. 

Keywords


[1] Adam Young and Moti Yung. Kleptography: Using cryptography against cryptography. In Advances in Cryptology—EUROCRYPT’97: International Conference on the Theory and Application of Cryptographic Techniques Konstanz, Germany, May 11–15, 1997 Proceedings 16, pages 62–74, 1997.
[2] Daniel J Bernstein, Tanja Lange, and Ruben Niederhagen. Dual ec: A standardized back door. pages 256–281. Springer, 2016.
[3] Phillip Rogaway. The moral character of cryptographic work. Cryptology ePrint Archive, 2015.
[4] Adam Janovsky, Jan Krhovjak, and Vashek Matyas. Bringing kleptography to real-world tls. In Information Security Theory and Practice: 12th IFIP WG 11.2 International Conference, WISTP 2018, Brussels, Belgium, December 10– 11, 2018, Revised Selected Papers 12, pages 15-27, 2019.
[5] Prasanna Ravi, Shivam Bhasin, Anupam Chattopadhyay, Aikata Aikata, and Sujoy Sinha Roy. Backdooring post-quantum cryptography: Kleptographic attacks on lattice-based kems. In Proceedings of the Great Lakes Symposium on VLSI 2024, pages 216–221, 2024.
[6] Antoine Joux, Julian Loss, and Benedikt Wagner. Kleptographic attacks against implicit rejection. 2024.
[7] Darren Hurley-Smith and Julio HernandezCastro. Certifiably biased: An in-depth analysis of a common criteria eal4+ certified trng. IEEE Transactions on Information Forensics and Security, 13(4):1031–1041, 2017.
[8] Felix Brockherde, Leslie Vogt, Li Li, Mark E Tuckerman, Kieron Burke, and Klaus-Robert Mu¨ller. Bypassing the kohn-sham equations with machine learning. Nature communications, 8(1):872, 2017.
[9] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25, 2012.
[10] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303–314, 1989.
[11] Yulong Feng and Lingyi Hao. Testing randomness using artificial neural network. IEEE Access, 8:163685–163693, 2020.
[12] Fenglei Fan and Ge Wang. Learning from pseudo-randomness with an artificial neural network–does god play pseudo-dice? IEEE Access, 6:22987–22992, 2018.
[13] Cai Li, Jianguo Zhang, Luxiao Sang, Lishuang Gong, Longsheng Wang, Anbang Wang, and Yuncai Wang. Deep learning-based security verification for a random number generator using white chaos. Entropy, 22(10), 2020.
[14] Nhan Duy Truong, Jing Yan Haw, Syed Muhamad Assad, Ping Koy Lam, and Omid Kavehei. Machine learning cryptanalysis of a quantum random number generator. IEEE Transactions on Information Forensics and Security, 14(2):403–414, 2019.
[15] Elaine B Barker, John Michael Kelsey, et al. Recommendation for random number generation using deterministic random bit generators (revised). US Department of Commerce, Technology Administration, National Institute of Standards and Technology, Computer Security Division, Information Technology Laboratory, Washington, DC, USA, 2007.
[16] Joan Boyar. Inferring sequences produced by a linear congruential generator missing low-order bits. Journal of Cryptology, 1(3):177–184, 1989.
[17] Adam Young and Moti Yung. The dark side of “black-box” cryptography or: Should we trust capstone? In Advances in Cryptology—CRYPTO’96: 16th Annual International Cryptology Conference Santa Barbara, California, USA August 18–22, 1996 Proceedings 16, pages 89–103. Springer, 1996.
[18] Rosario Gennaro. An improved pseudo-random generator based on the discrete logarithm problem. Journal of Cryptology, 18:91–110, 2005.
[19] Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4):469–472, 1985.
[20] Lawrence E Bassham, Andrew L Rukhin, Juan Soto, James R Nechvatal, Miles E Smid, Stefan D Leigh, M Levenson, M Vangel, Nathanael A Heckert, and D L Banks. A statistical test suite for random and pseudorandom number generators for cryptographic applications. 2010.

Articles in Press, Accepted Manuscript
Available Online from 22 February 2026