3

A. K. Lenstra et al. in an extensive examination of the RSA moduli employed in practice (http://infoscience.epfl.ch/record/174943/files/eprint.pdf, p.10) wrote that they "could not explain the relative frequencies and appearance of the occurrence of duplicate RSA moduli and depth one trees" found in their study.

How could the high security risks arising from this direction be effectively countered in the current actual practice of RSA applications on the Internet?

Having in the past done two implementations of AES, I have with surprise just learned in another community that NIST has, in addition to the (known-answer) tests in Appendix C of FIPS-197, issued a document specifying a very much more comprehensive test suite, with which an accredited laboratory could (independently) certify the correctness of a vendor's implementation in a variety of application scenarios, i.e. not merely the straightforward transformation of a block of 128 input bits to the corresponding output bits with a given 128/256 bit key. See csrs.nist.gov/groups/STM/cavp/documents/aes/AESAVS.pdf. Now, even a commercial AES software with some added nice features is apparently very much smaller in size and simpler in programming logic and organization than the currently in practice used diverse open-source or closed-source packages that support the employment of RSA for the purpose of achieving communication security of the end-users on the Internet. When it is thus deemed desirable/necessary to highly carefully verify the correctness of an AES implementation, how much MORE efforts in comparison should therefore sensibly need to be done to ensure the correctness of RSA software, and that EXTREMELY urgently in view of the high security risks mentioned above?

Efficiency is naturally one of the desiderata of any software. However insecure IT-security software is evidently useless, no matter how fast it runs. There are of course applications where achieving extremely high speed is very essential, e.g. automatic stock trading where some financial firms have located their computing centres as near as possible to the stock exchange markets in order to gain the advantage of being able to put orders some microseconds earlier than their competitors and recently a tower is said to be planned to be built in London to realize fast microwave direct communications with corresponding locations in Europe for that purpose. Nevertheless I strongly believe it is generally acceptable for the absolute majority of the commen end users in case e.g. a web page needs one second longer to pop up on their monitors than it currently is, if the security of the applications could be rendered much more secure thereby, e.g.via use of open-source software that are certified by publically trusted institutions. (Note on the other hand that we could let e.g. the above mentioned financial firms develop their own special communication hardware/software and be accordingly responsible for the security of the use of their own products.)

Obviously it isn't difficult from the viewpoint of software engineering to specify (similarly to the case of AES and AESAVS) an RSA key generation program unit that has a standard interface to its environment. If this is ISO standardized, implementations could be certified independently by national standardization bodies and/or IT professional associations of diverse countries of the world. While there is nothing 100.00% perfect in the real world (excepting certain mathematical theories that are logically impacable, though still contingent on their axioms), the trustworthiness of such implementations will obviously become higher, when their number of certifications obtained increases. In this situation, at least a common end user doing encryption/decryption of his personal communications could easily have a choice for his RSA key generation between such a certified implementation (which may be not very efficient) or another implementation that is not certified but more efficient and with lots of convenience features.

There are certainly a vast number of applications where CAs are practically necessarily to be invoved. This leads to the IMHO verily difficult issue of trust on the CAs (their cooperations with one another, the faithfulness and correctness of the work of their employees, attempts of third parties to excercise different malicious influences on their work, etc.) However, if the goal sketched in the preceding paragraph could be satisfactoriy achieved, then that's already an extremely essential achievement in countering the security risks currently facing the common end users resulting from the phenomenon of shared prime factors among RSA moduli employed in practice. Improvements in the issues related to the CAs could be strived at simultaneously, but preferrably with a comparatively lower priority in my personal opinion.

[added on Jan 10, edited on Jan 12:]

A possible cause of the phenomenon reported by Lenstra et al. could be that a certain non-open-source RSA key generation software employed in practice contains a backdoor. With PRNGs it is namely very simple to specifiy a set of N prime numbers (without having to explicitly store them in the software) to be pseudo-randomly selected for use in an RSA key generation session. N could be chosen by the malice to his advantage to be fairly large without causing difficulties to his purposes. For the set of N prime numbers can be all pre-generated by him, forming a list at his disposal to probe a given RSA modulus in order to find his prime factor in case the modulus happens to have been generated by the RSA software that contains his backdoor.

It may be remarked that backdoors of the genre of the preceding paragraph is actually of a comparatively simple nature. More sophisticated and practically impossible to be detected backdoors in non-open-source RSA key generation software are conceivable. One idea of designing such backdoors, sketched by maartin decades ago, was recently explained by me in details in the Epilogue of a software of mine (PROVABLEPRIME, http://s13.zetaboards.com/Crypto/topic/7234475/1/). The security risks stemming from this direction are IMHO much more hideous and lie clearly beyond the feasible realm of studies of the art of Lenstra et al.

3

Shared prime factors result from poor random number generation, they aren't a specific risk of their own. An RSA key is generated by generating two random numbers of the desired size and trying again until the numbers have suitable mathematical properties, including them being (probably) prime. RSA keys with shared prime factors is just one symptom of a bad RNG that's relatively easy to notice in a mass study.

AESAVS is part of CAVP, which is the US validation program for cryptographic algorithms. You seem to be rather mistaken as to what this validates. CAVP only validates that the algorithm is implemented correctly; it is not concerned about things like key generation or resistance to attacks such as side channels. There's another validation program for systems that use cryptography, which includes the validation of key generation: CMVP. The CMVP process includes CAVP for the algorithms that the system uses, but also other requirements such as relying only on NIST-approved algorithms. Passing CMVP gives what is known as a FIPS 140-2 certificate.

Unlike algorithm correctness validation, which is purely mechanical, the validation of cryptographic systems requires human review. Random number generation involves two parts: a mathematical way to generate a stream of bits from a seed (a pseudorandom number generator (PRNG), also known as deterministic random bit generator (DRBG); and a way to generate a seed that nobody can predict (entropy generation). A PRNG can just be picked from an approved list such as SP800-09A, but entropy generation is a difficult problem, and it's in particular difficult to test that you're doing it right. While there are mathematical tests to estimate the entropy of a source, they are insufficient: a source can be random-looking but predictable, and that's no good for security. And testing the system as a whole (to catch bugs such as not making correct calls to the RNG in the key generation code) is not really feasible (again, most bugs can only be found by knowing the design, not just by seeing the output); this is also a very difficult problem for static analysis, and requires human review.

The best way to ensure that your system has a good entropy source is to rely on someone else to solve the problem for you. If you're an IT manager, the operating system vendor should provide methods to gather entropy and provide it to applications. (Linux, Windows, OS X, etc. all do.) If you have high security requirements, ensure that your systems have access to (and make use of) hardware entropy sources, such as RdRand on modern Intel processors, or a separate hardware component (for example a smartcard). Of course, bugs can happen, so keep up with security updates and take care when more remediation is required than just installing the updates. The main problem is devices sold as appliances where you don't get to look inside; then you pretty much need to rely on the reputation, certifications or guarantee of the vendor. If you're an application vendor, always seed your PRNG from the operating system (/dev/random or /dev/urandom on most Unix variants, CryptGenRandom on Windows, etc.).

  • I don't yet fully understand your 1st paragraph. If a common end user employs a certain RSA modulus n, how could he check that n doesn't have a shared factor with the enormously huge number of RSA moduli used by others? (Further, a common end user normally practically doesn't have any direct control over RSA involved in the applications that render services for him, if I don't err.) – Mok-Kong Shen Jan 7 '16 at 13:59
  • @Mok-KongShen It is not really practical to check one modulus against all the other moduluses in existence. Rather than tackle the problem at this level, it is easier to ensure that the modulus was randomly generated using a properly working crypto-strength RNG (like /dev/urandom on Linux or CryptGenRandom on Windows, subject to proper seeding which would be room for a whole other question (which we may well have on the site already)). A randomly-generated key does not share any factors with any other key. – Gilles Jan 7 '16 at 15:43
  • The problem is IMHO that how could a common end user, directly or indirectky, of an RSA modulus know whether that's risky or not. He just (1) uses a popularly recommended software to obtain his RSA keys without detailed knowledge of the software or criteria of selection of options, or (2) he uses the service of an application that depends on RSA but has no influence at all to have that application to choose to use a particular RSA software in a particular way. – Mok-Kong Shen Jan 7 '16 at 19:02
  • @Mok-KongShen You cannot tell from the RSA modulus (not without doing a massive study like the one you read). You need to rely on the application doing it correctly, just like you're relying on it implementing RSA encryption or verification correctly, on not uploading a copy of all the data it sees to archive.org, etc. – Gilles Jan 7 '16 at 19:25
  • 1
    @Mok-KongShen Go by the reputation of the provider of the software. You have to go by this for everything else, why are you looking for something specifically about one aspect of key generation for one particular kind of key? Once again: you cannot evaluate a correct key generation process by looking at the generated keys, you have to look at the process. This holds for RSA keys and every other kind of cryptographic key. – Gilles Jan 8 '16 at 15:32
1

The cause of distinct keys with shared primes is

  1. The PRNG is poorly seeded in the first place
  2. Additional unpredictable input is gathered and fed to the PRNG during key generation.

If the PRNG was just seeded badly at the start but no additional unpredictability is fed in later you would expect duplicate keys. Different seed values (even if selected from a small set) would be expected to produce keys that differed in both primes. That is bad but it still means an attacker has to figure out a lot about your system (or obtain a copy of your system) to duplicate the key.

but if additional input with some degree of unpredictability is fed in afer the first prime is generated (either totally predictablly or with a small ruange of possibilities) then you can get a case where the first prime is the same but the second prime differs. At that point someone who is in posssention of both public keys can derive the private keys by running GCD on the two moduluses to obtain the shared prime and then dividing the moduluses by the shared prime to get the other primes.

Unfortunately openssl suffered (no idea if it still does) from point 2, they repeatedly crunched the time in seconds into the random number generator during key generation.

Generating keys in first boot scripts on embedded devices provided the perfect storm of conditions needed to generate keys with duplicate primes. The boot process was predictable enough to leave the RNG poorly seeded. The system clock was also left in a predictable state (either uninitialised or set to a well-known value). Slight timing variations could lead to the time in seconds "ticking over" to a new value at slightly different points in the key generation process thereby leading to the second prime changing while the first remained the same.

IMO the main mitigation is to treat any key generated in a "first boot script" as suspect. Keys generated on long running systems that interact with users and/or with the outside world should not be affected.

If you must generate keys in a first boot script you should take steps to explicitly seed the operating system's random number generator from either a hardware random number generator or an external source of randomness before performing key generation.

Some more info at https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs/

  • I have just added a little bit to my OP and would appreciate your comment to that, if any. – Mok-Kong Shen Jan 9 '16 at 14:42
  • I personally doubt the claim in the reference you gave that "this problem mainly affects various kinds of embedded devices". Anyway, the paper of Lenstra et al,.doesn't mention differences with respect to application fields, if I don't err. BTW, IMHO much more panic actually deserves the issue of potential highly sophisticated backdoors of the genre mentioned in my OP, since their presence couldn't be detected by the method employed by Lenstra et al. – Mok-Kong Shen Jan 10 '16 at 12:46
  • Does anyone happen to have a link to the full paper of the authors of the above link that, according to what they wrote, should have followed the materials published there? – Mok-Kong Shen Jan 11 '16 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.