There is a growing debate in the cryptography community over whether the cryptographic keys used in dozens of applications should be considered compromised in light of a recent paper detailing a more efficient way of factoring large numbers.
On one side are security and cryptography enthusiasts—professionals and amateurs alike—who believe that the technique, described in a paper published last fall by a University of Illinois-Chicago mathematician, could enable someone with enough time and money to build a machine capable of factoring keys as large as 1024 bits derived from the RSA algorithm in a relatively short amount of time. Such a breakthrough theoretically would jeopardize the security of common protocols and applications such as Pretty Good Privacy (PGP), IPSec, SSH and others, all of which are typically deployed with keys smaller than 1024 bits, these people contend.
On the other side is an equally well-informed group of crypto and security folks who acknowledge the theoretical possibility of the factoring method but believe that the machine required to perform the computations is practically impossible to build and is therefore no threat to the keys in use today.
And right in the middle is Daniel Bernstein, the associate professor of mathematics at UIC whose paper has caused all of the furor. Bernstein has stayed above the fray, but that hasnt slowed the discussion of his work one bit.
On Saturday, Marc Briceno, a longtime member of the Cypherpunks group, posted to the Bugtraq mailing list a detailed message describing how an entity such as the National Security Agency with its huge budget and unparalleled resources could build the kind of machine needed to use Bernsteins technique. Some experts have estimated that it would cost nearly $1 billion to build such a system.
“Would the NSA have built a device at less than half the cost of one of their satellites to be able to decipher interception data obtained via many such satellites? The NSA would be derelict of duty to not have done so,” wrote Briceno, who is on the board of directors of the International Financial Cryptography Association and is one of the people responsible for breaking in 1998 the authentication and encryption cipher used in GSM phones.
He went on to say that he has revoked all of his 1024-bit RSA keys and considers them compromised.
But building such a machine may not be necessary. At a recent cryptography conference, Nicko van Someren, CTO of nCipher Inc., a security company based in Cambridge, U.K., announced that nCipher researchers had developed a method of factoring 512-bit RSA keys in less than six weeks using readily available computers. Keys of that length are far more common than 1024-bit or 2048-bit keys and the possibility of their being compromised is much more worrisome to many in the security community.
Even so, Bricenos post received considerable attention on several mailing lists, but some experts say hes jumping the gun and giving the NSA and its counterparts too much credit.
“[Bricenos]e-mail is alarmist, in my opinion. I dont assume that someone with a massive budget has already built this machine, because I dont believe that the machine can be built,” said Bruce Schneier, a noted cryptographer and author and the CTO of Counterpane Internet Security Inc., in Cupertino, Calif., who wrote an analysis of Bernsteins paper in his Crypto-Gram email newsletter recently. “The Bernstein paper is theoretical only, and there is no reason to believe that it has any affect on practical key lengths. We have no way of knowing when the efficiencies would kick in.”
Others arent so sure, however, and say that the prudent course is to assume that keys of 1024 bits and smaller are insecure.
“I think that we should assume that well funded government agencies can break 1024-bit keys on demand, rather than the previous common belief that they could break them but only with a huge amount of time and effort,” van Someren said. “The implications of this for national security are clear. The implication for business is less so.”
