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

91–100 of 199 posts

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

#91

Post by 542458 »

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…

Oh jeez. That non-prime is evenly divisible by 271 and 13597 (among other things).

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

#92

Post by smegel »

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.

Given that there is so much probability in the world, you would think you would want to be certain about things you can be objectively 100% certain about, especially for one off long term choices that have big implications.

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

#94

Post by fixermark »

marcosdumay wrote: post #57
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...

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

Would it be reasonable to say that the following scenarios are more probable?

* The specific version of the software that was used to generate the non-prime contained a bug in its implementation of the algorithm

* The specific hardware upon which the software was run was flawed in a way that generated an incorrect output number from the program (i.e. on-disk corruption, RAM corruption, etc., undetected by the checksums in the hardware)

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

#96

Post by fivesigma »

nothis wrote: post #69
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...

There's one in a thousand chances and there's 1-2^-80 chances. Wouldn't that be some "electrons in the universe" level coincidence? Believing in that borders on religion.

That would be 10^80 which is much, much larger than 2^80.

Unrelated, but 2^80 isn't that astronomic when it comes to computers, considering that the entire Bitcoin network has performed 2^84 hashes.

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

#97

Post by stouset »

smegel wrote: post #92
defen wrote: post #55

Earlier quoted context omitted.

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

Given that there is so much probability in the world, you would think you would want to be certain about things you can be objectively 100% certain about, especially for one off long term choices that have big implications.

2^-80 is orders and orders of magnitude less likely than the chance of a bit error in RAM when performing the calculation. Or of fucking up the implementation of such a check. Or of a CPU error.

https://blogs.msdn.microsoft.com/oldnewthing/20160114-00/?p=...

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

#98

Post by schoen »

__mbm__ wrote: post #77
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…

For anyone following along at home, you missed a D at the very end (0x6D). A number whose hexadecimal representation ended in 6 couldn't be prime because it is even.

(final digit is divisible by d ←→ number is divisible by d works for any d that is a divisor of the base the number is written in)

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

#99

Post by mehwoot »

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.

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 only expected to find a true prime in 1 every 2^80 numbers anyway, there would be a 50% chance that a number you found is prime and a 50% chance it would not actually be.

https://en.wikipedia.org/wiki/Bayes%27_theorem

Post reply on HN