As you may or may not know, No Such lAbs (trading on MPEx as S.NSA) has been for a while using BISP hardware to run Phuctor, a RSA key factorization service.
As you can see, it employs bleeding edge Greek technology from 2`500 years ago, in the shape of Euclid's GCDi to try and find common factors among keys. Since there's about 4 million keys (a little under) in the bundle of publicly known keys that it is processingii, if you're even vaguely mathematically literate and even marginally aware of what exactly theoretical RSA promises, you would on the strength of this introduction expect a key to be factored just a little before Elvis comes back as the Queen of England. So did we. So did everyone else.iii
Imagine my surprise, and Stan's surprise, and everyone's surprise - including your own once you find that yes, it has broken a pair of keys.
And it didn't even need the whole 4 million set - only a shade shy of 200k. If we were to liniarly extrapolate - which we won'tiv - that'd mean we'll see dozens more before all of this is said and done.
And it's not even an ancient 1024 bit key. No, it's a spiffy, relatively recent 4096 bit key, made 2011-09-22 and owned by someone in all likelyhood you know, or at any rate have heard of. Yes, that's right - the key's in the GPG strong set.
It is our sad duty to inform Mr. H. Peter Anvin (hpa) that his key with fingerprint 51EA B526 D875 4202 2AA1 BC85 E99E F4B4 5122 1121 is factorizable. And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77. Way, way, way too small to be appearing here. How exactly it got past Pollard-rho and why exactly is 231 a factor in RSA keys is beyond the scope of this writing and sadly something we had not the time to investigate.
Which brings us to the most bitter part of this entire discussion : the server hosting phuctor suddenly became inaccessible yesterday. It returned, apparently untouched, after the DC rebooted it. While this may be simple coincidence, we have at the present time no way to ascertain whether it is or it is not. Consequently, the originally intended, civilised process of emailing the victim, keeping things quiet for a while to give them time to update and so on is not practicable : for all we know others unknown are at the current time in possession of the same information we have. On the balance of these considerations, it is my decision that all this must be published immediately, with apologies to everyone on the receiving end.
Nevertheless : emergency testing of all deployed RSA key generators must be undertaken now, to verify why exactly they would produce weak keys. Of special interest is, of course, the mechanism employed by Mr. Anvin himself, but one should not limit himself to that alone.
Let the scramble begin!
Update : Another pair was found. This also has one member in the strong set, but its owner is, apparently, luckier.
Update II : Amusingly enough, it seems Hacker News hand-diddled their story list to remove this discussion. Way to go Ydumbinator crew!
Update III : Because half the interest seems to be for some reason along these lines - here, that's how being on popurls, twitter etc looks like :
The server load was never above 0.5 ; Apache (unoptimized) chuggling quietly along, really nothing sensational to report. Even with all the software rot, hardware has progressed sufficiently since a decade ago so as to render "slashdotting" a historical relic rather than a fact of life. So it goes.
———
- Incidentally, not that many algorithms over two thousand years old are still efficient, today. Remarkable, isn't it ? [↩]
- Speaking of which - thanks a lot Gnu PG for making archival retarded. [↩]
- 50:1 odds against is a pretty decent approximation of "never", seeing how what that says is "50 or more". [↩]
- We won't because liniar approximation never fits this. It's either one exponential or the other : before anything is found, it's exponential one way, but after something is found it becomes exponential the other way. In short, it would not particularly surprise me at this point if we find thousands, not dozens. [↩]