Testing, Testing, Testing, 123!

Testing, Testing, Testing, 1-2-3!

Remember when Microsoft opened up a large security hole on the Internet? What you’ve forgotten about that, already? 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.

One thing I have learnt about software development is that testing and debugging often takes up the majority of my time. Why? Well, the actual coding part increasingly involves using fairly standard code and integrating libraries, but the complexity of the code often involves testing for a range of conditions. Unfortunately, a single bug in a program could thus bring down a company and even release sensitive data into the wild.

One area that I have found to be extremely weak is in the generation of random values, such as for encryption keys. While the randomization may be strong, most methods have other parameters that must be checked before the encryption keys are validated as usable. Now an interesting new paper from Daniel Shumow outlines how easy it might be to generate incorrect insecure parameters within a program, and illustrates this with RSA key generation [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. But, before we start, let’s do some of the basics of the RSA method:

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 Chinese Remainder Theory (CRT) in order to crack ciphertext. But one definite vulnerablity 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 which 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 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 which 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 in 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 key 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

If Microsoft — with all their expertise and resources - can cause a serious security vulnerability in the generation of random keys, then you can! Go test, test and test …