>there is no indication of how these parameters were chosen
Is there really no protocol used in projects undertaken by the security community that would ensure that each component of the tools we rely on has a known history?
Socat: “the hard coded 1024 bit DH p parameter was not prime”
31–40 of 199 posts
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#32Q: 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 (…
>> 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 of it IDK.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#33Earlier quoted context omitted.
But once you have the factorization for p, since it's hardcoded, it's now much easier to break every DH key exchange used by this application. Getting that factorization would be very very difficult, but once you have it you can use it on everyone.
if it's not an easy factorization => it will be hard. According to recent results we believe state-sized adversary should be able to do it. If you're threat model is against criminals, then you might be OK. EDIT: if 1024bits factorization is easy in general, you can say goodbye to every 1024bits RSA modulus. My first statement doesn't mean it can never be easy, it means that if you try and factor it the easy way and…
Well, it isn't known who provided the number in the first place. Whoever that unknown party is presumably knows the factorization they used to construct p. This could be a state, or could be a criminal enterprise. Better not to trust it!
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#34I 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 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.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#35Nice catch. Now, the real question is who committed it, and how they came up with the number.
If it is a backdoor, it's pretty smart, because it's very deniable as a "stupid mistake". And if it's a stupid mistake, it's extra stupid, because this committer will have trouble convincing the world that that's all it was. At the very least, somebody needs to be going through all this person's commits with a fine-toothed comb.
The methods of handling situations like this in the face of a known threat is going to be interesting. You hate to ban or hinder a good programmer from a project, but once possibly-bitten, twice shy.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#36Earlier quoted context omitted.
Just because there are exact tests doesn't make the AKS primarily test usable in the real world because of constant factors . Using Fermats little theorem for primality testing is fine because the probably of encountering a Carmichael number is very low.
You're right, AKS is not a very efficient algorithm and randomized tests are generally good enough. But, there are exact tests which do run fast in practice, such as ECPP. Here's some of the largest primes found using ECPP: http://primes.utm.edu/top20/page.php?id=27 Note the largest there is 30,950 digits, which is about 102,813 bits unless I did my math wrong, so I bet it is usable for 1024-bit numbers. Non-exact me…
That does seem pretty efficient for numbers of this size; thanks for the example!
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#37It 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/commitdiff/281d1bd6515c2f0f8984f...
The commit message reads: "Socat did not work in FIPS mode because 1024 instead of 512 bit DH prime is required. Thanks to Zhigang Wang for reporting and sending a patch." So a certain Zhigang Wang presumably chose this prime. Who is he?
Apparently he is an Oracle employee involved with Xen and Socat. Here is a message he wrote: http://bugs.xenproject.org/xen/bug/19
So why has Gerhard seemingly not asked Zhigang how he created the parameter?
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#38Nice catch. Now, the real question is who committed it, and how they came up with the number. If it is a backdoor, it's pretty smart, because it's very deniable as a "stupid mistake". And if it's a stupid mistake, it's extra stupid, because this committer will have trouble convincing the world that that's all it was. At the very least, somebody needs to be going through all this person's commits with a fine-toothed c…
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?
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#39Q: 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 (…
>> 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.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#40Earlier quoted context omitted.
Not just a quick code review; it should be a build time assertion.
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
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.