Daemonic Dispatches

The Factoring Cryptopocalypse

The key detail to understand about the work in the Joux papers is that it is limited to solving discrete logarithm problems over fields of small characteristic. As interesting as the work is, mathematically, it should not be a great surprise to cryptographers: We've known for over a decade that small-characteristic fields are "scary", and in 2005 when the NSA announced their "Suite B" cryptography using Elliptic curves, nobody was surprised to see that they selected ECC over prime fields instead. In that sense, this work is akin to seeing a buffer overflow discovered in Sendmail in 2003: Interesting to the research community, but not really a great surprise to anyone who has been paying attention.

When should we worry? If there's any hint of this work being extended to apply to prime fields. The discrete logarithm problem over prime fields is very closely related to the problem of integer factorization — there's a long history of improvements in one translating directly to improvements in the other. (In fact, I'd say DLP over prime fields is more closely related to factoring than it is to DLP over small-characteristic fields.) In the mean time, I see no reason to panic. If you want to switch over to using Elliptic curves, go ahead; but my earlier remarks still apply there: Because ECC is more complex than RSA, it's easier to make implementation errors and/or introduce side channels. I would add one extra caveat however: If you do decide to use ECC, do it over a prime field. While I've never been fond of ECC over small-characterstic (aka. binary) fields, this latest attack provides all the more reason to be cautious about them: It's the inherent "structure" which makes them scary, and the work of Joux et al. just reinforces that such structure can be exploited.

For my own purposes, I'm going to keep on using 2048-bit RSA.