CS 161 Computer Security Fall 2008 Dawn Song 1 Notes 2 Brief History of Cryptography The word cryptography comes from the latin root crypt meaning secret and graphia meaning writing So cryptography is literally the study of how to send secret messages In the next few lectures we shall study encryption schemes as well as some other fundamental goals of cryptography authentication and digital signatures Schemes for sending secret messages go back to antiquity the Romans used the Caesar cypher which consists 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 the developement of the telegraph wireless communication at the end of the nineteenth century the need for encryption in military and diplomatic communications became particularly important The codes that were used during this pen and ink period were relatively simple since messages had to be decoded by hand The codes were not very secure especially with the use of mathematical and statistical techniques The second phase of cryptography the mechanical era was the result of an intense German project to create a mechanical device for encrypting messages in an unbreakable code The resulting Enigma machine was a 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 and according to most experts shortened the war by about a year There were two important factors in the breaking of the Enigma code first the British managed to obtain a replica of a working Enigma machine from Poland which had cracked a simpler version of the code The second factor was scale and sophistication of the code breaking effort first by the Poles who employed a large contingent of mathematicians to crack the structure and then by the British whose massive effort included Alan Turing one of the founding fathers of computer science Modern cryptography is distinguished by its reliance on mathematics and electronic computers It has its early roots in the work of Claude Shannon following World War II The analysis of the one time pad later in this 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 encryption standards in banking and other business The decade starting in the late seventies saw an explosion of work on a computational theory of cryptography The most basic problem in cryptography is one of ensuring the security of communications across an insecure medium The two main members of the cast of characters in cryptography are Alice and Bob who wish 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 be tapped by Eve the eavesdropper The goal is to design a scheme for scrambling the messages between Alice and Bob in such a way that Eve has no clue about the content of their exchange In other words we wish to simulate the ideal commuication channel with the available insecure channel In a symmetric trust model or the shared key model Alice and Bob share a random key K that is unknown to Eve Alice encrypts her message A based on the key K and Bob decrypts the received ciphertext to recover CS 161 Fall 2008 Notes 2 1 the original message the plaintext using the same key K Let us now examine the threat model which in this setting involves answering the question how powerful is Eve We will assume that Eve knows the encryption and decryption algorithms The only information she is missing is the secret key K There are several possibilities about how much access Eve has to the insecure channel 1 Eve has managed to intercept a single encrypted message and wishes to recover the plaintext the original 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 of her choice this might happen if Eve has access to the encryption program 4 Eve can trick Bob into decrypting some ciphertexts 2 One time Pad The one time pad is a simple and idealized encryption scheme that will help illustrate some important concepts Alice and Bob share an n bit secret key K k1 kn where the bits k1 kn are picked at random they are the outcomes of independent unbiased coinflips Suppose Alice wishes to send the n bit message A a1 an The desired properties of the encryption scheme are 1 It should scramble up the message i e map it to a ciphertext B b1 bn 2 Given knowledge of the secret key K it should be easy to recover A from B 3 Eve who does not know K should get no information about A The encryption scheme is very simple b j a j k j where is the xor or exclusive or of the two bits 0 if the two bits are the same and 1 if they are different Decryption is equally simple a j b j k j To sum up the one time pad or any symmetric encryption scheme is described by specifying three procedures Key generation Alice and Bob pick a shared random key K Encryption algorithm B A K Decryption algorithm A B K Let us now analyze how much information Eve gets about the plaintext A by intercepting the ciphertext B What is the correct measure of this information gained by Eve It might be the case that Eve had some partial information about A to begin with Perhaps she knew that the last bit of A is a 0 or that 90 of the bits of A are 10 s We wish to show that after intercepting B Eve gets no additional information about A We will show this by proving that no matter what the value of A is the transmitted value b is a uniformly random n bit string Another way of saying this is the following CS 161 Fall 2008 Notes 2 2 Consider the following experiment suppose Alice has sent one of two messages A or A0 Eve tries to distinguish which by looking at the ciphertext We will show that Eve s success probability is 1 2 which is no different than it would be if she had not intercepted the ciphertext at all The proof is very simple how does the one time pad encrypt a particular message A Each possible value of the ciphertext B can be achieved by an appropriate and unique choice of the shared key K namely K A B Since each such key value K is equally likely it follows that B is also
View Full Document
Unlocking...