4 ms·
Research on how to backdoor Diffie-Hellman
- egonschiele 11y ago"This repo contains some research I'm currently doing on how to bakdoor Diffie-Hellman". Is this a working backdoor, or a work-in-progress?
- noobie 11y agoIt works. https://youtu.be/W8vBm6oXlEM https://youtu.be/W8vBm6oXlEM
- yeukhon 11y agoI am always interested in knowing how cryptographers come up with these big big big big numbers? https://github.com/mimoo/Diffie-Hellman_Backdoor/blob/master/attack/1024_backdoored_params https://github.com/mimoo/Diffie-Hellman_Backdoor/blob/master... They appear to be mysterious, magic numbers in every single crypto implementation. And many are written in byte form. I mean how can people comprehend them?
- deleted 11y ago[deleted]
- tptacek 11y agoPeople generate large primes using programs designed to do that, and maybe generators/primitive roots for those primes using a CAS like Sage or Octave/Matlab. The same goes for ECC crypto, with a lot of extra testing/filtering to find "nice" constants. A lot of the other giant numbers you see in cryptosystems are random numbers derived from other constants. Sometimes there are things to learn by studying the numbers themselves. For instance, the prime field in Curve25519 is a special prime with (bit-level) characteristics that make it especially nice to do math on with general-purpose computers. Other times, the numbers are, for instance, just giant random primes, and aren't themselves very interesting.
- yeukhon 11y agoI see. Thank you, tptacek. > People generate large primes using programs designed to do that Do you mind to name one such program?
- tptacek 11y agoWell, anything that does RSA, right? An easy way to do this yourself is to jump into a Ruby IRB and do "OpenSSL::BN.generate_prime(512).to_s".
- y04nn 11y agoWikipedia gives some information. https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Primality_test https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Generalizations https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Gene...
- tptacek 11y agoThis is a lot more interesting than I thought it would be from the title. Obviously, anyone can trivially generate "backdoored" Diffie-Hellman parameters; for instance, just use a bogus generator that locks the algorithm into a tiny subgroup. No matter what private keys Alice or Bob generate, the DH computation will be predictable. This writer wants to do something cooler: generate NOBUS parameters, in the fashion of Dual_EC DRBG, so that the parameter's authors can predict DH computations but (without Significant effort) nobody else can. Several of the methods the writer is playing with involve DH parameters for which they can use Pohlig-Hellman to recover secrets. Pohlig-Hellman breaks DH when its victims are unfortunate enough to be in a group with a smooth order --- that is (I'm butchering this), when the group order factors into small primes. It works by collecting samples from the target for each factor of the group; each leaks a bit of the key modulo that factor. You knit the samples together with CRT. David wrote this up well here: https://www.cryptologie.net/article/196/pohlig-hellman-algorithm/ https://www.cryptologie.net/article/196/pohlig-hellman-algor... Obligatory plug: a fun version of this attack is the kick-off problem on Sean Devlin's very excellent Set 8 of the Cryptopals challenges. Set 8 isn't on the website, but you can mail him (finding him is an exercise for the reader) to get a copy (on the honor system, like the other challenges were before we published). Set 8 builds this attack to an extremely useful attack on Elliptic Curve Diffie-Hellman.
- jamiesonbecker 11y agoLink to more details on what the OP is working on: https://github.com/mimoo/Diffie-Hellman_Backdoor/tree/master/socat_reverse https://github.com/mimoo/Diffie-Hellman_Backdoor/tree/master...
- cperciva 11y agoSeveral of the methods the writer is playing with involve DH parameters for which they can use Pohlig-Hellman to recover secrets. Pohlig-Hellman breaks DH when its victims are unfortunate enough to be in a group with a smooth order --- that is (I'm butchering this), when the group order factors into small primes. It works by collecting samples from the target for each factor of the group; each leaks a bit of the key modulo that factor. You knit the samples together with CRT. I'm not entirely sure how this gets you NOBUS parameters though. You can find any small prime factors of the group order using ECM, so if you're relying on those to let you run Pohlig-Hellman then everybody else can do it too. (But in any case, you should be locking down your DH implementations to use a fixed nothing-up-my-sleeve group, so even if this is a backdoor it would be a backdoor with flashing neon lights around it.)