CS 161 Fall 2005 1 Computer Security Joseph Tygar Vazirani Wagner Notes 9 Block Ciphers In symmetric encryption schemes Alice and Bob share a random key and use this single key to repeatedly exchange information securely despite the existence of an eavesdropping adversary Eve The block cipher is a fundamental building block in implementing a symmetric encryption scheme In a block cipher Alice and Bob share a k bit random key K and use this to encrypt an n bit message into an n bit ciphertext In mathematical notation this can be said as follows There is an encryption function E 0 1 k 0 1 n 0 1 n Once we fix the key K we get a function mapping n bits to n bits EK 0 1 n 0 1 n defined by EK M E K M EK is required to be a permutation on the n bit strings The inverse mapping of this permutation DK is the decryption algorithm DK EK M M The Data Encryption Standard DES is an example of a block cipher It was designed by IBM in 1974 in response to a request from NIST for an encryption algorithm that could be standardized DES uses a key length of k 56 and a block length of n 64 It was designed to have extremely fast VLSI implementations In terms of security DES has proved to be an impressively strong algorithm After all these years the best practical attack known is exhaustive key search a symmetry in the key structure can be used to halve the search space which requires 255 computations Thus DES behaves very differently than the one time pad Even given a very large number of plaintext ciphertext pairs there appears to be no effective way to decrypt any new ciphertexts The best such technique for DES is through linear cryptanalysis and requires 242 such chosen plaintext ciphertext pairs We will formalize these security properties of DES by saying that the function EK for a randomly chosen key K behaves like a random permutation on the n bit strings Formally we shall measure the security of the block cipher by performing the following experiment suppose that the adversary Eve is given a box which contains either I the block cipher with a random key or II a uniformly random permutation on n bits Eve is allowed T steps in which to play with the box to guess whether it type I or type II Define the advantage of Eve to be Adv Eve Pr Eve guesses I when the box is of type I Pr Eve guesses I when the box is of type II If the maximum advantage over all guessing strategies for the adversary is then we say that the block cipher is T secure For DES the above discussion says that if we want 1 we need T TDES 255 where TDES is the time required to run DES on T 55 a single input In general there is a tradeoff between T and and so we could say that TDES 2 In some sense log T is the effective key length of the block code We could also write a more detailed tradeoff in DES 2q42 terms of the number q of plaintext ciphertext pairs available In this case we would write T T 255 In 1998 NIST announced a competition for a new block cipher One motivation is that the block length of n 64 is just too short to guarantee security Another motivation is speed DES was really designed for hardware implementation and is quite slow in software In the summer of 2001 NIST announced their choice the Advanced Encryption Standard AES which was designed by Joan Daemen and Vincent Rijmen both from Belgium AES has a block length of n 128 bits and a key length k that may be either 128 192 or 256 bits CS 161 Fall 2005 Notes 9 1 2 Symmetric Encryption Schemes A symmetric encryption scheme allows Alice and Bob to privately exchange a sequence of messages in the presence of an eavesdropper Eve We will assume that Alice and Bob share a random secret key K How Alice and Bob managed to share a key without the adversary s knowledge is not going to be our concern here The encryption scheme consists of an encryption algorithm E that takes as input the key K and the plaintext message M 0 1 and outputs the ciphertext The decryption algorithm D takes as input the key and the ciphertext and reconstructs the plaintext message M In general the encryption algorithm builds upon a block cipher to accomplish two goals one is to show how to encrypt arbitrarily long messages using a fixed length block cipher The other is to make sure that if the same message is sent twice the ciphertext in the two transmissions is not the same The encryption algorithm to achieve these goals can either be randomized or stateful it either flips coins during its execution or its operation depends upon some state information The decryption algorithm is neither randomized nor stateful ECB Mode Electronic Code Book In this mode the plaintext M is simply broken into n bit blocks M1 Ml and each block is encoded using the block cipher Ci EK Mi The ciphertext is just a concatenation of these individual blocks C C1 C2 Cl This scheme is adequate for simple tasks such as encrypting PINs for cash machine systems However any redundancy in the blocks will show through and allow the eavesdropper to deduce information about the plaintext We will discuss this in more detail after formalizing the notion of the security of a symmetric encryption scheme below CBC Mode Cipher Block Chaining This is a popular mode for commercial applications A random n bit string the initial vector or IV is selected Define C 0 EK IV The ith encrypted block Ci EK Ci 1 Mi The ciphertext is the concatenation of the initial vector and these individual blocks C IV C1 C2 Cl The CBC mode does provide strong security guarantees on the privacy of the plaintext message This is formalized later in this lecture and explored further in the homework OFB Mode Output Feedback Mode In this mode the initial vector IV is repeatedly encrypted to obtain a set of keys Ki as follows K0 IV and Ki EK Ki 1 These keys Ki are now used as keys for a one time pad so that Ci Ki Mi The ciphertext is the concatenation of the initial vector and these individual blocks C IV C1 C2 Cl This scheme suffers from an important weakness the message is malleable i e suppose that the adversary happens to know that the j th block of the message specifies the amount of money being transferred to his account from the bank and is 100 Since he knows both M j and C j he can determine K j He can then substitute any n bit block in place of M j and get a new ciphertext where the 100 is replaced by any amount of his choice Counter Encryption One drawback of …
View Full Document
Unlocking...