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

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by archgoon on Monday February 01, 2016 @02:51PM (#11014829)

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,0x90,0xA8,0xF5,0xF8,
    922      0xD3,0x8D,0x43,0xC8,0x8F,0x7A,0xBD,0xBB,0x28,0xAC,0x04,0x69,
    923      0x4A,0x0B,0x86,0x73,0x37,0xF0,0x6D,0x4F,0x04,0xF6,0xF5,0xAF,
    924      0xBF,0xAB,0x8E,0xCE,0x75,0x53,0x4D,0x7F,0x7D,0x17,0x78,0x0E,
    925      0x12,0x46,0x4A,0xAF,0x95,0x99,0xEF,0xBC,0xA6,0xC5,0x41,0x77, 
    926      0x43,0x7A,0xB9,0xEC,0x8E,0x07,0x3C,0x6D,
    927       };

  $ echo 'isprime(143319364394905942617148968085785991039146683740268996579566827015580969124702493833109074343879894586653465192222251909074832038151585448034731101690454685781999248641772509287801359980318348021809541131200479989220793925941518568143721972993251823166164933334796625008174851430377966394594186901123322297453)' | gp -q
  0

With fix

    xio-openssl.c
    915       static unsigned char dh2048_p[] = {
    916      0x00,0xdc,0x21,0x64,0x56,0xbd,0x9c,0xb2,0xac,0xbe,0xc9,0x98,0xef,0x95,0x3e,
    917      0x26,0xfa,0xb5,0x57,0xbc,0xd9,0xe6,0x75,0xc0,0x43,0xa2,0x1c,0x7a,0x85,0xdf,
    918      0x34,0xab,0x57,0xa8,0xf6,0xbc,0xf6,0x84,0x7d,0x05,0x69,0x04,0x83,0x4c,0xd5,
    919      0x56,0xd3,0x85,0x09,0x0a,0x08,0xff,0xb5,0x37,0xa1,0xa3,0x8a,0x37,0x04,0x46,
    920      0xd2,0x93,0x31,0x96,0xf4,0xe4,0x0d,0x9f,0xbd,0x3e,0x7f,0x9e,0x4d,0xaf,0x08,
    921      0xe2,0xe8,0x03,0x94,0x73,0xc4,0xdc,0x06,0x87,0xbb,0x6d,0xae,0x66,0x2d,0x18,
    922      0x1f,0xd8,0x47,0x06,0x5c,0xcf,0x8a,0xb5,0x00,0x51,0x57,0x9b,0xea,0x1e,0xd8,
    923      0xdb,0x8e,0x3c,0x1f,0xd3,0x2f,0xba,0x1f,0x5f,0x3d,0x15,0xc1,0x3b,0x2c,0x82,
    924      0x42,0xc8,0x8c,0x87,0x79,0x5b,0x38,0x86,0x3a,0xeb,0xfd,0x81,0xa9,0xba,0xf7,
    925      0x26,0x5b,0x93,0xc5,0x3e,0x03,0x30,0x4b,0x00,0x5c,0xb6,0x23,0x3e,0xea,0x94,
    926      0xc3,0xb4,0x71,0xc7,0x6e,0x64,0x3b,0xf8,0x92,0x65,0xad,0x60,0x6c,0xd4,0x7b,
    927      0xa9,0x67,0x26,0x04,0xa8,0x0a,0xb2,0x06,0xeb,0xe0,0x7d,0x90,0xdd,0xdd,0xf5,
    928      0xcf,0xb4,0x11,0x7c,0xab,0xc1,0xa3,0x84,0xbe,0x27,0x77,0xc7,0xde,0x20,0x57,
    929      0x66,0x47,0xa7,0x35,0xfe,0x0d,0x6a,0x1c,0x52,0xb8,0x58,0xbf,0x26,0x33,0x81,
    930      0x5e,0xb7,0xa9,0xc0,0xee,0x58,0x11,0x74,0x86,0x19,0x08,0x89,0x1c,0x37,0x0d,
    931      0x52,0x47,0x70,0x75,0x8b,0xa8,0x8b,0x30,0x11,0x71,0x36,0x62,0xf0,0x73,0x41,
    932      0xee,0x34,0x9d,0x0a,0x2b,0x67,0x4e,0x6a,0xa3,0xe2,0x99,0x92,0x1b,0xf5,0x32,
    933      0x73,0x63
    934       };

  $ echo 'isprime(27788893276069724796504555675597658900595616769773727063231875314156885361379100133264804184710789407128574011804155595735704837674243828066040543912171576627544718762752948158991754559261759162739343094515270757451837630913502740443023902769553802723685440839891240497710460941757089246131322686180648463540974702859210630184042730717698427486397505787974799692901205514386555272667298045803284972074823213104807295638814082142694729938965663710648170010420323923305528998108799706139846097432481556448740855888110797022123731105964852194684036975049177742094726795060211226322344210328442014189175085444396370522979)' | gp -q
  1

The original error could have been checked with a quick code review verifying that the provided number was in fact prime. This should have been done when the original patch was submitted.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by 542458 on Monday February 01, 2016 @05:28PM (#11016103)

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

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by gus_massa on Monday February 01, 2016 @06:45PM (#11016618)

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?)

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by lifthrasiir on Monday February 01, 2016 @07:51PM (#11016960)

I've tested some of them with PARI/GP. There is no probable prime with the Hamming distance 1. There are several (probably 3--400, haven't exhaustively listed) probable primes with the Hamming distance 2 (p ^ (1<<30) ^ (1<<14) is one example).

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by bonzini on Tuesday February 02, 2016 @04:57PM (#11022994)

About 1 in 700 1024-bit numbers is prime. There are 1023512 Hamming-distance 2 numbers for a 1024-bit number, about 750 of them will be prime.

If you found no Hamming distance 1 primes (expected: 0.68) and 3-400 Hamming distance 2 primes (expected: 750), this is one really* bad "prime"...

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by kazagistar on Tuesday February 02, 2016 @12:21PM (#11020803)

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?

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by 3JPLW on Monday February 01, 2016 @02:59PM (#11014898)

The change log message that introduced the new constant is interesting, too. "Socat did not work in FIPS mode because 1024 instead of 512 bit DH prime is required. Thanks to XXX for reporting and sending a patch."

I wonder what prompted the review a year later.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by rlpb on Monday February 01, 2016 @03:25PM (#11015117)

Not just a quick code review; it should be a build time assertion.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by codeulike on Monday February 01, 2016 @03:38PM (#11015195)

I dont think that testing whether huge numbers are prime or not is quite as easy as you assume.

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

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by alextgordon on Monday February 01, 2016 @03:52PM (#11015326)

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 different kinds of numbers.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by CamperBob2 on Monday February 01, 2016 @04:19PM (#11015548)

It might be "easy" but is it quick enough to be tolerated as part of a build?

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by anderskaseorg on Monday February 01, 2016 @05:14PM (#11015992)

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

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by lorenzhs on Monday February 01, 2016 @04:29PM (#11015612)

The primality test of the original number using gp that archgoon posted takes 6ms on my Sandy Bridge laptop, that's plenty fast. (The new number takes a minute to check, though, so that might really be too long)

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by sdhsdh on Monday February 01, 2016 @04:48PM (#11015765)

Maxima's primep takes 360ms on the 1024-bit one for me, so seems quick enough to stick into the build.

It sounds like the chance if it passing the test is around 10^-15 using the default values; which seems sufficient for a build test which is run many times.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by jldugger on Monday February 01, 2016 @06:35PM (#11016559)

If this the alternative, it very well might be.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by leni536 on Tuesday February 02, 2016 @04:30AM (#11018461)

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

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by CamperBob2 on Monday February 01, 2016 @04:17PM (#11015531)

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.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by bigiain on Monday February 01, 2016 @05:27PM (#11016093)

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

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by cperciva on Monday February 01, 2016 @06:38PM (#11016577)

Extra bytes would have made it not a 1024-bit integer.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by gertef on Monday February 01, 2016 @09:10PM (#11017259)

Whicgh provides an excuse for why the prime was truncated, and OOPS made it into a not-prime.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by cperciva on Monday February 01, 2016 @05:27PM (#11016096)

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

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by CamperBob2 on Monday February 01, 2016 @06:05PM (#11016369)

(Actually I may be confusing the extra comma here with an extra comma at the end of an enum list. Some compilers are OK with that, while others aren't.)

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by 1amzave on Tuesday February 02, 2016 @02:41AM (#11018096)

If I'm reading N1256 right (not sure how far back it actually dates, but that's a C standard draft dated 2007), section 6.7.2.3 also explicitly allows a trailing comma in that context as well, so if such a compiler exists its makers should get with the program, so to speak.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by xnyhps on Tuesday February 02, 2016 @04:00AM (#11018355)

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

[ Parent | on HN ]