I’m definitely not qualified to comment on the feasibility of attacking these known primes on x86/GPU compute vs. ASICs; but as I remember the private sector(starting with the relatively spendy enterprise guys, and moving down pretty quickly with RAM prices) loved 64 bit address spaces. PAE was always an awful hack, and 4GB just isn’t a terribly large address space for a lot of problems. Once AMD64 hit the scene, there was practically dancing in the streets from the people who could now move away from hugely expensive big-iron UNIXes and run cheapo x86 gear instead.
Plus, many, though not all, flavors of brute forcing are amenable to parallelization; and the individual parallel tasks fit in relatively tiny amounts of memory, potentially even into oddballs like the Cell SPEs. Unless your brute-force problem parallelizes quite badly, a big PAE system or a lot of networked 32 bit systems should be fine. 64 bit is nicer than PAE for running lots of small tasks in a single memory space, not as hacky; but it only really comes into its own when per-process memory limits go from being ‘inelegant’ to being ‘a deal killer’.
I wouldn’t be at all surprised if the answer to their problem ended up being COTS hardware; but I’d be more skeptical about 64 bit gear being a primarily-military thing.
Of the crypto in use worldwide, what portion is DFDPDQ DH, what is elliptical and what is something else? How BIG of a problem is cracking DFDPDQ DH? Big, big problem, or minor problem?
Cut the wire, all you have to do is replace the wire. Smash the lenses, you’ve got a much more difficult/expensive repair. Of course, it depends on what your end goal is - if it’s just a quick disabling, sure, just cut the wires.
Breaking the single, most common 1024-bit prime used by web servers would allow passive eavesdropping on connections to 18% of the Top 1 Million HTTPS domains. A second prime would allow passive decryption of connections to 66% of VPN servers and 26% of SSH servers.
PFS based on elliptic curves uses DH for the key exchange but is not affected, as the underlaying problem is caused by widely used primes - a hard to solve but attractive target for resource-rich adversaries.
I doubt there would ever be a way of determining this with any certainty. Though, from a little bit of research, DF is more prevalent, which is about the highest level of certainty I can find.
BIG. As the article states, DF is baked into a lot of things, and switching is hard or impossible in my existing applications. Cracking DF takes unauthorized access to encrypted information from “the lifetime of the universe” to merely “difficult (but maybe not if you have a billion dollars, and a couple tons of silicon)”. If the NSA is at this later point, it is even scarier (if that is possible) because in a couple years this will be “hard (but not if you have a million dollars and a smallish rack of silicon)”.
I’m not a security expert, so take this with a decent sized grain of salt.
DF as in disk free the Unix command. YES, of course I meant Diffie Hillman but there are so many friggin f’s that it’s hard to skip over them to get to the H. LOL
Or better yet make two cuts and take the piece away so it can’t be easily spliced. Or pour something flammable or acidic down the conduit and burn the wires.
This doesn’t surprise me. Back in the 1970s, when the RSA paper and a number of others came out, I was talking with some friends about the wonders of the new age of cryptography before us. Anyone, we were sure, could keep anything secret if they had a supply of long prime numbers. But Paul Karger who was working on the Multics project at the time replied, “Yes, but where are you getting your primes.”
I did read the article, but I still need more context. 18% of the top 1 mil HTTPS domains using a 1024 bit prime does nothing for me. I need to know: WHY? Aren’t those HTTPS domains using old, low-bit encryption (1024)? Can’t they just upgrade?
Are the VPN’s and SSH servers using old style keys? Couldn’t they just re-run their keygen to make them all rsa 4096?
It seems a bit like the argument is, “We decrypted the control units on 1996 Hondas.” 18% of all pre-2000 Hondas are now are risk. But how big of a real problem is that? If you are driving a pre-2000 Honda, uhhh, …expect a problem. If you are running IIS 5.0, you basically deserve to have all your traffic intercepted.
DH params with a length of 1024 bit are fine for the moment.
The real problem is that until a few months no one thought about creating new parameters with different prime numbers used for exchanging encryption keys.
So currently we’re in the situation that many web servers* use the same param set - a computationally intensive problem, but very very sexy for attackers: Solve it once, use it for multiple targets.
No one knows if the NSA (and other interested party with the resources of a nation state) solved this for the handful of widely used primes, but they have a big incentive to throw money at the issue.
*) as an example, also true for IPSec VPN gateways and umpteen other methods using this method for KEX
Well, let’s just compute some new bigger primes then. Primes to thousands of digits have been a mathematical hobby for many decades. I remember when “the largest prime known” was printed in the newspaper in a block of about 1000 characters. All I did was check if it ended in an odd digit and no 5’s. We could calculate primes out to millions of digits if we wanted and then prime-of-primes randomly select them. Largest known prime is currently over 17 million digits. It’s a Mersenne, but so what. We could find others because there’s an infinite amount.
All I am saying is that yes, there is a boohoo factor. But there is also a “dumbass” factor in that we can’t just sit around and complain that the NSA has cracked our everyday encryption. If we value our privacy, then we need to outrun them. Which we can, because, you know, math & stuff.
Too loud, everybody in a ten-block radius will call the cops. Plus if you get caught it’s much heavier charges than “malicious mischief” or “destruction of property” or whatever they call it these days.
We could calculate primes out to millions of digits if we wanted and then prime-of-primes randomly select them. Largest known prime is currently over 17 million digits. It’s a Mersenne, but so what. We could find others because there’s an infinite amount.
