17 ms·
How is NSA breaking so much crypto? (2015)
- yuhong 10y agoI wonder how long before real world SHA-1 collision ASICs come out. Or 64-bit KASUMI for that matter.
- Spooky23 10y agoNSA owns a fab. I'm sure they have one already!
- schoen 10y ago(2015)
- tribby 10y ago>For the nerds in the audience: this line made me chuckle.
- iamthepieman 10y agoIf 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?
- blackflame7000 10y agoWho else has the machines to do so as well.
- user837387 10y agogoogle, facebook, amazon?
- rahrahrah 10y agoOh really? Those companies each have 100m-worth of crypto-breaking hardware? Ok then.
- blackflame7000 10y agoYea pretty sure google, facebook, and amazon servers are busy, you know, running google, facebook, and amazon. Business can't afford to have resources like that NSA sitting around for test. The government throws out more hardware in a day then most business buy in a year. Literally thousands of perfectly good i7/i5s being destroyed because they don't have up to date TPM / secure boot stuff
- mabbo 10y agoEach of those companies needs enough hardware to handle their highest expected loads. But most of the time, they aren't near their peak needs, leaving a lot of hosts sitting idle. AWS and other cloud providers face the same situation, but to another order of magnitude. These leftovers would be enough to match what the NSA has.
- deleted 10y ago[deleted]
- robotresearcher 10y agoHow do you know?
- iamthepieman 10y agoThis is not true
- petre 10y ago> These leftovers would be enough to match what the NSA has. They still need power to run theese, space to store them. All of that costs money. Why woold a private org break crypto if it has nothing to gain from it? And besides, people willingly give their data to Google, Facebook, Amazon. Why would theese orgs need to crack anything at all?
- vmarsy 10y 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 10y agoI 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 10y agominimum 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/ https://weakdh.org/
- Natsu 10y agoI 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.
- Natsu 10y agoJust in case the above is not clear enough, newer versions of OpenSSL refuse to connect to anything with a weak DH key and nothing was showing up in our logs, making it extra confusing.
- ekimekim 10y agoFun 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 10y agoHasn'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-Curunir 10y agoYes, speculation is rampant, but the paper establishes that this is most likely what the NSA is doing, as opposed to breaking other crypto.
- funnyfacts365 10y agoHow 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 10y agoRelevant: https://weakdh.org/ https://weakdh.org/
- McKayDavis 10y agoThere was a lengthy HN discussion when the article was originally published [1] [1] https://news.ycombinator.com/item?id=10390822 https://news.ycombinator.com/item?id=10390822
- dimino 10y agoIf 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.
- deleted 10y ago[deleted]
- cryptothink 10y ago// this comment has been removed by the U.S. Government
- LAMike 10y agoThere is a reason Satoshi used an elliptic curve algorithm for Bitcoin...
- rphlx 10y agoA 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 10y agoAlso, 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 10y agoBecause he/she worked for the NSA and figured early "that shit was broke."
- scott_karana 10y agoWhat, because he worked for the NSA? I don't think so ;)
- Godel_unicode 10y agoWhy not? TOR was largely created by the US government, what makes you think BTC is different?
- YCode 10y agoIt always kind of makes me chuckle when I read a comment about using TOR to stay off the grid and away from government spying. I can't help but think, at least in principal, should you be using something they created and then gave away?
- 10y ago
- mark-r 10y agoSo 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.
- mirimir 10y agoAnyone 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 10y agoOr just run: openssl dhparam -out dhparam.pem 2048
- philip142au 10y agoJust a question, what does the NSA to do protect security with so many USA institutions hacked in recent years?
- maehwasu 10y agoa) 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 10y agoDefense 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...
- andrewstuart2 10y agoNSA 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 https://en.wikipedia.org/wiki/National_Security_Agency [2] https://www.nsa.gov/what-we-do/ https://www.nsa.gov/what-we-do/ [3] https://www.nist.gov/about-nist https://www.nist.gov/about-nist
- philip142au 10y agoIf 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-government-hack-stole-fingerprints 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.
- mirimir 10y agoReputable VPN services use custom DH keys. At least 2048-bit. And they change them periodically.
- clord 10y agoThis 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 10y agoThink of it this way: the propaganda worked.
- Godel_unicode 10y agoWhat do you think is propaganda, exactly? That crypto is hard to do well?
- patall 10y agoI think he means that we are encouraged by propaganda to assume that all crypto is broken, so that we do not even attemp to use it as that would just take more time to implement with no additional security for us. "Why should I use Signal if it is no more save then WhatsApp but just less convienient?"
- bsder 10y 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.
- disposablezero 10y agoAlways, always, always generate your own SSH moduli.
- notyourwork 10y agoFor 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 10y agoplease elaborate!
- knweiss 10y agoFrom 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 https://bugzilla.redhat.com/show_bug.cgi?id=1396943
- alkonaut 10y agoMost people with desktops are using Windows. What are the best practices there?
- TazeTSchnitzel 10y ago(2015)
- jokoon 10y agoI 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_unicode 10y agoI'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..."
- jokoon 10y agoI could remember seeing some photo, cannot remember where.
- retox 10y agoI read that in the Dan Brown book, Digital Fortress.
- dancek 10y agoI don't know why this is downvoted. Might be the correct explanation to "I saw somewhere".
- willholloway 10y agoWe 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 10y agoA 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 10y agoIt 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-was-hacked-look-at-the-ballots-c61a6113b0ba#.gmhktqr03 https://medium.com/@jhalderm/want-to-know-if-the-election-wa...
- Fnoord 10y agoNot 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 https://www.coursera.org/learn/digital-democracy I can highly recommend it.
- tgarma1234 10y agoI 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 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 10y agoAdmittedly 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 10y agoI 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 10y agoPeople 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 10y agoFWIW, 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 10y agoThere 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-algorithm-been-compromised.htm https://www.emc.com/emc-plus/rsa-labs/historical/has-the-rsa...
- jheriko 10y agoi'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 10y agoAre 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 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.
- jheriko 10y agoits 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 10y agoUse 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 https://news.ycombinator.com/item?id=13057816
- tsaoutourpants 10y agoPractical advice, there.
- edblarney 10y agoThe 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 10y agoCorrect 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 10y agoA "quantum computer" is a very, very broad term.