Special number field sieve discrete log computation in a 1024-bit prime field
eprint.iacr.org
eprint.iacr.org
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.
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.
(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.)
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.
[1] https://bada55.cr.yp.to/bada55-20150927.pdf
[2] https://cr.yp.to/talks/2014.10.08/slides-djb-20141008-4x3.pd...
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).
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?
Can anyone explain to me what is the risk with such trapdoored primes? Thanks!
I welcome correction.
EDIT: Time squeezed per tptacek, computation space reference removed per schoen.
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.
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.