N.S.A. Foils Much Internet Encryption • Hacker News Board

Re: N.S.A. Foils Much Internet Encryption

#251

Post by Canada » Thu, Sep 05, 2013, 10:20 PM UTC

pfortuny wrote: post #30

w1ntermute wrote: post #17

Can someone who actually knows about encryption comment on whether it's actually physically feasible for the NSA to have actually broken, say, SSL 3.0 (which has 128 bits of entropy, IIRC) on a large scale (i.e., when you're sifting through petabytes of data on a daily basis)? And if this were really an issue, couldn't you just use 4096-bit RSA (unless they have managed to surreptitiously insert a backdoor in it)?

It might be but it is highly dubious. However, they MIGHT have put some effort into "plugging" each implementation and planting a subtle bug in them. You never can tell. It is not somuch the protocol what matters but the implementations. Imagine they "rig" all those beatiful hardware RNG. Could you tell the difference? Are you sure renowned developer X van Y is not an NSA mole?

Remember the OpenBSD IPSec backdoor allegation?

https://lwn.net/Articles/420858/

Re: N.S.A. Foils Much Internet Encryption

#252

Post by normalhuman » Thu, Sep 05, 2013, 10:21 PM UTC

gknoy wrote: post #172

tptacek wrote: post #137

Earlier quoted context omitted.

Yeah, I'm a little baffled by Schneier's reaction to this. The revelation is advanced cryptanalytic capabilities at NSA, which is literally an article of faith with Schneier. Why is he freaking out about this when he didn't instead freak out about wholesale call record database dumps or AT&T fiber taps?

I think there is a fundamental difference advanced Cryptanalysis (which we always assumed they had due to hiring practices and history) and being able to break crypto by subverting infrastructure. If the NSA said, "Our super smart brain trust figured out how to own your stuff with math five years ago ... ha ha!", I think we would be Totally Fine with that. Hats off to them for winning that game, but at least they pla…

I would be keeping my hat on. They would have done it with the taxpayers' money but without their consent or even knowledge. They would then be withholding a major scientific breakthrough from the public that financed it. A scientific breakthrough that might have all sorts of applications that could make our lives better.

They would be exposing all the people that rely in strong cryptography to major risks. Including people that have done nothing illegal and helped fund their research.

And more importantly, they shouldn't be reading our emails to being with, independently of them being encrypted or not. That was never the deal, no democratic process ever gave them the right.

Re: N.S.A. Foils Much Internet Encryption

#253

Post by tedunangst » Thu, Sep 05, 2013, 10:22 PM UTC

tptacek wrote: post #124

andrewcooke wrote: post #119

Earlier quoted context omitted.

so what was the vulnerability found by ms in 2007 that they are referring to? (search for 2007 in single page version at http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet... ) edit: reading in more detail around there, i am pretty sure that section of the article is referring to the CSPRNG vulnerability above. the article covers a lot of ground and not all of it is about problems with ssl. that particular…

I don't know. I'm just saying, weakening a CSPRNG design that nobody uses or is ever likely to use (it's extremely expensive) is not a particularly meaningful action.

This may be a case of the Times assuming that since 1.5 rounds to 2, 1.5 + 1.5 = 4. "The NSA breaks crypto" + "The NSA backdoored Dual-EC DRBG" = "The NSA breaks crypto via backdoored Dual-EC DRBG".

Re: N.S.A. Foils Much Internet Encryption

#254

Post by pja » Thu, Sep 05, 2013, 10:23 PM UTC

_phred wrote: post #86

Achshar wrote: post #12

So does this means they have broken or fund a bug in RSA, fast enough computers to brute force or solved the P versus NP problem. In decreasing chances of possibility. I am also an encryption noob, so I gather that if they have broken a crypto then my 4096 bit files will be no more secure than 1024 bit ones. Right?

The best publicly known attacks on RSA reduce the attack time by a few orders of magnitude at best. A functional quantum CPU could reduce that by a few more orders. Your 4096-bit RSA key is still 2^3072 times harder to break, so even with reductions we're still talking about "heat death of the universe" amounts of time to brute force. RSA has issues but as of yet hasn't yielded entirely to cryptanalysis. As the artic…

"Your 4096-bit RSA key is still 2^3072 times harder to break,"

No, because the difficulty of breaking RSA keys doesn't scale in the same way as symmetric encryption. Integer factorisation is much easier than a brute force search of the keyspace. A 1024-bit RSA key is believed to be roughly equivalent to an 80-bit symmetric key. A 3072 bit key is about as hard to brute force as an 128-bit symmetric key.

(Source: http://www.keylength.com/en/4/ )

Re: N.S.A. Foils Much Internet Encryption

#255

Post by Achshar » Thu, Sep 05, 2013, 10:23 PM UTC

_phred wrote: post #86

Achshar wrote: post #12

So does this means they have broken or fund a bug in RSA, fast enough computers to brute force or solved the P versus NP problem. In decreasing chances of possibility. I am also an encryption noob, so I gather that if they have broken a crypto then my 4096 bit files will be no more secure than 1024 bit ones. Right?

The best publicly known attacks on RSA reduce the attack time by a few orders of magnitude at best. A functional quantum CPU could reduce that by a few more orders. Your 4096-bit RSA key is still 2^3072 times harder to break, so even with reductions we're still talking about "heat death of the universe" amounts of time to brute force. RSA has issues but as of yet hasn't yielded entirely to cryptanalysis. As the artic…

But what if they have some vulnerability in the crypto itself? thus skipping the need to brute force.

Re: N.S.A. Foils Much Internet Encryption

#256

Post by Filligree » Thu, Sep 05, 2013, 10:23 PM UTC

ihsw wrote: post #110

bhauer wrote: post #101

Out of humor and a bit of worry, I had previously posed a conspiracy theory that the NSA/etc. had undermined (coerced, compromised, whatever) the Internet's certificate authorities. I no longer am comfortable dismissing it as silly humor. I worry that such a theory has about equal parts merit as not. I now want viable open source web-of-trust encryption for the web as soon as possible.

The worrying part is the "etc" part of your sentence, namely that all federal agencies in the US Government now have unrestricted access to encrypted communications. The DEA and the IRS are only the tip of the iceberg. If one government agency has your data then the rest of them do too.

Oh, don't forget other governments. If the NSA can do it, China and Russia certainly can too.

Re: N.S.A. Foils Much Internet Encryption

#257

Post by mindslight » Thu, Sep 05, 2013, 10:25 PM UTC

tptacek wrote: post #111

lambda wrote: post #104

Earlier quoted context omitted.

One of the vulnerabilities was already discovered by researchers in 2007: http://rump2007.cr.yp.to/15-shumow.pdf At the time, it wasn't clear if this was a deliberate backdoor or an accident, but it was proven that there there was a possibility that there was a secret key that would allow someone to predict future values of a pseudo random number generator based on previous values. Now it looks pretty clear that it w…

This is almost definitely not "one of the vulnerabilities" implicated in the story today, because nobody uses CSPRNGs based on Elliptic Curve.

A RNG that is reducible to a different believed-hard problem has possible features, so it's not like there could never be a reason for someone to choose this generator. What we could be seeing is the discovery of one failed attempt of a shotgun approach to promulgate insecure primitives. It's hard to know what will happen to become commercially successful, so spray and pray.

Something this blatant does seem like a severe misstep, but perhaps what led to discovery of this case is the wide body of public knowledge on number theoretic crypto. The energy of the public sphere seems mostly devoted to studying problems with interesting mathematical structure. Symmetric crypto has been around a lot longer, and is sufficient for state security purposes, so one would expect the NSA to have a deep analytic understanding of it (hence the differential analysis olive branch). It's not hard to imagine that they'd have ways of creating trapdoor functions out of bit primitives, generating favorable numbers with plausibly-impartial explanations, etc.

Re: N.S.A. Foils Much Internet Encryption

#258

Post by Achshar » Thu, Sep 05, 2013, 10:27 PM UTC

mrb wrote: post #149

tc wrote: post #68

This is really damaging. Not only will this cause other countries to put up barriers against US (and UK) services and products, it's going to affect uptake of standards developed here. On the lighter side, a treasure hunt was just announced. Can you find one of these vulnerabilities, or evidence of the NSA having attacked a particular system to steal keys? ---- [Edit 1] Some speculation: By careful hardware design --…

I think we know very well which encryption has been foiled by the NSA. This is not speculation, but quasi-certainty: 1024-bit RSA. - Crytographers all acknowledge 1024-bit RSA is dead [1]. - Attack cost 10 years ago was estimated to be a few million USD to build a device able to crack a 1024-bit key every 12 months [2]. - "Much of" the "secure" HTTPS websites use such weak key sizes [3]. - NSA had a budget of 10.8 bi…

I am confused. When I see HN or facebook certs they show 128 bit encryption in the browser box. 128 bit seems pretty low.

Re: N.S.A. Foils Much Internet Encryption

#259

Post by Filligree » Thu, Sep 05, 2013, 10:29 PM UTC

Dylan16807 wrote: post #142

_phred wrote: post #86

Earlier quoted context omitted.

The best publicly known attacks on RSA reduce the attack time by a few orders of magnitude at best. A functional quantum CPU could reduce that by a few more orders. Your 4096-bit RSA key is still 2^3072 times harder to break, so even with reductions we're still talking about "heat death of the universe" amounts of time to brute force. RSA has issues but as of yet hasn't yielded entirely to cryptanalysis. As the artic…

Are you sure about that? As far as I understand it, generic quantum computation would cut that '3072' in half , and using quantum computers specifically for factoring reduces problems to a low polynomial time.

Correct. Shor's algorithm renders any use of RSA... pointless.

And while there are limits to the applicability of Grover's algorithm, you're correct that it effectively cuts the number of bits in any cryptosystem it applies to in half. Which, to my nonexpert eyes, looks to be most of them.

Re: N.S.A. Foils Much Internet Encryption

#260

Post by pyaniv » Thu, Sep 05, 2013, 10:30 PM UTC

Just shame on the rest of countries around the world to let the USA control and abuse the internet and all relevant technologies. Every major chip, OS and software is created in the USA. If people elsewhere lack the brains and innovation of USA, they should accept the consequences. Of course, I'm part of the dumb ass rest of the world.