CS 161 Computer SecuritySpring 2010 Paxson/Wagner Notes 3/11 Brief History of CryptographyThe word “cryptography” comes from the latin root crypt meaning secret, and graphia, meaning writing. Socryptography is literally the study of how to send secret messages. In the next few lectures we shall studyencryption schemes as well as some other fundamental goals of cryptography: authentication and digitalsignatures. In a nutshell, cryptography is about communicating securely over an insecure communicationsmedium.Schemes for sending secret messages go back to antiquity. The Romans used the “Caesar cypher” whichconsists of permuting the alphabet by simply shifting each letter forward by a fixed amount. For example,Caesar used a shift by 3 so the message “cryptography” would be encoded as ”fubswrjudskb”. With thedevelopement of the telegraph (wireless communication) at the end of the nineteenth century, the need forencryption in military and diplomatic communications became particularly important. The codes that wereused during this “pen and ink” period were relatively simple since messages had to be decoded by hand.The codes were not very secure, especially given modern mathematical and statistical techniques.The second phase of cryptography, the “mechanical era” was the result of a German project to create amechanical device for encrypting messages in an unbreakable code. The resulting Enigma machine wasa remarkable engineering feat. Even more remarkable was the massive British effort to break the code.The breaking of the Enigma code was an important event that determined the course of World War II, andaccording to most experts shortened the war by about a year. There were three important factors in thebreaking of the Enigma code. First, the British managed to obtain a replica of a working Enigma machinefrom Poland, which had cracked a simpler version of the code. The second factor was the sophisticationof the Allied codebreakers, first the Poles, who employed a large contingent of mathematicians to crackthe structure, and then the British, whose massive effort included Alan Turing, one of the founding fathersof computer science. The third factor was the scale of the code-breaking effort. The Germans figuredthat the Enigma was well-nigh uncrackable, but what they didn’t figure on was the unprecedented level ofcommitment the British poured into breaking the Enigma, once the codebreakers made initial progress: atits peak, the British codebreaking organization employed over 10,000 people breaking these codes, a levelof effort that vastly exceeded anything the Germans had anticipated.Modern cryptography is distinguished by its reliance on mathematics and electronic computers. It has itsearly roots in the work of Claude Shannon following World War II. The analysis of the one-time pad later inthis lecture is due to Shannon. The early seventies saw the the introduction of the cryptosystem DES by NIST(the National Institute for Standards in Technology). DES answered the growing need for digital encryptionstandards in banking and other business. The decade starting in the late seventies saw an explosion of workon a computational theory of cryptography.The most basic problem in cryptography is one of ensuring the security of communications across an in-secure medium. The two main members of the cast of characters in cryptography are Alice and Bob whowish to communicate securely as though they were in the same room or were provided with a dedicated,untappable line. In actual fact they have available a telephone line or an internet connection which can beCS 161, Spring 2010, Notes 3/1 1tapped by an eavesdropping adversary, Eve. The goal is to design a scheme for scrambling the messagesbetween Alice and Bob in such a way that Eve has no clue about the content of their exchange. In otherwords we wish to simulate the ideal communication channel with the available insecure channel.We will discuss encryption in this lecture. Encryption is focused on ensuring the confidentiality of commu-nications between Alice and Bob. In the symmetric-key model, Alice and Bob share a random key K that isunknown to Eve. Alice encrypts her message M using the key K, and Bob decrypts the received ciphertext(to recover the original message) using the same key K. The unencrypted message M is sometimes knownas the plaintext, and its encryption is sometimes called the ciphertext.Let us now examine the threat model, which in this setting involves answering the question, how powerfulis Eve? Consistent with Kerkhoff’s principle, we will assume that Eve knows the encryption and decryptionalgorithms1. The only information she is missing is the secret key K. There are several possibilities abouthow much access Eve has to the insecure channel:1. Eve has managed to intercept a single encrypted message and wishes to recover the plaintext (theoriginal message).2. Eve has intercepted an encrypted message and also has some partial information about the plaintext.3. Eve can trick Alice to encrypt messages M1,M2,...,Mnof her choice (this might happen if Eve hasaccess to the encryption program). At some other point in time, Alice encrypts a message M that isunknown to Eve; Eve has intercepted the encryption of M and would like to recover M.4. Eve can trick Bob into decrypting some ciphertexts C1,...,Cn. Eve would like to use this to learn thedecryption of some other ciphertext C (different from C1,...,Cn).5. A combination of cases 3 and 4: Eve can trick Alice into encrypting some messages of Eve’s choosing,and can trick Bob into decrypting some ciphertexts of Eve’s choosing. Eve could like to learn thedecryption of some other ciphertext that was sent by Alice (and in particular did not occur as a resultof her trickery).The first two cases are known as a ciphertext-only attack (the difference between them is that in the sec-ond case, Eve has partial information, whereas in the first case she does not). The third case is known asa chosen-plaintext attack, and the fourth as a chosen-ciphertext attack. The fifth is known as a chosen-plaintext/ciphertext attack, and is the most serious threat model. Today, we usually insist that our encryptionalgorithms provide security against chosen-plaintext/ciphertext attacks, both because those attacks are prac-tical in some settings, and because we can: it is feasible to provide good security even against this very pow-erful attack model. However, for this lecture we will
View Full Document
Unlocking...