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

101–110 of 199 posts

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

#101

Post by __mbm__ »

schoen wrote: post #98
__mbm__ wrote: post #77

Earlier 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)

Thanks for the edit. Of course an even number isn't prime ;)

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

#102

Post by CamperBob2 »

cperciva wrote: post #90
CamperBob2 wrote: post #52

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

The optional comma at the end of the list of entries in an array is explicitly allowed by the C standard.

(Actually I may be confusing the extra comma here with an extra comma at the end of an enum list. Some compilers are OK with that, while others aren't.)

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

#103

Post by brianberns »

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…

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.

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

#105

Post by marshray »

cperciva wrote: post #87
wtbob wrote: post #80

Earlier quoted context omitted.

> 2^-80 is an incomprehensibly tiny number. When one wants a 128-bit security margin, 2^-80 is 2^48 times too big.

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.

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.

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

#106

Post by digler999 »

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 ?

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

#107

Post by schoen »

chris_wot wrote: post #95

I'm curious, is there a list of known primes held somewhere?

There are plenty; see, for example

https://en.wikipedia.org/wiki/List_of_prime_numbers#External...

But you couldn't hope to list all primes up to 1024 bits.

https://en.wikipedia.org/wiki/Prime-counting_function

https://en.wikipedia.org/wiki/Prime_number_theorem

For example, there are about 2⁸⁰ primes less than 10²⁶, that is, with 26 or fewer digits. (Where could you get 2⁸⁰ bits of storage, even if you could do the huge computation necessary to check each of these?) 1024-bit primes are about 308 digits long.

You can imagine trying to get an intuition for a few different kinds of things:

* Up to what point has the primality of every number been checked?

* What is the largest general-form number whose primality has been checked conclusively? (or, what is the largest-known general-form prime?)

* What's the largest general-form semiprime that has been factored into primes without foreknowledge of the factors?

* How big are the primes we use in cryptography?

* How big are the largest-known (special-form) primes?

These things are very different orders of magnitude. I'm not sure of the exact answers to the first two, but I expect the first is below 20 digits (the π(n) calculations apparently didn't check all the individual numbers). The answers to the last 3 are: 232 digits, 308 to 1233 digits, and 22338618 digits.

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

#108

Post by ikeboy »

makmanalp wrote: post #64
defen wrote: post #55

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

https://blogs.msdn.microsoft.com/oldnewthing/20160114-00/?p=...

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

#109

Post by cperciva »

marshray wrote: post #105
cperciva wrote: post #87

Earlier quoted context omitted.

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.

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.

Sure, I'd aim for a higher security level in a "attacker can keep asking for new primes until we screw up" scenario.

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

#110

Post by ninguem2 »

matthewaveryusa wrote: post #49
mrb wrote: post #37

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/com…

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.
Post reply on HN