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 a new way of building a Nobody-But-Us (NOBUS) Diffie-Hellman backdoor by using a composite modulus with a smooth order. We then explain how we were able to implement a proof of concept with Socat and OpenSSL in order to exploit our backdoor on the TLS protocol. Update (December 2016): Dorey et al. have pointed an attack on our first contribution, as well as an improvement for the exploitation of our second contribution. This work has been updated to reflect these advances.

Note: paper https://eprint.iacr.org/2016/999 has broken a section of this paper, and improved another one.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Diffie-HellmanEphemeralDHENOBUSBackdoorDiscrete LogarithmSmall Subgroup AttackPohlig-HellmanPollard RhoFactorizationPollard's p-1ECMDual-ECJunipersocat
Contact author(s)
moi @ davidwong fr
History
2016-12-27: revised
2016-06-24: received
See all versions
Short URL
https://ia.cr/2016/644
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/644,
      author = {David Wong},
      title = {How to Backdoor Diffie-Hellman},
      howpublished = {Cryptology ePrint Archive, Paper 2016/644},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/644}},
      url = {https://eprint.iacr.org/2016/644}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.