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

171–180 of 199 posts

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

#171

Post by leni536 »

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?

Just build your sensitive hard coded primes in a separate object file. It rarely needs updating.

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

#172

Post by Lozzer »

tankenmate wrote: post #51
duaneb wrote: post #41

Earlier quoted context omitted.

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

I expect you have enough hardware to factor widely deployed primes. Compound numbers might be a different story.

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

#173

Post by chris_wot »

tzs wrote: post #162
Natsu wrote: post #158

Earlier quoted context omitted.

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 expa…

Sorry to go off topic here, but can you give an example of a number that isn't interesting?

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

#174

Post by williamstein »

qwerty1793 wrote: post #146
21 wrote: post #88

Earlier quoted context omitted.

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.

The following Sage script shows that p has no prime factors less than 2^32 other than 271 and 13597: 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, 0x4…

Sage also has an is_prime function, which provably show that p is not prime: "is_prime(p)". This takes less than 1ms to run. Proving primality of a 1024 bit prime in Sage takes a few seconds, and for a 2048 bit prime about a minute. Sage uses PARI for this, with sophisticated elliptic curve based algorithms called ECPP("=elliptic curve primality proving"), which are non-deterministic (unlike AKS) but fast in practice and provably correct. https://goo.gl/34uxJl

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

#175

Post by pjc50 »

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.

If they have a complete IP traffic recording facility, they will be applying automatic classification to it and looking to make the classification as complete as possible. Anything that doesn't fit the existing categories will attract attention.

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

#176

Post by cyphar »

Natsu wrote: post #158
im2w1l wrote: post #154

Earlier 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, but that has nothing to do with "containing every number". A transcendental number is defined as a number which is not the root of any non-zero polynomial with rational coefficients. The two properties are not related. For example, the first example of a transcendental number (Louisville numbers) isn't capable of being base-10 normal (it only contains the digits 0 and 1).

The property you're referring to is related to normality. A normal number in a base b is a number where the frequency of digits in that base approaches 1/b, but is not a rational number (and thus does not have cycles). Pi has not been proven to be normal, but if it were then it would have the property of which you speak (which is an informal property provided by normality).

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

#177

Post by cyphar »

Ded7xSEoPKYNsDd wrote: post #169
cyphar wrote: post #161

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?

Generating those parameters is very slow. Just run `time openssl dhparam -text -noout 1024` a few times and see for yourself.

Then do it on first run and store it in ~/.socat_prime and do a primality check each time it's loaded.

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

#178

Post by cyphar »

tzs wrote: post #162
Natsu wrote: post #158

Earlier quoted context omitted.

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 expa…

More correctly, all (AFAIK) currently provable normal numbers have been designed to be normal.

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

#180

Post by kazagistar »

gus_massa wrote: post #121
542458 wrote: post #91

Earlier quoted context omitted.

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

Let's assume it's not malice. Can it be a typo? Is there a prime with a low Levenshtein distance in hex of the old no-prime number? (Is there a always a prime within a low distance from any number?)

Well, the provided command takes 2.5 min to for pari to test the given "prime" on my computer. There are 16*256 numbers with a single hex digit mutation from the number given.

Anyone got a cluster laying around?

Post reply on HN