Foundations of Computer SecurityLecture 42: A Perfect CipherDr. Bill YoungDepartment of Computer SciencesUniversity of Texas at AustinLecture 42: 1 A Perfect CipherA Perfect Cipher... ...... ...{M}K?SenderAnalystA perfect cipher wouldbe one for which no reduction of thesearch space is gained from knowing:1the encryption algorithm, and2the ciphertext.Shannon proved that a perfectcipher requires as many possible keys asplaintexts, with the key chosen randomly.Lecture 42: 2 A Perfect CipherOne Time PadA one-time pad, invented by Miller (1882) and independently byVernam and Mauborgne (1917), is a theoretically perfect cipher.The idea is to use a key that is the same length as the plaintext,and to use it only once. The key is XOR’d with the plaintext.Example: Given a 15-bit binary message:plaintext: 10110010111001key: 11010001010100ciphertext: 01100011101101Notice the space of plaintexts, ciphertexts, and keys are all thesame: 15-bit binary strings.Lecture 42: 3 A Perfect CipherOne Time Pad000001111...000001111...SenderAnalyst ?101 = P xor KWhy is the one-time pad perfect? Consider the space of three-bitmessages.Suppose the attackerintercepts the ciphertext (“101”)and knows that a one-time pad is in use.Every possible plaintextcould be the pre-image of that ciphertextunder a plausible key. Therefore, noreduction of the search space is possible.Why does it matter that the key berandom?Lecture 42: 4 A Perfect CipherKey DistributionThe main problem with the one-time pad is practical, rather thantheoretical.Given the need to communicate securely, how do the sender andreceiver agree on a secret (key) that they can use in the algorithm.If sender and receiver already have a secure channel, why dothey need the key?If they don’t, how do they distribute the key securely?This is the key distribution problem.Lecture 42: 5 A Perfect CipherVernam CipherThe Vernam cipher is a type of one-time pad suitable for use oncomputers.XOR- - -plaintext ciphertextoriginalplaintextXORlong seq. of numbers¡¡¡¡¡ª@@@@@RLecture 42: 6 A Perfect CipherOne Time Pad ApproximationApproximate the one-time pad using a PRNG to generate a key.Another computer running the same random number generatorfunction can produce the key from the seed. This works wellbecause a pseudorandom sequence may have a very long period.It is susceptible to compromise by someone who knows thealgorithm and the seed.Lecture 42: 7 A Perfect CipherLessonsThe one-time pad is a theoretically perfect encryptionalgorithm.However, it requires as much key material as there isplaintext, and suffers from the key distribution problem.An approximation suitable for computers uses a PRNG togenerate a seed.Next lecture: Transposition CiphersLecture 42: 8 A Perfect
View Full Document