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

71–80 of 199 posts

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

#71

Post by Lazare »

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.

We happily incarcerate and (for countries that do so) execute people based on much weaker evidence. 2^-80 is absurdly small, to the point that essentially any other possibility is more likely.

You say you want to see it twice, but one data point with an error rate of 1 in 2^80 is, statistically, about a billion times more convincing than a million observations with an error rate of 1 in a million.

(That being said, there are a lot of of explanations that don't involve malice, including honest error, bugs in any of the software products involved in the process, etc. But no, I don't believe that this was a 1 in 2^80 fluke.)

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

#72

Post by marvin »

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.

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.

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

#73

Post by xyzzyz »

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.

2^-80 (~10^24) is is about as likely as being hit by a meteorite (~10^-16)[1] at exactly the same moment you are learning that you won the Powerball (~10^-8). Alternatively, it is as likely as winning Powerball in three consecutive drawings.

[1] - https://what-if.xkcd.com/19/

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

#74

Post by Sharlin »

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.

There are countless other possible causes that are much more probable than M-R returning a false positive. What should we do about all of them? Start ruling them out, one by one, sure, but in which order? Common sense says we should do it in the order of decreasing prior probability. The hypothesis "M-R returned a false positive" is there somewhere, in the space of all possible hypotheses, and we'll surely encounter it after all other more likely alternatives are exhausted. I bet we don't have to go that far.

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

#75

Post by pbsd »

schoen wrote: post #54
pbsd wrote: post #48

Earlier quoted context omitted.

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?

I am not familiar with all the ways the GRH can be disproven, but Miller-Rabin doesn't strike me as the most efficient, with its running time of O((log n)^4) for each attempt. I am not sufficiently competent to say whether a GRH counterexample also directly results in a MR counterexample.

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

#76

Post by heavenlyhash »

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

It would be fantastic to see this fix accompanied by a patch that adds a test that runs that primality check again.

It's a check that probably doesn't need to run in CI over and over again, but boy would it be nice to have it codified so everyone reading now could reproducibly run the check if we felt the desire.

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

#77

Post by __mbm__ »

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…

# Run Miller-Rabin on the prime in the blink of an eye:

from gmpy2 import mpz, is_prime

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, 0x40, 0xF9, 0x87, 0x03, 0xBF, 0x60, 0x9B, 0x08, 0xC6, 0x8E, 0x99, 0xC6, 0x05, 0xFC, 0x00, 0xD6, 0x6D, 0x90, 0xA8, 0xF5, 0xF8, 0xD3, 0x8D, 0x43, 0xC8, 0x8F, 0x7A, 0xBD, 0xBB, 0x28, 0xAC, 0x04, 0x69, 0x4A, 0x0B, 0x86, 0x73, 0x37, 0xF0, 0x6D, 0x4F, 0x04, 0xF6, 0xF5, 0xAF, 0xBF, 0xAB, 0x8E, 0xCE, 0x75, 0x53, 0x4D, 0x7F, 0x7D, 0x17, 0x78, 0x0E, 0x12, 0x46, 0x4A, 0xAF, 0x95, 0x99, 0xEF, 0xBC, 0xA6, 0xC5, 0x41, 0x77, 0x43, 0x7A, 0xB9, 0xEC, 0x8E, 0x07, 0x3C, 0x6D]

p = mpz(0) # Edit: should be zero, not 1

for num in p_list: p = (p print("Q: Is p a prime?\nA: %s" % (is_prime(p) and 'Yes' or 'No'))

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

#78

Post by wolfgke »

duaneb wrote: post #66
nisa wrote: post #62

Earlier quoted context omitted.

> it's also pretty laughable to think that the NSA has an exhaustive list of encryption vulnerabilities Why not? They have enough mathematicians and cryptographers on payroll that they can analyse the major protocols and software that is used. If you look at the recent attacks on TLS - especially the downgrade attacks to export grade ciphers they would be stupid to not exploit this for targeted attacks. That being sa…

Because coming up with an exhaustive list of all the encryption software in the world would be difficult, let alone enumerating all of their vulnerabilities.

For practical purposes it should suffice if they create an exhaustive list of the encryption software that is used, say, in 99% of all cases. Finding those and documenting some vulnerabilities of each is quite a realistic goal.

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

#79

Post by duaneb »

wolfgke wrote: post #78
duaneb wrote: post #66

Earlier quoted context omitted.

Because coming up with an exhaustive list of all the encryption software in the world would be difficult, let alone enumerating all of their vulnerabilities.

For practical purposes it should suffice if they create an exhaustive list of the encryption software that is used, say, in 99% of all cases. Finding those and documenting some vulnerabilities of each is quite a realistic goal.

Sure. This is also not exhaustive, by definition.

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

#80

Post by wtbob »

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.

> 2^-80 is an incomprehensibly tiny number.

When one wants a 128-bit security margin, 2^-80 is 2^48 times too big.

Post reply on HN