CS 161 Computer Security Spring 2010 Paxson Wagner 1 Notes 3 1 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 In a nutshell cryptography is about communicating securely over an insecure communications medium 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 given modern mathematical and statistical techniques The second phase of cryptography the mechanical era was the result of a 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 three 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 the sophistication of the Allied codebreakers first the Poles who employed a large contingent of mathematicians to crack the structure and then the British whose massive effort included Alan Turing one of the founding fathers of computer science The third factor was the scale of the code breaking effort The Germans figured that the Enigma was well nigh uncrackable but what they didn t figure on was the unprecedented level of commitment the British poured into breaking the Enigma once the codebreakers made initial progress at its peak the British codebreaking organization employed over 10 000 people breaking these codes a level of effort that vastly exceeded anything the Germans had anticipated 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 CS 161 Spring 2010 Notes 3 1 1 tapped by an eavesdropping adversary Eve 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 communication channel with the available insecure channel We will discuss encryption in this lecture Encryption is focused on ensuring the confidentiality of communications between Alice and Bob In the symmetric key model Alice and Bob share a random key K that is unknown 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 known as 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 powerful is Eve Consistent with Kerkhoff s principle we will assume that Eve knows the encryption and decryption algorithms1 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 M1 M2 Mn of her choice this might happen if Eve has access to the encryption program At some other point in time Alice encrypts a message M that is unknown 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 the decryption 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 the decryption of some other ciphertext that was sent by Alice and in particular did not occur as a result of her trickery The first two cases are known as a ciphertext only attack the difference between them is that in the second case Eve has partial information whereas in the first case she does not The third case is known as a chosen plaintext attack and the fourth as a chosen ciphertext attack The fifth is known as a chosenplaintext ciphertext attack and is the most serious threat model Today we usually insist that our encryption algorithms provide security against chosen plaintext ciphertext attacks both because those attacks are practical in some settings and because we can it is feasible to provide good security even against this very powerful attack model However for this lecture we will focus primarily on security against chosen plaintext attack 2 One Time Pad The one time pad is a simple and
View Full Document
Unlocking...