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

81–90 of 199 posts

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

#81

Post by [deleted] »

pygy_ wrote: post #14
baby wrote: post #9

Q: How does p not being a prime => backdoor? A: p not being a prime means two things: * subgroup confinement attacks (where you send a public key made with a fake generator g) should be able to take place if the code is weak -> this is because there must be low order subgroups. * the generator g might not be of great order. This can be easily tested if you know how to factor p: the order of the multiplicative group (…

p not being prime means it has not been generated using a standard tool like OpenSSL. It's therefore likely it's been handcrafted for nefarious purposes, opening the possibility of further shenanigans. Another possibility would be the use of a buggy generator, or a clueless dev using random bits rather than a large prime.

[deleted]

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

#82

Post by daveguy »

pygy_ wrote: post #14
baby wrote: post #9

Q: How does p not being a prime => backdoor? A: p not being a prime means two things: * subgroup confinement attacks (where you send a public key made with a fake generator g) should be able to take place if the code is weak -> this is because there must be low order subgroups. * the generator g might not be of great order. This can be easily tested if you know how to factor p: the order of the multiplicative group (…

p not being prime means it has not been generated using a standard tool like OpenSSL. It's therefore likely it's been handcrafted for nefarious purposes, opening the possibility of further shenanigans. Another possibility would be the use of a buggy generator, or a clueless dev using random bits rather than a large prime.

Or someone made a mistake copying and pasting.

Edit: wow. that is serendipity. Just accidentally posted twice. Does hitting "submit" twice do that?

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

#83

Post by saurik »

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.

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 was actually more likely to return the wrong answer because the computer was hit by a cosmic ray while it was determining if the number were prime.

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

#84

Post by xyzzyz »

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.

No, it's not the same order. 1/2^80 is the same order as the likelihood of as picking 1000 grains out of 1010, and I'm sure you'll agree that Sahara has more grains that 1010.

However, if you picked a single grain from Sahara desert, you'll be only 2 or 3 orders of magnitude off, so one could say that 2^-80 is only slightly easier than finding a particular grain in a Sahara desert.

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

#85

Post by anderskaseorg »

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?

A primality certificate could be included that allows the prime to be verified quickly during the build. This certificate for the 2048-bit prime took 90 seconds to generate, and can be verified in 3 seconds.

http://web.mit.edu/andersk/Public/socat-prime.pl

https://en.wikipedia.org/wiki/Primality_certificate

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

#86

Post by mrb »

wtbob wrote: post #80
defen wrote: post #55

Earlier quoted context omitted.

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.

This is not a valid comparison.

An attacker who can bruteforce, say, 2^80 128-bit keys (approximate limit of the computational power of the largest adversaries) has 1 chance out of 2^48 to break the security.

But an attacker has only 1 chance out of 2^80 that this parameter is a non-prime.

2^80 is much larger than 2^48, therefore it is not a problem.

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

#87

Post by cperciva »

wtbob wrote: post #80
defen wrote: post #55

Earlier quoted context omitted.

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.

Apples and oranges. When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken.

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

#88

Post by 21 »

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.

Wow. 271 is a factor.

Why not try dividing by all 32 bit numbers, to at least filter easy cases. Shouldn't take more than a few seconds.

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

#89

Post by bigiain »

CamperBob2 wrote: post #52
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.

That's a nice piece of plausible deniability, huh? I wonder if the committer has a few extra bytes that he can claim were supposed to be there which make a number that passes all the primality tests? That'd be a nice excuse for the NSA/3PLA overlords to have given him...

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

#90

Post by cperciva »

CamperBob2 wrote: post #52
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.

The optional comma at the end of the list of entries in an array is explicitly allowed by the C standard.
Post reply on HN