Phuctor: The RSA Super Collider.


I. What is RSA ?

RSA is a method for asymmetric cryptography that relies on some properties of numbers.

Asymmetric-key systems are the only practicable way for people to exchange secrets on the cheap. The alternative, absent these, is using OTPs (One Time Pads) which require sharing a secret in the past, and keeping it secret in the present, to be able to share a secret in the future.

The properties of numbers in question boil down to it being a lot easier to compute the product of 11, 13 and 17 than to find the factors that compose the number 2`431.

Various larger entities (such as government agencies), jealous of the fact that RSA allows private persons to exchange secrets safely and with minimal expenditure have been working hard and for many decades to weaken this cryptographic system as much as possible, and to destroy it as soon as possible. Part of their efforts is the push towards Elliptic Curve Cryptography (ECC) to replace RSA, in spite of obvious mathematical weaknesses in this proposition. Part of the same efforts have been the numerous and diverse implementation flaws, so that the promise of mathematics is not realized by the capabilities of the available software.

II. What is an RSA key ?

An RSA public key consists of a modulus N and an exponent e.

A typical GPG public key contains one or more RSA moduli, depending on the number of sub-keys.

III. What is the modulus ?

The modulus, aka N, is a product of two large primes, p and q. If one knows p or q, one can derive the private key corresponding to the given public key.

The security of RSA depends on the size of N. Particular cases have been studied, and specific estimations as to their strength are publicly known and generally accepted. This is the meaning of "4096-bit key" or "1024-bit key" : that N is 4096, or 1024 bits long, i.e. about 1200 or 300 decimal digits respectively.

It is for, instance, known that a ~700-bit RSA key is not safe, because publicly known examples of factored Ns of that size exist. It is probably the case keys of 1024 bits and under are not safe in front of concerted effort by a state actor ; 4096-bit keys, however, are safe in all cases. If correctly generated, their hardness exceeds the computational resources of the entire known universe, 200 billion galaxies and all.

The danger of a factored N is that if an adversary knows some of the factors, that adversary is therefore able to chisel away at the strength of the encryption. What the user would consider a 4096-bit key and therefore safe may in practice work as a merely 512-bit key - and therefore is not safe at all.

As a general rule, it is reasonable to expect that moduli with small factors were in all cases generated by buggy software ; whereas moduli with recurring large factors were generated by subverted software.

IV. What is the exponent ? Why should the exponent be prime ?

RSA relies on the observation that it is practical to find very large positive integers e, d and N so that modular exponentiation of an arbitrary quantity m to the power of e to the power of d equals m modulo N ; while knowledge of m, e and N does not allow an adversary to easily compute d. In this formula, m is the message ; e is a known exponent, part of the public key ; N is the modulus, also part of the public key, whereas d is the secret key, obtained as (p-1)*(q-1).

There's no requirement per se, mathematically, for e to be prime. E must be coprime with phi(N), because otherwise encrypted messages can no longer be singularly decrypted (ie, the decryption process allows multiple ambiguous solutions).

In practice, it is a lot cheaper to pick a prime exponent than to check and make sure the exponent shares no factors with phi(N), much like in practice it is a lot cheaper to not drive through the swamp than to clean your car after you have. For this reason, a key using a nonprime e is generally an indication of subversion of the cryptosystem implementation on other levels, and should be seriously investigated - much like a person who actually prefers driving through swamps probably has other issues as well.

Keys with very low e (such as e=3) were used in the past, but are generally considered bad practice today. For a number of reasons, e=65537 is standard.

V. What does Phuctor do ?

Phuctor looks for factors of known RSA keys through two methods, which are related.

The first is to try to find the greatest common divisors of pairs of moduli, through a refined version of Euclid's algorithm.

The second is to try to find common divisors of individual moduli paired with a very large composite of all primes (primorial) up to a certain value, known as the "8ball". Phuctor is continuously adding primes to the 8ball ; sometime in May 2016 it passed the 10th million prime (which is to say that at that time, the 8ball consisted of the product of the first ten million prime numbers).

Phuctor also looks for specific problems with keys, such as nonprime or nonstandard exponents, as indicative of problems with the RSA implementation that generated them.

VI Does Phuctor notify the key owners if it finds anything ?


VII. How cool is that Hanno Böck dude ?

Hanno Böck is a deceitful shitbag.

VIII. But I heard that most of the phuctored keys won't import into GPG!

Various broken PGP clients are more than happy to eat public keys with invalid self-signatures.

IX. Phuctor broke my key! How will I live now?!

See here.

X. I demand that you remove this here key from Phuctor!

No. And get lost.

XI. What can I do with Phuctor ?

You can submit an RSA key to determine if any of its moduli share a common factor with with the moduli of public keys already in our database.

You can follow the notifications of broken moduli and other issues in #trilema.

It is possible you might also be able to help ; if you think this may be the case, please see the contact page and get in touch.

XII. Where does Phuctor get RSA keys from ?

Originally we started with people adding keys manually. A complete SKS dump was added in 2015. A complete dump was added in 2016. A dump of RSA SSH keys off GitHub, as well as a complete ssh-keyscan of the entire ipv4 space were added in 2018, and we're exploring other sources. As of August 2018, SSL pubkeys from a scan of the entire ipv4 space are being entered.


No Such lAbs wishes to thank:

No Such lAbs

Pizarro ISP