As part of Entrust’s ongoing celebration of our 20th Anniversary of Public Key Infrastructure (PKI), we’re looking back in a four-part series on the pioneers, processes and events that have shaped this ever-evolving technology.
In parts one and two, we traced the early history of PKI and highlighted some of the challenges and innovations that shaped the technology. Today we look back at how patent issues and government involvement affected the continued development, access and adoption of PKI.
The ideas behind public-key cryptography had been patented in the U.S. in the mid-1970s, which ultimately delayed the widespread adoption of the technology. But by 1989, the Internet Engineering Task Force was ready to publish specifications for Privacy-Enhanced eMail (PEM), which included extensions to the Internet mail protocol, providing for encryption and digital signature using public-key cryptography.
The specification identified just one particular company – RSA Data Security Inc. – as the global root certification authority of the PKI. What’s more, they also specified the price to be paid for an end-user certificate. Many found this contrary to the ethos of the Internet and PEM turned out to be a failure. Its successor S/MIME had to await the expiry of the patents.
Through the early ‘90s, it was becoming increasingly clear that advances in cryptanalysis and silicon technology were nibbling away at the security of the DES algorithm. Yet in North America, it was not possible to obtain an export license for products with greater cryptographic strength – nor for products with an RSA key length greater than 512 bits. Meanwhile, locally developed products in Europe were available with greater strength. The industry lobbied the U.S. Congress to change the law and to allow the export of stronger cryptography.
At the same time, the FBI was lobbying Congress to obtain a provision in law requiring vendors and service providers to include an escrow facility that would allow them to recover plaintext from encrypted communications. The FBI and NSA collaborated on the design of an algorithm, called “Skipjack” and a chip implementation named “Clipper” to meet the FBI’s needs.
In the academic community, researchers using a special purpose machine demonstrated that DES could be cracked. And in a large-scale collaborative effort, another research team cracked 512-bit RSA. Dan Bernstein, a student at the University of California at Berkeley challenged the U.S. Government over its refusal to allow him to publish a new cryptographic algorithm – claiming that export laws violated his first amendment rights. After protracted court proceedings lasting almost the whole decade, he prevailed.
Hobbyists were also getting in on the act. Phil Zimmerman developed his PGP software program, which provided strong encryption for email and distributed it in guerrilla fashion for free download from the Internet.
Eventually, something had to give. Finally, in 2000 the U.S. Government relented and the FBI’s “Clipper” initiative was abandoned. Today, encryption products are available worldwide with a strength of more than 100 bits.
The first practical public-key cryptographic systems were based on groups whose elements were integers. But Whitfield Diffie of MIT first pointed to the possibility of using groups based on quite different elements. One alternative has withstood cryptanalytic scrutiny: Elliptic-curve cryptography (ECC), whose elements are discrete points on a continuous curve, combined using geometric formulae. This has a number of features that make it attractive in constrained environments, such as those that are encountered in both smartcards and the Internet of Things.
The best known algorithm for breaking elliptic curve cryptography has exponential running time, which means that adding two bits to the key size doubles the cryptographic strength – and doubles the work required by an attacker to disclose the private key – regardless of what strength you start with. On the other hand, the best-known algorithm for breaking RSA has sub-exponential running time. This means that as strength requirements grow, the key size has to grow at a faster pace. The key size required for effective long-term protection using the RSA algorithm is already a performance challenge for constrained environments.
The performance impact of RSA will become harder to tolerate as the demand for increasing cryptographic strength continues. For this reason, elliptic curve cryptography will become increasingly important.
Next Time: The Future of PKI