6 ms·

Special number field sieve discrete log computation in a 1024-bit prime field

46 points by nanis 9y ago

Cynddl 9y ago
> Our computations show that trapdoored primes are entirely feasible with current computing technology. Can anyone explain to me what is the risk with such trapdoored primes? Thanks!
- falcolas 9y ago
  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.
  - weinzierl 9y ago
    >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.
  - tptacek 9y ago
    See page 13. Given an SNFS-weakened 1024 bit prime, a single discrete log (ie, a break of a single handshake or signature) cost 80 minutes.
  - schoen 9y ago
    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.
    - tptacek 9y ago
      The problems are closely related, and, in fact, the NFS algorithms are really IFP algorithms.
- AlexCoventry 9y ago
  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.
  - tptacek 9y ago
    No, that's not what this paper says.
    - AlexCoventry 9y ago
      You're right. Thanks for the correction.
tptacek 9y ago
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.
- weinzierl 9y ago
  > 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. [1] https://bada55.cr.yp.to/bada55-20150927.pdf https://bada55.cr.yp.to/bada55-20150927.pdf [2] https://cr.yp.to/talks/2014.10.08/slides-djb-20141008-4x3.pdf https://cr.yp.to/talks/2014.10.08/slides-djb-20141008-4x3.pd...

46 points by nanis 9y ago

> Our computations show that trapdoored primes are entirely feasible with current computing technology. Can anyone explain to me what is the risk with such trapdoored primes? Thanks!

falcolas 9y ago
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.
- weinzierl 9y ago
  >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.
- tptacek 9y ago
  See page 13. Given an SNFS-weakened 1024 bit prime, a single discrete log (ie, a break of a single handshake or signature) cost 80 minutes.
- schoen 9y ago
  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.
  - tptacek 9y ago
    The problems are closely related, and, in fact, the NFS algorithms are really IFP algorithms.
AlexCoventry 9y ago
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.
- tptacek 9y ago
  No, that's not what this paper says.
  - AlexCoventry 9y ago
    You're right. Thanks for the correction.

tptacek 9y ago

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.

weinzierl 9y ago
> 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. [1] https://bada55.cr.yp.to/bada55-20150927.pdf https://bada55.cr.yp.to/bada55-20150927.pdf [2] https://cr.yp.to/talks/2014.10.08/slides-djb-20141008-4x3.pdf https://cr.yp.to/talks/2014.10.08/slides-djb-20141008-4x3.pd...