19 ms·
How is NSA breaking so much crypto?
- AnonNo15 11y agoCrap. So what are the immediate countermeasures? Switch to elliptic curves cryptography?
- 6502nerdface 11y agoDon't use out-of-the-box Diffie Hellman params, I suppose. See, e.g., [1,2]. [1] https://weakdh.org/ https://weakdh.org/ [2] http://security.stackexchange.com/questions/42415/openvpn-dhparam http://security.stackexchange.com/questions/42415/openvpn-dh...
- cperciva 11y agoDon't use out-of-the-box Diffie Hellman params Wrong answer. Standard primes are fine; just avoid the small ones. If you try to select your own parameters you're probably going to pick wrong, either in the sense of breaking the crypto or making people wonder if you selected your parameters to hide a backdoor. The standard large primes (my preferred option is the "group #14" 2048-bit prime) were very obviously not selected maliciously, and there's no way anyone has done the precomputations necessary to index that group.
- runn1ng 11y agoThis is a newbie question, but how are the standard primes created? How is it ensured that they are not selected maliciously, etc? (a link will suffice)
- cperciva 11y agoThe standard prime groups have their highest and lowest 64 bits set, and as many as possible of the rest taken from the binary expansion of pi. The group #14 prime for example is p = 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 } The value 124476 is the smallest non-negative value which results in p and (p-1)/2 both being prime and 2 being a quadratic residue mod p; this ensures that the subgroup {2^0, 2^1, 2^2, 2^3, ... } is cyclic. We assume that the binary expansion of Pi is not selected maliciously. ;-)
- cantrevealname 11y agoAnd as an amusing tidbit, here is the actual value in hex: FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F 83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D 670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9 DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510 15728E5A 8AACAA68 FFFFFFFF FFFFFFFF Source: https://tools.ietf.org/html/rfc3526#section-3 https://tools.ietf.org/html/rfc3526#section-3
- webmaven 11y ago> We assume that the binary expansion of Pi is not selected maliciously. ;-) Well, I suppose that we must assume that, as assuming otherwise is self-defeating: anyone running the simulation we're living in already has direct access to the plaintexts anyway.
- qb45 11y agoThat somebody maliciously caused the circle's circumference to diameter ratio to be insecure in this application is indeed not an issue. However, a possible danger is that somebody maliciously suggested using π instead of e...
- cperciva 11y agoTrue, but Pi is pretty much tradition now... enough so that when Decorrelated Fast Cipher used e instead, it raised some eyebrows.
- wfunction 11y ago> (a link will suffice) https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
- andrius4669 11y agopretty good presentation on that by djb: https://projectbullrun.org/surveillance/2015/video-2015.html#bernstein https://projectbullrun.org/surveillance/2015/video-2015.html...
- dfc 11y agoAre there reasons other than speed/resource-usage for not using 15-18? Or put another way do you prefer group #14 above all others or is #14 the lowest level of security you are comfortable with?
- cperciva 11y agoSpeed is the main reason. Going bigger doesn't gain you anything; in some cases it may lose you something since slower arithmetic makes it possible to exploit lower-bandwidth side channel attacks.
- throwaway7767 11y ago> If you try to select your own parameters you're probably going to pick wrong, either in the sense of breaking the crypto Is there any known situation in which generating parameters with 'openssl dhparam' will give you broken/weak parameters? > either in the sense of breaking the crypto or making people wonder if you selected your parameters to hide a backdoor This is a concern if you're going to distribute your parameters with software, but it could make sense where a sysadmin controls both endpoints, such as a site-to-site VPN.
- 6502nerdface 11y ago> > Don't use out-of-the-box Diffie Hellman params > Wrong answer. Standard primes are fine; just avoid the small ones. Sure, that's what I meant insofar as the out of the box params are apparently too small in many apps/libs. The links I gave cover it pretty well, I think, no?
- aruss 11y agoECC just shifts the problem domain. Just change your curve/prime modulus often and don't use NSA-recommended parameters.
- tptacek 11y agoThat's a terrible idea, trading an extremely unlikely weakness (a problematic 2048 bit standard prime) for an extremely likely weakness (a mistake in the code you probably won't even think to write to check your constantly changing parameters). Do what Colin says upthread.
- aruss 11y agoFirst, to clarify: what I meant by "your" was an entity like a standards community, not an individual, and by "often" I meant within a timeframe that makes bruteforcing parameters infeasible (which itself changes over time wrt the size of the parameters). Key rotation for example is just good practice. Nothing that I said was wrong - nor does it contradict Colin's advice - and while simple systems are better, that's a tradeoff that should be made if you care about entities with lots of resources like e.g. the NSA. As history shows, bad parameters (or parameters that are feasibly bruteforced over a particular timeframe) are not an 'unlikely' weakness. Besides, being aware of potential vulnerabilities - especially those that you know pose real threats - and not addressing them is simply bad practice.
- njharman 11y agoDon't be a target the NSA is interested in.
- avn2109 11y agoNot possible; they interpret their mandate as universal.
- wernercd 11y agoBy stating your intent to not be noticed, you have drawn their eyes. Why else would you want that if you aren't trying to hide something?
- crpatino 11y agoIt's a pretty safe bet that everyone here - a forum called "hacker news" which discusses, among other things, the several aspects of online security - is already on a watch list. The idea is to not promote yourself even further in their attention.
- a3n 11y agoWhat is the first non-interesting integer? If it's N, then N becomes interesting, as the first non-interesting integer.
- chris_wot 11y agoI was so uninteresting I became interesting.
- bburshteyn 11y agoHave you checked out http://www.cryptomove.com http://www.cryptomove.com? The thesis is precisely that encryption is a losing game of cat and mouse, so instead continuous concealment is the last line of defense.
- Natanael_L 11y agoMore ciphertext to analyze, yay! - Every TLA cryptanalysist ever I'd prefer Tahoe-LAFS
- auntienomen 11y agoHa ha! (Seriously, nice paper.)
- agwa 11y agoThere aren't any new findings here. It's merely a rehash of the Weak DH attack (by the same researchers) that was made public in May of this year: https://weakdh.org/ https://weakdh.org/ Still, it's a good reminder that you should not be using 1024-bit Diffie-Hellman.
- swolchok 11y ago> It's merely a rehash of the Weak DH attack that was made public in May of this year Just to clarify (because I was confused when I read your comment), the weak DH attack was made public by the same people who wrote this post and the academic paper attached to it. It looks like the post and the paper are part of the same "release". Conflict of interest disclaimer: I was a grad student of Professor Halderman's several years ago.
- agwa 11y agoIndeed. I wasn't implying that the blog post authors were copycats. I've updated my comment to hopefully avoid confusion.
- sohkamyung 11y agoTo rehash is to: "To bring forth again in another form without significant alteration". If I'm not mistaken, they gave a presentation in May and have now published a full technical paper. Perhaps rehash is too harsh a word to apply to a paper that contains more details than given in the slides.
- agwa 11y agoThey published a technical report in May that is almost identical to the paper submitted to the conference. No criticism of the authors is intended (to the contrary, their findings are amazing and very important). But readers need to know this isn't a new attack before they go off panicking.
- sohkamyung 11y ago
- ape4 11y agoImportant stuff.
- mrb 11y agoFYI this is not really new news. The authors of that research had already disclosed their findings at https://weakdh.org https://weakdh.org about 5 months ago. Today they simply formally presented their research at ACM CCS.
- 542458 11y agoI wonder what the effort to break a 2048-bit prime would be. I suspect it's heading into "dyson sphere powered ideal computer" territory, but I'd be curious to know what it would actually be.
- tptacek 11y agoThe thing that breaks 2048 bit conventional multiplicative group Diffie Hellman is likely to break conventional multiplicative group Diffie Hellman altogether.
- Locke1689 11y agoAny reason not to just settle on ECDH for new applications?
- tptacek 11y agoIt's Complicated. All else equal, yes, you should use ECDH over a good curve, implemented carefully in a curve library you yourself did not write, which library has been carefully reviewed for flaws. But if you don't have access to that code on every platform you might need to deploy on, it might be better to do DH-2048 than to use crappy curve code. Basically, your best choice right now is Curve25519. If you can't get a trustworthy Curve25519, though, it might be tricky to pick between DH-2048 and {other curve software}.
- MichaelGG 11y agoWhy is there not more hedging of bets by implementing both? That way if one is broken or improperly implemented, there's a bit of safety. Apart from being ugly is there a reason this doesn't work?
- grrowl 11y agoYou're increasing your attack surface area. Do you use both, do you let the server choose, do you let the client choose? What if the client requests the lower-security crypto? What if what the client asked you is different to what you think you were asked from the client (MITM)?
- paulgerhardt 11y agoSee also Martin Hellman's oral history on trap doors: https://conservancy.umn.edu/bitstream/handle/11299/107353/oh375mh.pdf?sequence=1 https://conservancy.umn.edu/bitstream/handle/11299/107353/oh...
- zmanian 11y agoHow much software has been updated to use stronger DH either ECC or 2048 bit prime field? Is there an easy way to check if a VPN provider has updated? The ASICs NSA built for breaking some common 1024 bit fields are probably breaking specific RSA keys now...
- andrewpe 11y agoRun your private key through the second command here: http://etherhack.co.uk/asymmetric/docs/rsa_key_breakdown.html http://etherhack.co.uk/asymmetric/docs/rsa_key_breakdown.htm...
- deleted 11y ago[deleted]
- kevinchen 11y agoCare to clarify why not?
- bvandersloot 11y agoSorry, I thought this was a troll comment to get someone to upload their private key.
- kobayashi 11y agoThat was my first impression to. Why is that impression incorrect?
- Estragon 11y ago"man openssl"
- schoen 11y agoThe "command" is a local command you can run, not a web service to upload keys to. So it's not an attempt to trick people into doing something dangerous (although it might not be a great idea to display private key material on your screen!). But I'm not convinced that this command will answer the question; if you take the TLS analogy, you can have a client certificate with a 4096-bit RSA key but you can then use that to authenticate to a server with a 768-bit DH parameter! So these parameter sizes are independent.
- NN88 11y agoIts...their...job... I wonder what world you all live in in which this is a bad thing. Theres real threats out there and i'd hate to live in a country that lacked the geopolitical leverage to make use of these tools to my nation's interests.
- stonogo 11y agoI'd love to live in an America where they did that instead of their current 'whatever the hell we feel like' policy.
- SeldomSoup 11y ago> I wonder what world you all live in in which this is a bad thing. The world where we all depend on secure communications for autonomy of our own lives?
- dogma1138 11y agoAgain that's not the issue, the NSA's mission is to be capable of breaking crypto that's their job. Having the ability doesn't mean that they need to use it all the time which is what you should be fighting against. As long as the fight is centered around trying to disarm the NSA you'll lose because that's not the right tactic an the US as a nation cannot accept it.
- mirimir 11y agoHow can we know who the NSA works for?
- dogma1138 11y agoIt's the only agency that works directly for the president :)
- mirimir 11y agoFrom what I've read, I gather that they don't always tell the President everything ;) Partly that's just complexity and incoherence. Nobody reporting to the President knows everything. Or even the important stuff. And I gather that the reporting structure is extremely convoluted. Maybe it's all just petty fiefdom bullshit. But those are standard approaches for plausible deniability. And some bits are reportedly unaccountable, walled off through "need to know basis" policy. So how can we know who they work for?
- dogma1138 11y agoBreaking crypto is what the NSA was created to do, playing a cat and mouse game with it means you'll always loose. If the NSA cannot break crypto it's useless, and given 2 outcomes them giving up or them just asking for more money and being more intrusive the latter is much more likely. No one will get their privacy "back" by fighting the NSA through technology, considering their mission, budget and capabilities they'll always win, the only way to pacify the NSA is through legislation that will ensure that they only use their capabilities when it's warranted.
- jMyles 11y agoThis depends on your view of the nature of technology vs. the nature of political institutions. I tend to believe that, with time as the X-axis, that the nature of technology is on a positive curve with regard to liberty while the nature of political institutions is on a negative one.
- bitJericho 11y agoYour beliefs are opposite the reality. Invasion of privacy has never been so high
- BinaryIdiot 11y agoWell that doesn't technically preclude the parent's thought; we could simply be at the beginning of the curve in his / her graph.
- dogma1138 11y agoTechnology can be positive or negative it's all in the application, but that's not the issue. It's not that the NSA is inherently bad or good, as long as it exists it will be able to break crypto because that is it's mission, the US needs that ability for national security but it doesn't mean that the NSA has to apply their capabilities to cast a net on the entire planet. That said it's very unlikely that an organization with virtually unlimited funding, and a recruitment monopoly on the best and the brightest in the field of cryptography and computer security will lose on the technology front. Trying to disarm the NSA is effectively trying to disarm the US that won't fly, the only option is to ensure that they use it only when its explicitly warranted and not as a business as usual tool.
- misiti3780 11y ago"Since weak use of Diffie-Hellman is widespread in standards and implementations, it will be many years before the problems go away, even given existing security recommendations and our new findings. In the meantime, other large governments potentially can implement similar attacks, if they haven’t already. " can someone explain to me why this cant be fixed over night. im no crypto expert, but " If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. " why can't you just switch the large prime number and then continue on sending encrypted data?
- tptacek 11y agoYou can, but there's a cubic fuckload of software deployed using the old parameters, and a whole lot of it doesn't know how to update itself.
- dadrian 11y agoBeyond that, generating prime numbers >= to 2048 bits takes a non-trivial amount of time, sometimes close to a minute. This isn't feasible for servers to do on launch, and might not even be feasible to generate during install---which brings us back to predistributed parameters.
- schoen 11y agoI think "close to a minute" is far too optimistic for the time required :-( -- note that the prime for DH is supposed to be a safe prime. https://en.wikipedia.org/wiki/Safe_prime https://en.wikipedia.org/wiki/Safe_prime You can contrast openssl dhparam -5 2048 which generates 2048-bit Diffie-Hellman parameters, to openssl genrsa 4096 which generates a 4096-bit RSA key (containing two 2048-bit primes) and note that the second is dramatically faster than the first. On-the-fly DH parameter generation is really slow. However, generating 1024-bit parameters is probably fast enough to do on launch or install. Under the authors' estimates this might be fairly safe today because the adversary will have to spend many millions of dollars to attack your individual service (and you could change the parameters once a day or something if you wanted). But I think the authors agreed that large predistributed parameters make a better tradeoff for most cases. There is an RFC about to issue listing such parameters https://datatracker.ietf.org/doc/draft-ietf-tls-negotiated-ff-dhe/ https://datatracker.ietf.org/doc/draft-ietf-tls-negotiated-f... Edit: I possibly shouldn't refer to "the authors" in the third person here, because you are the lead author. Further edit: "Close to a minute" is actually not a bad estimate, but the variance is very high! So it can easily be considerably worse.
- Pyxl101 11y agoSome advice from the authors on how to properly deploy Diffie-Hellman: https://weakdh.org/sysadmin.html https://weakdh.org/sysadmin.html
- nly 11y agoThere's also https://cipherli.st/ https://cipherli.st/ which, imho, is better. What's really awful is the sets are similar yet almost disjoint, only agreeing on 4 cipher combos: DHE-RSA-AES128-GCM-SHA256 DHE-RSA-AES128-SHA ECDHE-RSA-AES128-GCM-SHA256 ECDHE-RSA-AES128-SHA Personally I use the shorter "strong" config off cipherli.st
- Buge 11y agoWhen I checked, I got 16 in common. weakdh.org recommended 43, and cipherlist.st 16. cipherlist.st was a subset of the weakdh.org list.
- dadrian 11y agoOur cipher recommendations on the Weak DH site come directly from Mozilla. See https://wiki.mozilla.org/Security/Server_Side_TLS#Recommended_configurations https://wiki.mozilla.org/Security/Server_Side_TLS#Recommende...
- smegel 11y agoCan someone explain what "breaking a prime" means? What is the output after your year of computation?
- zmanian 11y agoThe output is a giant table of A= g^X mod p where given A you can look up x.
- caf 11y agoThere's more to it than that, though - a table that could let you directly look up the discrete log of an arbitrary A would require on the order of 2^1024 entries (for a 1024 bit group). It's a table specifically of the discrete logs of a large (but tractable) number of small primes. Those discrete logs can be used as the input to a separate stage that can calculate the discrete log of any value in the field.
- qopp 11y agoThe paper mentioned in the article shows how a few complex steps reduces to very large polynomial time, most of which can be precomputed given "45 million computer-years", the rest computed on a per-session basis very quickly.
- r0naa 11y agoSounds like my PMATH assignment for this week :-)
- xnyhps 11y agoAssuming they are using an index-calculus attack, the output is the discrete logarithms of a set of small primes. (But who knows, they may have much better attacks.) This is how that attack works. You generate a set of small primes called the base primes: 2, 3, 5, 7, 11, ... Then you generate powers of p which all factor in only the base primes. This creates a set of linear equations, which can be solved to find the discrete logarithm of all base primes. This was all pre-computation. After this, to find the discrete logarithm of x, you generate powers of x until it factors in the set of base primes. Once that is found, calculating the logarithm is easy. This requires a trade-off: the larger the set of base primes, the longer the first step takes, but the faster the second step is.
- kristopolous 11y agoabout 12 years ago I came up with a pretty clever way to factor numbers that I never pursued the computational complexity of. The basic algorithm is that you take some candidate X (which will be our 2048 bit number here) and classify your question (primality, whether it is the product of 2 primes, etc) --- once you have your question, Q, then you can pick a number Y0 to get X % Y0 = Z0 ... sometimes ~sqrt(X) works well, other times it's the closest prime factorial, etc. now using those results, [Q, Y0, Z0], you can optimally pick Y1 and do the operation again, X % Y1 = Y2 ... Like the Chinese remainder theorem each Z gives you information on the next optimum Y given your question Q ... I called it tunnel factoring and saw some great early results ... but for some reason I haven't ever pursued it
- chadnickbok 11y agoGood engineers ship.
- deleted 11y ago[deleted]
- kristopolous 11y agoDo you actually want the source? It's similar to gnfs, but my implementation of my algorithm seems to be faster in c, under probably gcc 2.95 when compared to a reference gnfs i had found online ... enough times to be significant (but a result of "faster on my computer" doesn't really lead to any kind of "breaking news"). It could just be due to an ineffecient implementation. I'll have to look at some old cvs repos ... Hopefully I can find it. I'll put it on guthub if i can. I worked a good 6 months on it and I understand the gravity of the claim. I have no interest in being bogus or fraudulent.
- sillysaurus3 11y agoHopefully I can find it. I'll put it on guthub if i can. Please do. It sounds very interesting.
- chadnickbok 11y ago
- nosuchthing 11y agoBeing that crypto is 'just math', why would crypto be safe? The only claim that crypto is safe assumes computational power is limited. Is that a safe assumption? Assuming the crypto math is safe, one also has to be certain the entire system which runs the crypto is safe as well. Analysis and attempts to decode the Voynich manuscript lead me to believe mathematical patterns intended to hide information, languages in particular, are not safe in the least.
- ianremsen 11y agoThat assumption is correct, founded deep within the well-tested parts of our current understanding of physics. When the work required to brute-force a cipher in a sane timeframe doesn't exist (or even couldn't fit) within the bounds of the observable universe, (if the crypto works as intended, which, to be fair, is a big if) brute-forcing is safely axed as an avenue of attack. Of course, on these scales, if you really want to, you could connive and threaten your way into having a backdoor installed. Or you could spy on the victim and steal their laptop, with the key decrypted and in memory. Or you could beat the key and password out of them. Brute-forcing shouldn't be the most pressing of anyone's cryptographic worries.
- cordite 11y agoMath works when all of the lemmas are satisfied. In this case, for he sake of efficiency or otherwise, a lot of people made a bad decision and only fulfilled a partial set of the requirements. When software uses a known set of hard coded primes, it is logarithmically simplified in what it takes to defeat it. Maybe there are good primes, bad primes, but to "standardize" a prime is to give an anchor to an adversary.
- crpatino 11y agoIf you have any means of "unlimited computational power", why haven't you already taken over the world through financial speculation. The trade floors are already opening in Asia, I think. You have got 24 hours. Go!!!
- deleted 11y ago[deleted]
- kobayashi 11y agoRegarding VPN usage, is the fix a client-side or a server-side solution?
- Natanael_L 11y agoServer side. They need to change parameters.
- cm2187 11y agoIsn't the bulk of the https traffic using RSA, not Diffie-Hellman?
- justsayinghi 11y agoIIRC asymmetric decryption is time consuming, so it is used as the initial step to send/receive the symetric DH key. All additional encryption/decryption is symetric.
- cm2187 11y agoBut I thought DH was an alternative to RSA, not a symetric encryption algorithm.
- schoen 11y agoYes, and in fact it's slower than RSA key exchange for the server! The big benefit is forward secrecy because the server no longer has the ability to recover the keys for old sessions (which it could with RSA key exchange).
- Natanael_L 11y agoHere's some of the options: Client generates a key, encrypts with server's RSA key, sends it to the server, and the session starts. This lacks PFS. Client and server participates in DH key exchange, the server signs their DH parameters using the RSA key so that the client knows that he's talking to the right person. They now start the session using that DH generated key. This has PFS. And there's same as the above but with DH replaced with elliptic curve DH (different way of achieving the same thing), and RSA replaced with ECDSA, and a few other options.
- z3t4 11y agoCheck your root certificates. If any of those has capabilities of "Man in the middle", they can see your SSL traffic. That's probably how they do it.
- caf 11y agoIt's not that simple. A CA can intercept your SSL traffic, but to do so it has to create a fradulent certificate for the end site and proxy your traffic to the site, presenting the fradulent certificate to you. This means it can't be done without risking that you might notice it. And it can't be done just by passively hoovering up all the traffic and then retrospectively going back and decrypting it.
- schoen 11y agoAnd nowadays "you might notice" in an automated way because of HPKP!
- ck2 11y agoThis is an arms race and it doesn't address the underlying cause. The government of the people should not be spending $10B a year to monitor and track all of its people just to warehouse the data. That is quite literally Stasi. Not vaguely like, exactly like.
- johncolanduoni 11y ago> That is quite literally Stasi. Not vaguely like, exactly like. Come on. I agree this is ridiculous and unacceptable, but this kind of hyperbole only serves to make people discount the sentiment. The NSA has not tried to use this to suppress political dissidence. The Stasi themselves called the way they manipulated prisoners "decomposition", and all evidence suggests it deserved the name. It makes the CIA torture look like juvenile detention. Is that a possible dark future if this goes unchecked? For sure. But I think one of the main reasons serious anti-NSA sentiment and action has had trouble making it to the mainstream is that people say things like this that make most people write the movement off as a bunch of crackpot conspiracy theorists. I don't think you are one, so please don't talk like one.
- ck2 11y agoI mean the data warehousing part of the stasi. Didn't mean to imply the entire government is 100% stasi, I mean their data warehousing obsession about their own citizens is exactly stasi-like.
- laotzu 11y ago>The NSA has not tried to use this to suppress political dissidence. False. They did with Martin Luther King Jr. To quote the Senator Church of the Church Committee which investigated this: >In the need to develop a capacity to know what potential enemies are doing, the United States government has perfected a technological capability that enables us to monitor the messages that go through the air. Now, that is necessary and important to the United States as we look abroad at enemies or potential enemies. We must know, at the same time, that capability at any time could be turned around on the American people, and no American would have any privacy left such is the capability to monitor everything—telephone conversations, telegrams, it doesn't matter. There would be no place to hide. >If this government ever became a tyrant, if a dictator ever took charge in this country, the technological capacity that the intelligence community has given the government could enable it to impose total tyranny, and there would be no way to fight back because the most careful effort to combine together in resistance to the government, no matter how privately it was done, is within the reach of the government to know. Such is the capability of this technology. >I don't want to see this country ever go across the bridge. I know the capacity that is there to make tyranny total in America, and we must see to it that this agency and all agencies that possess this technology operate within the law and under proper supervision so that we never cross over that abyss. That is the abyss from which there is no return.
- chinathrow 11y agoImagine the money spent on both a) measures and b) countermeasures related to the ongoing spying by the intelligence apparatus around the world. Imagine the money not spent on more pressing issues we face these days: health problems, poverty and the destruction of nature earth, just to name a few. Why do we, as a society, tolerate this?
- JabavuAdams 11y agoBecause we think we can have it all, and we may just be right. * for some ambitious but obviously not literal definition of "all".
- pbhjpbhj 11y ago>Why do we, as a society, tolerate this? // In Western democracies [I really want to put quotes around both those words] do we have a choice? In the UK we get to vote but it's for one of 2 or 3 sets of policies for the next 5 years, at no point do I recall any main party saying they were going to do something about NSA/GCHQ incursions in to UK life; I imagine USA have us over a barrel even if there were political will amongst the elite to change the spying on ordinary subjects [of the Crown].
- arethuza 11y agoYou can read Chris Mullin's excellent A Very British Coup for what would happen if someone got into power that actually threatened that part of the establishment. Of course that would never happen as nobody who actually had any intention to do such a thing would ever get elected as PM - look at the complete lambasting that Jeremy Corbyn has been getting, including murmurings that the Army would mutiny if he got into power. [NB I am not a Labour supporter and wouldn't vote for Corbyn but I do think that the way he has been treated recently is pretty appalling.]
- J_Darnley 11y agoBecause the establishment has successfully made everyone so terrified of terrorism that they (the people) are willing to throw trillions of dollars at a tiny problem.
- deleted 11y ago[deleted]
- andyjohnson0 11y ago"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. [...] an adversary can perform a single enormous computation to “crack” a particular prime [...]" Can someone explain to me what the authors mean by "cracking" a prime? Is the difficulty of this related to the difficulty factoring a composite number? The language used is annoyingly imprecise. Edit: Question was already asked by smegel, and has some useful answers.
- johncolanduoni 11y agoIt's called index calculus[1]. Basically, it allows you to do a (huge) amount of work that can be factored out from breaking specific DH exchanges, as long as the same prime is used. Since finding good DH primes is far more expensive than coming up with good primes for RSA, these primes tend to be reused on a massive scale. [1]: https://en.wikipedia.org/wiki/Index_calculus_algorithm https://en.wikipedia.org/wiki/Index_calculus_algorithm
- bvandersloot 11y agoTraditionally, index calculus attempts for record discrete log calculations attempt to balance the "precomputation" step and the individual log calculation much more closely than in this work. This is more efficient if you only intend to perform one discrete log. One of the contributions here is that because of the massive reuse of primes, it would be more useful in a practical attack to shift much of the work into the steps solely dependent on the primes.
- dheera 11y agoThis system sounds incredibly insecure to me. What are the benefits of this over just plain old RSA with everyone using their own keys?
- minitech 11y agoForward secrecy in the event of a compromised key.
- mkagenius 11y agoDevil is in the details, I would take this with a grain of salt before I read the paper. What if few hundred millions is 10x less than actual amount. What if it takes 10 years instead of 1.
- onderkalaci 11y agoThere 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. Then, if the prime number is standardized or hard-coded, why they just not use it? Why we need to break it?
- macns 11y agoIt shouldn't be nor standardized nor hard-coded because someone with the funds (e.g. NSA) would need to break the encryption using this 'standardized' number only once. If everyone used a random very large prime (spec suggests so) then NSA would have to break with every prime number possible which currently is not possible
- acd 11y agoYou can check for web sites common Diffehellman primes on ssllabs.com Check section Protocol details "Uses common DH primes" Also the latest openssh package warns against Diffie hellman ssh keys now we know why they warn us.
- vbezhenar 11y agoWhen I setup TLS for web or smtp, there's an option to generate custom dh params. So basically one must generate new dh params for every installation to be safe against attack presented in the article, is it correct?
- schoen 11y agoThat would work, but there's still a problem when the client can't verify that the parameters are safe, at least when using client certificates. See the references in section 9.7 of https://datatracker.ietf.org/doc/draft-ietf-tls-negotiated-ff-dhe/ https://datatracker.ietf.org/doc/draft-ietf-tls-negotiated-f... As a result, that draft proposes using specific much larger parameters, on the basis of scaling considerations for the attacker. I think the authors of this paper endorse this solution. (It's OK in general if you share parameters with someone else, it just means that an attacker who can do this precomputation for those parameters gets to attack both of your DH sessions as a result.)
- Natanael_L 11y agoOnly if the parameters are too small (1024 bits and close), and if the source of the parameters aren't necessarily trustworthy (maybe because of lack of verification). 2048 bit parameters should be good enough.
- deleted 11y ago[deleted]
- petra 11y agoSince we don't exactly know what other ways to break crypto are there - why aren't we focusing on concatenated encryption(at least for critical apps) - while working hard to ensure no crypto vulnerable to malware type attacks, especially considering that malware isn't a good way for web scale surveillance ?
- Natanael_L 11y agoIt is more commonly called cascade encryption. The problem is that in many cases you can't afford to sacrifice enough performance for it. Also, malware and crypto doesn't "play in the same field". Malware is solved by secure programming, access controls and users that are educated to not fall for trojans. Encryption handles communication and storage, and only to a small degree data processing.
- sfilipov 11y agoTo support your point, virtually all crypto vulnerabilities we know of for sure are a result of bugs in implementations rather than problems with the underlying algorithms. On the other hand there are algorithms which are believed to be backdoored by the NSA (some elliptic curves). These algorithms can be avoided. In the end, cascading encryption has very limited benefits because the weakest point of a security application is almost never the algorithm used.
- ibmthrowaway271 11y agoIs there a tool to output the DH params being used when attempting a TLS connection (not dumping them from a packet capture)? I know I can, but I'm hoping for something simpler than having to parse the TLS messages from:- openssl s_client -connect host:port -msg to work it out.
- thiagoharry 11y agoAccording with the estimated cost given to that machine (few hundred million dollars) and the problem's nature, what they propose is very similar to TWIRL, an hypothetical machine that could factor 1024-bits integer to break RSA. That was the reason that made a lot of people consider 1024-bit RSA not secure anymore and change their keys to 2048 bits. The same should happen with DH now.
- puppetmaster3 11y agoHello. I'm L.E. Give me your keys. Thank you for your cooperation, you can see your kids now.
- too_late 11y agoWouldn't this be easy to subvert, though? I mean, say we put through a few patches and started generating primes more often. Then there big-ass special purpose prime machine becomes an order of magnitude less-effective, right? I think the best way to defend against these one-to-many attacks is to spread out the cost of decrypting large quantities of data. If we all had our own keys, even if they weren't as strong as one single key that everyone used, that much more work has to be done to decrypt data for a group of users. I know nothing about crypto, but a layman can hear about these implementation architectures and immediately realize what's wrong with it all.
- JacobEdelman 11y agoThe problem is that there needs to be an agreed upon key that each of the parties knows before-hand. But yes, there are definitely viable ways to generate new ones or implement new, safer, standards. Alternatively, a much larger prime can be used. Also, the Diffie-Hellman protocol is a well known one that many many security researchers, programmers, and students have looked at. The flaws are not obvious, as it's initially unclear how "cracking" a large prime would work.
- too_late 11y agoIf they have special-purpose hardware specially designed for cracking primes, maybe bigger isn't better, right? What can end-users be doing about this?
- crozewski 11y agoCan we use distributed computing to crowdsource the computation of more/better primes? Can OpenSSL look to this pool for its primes?
- JacobEdelman 11y agoWe wouldn't need to do this. One computer would suffice to generate primes at a pace making cracking computation infeasible. Though, even if we switch primes every few seconds, if somebody wanted to put a few hundred million dollars into cracking a few seconds of messages, they could do it.
- devit 11y agoApparently some Cisco products might even be using 768-bit DH as default for IPsec! From http://www.cisco.com/en/US/docs/ios-xml/ios/sec_conn_ikevpn/configuration/15-2mt/sec-key-exch-ipsec.html http://www.cisco.com/en/US/docs/ios-xml/ios/sec_conn_ikevpn/...: << Diffie-Hellman--A public-key cryptography protocol that allows two parties to establish a shared secret over an unsecure communications channel. Diffie-Hellman is used within IKE to establish session keys. It supports ==> 768-bit (the default) <==, 1024-bit, 1536-bit, 2048-bit, 3072-bit, and 4096-bit DH groups. It also supports a 2048-bit DH group with a 256-bit subgroup, and 256-bit and 384-bit elliptic curve DH (ECDH). Cisco recommends using 2048-bit or larger DH key exchange, or ECDH key exchange. >> Malice or incompetence? (or crappy hardware that needs help to not be slow?) The recommendation is correct so...
- seanwilson 11y agoIsn't the much simpler explanation that, for particular servers, they either have permission (e.g. companies have agreed to hand over the encryption keys or allow monitoring of the data after it is unencrypted on arrival) or some other means (man-in-the-middle attacks, server backdoors, hacking vulnerable software) to bypass the encryption entirely without you knowing? For instance, I find the idea that they would direct huge amounts of computing power to crack individual keys implausible given the previous example methods are so much easier.
- redblacktree 11y agoI agree. The NSA is probably mostly investing in the five-dollar wrench. https://xkcd.com/538/ https://xkcd.com/538/
- sarciszewski 11y agoWhy spend $5 on a wrench when you can make a phone call to the FBI and compromise any server on US soil? These cryptanalytic capabilities are mostly relevant for servers hosted outside the US, I'd wager.
- acqq 11y agoFor the servers outside, the case that happened in Greece after the Olympic games as an example of something much, much bigger but conceptually still more an immense "wrench" than a "cryptanalytic" approach: https://theintercept.com/2015/09/28/death-athens-rogue-nsa-operation/ https://theintercept.com/2015/09/28/death-athens-rogue-nsa-o...
- kllrnohj 11y agoThe five-dollar wrench doesn't allow for passive collection. You kinda know when you get hit with a wrench.
- redblacktree 11y agoI was thinking more about NSLs and threats to companies to force them to hand over their encryption keys.
- qakmail 11y agoJust to clarify (because I was confused when I read your comment), the weak DH attack was made public by the same people who wrote this post and the academic paper attached to it. It looks like the post and the paper are part of the same "release". Conflict of interest disclaimer: I was a grad student of Professor Halderman's several years ago.
- late2part 11y agoI wonder if that estimated cost is the COGS or the R&D? If it's the R&D, what is the cost of the second machine?
- sarciszewski 11y agoThis might not contribute much to the discussion, but I just want to add: I for one welcome the coming arrival of ECDH over curve25519 in TLS everywhere. (And I really hope that comes to pass.)
- api 11y agoQuestion I don't know the answer to: Is there any chance that ECC is vulnerable to similar issues with static universally agreed upon constants. In ECC these are curves, and is it feasible to "pre-crack" a curve? Or is the space so huge in this case that it would take millions of years of compute time to do so? Someone who knows ECC math better than I do would have to answer this one.
- tptacek 11y agoA big part of the whole point of ECC is that it resists index calculus. Also, remember: this isn't a fatal flaw in all of Diffie Hellman. It's a variant of a well-known attack that makes it economical to attack 1024 bit DH, not merely plausible. So far as anyone knows, it does nothing to help attack 2048 bit DH.
- sarciszewski 11y agoRight. 2048-bit RSA/DH is fine, but EdDSA/ECDH is looking more attractive every day (so long as Bernstein or Langley provided the implementation).
- api 11y agoSo Curve25519 is pretty much rock solid unless (a) someone discovers genuinely new math or (b) we get a practical quantum computer with enough coherent qubits to actually run the ECC variant of Shor's algorithm. Note the qualifications around (b). Just any QC would not do... it would have to (as far as I know) have a rather "wide" coherent qubit capacity among other characteristics. So what... Curve25519 until 2050? 2100? Hard to say and new math is always a total wildcard, but it seems damn secure. ... and as you say DH and RSA are also great with >2048 bits. 4096 bits is what I typically use.
- astazangasta 11y agoIf one is not enough, why not just have a million standard keys to choose from? This makes the problem space prohibitively large, but this many keys could be passed around in a standard distribution easily enough.
- kordless 11y ago> For the most common strength of Diffie-Hellman (1024 bits), it would cost a few hundred million dollars to build a machine, based on special purpose hardware, that would be able to crack one Diffie-Hellman prime every year. I'll just leave this here: http://fortune.com/2015/06/29/intelligence-community-loves-its-new-amazon-cloud/ http://fortune.com/2015/06/29/intelligence-community-loves-i...
- nickpsecurity 11y agoIrrelevant: such a cloud would be useless for this application. NSA more likely will use a massively-parallel cluster with FPGA's. Potentially ASIC's if the numbers added up.
- kordless 11y ago> such a cloud would be useless for this application Either you don't know what is in that DC, or you do. If you don't know what's in the DC, you can't say one way or the other about what it can and can't do. If you do know what's in the DC, then you'd likely be prevented from saying what it's capabilities were or would deny those capabilities publicly if it did possess them. This is why people make tinfoil hats; because they reach cognitive dissonance quickly with logic built around untrusted data. Because I can't implicitly trust you, or Amazon, or the intelligence agencies, I'm left with the reasoning capabilities I have and trust. Floundering in cognitive dissonance isn't going to get me anywhere in that regard. I'm left with what I know, which is that US agencies pay Amazon a staggering amount of money to run a datacenter for them. I know that AWS itself runs servers with special purpose hardware in them, such as GPUs, and that most of the value in AWS comes from federating systems and providing fault tolerance and easy programmatic access to provisioning. What sits behind all those features is anyone's guess. Amazon does not publicly discuss their relationship with the government, so that's zero help here. If Amazon wanted to own the world's public cloud AND remain trusted, they should have thought twice about doing a deal with the government. In Germany, this shit wouldn't fly. Companies who provide services to the government there sign special agreements to ensure what services they provide to the government aren't colluded with the services they provide to individuals. It's beyond dumb that we allow this in the US and that the largest cloud provider here is mute in that regard.
- metachris 11y agoInteresting paper (https://weakdh.org/imperfect-forward-secrecy.pdf https://weakdh.org/imperfect-forward-secrecy.pdf) and lots of good references! Inspired me to write a little tool to download all referenced pdfs from any given pdf: https://github.com/metachris/pdf-link-extractor https://github.com/metachris/pdf-link-extractor
- mediocrejoker 11y agoIf the NSA wasn't doing this, you can bet they will be soon.
- jgalt212 11y agoHow do these findings affect the usage of Tor and Tails?