A team of French mathematicians and computer scientists has made an important advancement in the field of algorithms for breaking cryptographic codes. In a certain class of problem, the new algorithm is able to efficiently solve the discrete logarithm problem that underlies several important types of modern cryptosystems.
“Problem sizes, which did not seem even remotely accessible before, are now computable with reasonable resources,” says Emmanuel Thomé, a researcher at the French Institute for Research in Computer Science and Control (INRIA) and one of four researchers reporting the advance. However, he notes, the new algorithm poses no immediate threat to most existing cryptosystems, including the RSA-based cryptography used in credit cards and much of e-commerce.
Virtually all the major types of cryptography in use today rely on the use of one-way functions, mathematical functions that are easy to compute but impractical to invert, or reverse. For example, it is easy to multiply together two large prime numbers, but it is computationally impractical to reverse that by factoring the resulting product. That is the basis of RSA cryptography. Similarly, it is easy to compute a = xn given x and n, but hard to compute the discrete logarithm n given a and x. The “discrete logarithm problem” is the basis for a number of cryptosystems, such as the Diffie-Hellman protocol and elliptic curve cryptography.
The “time complexity” of an algorithm is a measure of how execution time varies with input size, n. Those that work in “polynomial” time tend to be computationally feasible for large n, with execution time increasing in proportion to some polynomial with constant exponents, such as 5n3 + 3n. However, for algorithms of an “exponential” complexity, execution time varies with the nth power, so that for a sufficiently large n, the algorithm becomes computationally intractable. Computer scientists and mathematicians use a notation that varies from L(1), exponential, to L(0), polynomial. The advancement recently announced in essence moves the discrete logarithm problem from complexity L(1/3), sometimes called “sub-exponential,” to a complexity close to L(0), or “quasi-polynomial.”
What that means in practical terms depends on the exact nature of the problem and the input size, but in one example analyzed by the researchers, the new algorithm improves execution time from 280 to 270 operations, or about a factor of 1,000 faster. For that problem example, a computer configuration that would have taken three years to decipher a message before could now do it in a little more than a day, a feasible job for a sophisticated adversary. Also, the researchers point out, the algorithms in question exhibit asymptotic computational complexity, and the advantage of the new algorithm grows as the problem size increases.
“The computations that we have done recently would have been completely infeasible without this algorithm,” says Antoine Joux, co-developer of the algorithm and a professor at the University of Versailles-Saint-Quentin-en-Yvelines. The latest algorithm is built on work by Joux in 2012, which moved the complexity down to L(1/4).
Yet as Joux points out, the new algorithm is not efficient against all discrete logarithms. The algorithm is intended for use on finite fields of small characteristic. The elements of a finite field can be expressed as polynomials, and for small characteristic finite fields, the coefficients of the polynomials are small integers. In a “binary finite field,” for example, the coefficients are 0 and 1, and the characteristic is 2. However, for large characteristic finite fields, used for example in the digital signature algorithm (DSA), solving for the discrete logarithm remains a problem of sub-exponential complexity L(1/3).
Small characteristic finite fields may be found in a type of cryptography known as “pairing-based,” in which elements of two cryptographic groups are combined. This kind of cryptography is used in some systems that, for example, base encryption keys on personal attributes or the names of users. Pairing-based systems that use finite fields of small characteristic should now be avoided, the developers of the new algorithm say. “We are proving that some discrete log problems are much, much easier than we once thought,” Thomé says. The warning may apply in particular to makers of hardware-based crypto, who like to use the small-characteristic, binary finite fields because they are easy to implement in hardware.
Some companies use pairing-based systems of their own design, but so far there is no firmly established standard for them, Thomé says. “They are an attractive option for applications like identity-based crypto or voting systems,” he notes.
Alfred Menezes, who has studied the new algorithm as a cryptographic researcher at the University of Waterloo in Ontario, Canada, calls it “a fantastic algorithm—a stunning development.” He says, “If I were a company today considering the use of pairing-based cryptography, I would be terrified of using small-characteristic pairings.” In one case he studied, the algorithm succeeds in 274 operations, vs. 2103 operations with the previous best algorithm. “While the 274 computation is certainly a formidable challenge, with an organization like the NSA, it becomes feasible.”
Menezes says his analysis also shows the algorithm only becomes effective as the parameters of a cryptosystem, essentially the key size, grow asymptotically large. It may not be efficient; in fact, it may be slower than other algorithms against systems of small key size. Also, it is not effective against RSA and other non-pairing-based systems.
The Algorithm
The new method lies in a family of what are called index calculus algorithms, used for computing discrete logarithms. It uses a “Las Vegas” algorithm, one that always yields the correct result, but in an amount of time that varies. Researchers can estimate runtimes, but cannot know exactly what the run time will be in any specific case. “We are sure of the result, but do not know if it will take two months or two months plus one week,” says Razvan Barbulescu, a Ph.D. student at the University of Lorraine and a co-developer of the algorithm. However, they can be sure it would not take two minutes, he adds.
The new method lies in a family of what are called index calculus algorithms, used for computing discrete logarithms.
The algorithm is heuristic and involves the use of conjectures that cannot be proven. Says Barbulescu, “We can check experimentally that it works, but the math to prove it is difficult.” Finally, he says, it is a recursive process, one that solves a big problem by solving smaller (and easier) instances of it.
The algorithm’s recursion involves representing the elements of the finite field in a cascade of polynomials, starting with the polynomial from which the discrete log is to be computed. This is broken down into smaller polynomials, and those into successively smaller polynomials, into something called a “descent tree.” Then, “building up an answer from the bottom with logs is pretty easy,” says Barbulescu.
The breakthrough lay in finding a way to perform the descent process more efficiently than previously possible, he says, and in building a deeper tree with smaller problems at the end points.
The Future
Barbulescu says the research group has considered trying to push its ideas to medium- and large-characteristic systems, “but there is a huge difficulty porting this algorithm to these other cases,” he says. “But if we were able to extend it to large characteristic, then it would be an earthquake in cryptography because every time there is an improvement in discrete logarithm, there is a corresponding improvement in factorization (RSA), because the problems are similar.”
Meanwhile, though, existing RSA-based systems should be considered secure. “There are some buzz articles floating around on the Web saying that this is the endgame for RSA,” Thomé says. “It is wrong to say that.”
The University of Waterloo’s Menezes says he is not aware of any cryptosystems in use today that are suddenly at risk because of the work by the French team. However, he warns, “There will be faster algorithms, better implementations of the existing algorithm perhaps through special-purpose hardware, and better analysis. Maybe the algorithms are faster than we think they are.”
Further Reading
Adj, Gora, Menezes, A., Oliveira, T., and Rodriguez-Henriquez, F.
Weakness of F36.509 for discrete logarithm cryptography, http://eprint.iacr.org/2013/446 Presented at Crypto 2013 rump session, Santa Barbara, Calif., Aug. 20, 2013 http://crypto.2013.rump.cr.yp.to/.
Barbulescu, R., Gaudrey, P., Joux, A., and Thomé, E.
A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, June 2013, preprint available at http://eprint.iacr.org/2013/400.pdf
Blake, I., Seroussi, G., and Smart, N.
Advances in elliptic curve cryptography, second edition, London Mathematical Society Lecture Note Series, April 2005 http://www.amazon.com/Advances-Elliptic-Cryptography-Mathematical-Society/dp/052160415X
Joux, A.
A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic, to be in Proceedings of Selected Areas in Cryptography 2013 (SAC 2013), Burnaby, British Columbia, Canada, August 2013. Paper at Cryptology ePrint Archive, Report 2013/095, 2013 http://eprint.iacr.org/2013/095
Menezes, A., van Oorschot, P., Vanstone, S.
Handbook of Applied Cryptography, CRC Press, October 1996, http://www.cacr.math.uwaterloo.ca/hac
Join the Discussion (0)
Become a Member or Sign In to Post a Comment