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

181–190 of 199 posts

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

#181

Post by orthopteroid »

pbsd wrote: post #39
phkahler wrote: post #32

Earlier quoted context omitted.

>> 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…

One of the factors is 3684787 = 271 x 13597, so I suspect this is more accidental than malicious. The generator, 2, does not seem to have pathologically small order, but I didn't check very far.

Coincidentally, 13597 base 10 is 351d hex, which in unicode is defined as 'strong resistance'.

http://www.charbase.com/351d-unicode-cjk-unified-ideograph

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

#182

Post by tzs »

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?

By "interesting" I mean a number that arises out of something else that one might be interested in.

For instance, consider pi. If you are interested in geometry, pi will turn up. If you are interesting in number theory, pi will turn up (e.g., it is connected to zeta functions). If you are interested in probability and statistics, pi will turn up. If you are interested in differential equations, pi will come to the party.

If you somehow have never encountered pi, I can convey it to you by telling you about one of those things. For instance, I could tell you that it is the period of the non-zero solutions of the differential equation y'' + y = 0.

An uninteresting number would be one that has no known connection to other things. If I have a particular uninteresting number, and I want to convey it to you, I'll have to just tell you the number.

A random number would almost certainly be uninteresting, such as this hex fraction, which came from /dev/urandom on my computer: 0.bfdab557104bf2d8952fb1ea0adfd732794a353d5b35d95cda927f4ad8f6dd11f11b2e968298. It is extremely unlikely that anyone has ever seen that number before. The only known thing interesting about it is that it was made specifically as an example of a number that is not otherwise interesting.

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

#183

Post by anon4711 »

brianberns wrote: post #103
mehwoot wrote: post #99

Earlier quoted context omitted.

Assuming you are given a single number and you test it and is_prime says it is prime. If on the other hand you are looking for a number that is_prime says is prime, and you are iterating through candidates, you need to know how likely it is to find a prime number in the first place to tell you how unlikely this is. In most cases the chance of a false positive will be much, much higher than 2^-80. If for example, you…

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.

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

#184

Post by bonzini »

lifthrasiir wrote: post #129
gus_massa wrote: post #121

Earlier quoted context omitted.

Let's assume it's not malice. Can it be a typo? Is there a prime with a low Levenshtein distance in hex of the old no-prime number? (Is there a always a prime within a low distance from any number?)

I've tested some of them with PARI/GP. There is no probable prime with the Hamming distance 1. There are several (probably 3--400, haven't exhaustively listed) probable primes with the Hamming distance 2 (p ^ (1<<30) ^ (1<<14) is one example).

About 1 in 700 1024-bit numbers is prime. There are 1023512 Hamming-distance 2 numbers for a 1024-bit number, about 750 of them will be prime.

If you found no Hamming distance 1 primes (expected: 0.68) and 3-400 Hamming distance 2 primes (expected: 750), this is one really* bad "prime"...

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

#185

Post by mchahn »

defen wrote: post #55
matthewaveryusa wrote: post #49

Earlier quoted context omitted.

I'm pretty sure that when you generate a prime you're using the Miller–Rabin primality test in which case you only probabilistically choose a prime. In fact, the is_prime functions in openssl don't check if a number is prime. They only check that a number is prime within 1-2^-80 probability. I'm not sure what the implications are though. See https://www.openssl.org/docs/manmaster/crypto/BN_generate_pr...

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

Marilyn Vos Savant got a question on her column I'll never forget. The answer was awesome ..

Q: My friend got a perfect hand in bridge. What are the odds of this happening?

A: Your friend is a liar.

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

#186

Post by tika »

matthewaveryusa wrote: post #49
mrb wrote: post #37

It irks me that in security advisories that fix a possible backdoor—like here—sometimes no root cause analysis is done or communicated to the public. Who chose this parameter? Who wrote the code? Who committed it? So I did a little sleuthing... Here is the commit introducing the non-prime parameter (committed by Gerhard Rieger who is the same socat developer who fixed the issue today): http://repo.or.cz/socat.git/com…

I'm pretty sure that when you generate a prime you're using the Miller–Rabin primality test in which case you only probabilistically choose a prime. In fact, the is_prime functions in openssl don't check if a number is prime. They only check that a number is prime within 1-2^-80 probability. I'm not sure what the implications are though. See https://www.openssl.org/docs/manmaster/crypto/BN_generate_pr...

2^1024 is a lot larger than 2^80. The implication is clear.

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

#187

Post by tika »

geofft wrote: post #141
mehwoot wrote: post #99

Earlier quoted context omitted.

Assuming you are given a single number and you test it and is_prime says it is prime. If on the other hand you are looking for a number that is_prime says is prime, and you are iterating through candidates, you need to know how likely it is to find a prime number in the first place to tell you how unlikely this is. In most cases the chance of a false positive will be much, much higher than 2^-80. If for example, you…

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.

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

#188

Post by tika »

marvin wrote: post #72
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.

The likelihood of 1/2^80 is on the same order as me picking out a thousand grains of sand from the Sahara desert, spreading them randomly out through the desert and having you pick out those exact thousand grains of sand. It's a practical impossibility, a philosophical exercise.

Yes, but 1/2^80 is ridiculously large compared to 1/2^1024.

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

#190

Post by tika »

pbsd wrote: post #39
phkahler wrote: post #32

Earlier quoted context omitted.

>> 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…

One of the factors is 3684787 = 271 x 13597, so I suspect this is more accidental than malicious. The generator, 2, does not seem to have pathologically small order, but I didn't check very far.

271 is rather small. Which means this fake prime was quite easy to generate.
Post reply on HN