7 ms·

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

by defen 11y ago

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.

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

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