Design and Analysis of Cryptographic Protocols Lecture 1 (Sept. 10) Scribe: Martine Coscia SYMMETRIC CIPHERS scenario: - Bob and Alice want to communicate with each other in a secure way using an insure communication line - A secret key K is communicated once between Bob and Alice outside the communication line e.g. phone - Bob encrypts messages he's sending using K - Alice decrypts messages she's receiving using K 1. ECB: ------- - Electronic Code Block - |K| << |P|, where K is the key and P is the plaintext - A Plaintext P is divided into K-size blocks. Encryption is applied to each of these blocks. The ciphertext C is obtained by piecing together the blocks. Danger: swapping the blocks still gives English messages if the size of K is known. - ciphertext C(i) = E(K)(P(i)) where i is the chosen block size 2. CBC: ------- - Cipher Block Chaining - C(i) = E(K) (exclusive-or(P(i),C(i-1))). IV is used as an initialization vector: C(1) = E(K) (exclusive-or(P(1),IV)). i is the chosen block size. - The encryption C conceals patterns in the plaintext (due to the exclusive-or) - Noisy channel errors are propagated in one block only - Allows for random access decryption with one block lookback - The last block of C is a good check sum since it contains information about all of the previous bits. - Need to keep track of code block length and padding (message may not be a multiple of the block size) - Possible IV values: constant, random, the key - If the goal is to encrypt the same plaintext many times, a random IV is desirable. If a constant IV is used, the adversary may find two equal encryptions 3. DES ------ - Data Encryption Standard (x 1977) - Developed by Don Coppersmith and NSA (National Security Agency) - A 56-bit key is permuted into 16 48-bit key masks (includes padding), labeled K(1) through K(16), together containing all of the key's bit information ("expansion permutation"). Security of the algorithm is provided by the 8 s-boxes. Each s-box accepts 6 bits of a 48-bit key mask. Each s-box is a two-dimensional pre-defined number table. Bits 1 and 6 provided by the 6-bit key mask portion correspond to the row of an s-box, bits 2 through 5 correspond to the column of an s-box. - Theoretically there are 2**56 key values; practically there are 2**55 due to the complement - Plaintext P is divided into 64-bit strings and an IP (initial permutation) is applied to the 64-bit string. Initially, the 64-bit string is split into two 32-bit pieces, labeled L(0) and R(0). For i=1 .. 16 , R(i) = exclusive-or(L(i-1), f(R(i-1),K(i))) and L(i) = R(i-1). Last step: C = IP(concatenate(L(16),R(16)). - Decryption is obtained by reversing the order of applying the 16 key permutations. - DES is known to be secure and is used commercially e.g. EDI. - speed: 1 Mb/sec ------------------------------------------------------------------------------- ONE-WAY HASH FUNCTION - Y = f(X), where X is arbitrary and Y is fixed length - Properties: X cannot be computed given Y No collisions: there is no X, X' s.t. Y = f(X) and Y = f(X') - Examples: MD5 (message digest 5), SHA (secure hash algorithm) - Applications: S/KEY, digital time stamp ------------------------------------------------------------------------------- MAC FUNCTIONS - Message Authentication Code (MAC) - Example: DES-CBC. The last block of the encrypted message C = CBC(K)((M)) serves as a checksum. If decryption of C using K results in M, the receiver can authenticate the sender. ------------------------------------------------------------------------------- PUBLIC KEYS - Each user has a pair of keys, K+ and K- , public and private respectively, which are the inverses of each other. E(K-) ((E(K+)((M)))) = M. - Typically a message M is encrypted with the sender's private key. The receiver must somehow get hold of the sender's public key to decrypt the message. - Public keys are communicated using an insecure network. Depending on the requirement, there may be a need to authenticate the user who's sending the request for public key, i.e. certified authority (CA) public key.