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

141–150 of 199 posts

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

#141

Post by geofft »

mehwoot wrote: post #99
defen wrote: post #55

Earlier quoted context omitted.

2^-80 is an incomprehensibly tiny number. Malice or incompetence are both FAR more likely.

Assuming you are given a single number and you test it and is_prime says it is prime. If on the other hand you are looking for a number that is_prime says is prime, and you are iterating through candidates, you need to know how likely it is to find a prime number in the first place to tell you how unlikely this is. In most cases the chance of a false positive will be much, much higher than 2^-80. If for example, you…

There are approximately x / ln (x) primes below x. That means that there are 2^1024 / (1024 ln 2) - 2^1023 / (1023 ln 2) = 1.3e305 1024-bit primes. There are 2^1024 - 2^1023 = 9.0e307 1024-bit numbers. So, the chance that a randomly-selected 1024-bit number is prime is a little higher one in a thousand, that is, a little higher than 2^-10.

So Bayes' theorem doesn't save you here: it is still statistically unlikely that you will stumble upon a 1024-bit pseudoprime by mistake.

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

#142

Post by geofft »

makmanalp wrote: post #137
makmanalp wrote: post #64

Earlier quoted context omitted.

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.

Wow - this has got to be my most downvoted comment. I can't edit the original anymore, so here's my update: I guess the harsh reaction came from the fact that I didn't define the scope very well: My question wasn't in reference to M-R specifically, just in general. I understand that in this case it makes sense to look at likelier causes (see Sharlin's response). My point was that it's interesting to look at what happ…

The catch with your logic is that "The odds of any person getting struck by lightning is 1 in 10000" is sloppy phrasing. Of the number of people studied, one ten-thousandth of them got struck by lightning, but lightning does not, as you have observed, choose people at random among those 10,000. Some people are constantly indoors; some are constantly outdoors. Some live in places with frequent thunderstorms; some don't. The only way to get that 1/10000 probability is to pick a person randomly. Picking Roy Sullivan isn't random; neither is picking me.

"The probability of a randomly-selected 1024-bit number passing this primarily test without being prime is 2^-80" is a much more precise statement, because you have selected that number randomly. Obviously, if you have a specific number in mind, the probability of that number being a false positive is either 0 or 1. It either is prime, or it isn't.

Remember that there is no such thing as a random number; there is only a randomized process for selecting numbers.

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

#144

Post by Jach »

makmanalp wrote: post #137
makmanalp wrote: post #64

Earlier quoted context omitted.

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.

Wow - this has got to be my most downvoted comment. I can't edit the original anymore, so here's my update: I guess the harsh reaction came from the fact that I didn't define the scope very well: My question wasn't in reference to M-R specifically, just in general. I understand that in this case it makes sense to look at likelier causes (see Sharlin's response). My point was that it's interesting to look at what happ…

You've touched upon an old conflict. http://lesswrong.com/lw/oj/probability_is_in_the_mind/

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

#145

Post by mabbo »

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 ?

isPrime(p) is polynomial relative to the number of digits of p, but not in any useful way- takes way too long practically speaking. But that's only if you want a definite solution.

If you're willing to do a probabilistic test, you can use algorithms like Miller-Rabin- the more time you use it with random inputs the more sure you are that the number is prime. And it's relatively easy to implement- check Wikipedia for the pseudocode.

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

#146

Post by qwerty1793 »

21 wrote: post #88
pbsd wrote: post #39

Earlier quoted context omitted.

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.

Wow. 271 is a factor. Why not try dividing by all 32 bit numbers, to at least filter easy cases. Shouldn't take more than a few seconds.

The following Sage script shows that p has no prime factors less than 2^32 other than 271 and 13597:

  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, 0x03, 0xBF, 0x60, 0x9B, 0x08, 0xC6, 0x8E, 0x99, 0xC6, 0x05, 0xFC, 0x00, 0xD6, 0x6D, 0x90, 0xA8, 0xF5, 0xF8, 0xD3, 0x8D, 0x43, 0xC8, 0x8F, 0x7A, 0xBD, 0xBB, 0x28, 0xAC, 0x04, 0x69, 0x4A, 0x0B, 0x86, 0x73, 0x37, 0xF0, 0x6D, 0x4F, 0x04, 0xF6, 0xF5, 0xAF, 0xBF, 0xAB, 0x8E, 0xCE, 0x75, 0x53, 0x4D, 0x7F, 0x7D, 0x17, 0x78, 0x0E, 0x12, 0x46, 0x4A, 0xAF, 0x95, 0x99, 0xEF, 0xBC, 0xA6, 0xC5, 0x41, 0x77, 0x43, 0x7A, 0xB9, 0xEC, 0x8E, 0x07, 0x3C, 0x6D]

  p = 0
  for num in p_list: p = (p

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

#147

Post by [deleted] »

21 wrote: post #88
pbsd wrote: post #39

Earlier quoted context omitted.

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.

Wow. 271 is a factor. Why not try dividing by all 32 bit numbers, to at least filter easy cases. Shouldn't take more than a few seconds.

[deleted]

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

#148

Post by qwerty1793 »

xnyhps wrote: post #26
baby wrote: post #22

Earlier quoted context omitted.

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…

Testing for 2 seconds already found the prime factors 271 and 13597. It will probably not be hard. Edit: To add some more information, p / (271 * 13597) is still not prime, however, the library I was using didn't find any new factors in 30 minutes.

There are no other factors less than 2^32. You can see my other comment for details on verifying this.

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

#149

Post by bonoboTP »

Jach wrote: post #144
makmanalp wrote: post #137

Earlier quoted context omitted.

Wow - this has got to be my most downvoted comment. I can't edit the original anymore, so here's my update: I guess the harsh reaction came from the fact that I didn't define the scope very well: My question wasn't in reference to M-R specifically, just in general. I understand that in this case it makes sense to look at likelier causes (see Sharlin's response). My point was that it's interesting to look at what happ…

You've touched upon an old conflict. http://lesswrong.com/lw/oj/probability_is_in_the_mind/

There's no need to refer people to lesswrong for this. The interpretation of probability as a subjective degree of knowledge/evidence is well-known. For example: http://plato.stanford.edu/entries/probability-interpret/ or http://plato.stanford.edu/entries/epistemology-bayesian/

No need to spam links to that cult site.

Post reply on HN