This is the reason RFC 5114 exists.
Socat: “the hard coded 1024 bit DH p parameter was not prime”
111–120 of 199 posts
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#112Earlier 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...
This number (removed, as it seemed to cause problem in some browsers, sorry) fails the Fermat test for base 2 (i.e. 2^(p-1) is not 1 mod p). I can't believe it will pass Miller-Rabin. Edit: fails all bases up to 1000.
Congrats, you broke HN.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#113Earlier 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.
The NSA is old enough, and well resourced enough. Time and money solve these problems readily enough. In the case of FOSS, all you really need is a parser designed to hunt down specific sorts of flaws. We have static analysis for non-crypto needs, it seems reasonable someone at NSA got funded to write one for their use case.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#114Earlier 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?
If this the alternative, it very well might be.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#115Earlier quoted context omitted.
For anyone following along at home, you missed a D at the very end (0x6D). A number whose hexadecimal representation ended in 6 couldn't be prime because it is even. (final digit is divisible by d ←→ number is divisible by d works for any d that is a divisor of the base the number is written in)
Thanks for the edit. Of course an even number isn't prime ;)
There is one even prime. ;-)
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#116Earlier quoted context omitted.
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.
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...
Extra bytes would have made it not a 1024-bit integer.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#117Earlier quoted context omitted.
This number (removed, as it seemed to cause problem in some browsers, sorry) fails the Fermat test for base 2 (i.e. 2^(p-1) is not 1 mod p). I can't believe it will pass Miller-Rabin. Edit: fails all bases up to 1000.
Congrats, you broke HN.
What, how?
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#118Earlier 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.
My own list is of length 1 as a category of events. Back in July (it's a bit harder now), the odds that someone's calculated sha256 sum solved a new bitcoin block were around 2^-68. This very tiny probability event was observed on average once every 10 minutes.
2^-80 is absurdly small. But that only means something useful if the number of attempts isn't absurdly large.
Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#119Re: Socat: “the hard coded 1024 bit DH p parameter was not prime”
#120Earlier quoted context omitted.
# Run Miller-Rabin on the prime in the blink of an eye: from gmpy2 import mpz, is_prime 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, 0x40, 0xF9, 0x87…
For anyone following along at home, you missed a D at the very end (0x6D). A number whose hexadecimal representation ended in 6 couldn't be prime because it is even. (final digit is divisible by d ←→ number is divisible by d works for any d that is a divisor of the base the number is written in)
[deleted]