I think most people are glossing over the first part of the title. Why is the DH p parameter hardcoded? Why not just generate one on each startup?
Socat: “the hard coded 1024 bit DH p parameter was not prime”
161–170 of 199 posts
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#162Earlier quoted context omitted.
That is not know to be the case, only conjectured.
I thought it was proven to be trancendental? Or were you saying that this property of trancendental numbers is only conjectured?
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 expansion clearly does not contain every decimal number. It only contains the digits 0 and 1, and after the first two places never even contains consecutive 1s.
It is known that "almost all" real numbers do in fact contain in their base b expansion every sequence of base b numbers, each sequence occurring with frequency proportional to its length. These are called "normal" numbers. Very few interesting numbers (where "interesting" means that we have some reason to be interested in aside from their normality) are known to be normal, though.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#163It 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...
> 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.
Why would somebody use MR when there are faster sieves already running, as well as additional public lists of known large primes?
Maybe they shouldn't be near primes, let alone picking them.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#164Earlier 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.
For many years, in the computer science lab at the college where I sort of work, there was a "serious joke" written on the wall which said, with much better wording and some math to back it up, that the difference between a mathematician and an engineer is that the former was more concerned that a probabilistic primality test could inherently fail while the latter was more concerned that even a guaranteed algorithm w…
Probably a quote from SICP:
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#165Earlier 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.
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/
A person was hit by a meteorite [1]
[1] http://www.telegraph.co.uk/news/science/space/5511619/14-yea...
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#166Earlier quoted context omitted.
There are exact tests that run in polynomial time, like https://en.wikipedia.org/wiki/AKS_primality_test
I hate to say that a polynomial-time test isn't efficient because many people use that as the very definition of efficient, but my understanding is that AKS is incredibly impractical because the polynomial is ginormous, even though its asymptotic behavior is nice. So if you actually wanted to know if, say, a 1024-bit number was definitely prime, you wouldn't be able to run AKS on it in a "reasonable time" on a real c…
[deleted]
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#167Earlier quoted context omitted.
I hate to say that a polynomial-time test isn't efficient because many people use that as the very definition of efficient, but my understanding is that AKS is incredibly impractical because the polynomial is ginormous, even though its asymptotic behavior is nice. So if you actually wanted to know if, say, a 1024-bit number was definitely prime, you wouldn't be able to run AKS on it in a "reasonable time" on a real c…
I haven't actually studied to what extent the AKS tests are do-able. I always figured there would be no problem running one for a 1024 bits prime. Found this on SO: http://cs.stackexchange.com/questions/23260/when-is-the-aks-... Also, to further the discussion on probable vs provable: the probable tests are enough in our case because they tell us _provably_ if an integer is not a prime (that we care), but _probably_…
This is not conclusive, but the best deterministic primality test (an AKS variant by Pomerance and Lenstra) is 6th power. 1024^6 is quite large.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#168Previously: 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.
It's also there for the previous 512 bit prime. Probably just the style preference of the project.
Edit: Actually, it looks a lot like the code was originally generated using openssl dhparam -2 -C: https://gist.github.com/xnyhps/df16e7d43e32b7dbe3fb
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#169I think most people are glossing over the first part of the title. Why is the DH p parameter hardcoded? Why not just generate one on each startup?
Generating those parameters is very slow. Just run `time openssl dhparam -text -noout 1024` a few times and see for yourself.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#170Earlier quoted context omitted.
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…
f) Used a machine with bad RAM that flipped a bit. This case could actually be tested for - see if any of the one-bit differences from the number used are prime.
A bit could have been flipped in the software or the result of the function (true/false), but in the number itself there appear to be no single bit flips that make it prime (at least in the binary representation).
Edit: A single bit flip could have been used as "semi" plausible deniability in the case of malicious intent.