Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The NSA's crypto "breakthrough"

economist.com

Post reply on HN
Print view View original

41–50 of 101 posts

Re: The NSA's crypto "breakthrough"

#41

Post by yk »

sdevlin wrote: post #12
derefr wrote: post #5

One of the "nice" things about the NSA: they rely on pretty standard crypto--the same kind the rest of us do!--for their less sensitive, but still classified, secrets. NSA Ciphersuite B ( http://en.m.wikipedia.org/wiki/NSA_Suite_B_Cryptography ) is built into a lot of gov/mil communications technology. And it's just RSA, ECDHE, and so on--all that same stuff available in TLS. In other words: if the NSA break one of t…

Suite B does not contain RSA. EDIT: To your latter point, some people would consider this to be a telling fact.

Judging from the wikipedia link, Suite B does not contain a public key cypher. Which either tells us, that the NSA does not use asymmetric cyphers because they are broken. Or that they have a technical reason for it, like being able to do everything they want with key exchange, signature and symmetric cypher. So it is probably worth pointing out, that this speculations are interesting, but ultimately fruitless since we simply do not have enough information.

Re: The NSA's crypto "breakthrough"

#42

Post by crazygringo »

Totally tangential, but... I must have seen that exact same photo of NSA headquarters 100 times over the past month, at the head of every blog entry related to it.

It is too much to ask the nation's photographers just to take a few more pictures from different angles? ;) It's as bad as as the Onion's opinion on Snowden ("Nation Demands New Photograph Of Edward Snowden"):

https://www.google.com/search?safe=off&q=%22Nation+Demands+N...

Re: The NSA's crypto "breakthrough"

#43

Post by regularfry »

gnaffle wrote: post #28
kcorbitt wrote: post #9

Breaking public-key crypto would have to be the biggest coup in SIGINT in the history of ever . Much bigger than cracking the Enigma. Just thinking about the sheer volume of internet traffic at every level and in every country that relies on the security of encryption makes the possibility of it being fundamentally broken a literal nightmare. I don't think it has happened. But if it had , that would be the kind of se…

And, as a corrolary of this, you presently won't have much to fear if this break has happened, simply because the NSA would only use it _very_ sparingly, like how the allies used the Enigma break during WW2. Of course, if the cat ever gets out of the bag, that situation would change.

Carrying on from that thought, the various mathematician-employing agencies have now had over 60 years to study the problem of "how much can we use this critical information-revealing tool without exposing its existence?" If they can identify an upper bound on "sparingly", that's immensely valuable.

Re: The NSA's crypto "breakthrough"

#44

Post by wbl »

ianstallings wrote: post #13
devx wrote: post #2

Sounds like we need a couple more Snowden's to come out from NSA.

Chances are, if this system exists it will be accessible by only a very small number of people and kept a secret from the others with obfuscation and compartmentalization. So we'd need a very specific leaker out of a small group of people. It would be akin to hoping we'll see the secrets of the "nuclear football". Now one day over-the-counter quantum computers will probably become a reality. In that age we'll see mor…

What secrets about the football? It's a Haliburton aluminum suitcase with a radio, a book describing the options, and a Marine handcuffed to the end of it. This is all from Wikipedia.

Re: The NSA's crypto "breakthrough"

#45

Post by ianstallings »

wbl wrote: post #44
ianstallings wrote: post #13

Earlier quoted context omitted.

Chances are, if this system exists it will be accessible by only a very small number of people and kept a secret from the others with obfuscation and compartmentalization. So we'd need a very specific leaker out of a small group of people. It would be akin to hoping we'll see the secrets of the "nuclear football". Now one day over-the-counter quantum computers will probably become a reality. In that age we'll see mor…

What secrets about the football? It's a Haliburton aluminum suitcase with a radio, a book describing the options, and a Marine handcuffed to the end of it. This is all from Wikipedia.

From that description you should be able to build one yourself..

Re: The NSA's crypto "breakthrough"

#46

Post by yk »

shmageggy wrote: post #30
batgaijin wrote: post #17

p=np yo

Integer factorization is currently not known to be NP complete, and is expected to not be so. Therefore, even such a breakthrough as posited in the article would have no immediate bearing on the question of P vs NP. http://en.wikipedia.org/wiki/Integer_factorization#Difficult...

Other way round, multiplication is in P, so integer factorization is in NP. And a breakthrough in P?=NP could have implications for factorization.

Re: The NSA's crypto "breakthrough"

#47

Post by twotwotwo »

kcorbitt wrote: post #9

Breaking public-key crypto would have to be the biggest coup in SIGINT in the history of ever . Much bigger than cracking the Enigma. Just thinking about the sheer volume of internet traffic at every level and in every country that relies on the security of encryption makes the possibility of it being fundamentally broken a literal nightmare. I don't think it has happened. But if it had , that would be the kind of se…

Breaking RSA keys up to 1024 bits is one less-outlandish-than-some possibility.

NSA published a note advocating use of ECC in 2009: http://www.nsa.gov/business/programs/elliptic_curve.shtml

NSA's statement wasn't "we've got an RSA-breaking machine" or anything like that; the highlights are 0) folks are using RSA-1024, which public sources only ascribe 80 bits' worth of security to, smaller than the usual margin; 1) RSA gets slow with long keys: according to public sources, 256-bit security requires RSA-3072, which is 64x slower than the equivalent ECC-512; 2) RSA-breaking implementations keep getting gradually better over time, whereas ECC's effort-to-break has basically stood still.

Their own ("Suite B") guidelines for use of public algorithms to protect classified data tell the US government to use ECC, not RSA. (AES-256 is fine, though.) They licensed patents for particular implementation techniques: http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography

Bruce Schneier, reacting to Bamford's statement about a cryptographic breakthrough, said: "Another option is that the NSA has built dedicated hardware capable of factoring 1024-bit numbers. There's quite a lot of RSA-1024 out there, so that would be a fruitful project. So, maybe."

(There's a lot of RSA-1024 out there partly because old 1024-bit SSL certs die hard, and people are lazy about switching to bigger keys if, for example, it would make establishing SSL sessions more expensive.)

Finally, perhaps not related to public-key crypto but really interesting, the XKeyScore deck had the bullet point "Show me all the VPN startups in country X, and give me the data so I can decrypt and discover the users" as one of the things you can tell the system to do. That could just refer to one of those protocols that everyone knows is broken but is still in use (MS-CHAP/PPTP) or to either a protocol/implementation break or something else affecting VPNs we currently think are secure.

Maybe the best argument against a crypto breakthrough is that it's clearly extremely hard (none of the brilliant mathematicians working in the open are close) whereas attacks on implementations and protocols are relatively easy. If you have a big bag of 0-days, have stolen some certificates (as Stuxnet seemed to indicate), and are inside a bunch of service providers, it seems almost redundant to put a lot of effort into factoring big numbers, unless some big technical improvement basically falls in your lap.

Re: The NSA's crypto "breakthrough"

#48

Post by venomsnake »

cmyr wrote: post #21
derefr wrote: post #5

One of the "nice" things about the NSA: they rely on pretty standard crypto--the same kind the rest of us do!--for their less sensitive, but still classified, secrets. NSA Ciphersuite B ( http://en.m.wikipedia.org/wiki/NSA_Suite_B_Cryptography ) is built into a lot of gov/mil communications technology. And it's just RSA, ECDHE, and so on--all that same stuff available in TLS. In other words: if the NSA break one of t…

I'm not sure if this would be true. It's a game theory problem, surely. I'm not especially crypto-literate, but if player A has the ability to read the majority of currently encrypted comms world-wide, broadcasting that ability (by suddenly and dramatically changing their own encryption methodologies) would be a very silly move unless there was a very serious reason to believe somebody else was very close to developi…

There is very good reason to believe that once you have developed something someone else is close too. The reason is you found it.

If you check some scientific breakthroughs during the Cold War they were very close on the both sides in the matter of months.

Also with 5% of the world population NSA have limited talent pool. Assuming you are first to the goal in that case is ... overly confident. (Even if we correct for a lot of people that are not easy to tap in the outside populations chances are not on the NSA side). And I am sure a lot of the messages in other countries communications are fake and testing just to see if someone is snooping.

Re: The NSA's crypto "breakthrough"

#49

Post by venomsnake »

sillysaurus2 wrote: post #8
devx wrote: post #2

Sounds like we need a couple more Snowden's to come out from NSA.

Why? Because the government doesn't deserve to have any secret programs whatsoever? I've said it before and I'll say it again: Even if leaking XKeyscore and PRISM was morally justified, leaking the intelligence budget or leaking other programs is probably unwise. Remember that when we talk about leaking, we're talking about weakening the American government. We should at least think about the implications.

Except no - do you really think that prism and the budgets are really secret? Give some credit to the US adversaries.

I suppose that Snowden leaks were not a great surprise to the foreign governments.

Re: The NSA's crypto "breakthrough"

#50

Post by michaelt »

ianstallings wrote: post #16

Could it instead be ASIC technology on a massive scale? This might help break some of the hashing through very specialized chips.

According to https://www.schneier.com/blog/archives/2009/09/the_doghouse_... if you built a chip that could could test a password with a single increment of a counter, and that chip was the most efficient chip theoretically possible, and you built a dyson sphere to capture all the sun's energy to run the chip, it would still take 32 years to crack a 192-bit symmetric crypto password.

ASICs may well be involved, but they'd need math advances or implementation bugs rather than just brute force.

Post reply on HN