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

191–199 of 199 posts

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

#191

Post by jibalt »

anon4711 wrote: post #183
brianberns wrote: post #103

Earlier quoted context omitted.

I don't think Bayes' theorem applies very well here, because there's no practical way to check enough numbers such that the effect you're describing comes into play. 2^80 is approximately a million billion billion (10^24), so if you had a million CPUs each checking a billion numbers every second, it would still take a billion seconds (over 30 years) to check that many numbers. I suspect that's why such a small level…

Why would 10^24 be a million billion billion? It's 4 blocks of 6 zeros each, so that I'd expect you to call it a billion billion billion billion, if anything.

1 million = 10^6. 1 billion = 10^9. 6+9+9 = 24.

This isn't rocket science.

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

#192

Post by geofft »

tika wrote: post #187
geofft wrote: post #141

Earlier quoted context omitted.

There are approximately x / ln (x) primes below x. That means that there are 2^1024 / (1024 ln 2) - 2^1023 / (1023 ln 2) = 1.3e305 1024-bit primes. There are 2^1024 - 2^1023 = 9.0e307 1024-bit numbers. So, the chance that a randomly-selected 1024-bit number is prime is a little higher one in a thousand, that is, a little higher than 2^-10. So Bayes' theorem doesn't save you here: it is still statistically unlikely th…

"There are 2^1024 - 2^1023 = 9.0e307 1024-bit numbers" This is the count of 1023 bits numbers [(x - x/2) = x/2]. 0 is a valid leftmost digit.

The standard usage in the field of crypto is that a phrase like "1024-bit prime" means a number between 2^1023 and 2^1024. For symmetric keys, yes, a "128-bit key" can start with a 0 and can even be all zeros. But for integers with mathematical properties like prime numbers, there's a big difference in the ability to e.g. factor the product of two "1024-bit primes" randomly chosen from [2^1023, 2^1024) and the product of two "1024-bit primes" randomly chosen from [0, 2^1024).

It matches the common-English usage of a phrase like "a six-figure salary." A salary of $020,000 isn't what's meant by the phrase.

You can verify this by, say, running `openssl genrsa 1024 | openssl rsa -noout -text` a few times and looking at the generated prime1 and prime2. They each have the 512th bit set. (They seem to be printed with a leading hex "00:", but there are 512/8 = 64 bytes afterwards, and the first byte always has the high bit set.)

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

#193

Post by jibalt »

makmanalp wrote: post #64
defen wrote: post #55

Earlier quoted context omitted.

2^-80 is an incomprehensibly tiny number. Malice or incompetence are both FAR more likely.

You know, I never know what to make of that logic - what if that tiny probability was exactly this one time? It's not like we saw it happen twice, and it could happen at some point. To my gut it seems you can't really know until you have other positive or negative observations. I wonder if someone has compiled a list of very improbable events that have been observed.

Your gut is bad at statistics.

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

#194

Post by jibalt »

makmanalp wrote: post #137
makmanalp wrote: post #64

Earlier quoted context omitted.

You know, I never know what to make of that logic - what if that tiny probability was exactly this one time? It's not like we saw it happen twice, and it could happen at some point. To my gut it seems you can't really know until you have other positive or negative observations. I wonder if someone has compiled a list of very improbable events that have been observed.

Wow - this has got to be my most downvoted comment. I can't edit the original anymore, so here's my update: I guess the harsh reaction came from the fact that I didn't define the scope very well: My question wasn't in reference to M-R specifically, just in general. I understand that in this case it makes sense to look at likelier causes (see Sharlin's response). My point was that it's interesting to look at what happ…

"It seems weird to go with the assumption that because something is extremely unlikely that it won't happen."

No, it's rational.

As for the rest of your post, you are confused between a priori and a posteriori probability.

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

#195

Post by jibalt »

makmanalp wrote: post #137
makmanalp wrote: post #64

Earlier quoted context omitted.

You know, I never know what to make of that logic - what if that tiny probability was exactly this one time? It's not like we saw it happen twice, and it could happen at some point. To my gut it seems you can't really know until you have other positive or negative observations. I wonder if someone has compiled a list of very improbable events that have been observed.

Wow - this has got to be my most downvoted comment. I can't edit the original anymore, so here's my update: I guess the harsh reaction came from the fact that I didn't define the scope very well: My question wasn't in reference to M-R specifically, just in general. I understand that in this case it makes sense to look at likelier causes (see Sharlin's response). My point was that it's interesting to look at what happ…

"Or maybe it's that somehow the probability changes when we have more information"

Um, yes, that's all that probability is. See Bayes Theorem.

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

#196

Post by jibalt »

baby wrote: post #29
Filligree wrote: post #11

Earlier quoted context omitted.

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.

It's clear that you haven't read it at all:

http://www.merriam-webster.com/dictionary/proof

The fact of the matter is that the sort of Platonic definition of proof that you fantasize is impossible because it depends on certainty, which itself cannot be proven. The best we can do is fail to find an error in an alleged proof.

Consider the proofreader's paradox: A proofreader can be prepared to swear, for any given page of a 1000 page book, that there are no typos on that page, but no proofreader is so foolish as to claim that there are no typos in the book.

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

#197

Post by jibalt »

phkahler wrote: post #32
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 (…

>> Unfortunately, if you don't know how to factor p then you can't easily do that. The link says they don't know where p came from. Presumably someone constructed it as a product of primes known only to them. I don't recall the state of the art in factorization, but if 1024 bits can be factored easily that's news to me. So the weakness would only be exploitable to whomever created p. Why nobody checked the primality…

"Presumably someone constructed it as a product of primes known only to them"

It would be foolish to presume that. And knowing the factors of the Diffie-Hellman parameter isn't all that important.

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

#198

Post by jibalt »

chris_wot wrote: post #173
tzs wrote: post #162

Earlier quoted context omitted.

Pi is transcendental, which means that it is not a root of a non-zero polynomial with rational coefficients. Being transcendental does not imply that a number's expansion in a given base must include every digit string. Consider the number 1/10^1! + 1/10^2! + 1/10^3! + 1/10^4! + .... This number, whose decimal expansion is 0.110001000000000000000001... is transcendental (proven by Liouville in 1844). Its decimal expa…

Sorry to go off topic here, but can you give an example of a number that isn't interesting?

Generate some random numbers. They aren't interesting.

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

#199

Post by baby »

qwerty1793 wrote: post #146
21 wrote: post #88

Earlier quoted context omitted.

Wow. 271 is a factor. Why not try dividing by all 32 bit numbers, to at least filter easy cases. Shouldn't take more than a few seconds.

The following Sage script shows that p has no prime factors less than 2^32 other than 271 and 13597: p_list = [0xCC, 0x17, 0xF2, 0xDC, 0x96, 0xDF, 0x59, 0xA4, 0x46, 0xC5, 0x3E, 0x0E, 0xB8, 0x26, 0x55, 0x0C, 0xE3, 0x88, 0xC1, 0xCE, 0xA7, 0xBC, 0xB3, 0xBF, 0x16, 0x94, 0xD8, 0xA9, 0x45, 0xA2, 0xCE, 0xA9, 0x5B, 0x22, 0x25, 0x5F, 0x92, 0x59, 0x94, 0x1C, 0x22, 0xBF, 0xCB, 0xC8, 0xC8, 0x57, 0xCB, 0xBF, 0xBC, 0x0E, 0xE8, 0x4…

Have you tried dividing the order by 271 and 13597 and search again on that?
Post reply on HN