Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Socat: “the hard coded 1024 bit DH p parameter was not prime”

openwall.com

Post reply on HN
Print view View original

21–30 of 199 posts

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#21

Post by baby »

schoen wrote: post #19
openasocket wrote: post #12

Earlier quoted context omitted.

There are exact tests that run in polynomial time, like https://en.wikipedia.org/wiki/AKS_primality_test

I hate to say that a polynomial-time test isn't efficient because many people use that as the very definition of efficient, but my understanding is that AKS is incredibly impractical because the polynomial is ginormous, even though its asymptotic behavior is nice. So if you actually wanted to know if, say, a 1024-bit number was definitely prime, you wouldn't be able to run AKS on it in a "reasonable time" on a real c…

I haven't actually studied to what extent the AKS tests are do-able. I always figured there would be no problem running one for a 1024 bits prime. Found this on SO: http://cs.stackexchange.com/questions/23260/when-is-the-aks-...

Also, to further the discussion on probable vs provable: the probable tests are enough in our case because they tell us _provably_ if an integer is not a prime (that we care), but _probably_ if an integer is a prime (which we don't care here).

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#22

Post by baby »

openasocket wrote: post #15
baby wrote: post #9

Q: How does p not being a prime => backdoor? A: p not being a prime means two things: * subgroup confinement attacks (where you send a public key made with a fake generator g) should be able to take place if the code is weak -> this is because there must be low order subgroups. * the generator g might not be of great order. This can be easily tested if you know how to factor p: the order of the multiplicative group (…

But once you have the factorization for p, since it's hardcoded, it's now much easier to break every DH key exchange used by this application. Getting that factorization would be very very difficult, but once you have it you can use it on everyone.

if it's not an easy factorization => it will be hard. According to recent results we believe state-sized adversary should be able to do it. If you're threat model is against criminals, then you might be OK.

EDIT: if 1024bits factorization is easy in general, you can say goodbye to every 1024bits RSA modulus. My first statement doesn't mean it can never be easy, it means that if you try and factor it the easy way and it doesn't work... you are in for a lot of work and research.

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#23

Post by eutectic »

schoen wrote: post #10
baby wrote: post #9

Q: How does p not being a prime => backdoor? A: p not being a prime means two things: * subgroup confinement attacks (where you send a public key made with a fake generator g) should be able to take place if the code is weak -> this is because there must be low order subgroups. * the generator g might not be of great order. This can be easily tested if you know how to factor p: the order of the multiplicative group (…

> We have efficient provable tests for that: they tell you if p is prime or not and nothing else. I think this is a typo -- the efficient general-form tests are probable rather than provable . https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...

They can provably tell you that a number is composite.

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#24

Post by bjornsing »

schoen wrote: post #10
baby wrote: post #9

Q: How does p not being a prime => backdoor? A: p not being a prime means two things: * subgroup confinement attacks (where you send a public key made with a fake generator g) should be able to take place if the code is weak -> this is because there must be low order subgroups. * the generator g might not be of great order. This can be easily tested if you know how to factor p: the order of the multiplicative group (…

> We have efficient provable tests for that: they tell you if p is prime or not and nothing else. I think this is a typo -- the efficient general-form tests are probable rather than provable . https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...

From your own reference (https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...): "the usual randomized primality tests never report a prime number as composite".

So I'd say that's probably what happened here (i.e p was reported composite by a randomized primality test and that would never have happened had it been prime).

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#25

Post by rlpb »

archgoon wrote: post #13

Previously: 915 static unsigned char dh1024_p[] = { 916 0xCC,0x17,0xF2,0xDC,0x96,0xDF,0x59,0xA4,0x46,0xC5,0x3E,0x0E, 917 0xB8,0x26,0x55,0x0C,0xE3,0x88,0xC1,0xCE,0xA7,0xBC,0xB3,0xBF, 918 0x16,0x94,0xD8,0xA9,0x45,0xA2,0xCE,0xA9,0x5B,0x22,0x25,0x5F, 919 0x92,0x59,0x94,0x1C,0x22,0xBF,0xCB,0xC8,0xC8,0x57,0xCB,0xBF, 920 0xBC,0x0E,0xE8,0x40,0xF9,0x87,0x03,0xBF,0x60,0x9B,0x08,0xC6, 921 0x8E,0x99,0xC6,0x05,0xFC,0x00,0xD6,0x6D…

Not just a quick code review; it should be a build time assertion.

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#26

Post by xnyhps »

baby wrote: post #22
openasocket wrote: post #15

Earlier quoted context omitted.

But once you have the factorization for p, since it's hardcoded, it's now much easier to break every DH key exchange used by this application. Getting that factorization would be very very difficult, but once you have it you can use it on everyone.

if it's not an easy factorization => it will be hard. According to recent results we believe state-sized adversary should be able to do it. If you're threat model is against criminals, then you might be OK. EDIT: if 1024bits factorization is easy in general, you can say goodbye to every 1024bits RSA modulus. My first statement doesn't mean it can never be easy, it means that if you try and factor it the easy way and…

Testing for 2 seconds already found the prime factors 271 and 13597. It will probably not be hard.

Edit: To add some more information, p / (271 * 13597) is still not prime, however, the library I was using didn't find any new factors in 30 minutes.

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#27

Post by openasocket »

zitterbewegung wrote: post #18
openasocket wrote: post #12

Earlier quoted context omitted.

There are exact tests that run in polynomial time, like https://en.wikipedia.org/wiki/AKS_primality_test

Just because there are exact tests doesn't make the AKS primarily test usable in the real world because of constant factors . Using Fermats little theorem for primality testing is fine because the probably of encountering a Carmichael number is very low.

You're right, AKS is not a very efficient algorithm and randomized tests are generally good enough. But, there are exact tests which do run fast in practice, such as ECPP. Here's some of the largest primes found using ECPP: http://primes.utm.edu/top20/page.php?id=27

Note the largest there is 30,950 digits, which is about 102,813 bits unless I did my math wrong, so I bet it is usable for 1024-bit numbers. Non-exact methods are much much faster of course, but when you really really need exactness it is an option.

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#28

Post by schoen »

bjornsing wrote: post #24
schoen wrote: post #10

Earlier quoted context omitted.

> We have efficient provable tests for that: they tell you if p is prime or not and nothing else. I think this is a typo -- the efficient general-form tests are probable rather than provable . https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...

From your own reference ( https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t... ): "the usual randomized primality tests never report a prime number as composite ". So I'd say that's probably what happened here (i.e p was reported composite by a randomized primality test and that would never have happened had it been prime).

Oh sure, I don't mean that there's uncertainty that this number is composite, just that in a formal sense there isn't "proof" that other numbers that passed, say, openssl -checks 100000 are prime. But I wouldn't consider it unsafe to use them for cryptography.

The comment I was replying to referred to tests that "tell you if a number is prime or not", and the probable ones don't exactly always do that. :-)

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#29

Post by baby »

Filligree wrote: post #11
schoen wrote: post #10

Earlier quoted context omitted.

> We have efficient provable tests for that: they tell you if p is prime or not and nothing else. I think this is a typo -- the efficient general-form tests are probable rather than provable . https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...

Keep up the tests until you have ten or twenty nines of certainty. I'd call that proof.

then you should re-read the definition of a proof.

Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”

#30

Post by codeulike »

rlpb wrote: post #25
archgoon wrote: post #13

Previously: 915 static unsigned char dh1024_p[] = { 916 0xCC,0x17,0xF2,0xDC,0x96,0xDF,0x59,0xA4,0x46,0xC5,0x3E,0x0E, 917 0xB8,0x26,0x55,0x0C,0xE3,0x88,0xC1,0xCE,0xA7,0xBC,0xB3,0xBF, 918 0x16,0x94,0xD8,0xA9,0x45,0xA2,0xCE,0xA9,0x5B,0x22,0x25,0x5F, 919 0x92,0x59,0x94,0x1C,0x22,0xBF,0xCB,0xC8,0xC8,0x57,0xCB,0xBF, 920 0xBC,0x0E,0xE8,0x40,0xF9,0x87,0x03,0xBF,0x60,0x9B,0x08,0xC6, 921 0x8E,0x99,0xC6,0x05,0xFC,0x00,0xD6,0x6D…

Not just a quick code review; it should be a build time assertion.

I dont think that testing whether huge numbers are prime or not is quite as easy as you assume.

https://en.wikipedia.org/wiki/Primality_test

Post reply on HN