Novice Cybersecurity Mistakes: Why Must “e” Not Share A Factor with PHI?

Novice Cybersecurity Mistakes: Why Must “e” Not Share A Factor with PHI?

I know I have a great privilege in my work, and I know we have some of the best cybersecurity students around. And, so, yesterday, I covered public key encryption, and it was so much fun to present to such an engaged group of students.

Part of the presentation outlined the RSA encryption method, and in how to pick e so that it does not share a factor with PHI — and where PHI is (p-1) times (q-1) — of which p and q are the two prime numbers used. After the lecture, a student asked me about the selection of e, and I explained that e is always fixed (65,537), but where we should always check that our PHI does not share any factors with e. But, has this happened in the past? Oh, yes … Microsoft!

Novice mistakes

Well, it happened with one of the first releases of Windows 10, and where around 1-in-every-30K users generated weak RSA encryption keys [here]:

And so a method which is highly secure — such as the RSA public-key encryption method — could crumble by picking poor parameters, and not have the right randomization and checking.

While the paper is mostly theoretical in its scope, it shows clearly the pitfalls that someone could fall into when using security methods. This includes using the Chinese Remainder Theory (CRT) in order to crack ciphertext. But one definite vulnerability is where the public exponent e should be relatively prime to PHI, and where PHI is (p-1)(q-1). For example, to use a simple example, if e=5, and p=11 and q=7, the public modulus N will be:

N = p.q = 7 x 11 = 77

PHI = (p-1)(q-1) = 6 x 10 = 60

The RSA method says that we must select a value of e that does not share a factor with PHI, but we see that selecting e as 5 will breach this rule. We thus have a 1-in-5 chance that (p-1) will have a factor of 5, and the same for (q-1), so the probability is 2-in-5 of e sharing a factor with PHI. Here is a demo:

and here is some sample code to show:

We can recover a decryption key with [here]:

and:

Dan then creates code that will break a cipher created where e and PHI(N) share a factor [here]:

The area of padding in RSA has also been an Achilles heel for weaknesses, and Dan brings back all these threats as a warning for every development involved with security integration:

And just to show how sloppy developers can be, Dan is honest in showing that even Microsoft can drop a bomb. For this, Microsoft found that a “bad” RSA key could be generated within a reasonable amount of time:

And, to pick another real example, Don picks the problem of selecting a poor random number within RSA PKCS v1.5 padding:

Dan points out that it is important not just to test a program a few times, but to generate many iterations, in order to spot a potential problem. In the case of the Windows 10 bug, the vulnerability did not appear until 100s of thousands of RSA keys were generated. While maths and probability theory will show these, often developers do not fully analyse these in detail, and thus rely on extensive testing to show potential problems:

This gap between what a developer may see and what users will see when software is released motivates an analysis of how many test iterations are re-quired to detect bugs and limit the expected number of users affected by bugs.

In the Windows 10 bug, Dan outlines that the problem would occur in one in every 32K users, and which could be significant if scaled across every Windows user. This, he says is because the possibility of selecting PHI(N) which shares a factor with e is 2/e — the factor of two is because either (p-1) or (q-1) may have a factor of e. So as e is typically 65,537, then the probability is around one-in-32,000. Thus Microsoft had been blinding generating the modulus, forgetting that around 1-in-32,000 of the keys produced were extremely weak, and the cipher texts could be cracked.

So, go read the paper, it even ends with a method that can crack RSA being applied to a zero-knowledge proof method:

Conclusions

Test your code!

Train your engineers!

Do “crypto” properly!