If you don't know what SNFS is, the headline is a little misleading. It hasn't gotten easier to solve 1024 bit discrete logs (ie: to break 1024 bit FFDH) --- though it's already presumed feasible to do so given state-level resources.
Instead, the authors have extended a proposed backdoor attack from the 1990s to 1024 bit parameters. Specifically, they show that it is now practical to generate a set of SNFS parameters that will produce a random-looking prime with L=1024 N=160 (ie, a plausible DSA parameter). Since the prime is generated to conform to SNFS, it's much easier to solve discrete logs in than a general prime; the difficulty of attacking systems built on it is reduced from state-level to university-level.
It was possible in the '90s to generate these weakened parameters, but not to hide them effectively --- making them useless as NOBUS parameters. Two things appear to have made this tricky: first, the primes in common use at the time were 512/160, and the smaller gap between L/p and N/q gave less flexibility to backdoor designers; secondly, we have much better compute available today. Also, we (meaning them, not me) understand NFS a lot better than we used to.
This paper is interesting from a scientific standpoint and from the standpoint of Kremlinology ("could NSA have done this to earlier systems? was this ever in their repertoire?"). It's not as interesting from a practical perspective today, because:
* 1024 bit FFDH is already presumed broken, and while the compute resources needed to attack SNFS-weakened 1024 bit FFDH might not be state-level, the logistical resources needed to get an SNFS-weakened 1024 bit prime deployed probably still are.
* The most common 1024 bit FFDH parameters we use are if not entirely verifiable than at least significantly more constrained than the parameters this paper generates (for instance, if not derived from the bits of pi, as some are, than at least sequential series of primes).
Most importantly: we've moved away as a field not only from FFDH itself, but also from asymmetric systems with opaque parameters. The Curve25519 parameters, for instance, have clear, easily understood performance and security rationales.
The more important point to take away from this paper is not that 1024-bit is already considered broken, so this doesn't matter. It's that the cost of 2048-bit DH---which is used and recommended today, and will stick around forever---has roughly the cost of 1024-bit DH when coupled with a special polynomial.
I guess another thing to take away from this is that the logistics of actually deploying a SIGINT infrastructure based on breaking 1024-bit DH needs to take into account that a university can break a single dlog in 80 minutes (and so the NSA's hypothetical Utah data center can probably do it in under a minute) if you can get SNFS-weakened parameters deployed.
That takes attacks against 1024 bit DH from a "special order, only for high value target" sort of thing to a "file a ticket and wait a few minutes" kind of thing.
According to the Logjam paper, the 1024-bit individual logarithm would cost around 30 (parallelizable) core-days once the group precomputation is over with. Unless they're being exceedingly stingy with their hardware, 30 core-days (less than a day in a single powerful workstation) would already be 'file a ticket' levels of easy.
(Note that the time reported in this newer paper is calendar time---it's still 10 core-days, so quite comparable to the non-special variant.)
> Most importantly: we've moved away as a field not only from FFDH itself, but also from asymmetric systems with opaque parameters.
For another example of asymmetric systems with opaque parameters: The BADA55 paper [1] and the related slides [2] shine a light on the parameters of elliptic curves.
There's an academic rivalry between Bernstein and the team behind the Brainpool curves.
Both teams reject fully opaque parameters, for the same reason the authors of this SNFS paper do. But they use different approaches to mitigate the risk.
The Brainpool approach is to start parameter generation from mathematical constants. We assume that the ultimate creator of the universe didn't embed an NSA backdoor in the digits of pi, for instance, so basing a parameter on some permutation of pi is unlikely to result in compromise.
Bernstein's approach is to optimize parameters for size, performance, and security, and to provide a detailed systems rationale for those parameters. The Curve25519 paper is a good example of what that approach looks like.
Bernstein's argument in BADA55 is that the Brainpool approach has a weakness, which is that there are so many different mathematical constants to work from and so many different permutations of them that a backdoor designer still has enough flexibility to find a weakened parameter.
Bernstein's argument is also interesting scientifically. But unlike the SNFS paper, it's not so interesting from a Kremlinology standpoint: it is, let's face it, really unlike that there's a backdoor expressed in the permutation of universal mathematical constants used in any cryptographic standard.
(I'm doing this from memory and may be missing an aspect of that paper).
> it is, let's face it, really unlike that there's a backdoor expressed in the permutation of universal mathematical constants used in any cryptographic standard.
Why? I mean, there's plenty of reasons to be skeptical of backdoors in standards in the first place, but why do you consider it especially unlikely for any hypothetical backdoor to hide in the details of "nothing up my sleeve" numbers?
Not a mathematician but have a background in engineering. Some damn constants are everywhere and have too many useful properties. Take "e" for instance. I'll be damned if that isn't a terribly versatile number.
If I understand it correctly, it means that keys derived from such a prime number (such as via DH Key Exchange) can be factored and messages decrypted in a reasonable amount of time, where reasonable is less than a day.
I welcome correction.
EDIT: Time squeezed per tptacek, computation space reference removed per schoen.
Also not "factored", but rather a discrete logarithm can be taken.
The apparent difficulty of factorization underlies some public-key systems (like RSA), while the apparent difficulty of extracting discrete logarithms underlies others (like Diffie-Hellman key exchange and DSA). This research is about the second problem.
>in a reasonable amount of time and space, where reasonable is less than a year, and 1kb.
I think kilobit refers to the prime field of 1024 bit.
If you look at last page of the paper there is a table with the details of the cluster they used. Roughly 28 nodes with 512 GiB, 48 nodes with 64 GiB and a few bits and pieces.
For instance, Private Internet Access recommended using 1024-bit certificates to linux users for a long time. This meant that the NSA probably had the resources to MITM your proxy through them.
Instead, the authors have extended a proposed backdoor attack from the 1990s to 1024 bit parameters. Specifically, they show that it is now practical to generate a set of SNFS parameters that will produce a random-looking prime with L=1024 N=160 (ie, a plausible DSA parameter). Since the prime is generated to conform to SNFS, it's much easier to solve discrete logs in than a general prime; the difficulty of attacking systems built on it is reduced from state-level to university-level.
It was possible in the '90s to generate these weakened parameters, but not to hide them effectively --- making them useless as NOBUS parameters. Two things appear to have made this tricky: first, the primes in common use at the time were 512/160, and the smaller gap between L/p and N/q gave less flexibility to backdoor designers; secondly, we have much better compute available today. Also, we (meaning them, not me) understand NFS a lot better than we used to.
This paper is interesting from a scientific standpoint and from the standpoint of Kremlinology ("could NSA have done this to earlier systems? was this ever in their repertoire?"). It's not as interesting from a practical perspective today, because:
* 1024 bit FFDH is already presumed broken, and while the compute resources needed to attack SNFS-weakened 1024 bit FFDH might not be state-level, the logistical resources needed to get an SNFS-weakened 1024 bit prime deployed probably still are.
* The most common 1024 bit FFDH parameters we use are if not entirely verifiable than at least significantly more constrained than the parameters this paper generates (for instance, if not derived from the bits of pi, as some are, than at least sequential series of primes).
Most importantly: we've moved away as a field not only from FFDH itself, but also from asymmetric systems with opaque parameters. The Curve25519 parameters, for instance, have clear, easily understood performance and security rationales.