The eponymous inventors of RSA, Drs Rivest, Shamir, and Adleman, were awarded the Turing Award for 2002 [1]. For those who don't know, the Turing Award, named after Alan Turing (the inventor of the modern computer architecture, and also the inventor of the Turing Test), is the premier prize in the computing world. It's a bit like a Nobel for software, but software was invented after dynamite.
In the three-way Turing Lectures, Professors Adleman and Rivest talked about the early days of RSA, and it was left to Professor Adi Shamir to present "A Status Report [2]" as his contribution. Three (quick) slides that leaped out, see below.
What is Prof Shamir trying to say? To me, he is confiming that the current cycle of revisionism in cryptography and software engineering is now acceptable mainstream thinking, if not complete. It is now accepted that Internet security modelling in the 90s was flawed, based on a poor understanding of the role of risk in cryptography systems.
The goal of practical cryptography is to improve the security, at a cost that is less than the benefit gained. Don't try and solve it, because you can't. As Prof. Shamir says, "absolutely secure systems do not exist.
Cryptographic misconceptions
- By policy makers: crypto is dangerous, but: - weak crypto is not a solution - controls can't stop the inevitable
- By researchers: A provably secure system is secure, but:
- proven false by indirect attacks
- can be based on false assumptions
- requires careful choice of parameters- By implementers: Cryptography solves everything, but:
- only basic ideas are successfully deployed
- only simple attacks are avoided
- bad crypto can provide a false sense of security
The three laws of security:
- Absolutely secure systems do not exist
- To halve your vulnerability, you have to double your expenditure
- Cryptography is typically bypassed, not penetrated
Cryptographic predictions:
- AES will remain secure for the forseeable future
- Some PK schemes and key sizes will be successfully attacked in the next few years
- Crypto will be invisibly everywhere
- Vulnerabilities will be visibly everywhere
- Crypto research will remain vigorous, but only its simplest ideas will become practically useful
- Non-crypto security will remain a mess
[1] 2002 A.M. Turning Award Winners, for seminal contributions to the theory and practical applications of Public Key Cryptography, Dr. Leonard M. Adleman, Dr. Ronald L. Rivest, Dr. Adi Shamir,
http://www.acm.org/awards/turing_citations/rivest-shamir-adleman.html?code=nlsec121
[2] Dr. Adi Shamir, "Turing Lecture on Cryptology: A Status Report,"
http://www.acm.org/awards/turing_lectures_project/turing/S/s-pp/shamir_1files.html
Wednesday, 12th May 2004
RSA founders give perspective on cryptography
M.E. Kabay, Network World
The famous cryptographers Leonard Adleman, Ronald Rivest, and Adi Shamir - the developers of the RSA encryption code - received the Association for Computing Machinery's 2002 Turing Award "for their seminal contributions to the theory and practical application of public-key cryptography." Their Turing Award lectures, given last June, are available online.
Rivest, Shamir and Adleman implemented public-key cryptography in the 1970s following the landmark work of Whitfield Diffie, Martin Hellman and Ralph Merkle. They then founded RSA Security, which became one of the most respected security companies in the world.
RSA organizes the immensely valuable annual RSA Conferences, perhaps the most significant security conference of the year now that the National Computer Security Center and the National Institute of Standards and Technology have stopped their late lamented National Computer Security Conferences.
While I'm mentioning RSA, I should remind readers that its FAQ is an excellent source of information about cryptography.
The distinguished scientists' lectures are available online in a variety of formats at: http://www.acm.org/awards/turing_citations/rivest-shamir-adleman.html?code=nlsec121
Adleman started the event with a brief historical overview of three major areas of study that led to the public-key cryptosystem (PKC): number theory, the study of computational complexity, and cryptology.
Next, Rivest reviewed the events around the invention of the RSA PKC. They hit on the idea of depending on the difficulty of factoring as the basis for a public/private key cryptosystem, where one key would be public, the other private, and each key would decrypt what the other key encrypted. Martin Gardner of _Scientific American_ helped them by publishing an article with a US$100 challenge for factoring a 129-digit product of two large primes (RSA-129). They estimated that factoring this number would take 40 quadrillion years. But the RSA-129 challenge was finally factored using thousands of cooperating computers via the Internet 10 years ago, and a ciphertext was decrypted as, "The magic words are squeamish ossifrage."
Finally, Shamir reviewed the current state of cryptography. Despite initial fears among the law enforcement community that encryption would lead to serious impediments for investigations and anti-terrorism work, reports from the US Department of Justice show that no federal wiretaps encountered encryption in 2002. In state and local jurisdictions, investigators encountered encryption in 16 wiretaps out of approximately 1,300 cases; however, in none of these cases did encryption interfere with the ability of the investigators to gather the evidence needed for prosecution.
Shamir pointed out that cryptography is central to today's technology. One of the most important benefits of cryptography is the constant interaction of theory and practice; for example, abstract mathematical tools have been productively applied to cryptanalysis. Similarly, well-established practical concepts such as basic notions of security, complexity, logic and randomness have stimulated much theoretical creativity.
Shamir formulated three laws of security. First, "Absolutely secure systems do not exist." We have to accept that we should implement systems that are secure enough. For example, postage stamps are a ridiculous security measure, but they work for millions of people around the world. Vending machines where you put in a coin and choose one newspaper out of the pile available are weak security systems, but they're good enough.
The second law is, "To halve your vulnerability, you have to double your expenditure." This law implies that improvements in security become less and les cost-effective the further one goes in improving one's systems.
Finally, "Cryptography is typically bypassed, not penetrated." He said he is unaware of any major, world-class security failure in which hackers penetrated systems by using heavy-duty cryptanalysis. They usually use much easier methods.
The last part of Shamir's presentation is a review of six major areas of today's cryptography: theory; public-key encryption and signature schemes; secret-key cryptography using block ciphers; secret-key cryptography using stream ciphers; theoretical cryptographic protocols; and practical cryptographic protocols.
[snip]
Posted by: Another Perspective at May 26, 2004 11:37 AMAh, well, it all depends... Software was first conceived by Ada Byron (later, Lady Lovelace) around 1838-1843. These years mark her interchange of letters with Babbage over the translation of lectures and an article dscribing his Analytical Engine. In the paper she published in 1843, she outlined the concept of software as an exposition of how to use the engine.
Alfred Nobel invented dynamite in 1866, and patented it a year later.
An invention in words is not an invention in deed. It wasn't until the construction of the Bomba in WWII, a full 100 years later, that software entered the world of deeds. Hence, the Turing Prize, not the Ada Prize.
Posted by: Iang at June 2, 2004 07:07 AMHi Ian,
The "laws" of security as presented in Shamir's Turing lecture were already common knowledge in the security research community at the time.
Making them part of his Turing lecture, Shamir did that community a Great service. He used the standing, fame and authority of the Turing awards, to lend these truisms appreciation by a wider audience. Quoting from his own T
lecture: "Received the ultimate seal of approval".
At the same time, because of their elusive nature, he made it sound as a grant proposal for further research ;-)
gr
Posted by: Twan at February 8, 2005 01:59 PM