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

121–130 of 199 posts

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

#121

Post by gus_massa »

542458 wrote: post #91
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).

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

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

#122

Post by Coincoin »

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.

It's very easy to detect those kind of fuck ups, you just have to look for them. We don't have the mean to do it, and sometime we are just ignorant or lazy. They are neither.

We assume actual human beings need to press buttons to detect obvious developer errors. I bet if an encrypted communication with any kind of bad (or even just popular default) parameter goes through anything the NSA oversees it gets instantly attacked and put in a bin somewhere with your new software name on it. The machine probably even picks a random name for the exploit once it found one.

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

#123

Post by btilly »

fixermark wrote: post #94
marcosdumay wrote: post #57

Earlier quoted context omitted.

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

Both of those scenarios are more probable. But neither is anywhere nearly as probable as human error or human malice.

In the case of human error, it could be as simple as a bad cut-and-paste. In that case the number likely has a half-dozen or so factors, some of which should be found relatively easily.

Malice is, of course, impossible to verify.

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

#124

Post by cyphar »

digler999 wrote: post #106
mabbo wrote: post #65

Someone should really write a set of unit tests available in every conceivable language, marked as "Please copy this unit test into your test base, and use it to verify all your primes are prime". You can even make it a bit fuzzy- Miller-Rabin uses random numbers, right? So make it that every time the unit test is run it generates new random values. Your test won't be deterministic, but it will fail at least some of…

I'm aware that factoring a prime into composites is one of the most difficult computational problems, but isn't it cheap to determine if a number is prime ? a^(p-1) == a mod p (where == means "congruent to" ). with modular exponentiation isn't it simple to compute the modulus ?

The little Fermat test requires you to test all "a"s in order to remove false positives. For most numbers, testing a few thousand bases is enough but you have Carmichael numbers that break the test.

There are better primality checks, but they all have downsides (either slow but provable or fast but probabilistic). Finding prime numbers can be shown to be easier than finding factors (see: how GIMPS checks for primality), but that doesn't make it easy.

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

#125

Post by [deleted] »

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.

[deleted]

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

#126

Post by cyphar »

nicolas314 wrote: post #104
chris_wot wrote: post #95

I'm curious, is there a list of known primes held somewhere?

Pi would be a good source, but they are in the wrong order.

Pi would be a horrible source. Why would you want to use a deterministic digit generation function to generate your entropy. Even if you always used very large digit offsets. I can't imagine it being a remotely good idea.

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

#128

Post by smegel »

stouset wrote: post #97
smegel wrote: post #92

Earlier quoted context omitted.

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

So how did it happen in this case?

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

#129

Post by lifthrasiir »

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

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

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

#130

Post by Filligree »

baby wrote: post #29
Filligree wrote: post #11

Earlier quoted context omitted.

Keep up the tests until you have ten or twenty nines of certainty. I'd call that proof.

then you should re-read the definition of a proof.

What more are you hoping for?

Given a mathematical proof, the chance of an error in the proof is vastly larger than 10^-20.

Post reply on HN