8 ms·

NSA's Backdoor Key from Lotus Notes

281 points by yuhong 12y ago

yuhong 12y ago
Notice they used only 760 bit RSA and it only has to be factored once. Then you can brute force the remaining 40-bit keyspace with GPUs.
- lstyls 12y ago
  I don't know much about crypto. This is bad I assume?
  - yuhong 12y ago
    It is stronger than the 512-bit RSA factored in the FREAK attack but is still factorable with clusters. I wonder how fast a FPGA would be able to do it.
    - dogma1138 12y ago
      FPGA are very very inefficient at doing anything, they are very flexible and you can program them to perform specific operations very quickly relative to general purpose hardware however most of the silicon is dedicated to facilitate the programmability of the FPGA rather than the actual processing. If you only have access to commodity hardware than GPU's would probably be better. Xeon Phi is also insanely cheap right now and you can get a 57 core card for under or just about 200$ but I don't have clear performance data for it, i know for BC mining it's comparable to R9 290/295X or so but with much lower power consumption, but i also suspect that due to its relative low market cap it's fairly poorly optimized atm. NSA and large private organizations use most likely specially designed hardware rather than commodity hardware and surely not FPGAs. For private individuals the most cost effective way to factor a single key these days is probably renting EC2 GPU instances (CUDA) from Amazon @ about 70 cents and hour you should be able to factor 512bit keys for 75-150$ (based on confirmed reports). 1024 bit might also be in reach however it will require a sizable budget. Based on the current development of "auxiliary" processing components whether it's GPU based compute cards or more traditional but highly threaded processing cards ala Xeon Phi it would not surprised me if 1024 or even 2048 bit keys will be easy to factor before 2020. My current bet is that 1024 will be achievable on EC2 or a similar service by late 2016 to mid 2017. NIST has disallowed 1024bit since 2014, and based on it's previous deprecation most keys were factored within 2 years after it's final deprecation notice. It's also quite important to point that there are quite a bit of "weak" RSA keys out there and there's a good chance that the NSA and similar organizations have the capability to factor certain keys probably upto and including 2048 bit.
      - wolf550e 12y ago
        Factoring RSA-2048 in 2020 sounds impossible. tptacek said it's extraordinarily unlikely NSA can scalably factor RSA-1024 today [1]. Look at how difficulty increases in the Yafu with GGNFS benchmark on wikipedia [2]. 1 - https://news.ycombinator.com/item?id=8844239 https://news.ycombinator.com/item?id=8844239 2 - https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Integer_factorization_and_RSA_problem https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Integer...
        raverbashing 12y ago
        Well, they have very good mathematicians. Also, there's the possibility that even if a product uses a 2048 bit RSA key it might have been weakened. "As of 2010, the largest factored RSA number was 768 bits long" I read this as "today, 1024 bit factorizations are possible"
        tptacek 12y ago
        By "scalably factor", I was referring to their ability to take arbitrary 1024 bit public keys as they appeared in random TLS sessions on the Internet and factor them on demand. NSA can virtually certainly target a specific, hardcoded 1024 bit key and break it. In fact, leaving out the cost and difficulty of recruiting the team to actually put the pieces together, the typical California venture capital firm has the resources to build a machine to do that today. Eran Tromer put the cost of such a machine in the single-digit millions, many years ago. Apropos nothing: the gap between a 1024 bit key and a 2048 bit key is enormous. The thing that allows the NSA to meaningfully attack a 2048 bit key is likely to take RSA out altogether (and with it probably multiplicative finite field --- ie, "conventional" --- Diffie Hellman).
        yuhong 12y ago
        Yea, this is one reason why I don't consider 1024-bit end entity certs (as opposed to roots) that much of a threat.
        wolf550e 12y ago
  - wolf550e 12y ago
    RSA-768 has been factored by academics in 2009[0]. It has long been speculated that NSA can factor 1024bit RSA (or DHE) using custom hardware, which is why in protocols like TLS and SSH the current recommendation is for keys, certificates and Diffie Hellman key exchange to be at least as strong as RSA-2048 (e.g. 256 bit elliptic curve crypto is strong enough). 0 - https://en.wikipedia.org/wiki/RSA_numbers#RSA-768 https://en.wikipedia.org/wiki/RSA_numbers#RSA-768
    - userbinator 12y ago
      If I got the maths right, due to the exponential relationship a 760-bit key should on average take roughly 1/256th of the time a 768-bit key takes to factor.
      - pbsd 12y ago
        No, that is not how factorization scales. The time difference between a 760 and 768-bit modulus is less than a factor of 2.
- Buge 12y ago
  Are you saying that the NSA would have to brute force this public key? I was under the impression that the NSA created a public/private key pair and gave this public key to Lotus Notes to use.
  - fabulist 12y ago
    I think he's saying many people today could brute force this public key. Less than 2048 bits is considered unsafe today.
nailer 12y ago
There was also a key marked as 'NSAKEY' in a normally encrypted part of Windows NT that was revealed in a Service Pack. However Microsoft said it had another purpose. http://en.m.wikipedia.org/wiki/NSAKEY http://en.m.wikipedia.org/wiki/NSAKEY
- godgod 12y ago
  Anyone have a list of software that the NSA has backdoored? http://en.wikipedia.org/wiki/NSAKEY http://en.wikipedia.org/wiki/NSAKEY It'd be nice to have a single wikipedia page of all the software.
- fabulist 12y ago
  A buddy who is an excellent reverse engineer assures me that this isn't a conspiracy. Crypto services had to be verified by a key; the NSA's crypto services were classified, so they couldn't let Microsoft sign them; therefore, they needed their own key. The key is only used to authenticate crypto services, which I think Douglas Adams would describe as Mostly Harmless. I don't have the reverse engineering skills/IDA Pro license to verify this, but fwiw I trust and respect this person's skills. But lets do a thought experiment. 1. How much would the NSA gain from pressuring Microsoft into backdooring (or as they say, "enabling") Windows, in terms of systems they could not access before that they can access now? 2. How much would it cost the NSA, in terms of effort, good will, and exposure to risk by the people at Microsoft who would know about the backdoor and may leak or abuse it? How bad would it be if the public got wind of it? How hard would it be to keep it secret over the years, especially as engineers moved around to other companies? Would they have to involve foreign nationals on the dev team? Could they be trusted not to warn their governments? 3. How many times could they abuse their backdoor before it was obvious Windows couldn't be trusted? When/if that happened, what would be the damage to the US economy, and to their ability to penetrate systems? When I put myself in the shoes of DIRNSA and ask myself these questions, backdooring Windows (at least through official channels, like _NSAKEY supposedly is) seems like an insane proposition.
  - na85 12y ago
    Answers from my POV: 1 - Privileged access to the dominant consumer operating system, also used by many corporations likely to be targeted. 2 - Minimal effort cost. Good will cost seems like something NSA ignores. Exposure to risk seems minimal given the existence of NDA contracts. 3 - I think anyone who isn't deluded and/or a member of the "nothing to hide; nothing to fear" camp already knows you can't trust Windows. The damage to the US economy seems minimal in light of the Snowden leaks that implicate nearly every US-based technology company, and Microsoft is investing heavily into things like X-box to diversify their revenue streams. I don't think there'd be any fallout worth mentioning, tbh. When I put myself into the shoes of the DIRNSA and ask myself these questions, backdooring Windows seems like an obvious "Yes". _NSAKEY may very well not be a backdoor, but I find the suggestion that Windows doesn't contain one to be laughably naive.
noblethrasher 12y ago
From Ray Ozzie himself in a previous discussion: https://news.ycombinator.com/item?id=5846189 https://news.ycombinator.com/item?id=5846189
- mentat 12y ago
  This is an amazing thread, just want to make sure people in this one know.
- DanielBMarkham 12y ago
  Ozzie's comment is great. Well worth the read.
macmac 12y ago
While US export control based on crypto have been changed, they still do exist http://en.wikipedia.org/wiki/Export_of_cryptography_from_the_United_States#Current_status http://en.wikipedia.org/wiki/Export_of_cryptography_from_the...
- rtpg 12y ago
  this is the source of e.g. Skype's installer requiring you to acknowledge you are not in Iran, NK, or Syria (that list might have changed recently)

281 points by yuhong 12y ago

Notice they used only 760 bit RSA and it only has to be factored once. Then you can brute force the remaining 40-bit keyspace with GPUs.

lstyls 12y ago
I don't know much about crypto. This is bad I assume?
- yuhong 12y ago
  It is stronger than the 512-bit RSA factored in the FREAK attack but is still factorable with clusters. I wonder how fast a FPGA would be able to do it.
  - dogma1138 12y ago
    FPGA are very very inefficient at doing anything, they are very flexible and you can program them to perform specific operations very quickly relative to general purpose hardware however most of the silicon is dedicated to facilitate the programmability of the FPGA rather than the actual processing. If you only have access to commodity hardware than GPU's would probably be better. Xeon Phi is also insanely cheap right now and you can get a 57 core card for under or just about 200$ but I don't have clear performance data for it, i know for BC mining it's comparable to R9 290/295X or so but with much lower power consumption, but i also suspect that due to its relative low market cap it's fairly poorly optimized atm. NSA and large private organizations use most likely specially designed hardware rather than commodity hardware and surely not FPGAs. For private individuals the most cost effective way to factor a single key these days is probably renting EC2 GPU instances (CUDA) from Amazon @ about 70 cents and hour you should be able to factor 512bit keys for 75-150$ (based on confirmed reports). 1024 bit might also be in reach however it will require a sizable budget. Based on the current development of "auxiliary" processing components whether it's GPU based compute cards or more traditional but highly threaded processing cards ala Xeon Phi it would not surprised me if 1024 or even 2048 bit keys will be easy to factor before 2020. My current bet is that 1024 will be achievable on EC2 or a similar service by late 2016 to mid 2017. NIST has disallowed 1024bit since 2014, and based on it's previous deprecation most keys were factored within 2 years after it's final deprecation notice. It's also quite important to point that there are quite a bit of "weak" RSA keys out there and there's a good chance that the NSA and similar organizations have the capability to factor certain keys probably upto and including 2048 bit.
    - wolf550e 12y ago
      Factoring RSA-2048 in 2020 sounds impossible. tptacek said it's extraordinarily unlikely NSA can scalably factor RSA-1024 today [1]. Look at how difficulty increases in the Yafu with GGNFS benchmark on wikipedia [2]. 1 - https://news.ycombinator.com/item?id=8844239 https://news.ycombinator.com/item?id=8844239 2 - https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Integer_factorization_and_RSA_problem https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Integer...
      - raverbashing 12y ago
        Well, they have very good mathematicians. Also, there's the possibility that even if a product uses a 2048 bit RSA key it might have been weakened. "As of 2010, the largest factored RSA number was 768 bits long" I read this as "today, 1024 bit factorizations are possible"
      - tptacek 12y ago
        By "scalably factor", I was referring to their ability to take arbitrary 1024 bit public keys as they appeared in random TLS sessions on the Internet and factor them on demand. NSA can virtually certainly target a specific, hardcoded 1024 bit key and break it. In fact, leaving out the cost and difficulty of recruiting the team to actually put the pieces together, the typical California venture capital firm has the resources to build a machine to do that today. Eran Tromer put the cost of such a machine in the single-digit millions, many years ago. Apropos nothing: the gap between a 1024 bit key and a 2048 bit key is enormous. The thing that allows the NSA to meaningfully attack a 2048 bit key is likely to take RSA out altogether (and with it probably multiplicative finite field --- ie, "conventional" --- Diffie Hellman).
        yuhong 12y ago
        Yea, this is one reason why I don't consider 1024-bit end entity certs (as opposed to roots) that much of a threat.
        wolf550e 12y ago
- wolf550e 12y ago
  RSA-768 has been factored by academics in 2009[0]. It has long been speculated that NSA can factor 1024bit RSA (or DHE) using custom hardware, which is why in protocols like TLS and SSH the current recommendation is for keys, certificates and Diffie Hellman key exchange to be at least as strong as RSA-2048 (e.g. 256 bit elliptic curve crypto is strong enough). 0 - https://en.wikipedia.org/wiki/RSA_numbers#RSA-768 https://en.wikipedia.org/wiki/RSA_numbers#RSA-768
  - userbinator 12y ago
    If I got the maths right, due to the exponential relationship a 760-bit key should on average take roughly 1/256th of the time a 768-bit key takes to factor.
    - pbsd 12y ago
      No, that is not how factorization scales. The time difference between a 760 and 768-bit modulus is less than a factor of 2.
Buge 12y ago
Are you saying that the NSA would have to brute force this public key? I was under the impression that the NSA created a public/private key pair and gave this public key to Lotus Notes to use.
- fabulist 12y ago
  I think he's saying many people today could brute force this public key. Less than 2048 bits is considered unsafe today.

nailer 12y ago

There was also a key marked as 'NSAKEY' in a normally encrypted part of Windows NT that was revealed in a Service Pack. However Microsoft said it had another purpose. http://en.m.wikipedia.org/wiki/NSAKEY http://en.m.wikipedia.org/wiki/NSAKEY

godgod 12y ago
Anyone have a list of software that the NSA has backdoored? http://en.wikipedia.org/wiki/NSAKEY http://en.wikipedia.org/wiki/NSAKEY It'd be nice to have a single wikipedia page of all the software.
fabulist 12y ago
A buddy who is an excellent reverse engineer assures me that this isn't a conspiracy. Crypto services had to be verified by a key; the NSA's crypto services were classified, so they couldn't let Microsoft sign them; therefore, they needed their own key. The key is only used to authenticate crypto services, which I think Douglas Adams would describe as Mostly Harmless. I don't have the reverse engineering skills/IDA Pro license to verify this, but fwiw I trust and respect this person's skills. But lets do a thought experiment. 1. How much would the NSA gain from pressuring Microsoft into backdooring (or as they say, "enabling") Windows, in terms of systems they could not access before that they can access now? 2. How much would it cost the NSA, in terms of effort, good will, and exposure to risk by the people at Microsoft who would know about the backdoor and may leak or abuse it? How bad would it be if the public got wind of it? How hard would it be to keep it secret over the years, especially as engineers moved around to other companies? Would they have to involve foreign nationals on the dev team? Could they be trusted not to warn their governments? 3. How many times could they abuse their backdoor before it was obvious Windows couldn't be trusted? When/if that happened, what would be the damage to the US economy, and to their ability to penetrate systems? When I put myself in the shoes of DIRNSA and ask myself these questions, backdooring Windows (at least through official channels, like _NSAKEY supposedly is) seems like an insane proposition.
- na85 12y ago
  Answers from my POV: 1 - Privileged access to the dominant consumer operating system, also used by many corporations likely to be targeted. 2 - Minimal effort cost. Good will cost seems like something NSA ignores. Exposure to risk seems minimal given the existence of NDA contracts. 3 - I think anyone who isn't deluded and/or a member of the "nothing to hide; nothing to fear" camp already knows you can't trust Windows. The damage to the US economy seems minimal in light of the Snowden leaks that implicate nearly every US-based technology company, and Microsoft is investing heavily into things like X-box to diversify their revenue streams. I don't think there'd be any fallout worth mentioning, tbh. When I put myself into the shoes of the DIRNSA and ask myself these questions, backdooring Windows seems like an obvious "Yes". _NSAKEY may very well not be a backdoor, but I find the suggestion that Windows doesn't contain one to be laughably naive.

noblethrasher 12y ago

From Ray Ozzie himself in a previous discussion: https://news.ycombinator.com/item?id=5846189 https://news.ycombinator.com/item?id=5846189

mentat 12y ago
This is an amazing thread, just want to make sure people in this one know.
DanielBMarkham 12y ago
Ozzie's comment is great. Well worth the read.

macmac 12y ago

While US export control based on crypto have been changed, they still do exist http://en.wikipedia.org/wiki/Export_of_cryptography_from_the_United_States#Current_status http://en.wikipedia.org/wiki/Export_of_cryptography_from_the...

rtpg 12y ago
this is the source of e.g. Skype's installer requiring you to acknowledge you are not in Iran, NK, or Syria (that list might have changed recently)