CS 161 Computer SecurityFall 2005 Joseph/Tygar/Vazirani/Wagner Notes 91 Block Ciphers:In symmetric encryption schemes, Alice and Bob share a random key and use this single key to repeatedlyexchange information securely despite the existence of an eavesdropping adversary, Eve. The block cipheris 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 messageinto an n bit ciphertext. In mathematical notation this can be said as follows. There is an encryptionfunction 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}ndefined by EK(M) = E(K,M). EKis required to be a permutation on the n bit strings.The inverse mapping of this permutation DKis 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 inresponse 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 VLSIimplementations. In terms of security, DES has proved to be an impressively strong algorithm. After allthese years, the best practical attack known is exhaustive key search (a symmetry in the key structure can beused to halve the search space) which requires 255computations. Thus DES behaves very differently than theone-time pad. Even given a very large number of plaintext, ciphertext pairs, there appears to be no effectiveway to decrypt any new ciphertexts. The best such technique for DES is through linear cryptanalysis andrequires 242such chosen plaintext-ciphertext pairs. We will formalize these security properties of DES bysaying that the function EKfor a randomly chosen key K “behaves like” a random permutation on the n bitstrings.Formally, we shall measure the security of the block cipher by performing the following experiment: sup-pose that the adversary, Eve, is given a box which contains either (I) the block cipher with a random keyor (II) a uniformly random permutation on n bits. Eve is allowed T steps in which to play with the box toguess whether it type I or type II. Define the advantage of Eve to be Adv(Eve) = Pr[Eve guesses I when thebox is of type I] − Pr[Eve guesses I when the box is of type II]. If the maximum advantage over all guessingstrategies for the adversary isε, then we say that the block cipher is (T,ε) secure. For DES, the abovediscussion says that if we wantε= 1 we need T/TDES≥ 255, where TDESis the time required to run DES ona single input. In general there is a tradeoff between T andε, and so we could say thatTTDESε≥ 255. In somesense log T/εis the effective key length of the block code. We could also write a more detailed tradeoff interms of the number q of plaintext-ciphertext pairs available. In this case we would write:ε≤T/TDES255+q242.In 1998 NIST announced a competition for a new block cipher. One motivation is that the block lengthof n = 64 is just too short to guarantee security. Another motivation is speed - DES was really designedfor hardware implementation, and is quite slow in software. In the summer of 2001 NIST announcedtheir choice - the Advanced Encryption Standard (AES) which was designed by Joan Daemen and VincentRijmen, both from Belgium. AES has a block length of n = 128 bits and a key length k that may be either128, 192 or 256 bits.CS 161, Fall 2005, Notes 9 12 Symmetric Encryption Schemes:A symmetric encryption scheme allows Alice and Bob to privately exchange a sequence of messages in thepresence of an eavesdropper Eve. We will assume that Alice and Bob share a random secret key K. HowAlice and Bob managed to share a key without the adversary’s knowledge is not going to be our concernhere. The encryption scheme consists of an encryption algorithm E that takes as input the key K and theplaintext message M ∈ {0,1}∗, and outputs the ciphertext. The decryption algorithm D takes as input thekey and the ciphertext and reconstructs the plaintext message M. In general the encryption algorithm buildsupon a block cipher to accomplish two goals: one is to show how to encrypt arbitrarily long messages usinga fixed length block cipher. The other is to make sure that if the same message is sent twice, the ciphertextin the two transmissions is not the same. The encryption algorithm to achieve these goals can either berandomized or stateful - it either flips coins during its execution, or its operation depends upon some stateinformation. 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 blocksM1,...Ml, and each block is encoded using the block cipher: Ci= EK(Mi). The ciphertext is just a con-catenation of these individual blocks: C = C1·C2···Cl. This scheme is adequate for simple tasks such asencrypting PINs for cash machine systems. However any redundancy in the blocks will show through andallow the eavesdropper to deduce information about the plaintext. We will discuss this in more detail afterformalizing 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 randomn bit string, the initial vector or IV is selected. Define C(0) = EK(IV). The ithencrypted 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 plaintextmessage. 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 aset of keys Kias follows: K0= IV and Ki= EK(Ki−1). These keys Kiare now used as keys for a one-timepad, 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 jthblock of the message specifies the amount of moneybeing transferred to his account from the bank and is 100. Since he knows both Mjand Cj, he can determineKj. He can then substitute any n bit block in place of Mjand get a new ciphertext where the 100 is
View Full Document
Unlocking...