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

61–70 of 199 posts

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

#61

Post by wanderfowl »

wanderfowl wrote: post #59
jcoffland wrote: post #38

Earlier quoted context omitted.

Aren't large non-primes usually created by multiplying two large but smaller primes together. Factoring is then the challenge. Or is there more to this that I'm missing?

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…

Then again, this is wholly academic. It's not like, if it's A, the committer is going to say "yup im NSA u caught me lol."

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

#62

Post by nisa »

duaneb wrote: post #41
phkahler wrote: post #34

Earlier quoted context omitted.

>> I always wonder if when things like this get found, there's someone in the NSA going "Wow they finally found it, only took them x years" I would guess they were aware of the problem weather they created it or not. So yes.

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

> 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 said I doubt they'll have very good mathematical attacks as a lot of researchers look at this stuff but implementation bugs, side channel attacks and plain bugs are plenty.

most of the world runs openssl or CryptoAPI - why not spend a few man years looking through these implementations?

Well at least if I where them I'd have some programmers to come up with automatic bug finding techniques and fuzz the hell out of existing applications.

They also likely don't care about your encrypted facebook chat but government infrastructure, mobile telecommunication providers and lots of important enterprises are probably pretty often on their "we need to get in list" if you can decrypt captured encrypted traffic - I imagine this would be a huge net win.

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

#63

Post by sova »

wanderfowl wrote: post #61
wanderfowl wrote: post #59

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

Then again, this is wholly academic. It's not like, if it's A, the committer is going to say "yup im NSA u caught me lol."

it is the same clear path as unix vs closed source research. perhaps there will be some achievements privately, but all mind and matter is interco-mingled already and forever. secrets are just another way of saying "obscure path" ... feels?

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

#64

Post by makmanalp »

defen wrote: post #55
matthewaveryusa wrote: post #49

Earlier quoted context omitted.

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

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.

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

#65

Post by mabbo »

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 the time which should be enough to raise an alarm of a problem.

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

#66

Post by duaneb »

nisa wrote: post #62
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.

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

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

#67

Post by duaneb »

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.

Definitely agree with this.

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

#68

Post by sdhsdh »

lorenzhs wrote: post #60
CamperBob2 wrote: post #53

Earlier quoted context omitted.

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

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)

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.

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

#69

Post by nothis »

matthewaveryusa wrote: post #49
mrb wrote: post #37

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

There's one in a thousand chances and there's 1-2^-80 chances. Wouldn't that be some "electrons in the universe" level coincidence? Believing in that borders on religion.

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

#70

Post by eli »

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.

I get what you're saying, but 2^-80 is very VERY improbable. Hitting it once is equivalent to a merely "very unlikely" event like winning powerball happening multiple times in a row.
Post reply on HN