Hacker News Reader

Comment by baby | Hacker News Reader

Q: How does p not being a prime => backdoor?

A: p not being a prime means two things:

* subgroup confinement attacks (where you send a public key made with a fake generator g) should be able to take place if the code is weak -> this is because there must be low order subgroups.

* the generator g might not be of great order. This can be easily tested if you know how to factor p: the order of the multiplicative group (Zp)* is the euler's totient function on p. If you know the order of the multiplicative group then you have an algorithm to find the order of your generator: you try all the divisors of the group's order, see the smallest one that works.

Unfortunately, if you don't know how to factor p then you can't easily do that.

Another question is: How can they know it's not a prime if they don't know the factorization of p? We have efficient provable tests for that: they tell you if p is prime or not and nothing else.

View on HN

p not being prime means it has not been generated using a standard tool like OpenSSL.

It's therefore likely it's been handcrafted for nefarious purposes, opening the possibility of further shenanigans.

Another possibility would be the use of a buggy generator, or a clueless dev using random bits rather than a large prime.

Or someone made a mistake copying and pasting.

Edit: wow. that is serendipity. Just accidentally posted twice. Does hitting "submit" twice do that?

> Edit: wow. that is serendipity. Just accidentally posted twice. Does hitting "submit" twice do that?

I get that a lot. I've not worked out what's causing it.

The way this post is written it sounds like you are asking these questions but then you go on to answer them. It's confusing. It took me a second read to realize you are actually not calling the weakness in to question but explaining why it really is a weakness.

edited to clarify :) thanks

> We have efficient provable tests for that: they tell you if p is prime or not and nothing else.

I think this is a typo -- the efficient general-form tests are probable rather than provable.

https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...

Keep up the tests until you have ten or twenty nines of certainty. I'd call that proof.

then you should re-read the definition of a proof.

What more are you hoping for?

Given a mathematical proof, the chance of an error in the proof is vastly larger than 10^-20.

It's clear that you haven't read it at all:

http://www.merriam-webster.com/dictionary/proof

The fact of the matter is that the sort of Platonic definition of proof that you fantasize is impossible because it depends on certainty, which itself cannot be proven. The best we can do is fail to find an error in an alleged proof.

Consider the proofreader's paradox: A proofreader can be prepared to swear, for any given page of a 1000 page book, that there are no typos on that page, but no proofreader is so foolish as to claim that there are no typos in the book.

There are exact tests that run in polynomial time, like https://en.wikipedia.org/wiki/AKS_primality_test

Just because there are exact tests doesn't make the AKS primarily test usable in the real world because of constant factors . Using Fermats little theorem for primality testing is fine because the probably of encountering a Carmichael number is very low.

You're right, AKS is not a very efficient algorithm and randomized tests are generally good enough. But, there are exact tests which do run fast in practice, such as ECPP. Here's some of the largest primes found using ECPP: http://primes.utm.edu/top20/page.php?id=27

Note the largest there is 30,950 digits, which is about 102,813 bits unless I did my math wrong, so I bet it is usable for 1024-bit numbers. Non-exact methods are much much faster of course, but when you really really need exactness it is an option.

That does seem pretty efficient for numbers of this size; thanks for the example!

Seems like a Carmichael number could be a good choice for an attacker. This would make your chances of encountering a Carmichael number quite high. You have to consider who's choosing the number. Or do I have it wrong?

Only the simple Fermat tests are vulnerable to Carmichael numbers. The test which is used in practice, Rabin-Miller, is not vulnerable to them. In fact, if you assume the extended Riemann hypothesis is true, (log n)^2 iterations of Rabin-Miller are sufficient to prove primality.

How efficient might this be compared to other approaches for searching for Riemann hypothesis counterexamples? Is there a one-to-one relationship between direct Riemann counterexamples and composite numbers that pass (log n)² Rabin-Miller tests?

I am not familiar with all the ways the GRH can be disproven, but Miller-Rabin doesn't strike me as the most efficient, with its running time of O((log n)^4) for each attempt. I am not sufficiently competent to say whether a GRH counterexample also directly results in a MR counterexample.

In addition to what pbsd said, Carmichael numbers are incredibly rare. Your odds of stumbling across one by chance are lower than the odds of a cosmic ray flipping the bit of memory that causes you to believe you have stumbled across one, as I recall.

I hate to say that a polynomial-time test isn't efficient because many people use that as the very definition of efficient, but my understanding is that AKS is incredibly impractical because the polynomial is ginormous, even though its asymptotic behavior is nice. So if you actually wanted to know if, say, a 1024-bit number was definitely prime, you wouldn't be able to run AKS on it in a "reasonable time" on a real computer.

I haven't actually studied to what extent the AKS tests are do-able. I always figured there would be no problem running one for a 1024 bits prime. Found this on SO: http://cs.stackexchange.com/questions/23260/when-is-the-aks-...

Also, to further the discussion on probable vs provable: the probable tests are enough in our case because they tell us _provably_ if an integer is not a prime (that we care), but _probably_ if an integer is a prime (which we don't care here).

This is not conclusive, but the best deterministic primality test (an AKS variant by Pomerance and Lenstra) is 6th power. 1024^6 is quite large.

They can provably tell you that a number is composite.

From your own reference (https://en.wikipedia.org/wiki/Primality_test#Probabilistic_t...): "the usual randomized primality tests never report a prime number as composite".

So I'd say that's probably what happened here (i.e p was reported composite by a randomized primality test and that would never have happened had it been prime).

Oh sure, I don't mean that there's uncertainty that this number is composite, just that in a formal sense there isn't "proof" that other numbers that passed, say, openssl -checks 100000 are prime. But I wouldn't consider it unsafe to use them for cryptography.

The comment I was replying to referred to tests that "tell you if a number is prime or not", and the probable ones don't exactly always do that. :-)

>> Unfortunately, if you don't know how to factor p then you can't easily do that.

The link says they don't know where p came from. Presumably someone constructed it as a product of primes known only to them. I don't recall the state of the art in factorization, but if 1024 bits can be factored easily that's news to me. So the weakness would only be exploitable to whomever created p.

Why nobody checked the primality of it IDK.

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 << 8) + num

  for i, prime in enumerate(primes(2^32)):
      if i % 100 == 0: print str(prime) + '\r',
      if p % prime == 0: print('\n')

Sage also has an is_prime function, which provably show that p is not prime: "is_prime(p)". This takes less than 1ms to run. Proving primality of a 1024 bit prime in Sage takes a few seconds, and for a 2048 bit prime about a minute. Sage uses PARI for this, with sophisticated elliptic curve based algorithms called ECPP("=elliptic curve primality proving"), which are non-deterministic (unlike AKS) but fast in practice and provably correct. https://goo.gl/34uxJl

Have you tried dividing the order by 271 and 13597 and search again on that?

Coincidentally, 13597 base 10 is 351d hex, which in unicode is defined as 'strong resistance'.

http://www.charbase.com/351d-unicode-cjk-unified-ideograph

271 is rather small. Which means this fake prime was quite easy to generate.

"Presumably someone constructed it as a product of primes known only to them"

It would be foolish to presume that. And knowing the factors of the Diffie-Hellman parameter isn't all that important.

Some of these issues are orthogonal.

You're correct that the ring of integers mod n with n composite will have small multiplicative subgroups. But so will the integers mod p with p prime. At the very least, 1 and p-1 will always have orders 1 and 2, respectively. I could be wrong, but I don't think the primality or compositeness of the modulus alone tells you much about the smoothness of the group order.

Small subgroups may not always lead to key recovery, but they can lead to key dictation in certain protocols. So subgroup-confinement attacks are always a consideration in this setting.

If you want to learn more about subgroup-confinement attacks on DH and ECDH, check out set 8 of cryptopals. Mail set8.cryptopals@gmail.com with subject "Crazy Flamboyant for the Rap Enjoyment".

But once you have the factorization for p, since it's hardcoded, it's now much easier to break every DH key exchange used by this application. Getting that factorization would be very very difficult, but once you have it you can use it on everyone.

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 it doesn't work... you are in for a lot of work and research.

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.

Well, it isn't known who provided the number in the first place. Whoever that unknown party is presumably knows the factorization they used to construct p. This could be a state, or could be a criminal enterprise. Better not to trust it!

Oh right. I guess I forgot this part 8)

Reply on news.ycombinator.com