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

51–60 of 199 posts

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

#51

Post by tankenmate »

duaneb wrote: post #41
phkahler wrote: post #34

Earlier quoted context omitted.

>> I always wonder if when things like this get found, there's someone in the NSA going "Wow they finally found it, only took them x years" I would guess they were aware of the problem weather they created it or not. So yes.

> I would guess they were aware of the problem weather they created it or not. While it's smart to assume so, it's also pretty laughable to think that the NSA has an exhaustive list of encryption vulnerabilities.

> While it's smart to assume so, it's also pretty laughable to think that the NSA has an exhaustive list of encryption vulnerabilities.

True, but in this case I'm sure they have enough hardware to factor any widely deployed primes used in crypto or semi crypto comms software. After all, that is half of the NSAs job description.

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

#52

Post by CamperBob2 »

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…

Kind of interesting that the first nonprime version ended in a comma, as if it originated as a fragment of a longer array of bytes. That's nonstandard C, and I'd expect that whatever tool(s) generate those arrays would know not to add a comma after the final entry.

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

#53

Post by CamperBob2 »

alextgordon wrote: post #40
codeulike wrote: post #30

Earlier quoted context omitted.

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

It's pretty easy. There are ways to test primarily such that constructing a counterexample would be an important mathematical result. https://en.wikipedia.org/wiki/Baillie–PSW_primality_test > The power of the Baillie-PSW test comes from the fact that these lists of strong Fermat pseudoprimes and strong Lucas pseudoprimes have no known overlap. There is even evidence that the numbers in these lists tend to be differe…

It might be "easy" but is it quick enough to be tolerated as part of a build?

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

#54

Post by schoen »

pbsd wrote: post #48
jcoffland wrote: post #47

Earlier quoted context omitted.

Seems like a Carmichael number could be a good choice for an attacker. This would make your chances of encountering a Carmichael number quite high. You have to consider who's choosing the number. Or do I have it wrong?

Only the simple Fermat tests are vulnerable to Carmichael numbers. The test which is used in practice, Rabin-Miller, is not vulnerable to them. In fact, if you assume the extended Riemann hypothesis is true, (log n)^2 iterations of Rabin-Miller are sufficient to prove primality.

How efficient might this be compared to other approaches for searching for Riemann hypothesis counterexamples? Is there a one-to-one relationship between direct Riemann counterexamples and composite numbers that pass (log n)² Rabin-Miller tests?

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

#55

Post by defen »

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^-80 is an incomprehensibly tiny number. Malice or incompetence are both FAR more likely.

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

#56

Post by gchpaco »

jcoffland wrote: post #47
zitterbewegung wrote: post #18

Earlier quoted context omitted.

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.

Seems like a Carmichael number could be a good choice for an attacker. This would make your chances of encountering a Carmichael number quite high. You have to consider who's choosing the number. Or do I have it wrong?

In addition to what pbsd said, Carmichael numbers are incredibly rare. Your odds of stumbling across one by chance are lower than the odds of a cosmic ray flipping the bit of memory that causes you to believe you have stumbled across one, as I recall.

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

#57

Post by marcosdumay »

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

Except for a possible bug, 2^-80 is effectively zero, and getting a non-prime from this routine is effectively impossible.

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

#58

Post by malandrew »

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…

What's worse, a 512 bit DH prime or a 1024 not-quite-prime?

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

#59

Post by wanderfowl »

jcoffland wrote: post #38
wanderfowl wrote: post #35

Nice catch. Now, the real question is who committed it, and how they came up with the number. If it is a backdoor, it's pretty smart, because it's very deniable as a "stupid mistake". And if it's a stupid mistake, it's extra stupid, because this committer will have trouble convincing the world that that's all it was. At the very least, somebody needs to be going through all this person's commits with a fine-toothed c…

Aren't large non-primes usually created by multiplying two large but smaller primes together. Factoring is then the challenge. Or is there more to this that I'm missing?

The question is whether they:

a) knew it was non-prime, and used it to weaken the crypto

b) knew it was non-prime, and used it because they didn't think it needed to be prime (which is a massive sin of ignorance)

c) grabbed 1024 bits of rand() and didn't check if it was prime (again, stupid)

d) grabbed some rand and checked the prime-ness using a bad method

e) used a "prime number generator" that produced bad output

I agree that making non-prime numbers is not terribly difficult, but the question of how they got the number is only interesting in that it gives info about why.

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

#60

Post by lorenzhs »

CamperBob2 wrote: post #53
alextgordon wrote: post #40

Earlier quoted context omitted.

It's pretty easy. There are ways to test primarily such that constructing a counterexample would be an important mathematical result. https://en.wikipedia.org/wiki/Baillie–PSW_primality_test > The power of the Baillie-PSW test comes from the fact that these lists of strong Fermat pseudoprimes and strong Lucas pseudoprimes have no known overlap. There is even evidence that the numbers in these lists tend to be differe…

It might be "easy" but is it quick enough to be tolerated as part of a build?

The primality test of the original number using gp that archgoon posted takes 6ms on my Sandy Bridge laptop, that's plenty fast. (The new number takes a minute to check, though, so that might really be too long)
Post reply on HN