9 ms·

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, t

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_prime.html https://www.openssl.org/docs/manmaster/crypto/BN_generate_pr...

defen 11y ago
2^-80 is an incomprehensibly tiny number. Malice or incompetence are both FAR more likely.
- wtbob 11y ago
  > 2^-80 is an incomprehensibly tiny number. When one wants a 128-bit security margin, 2^-80 is 2^48 times too big.
  - mrb 11y ago
    This is not a valid comparison. An attacker who can bruteforce, say, 2^80 128-bit keys (approximate limit of the computational power of the largest adversaries) has 1 chance out of 2^48 to break the security. But an attacker has only 1 chance out of 2^80 that this parameter is a non-prime. 2^80 is much larger than 2^48, therefore it is not a problem.
    - wtbob 11y ago
      It's not about bruteforcing. If I want a 128-bit security level, I'm willing for a random guess of my key to have a 2^-128 chance of being correct. I'm likewise willing for a prime I generate to have a 2^-128/uses chance of not being prime (where uses is equal to the number of times I'll actually be using it). I can't be 100% certain that a large number is actually prime. But I can be certain enough. Having a 2^-80 chance of being wrong isn't good enough when I want a 2^-128 security level.
      - mrb 11y ago
        Yes, security margins are all about what can and cannot be brute forced! You can't compare these 2 scenarios directly, because in practice: - attackers can take as many guesses as they want against a piece of data protected by a 128-bit key, but - attackers get only 1 chance that a particular piece of data protected by a supposed prime is not a prime.
  - cperciva 11y ago
    Apples and oranges. When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken.
    - marshray 11y ago
      Most protocols do allow the attacker to choose how many times the defender must win at some game of probability. If the defender is somehow put in a situation to generate 2^80 primes, then he's in trouble.
      - cperciva 11y ago
        Sure, I'd aim for a higher security level in a "attacker can keep asking for new primes until we screw up" scenario.
    - wtbob 11y ago
      > When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken. But it also implies that e.g. the attacker has a 2^-128 chance of randomly guessing a key.
- makmanalp 11y ago
  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.
  - eli 11y ago
    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.
  - Lazare 11y ago
    We happily incarcerate and (for countries that do so) execute people based on much weaker evidence. 2^-80 is absurdly small, to the point that essentially any other possibility is more likely. You say you want to see it twice, but one data point with an error rate of 1 in 2^80 is, statistically, about a billion times more convincing than a million observations with an error rate of 1 in a million. (That being said, there are a lot of of explanations that don't involve malice, including honest error, bugs in any of the software products involved in the process, etc. But no, I don't believe that this was a 1 in 2^80 fluke.)
  - marvin 11y ago
    The likelihood of 1/2^80 is on the same order as me picking out a thousand grains of sand from the Sahara desert, spreading them randomly out through the desert and having you pick out those exact thousand grains of sand. It's a practical impossibility, a philosophical exercise.
    - xyzzyz 11y ago
      No, it's not the same order. 1/2^80 is the same order as the likelihood of as picking 1000 grains out of 1010, and I'm sure you'll agree that Sahara has more grains that 1010. However, if you picked a single grain from Sahara desert, you'll be only 2 or 3 orders of magnitude off, so one could say that 2^-80 is only slightly easier than finding a particular grain in a Sahara desert.
- smegel 11y ago
  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.
  - stouset 11y ago
    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=92851 https://blogs.msdn.microsoft.com/oldnewthing/20160114-00/?p=...
    - smegel 11y ago
      So how did it happen in this case?
- mehwoot 11y ago
  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 only expected to find a true prime in 1 every 2^80 numbers anyway, there would be a 50% chance that a number you found is prime and a 50% chance it would not actually be. https://en.wikipedia.org/wiki/Bayes%27_theorem https://en.wikipedia.org/wiki/Bayes%27_theorem
  - brianberns 11y ago
    I don't think Bayes' theorem applies very well here, because there's no practical way to check enough numbers such that the effect you're describing comes into play. 2^80 is approximately a million billion billion (10^24), so if you had a million CPUs each checking a billion numbers every second, it would still take a billion seconds (over 30 years) to check that many numbers. I suspect that's why such a small level of uncertainty was chosen in the first place.
    - anon4711 11y ago
      Why would 10^24 be a million billion billion? It's 4 blocks of 6 zeros each, so that I'd expect you to call it a billion billion billion billion, if anything.
      - jibalt 11y ago
        1 million = 10^6. 1 billion = 10^9. 6+9+9 = 24. This isn't rocket science.
  - geofft 11y ago
    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.
- mchahn 11y ago
  Marilyn Vos Savant got a question on her column I'll never forget. The answer was awesome .. Q: My friend got a perfect hand in bridge. What are the odds of this happening? A: Your friend is a liar.
marcosdumay 11y ago
Except for a possible bug, 2^-80 is effectively zero, and getting a non-prime from this routine is effectively impossible.
- fixermark 11y ago
  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 checksums in the hardware)
  - btilly 11y ago
    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.
nothis 11y ago
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.
- fivesigma 11y ago
  That would be 10^80 which is much, much larger than 2^80. Unrelated, but 2^80 isn't that astronomic when it comes to computers, considering that the entire Bitcoin network has performed 2^84 hashes.
heavenlyhash 11y ago
It would be fantastic to see this fix accompanied by a patch that adds a test that runs that primality check again. It's a check that probably doesn't need to run in CI over and over again, but boy would it be nice to have it codified so everyone reading now could reproducibly run the check if we felt the desire.
ninguem2 11y ago
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.
- nathancahill 11y ago
  Congrats, you broke HN.
  - ninguem2 11y ago
    What, how?
    - nathancahill 11y ago
      Stick the number in a code block (4 spaces at the beginning of the line). The CSS here doesn't handle long strings well.
      - deleted 11y ago
        [deleted]
mfukar 11y ago
> 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. Why would somebody use MR when there are faster sieves already running, as well as additional public lists of known large primes? Maybe they shouldn't be near primes, let alone picking them.
tika 11y ago
2^1024 is a lot larger than 2^80. The implication is clear.

defen 11y ago

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

wtbob 11y ago
> 2^-80 is an incomprehensibly tiny number. When one wants a 128-bit security margin, 2^-80 is 2^48 times too big.
- mrb 11y ago
  This is not a valid comparison. An attacker who can bruteforce, say, 2^80 128-bit keys (approximate limit of the computational power of the largest adversaries) has 1 chance out of 2^48 to break the security. But an attacker has only 1 chance out of 2^80 that this parameter is a non-prime. 2^80 is much larger than 2^48, therefore it is not a problem.
  - wtbob 11y ago
    It's not about bruteforcing. If I want a 128-bit security level, I'm willing for a random guess of my key to have a 2^-128 chance of being correct. I'm likewise willing for a prime I generate to have a 2^-128/uses chance of not being prime (where uses is equal to the number of times I'll actually be using it). I can't be 100% certain that a large number is actually prime. But I can be certain enough. Having a 2^-80 chance of being wrong isn't good enough when I want a 2^-128 security level.
    - mrb 11y ago
      Yes, security margins are all about what can and cannot be brute forced! You can't compare these 2 scenarios directly, because in practice: - attackers can take as many guesses as they want against a piece of data protected by a 128-bit key, but - attackers get only 1 chance that a particular piece of data protected by a supposed prime is not a prime.
- cperciva 11y ago
  Apples and oranges. When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken.
  - marshray 11y ago
    Most protocols do allow the attacker to choose how many times the defender must win at some game of probability. If the defender is somehow put in a situation to generate 2^80 primes, then he's in trouble.
    - cperciva 11y ago
      Sure, I'd aim for a higher security level in a "attacker can keep asking for new primes until we screw up" scenario.
  - wtbob 11y ago
    > When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken. But it also implies that e.g. the attacker has a 2^-128 chance of randomly guessing a key.
makmanalp 11y ago
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.
- eli 11y ago
  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.
- Lazare 11y ago
  We happily incarcerate and (for countries that do so) execute people based on much weaker evidence. 2^-80 is absurdly small, to the point that essentially any other possibility is more likely. You say you want to see it twice, but one data point with an error rate of 1 in 2^80 is, statistically, about a billion times more convincing than a million observations with an error rate of 1 in a million. (That being said, there are a lot of of explanations that don't involve malice, including honest error, bugs in any of the software products involved in the process, etc. But no, I don't believe that this was a 1 in 2^80 fluke.)
- marvin 11y ago
  The likelihood of 1/2^80 is on the same order as me picking out a thousand grains of sand from the Sahara desert, spreading them randomly out through the desert and having you pick out those exact thousand grains of sand. It's a practical impossibility, a philosophical exercise.
  - xyzzyz 11y ago
    No, it's not the same order. 1/2^80 is the same order as the likelihood of as picking 1000 grains out of 1010, and I'm sure you'll agree that Sahara has more grains that 1010. However, if you picked a single grain from Sahara desert, you'll be only 2 or 3 orders of magnitude off, so one could say that 2^-80 is only slightly easier than finding a particular grain in a Sahara desert.
smegel 11y ago
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.
- stouset 11y ago
  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=92851 https://blogs.msdn.microsoft.com/oldnewthing/20160114-00/?p=...
  - smegel 11y ago
    So how did it happen in this case?
mehwoot 11y ago
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 only expected to find a true prime in 1 every 2^80 numbers anyway, there would be a 50% chance that a number you found is prime and a 50% chance it would not actually be. https://en.wikipedia.org/wiki/Bayes%27_theorem https://en.wikipedia.org/wiki/Bayes%27_theorem
- brianberns 11y ago
  I don't think Bayes' theorem applies very well here, because there's no practical way to check enough numbers such that the effect you're describing comes into play. 2^80 is approximately a million billion billion (10^24), so if you had a million CPUs each checking a billion numbers every second, it would still take a billion seconds (over 30 years) to check that many numbers. I suspect that's why such a small level of uncertainty was chosen in the first place.
  - anon4711 11y ago
    Why would 10^24 be a million billion billion? It's 4 blocks of 6 zeros each, so that I'd expect you to call it a billion billion billion billion, if anything.
    - jibalt 11y ago
      1 million = 10^6. 1 billion = 10^9. 6+9+9 = 24. This isn't rocket science.
- geofft 11y ago
  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.
mchahn 11y ago
Marilyn Vos Savant got a question on her column I'll never forget. The answer was awesome .. Q: My friend got a perfect hand in bridge. What are the odds of this happening? A: Your friend is a liar.

marcosdumay 11y ago

Except for a possible bug, 2^-80 is effectively zero, and getting a non-prime from this routine is effectively impossible.

fixermark 11y ago
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 checksums in the hardware)
- btilly 11y ago
  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.

nothis 11y ago

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.

fivesigma 11y ago
That would be 10^80 which is much, much larger than 2^80. Unrelated, but 2^80 isn't that astronomic when it comes to computers, considering that the entire Bitcoin network has performed 2^84 hashes.

heavenlyhash 11y ago

It would be fantastic to see this fix accompanied by a patch that adds a test that runs that primality check again. It's a check that probably doesn't need to run in CI over and over again, but boy would it be nice to have it codified so everyone reading now could reproducibly run the check if we felt the desire.

ninguem2 11y ago

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.

nathancahill 11y ago
Congrats, you broke HN.
- ninguem2 11y ago
  What, how?
  - nathancahill 11y ago
    Stick the number in a code block (4 spaces at the beginning of the line). The CSS here doesn't handle long strings well.
    - deleted 11y ago
      [deleted]

mfukar 11y ago

> 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. Why would somebody use MR when there are faster sieves already running, as well as additional public lists of known large primes? Maybe they shouldn't be near primes, let alone picking them.

tika 11y ago

2^1024 is a lot larger than 2^80. The implication is clear.