10 ms·

The NSA's crypto "breakthrough"

78 points by qubitsam 13y ago

devx 13y ago
Sounds like we need a couple more Snowden's to come out from NSA.
- Karunamon 13y ago
  Indeed.. but honestly, I'm not hopeful. I would have thought that shenangians on the level going on in the NSA (for as long as they've been at it) would have led to more conscience-burdened folks blowing the whistle either in public as Snowden did, or more covertly. But who knows. Maybe Snowden emboldened a few people who will be able to shine some light on these things in a more quiet manner.
- sillysaurus2 13y ago
  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.
  - derefr 13y ago
    I imagine these arguments usually come from a perspective that the US should be as weak as it would be with all its cards on the table; possibly coupled with the idea that if we're spending $500b/yr on defense, going down a few rungs on the power ladder still leaves us above everyone else. It's a very populist idea--that we can trade tactical power (the kind you get from having secrets) for strategic power (the kind you get, supposedly, by having the average voter participating in the decision-making process.) Let alone that the military isn't under congress...
  - sneak 13y ago
    http://youtu.be/ZmwRgTSqT9U http://youtu.be/ZmwRgTSqT9U
  - fnordfnordfnord 13y ago
    >weakening the American government. There are some who believe that wasting incredible resources on military / defense is actually weakening the country in light of the fact that we have no superpower enemy with even the remote potential to match our military. This leaves us vulnerable to other novel attacks, as well as just spending ourselves into oblivion. You know, the same way we 'overcame' the USSR's military threat via the arms race when their economy could not match the pace of ours. Yes, the US gov't should be weakened by any account; given the degree which it has overstepped its stated bounds.
  - yk 13y ago
    Leaking the intelligence budget was probably the most justified leak. Even if you want a geopolitically strong American government, the intelligence budget tells the public how much effort the USG puts into covert programs. So without it you can not have a meaningful debate about the size of the intelligence agencies. But on the other hand, I do not believe that other agencies can infer much from it, since everybody already knows that there is a quite big budget. So even in a real politics interpretation, the budget tells other intelligence agencies, how nice the chess board is, not what strategy is played.
  - venomsnake 13y ago
    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.
  - natrius 13y ago
    The American government is collecting as much data about as many humans as it can, which I find morally repugnant. I support efforts to make that more difficult, even if it weakens the American government.
    - engrenage 13y ago
      Government strength is relative. Weakening the American government is equivalent to strengthening other Governments. Would you mind telling us which ones you prefer and why they are morally superior?
      - CamperBob2 13y ago
        Weakening the American government is equivalent to strengthening other Governments. No, building petabyte-scale data centers to spy on you and me is what's weakening the American government. We're not the problem, right? The NSA is like the drunk who looks for his lost keys under the lamppost, "because that's where the light is." Not only does the American government's idea of a hypersecure state not make us any more free, there's vanishingly little evidence that it accomplishes its purpose of making us any more secure.
        engrenage 13y ago
        The lack of evidence isn't surprising given that they are a spy agency. They may not be protecting the US from terrorism, but there are major geopolitical adversaries at work who have no scruples about using cyberwarfare techniques. There is something akin to the Cold War in play, and the NSA is a significant part of the US's position in that war.
        CamperBob2 13y ago
        Sorry, 1% of America's GDP is too much to pay for a suit-and-tie version of Anonymous.
        13y ago
- ianstallings 13y ago
  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 more information on it because the secret will be no secret at all.
  - wbl 13y ago
    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.
    - ianstallings 13y ago
      From that description you should be able to build one yourself..
  - tomjen3 13y ago
    That might happen if you handle dry cleaning for the white house: http://newsbusters.org/blogs/brad-wilmouth/2010/10/21/abc-notes-bill-clinton-lost-nuclear-codes-while-president-maybe-jimmy http://newsbusters.org/blogs/brad-wilmouth/2010/10/21/abc-no...
    - ianstallings 13y ago
      I'm surprised they didn't mention Reagan. When he got shot the codes were lost in the hospital and found on the floor later.
- rhizome 13y ago
  Sounds like we need a Truth and Reconciliation Commission.
s_q_b 13y ago
The Economist: >Does the NSA have a quantum computer in the basement of its headquarters in Maryland (pictured above)? It is theoretically possible, but pretty unlikely... A Canadian firm called D-Wave is presently selling a specialised kind of quantum computer—Lockheed Martin, an American defence giant, and Google have each bought one—but it is not suitable for this kind of work. In-Q-Tel - "About Us" >"We make investments in startup companies that have developed commercially-focused technologies that will provide strong, near-term advantages (within 36 months) to the IC mission. We design our strategic investments to accelerate product development and delivery for this ready-soon innovation, and specifically to help companies add capabilities needed by our customers in the Intelligence Community. "D-Wave Systems, Inc., the World's First Commercial Quantum Computing Company, Secures $30 Million in a New Equity Round From Investors Including Bezos Expeditions and In-Q-Tel" [0] "Burnaby, BC - Milpitas, CA - October 4, 2012 - D-Wave Systems, Inc. today announced that it has closed a $30 million round of equity funding. Bezos Expeditions and In-Q-Tel (IQT) have joined the investment round. Bezos Expeditions is the personal investment company of Jeff Bezos. IQT is the strategic investment firm that delivers innovative technology solutions in support of the missions of the U.S. Intelligence Community." [0] http://www.dwavesys.com/en/pressreleases.html#investment_2012 http://www.dwavesys.com/en/pressreleases.html#investment_201...
- seiji 13y ago
  The most advanced math a quantum computer has done to date is "factored 21 into 3×7, with high probability (Martín-López et al. 2012)." Remember: companies are in the game of marketing hype to ride your scifi hopes and dreams. When you see a company saying "quantum" anything, discount their unqualified claims greatly. (Investors are not immune to being manipulated by hype. Claiming "they must be good because they have fancy investors!" provides no more weight to their ability than a hobo claiming he keeps the airplane aloft by snapping his fingers every 3.2 seconds.)
  - devx 13y ago
    I think that's for "normal" quantum computers. D-wave is a different kind of quantum computer.
lazyjones 13y ago
Somewhat misleading title. No answers, just more questions on the topic.
- frank_boyd 13y ago
  Well, that's important to keep in mind: There are no answers and there will never be, b/c: We can never trust/accept any statements from any government, except for admissions of guilt.
derefr 13y ago
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 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 these "public" algorithms, you'll be able to tell; they'll soon be picking new Suite B ciphers. (There will be a time-delay, but not of the intentional "let's capture+break foreign transmissions before scaring them away from this cipher" kind. Re-securing our own transmissions takes priority, always. Even if it was broken because of some "quantum leap"--pardon the pun--we have to assume our enemies are advancing their own tech at roughly the same rate, so if we can crack it, they can too.)
- quantumpotato_ 13y ago
  By "our enemies" you mean enemies of the USG, I assume. I agree with your point, but do you think they'd force widespread cipher switch across government bodies? Or leave other government entities using broken encryption so they can more easiler spy?
- sdevlin 13y ago
  Suite B does not contain RSA. EDIT: To your latter point, some people would consider this to be a telling fact.
  - sneak 13y ago
    Or non-EC DH, either. (It does include ECDH.) Perhaps they were simply anticipating DLP progress and wanted to be future-proof?
    - ctz 13y ago
      It's more likely because you can't achieve modern security levels with cryptosystems built on the DLP or IFP at acceptable performance. Suite B aims for 128-bit or 192-bit security levels; for comparison 1024-bit modulus RSA is currently thought to provide 73-bit security. (The next natural question is why the internet community is still failing to widely deploy cryptosystems with appropriate security levels. I don't know. But HTTPS, OTR and DNSSEC are all built of cheese in this respect.)
alcari 13y ago
This article does a few things that make it seem poorly written. First, there's the sentence "But, analysing a particular colossal number and trying to determine whether it possesses prime factors is colossally difficult." No, it's not difficult to determine whether a large number has prime factors. The answer to that question is yes. Determining which prime numbers are factors is extremely hard, and what they should have said. Second, they use an example from GCHQ's public key cryptography work rather than the more relevant NSA work on differential cryptanalysis, which became public knowledge in the late 1980s, was discovered by IBM in 1974, and which the NSA was already "well aware of" in 1974 [0]. [0]: https://en.wikipedia.org/wiki/Differential_cryptanalysis#History https://en.wikipedia.org/wiki/Differential_cryptanalysis#His...
kcorbitt 13y ago
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 secret that would go in the President's book of secrets right along with the existence of National Treasure or the Men in Black. :P Snowden would never have a clue.
- yk 13y ago
  Well, it would be a very well guarded secret. But even then the question is how public key crypto is broken. If they can easily generate exploits for implementations, because they know a essential implementation detail everybody else is missing, then it would be fundamentally different from being able to break RSA directly, or if they have a constructive prove of P=NP.
  - deleted 13y ago
    [deleted]
  - deleted 13y ago
    [deleted]
  - cschmidt 13y ago
    Remember that factoring primes isn't know to be NP Hard. There is no complexity breakthrough required, we just don't know how to do it quickly. So we don't get P=NP from any factoring breakthrough.
    - yk 13y ago
      Depends on the breakthrough, we know that multiplication is in P and therefore factorization in NP. So a P?=NP breakthrough may or may not have consequences for integer factorization. ( Actually since I did write that, I wonder if P=NP would invalidate any public key crypto, since efficient encryption should be in P.)
ianstallings 13y ago
Could it instead be ASIC technology on a massive scale? This might help break some of the hashing through very specialized chips.
- sseveran 13y ago
  In fact if/when someone comes up with a working attack it will probably require ASICs to run cost effectively.
- michaelt 13y ago
  According to https://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html 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.
batgaijin 13y ago
p=np yo
- shmageggy 13y ago
  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#Difficulty_and_complexity http://en.wikipedia.org/wiki/Integer_factorization#Difficult...
  - yk 13y ago
    Other way round, multiplication is in P, so integer factorization is in NP. And a breakthrough in P?=NP could have implications for factorization.
    - shmageggy 13y ago
      > so integer factorization is in NP I never said it wasn't. > And a breakthrough in P?=NP could have implications for factorization. Indeed, but what's implied in the article is that they might have made a breakthrough in factorization specifically, not in fundamental CS theory at large.
- cheald 13y ago
  Prove it.
ianstallings 13y ago
What worries me is that the breakthrough might just be a re-interpretation of the law.
officialjunk 13y ago
"algorithsm"
crazygringo 13y ago
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+New+Photograph+Of+Edward+Snowden%22 https://www.google.com/search?safe=off&q=%22Nation+Demands+N...
- deleted 13y ago
  [deleted]
- dasil003 13y ago
  Show some gratitude. You have no idea how many individuals had to sacrifice their personal lives to get that picture into the commons.
  - advice4u 13y ago
    What do you mean? As far as I can tell, it is freely available on NSA's website: http://www.nsa.gov/about/_images/pg_hi_res/nsa_aerial.jpg http://www.nsa.gov/about/_images/pg_hi_res/nsa_aerial.jpg
    - lifeisstillgood 13y ago
      Perhaps it would sound better as "Many Bantha spies have given their lives to bring us that photo, General Calrissian" (I'm sure I have that wrong - so a prize to whoever corrects the quote from memory :-)
      - advice4u 13y ago
        *Bothans Banthas are the large beasts-of-burden on Tatooine. Bothans are humanoid aliens with cat/dog-like faces. Why do I know that? I play a lot of Star Wars video and card games :) EDIT: just googled for the quote. The full one is "Many Bothans died to bring us this information."
ig1 13y ago
There's at least two other significant possibilities: 1) There's an attack against RSA which doesn't involve factorization 2) There's an attack against AES / Serpent / Twofish I'd say the second is considerably more likely, firstly because the one NSA quote we have on it is "cryptanalyze, or break, unfathomably complex encryption systems" - which sounds much more like a new attack like differential cryptanalysis which provides a general purpose attack against complex symmetric crypto ("unfathomly complex" sounds much more like AES than RSA). In addition we have numerous quotes in recent days about how GCHQ is working on breaking the encryption on the Miranda hard-drive; which we now know to be a truecrypt drive.
- twotwotwo 13y ago
  On point 2, NSA still allows the use of AES-256 to protect top secret data: http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography
  - ig1 13y ago
    Another option could be a practical attack on 128bit RC4. But I don't think the fact they're still using it means it hasn't been broken. Historically countries have sacrificed countless soldiers because saving them would have revealed that the enemy crypto-system had been broken.
  - crazypyro 13y ago
    Why is everyone assuming the NSA has to be using their own standards, behind close doors?
    - harshreality 13y ago
      They don't. They use Suite A, which is an eclectic mix of proprietary algorithms. Firefly/Enhanced Firefly for key exchange (PKI), Joeski (allegedly a pair of algorithms for encrypting and decrypting other ciphers or firmware with the interesting property that encryption algorithm cannot be deduced from the decryption algorithm and vice versa), and a bunch of others. They have different algorithms depending on the specific information channel. Permanent data storage uses one (or perhaps a few), communications traffic uses others, and communications are further split depending on channel bandwidth and presumably long-term classification needs of the data. They have to recommend Suite B to the government and military in cases where NSA validated hardware can't be used. Examples would be military communications with allies, garden variety agencies that can't afford or can't be trusted with Suite A modules.
nilved 13y ago
As a rule of thumb, I don't take any article that refers to Snowden's leaks as "revelations" seriously. The only new information Snowden revealed is that their programs are called PRISM, upstream and xKeyscore; and if a journalist learned the details behind those programs from Snowden -- when they've been going on for at least a decade -- they clearly don't know much about the subject.
- nodata 13y ago
  What a ridiculous rule of thumb: Snowden got a lot of closely held information in front of the general public. If that doesn't count as a revelation, your standards are too high.
  - nilved 13y ago
    No, he really didn't. We knew that the USA intercepted any Internet traffic they could get their hands on, and we knew that big data companies were in bed with the NSA. If the talking point is that Snowden got these facts on mainstream news, that isn't a revelation, that's marketing. "Relevation" implies the idea didn't exist beforehand.
    - nodata 13y ago
      So a revelation isn't the revealing of a secret to people who don't know the secret? (or to put it another way: revealing a secret to a population where the vast majority do not know it) Snowden revealed the scale of the operation too, and the depth of the rabbit hole.
      - nilved 13y ago
        Not if that information is already publicly and easily accessible to that group. If I was to post a link to an existing but obscure Wikipedia article on Hacker News, it would be as much of a "revelation" as Snowden's "revelations."
shortcj 13y ago
In view of this "breakthrough" leak, I am now supposing that Edward Snowden is a willing participant in psy-ops. "An all knowing deity is a cheap cop."

78 points by qubitsam 13y ago

devx 13y ago

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

Karunamon 13y ago
Indeed.. but honestly, I'm not hopeful. I would have thought that shenangians on the level going on in the NSA (for as long as they've been at it) would have led to more conscience-burdened folks blowing the whistle either in public as Snowden did, or more covertly. But who knows. Maybe Snowden emboldened a few people who will be able to shine some light on these things in a more quiet manner.
sillysaurus2 13y ago
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.
- derefr 13y ago
  I imagine these arguments usually come from a perspective that the US should be as weak as it would be with all its cards on the table; possibly coupled with the idea that if we're spending $500b/yr on defense, going down a few rungs on the power ladder still leaves us above everyone else. It's a very populist idea--that we can trade tactical power (the kind you get from having secrets) for strategic power (the kind you get, supposedly, by having the average voter participating in the decision-making process.) Let alone that the military isn't under congress...
- sneak 13y ago
  http://youtu.be/ZmwRgTSqT9U http://youtu.be/ZmwRgTSqT9U
- fnordfnordfnord 13y ago
  >weakening the American government. There are some who believe that wasting incredible resources on military / defense is actually weakening the country in light of the fact that we have no superpower enemy with even the remote potential to match our military. This leaves us vulnerable to other novel attacks, as well as just spending ourselves into oblivion. You know, the same way we 'overcame' the USSR's military threat via the arms race when their economy could not match the pace of ours. Yes, the US gov't should be weakened by any account; given the degree which it has overstepped its stated bounds.
- yk 13y ago
  Leaking the intelligence budget was probably the most justified leak. Even if you want a geopolitically strong American government, the intelligence budget tells the public how much effort the USG puts into covert programs. So without it you can not have a meaningful debate about the size of the intelligence agencies. But on the other hand, I do not believe that other agencies can infer much from it, since everybody already knows that there is a quite big budget. So even in a real politics interpretation, the budget tells other intelligence agencies, how nice the chess board is, not what strategy is played.
- venomsnake 13y ago
  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.
- natrius 13y ago
  The American government is collecting as much data about as many humans as it can, which I find morally repugnant. I support efforts to make that more difficult, even if it weakens the American government.
  - engrenage 13y ago
    Government strength is relative. Weakening the American government is equivalent to strengthening other Governments. Would you mind telling us which ones you prefer and why they are morally superior?
    - CamperBob2 13y ago
      Weakening the American government is equivalent to strengthening other Governments. No, building petabyte-scale data centers to spy on you and me is what's weakening the American government. We're not the problem, right? The NSA is like the drunk who looks for his lost keys under the lamppost, "because that's where the light is." Not only does the American government's idea of a hypersecure state not make us any more free, there's vanishingly little evidence that it accomplishes its purpose of making us any more secure.
      - engrenage 13y ago
        The lack of evidence isn't surprising given that they are a spy agency. They may not be protecting the US from terrorism, but there are major geopolitical adversaries at work who have no scruples about using cyberwarfare techniques. There is something akin to the Cold War in play, and the NSA is a significant part of the US's position in that war.
        CamperBob2 13y ago
        Sorry, 1% of America's GDP is too much to pay for a suit-and-tie version of Anonymous.
        13y ago
ianstallings 13y ago
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 more information on it because the secret will be no secret at all.
- wbl 13y ago
  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.
  - ianstallings 13y ago
    From that description you should be able to build one yourself..
- tomjen3 13y ago
  That might happen if you handle dry cleaning for the white house: http://newsbusters.org/blogs/brad-wilmouth/2010/10/21/abc-notes-bill-clinton-lost-nuclear-codes-while-president-maybe-jimmy http://newsbusters.org/blogs/brad-wilmouth/2010/10/21/abc-no...
  - ianstallings 13y ago
    I'm surprised they didn't mention Reagan. When he got shot the codes were lost in the hospital and found on the floor later.
rhizome 13y ago
Sounds like we need a Truth and Reconciliation Commission.

s_q_b 13y ago

The Economist: >Does the NSA have a quantum computer in the basement of its headquarters in Maryland (pictured above)? It is theoretically possible, but pretty unlikely... A Canadian firm called D-Wave is presently selling a specialised kind of quantum computer—Lockheed Martin, an American defence giant, and Google have each bought one—but it is not suitable for this kind of work. In-Q-Tel - "About Us" >"We make investments in startup companies that have developed commercially-focused technologies that will provide strong, near-term advantages (within 36 months) to the IC mission. We design our strategic investments to accelerate product development and delivery for this ready-soon innovation, and specifically to help companies add capabilities needed by our customers in the Intelligence Community. "D-Wave Systems, Inc., the World's First Commercial Quantum Computing Company, Secures $30 Million in a New Equity Round From Investors Including Bezos Expeditions and In-Q-Tel" [0] "Burnaby, BC - Milpitas, CA - October 4, 2012 - D-Wave Systems, Inc. today announced that it has closed a $30 million round of equity funding. Bezos Expeditions and In-Q-Tel (IQT) have joined the investment round. Bezos Expeditions is the personal investment company of Jeff Bezos. IQT is the strategic investment firm that delivers innovative technology solutions in support of the missions of the U.S. Intelligence Community." [0] http://www.dwavesys.com/en/pressreleases.html#investment_2012 http://www.dwavesys.com/en/pressreleases.html#investment_201...

seiji 13y ago
The most advanced math a quantum computer has done to date is "factored 21 into 3×7, with high probability (Martín-López et al. 2012)." Remember: companies are in the game of marketing hype to ride your scifi hopes and dreams. When you see a company saying "quantum" anything, discount their unqualified claims greatly. (Investors are not immune to being manipulated by hype. Claiming "they must be good because they have fancy investors!" provides no more weight to their ability than a hobo claiming he keeps the airplane aloft by snapping his fingers every 3.2 seconds.)
- devx 13y ago
  I think that's for "normal" quantum computers. D-wave is a different kind of quantum computer.

lazyjones 13y ago

Somewhat misleading title. No answers, just more questions on the topic.

frank_boyd 13y ago
Well, that's important to keep in mind: There are no answers and there will never be, b/c: We can never trust/accept any statements from any government, except for admissions of guilt.

derefr 13y ago

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 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 these "public" algorithms, you'll be able to tell; they'll soon be picking new Suite B ciphers. (There will be a time-delay, but not of the intentional "let's capture+break foreign transmissions before scaring them away from this cipher" kind. Re-securing our own transmissions takes priority, always. Even if it was broken because of some "quantum leap"--pardon the pun--we have to assume our enemies are advancing their own tech at roughly the same rate, so if we can crack it, they can too.)

quantumpotato_ 13y ago
By "our enemies" you mean enemies of the USG, I assume. I agree with your point, but do you think they'd force widespread cipher switch across government bodies? Or leave other government entities using broken encryption so they can more easiler spy?
sdevlin 13y ago
Suite B does not contain RSA. EDIT: To your latter point, some people would consider this to be a telling fact.
- sneak 13y ago
  Or non-EC DH, either. (It does include ECDH.) Perhaps they were simply anticipating DLP progress and wanted to be future-proof?
  - ctz 13y ago
    It's more likely because you can't achieve modern security levels with cryptosystems built on the DLP or IFP at acceptable performance. Suite B aims for 128-bit or 192-bit security levels; for comparison 1024-bit modulus RSA is currently thought to provide 73-bit security. (The next natural question is why the internet community is still failing to widely deploy cryptosystems with appropriate security levels. I don't know. But HTTPS, OTR and DNSSEC are all built of cheese in this respect.)

alcari 13y ago

This article does a few things that make it seem poorly written. First, there's the sentence "But, analysing a particular colossal number and trying to determine whether it possesses prime factors is colossally difficult." No, it's not difficult to determine whether a large number has prime factors. The answer to that question is yes. Determining which prime numbers are factors is extremely hard, and what they should have said. Second, they use an example from GCHQ's public key cryptography work rather than the more relevant NSA work on differential cryptanalysis, which became public knowledge in the late 1980s, was discovered by IBM in 1974, and which the NSA was already "well aware of" in 1974 [0]. [0]: https://en.wikipedia.org/wiki/Differential_cryptanalysis#History https://en.wikipedia.org/wiki/Differential_cryptanalysis#His...

kcorbitt 13y ago

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 secret that would go in the President's book of secrets right along with the existence of National Treasure or the Men in Black. :P Snowden would never have a clue.

yk 13y ago
Well, it would be a very well guarded secret. But even then the question is how public key crypto is broken. If they can easily generate exploits for implementations, because they know a essential implementation detail everybody else is missing, then it would be fundamentally different from being able to break RSA directly, or if they have a constructive prove of P=NP.
- deleted 13y ago
  [deleted]
- deleted 13y ago
  [deleted]
- cschmidt 13y ago
  Remember that factoring primes isn't know to be NP Hard. There is no complexity breakthrough required, we just don't know how to do it quickly. So we don't get P=NP from any factoring breakthrough.
  - yk 13y ago
    Depends on the breakthrough, we know that multiplication is in P and therefore factorization in NP. So a P?=NP breakthrough may or may not have consequences for integer factorization. ( Actually since I did write that, I wonder if P=NP would invalidate any public key crypto, since efficient encryption should be in P.)

ianstallings 13y ago

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

sseveran 13y ago
In fact if/when someone comes up with a working attack it will probably require ASICs to run cost effectively.
michaelt 13y ago
According to https://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html 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.

batgaijin 13y ago

p=np yo

shmageggy 13y ago
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#Difficulty_and_complexity http://en.wikipedia.org/wiki/Integer_factorization#Difficult...
- yk 13y ago
  Other way round, multiplication is in P, so integer factorization is in NP. And a breakthrough in P?=NP could have implications for factorization.
  - shmageggy 13y ago
    > so integer factorization is in NP I never said it wasn't. > And a breakthrough in P?=NP could have implications for factorization. Indeed, but what's implied in the article is that they might have made a breakthrough in factorization specifically, not in fundamental CS theory at large.
cheald 13y ago
Prove it.

ianstallings 13y ago

What worries me is that the breakthrough might just be a re-interpretation of the law.

officialjunk 13y ago

"algorithsm"

crazygringo 13y ago

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+New+Photograph+Of+Edward+Snowden%22 https://www.google.com/search?safe=off&q=%22Nation+Demands+N...

deleted 13y ago
[deleted]
dasil003 13y ago
Show some gratitude. You have no idea how many individuals had to sacrifice their personal lives to get that picture into the commons.
- advice4u 13y ago
  What do you mean? As far as I can tell, it is freely available on NSA's website: http://www.nsa.gov/about/_images/pg_hi_res/nsa_aerial.jpg http://www.nsa.gov/about/_images/pg_hi_res/nsa_aerial.jpg
  - lifeisstillgood 13y ago
    Perhaps it would sound better as "Many Bantha spies have given their lives to bring us that photo, General Calrissian" (I'm sure I have that wrong - so a prize to whoever corrects the quote from memory :-)
    - advice4u 13y ago
      *Bothans Banthas are the large beasts-of-burden on Tatooine. Bothans are humanoid aliens with cat/dog-like faces. Why do I know that? I play a lot of Star Wars video and card games :) EDIT: just googled for the quote. The full one is "Many Bothans died to bring us this information."

ig1 13y ago

There's at least two other significant possibilities: 1) There's an attack against RSA which doesn't involve factorization 2) There's an attack against AES / Serpent / Twofish I'd say the second is considerably more likely, firstly because the one NSA quote we have on it is "cryptanalyze, or break, unfathomably complex encryption systems" - which sounds much more like a new attack like differential cryptanalysis which provides a general purpose attack against complex symmetric crypto ("unfathomly complex" sounds much more like AES than RSA). In addition we have numerous quotes in recent days about how GCHQ is working on breaking the encryption on the Miranda hard-drive; which we now know to be a truecrypt drive.

twotwotwo 13y ago
On point 2, NSA still allows the use of AES-256 to protect top secret data: http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography
- ig1 13y ago
  Another option could be a practical attack on 128bit RC4. But I don't think the fact they're still using it means it hasn't been broken. Historically countries have sacrificed countless soldiers because saving them would have revealed that the enemy crypto-system had been broken.
- crazypyro 13y ago
  Why is everyone assuming the NSA has to be using their own standards, behind close doors?
  - harshreality 13y ago
    They don't. They use Suite A, which is an eclectic mix of proprietary algorithms. Firefly/Enhanced Firefly for key exchange (PKI), Joeski (allegedly a pair of algorithms for encrypting and decrypting other ciphers or firmware with the interesting property that encryption algorithm cannot be deduced from the decryption algorithm and vice versa), and a bunch of others. They have different algorithms depending on the specific information channel. Permanent data storage uses one (or perhaps a few), communications traffic uses others, and communications are further split depending on channel bandwidth and presumably long-term classification needs of the data. They have to recommend Suite B to the government and military in cases where NSA validated hardware can't be used. Examples would be military communications with allies, garden variety agencies that can't afford or can't be trusted with Suite A modules.

nilved 13y ago

As a rule of thumb, I don't take any article that refers to Snowden's leaks as "revelations" seriously. The only new information Snowden revealed is that their programs are called PRISM, upstream and xKeyscore; and if a journalist learned the details behind those programs from Snowden -- when they've been going on for at least a decade -- they clearly don't know much about the subject.

nodata 13y ago
What a ridiculous rule of thumb: Snowden got a lot of closely held information in front of the general public. If that doesn't count as a revelation, your standards are too high.
- nilved 13y ago
  No, he really didn't. We knew that the USA intercepted any Internet traffic they could get their hands on, and we knew that big data companies were in bed with the NSA. If the talking point is that Snowden got these facts on mainstream news, that isn't a revelation, that's marketing. "Relevation" implies the idea didn't exist beforehand.
  - nodata 13y ago
    So a revelation isn't the revealing of a secret to people who don't know the secret? (or to put it another way: revealing a secret to a population where the vast majority do not know it) Snowden revealed the scale of the operation too, and the depth of the rabbit hole.
    - nilved 13y ago
      Not if that information is already publicly and easily accessible to that group. If I was to post a link to an existing but obscure Wikipedia article on Hacker News, it would be as much of a "revelation" as Snowden's "revelations."

shortcj 13y ago

In view of this "breakthrough" leak, I am now supposing that Edward Snowden is a willing participant in psy-ops. "An all knowing deity is a cheap cop."