7 ms·

It 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

by mrb 11y ago

It 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/281d1bd6515c2f0f8984fc168fb3d3b91c20bdc0 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 http://bugs.xenproject.org/xen/bug/19 So why has Gerhard seemingly not asked Zhigang how he created the parameter?

matthewaveryusa 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. 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.
  - 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.
malandrew 11y ago
What's worse, a 512 bit DH prime or a 1024 not-quite-prime?
__mbm__ 11y ago
# 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, 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 = mpz(0) # Edit: should be zero, not 1 for num in p_list: p = (p << 8) + num print("Q: Is p a prime?\nA: %s" % (is_prime(p) and 'Yes' or 'No'))
- schoen 11y ago
  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)
  - __mbm__ 11y ago
    Thanks for the edit. Of course an even number isn't prime ;)
    - cperciva 11y ago
      There is one even prime. ;-)
      - StavrosK 11y ago
        And one even primer.
droithomme 11y ago
> Here is a message he wrote In that Zhigang explicitly states that "I don't have enough knowledge to implement the merge." Yet the code is accepted without the slightest review whatsoever.

by mrb 11y ago

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

malandrew 11y ago

What's worse, a 512 bit DH prime or a 1024 not-quite-prime?

__mbm__ 11y ago

# 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, 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 = mpz(0) # Edit: should be zero, not 1 for num in p_list: p = (p << 8) + num print("Q: Is p a prime?\nA: %s" % (is_prime(p) and 'Yes' or 'No'))

schoen 11y ago
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)
- __mbm__ 11y ago
  Thanks for the edit. Of course an even number isn't prime ;)
  - cperciva 11y ago
    There is one even prime. ;-)
    - StavrosK 11y ago
      And one even primer.

droithomme 11y ago

> Here is a message he wrote In that Zhigang explicitly states that "I don't have enough knowledge to implement the merge." Yet the code is accepted without the slightest review whatsoever.