Paper 2016/644

How to Backdoor Diffie-Hellman

David Wong

Abstract

Lately, several backdoors in cryptographic constructions, protocols and implementations have been surfacing in the wild: Dual-EC in RSA's B-Safe product, a modified Dual-EC in Juniper's operating system ScreenOS and a non-prime modulus in the open-source tool socat. Many papers have already discussed the fragility of cryptographic constructions not using nothing-up-my-sleeve numbers, as well as how such numbers can be safely picked. However, the question of how to introduce a backdoor in an already secure, safe and easy to audit implementation has so far rarely been researched (in the public). We present two ways of building a Nobody-But-Us (NOBUS) Diffie-Hellman backdoor: a composite modulus with a hidden subgroup (CMHS) and a composite modulus with a smooth order (CMSO). We then explain how we were able to subtly implement and exploit it in a local copy of an open source library using the TLS protocol.