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