How is NSA breaking so much crypto? (2015)

https://freedom-to-tinker.com/2015/10/14/how-is-nsa-breaking-so-much-crypto/

by ColanR • 10 years ago

586 257 10 years ago

freedom-to-tinker.com

yuhong• 10 years ago

I wonder how long before real world SHA-1 collision ASICs come out. Or 64-bit KASUMI for that matter.

Spooky23• 10 years ago

NSA owns a fab. I'm sure they have one already!

schoen7• 10 years ago

(2015)

tribby• 10 years ago

For the nerds in the audience:

this line made me chuckle.

iamthepieman2• 10 years ago

If anyone is gonna break a lot of crypto, the NSA is. Who else has spent as much money, equipment and manpower on it? Who else has as many people working on it as they do?

blackflame70005• 10 years ago

Who else has the machines to do so as well.

user837387• 10 years ago

google, facebook, amazon?

vmarsy• 10 years ago

"Prior to our work, Internet Explorer, Chrome, Firefox, and Opera all accepted 512-bit primes, whereas Safari allowed groups as small as 16 bits"

I wonder what the minimum are today! (Article was from 2015)

ryuuchin• 10 years ago

I believe the minimum considered secure for standard DHE is 2048 bits. Qualys will label 1024 bit DHE exchanges as WEAK.

256-bit+ ECDHE is also considered secure on the standard curves (x25519, secp256r1, secp384r1).

joshAg• 10 years ago

minimum 1024. preferred is gonna be 2048 or 4096 if you have to use DHE. Actually preferred is ephemeral elliptic curve diffie hellman, or ecdhe.

PS: the logjam attack is related: https://weakdh.org/

Natsu2• 10 years ago

I had soooo much fun with that when I found out that one of my clients was connecting to a Logjam-vulnerable server and the OpenSSL-based code connecting to it suddenly failed without explanation after a security patch.

I found it by accident because I was able to reproduce with openssl s_server, which happened to be presenting a weak DH key by default as well.

ekimekim• 10 years ago

Fun story: when logjam broke, the company I was working for at the time immediately changed their SSL configs to require 2048-bit...then had to change it back the next day, because we had clients with ancient java versions that could only handle up to 1024. So we made do (and as far as I know, this company still makes do) with 1024 and a randomly generated dh_param.

darawk• 10 years ago

Hasn't this been essentially known for a long time? I'm not sure why that paper was even referenced. There's no breakthrough or new info here, people have speculated about this theoretical attack since forever.

Ar-Curunir4• 10 years ago

Yes, speculation is rampant, but the paper establishes that this is most likely what the NSA is doing, as opposed to breaking other crypto.

funnyfacts3652• 10 years ago

How is the paper more than speculation also? Because it's published as a PDF instead of a blog post? You guys are funny sometimes lol

mtgx• 10 years ago

Relevant:

https://weakdh.org/

McKayDavis• 10 years ago

There was a lengthy HN discussion when the article was originally published [1]

[1] https://news.ycombinator.com/item?id=10390822

dimino• 10 years ago

If they weren't doing it before, they should definitely be doing it "now" (2015)...

IOW, we have to assume they're doing it, and have been for at least as long as this paper has been out.

cryptothink• 10 years ago

// this comment has been removed by the U.S. Government

cmdrfred2• 10 years ago

Thank god, avoided some fake news yet again.

ozaark• 10 years ago

Propaganda is OK now[1]

Fake news is a reality of this ability

[1] http://www.businessinsider.com/ndaa-legalizes-propaganda-201...

LAMike• 10 years ago

There is a reason Satoshi used an elliptic curve algorithm for Bitcoin...

rphlx• 10 years ago

A future mathematical weakness in RSA/DSA could have been a concern, but 2 larger reasons to use EC in BTC are that a) signature computation is much faster, b) almost every 256-bit value is a valid key, allowing fast key generation that supports the (often ignored) recommendation to use a new key for each transaction.

divbit• 10 years ago

Also, lets not ignore the space savings for ec keys. The blockchain is huge, yet meant to be possible to run on a personal computer.

Mtinie• 10 years ago

Because he/she worked for the NSA and figured early "that shit was broke."

scott_karana• 10 years ago

What, because he worked for the NSA? I don't think so ;)

Godel_unicode6• 10 years ago

Why not? TOR was largely created by the US government, what makes you think BTC is different?

clarkmoody• 10 years ago

He also blinded the public key behind two different hash algorithms[1] for display as an address (RIPEMD-160 & SHA256). The public key of an address is only revealed in the output script when spending funds held by that address. Thus, with proper wallet behavior surrounding address reuse, your EC public key vulnerable for a short period.

Now, the private key must be secured properly, but that's the case with any crypto system.

[1] https://en.bitcoin.it/wiki/Technical_background_of_version_1...

mark-r2• 10 years ago

So do the adversaries we worry most about use the same prime numbers as everybody else, or do they come up with their own? It seems the most likely outcome is that the NSA is able to spy on Americans much more easily than they can spy on anybody else.

mirimir13• 10 years ago

Anyone can "come up with their own".

In Debian, install openvpn with easy-rsa. Then:

    # cd /etc/openvpn/easy-rsa
    # source ./vars
    # ./build-dh

Some time (depending on sources of randomness) later, you'll have a unique dh2048.pem key, aka prime, such as this one I just created:

    -----BEGIN DH PARAMETERS-----
    MIIBCAKCAQEA3Mdx5SV5kjdmq+QdTG+JIwkqdlsrXYitOTUK2GQdlRI9JhYFW3cZ
    6R1oLy14JbhTKTHEzRrljePCyJJDq1gAVAcIdIazNWFRnuAMRN5HdJcDyXluaajO
    k3u9HDVlIyTIDiJC6fNXuq76AQV1J+8V5t2s+nqhYFIjxxeXdSdGqeGlINgM+kMm
    cRZa77UTk3MZK0uEjxeZNFnMIW+laCUT96YB8Vs+PH+7JPeMPBWJP7yQmrSEkOgD
    h8BxnE+P+6lTgtNgd1wKDzdGd8wES7ObXhAcxhZnKSUIUyuzzaJtXDMsj/rXXQip
    xIXKARi8X7uCaYZUEh5qC2F+uBoPjV6NywIBAg==
    -----END DH PARAMETERS-----

vertex-four• 10 years ago

Or just run:

    openssl dhparam -out dhparam.pem 2048

mark-r2• 10 years ago

The question isn't about what's possible, the question is about common practice. If everybody used their own private prime numbers this wouldn't have been news.

ooqr2• 10 years ago

Thanks! I'll use that for all my secrets

Godel_unicode6• 10 years ago

You might be interested in googling Suite B. It lays out guidelines for encrypting government data up to the Top Secret level. If you dig a little bit, you can find guidelines for auditing crypto implementations and also for handling/generating key material.

Briefly, Suite B is AES-GCM, ECDH, ECDSA, and SHA2.

Edit: autocorrect

philip142au2• 10 years ago

Just a question, what does the NSA to do protect security with so many USA institutions hacked in recent years?

maehwasu• 10 years ago

a) It's extremely hard to defend against variants of social engineering, especially given the combinatorial proliferation of attack surfaces

b) the NSA doesn't really care about that aspect much

manquer• 10 years ago

Defense will never be perfect, however that is no excuse for not having dedicated organization training, audits and enacting and enforcing regulations strictly. While all of this may happen in bit and pieces, there is no single organization doing this and measuring their success by the number of attacks they prevent or failed to prevent.

NSA on the other hand wants backdoors and weakened cryptography tools...

andrewstuart22• 10 years ago

NSA is just the US Foreign Intelligence and Government protection agency [1][2]. They do nothing, and are expected to do nothing, to protect domestic civilian assets.

NIST [3] is possibly the closest agency I'm aware of that exists to disseminate knowledge and standards to civilian organizations, but they're more interested (per their website, anyway) in simply advancing US business to be competitive in the global marketplace. That, and we've seen that they will bend to the NSA over such critical things as which elliptic curve ought to be recommended for use.

[1] https://en.wikipedia.org/wiki/National_Security_Agency

[2] https://www.nsa.gov/what-we-do/

[3] https://www.nist.gov/about-nist

philip142au2• 10 years ago

If I go to the NSA website it says "How We Protect the Nation" - So I infer that they do some work to protect something, but the US government was hacked "5.6 million fingerprints stolen in U.S. personnel data hack" https://www.theguardian.com/technology/2015/sep/23/us-govern...

The Democrat and Republican computers recently hacked, you will say they are not specifically government since they are political parties.

Many more US government hacks and leaks on a large scale I don't need to list.

So I assume from your answer that they are tasked at protecting USA government assets, but it seems they don't do a good job.

oh_sigh• 10 years ago

NSA has no say in private group emails(such as the DNC).

Godel_unicode6• 10 years ago

Or in the non-DoD branches of government. That's some combination of the FBI and DHS (specifically NCCIC and US-CERT).

https://www.us-cert.gov/about-us

mirimir13• 10 years ago

Reputable VPN services use custom DH keys. At least 2048-bit. And they change them periodically.

clord• 10 years ago

This article cuts to the heart something I've wondered for a long time.

The common advice in all the classic texts is that developers should not roll their own crypto because smarter people have thought of more vulnerabilities and addressed them in battle-tested code.

But news like this shows that there is an antithesis: the conventional encryption techniques are also potentially widely exploitable by state-level actors. Furthermore if I was someone holding solutions to cherry-picked primes for well-understood algorithms in wide use, I'd be complaining loudly every time someone wrote a bespoke library too. I'd be paying to publish books that recommend no one write their own crypto because it's just such a darned hard problem, especially with so many high quality alternatives out there tested and ready to go.

Granted, one should certainly have a repulsion to to writing custom crypto for all of the many good reasons, but it makes me think it's worth putting in more than the minimal effort into it, especially when lives are on the line.

quickben• 10 years ago

Think of it this way: the propaganda worked.

Godel_unicode6• 10 years ago

What do you think is propaganda, exactly? That crypto is hard to do well?

bsder• 10 years ago

But news like this shows that there is an antithesis: the conventional encryption techniques are also potentially widely exploitable by state-level actors.

Are they? Really? We know that NSA has lots of vectors for exploiting the system AROUND encryption. We have pretty solid evidence that the NSA has weakened some encryption standards to make them crackable.

We DON'T have evidence that encryption developed outside the milieu of the NSA are equally crackable. And circumstantial evidence suggests quite the opposite.

The problem is that there are lots of things to get right to get crypto right, and getting even one wrong leads to failure. Which is why we tell people not to roll their own encyption and to let the experts do it.

Another problem with too many people rolling their own encryption is that it dilutes attention and no system gets sufficiently audited.

rainloft• 10 years ago

It took 33 years before it was publicly announced that GCHQ succeeded in deciphering Enigma codes.

Every single time they used intercepted intelligence to their benefit, they made sure to leave false trails of other ways they could've known so the Germans wouldn't suspect.

I would expect the NSA could hide it well.

bonzini• 10 years ago

We also know that the NSA hardened crypto against attacks that they knew but were not advertised to the public (DES against differential cryptanalysis, and SHA0). I guess the NSA is too big to be homogeneously the good guy or the bad guy.

rl3• 10 years ago

I recall an interview with William Binney where he suggested simply rearranging your message's payload at the protocol level would be enough to thwart automated analysis. It would require human attention, which is ultimately finite.

The trade-off there is that it might draw unwanted attention. Such an approach may be more suited for use inside of a message already encrypted using standard means.

It's worth noting that if there's no network interception angle, the NSA can easily penetrate all but the most hardened systems should they be so inclined.

pandler• 10 years ago

rearranging your message's payload at the protocol level

Do you have an example of how you might do that? Something like (real basic example) reversing a json payload?

{"key": {}} becomes {{}: "yek"}

Or is that too simplistic?

Zilroy• 10 years ago

Binney is suggesting the proper approach - safe manual customizations that require manual cryptanalyzis, which is not scalable.

If only few % of users start to roll out their own custom crypto, not stronger than ROT-13, that would completely overwhelm the interception industry, including the state-level players. There is no automated tool that can cryptanalyze in real time someone's naive but unique idea what crypto should be.

In other words, this is shifting the paradigm where few high priests of the open source crypto design few key components for billions to use, and cryptanalysis has to deal with only few problems which are eventually automated, to the problem where tens of thousands of brains construct their own weird crypto which has to be manually cryptanalysed. Cryptanalyzers would need to employ millions to achieve this.

Feel free to do this on top of the blessed crypto stacks.

cookiecaper3• 10 years ago

I think the fact is that in most cases, you can't do much about government actors, especially not the US. All you can do is use the best crypto that's available and hope that the government hasn't cracked it yet (but you should always expect that the message will be as good as plaintext in 30 years).

If you roll your own crypto, you're liable to have the guy down the street spot an issue in your custom implementation and walk out with all the goods before you realize what happened.

Maybe the most technologically advanced spy agency in the world can decrypt some industry-standard encryption if your messages are interesting enough and it justifies the time-cost (police, prosecutors, and laypeople still can't), but probably someone on HN can pick out errors with your custom cryptography and render it useless, at least until you've really spent a great deal of time testing and refining it. That's the difference, IMO.

wfunction14• 10 years ago

If you roll your own crypto, you're liable to have the guy down the street spot an issue in your custom implementation and walk out with all the goods before you realize what happened.

Isn't it quite obvious that you can have multiple layers of crypto? Like your own on top of a standard one? Why do you (and a lot of people, not just you) set up a silly strawman argument whenever talk of rolling your own crypto comes up in any online forum?

wfunction14• 10 years ago

Thanks for saying exactly the same thing that's come to my mind over and over again. I would totally roll my own crypto on top of an existing cryptosystem if I could and if someone with this much computational power was in my threat model. That way I would get the best of both.

Same goes for hashing by the way: I'd totally stack multiple hash functions on top of each other too. But in this I'd only stack cryptographic ones that have not yet been broken; I wouldn't roll my own.

Taek3• 10 years ago

You never get the best if you roll your own. The problem is that there are many broad classes of attack that cover wide ranges of knowledge. If OpenSSL can't get TLS right, how do you expect to get your home-rolled crypto right?

If you choose to roll your own, you will almost certainly have more vulnerabilities that are easier to find. Your gamble is that agencies like the NSA are already holding vulnerabilities to the common libraries, and that it's more expensive for them to break your weaker crypto (it will be weaker even if you are world class) because they have to take time to break it.

Edit: stacking multiple hash functions naively is a bad idea as well. As a thought experiment, let's say that I have a hash function that is effectively (because the NSA broke it) as useful as converting the input to all zeroes. Stacking more hashes on top of that hash won't help you, because it will still be trivial to find collisions.

feelix• 10 years ago

I wonder if a good way to go would be to implement standard encryption (AES in most cases), and then take that encrypted payload and encrypt it with your custom code that you designed.

So even if it's actually true, and that you shouldn't roll your own encryption in practice, even if they do break yours they'll still have to get through the AES as well. So it's a no risk addition.

0x0• 10 years ago

It's never a no-risk addition. Perhaps your custom code is buggy and ends up adding in random memory contents that happened to contain both your AES key and your custom crypto key, into the message payload ala heartbleed.

rlpb• 10 years ago

A contrary way of looking at this is that we can expect standard crypto implementations to switch to randomizing chosen primes. If you had been rolling your own, would you keep up to date with the state-of-the-art and switch, too?

Most hand-rollers probably won't, IMHO, because they don't have enough resources to spare a person to keep up with the art, let alone keep their own implementations up to date with it.

...I was someone holding solutions to cherry-picked primes for well-understood algorithms in wide use, I'd be complaining loudly every time someone wrote a bespoke library too.

Sure. This is pretty standard adversarial stuff, though. It's up to researchers to figure things out and publish. I don't see any evidence that this isn't happening. This article is a perfect example!

mirimir13• 10 years ago

There's some serious confusion here, I think. Maybe it's local [;)] but here goes ...

Furthermore if I was someone holding solutions to cherry-picked primes for well-understood algorithms in wide use ...

Well, the article notes:

For the nerds in the audience, here’s what’s wrong: If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn’t just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to “crack” a particular prime, then easily break any individual connection that uses that prime.

That prime is the "dhparam.pem". It's used in bootstrapping the encrypted connection. And it's my understanding that this is entirely distinct from the issue of "cherry-picked primes for well-understood algorithms in wide use". This vulnerability is simply using "standardized or hard-coded primes". Cipher vulnerabilities are about ...

And that's where my understanding ends. Maybe someone can complete the argument. Or sort me out ;)

agumonkey4• 10 years ago

cryptodiversity ?

alkonaut4• 10 years ago

What if 2048 bit was the standard? What if people used multiple passes with different primes? (That may not give any improved security, I'm. not familiar with the details).

It seems like a massive waste of energy and money to crack a few primes if the advantage you gain can be erased so quickly?

I agree it seems like writing custom bad crypto is way better than good crypto that can be broken in bulk. (Using both kinds together seems clever). A good analyst can likely break my homemade crypto in twenty minutes, but that's orders of magnitude better than using a compromised strong crypto!

Another question: Are good primes that hard to come by? Shouldn't apps generate new primes instead of re-using old ones?

Last question: are there good cryptos that aren't sensitive to a state level actor that can factor primes in linear time?

marcosdumay2• 10 years ago

Are good primes that hard to come by?

My laptop takes around 2 minutes to get a pair of 4k bits primes for DH parameters.

The problem is that people want their installers to be instantaneous. Those 2 minutes are too long.

caf• 10 years ago

Elliptic curve cryptography is unrelated to the integer factorisation problem.

rahrahrah5• 10 years ago

You're making the argument "If I apply good crypto plus crypto which might or might not be good, the worst case scenario is that I end up with crypto which is at least as good as the good crypto."

You're the perfect example of Dunning-Kruger, where your skills at crypto are really bad so lack the knowledge to evaluate your crypto skills. You're exactly the kind of person that advice is aimed at.

Helmet• 10 years ago

This comment boils down to: you're wrong and you're stupid.

Also, and quite ironically, you have misinterpreted and are misapplying the D.K. effect. Can you care to explain why the above wouldn't be true? Does an extra layer of bad crypto diminish the effectiveness of the good crypto? It doesn't seem like it would, and OPs statement reads more like a reasonable logical assumption, but I know very little about crypto, which is why I ask.

harpiaharpyja• 10 years ago

You're making the argument "If I apply good crypto plus crypto which might or might not be good, the worst case scenario is that I end up with crypto which is at least as good as the good crypto."

I'm really not seeing how you pulled that argument out of the GP's comment.

Lagged2Death2• 10 years ago

...the conventional encryption techniques are also potentially widely exploitable by state-level actors.

That really depends on how you define "conventional encryption techniques." As is so often the case, this proposed line of attack isn't against the crypto proper, but against habitually poor implementation details. Human laziness, really. They're not picking the locks, they've found a way to steal the keys.

agwa2• 10 years ago

Your comment shows a very dangerous misunderstanding of this issue. One of the reasons WeakDH/Logjam was so bad is because OpenSSL is so low-level that it forces application developers to supply their own DH parameters if they want to use Diffie-Hellman. Until recently, setting DH parameters required writing complicated code which required the application developer to understand obscure details of TLS like export ciphers, as well as whether it was safe to reuse temporary Diffie-Hellman keys.

In other words, OpenSSL forced developers to do crypto to use Diffie-Hellman. Unsurprisingly, developers did a poor job, and we got WeakDH/Logjam/CVE-2016-0701 as a result. The answer is not more hand-rolled crypto as you suggest, but rather better crypto libraries written by experts that leave as few details to the application developer as possible.

javajosh2• 10 years ago

So basically your point is that if app devs can't get DH parameters right, how on earth will they get the harder stuff right? I think that's a fine point, but you aren't really addressing the core concern, which is that "better crypto libraries written by experts" are precisely the ones most likely to be vulnerable to state actors doing massive prime computations. And by extension, state actors benefit from homogeneity of implementation.

Even if it takes a day for a kid at the NSA to break my custom crypto, that's better than if I use homogenous crypto that takes 2ms to break. And if everyone is using bad custom crypto, that's a lot of time needed to break each one individually. The argument is very close to that against monolithic grain cultures that, while they have the best yields, resisitance to pests, and so forth, they are also more vulnerable to as-yet-unknown diseases. Bio-diversity is a good defense against that contingency.

collinmanderson• 10 years ago

How much is DH used currently? Isn't https traffic mostly ECDHE now? Hasn't the issue mostly been fixed now?

https://www.ssllabs.com/ssltest/analyze.html?d=news.ycombina...

ape4• 10 years ago

Perhaps the solution is an audited framework for rolling your own crypto. This way you just need to write one small module. But everything else is handled using secure professional ways - eg key exchange, memory wiping, etc.

Ar-Curunir4• 10 years ago

You really believe the entire cryptographic community is so thoroughly morally compromised? The same community that has been investigating and fighting the NSA's wrongdoings?

Crypto is hard; coming up with sound cryptographic primitives is highly nontrivial if you do not have the right training. Even if you have the mathematics to back it up, safely implementing the mathematics is in itself tricky, with all kinds of side channel attacks potentially breaking your scheme.

jpitz• 10 years ago

It's not necessarily that the whole community is compromised, it's that the goals of an organization devoted to signals intelligence align here with the guidance of the community, fostering what converges towards a monoculture.

disposablezero• 10 years ago

Always, always, always generate your own SSH moduli.

notyourwork2• 10 years ago

For those uninformed you should expand on this to. It is a great suggestion but a statement like this to a uninformed isn't very helpful.

poisonarena• 10 years ago

please elaborate!

knweiss• 10 years ago

From the OpenSSH moduli(5) man page:

  "When performing Diffie-Hellman Group Exchange, sshd(8)
  first estimates the size of the modulus required to
  produce enough Diffie-Hellman output to sufficiently
  key the selected symmetric cipher. sshd(8) then randomly
  selects a modulus from /etc/ssh/moduli that best meets
  the size requirement."

The problem is

a) OS distributions ship pre-computed moduli in the /etc/ssh/moduli file. I.e. most users don't change these moduli. This facilitates pre-computation attacks.

b) These moduli are often too short (<2048 bit).

You can create your own moduli with ssh-keygen (see the "MODULI GENERATION" section in the ssh-keygen manpage).

FWIW: Here's my open bug for RHEL7 where I try to convince Red Hat to improve the situation (including more details and references):

https://bugzilla.redhat.com/show_bug.cgi?id=1396943

TazeTSchnitzel• 10 years ago

(2015)

jokoon2• 10 years ago

I saw somewhere that they were using custom built hardware modules to break AES keys, some kind of FPGA thing. It was cheap to build and extremely fast since it was specialized in doing just that.

Godel_unicode6• 10 years ago

I've seen this hypothesis before. What I haven't seen is anything more concrete than "I heard about a guy who knows a guy who sold the pspice license that was used to..."

jokoon2• 10 years ago

I could remember seeing some photo, cannot remember where.

retox• 10 years ago

I read that in the Dan Brown book, Digital Fortress.

dancek• 10 years ago

I don't know why this is downvoted. Might be the correct explanation to "I saw somewhere".

willholloway• 10 years ago

We just have to look at the world of bitcoin mining to see that custom fabricated ASICs would wipe the floor with general purpose CPUs for this kind of task.

Intel 3930k = 66.6 Mhash/s AntMiner S9 ASIC = 14,000,000 Mhash/s

tromp• 10 years ago

A single S9 uses 189 BM1387 chips to achieve that 14TH/s.

So that's only 74074 Mh/s per ASIC.

Granted, that's still wiping the floor...

triplesec• 10 years ago

It may be worth noting that author J Alex Halderman is the professor who has done the most recent work on publicising the dangers of the probability of Russian hacking of the US election. https://medium.com/@jhalderm/want-to-know-if-the-election-wa...

Fnoord• 10 years ago

Not only that, remember the Diebold debacle around GWB election? He was one of the people who hacked that machine, and researched other voting machines as well. He's running a course on Coursera called Securing Digital Democracy https://www.coursera.org/learn/digital-democracy I can highly recommend it.

tgarma1234• 10 years ago

I can't remember where I read a longer explanation of this but a quick google search got me to this blog entry http://www.scottaaronson.com/blog/?p=2059 where the topic comes up. I think that for the most part what we civilians know as cryptography is often either a red-herring, a trick, or woefully out of date from the point of view of what the professional state actors know how to do. Anyway you get that impression from declassified documents. Crypto works well enough for commercial and civilian purposes but has no impact on militarized hacking I think. Please correct me if I am wrong but I think this is all by design, even going so far as the NSA putting backdoors in CPUs and suchlike. If they send a company a national security letter that insists on compliance, the company not only has to comply but also can't legally disclose to the public that they complied, so we can't really know the truth here.

eganist• 10 years ago

Admittedly commenting without having jumped into the content here, but from what you're describing, it sounds less about how state actors are "breaking so much crypto" and more about how state actors are "breaking so many cryptographic implementations."

This might also explain the possible shift away from compromising algorithms (with perhaps the notable exception of Dual_EC_DRBG): the IC knows well enough that everyone's going to do just enough things wrong in _implementing them_ that it's perhaps more beneficial to promote unweakened ciphers in the grand scheme. Heck they could even promote sound implementation practices and have the confidence to know any one target will gum something up just enough to give them a way in.

But who knows. Odds are still decent that I'm wrong with the compromised algorithms assertion.

technofiend• 10 years ago

I sat in a two day class this week put on by people who claimed to be former intelligence agency types. They told a lot of entertaining stories about how far they'll go to both protect their own secrets and gain everyone else's.

Some of their advice seemed useful but some of their suggestions absurd and conclusions naive. The most interesting thing was that challenging them on their assertions (anti-virus is only n% effective) didn't result in any facts to back up the assertions. Instead they'd just mock the challenger and say things like "no matter what you do we can crack your systems in n minutes, regardless".

In fact one of their suggestions was to simply fire anyone who didn't have like-minded world views. People who didn't just nod along with whatever they had to say were the problem and needed to go. If that's how the intelligence community works I can see why they are in an echo chamber that justifies their any means necessary approach to intelligence gathering.

npiazza83• 10 years ago

People complain about Silicon Valley's obsession with culture fit, infantilizing its employees, and supplanting an actual adult life with 'perks' but truth be told only the last one is a SV invention. (government standard raises and hours are probably the only good thing about such jobs)

danbmil99• 10 years ago

FWIW, someone well-known and widely respected in the high tech community told me many years ago that he had consulted at the NSA, and they had computers that could crack 1024-bit RSA.

This would have been around 2001-2002.

heartbreak• 10 years ago

There was significant discussion around 1024-bit RSA keys around that timeframe. Here's a discussion of it from RSA Labs. Make note of the links in the References section: https://www.emc.com/emc-plus/rsa-labs/historical/has-the-rsa...

jheriko2• 10 years ago

i'm thinking they grossly overestimate the problem of cracking a 1024-bit prime... based on my dabbling in that area its certainly possible for a network of machines to do it, and with modern gpus and good number implementations on them, i don't think that days long, or even overnight, cracking is a stretch if you have a few spare machines lying around....

nkurz• 10 years ago

Are you possibly misinterpreting the terribly imprecise phrase "cracking a 1024-bit prime" as being the same as factoring a single number with two prime factors? I don't really understand what's involved with the actual process, but there was some discussion here earlier: https://news.ycombinator.com/item?id=10391925.

Alternatively, if you do correctly understand what's being done, it would be be interesting to hear how you made your estimate. Based on other examples, I agree that it might not be impossible that the "usual approaches" could be sufficiently optimized on commodity hardware to get the 100x or 1000x gain you would need for this.

jheriko2• 10 years ago

its the reverse modular exponentiation problem right?

e.g. some a is transformed into b by x^a mod y = b where y is a prime and x has special properties relative to it?

doing that once each, sharing the resulting b's then using the b from the other person raised to the power of your original input a to create a number that is kept secret (because a was kept secret) - so if you can get a back from b (x and y are not secret) then you can work out the derived secret number and its not so secret anymore

its true that for large numbers this becomes harder, and there are many a's for a given b, but iirc the properties of modular arithmetic make them identical in effect, such that finding any a is good enough to crack the key exchange.

... is that right?

j1vms• 10 years ago

Use a one-time pad (and distribute "securely") for anything you want to encrypt as best as possible. Consider everything else in the open already, or at some not too far off time in the future.

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

tsaoutourpants• 10 years ago

Practical advice, there.

edblarney• 10 years ago

The quality of information on this this thread is unbelievable, it makes me feel stupid. Are all these commenters crypto experts or do some devs just have such in-depth knowledge of the subject. Heyzeus.

sebow• 10 years ago

Correct me if i'm wrong but doesn't NSA have a quantum computer for few years now?

I mean my guess is that they're investing more in how to engineer software used by such things.

Etheryte• 10 years ago

A "quantum computer" is a very, very broad term.

How is NSA breaking so much crypto? (2015)

Related Stories