Update: No Such lAbs reports that other Phuctored keys have valid signatures.

Update 2: More factored RSA Keys and their purported owners have been disclosed

This morning the Phuctor operated by No Such lAbs broke its first RSA key. The compromised key in question which was a 4096 bit key which had a subkey divisible by 231, which is further divisible by 3, 7, and 11. This factorization was shortly followed by two other factorizations of identifiable keys. Each identifiable key has a companion which is similarly weak but they have yet to be identified.

In the original announcement of the occasion on Trilema No Such lAbs partner Mircea Popescu disclosed that the server running phuctor had been inaccessible for some time yesterday making it possible third parties could have knowledge of the broken key and decided to publicly disclose the compromised key in question was advertised by keyservers as being a subkey attributed to Linux kernel developer Hans Peter Anvin. The two other keys factored so far belonged to programmers with one being a GNU developer, due to less uncertainty of the server's condition at the time of their factoring the vulnerability of these keys were disclosed privately to their owners.

Earlier this month the Phuctor had begun processing the contents of a dump from sks keyservers and had processed just under two hundred thousand keys before the first factorizations happened. The security of RSA keys depends not only on the total length of the key, but also upon the the difficulty of factoring the public key which ideally should only de divisible by two very large prime numbers. When a public key is capable of being factored this readily no amount total key length can offer any security at all.

Shortly after the factoring of this key was disclosed a number of parties began posting stories that supposedly debunk the key's factoring by positing explanations that vary from the key was copied incorrectly, that it was likely corrupted on the server by cosmic rays acting upon the storage medium, to the key having potentially been created or corrupted by an obscure email client only popular in Germany. Other posts have insisted that since the factored 4096 bit RSA key was so weak, it isn't really a factored 4096 bit RSA key. (local archive)

Sometime after the disclosure of the key's factorization was submitted to YCombinator's "Hacker News" the piece's rank and appearance on the site appears to have been manually suppressed, which is a very common occurrence on that social media venue.

It is potentially coincidence that two of the first factored keys belonged to open source developers, with the disclosed developer Anvin holding a prominent position in Linux development. Given how gravely weak the key was and its presence on a public keyserver, auditing the quality of RSA key generators along with the security and integrity of keyservers appears to be a task of critical emergency importance. The entire chain of processes which could have been subverted range from the key's generation to its inclusion in the contents of a keyserver.

A public key which should have never passed any sane set of checks on its generation was distributed by a keyserver. It is important to understand what failings of the keyserver could have lead to a stored key becoming corrupted into a weaker form without any meaningful error checking and correction. It is also of critical importance to identify what RSA key generating software is being distributed in a form which would allow it to offer such weak keys.

A number of 512 bit RSA public keys of 1990's vintage have been submitted to the Phuctor by myself, and they have yet to be factored by the Phuctor though a dedicated effort aimed at each key individually could readily factor them. Yet a 4096 bit key was so astoundingly weak it managed to be factored first. Whatever ends up being fingered as the most likely culprit in this incident, this highlights a number of potentially weak points in the chain of events leading to key distribution as well as the delicacy of generating quality RSA keys whose security actually reflects their key length.