Most of the privacy technology used on the Internet, and in many other places, is under-pinned by public-key cryptography; most notably, public-key key agreement protocols and public-key encryption algorithms. Almost all of this technology is based on two incredibly important mathematical algorithms: the Diffie-Hellman key agreement protocol (publicly discovered in 1976) and the RSA encryption algorithm (publicly discovered in 1978). If we hadn’t had these two algorithms, then the security world would have been a very different place. And we almost didn’t have them…

It’s relatively well known now that, before the whole concept of public-key cryptography was publicly discovered by Whitfield Diffie and Marty Hellman in 1976, it was discovered several years before by the UK Government’s military cryptography group at GCHQ.

The notion of public-key cryptography was first invented by James Ellis in 1969 — seven years before the idea would be re-discovered in the public domain. However, Ellis couldn’t come up with a practical system — just a proof of concept system that would never be useable in practice. A practical system was not discovered until 1973, when Clifford Cocks invented the algorithm that we now call the RSA algorithm. The idea, he says, came to him overnight. A few months later, another researcher at GCHQ, Martin Williamson, invented the algorithm that we now call Diffie-Hellman, also overnight.

What is less well-known, and I only recently discovered, is that the UK government also considered patenting the ideas.

This revelation was announced during an invited talk by the cryptography pioneer Clifford Cocks at the Eurocrypt 2008 research conference — the largest and most highly regarded European conference in cryptographic research — which was held this year in Istanbul, Turkey. Geography buffs will be pleased to hear that it was held on the Western bank of the Bospherus river — if it had been held on the Eastern bank, then it would technically have had to be the Asiacrypt conference.

And so it was to a packed house of cryptographers, that Clifford Cocks announced that the UK Government had considered filing a patent on the Diffie-Hellman protocol and the RSA algorithm — the two algorithms which underpin privacy almost everywhere on the Internet. There was a collective gasp, from myself included, but I don’t think that I fully understood the implication of the revelation at that time. Naively, I only thought of the revenue that could have been created.

It’s not clear whether the UK Government would have actively sought to repress public-key cryptography during the 1980s. I think it’s fair to say that most major powers were worried about the proliferation about strong cryptography. Early attempts by the ISO standardisation committee to standardise the RSA algorithm in that decade were blocked for political reasons. However, it’s not really fair to say that this implies that the UK Government would have sought to control the technology, but if they had wanted to repress it, then a patent would have been the perfect weapon in their arsenal.

Regardless of the political controversy, it is fair to say that it is unlikely that RSA Labs are unlikely to have been formed if someone else had held the patent to the RSA algorithm, and this would have profound effects on the development of security technology. After the ISO standardisation committee failed to standardise public-key cryptography, it was RSA Labs that stepped in to help, by producing the RSA PKCS series of standards. These standards underpin the use of public-key key agreement and public-key encryption everywhere.

No public-key cryptography standards means there wouldn’t have been any secure commercial implementations, which means there wouldn’t have been a secure and private Internet.

So, even if the UK Government hadn’t inhibited the use of public-key technology, the patent would have probably had meant that we didn’t develop standards for public-key cryptography for many, many years. We might, at this stage, be as much as ten years behind on the development of practical privacy systems on the Internet.

So who should we thank for the development of useable public-key cryptography? Well, clearly we should thank the scientists involved in the discovery, both the governmental inventors of public-key cryptography (Ellis, Cocks, and Williamson) and their commercial counterparts (Merkle, Diffie, Hellman, Rivest, Shamir, and Adleman). However, in a weird way, we also need to thank the GCHQ lawyers who claimed that a patent on these ideas was unobtainable: if not for these lawyers, then we wouldn’t have the security sector that we have today.

Dr. Alex Dent

Cryptography is currently a very active, thriving area of interdisciplinary academic research. Various new proposals for cryptographic algorithms and protocols are published every year. New proposals are usually followed by extensive public scrutiny, which may often uncover design flaws. Lessons learned are incorporated, often leading to more secure and efficient designs in the future. Algorithms are continuously being analysed by the academic community; the old principle of “security through obscurity” seems to have finally been abandoned.

An interesting question arising from such form of development lifecycle is: what are the practical implications from an academic break of a cryptographic algorithm? What if academic research shows some structural weakness in an algorithm, implying that the security claims made by the designers are no longer valid? Although it should certainly represent a danger to the algorithm long term deployment, how can we assess whether this compromises the algorithm’s current practical use? For example, imagine that a researcher can show that, due to some unexpected structural properties, the complexity of a key-recovery attack against a 128-bit encryption algorithm (e.g. the AES) is of the order of 2¹⁰⁰ operations, rather than 2¹²⁸ operations as expected. These are both extraordinarily large numbers, so should this put in doubt the protection provided by the algorithm? Likewise, if some weakness or irregular behaviour affecting a specific application of a cryptographic algorithm is uncovered, does this compromise different uses of the same algorithm?

These are not easy questions to answer! Most researchers would argue that common sense should prevail in these situations. While medium-term replacement of the affected algorithm must be considered and disclosure of such properties will probably lead to better designs in the future, in most cases academic breaks represent little practical danger for current use of an algorithm. Such weakness in an encryption algorithm should not mean that one would find (in practice) easier to recover an encrypted message. Likewise, the lack of collision resistance in a hash function algorithm should in principle represent little danger to passwords protected by the same algorithm. However we currently witness a growing trend of regulation-driven deployment of information security measures, and as consequence, of cryptography. As a result, this advice may need to be reassessed, as the case below illustrates.

In late 2004, a driver was caught by a digital speeding camera driving above the limit in a town in New South Wales, Australia. During the court case that followed, the driver chose not to give evidence and never questioned the speed recorded in the digital image provided by the NSW Road and Traffic Authority. Instead, his lawyer relied on questioning the cryptographic algorithm used to provide integrity protection of the digital photos. The NSW Road Transport (Safety and Traffic Management) Act 1999 explicitly specified the MD5 hash function algorithm as digital security indicator to ensure that speeding camera evidence had not been tampered with.

The lawyer had apparently learned of a recent work by a group of Chinese researchers led by Xiaoyun Wang, which proposed new techniques to efficiently compute collisions in two of the most popular hash function algorithms, namely MD5 and SHA-1. This represented a surprising breakthrough in hash function cryptanalysis, and has led to a surge in research in the area. Many academic articles have followed, showing how to improve and extend the attacks against other hash functions. However it is common agreement among researchers working in the field that, while their findings showed an essential structural weakness in these algorithms and has definitely accelerated their replacement (in fact, NIST has announced a competition to select a new hash function standard), they affect specific uses of hash functions (such as digital signatures, commitment) and in specific situations. Although it would very unwise to develop and deploy new products using the affected algorithms, there is currently no evidence that all other uses of MD5 and SHA-1 have been compromised (for some interesting examples of applications of the attacks, see here and here).

Yet, the lawyer in the case argued that the recent research meant that MD5 was in essence broken (which is true, in academic terms) and as such could not be relied on to provide integrity protection. Although the RTA was given eight weeks to provide an expert witness to argue otherwise, it nevertheless failed to do so, and as a result the magistrate had little option but to throw the case against the defendant. In March 2006, the NSW Supreme Court upheld the lower court case ruling dismissing the speeding camera ticket as unreliable, and ordered the government to pay the defendant’s legal costs.

Although it is very unlikely that a malicious player could exploit the lack of collision resistance in MD5 to temper with the speeding camera digital photo and the evidence provided, this particular case illustrates the possible implications of the wide-spread deployment of cryptography, driven by legislation and regulation, without clear understanding of its strengths and limitations. Was this simply an anomalous, isolated case or can it be a sign of more to come? While apparently there have been no similar follow-up cases in Australia, the implications of such outcome could be potentially staggering: an early case in which the accuracy of speeding cameras were put in doubt resulted in the refund or waive of fines for thousands of motorists caught by speed cameras in Victoria, at a cost of A$26 million! Thus, in addition to software vulnerabilities, malware and hackers, CSOs may also need to start paying special attention to cryptanalytic research.

Dr Carlos Cid