6 ms·

About the supposed factoring of a 4096 bit RSA key

231 points by hachiya 11y ago

Dylan16807 11y ago
Or the much simpler counter, anything with a factor of three ain't a 'real' 4096 bit RSA key. Even if it was in use, it would say nothing about RSA. Referring to it as a "4096 bit RSA key" is a red herring.
- logicallee 11y ago
  Also if your modulus ends in A, C, or E you should probably ask for your money back.
- contravariant 11y ago
  It probably also doesn't help that most of the math fails when one of the factors used to generate the key is composite.
undata 11y ago
https://news.ycombinator.com/item?id=9560790 https://news.ycombinator.com/item?id=9560790
acqq 11y ago
For anybody who wants to think about how such entry happened, it seems that the difference among the two presented numbers is in exactly 32 bytes (256 bits): 913ff626efddfb f8ae8f1d40da8d13 a90138686884bad1 9db776bb4812f7e3 b2 c37b8cca2eb4ac 1e889d1027bc1ed6 664f3877cd7052c6 db5567a3365cf7e2 c6 starting from the 162nd byte if I counted correctly, which means the first 5 * 32+1 (or 2 * 80+1) bytes are the same, then 32 bytes differ. (The "easily factorable" number has two bytes which are represented as "bad1" in hex). But thinking about the 256 bits, that's exactly the size of a block on which a typical symmetrical cypher can operate, which suggests some kind of a bug, although the offset of 161 byte is a bit strange. The human would probably just change a few bits to achieve the same effect, not 256, unless he wanted to encode some message, and it doesn't look so. But see also the post of lawnchair_larry here.
- userbinator 11y ago
  Is there any sort of statistical analyses which could give some idea of whether those bits were generated randomly, by a human, or perhaps came from some other key?
  - acqq 11y ago
    They are just 256 bits. And if they come from a cypher they certainly can't be distinguished from the pure random bits or from the bits from any other key. But if they come from some other key unmodified it would be possible to scan for the match, and it's a fast operation, as soon as we have the keys in which we'd like to search.
    - userbinator 11y ago
      I was wondering about the possibility of distinguishing between a human opening a keyfile (I believe they are encoded in base64?) and manually overwriting pieces of it with random rubbish, or something else; humans make very poor RNGs, as anyone who has tried "randomly" mashing a keyboard will notice.
  - obituary_latte 11y ago
    Why the fuck would this be downvoted? You people sometimes... Edit: further contributing to the discussion, more anonymous downvotes. Great.
    - dang 11y ago
      Please resist complaining about downvotes, as the site guidelines ask. Most unfairly downvoted comments get corrective upvotes after a while—that's what happened in the GP's case. Comments like this one, though, just add noise.
      - obituary_latte 11y ago
        Fair enough. Apologies.
lawnchair_larry 11y ago
I feel like everyone is being quick to write this off as "some random, harmless error", probably because the focus is that RSA is not broken, rather than asking what this was really about. "The only case where this could matter would be a broken implementation of the OpenPGP key protocol that does not check if subkeys really belong to a master key." I'd be curious to explore that further. This kernel developer has been targeted in the past: http://arstechnica.com/security/2013/09/who-rooted-kernel-org-servers-two-years-ago-how-did-it-happen-and-why/ http://arstechnica.com/security/2013/09/who-rooted-kernel-or... "During that time, attackers were able to monitor the activities of anyone using the kernel.org servers known as Hera and Odin1, as well as personal computers belonging to senior Linux developer H. Peter Anvin. The self-injecting rootkit known as Phalanx had access to a wealth of sensitive data, possibly including private keys used to sign and decrypt e-mails and remotely log in to servers. A follow-up advisory a few weeks later opened the possibility that still other developers may have fallen prey to the attackers." Edit: The key in question was created the day before this post by HPA regarding the compromise: https://lwn.net/Articles/460376/ https://lwn.net/Articles/460376/
- diafygi 11y ago
  I've been fighting the fight to be more proactive about signature verification, but there's little interest in changing the status quo. Relevant GPG thread: https://lists.gnupg.org/pipermail/gnupg-users/2015-May/053546.html https://lists.gnupg.org/pipermail/gnupg-users/2015-May/05354... Relevant SKS thread: https://lists.nongnu.org/archive/html/sks-devel/2015-05/msg00022.html https://lists.nongnu.org/archive/html/sks-devel/2015-05/msg0...
- tedunangst 11y ago
  If I wanted to poison HPA with a fake key, why would I create a degenerate one? A fake key with strong factors would have gone unnoticed, at least by this analysis.
  - deleted 11y ago
    [deleted]
- 11y ago
diafygi 11y ago
It is highly likely that this is the work of a troll. The RSA subkey that was factored has an invalid self-signature in hpa's public key[1], which means that it wasn't really hpa who added the subkey. Since the sks-keyserver pool doesn't verify signatures[2], anyone could have inserted that subkey. So anyone could have purposefully picked an exploitable RSA subkey, added a fake signature to it, and uploaded it to the sks-keyserver pool. Luckily, GPG will drop the subkey when retrieving hpa's public key since it doesn't have a valid self-signature. But for anyone scanning all the public keys without verifying signatures (for research, etc.), this key might get recognized and cause a shitstorm. Which is exactly what has happened. So far, there's no evidence that there is a conspiracy to weaken RSA keys. There is only evidence that someone inserted a bogus subkey into hpa's public key. There will be evidence of a conspiracy if we find a weak RSA key in the strongset that has a valid self-signature. [1]: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L490 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-... [2]: https://lists.gnupg.org/pipermail/gnupg-devel/2015-March/029606.html https://lists.gnupg.org/pipermail/gnupg-devel/2015-March/029...
timothya 11y ago
Meanwhile, on the original post, the author is acting like HN was tampering with the ranking of the article because it started doing poorly after people realized that a real key wasn't factored: > "Update II : Amusingly enough, it seems Hacker News hand-diddled their story list to remove this discussion. Way to go Ydumbinator crew!" [0] [0]: http://trilema.com/2015/full-disclosure-4096-rsa-key-in-the-strongset-factored/ http://trilema.com/2015/full-disclosure-4096-rsa-key-in-the-...
- zf00002 11y ago
  that's pretty much typical of mircea popescu.
  - ikeboy 11y ago
    Does he have any claim to fame beyond very elaborate trolling? I've been trying to figure out what's up with him recently.
    - rewqfdsa 11y ago
      Popescu is waging a pathetic little personal war against FetLife [1]. He's a textbook example of a self-deluded crypto-narcissist who, if there's any justice on this earth, will see his comeuppance. People like him always do. [1] He's been scraping the profiles of young women (specifically) and posting links, names, and hometowns on his blog. Yes, as technologists, we know that this kind of indexing is trivial. That's no reason, as a decent human being, to terrorize innocent people.
    - Adlai 11y ago
      Wealth. Most of the publicly known early adopters don't spend as much (or any) time trolling about (and getting trolled) on IRC. http://search.bitcoin-assets.com/?q=from%3Amircea_popescu http://search.bitcoin-assets.com/?q=from%3Amircea_popescu
      - ikeboy 11y ago
        Do we know how much he's actually worth?
deleted 11y ago
[deleted]
- Adlai 11y ago
  Quite civil for an anonymous moderator! Every church has its child rapists; why should Bitcoin be an exception?
  - dang 11y ago
    Please don't respond to trolls, and especially not by inflaming the thread further. Instead, please flag trolls' comments by clicking on the timestamp to go to the comment's page, then clicking 'flag'.

231 points by hachiya 11y ago

Or the much simpler counter, anything with a factor of three ain't a 'real' 4096 bit RSA key. Even if it was in use, it would say nothing about RSA. Referring to it as a "4096 bit RSA key" is a red herring.

logicallee 11y ago
Also if your modulus ends in A, C, or E you should probably ask for your money back.
contravariant 11y ago
It probably also doesn't help that most of the math fails when one of the factors used to generate the key is composite.

undata 11y ago

https://news.ycombinator.com/item?id=9560790 https://news.ycombinator.com/item?id=9560790

acqq 11y ago

For anybody who wants to think about how such entry happened, it seems that the difference among the two presented numbers is in exactly 32 bytes (256 bits): 913ff626efddfb f8ae8f1d40da8d13 a90138686884bad1 9db776bb4812f7e3 b2 c37b8cca2eb4ac 1e889d1027bc1ed6 664f3877cd7052c6 db5567a3365cf7e2 c6 starting from the 162nd byte if I counted correctly, which means the first 5 * 32+1 (or 2 * 80+1) bytes are the same, then 32 bytes differ. (The "easily factorable" number has two bytes which are represented as "bad1" in hex). But thinking about the 256 bits, that's exactly the size of a block on which a typical symmetrical cypher can operate, which suggests some kind of a bug, although the offset of 161 byte is a bit strange. The human would probably just change a few bits to achieve the same effect, not 256, unless he wanted to encode some message, and it doesn't look so. But see also the post of lawnchair_larry here.

userbinator 11y ago
Is there any sort of statistical analyses which could give some idea of whether those bits were generated randomly, by a human, or perhaps came from some other key?
- acqq 11y ago
  They are just 256 bits. And if they come from a cypher they certainly can't be distinguished from the pure random bits or from the bits from any other key. But if they come from some other key unmodified it would be possible to scan for the match, and it's a fast operation, as soon as we have the keys in which we'd like to search.
  - userbinator 11y ago
    I was wondering about the possibility of distinguishing between a human opening a keyfile (I believe they are encoded in base64?) and manually overwriting pieces of it with random rubbish, or something else; humans make very poor RNGs, as anyone who has tried "randomly" mashing a keyboard will notice.
- obituary_latte 11y ago
  Why the fuck would this be downvoted? You people sometimes... Edit: further contributing to the discussion, more anonymous downvotes. Great.
  - dang 11y ago
    Please resist complaining about downvotes, as the site guidelines ask. Most unfairly downvoted comments get corrective upvotes after a while—that's what happened in the GP's case. Comments like this one, though, just add noise.
    - obituary_latte 11y ago
      Fair enough. Apologies.

lawnchair_larry 11y ago

I feel like everyone is being quick to write this off as "some random, harmless error", probably because the focus is that RSA is not broken, rather than asking what this was really about. "The only case where this could matter would be a broken implementation of the OpenPGP key protocol that does not check if subkeys really belong to a master key." I'd be curious to explore that further. This kernel developer has been targeted in the past: http://arstechnica.com/security/2013/09/who-rooted-kernel-org-servers-two-years-ago-how-did-it-happen-and-why/ http://arstechnica.com/security/2013/09/who-rooted-kernel-or... "During that time, attackers were able to monitor the activities of anyone using the kernel.org servers known as Hera and Odin1, as well as personal computers belonging to senior Linux developer H. Peter Anvin. The self-injecting rootkit known as Phalanx had access to a wealth of sensitive data, possibly including private keys used to sign and decrypt e-mails and remotely log in to servers. A follow-up advisory a few weeks later opened the possibility that still other developers may have fallen prey to the attackers." Edit: The key in question was created the day before this post by HPA regarding the compromise: https://lwn.net/Articles/460376/ https://lwn.net/Articles/460376/

diafygi 11y ago
I've been fighting the fight to be more proactive about signature verification, but there's little interest in changing the status quo. Relevant GPG thread: https://lists.gnupg.org/pipermail/gnupg-users/2015-May/053546.html https://lists.gnupg.org/pipermail/gnupg-users/2015-May/05354... Relevant SKS thread: https://lists.nongnu.org/archive/html/sks-devel/2015-05/msg00022.html https://lists.nongnu.org/archive/html/sks-devel/2015-05/msg0...
tedunangst 11y ago
If I wanted to poison HPA with a fake key, why would I create a degenerate one? A fake key with strong factors would have gone unnoticed, at least by this analysis.
- deleted 11y ago
  [deleted]
11y ago

diafygi 11y ago

It is highly likely that this is the work of a troll. The RSA subkey that was factored has an invalid self-signature in hpa's public key[1], which means that it wasn't really hpa who added the subkey. Since the sks-keyserver pool doesn't verify signatures[2], anyone could have inserted that subkey. So anyone could have purposefully picked an exploitable RSA subkey, added a fake signature to it, and uploaded it to the sks-keyserver pool. Luckily, GPG will drop the subkey when retrieving hpa's public key since it doesn't have a valid self-signature. But for anyone scanning all the public keys without verifying signatures (for research, etc.), this key might get recognized and cause a shitstorm. Which is exactly what has happened. So far, there's no evidence that there is a conspiracy to weaken RSA keys. There is only evidence that someone inserted a bogus subkey into hpa's public key. There will be evidence of a conspiracy if we find a weak RSA key in the strongset that has a valid self-signature. [1]: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L490 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-... [2]: https://lists.gnupg.org/pipermail/gnupg-devel/2015-March/029606.html https://lists.gnupg.org/pipermail/gnupg-devel/2015-March/029...

timothya 11y ago

Meanwhile, on the original post, the author is acting like HN was tampering with the ranking of the article because it started doing poorly after people realized that a real key wasn't factored: > "Update II : Amusingly enough, it seems Hacker News hand-diddled their story list to remove this discussion. Way to go Ydumbinator crew!" [0] [0]: http://trilema.com/2015/full-disclosure-4096-rsa-key-in-the-strongset-factored/ http://trilema.com/2015/full-disclosure-4096-rsa-key-in-the-...

zf00002 11y ago
that's pretty much typical of mircea popescu.
- ikeboy 11y ago
  Does he have any claim to fame beyond very elaborate trolling? I've been trying to figure out what's up with him recently.
  - rewqfdsa 11y ago
    Popescu is waging a pathetic little personal war against FetLife [1]. He's a textbook example of a self-deluded crypto-narcissist who, if there's any justice on this earth, will see his comeuppance. People like him always do. [1] He's been scraping the profiles of young women (specifically) and posting links, names, and hometowns on his blog. Yes, as technologists, we know that this kind of indexing is trivial. That's no reason, as a decent human being, to terrorize innocent people.
  - Adlai 11y ago
    Wealth. Most of the publicly known early adopters don't spend as much (or any) time trolling about (and getting trolled) on IRC. http://search.bitcoin-assets.com/?q=from%3Amircea_popescu http://search.bitcoin-assets.com/?q=from%3Amircea_popescu
    - ikeboy 11y ago
      Do we know how much he's actually worth?

deleted 11y ago

[deleted]

Adlai 11y ago
Quite civil for an anonymous moderator! Every church has its child rapists; why should Bitcoin be an exception?
- dang 11y ago
  Please don't respond to trolls, and especially not by inflaming the thread further. Instead, please flag trolls' comments by clicking on the timestamp to go to the comment's page, then clicking 'flag'.