Full disclosure : 4096 RSA key in the strongset factored.

Sunday, 17 May, Year 7 d.Tr. | Author: Mircea Popescu

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 :

bw-trilema-today

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.

———
  1. Incidentally, not that many algorithms over two thousand years old are still efficient, today. Remarkable, isn't it ? []
  2. Speaking of which - thanks a lot Gnu PG for making archival retarded. []
  3. 50:1 odds against is a pretty decent approximation of "never", seeing how what that says is "50 or more". []
  4. 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. []
Category: Breaking News
Comments feed : RSS 2.0. Leave your own comment below, or send a trackback.

36 Responses

  1. > 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.

  2. Kimmo Alm`s avatar
    2
    Kimmo Alm 
    Sunday, 17 May 2015

    "We won't because liniar approximation never fits this."

    "liniar"

    Shit-FUCKING-listed!

  3. Mircea Popescu`s avatar
    3
    Mircea Popescu 
    Sunday, 17 May 2015

    @. It's what it is.

    @Kimmo Alm Maaannnn... the problems you got, seriously.

  4. 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.

  5. Mircea Popescu`s avatar
    5
    Mircea Popescu 
    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.

  6. Alexandru C.`s avatar
    6
    Alexandru C. 
    Sunday, 17 May 2015

    woah if this is still ongoing regarding the ddos bot what you propose ?

  7. Hayden Jones`s avatar
    7
    Hayden Jones 
    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'

  8. Mircea Popescu`s avatar
    8
    Mircea Popescu 
    Sunday, 17 May 2015

    If you have money, use a strong VPS. If you don't, go in #freenode and ask for a cloak.

  9. this is sick - no matter how the output became what it is, even though this would be THE MOST important question to answer. ahhhh

  10. noway`s avatar
    10
    noway 
    Sunday, 17 May 2015

    wtf. "claims" this is proven/true!

  11. flying sheep`s avatar
    11
    flying sheep 
    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.

  12. Mircea Popescu`s avatar
    12
    Mircea Popescu 
    Sunday, 17 May 2015

    And updated, again.

  13. 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

  14. Mircea Popescu`s avatar
    14
    Mircea Popescu 
    Sunday, 17 May 2015

    Updated even more.

  15. simon2`s avatar
    15
    simon2 
    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

  16. Mircea Popescu`s avatar
    16
    Mircea Popescu 
    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.

  17. Jon Davis`s avatar
    17
    Jon Davis 
    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.

  18. Mircea Popescu`s avatar
    18
    Mircea Popescu 
    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.

  19. Mircea Popescu`s avatar
    19
    Mircea Popescu 
    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.

  20. There's paid content on this blog? My god.

    You really have no idea what you are talking abut.

  21. MichaelGG`s avatar
    21
    MichaelGG 
    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?

  22. Mircea Popescu`s avatar
    22
    Mircea Popescu 
    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.

  23. nice bird hair lmao

  24. Is there an offline factorization tester for weak primes? https://security.stackexchange.com/questions/89713/offline-rsa-strong-prime-test-similar-to-phuctor

  25. Mircea Popescu`s avatar
    25
    Mircea Popescu 
    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)".

  26. Rony ytpak`s avatar
    26
    Rony ytpak 
    Tuesday, 18 October 2016

    Perhaps failure of phuctor server was actually a coincidence -_-

  27. Mircea Popescu`s avatar
    27
    Mircea Popescu 
    Tuesday, 18 October 2016

    I'm not sure what you're saying. What are you saying ?

  28. Fodboldtrøjer`s avatar
    28
    Fodboldtrøjer 
    Monday, 11 June 2018

    Wow cuz this is excellent job! Congrats and keep it up.

  29. Richard Oddo`s avatar
    29
    Richard Oddo 
    Friday, 10 April 2020

    My brother recommended I might like this blog. He was totally right, this post made my day.

  1. 30
    4096 RSA factorized. | No more cubes. (via Pingback)
    Sunday, 17 May 2015

    [...] claims to have factorized Peter Anvins gpg/RSA key. Sharen mit:Auf Facebook teilen (Wird in neuem Fenster geöffnet)Klicke, [...]

  2. 31
    Hanno's blog (via Trackback)
    Sunday, 17 May 2015

    No, nobody has factored a 4096 bit RSA key...

    tl;dr News about a broken 4096 bit RSA key are not true. It is just a faulty copy of a valid key.

    Earlier today a blog post claiming the factoring of a 4096 bit RSA key was published and quickly made it to the top of Hacker News. The key in question...

  3. 32
    4096 RSA key in the strongset factored | infopunk.org (via Pingback)
    Monday, 18 May 2015

    [...] by johnmountain [link] [14 comments] [...]

  4. 33
    Two security researchers break RSA 4096 bit keys with ‘Phuctor | ZastMedia Blog (via Pingback)
    Wednesday, 20 May 2015

    [...] his Sunday’s blog post, Popescu mentioned: “expect a key to be factored just a little before Elvis comes back as the [...]

  5. [...] Something happened. [...]

  6. [...] this and they'd be meatballs. ———Short for "The Powers That Wanna Be". Because that's how it is. [↩]You should see what the turnover for intelligence jobs @USG is like - you'd think you've [...]

  7. [...] any further keys in the database, it'd be the first time since the original results were announced last Sunday that anyone proposed a useful, testable hypothesis - a sorer indictment of the soi dissant [...]

Add your cents! »
    If this is your first comment, it will wait to be approved. This usually takes a few hours. Subsequent comments are not delayed.