4 March 2007
Related:
http://cryptome.org/nsa-nse/nsa-nse-01.htm
(Times Higher Education Supplement, 22 April 1999)
Revelations from the secret world of spying raise academic questions for both history and mathematics
Duncan Campbell
Twenty five years ago, saving the world from a nuclear holocaust might have depended on the ability or inability of mathematicians to factorise the products of very large prime numbers. But the fundamental theories needed, although secretly discovered by and known to mathematicians inside intelligence organisations at the time, were just not available even to bomb-makers. The world was less secure as a result.
Soon afterwards, academic mathematicians made the same discoveries on parallel timescales, publishing them and in some cases registering valuable patent rights. Within the decade following, the methods published openly by the academic community had been used extensively by nuclear weapons engineers to install "permissive action links" to keep control of weapons stockpiles, and to reliably verify arms control treaties.
International commerce as well as military security now stands (or falls) on the same mathematical methods. By early next century, the safety of tens of billions of pounds worth of international trade will depend on the same systems and on a clutch of propositions in number theory.
The astonishing similarity of timescale and techniques which evolved during the 1970s within the secret and open worlds of mathematics highlights a fundamental and longstanding debate about "secret" scientific research. The questions are whether advances are made more quickly, better understood and utilised, or of greater public benefit if they are achieved in secret or in academia.
Next week in London the (open) inventor of public key cryptography, Dr Whitfield Diffie, a "distinguished engineer" with Sun Microsystems, California, will be lecturing to the British Society for the History of Mathematics at University College, London. He will compare his own open invention of "public key cryptography" in 1976 with a recent claim that British government cryptographers discovered the same idea six years earlier.
Diffie and colleague Martin Hellman first published the idea in a landmark paper, "New directions in cryptography" in November 1976. Over the next two years, a second group of mathematicians – Rivest, Shamir and Adelman (RSA) - published the first practical technique for implementing public key cryptography.
These inventions began a revolution in applied mathematics and communications engineering. It made routine communication encryption practical and potentially ubiquitous. It solved the deepest problem faced by all previous methods – how to establish a secure channel for sending keys, before any messages were sent. It also provided for "authentication" – a digital method whereby a message can mathematically be proven to have come from only one possible sender. The applications of "digital signatures" derived from these discoveries can embody an authority to launch nuclear attack just as easily as they can validate an Internet order for a case of wine So did mathematicians working secretly inside intelligence agencies actually beat Diffie, Rivest and their colleagues?
In 1997, with no prior warning, Britain's long-time secret signals intelligence agency GCHQ (Government Communications Headquarters) emerged from the shadows and claimed that its staff had invented the idea in the late 1960s. On 16 December 1997, they published (on the Internet) the first of a series of 6 papers written between 1970 and 1987 which, if authentic and complete, showed an astonishing "parallelism" of scientific and mathematical research between the academic community and the closed, ultra secretive world of "Sigint".**
British mathematicians James Ellis, Cliff Cocks and Malcolm Williamson were all employees of the government Communications-Electronic Security group, whose primary job as part of GCHQ was to provide secure codes for the British government and armed forces. Although there were differences of approach and of emphasis, the GCHQ papers together essentially lay claim to the first invention both of the public key idea and of its "RSA" implementation. The most obvious difference was the title the different groups gave their work, which Ellis and co-workers called "Non Secret Encryption".
Dr Diffie will say next week that he accepts the claim to parallel invention of his own discovery. He was first alerted to the issue in the early 1980s after hearing remarks by the director of GCHQ's American counterpart, the National Security Agency. NSA director Admiral Bobby Inman had claimed in a speech that NSA had discovered public-key methods "in the early seventies", but had then classified the method and locked it away from view.
Admiral Inman's claims have never been verified or substantiated. And it would be even more remarkable if a third group of NSA staff had come up with the same idea on the same timescale as both Diffie and Ellis. But given the wholesale co-operation that exists between GCHQ and NSA, it is likely that British ideas were shared with US colleagues. Both organisations circulate highly classified technical journals to their staff, so as to allow their large teams of mathematicians, engineers, linguists and scientists to share ideas within the closed community in which they work. Inman may have been incompletely briefed.
According to Dr Judith Field, who chairs the British Society for the History of Mathematics, there are many unsatisfactory aspects to the claims now being advanced that Ellis and his team was secretly ahead of academic work. The papers CESG have published are incomplete. They give no indication as to where they were originally published, or to whom. CESG claims that they are "internal technical papers" which apart from converting to HTML format (for the internet) "have not otherwise been edited". But CESG has so far been unwilling to provide copies of the papers as originally published, leaving themselves open to allegations that the electronic versions found only on their World Wide Web site may have been altered.
This is "thoroughly unsatisfactory" from an historical point of view, says Dr Field. Authentic documents are needed to make sure that their terms, dates and presentation have not been "improved" or adjusted. Nevertheless, leading cryptographers like Dr Diffie have long been aware of some of Ellis's work and accept that his claim is in substance likely to be correct.
But the careful selection of papers made by CESG obscures many fundamental issues. Most critically, why was the CESG discovery never exploited but left to stagnate? Although CESG now makes – and even sells – an e-mail cryptographic systems based on public keys called "Cloud Cover", this owes nothing to the pioneering advances which it now claims were its own.
As soon as the idea of digital signatures appeared in the open literature, weapons designers realised that it could provide a method of verifying arms control treaties, using "black boxes" installed at test sites. According to one of the top US verification systems designers, the first he heard of the idea was when he read about it in Scientific American - at the same time as everyone else. He started work immediately. By 1986, the RSA algorithm was inside US "black boxes" buried around the Soviet Kazakhstan test site, helping lead to the end of the Cold War.
According to Bruce Schneier, a leading open cryptographer, "the Ellis case is a useful tool to examine the interplay between the idea of a "secret" mathematics inside the walls of the spooks, and the open maths outside. I have heard many anecdotes about how the walls seem to have had to been breached, both ways, as key ideas in number theory moved forward on one side on the other. The Ellis/Diffie case becomes a special case with a highly applied and relevant result".
Schneier asks "If the British found public-key encryption in the late 1960s sixties, as well as essentially the RSA algorithm a few years later, the question arises - did they keep it to themselves, perhaps delaying the end of the Cold War?"
Part of the answer may lie in the limited material CESG has now published. They attribute the first discovery to Ellis in January 1970. His paper identifies a major principle of public key cryptography, the use of so-called "one way" functions. This makes encoding easy but deciphering the message infeasible in a reasonable, finite time.
After he retired in 1987, Ellis wrote a classified review of his early work. He explained how the basic idea had come to him "in bed one night".
"Cryptography is a most unusual science", he observed. Most professional scientists aim to be the first to publish their work, because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography is realised by minimising the information available to potential adversaries. Thus professional cryptographers normally work in closed communities to provide sufficient professional interaction to ensure quality while maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests of historical accuracy after it has been demonstrated clearly that no further benefit can be obtained from continued secrecy".
"The proof of the theoretical possibility took only a few minutes", he added. "We had an existence theorem. The unthinkable was actually possible".
Ellis's paper was declassified and published in 1997, shortly after he died. The papers were published partly in tribute and partly to enable his colleague, Cliff Cocks to lay claim to have been the original inventor of the "RSA" method.
Back in 1973 and just down from King's College Cambridge with a first in maths, Cliff Cocks joined GCHQ in Cheltenham. By November the same year, he had published a short paper on "non secret encryption". In essence, he described the system that Rivest revealed to the world five years later. Then two further CESG papers, in 1974 and 1976, foresaw the Diffie and Hellman method. But the author of these papers, Malcolm Williamson, pointed hesitantly to the flaws of working in a small and closed community.
"I find myself in an embarrassing position", he wrote, " as I have come to doubt the whole theory of non-secret encryption. I have no proof that the method is genuinely secure… This may be no more serious than the analogous fact that there is no proof that any of our ordinary encryption methods are genuinely secure but the fact does still worry me". He went on to say that he needed help from "someone who knows more number theory than myself" and that he did not sufficiently understand "computational complexity".
If that help was ever forthcoming, the evidence is still locked away behind GCHQ's fences. An academic researcher reaching the same point could have turned to the most accomplished colleagues anywhere in the world for support. Williamson could not. No-one could reassure him that the idea was not built on air.
There the CESG story ends. Within two years of Williamson's last paper, Diffie, Rivest and colleagues had published. Fame, fortune, history and acclaim belong to them. Even in the secret military world to which the Cheltenham team was supposed to contribute, the idea was apparently lost until rediscovered and published. It seems that, while Ellis and colleagues may have discovered the mathematics, they never understood the significance of what they had, nor had the confidence to develop it.
The proposition by the late James Ellis that "the fullest value of cryptography is realised by minimising the information available" thus fails. Although this was the authentic view of his secrecy-obsessed generation, the world has moved on. The industrial importance and success of academic cryptography is now fundamental to the open society.
(Times Higher Education Supplement, 22 April 1999)
* Thursday 29 April 1999, 5.30pm, Gustave Tuck Lecture Theatre, University College, London.
* http://www.cesg.gov.uk/about/nsecret/main.htm [dead URL]
Related British CESG papers:
"The History of Non-Secret Encryption," by J. H. Ellis, 1987 (made public in December 1997)http://www.cesg.gov.uk/site/publications/media/ellis.pdf (HTML version with CESG introduction in December 1997)
"A Note on Non-Secret Encryption'," by C. C. Cocks, 20 November 1973
http://www.cesg.gov.uk/site/publications/media/notense.pdf
"Non-Secret Encryption Using a Finite Field," by M J Williamson, 21 January 1974
http://www.cesg.gov.uk/site/publications/media/secenc.pdf
Thoughts on Cheaper Non-Secret Encryption," M J Williamson, 10 August 1976
Related:
http://cryptome.org/ukpk-diffie.htm (Whitfield Diffie message and others, with Cryptome's initial NSE FOIA to NSA)
http://jya.com/nsam-160.htm (message on Whitfield Diffie and the origin of NSE and public key cryptography)