Full disclosure : 4096 RSA key in the strongset factored.
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. [↩]
Sunday, 17 May 2015
> We won't because linear 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.
Lovely delicious sigmoids.
Sunday, 17 May 2015
"We won't because liniar approximation never fits this."
"liniar"
Shit-FUCKING-listed!
Sunday, 17 May 2015
@. It's what it is.
@Kimmo Alm Maaannnn... the problems you got, seriously.
Sunday, 17 May 2015
Warning to everybody looking at the references, do not join the freenode channel #bitcoin-assets mentioned in [ii]. Doing so will result in a denial of service attack being fired at your connecting IP address, something I learned the hard way.
Sunday, 17 May 2015
There was someone with a DDoS bot in there a few months back (see http://search.bitcoin-assets.com/?q=ddos ), and for all we know this is still ongoing, so yes.
Sunday, 17 May 2015
woah if this is still ongoing regarding the ddos bot what you propose ?
Sunday, 17 May 2015
this guy pawning himself off like some crypto-whiz when someone else found this key first...
not to mention, this doof can't even spell 'linear'
Sunday, 17 May 2015
If you have money, use a strong VPS. If you don't, go in #freenode and ask for a cloak.
Sunday, 17 May 2015
this is sick - no matter how the output became what it is, even though this would be THE MOST important question to answer. ahhhh
Sunday, 17 May 2015
wtf. "claims" this is proven/true!
Sunday, 17 May 2015
probably just a wrong copy on the server: https://news.ycombinator.com/item?id=9561179
it doesn’t pass the self check and was probably broken while uploaded.
therefore probably nothing really happened.
Sunday, 17 May 2015
And updated, again.
Sunday, 17 May 2015
The explanation of what's going on is relatively simple: It's just a faulty copy of the right key laying around on the keyservers. This happens because key servers don't check the uploaded keys. No faulty key generation involved.
I wrote a detailed explanation:
https://blog.hboeck.de/archives/872-About-the-supposed-factoring-of-a-4096-bit-RSA-key.html
Sunday, 17 May 2015
Updated even more.
Monday, 18 May 2015
Hi,
how do I check my own key? Because Phuctor shows me an Internal Server Error when I try to test a key.
I downloaded pgpdump, which gives me "RSA n(4096 bits)" as a hex value. This should be the product of the two prime numbers, right?
So I checked this value with GMP
mpz_set_str (a," the hex value from pgpdump goes here... ",16);
std::cout
Monday, 18 May 2015
To check your own key, you would have to extract it (pgpdump works) and apply any factorization / prime number finder algo to it. Worst case scenario, get a list of prime numbers up to sqrt(key) and check each individually with mod. Otherwise can try something like Pollard-rho.
Monday, 18 May 2015
" Amusingly enough, it seems Hacker News hand-diddled their story list to remove this discussion. Way to go Ydumbinator crew!"
Way to act like a child, it doesn't lend much credence to your article when you act this way.
They probably pinned it because the title and content is not quite accurate -- you found a problem with weak keys and didn't actually factor a 4096 bit key.
Monday, 18 May 2015
Bitch, I don't need any "credence" lent, and especially not from you lot.
You, and I mean that term in a very broad sense, so as to include the whole stack of you idiots all the way to Paul Graham & friends need me to lend you credence. Not the other fucking way around.
So get lost with the bs.
Monday, 18 May 2015
@Hanno & flying sheep (who, while probably not the same person, nevertheless ended up in the spam filter for some reason) : I will write up an article addressing this particular set of bullshit tomorrow. I promise it will be good. Engage bated breath.
Monday, 18 May 2015
There's paid content on this blog? My god.
You really have no idea what you are talking abut.
Monday, 18 May 2015
I don't understand your updates; how do they address the explanation given (that it's a tampered/error copy of a valid key)?
The link to "Ydumbinator" talks about FB at $27, and that it'd never reach IPO levels again. How is that [unfortunately] incorrect prediction relevant?
And what is meant by the graph? Is 7Mbps supposed to cause significant load?
Monday, 18 May 2015
@Kev You're welcome.
@MichaelGG My updates address what I wish to address, not what you wish to address. Them's the breaks.
I think your expectations seep into your reading comprehension, reducing you to this unfortunate position where you have really complicated problems with really simple things, as exemplified by the last issue you have. I find that either re-reading the source material immediately or else taking a walk (or a shower) after which re-reading the source material helps they in your position unstuck.
Monday, 18 May 2015
nice bird hair lmao
Wednesday, 20 May 2015
Is there an offline factorization tester for weak primes? https://security.stackexchange.com/questions/89713/offline-rsa-strong-prime-test-similar-to-phuctor
Wednesday, 20 May 2015
What pray tell would be a weak prime ?
If you mean, a to see if the modulus of a RSA key is factorizable, yes. There's probabilistic tests like Pollard-rho or Rabin-Miller, and there's the good old "try every prime up to sqrt(n)".
Tuesday, 18 October 2016
Perhaps failure of phuctor server was actually a coincidence -_-
Tuesday, 18 October 2016
I'm not sure what you're saying. What are you saying ?
Monday, 11 June 2018
Wow cuz this is excellent job! Congrats and keep it up.
Friday, 10 April 2020
My brother recommended I might like this blog. He was totally right, this post made my day.