Current Concepts and Issues in Cryptography and Security: An Overview Assistant Prof. Sarah Mocas Portland State University Background  Underlying security is cryptography. Secure cryptographic algorithms do not imply se- cure implementations using these algorithms!  Security often rests in: (1) the security in communication protocols using cryptographic algorithms, (2) the security in key distribution proto- cols. Cryptographic Services The following properties are \services" which may be provided by a set of cryptographic func- tions used in conjunction with protocols and keys. 1 Con dentiality is the property of commu- nicating such that the intended recipients know what was sent but unintended parties can not determine what was sent. Encryption is a mechanism used to provide con dentiality. Steganography is the art of hiding a secret message within a larger public message. This provides a service closely related to con - dentiality which is usually associated with digital watermarking or covert channels. Cryptographic Services 2 Authentication is the property of knowing that the data received is the same as the data that was sent and that the claimed sender is in fact the actual sender. 3 Integrity is the property of ensuring that the data is transmitted from source to destina- tion without undetected alteration. (This is a \cryptographic checksum".) Cryptographic Services 4 Digital Signatures, like Authentication, pro- vide the property of knowing that the data received is the same as the data that was sent and that the claimed sender is in fact the actual sender. In addition the signed message can only have been created by the signer and the signer can not disavow a sig- nature. In authentication: If Alice and Bob share a secret key K and Alice sends Bob a message M that has been \authenticated" using K then the message could have been created by either Alice or Bob (since they both own K). For a signed message: If Alice sends Bob a message M that has been \signed" by Alice using a key K A then the message could only have been created by Alice. Con dentiality 1. Encryption is the process of disguising a plain- text message P and producing ciphertext C, (using a secret key K): E K (P) = C. 2. Decryption is the process of transforming ci- phertext into plaintext: DK (C) = P . 3. DK2 (E K1 (P)) = P , where K1;K2 are keys. Plaintext ! Ciphertext ! Plaintext Encryption K1 Decryption K2 E K1 (P) = C D K2 (C) = P Con dentiality There are two standard types of cryptosystems. (1) Symmetric or Secret Key Cryptosystems: K1 and K2 are secret. Usually K1 = K2. (2) Public-key Cryptosystems: K1 is public. K2 is secret or private. K1 6= K2. Plaintext ! Ciphertext ! Plaintext Encryption K1 Decryption K2 E K1 (P) = C D K2 (C) = P Con dentiality Symmetric Key Cryptography 1. The decryption key can be calculated from the encryption key. Often the same key. 2. Key distribution is harder. 3. Encryption is usually fast. 4. Example: Block encryption algorithms: a xed key used to encrypt/decrypt a block of bits, usually 64 bits or 128 bits. DES Con dentiality Public Key Cryptography (1975) 1. The key used for decryption is not the same as the key used for encryption, Ke 6= Kd. 2. The decryption key can NOT be calculated from the encryption key in a reasonable amount of time. 3. The encryption key can be made public. encryption key  public key decryption key  private key It is still true that D Kd (E Ke (P)) = P . 4. Key distribution is easier. 5. Encryption is usually slower. Notions of Security Computational security - can not be broken with current or future computational resources. BIG CLAIM. Typically can not prove computationally secure but show provably secure. A cryptosystem is provably secure if it is proved that breaking it is as hard as solving another problem which is believed to be hard. Typically a problem in NP (class of problems solvable in nondeterministic polynomial time). Example: Factoring large numbers is in NP and is used as the base of some public key systems. Unconditional security (Shannon) - can not be broken given in nite resource. Example: One- time Pad. A \strong" cryptosystem may still be cracked if poorly used! Notions of Security How long should it take to decrypt a message if all possible keys are checked (brute force at- tack)? How much time is too much time? 2 14 years the next Ice Age 2 30 years age of the planet 2 170 atoms in the planet 2 190 atoms in the sun Most cryptosystems use keys that are length 64 or 128. If it requires 2 128 operations to break an algorithm and 1 million operations per second can be done on a computer and you use 1 million parallel processors then the time is greater then 10 19 . But 2 30 is only about 10 9 ! Symmetric Key - Classical Cryptography Simple Substitution Let P be the plaintext alphabet; K be the key alphabet and C be the cipher text alphabet. One character in P is replaced via a xed algo- rithm (and key) by another character in C. Example: Shift Cipher / Caesar Cipher P = C = K = f A, B, : : : Z g Let letters be represented as numbers so A is 0, B is 1, : : :, Z is 25. Let x be the numeric representation of a letter. E K (x) = (x +K) mod 26 DK (y) = (y K) mod 26 So we are shifting K letters to the right to en- crypt and reversing the shift to decrypt. How hard is it to break this cipher? Symmetric Key - Classical Cryptography Example: Caesar Cipher Encrypt CRYPTO with K = D (so K = 3) E 3 (C) = (2 + 3) mod 26 = 5 = F E 3 (R) = (17 + 3) mod 26 = 20 = U E 3 (Y ) = (24 + 3) mod 26 = 27 mod 26 = 1 which is B E 3 (P) = S, E(T) = W , E(O) = R The cipher text is FUBSWR. Decrypt FUBSWR with K = 3 D 3 (F) = (5 3) mod 26 = 2 = C D 3 (U) = (20 3) mod 26 = 17 = R D 3 (Y ) = (1 3) mod 26 so we need a rule for negative numbers (1 3) mod 26 = 26 2 = 24 which is Y etc. If c < k and D K (c) then D K (c) = 26 (k c). Symmetric Key - Classical Cryptography Example: One-time Pad (1917) The key is a large non-repeating random string. The sender and the receiver both have key pads. Keys are used only once. If the message and the key are both binary strings then the ciphertext is the XOR of the key bits and the message bits. P = HIDE H is 7, I is 8, D is 3, E is 4 = 7834 = 0111100000110100 in binary KEY = 10110111100101011101 : : : P = 0111100000110100 C = 1100111110100001 To decrypt just XOR K and C. Symmetric Key - Classical Cryptography One-time Pad If the key is generated randomly then the ci- phertext will also be a random string! This means NO information about the plaintext can be retrieved from the ciphertext! All possible plaintext messages are equally likely. This is the ONLY cryptosystem that is com- monly known to be unconditionally secure. Drawbacks: (1) distributing keys is hard (2) keys are long (3) on computers - synchronization Uses: Ultrasecure low-bandwidth channels. Maybe the Soviet Union/US hot line. Symmetric Key - Modern Cryptography The most commonly used symmetric system is DES (Data Encryption Standard) which en- crypts 64 bit blocks of plaintext at a time. A Little History on DES  DES evolved from work done at IBM in the early 1970s (an earlier related algorithm is called Lucifer). At the request of what is now the NIST (National Institute of Stan- dards), the NSA evaluated/modi ed the al- gorithm developed by IBM. This is DES. The NSA (National Security Agency) is the oĆcial security agency of the US. They crypt- analyze world wide communications and de- velop cryptosystems. Symmetric Key - Modern Cryptography More History on DES  NIST published DES in 1975 (20 years ago)!! NIST made DES the federal standard for all unclassi ed government communications (1977).  ANSI (American National Standards Insti- tute) approved DES as the private sector standard (1981). EVERYONE GOT ON BOARD.  DES is reviewed every 5 years. It is gen- erally agreed that DES has exceeded it's useful lifetime. The problem is that there has been no good alternative cipher pro- posed that is agreeable to both the NSA and the public. A recent cipher proposed by the NSA is the Skipjack algorithm which is used in the Clipper Chip. Skipjack is no longer in consideration. Symmetric Key - Modern Cryptography Cracking DES To prove the insecurity of DES, EFF built the rst unclassi ed hardware for cracking messages encrypted with it. In July 1998 the EFF DES Cracker, which was built for less than $250,000, easily won RSA Laboratory's "DES Challenge II" contest and a $10,000 cash prize. It took the machine less than 3 days to complete the challenge, shattering the previous record of 39 days set by a massive network of tens of thou- sands of computers. More information is available online at: http://www.e .org/descracker/ Symmetric Key - Modern Cryptography A DES Replacement  A process to develop a Federal Informa- tion Processing Standard (FIPS) for Ad- vanced Encryption Standard (AES) spec- ifying an Advanced Encryption Algorithm (AEA) has been initiated by NIST. It is in- tended that the AES will specify an unclassi- ed, publicly-disclosed encryption algorithm available royalty-free worldwide, that is ca- pable of protecting sensitive government in- formation well into the next century. It is hoped that this standard will be as widely accepted as the Data Encryption Standard (DES) in the private and public sectors.  Advanced Encryption Standard (AES) De- velopment E ort: http://csrc.nist.gov/encryption/aes/aes home.htm  The winning algorithm will be announced August 2000. Symmetric Key - Modern Cryptography AES Candidate Algorithms CAST-256 (Entrust Technologies, Inc.), CRYPTON (Future Systems, Inc.), DEAL (Richard Outerbridge, Lars Knudsen), DFC (CNRS Centre National pour la Recherche Scienti que), E2 (NTT Nippon Telegraph and Telephone Corp.), FROG (TecApro Internacional S.A), HPC (Rich Schroeppel), LOKI97 (Lawrie Brown, Josef Pieprzyk, Jen- nifer Seberry), MAGENTA (Deutsche Telekom AG), MARS (IBM), RC6 (RSA Inc.), RIJNDAEL (Joan Daemen, Vincent Rijmen), SAFER (Cylink Corporation), SERPENT (Ross Anderson, Eli Biham, Lars Knudsen), TWOFISH (Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Fer- guson) Symmetric Key - Modern Cryptography Triple DES or EDE * Two keys are used K1 and K2. EDE is E K1 (D K2 (E K1 (P ))) = C and DK1 (E K2 (D K1 (C))) = P . * Current proposed secure use of DES is as Triple DES. Advantage: no new crypto sys- tem is needed to upgrade. * Only a brute force attack, which requires nding both secret keys or searching over 2 112 possible strings, is know against EDE. * EDE is often used in CBC mode to get a chained encrypted message. CBC mode is used on the outside to preserve it's error correcting properties - self-synchronizing. * Applications for DES Banking transactions, PINs - transactions over the ATM machines, Department of Energy, Dept of Justice, Fed- eral Reserve System Symmetric Key - Modern Cryptography DES (and many of the AES candidates) is a combination of substitutions and permutations.  A substitution speci es for each of the 2 k possible values of the input, the k output bits. This is assuming that k bits are en- crypted at a time and that a binary alpha- bet is used. In the Ceaser cipher the size of the alpha- bet is 26 and one character was encrypted at a time so there are 26 1 substitutions to specify. DES encrypts 64 bit blocks of binary data so just considering substitution gives 2 64 sub- stitutions - too many to check.  A permutation speci es, for each of the k input bits, the output position to which it goes. Also called transposition. Symmetric Key - Modern Cryptography Overview of DES * Symmetric block cipher which encrypts 64 bit blocks to produce 64 bits of ciphertext. * The key length is 56 bits (that's funny). The key is used to generate sixteen 48-bit per-round keys one key for each round. * Encrypt and decrypt use the same algorithm (with per-round keys reversed). So it is no harder to decrypt then it is to encrypt. * The security rests with the secret key. * DES uses substitution and permutation of the text combined with the key. One set of substitutions and permutations is called a round. DES has 16 rounds that are repeated on 1 block. * DES is easy/fast to implement. Symmetric Key - Modern Cryptography Overview of the DES Algorithm Input: 64 bit plaintext, x; 64 bit key, k. 1. Perform an initial permutation, IP(x) = x 0 . Then x 0 is divided into two halves, 32 bit left half L 0 and 32 bit right half R 0 . 2. There is an encryption function that is re- peated 16 times. Each time that it is re- peated the left 32 bits are XORed with the output of a function f(R 0 ; K 1 ) (inputs are the right 32 bits and a key) and become the right 32 bits of the output. The right 32 bits from the start of the round be- come the left 32 bits of the output. So round(L 0 R 0 ) = R 0 (L 0  f(R 0 ; K 1 )) = L 1 R 1 . The key, K 1 is a key generated from the secret key k. K 1 is 48 bits long. 3. Perform an inverse permutation, IP 1 (R 16 L 16 ) = y. This is the inverse of the permutation in step 1. y is the ciphertext. Initial and Final Permutations (IP and IP 1 ) These permutations do not increase security! Anyone can reverse the permutations since they do not depend on the secret key. The table means that bit 58 of the input goes to position 1 in the output, bit 50 of the input goes to position 2 in the output, bit 42 of the input goes to position 3 in the output, etc. Initial Permutation (IP) 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 The inverse permutation IP 1 is done as the very last step of DES. It reverses the e ect of this permutation. Example Inverse Permutation The following gives an example of a much smaller permutation (over strings length 9) and the in- verse permutation. The string abcdefghi permutes to ghdecba. The string ghdecba inverts to abcdefghi. Permutation: Inverse: 9 8 7 6 9 7 5 6 1 8 4 5 3 4 2 3 2 1 Generating Per-round Keys The key is given as a 64 bit quantity but every 8 th bit is not used and can be a parity check on the other 7 bits. So the real length of the key is 56 bits. First the key is divided into two 28 bit halves C 0 and D 0 with a xed permutation PC-1. C 0 j D 0 57 49 41 33 25 17 09 j 63 55 47 39 31 23 15 01 58 50 42 34 26 18 j 07 62 54 46 38 30 22 etc. j etc. (No bit 8, 16 , 24, ..., 64) This permutation and the nal permutation on the key also have no security value. So the secret key is now in two pieces C 0 and D 0 . Each piece is now left shifted. Generating Per-round Keys Let C i = LeftShift(C i 1 ), D i = LeftShift(D i 1 ), The shifting is done 16 times . There are 16 rounds of DES to encrypt one 64 bit block. Each round uses a di erent per-round key. Each per-round key is gotten after a shift of C i and D i . The shift is not the same every time. Left Shift Table Round Number: 1 2 3 4 5 6 7 8 Amount Shifted: 1 1 2 2 2 2 2 2 Round Number: 9 10 11 12 13 14 15 16 Amount Shifted: 1 2 2 2 2 2 2 1 After a left shift C i and D i are permuted to create one per-round key of length 48 bits. The 2 pieces (before permutation) are also used to make the next per-round key. Generating Per-round Keys Note: jC i D i j = 56 but jK i j = 48 so some bits are not used. No bit 9, 18, 22 and some more. There is a second permutation PC-2 which re- duces the size of the key. This is called a com- pression permutation (on page 76). Because of the shifting, a di erent subset of key bits is used in each per-round key. Each bit of the secret key K is used in about 14 of the per-round keys. Pages 76-78 list which bit from the initial key k are used in each per-round key. Some initial secret keys are called weak keys because they do not produce good per-round keys. Can you give 3 weak keys? Size of the keyspace is 2 56 . Mangler Function f(R i ; K i+1 )) - The Guts The input to this function is the right side R i , 32 bits, and one per-round key, 48 bits. First R is expanded to 48 bits via an expansion permutation of R that uses some bits more then once. By allowing one bit to a ect two substi- tutions, the dependency of the output bits on the input bits spreads faster. This is called an avalanche e ect. For every 4 bits the rst and fourth bits are used twice. Input bit 3 becomes output bit 4. Expansion Permutation: 32 01 02 03 04 05 04 05 06 07 08 09 08 09 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 01 Next the per-round subkey is XORed with the result of the expansion permutation. This string is divided into 8 pieces each 6 bits long. S Boxes Each of the 6 bit length strings is input to a S-box (Substitution box). There are 8 S-boxes and 48/6 = 8 strings of 6 bits. Each S-box gets a 6 bit input and gives a 4 bit output. These are compression substitutions. There are ex- actly 4 di erent 6 bit inputs that map to each 4 bit output. S Box 1 14 04 13 01 02 15 11 08 03 19 06 12 05 09 0 07 00 15 07 04 14 02 13 01 10 06 12 11 09 05 3 08 04 01 14 08 13 06 02 11 15 12 09 07 03 10 5 00 15 12 08 02 04 09 01 07 05 11 03 14 10 00 6 13 Each entry in the S-box is read as 4 bits, for example 1 is 0001. Rows and column are numbered starting at 0. S Boxes The 6 input bits specify which row and col- umn gives the output. Idea: Say that the input is b 1 b 2 b 3 b 4 b 5 b 6 . Concatenate b 1 b 6 to get a 2 bit number. This is the row number. Concatenate b 2 b 3 b 4 b 5 to get a 4 bit number. This is the column number. Example: Given input 110010 pick row 10 which is the second row and column 1001 which is column 9. The output is 12 (1100 in binary). Guts continued The 4 bits output form each of the 8 eight S- boxes are concatenated together to make a 32 bit string. This string then gets one more per- mutation (permutation P page 75). This helps security because the output bits from one S- box of the current round will then a ect the output of a di erent S-box on the next round (remember 16 rounds). This permutation gets 32 bits as input and gives 32 bits as output. The S-boxes are nonlinear and give DES it's cryptographic strength. The 16 rounds are used as a product cipher. What cipher have we seen that would not be any more secure if it was repeated a number of times then if it is done once? Security * S-boxes give DES it's security but S-boxes are mysterious! Swapping the order of S- boxes has been shown to make DES less secure. * Properties designed into S-boxes: (0) Each row of an S-box permutes the in- tegers 1 : : : 15. (1) No S-box is a linear or aĆne function. (2) Each input bit to an S-box a ects 2 output bits of the S-box. (3) There are on average as many 1's as 0's in the output of an S-box, assuming a random key. * There are some weak keys (all 1's; all 0's; 1/2 1's and 1/2 0's) but the list is small, only 16 such keys where C and D are all 1's; all 0's or alternating 1's and 0's. The probability of generating one of these is 16 in 2 56 . Public Key Cryptography DiĆe-Hellman Key Agreement Protocol 1976 DiĆe-Hellman protocol predates RSA. Not a cryptosystem but a key exchange protocol. Two people agree on a secret key by the ex- change of public messages. Cleaver! A and B publicly pick 2 large integers p, g, g < p. 1 A chooses random number x and computes X = g x mod p. 2 B chooses random number y and computes Y = g y mod p. 3 A sends X to B. B sends Y to A (x and y are secret). 4 A computes K = Y x mod p. 5 B computes K 0 = X y mod p. Claim: K = K 0 = g xy mod p. K is the secret key. Proof: K = Y x mod p = (g y mod p) x mod p = g yx mod p. Same idea works for K 0 . What about authentication? Public Key Cryptography DiĆe-Hellman Key Agreement Not just any g and p will work. * p needs to be a prime number and (p 1)=2 should also be prime. This type of prime is called a strong prime. * g should be a primitive element of p. This means that g x mod p will cycle over all of the numbers from 0 to p 1. * p, x and y should be large, at least 512 bits. * The security is based on the notion that computing discrete logarithms in a nite eld is hard. So computing log g X mod p to nd x is assumed to be hard. But computing modular exponentiation is easy. * f(x) = g x mod n is a CANDIDATE for a one- way function. Public Key Cryptography Attack Against DiĆe-Hellman A and B publicly pick 2 large integers p, g, g < p. 1 A chooses x and computes X = g x mod p. 2 B chooses y and computes Y = g y mod p. 3 A sends X to B. M intercepts X. M chooses z and computes Z = g z mod p. M sends Z to B. B sends Y to A. M intercepts Y . M sends Z to A. 4 A computes K = Z x mod p (g zx ). 5 B computes K 0 = Z y mod p (g zy ). M computes K = Y z mod p (g xz ). M computes K 0 = X z mod p (g xz ). Now if M intercepts ALL of the communica- tions between A and B he can read everything without A and B even knowing. This occurs because there is no authentication in DiĆe- Hellman. This is called a man-in-the-middle at- tack. To x, authenticate messages. Public Key Cryptography Encryption using Public Key Cryptography RSA (Rivest, Shamir, Adleman) Key Generation: Creating a public/private key pair. 1 Choose random prime numbers p and q of length 200 digits (more like 512 bits). 2 Compute n = p  q. 3 Choose a random numbers e such that gcd(e; (p 1)(q 1)) = 1. 4 Compute d = e 1 mod (p 1)(q 1). (Find d such that e  d  1 mod (p 1)(q 1)). 5 Publish n and e. Keep d private. Throw out p; q. The public and private keys are a function of 2 large primes. In order to break the system ( nd d given n and e) it would be good enough to be able to factor n and nd the primes. Public Key Cryptography RSA - Con dentiality Public key (e; n) is in a public directory. Encryption 1 Divide the message m into blocks such that each block represents a 200-digit number. m i is a block. 2 Compute and send c i = m e i mod n. Decryption 1 Compute and send m i = c d i mod n. If a is a constant then this works since c d  (m e ) d  m ed  m a(p 1)(q 1) m  1  m  m mod n Public Key Cryptography RSA - Digital Signature Public key (e; n) is in a public directory. Sign a message: 1 Divide the message m into blocks such that the each block represents a 200-digit number. m i is a block. 2 Compute s i = m d i mod n and send (s i ; m i ). Verify a signature.: Get the sender's public key from the directory. 1 Compute n i = s e i mod n. 2 Check that m i = n i . A common use of a digital signature is to sign the message digest (hash) of a message (128 bits). This is faster then signing the whole mes- sage. Signatures are not as fast as algorithms like MD5 and DES. Integrity Cryptographic Hash Functions A cryptographic hash function or message digest function is typically used to supply integrity; as a part of a scheme which supplies authentica- tion or in a signature scheme. In a signature scheme a hash or digest of a message is signed. A cryptographic hash function is a type of one- way function. A message digest function is cryptographically secure if it is computationally infeasible to (1) nd the message given a hash and (2) nd two messages with the same hash. What is the problem with breaking a message up into blocks and signing each block? Integrity Uses of Message Digests  Fingerprint a document. Keep a hash of a document so that changes can be detected.  Authentication: Assume that A and B share a secret key K and messages digest MD(). A generates r A (random) and sends it to B. B sends MD(Kjr A ) to A A computes MD(Kjr A ) and check that this is what B sent. A now believes that the communications is with B. This is also repeated in the reverse direction.  Generating a MIC (Message Integrity Code): Two keyed message digests. Solution 1: A sends MD(P jK); P , to B. Solution 2: A sends half of the bits of MD(P jK) plus P to B. Either way B can compute MD(P jK) and check to see that P was not changed. Integrity MD5 - Rivset MD5 is a commonly used cryptographic has al- gorithm. In practice hash algorithms are used in a more complex way. This is an example of how MD5 is used in network security protocols (IPSEC). pad1 = 0x36 repeated 48 times. pad2 = 0x5C repeated 48 times. HMAC-MD5 is MD5(K; pad2; MD5(K; pad1; text)). K is a 16 byte random key string. The NIST proposed message digest function is SHA (Secure Hash Function) is based on MD4 but is considered to be more secure then both MD4 and MD5. Digital Signature Schemes A digital signature scheme is a method of elec- tronically signing a message. A signature scheme has 2 poly-time algorithms: one to sign messages (private - owned by signer), sig(m) = s one to verify signatures (public), ver(m; s) = True or False.  A message x is sent in the clear with the signature s. The goal is NOT con dential- ity of the message but is to associate the message with the senders identity.  The cryptographic service provided by a Sig- nature is stronger then that provided by Au- thentication. A signed message can only be produced by one entity.  Needed for Internet commerce. Digital Signature Schemes A signature scheme is (P; A; K; S:V) so that 1. P is a nite set of possible messages. 2. A is a nite set of possible signatures, sig(x) = s. 3. K is a nite set of possible keys, sig K (x) = s. 4. For each K 2 K there is a signing algo- rithm sig K : P ! A and a veri cation algorithm ver K : P  A ! (T rue; F alse) and for every mes- sage x 2 P and signature s 2 A: ver(x; s) = ( T rue if s = sig K (x) F alse if s 6= sig K (x) Digital Signature Schemes Signatures - Security A signature is secure under the following con- ditions. * Signing something does not give away the secret/private key. * Nobody can generate a signature for a mes- sage unless they own the private key. It is computationally not possible to do. * Nobody can generate a message that matches a given signature if then don't own the pri- vate key. Forgery is not possible. * Nobody should be able to modify a signed message without wreaking the signature. Ev- ery bit of the message should be \covered" by the signature. Digital Signature Schemes RSA Digital Signature Anyone can get the public key (e; n) from the public directory. In this case, (e; n) is used for the veri cation algorithm. Sign a message: 1 Divide the message m into blocks such that the each block represents a 200-digit number. m i is a block. 2 Compute s i = m d i mod n = sig d (m i ) send (s i ; m i ). Verify a signature.: Get the sender's public key from the directory. 1 Compute n i = s e i mod n. 2 Check that m i = n i . The value of this comparison is ver e (s i ; m i ). Digital Signature Schemes Signing Encrypted Messages A has public-key a v for verifying signatures. B has public-key be for encrypting messages. Protocol 1 A signs message x, s = siga s (x) A encrypts (x; s) with B's public-key, y = E b e ((x; s)) A sends B y 2 B decrypts y as (i; j) = D b d (y) B veri es A's signature using A's public-key, verav (i; j). If verav (i; j) = True then B knows that y MUST be from A. What if A rst encrypts and then signs? A encrypts x with B's public-key, y = E be (x) A signs message y, s = siga s (y) A sends B (y; s) Then M could intercept (y; s) and instead com- pute z = sigms (y) to sign y. Now M sends (y; z) to B. B may believe that M sent the message y. M can sign y even if he does not know the plaintext. Timestamps A timestamp provides proof that a message was signed at a certain time. If the key used to sign messages is gotten then all messages before the key was known are okay. Idea: If your credit card is lost today, the credit card company assumes that all charges before today were made by you. Protocol: Let TSS be a trusted Timestamp Service. B computes z = h(x) and y = sig K B (z) and sends (z; y) to TSS. TSS signs (z; y; D), D is the date so sig K TSS (z; y; D). TSS can send this to B or can hold it. This is good if the TSS is trusted. Key Distribution  Key distribution is a method that lets 1 party pick a secret key and then transmit it to 1 (or more) other users. Example: A Key Distribution Center (KDC).  Key agreement is a protocol that lets 2 (or more) users establish a shared secret key via the communication of public values. The nal key is determined by both users. Example: DiĆe-Hellman protocol.  Trusted Authority (TA) is a mutually trusted party that may be part of a protocol or key distribution scheme. Example: Certi cate Authority or KDC. Key Distribution So far we have seen secret key (symmetric) ciphers and public key ciphers and we have fudged over the issue of how users got their keys (with the exception of DiĆe-Hellman). Now we will look at methods for getting keys over a network. * Let's divide keys into two kinds: (1) Data Keys or Session Keys which are used to encrypt/decrypt large amounts of data (say with DES) and (2) Key-Encryption Keys which are used to encrypt/decrypt other keys (such as data keys) for distribution . * Data keys are used to encrypt lots of in- formation and so they are changed often. Key-encryption keys are only used to en- crypt and distribute other keys so they are changed less often. Key Distribution * The issue is how to distribute key-encryption keys. Possibilities: (1) manually (2) dis- tributed - split and send over several di er- ent channels. * Do NOT send a new key-encryption key over a network encrypted via the key that it is going to replace. * Scalability In a network, for n users of a symmetric key system each user would need n 1 key- encryption keys and there would be a total of n(n 1)=2 key exchanges required for ev- eryone to get data keys with every other user. Too much. Public-key systems are scalable when symmetric systems are not. Key Distribution Active Adversary An active adversary can modify a protocol by adding, deleting or modifying messages. Goals of an active adversary are:  To fool users A and B into accepting an \in- valid" key as valid. An invalid key might be an old key (that the adversary can decrypt) or a key picked by the adversary (basic man- in-the-middle against DiĆe-Hellman).  To make A and B believe that they have exchanged a key when they have not. Key Distribution KDCs Solution: Set up one trusted node that shares a key-exchange key with each user of the system. This is called a Key Distribution Center or KDC. The KDC can then give out, on request, data keys which are encrypted with key-distribution keys. This model is used for symmetric crypto systems. * Advantages: (1) when a new node is added only the KDC needs to get a new key for it; (2) users only need one key-distribution key. * Disadvantages: (1) if the KDC is compromised the whole network is not secure; (2) if the KDC goes down then nobody can start a new secure session; (3) the KDC is a performance bottleneck. Key Distribution Kerberos Kerberos is a secret key based service for pro- viding authentication over a network (designed at MIT). It's used to give a user legal access to remote resources securely. Assume that DES keys are shared between each user and a TA. DES will use CBC mode. The rst steps transmit a secret key. The last steps provide con rmation. U and V are convinced that they share the same key. This is done by using the new session key K to encrypt a known quantity. Timestamps & Lifetimes prevent an adversary from replaying messages - replay prevention. Kerberos needs synchronized clocks for times. There is no formal proof that Kerberos is se- cure - this is common. Key Distribution DiĆe-Hellman Predistribution of Keys This system is computationally secure (depends on Discrete Log Problem).  ( ; p) are public, is a primitive element for prime p.  Each User: 1. ID(U) is a users ID for U. 2. au is a secret exponent for U 3. bu = au mod p is a public value for U  TA (Trusted Authority): 1. private signing algorithm sig TA 2. public veri cation algorithm ver TA - each user has this 3. Assume data is hashed before signing so sig TA (ID(U); bu) might be sig TA (MD5(ID(U); bu))  Certi cate for each user: C(U) = (ID(U); bu ; sig TA (ID(U); bu)). Certi cates are stored in a public directory. TA doesn't know au . Key Distribution DiĆe-Hellman Predistribution of Keys If U wants to send V a message m, U needs to get V 's certi cate from the public directory, compute K U;V = (bv) au mod p, encrypt E K U;V (m) = c, send V either (c; U) or (c; C(U)). V can use U's certi cate to compute K U;V = (bu) av mod p and decrypt by D K U;V (c) = m. If U sends (c; C(U)) then V does not have to get U's certi cate. Typically, certi cates also need to include infor- mation like, an expiration time, the algorithms to use for the values like bu , etc. This system is predistribution because there is no need for an exchange between U and V be- fore encryption can be done. Key Distribution Security DiĆe-Hellman Problem Problem: Given I = (p; ; ; p is a prime is a primitive element for p ; 2 Zp Objective: Compute log mod p = log mod p log and log are the secret exponents. Fact: DiĆe-Hellman Key Predistribution is secure against passive attach i the DiĆe-Hellman Problem is intractible. Key Distribution Certi cate Authorities (CAs) * In a symmetric system a Key Distribution Center, KDC, is used to help pass session keys but in a public key system the trusted node is called a Certi cation Authority (CA). A CA generates certi cates which are signed messages that contain a name and a corre- sponding public key, example: E KCAd (A; KAe), where KCAd is the private (signing) key of CA and KAe is A's public (encoding) key. * So a signed message, E KCAd (M), from the CA can be read by anyone using CA's public key, KCAe, and since every other user of the system trusts CA all users will believe that the message is correct. * All nodes must have the CA'c public key in advance. So this is one key that must be passed securely o line. Key Distribution CAs * T is going to be the CA. His private key, used for signing messages is KCAd. His pub- lic key, KCAe, which everyone has, can be used to verify his signature and read any message that T signed. * The users are A, B and C. Each user has a public, private key pair hKAe; KAdi where T keeps the public key KAe for each user. In these protocols the private key is gen- eral being used to sign a message (which gives authentication) rather then to decrypt a message. The public key is used to verify a signature not to encrypt. * Any signed message sent over a network can be read and veri ed by anyone who can get the public key of the person who signed the message. Key Distribution CAs * Advantages: (1) when a new node is added, only the CA needs to get a new key. * Advantages over Key Distribution Center: (1) the CA does not need to be online, so it is less prone to attack over the network; (2) it can be simpler then a KDC; (3) if the CA goes down then only new users can not be added; (4) certi cates, if used correctly, are less security-sensitive (they can be deleted but not modi ed or replaced); (5) A dishonest CA can not decrypt con- versations (it can impersonate another user but can not decrypt messages between two legal users). * Disadvantages: (1) if the CA is compromised, the whole network is not secure. Key Distribution CAs Basic key exchange protocol with public-key cryptography. 1 A sends T a request for B's public key A; B. 2 T sends A D KTd (KBe;B) the key signed. 3 A decrypts E KTe (D KTd (KBe;B)). A generates K a session key. A sends B, E KBe (K). 4 B decrypts D KBd (E KBe (K)) = K. A and B then can use K to encrypt a session. The certi cate authority, T, is signing (using a private key) the public key for B in step (2). Because A trusts T's signature then A believes that this is B's public key. In step (3) A can decrypt or verify that B's key was signed by T because every user has T's public key. Key Distribution CAs Denning-Sacco Protocol T keeps a database of everyones public key. t A is a timestamp. 1 A sends T a request for B's public key A; B. 2 T sends A D KTd (KBe;B) the key signed. 3 A decrypts EKTe (D KTd (KBe;B)). A generates K a session key. A sends B, (E KBe (D KAd (K; t A )); D KTd (KBe;B); D KTd (KAe;A)). 4 B decrypts D KBd (E KBe (D KAd (K; t A ))) B decrypts E KTe (D KTd (KBe;B)) B decrypts E KTe (D KTd (KAe;A)). B decrypts E KAe (D KAd (K; t A )) B veri es A's signature. B checks for a valid timestamp t A . A and B then can use K to encrypt a session. Problem! The Denning-Sacco protocol has a problem because after completing the protocol B can now masquerade as A. Many protocols fail because the designer tries to optimize. Key Distribution CAs Now B can replay the old message because he has A's signature. Denning-Sacco Protocol 1 B sends T a request for C's public key B; C. 2 T sends B D KTd (KCe;C) the key signed. Assume B has D KTd (KBe;B), his key signed. 3 B decrypts E KTe (D KTd (KCe;C)). B uses the signed session key from A. B sends C, (E KCe (D KAd (K; t A )); D KTd (KAe;A); D KTd (KCe;C)). 4 C decrypts D KCd (E KCe (D KAd (K; t A ))) C decrypts E KTe (D KTd (KAe;A)) C decrypts EKTe (D KTd (KCe;C)). C decrypts E KAe (D KAd (K; t A )) C veri es A's signature. C checks for a valid timestamp t A . B has fooded C into thinking that she is talking with A. This works until the timestamp expires. To x this in step (3) send EKBe (D KAd (A; B; K; t A )); D KTd (KBe;B); D KTd (KAe;A). Key Distribution Certi cate Revocation Suppose that there is a reason for a user to loose his right to encrypt/decrypt in a system. If the system uses a Key Distribution Center then revoking the users access to shared keys is easy - just don't issue any. If the system uses a CA then revoking a cer- ti cate is harder. It is standard to put an expi- ration date on any certi cate but this could be a year. Solution is similar to that used with credit cards. Publish a book of revoked certi cates. Key Distribution Certi cate Revocation X.509 (ISO88) is a standard for security ser- vices within X.500 directory services frameworks. The X.509 encoding of public key certi cates is widely used, other protocols of X.509 are not. X.509 uses a list called CRL which has serial numbers of certi cates that are revoked. A new CRL is posted periodically and lists re- voked, unexpired certi cates. Certi cates in- clude: an expire time, user ID, user public key, serial number and a CA signature over the en- tire certi cate. The CRL has an issue time and is signed by the CA. A certi cate is valid if has a legal CA's sig- nature and has not expired and is not on the revoked list on the most recent CRL. Key Distribution Session Key Establishment Usually you want to use one key to encrypt data or session keys and another key to en- crypt the data in a session. The key which is used to encrypt the session keys is often also used to establish authentication. * Keys wear out. The more encrypted or signed data that goes over the network the higher the odds of breaking the cipher ( nd- ing the key). Since it is hard to give out au- thentication/ key exchange keys then don't use them to encrypt lots of data. The \bootstrap" is hard to do online. * Changing session keys frequently prevents adding, deleting and reordering old messages (block replay). Packet transmission might not include dated information that would prevent replay of a packet. IP Layer Security * Two new security headers are proposed (IETF working group IPSEC) for use on Internet packets. These headers go before IP head- ers and after TCP/UDP headers. * Authentication Header , AH, supplies au- thentication and integrity over a datagram. Authentication is of the IP address, and a \trust relationship". * Encapsulation Security Payload header, ESP, supplies con dentiality and optionally, in- tegrity and authentication. * A Security Association , SA, must exist be- tween the users. A SA is a negotiated set of algorithms, keys and usage modes that will be used to process a header. SAs de- ne trust relationships and relate to a given network connection or set of connections.. The tricky part is negotiating keys. IP Layer Security Security Associations * An IP Destination Address and SPI value identify a SA uniquely. * A SA typically includes: (1) Authentication algorithms and modes. (2) Keys for use with the algorithms. (3) Encryption algorithms and modes of use. (4) Keys for use with the encryption algo- rithm. (5) The size of a cryptographic synchroniza- tion IV if required by an algorithm. (6) Lifetime of keys. (7) Lifetime of the SA. (8) Source Address of the SA. (9) Sensitivity level (classi ed, unclassi ed, etc.). * An SA is shared by two or more hosts and/or gateways. IP Layer Security AH Header - Authentication Provides connectionless integrity and data ori- gin authentication for IP datagrams. Also re- play protection. AH Header Format Next Header (8) j Payload Len (8) j Reserved (16) Security Parameter Index or SPI (32) Sequence Number Field (32) Authentication Data (variable number of 32-bit words) Transport Mode for IPv4 IP header j AH j TCP header j Data authentication ! The SPI is a random value used, with the des- tination IP address, to index a SA. The SA contains the keys, algorithms, etc. needed to process the header. IP Layer Security AH Header - Authentication The Authenticated Data contains the integrity check value. All elds of the IP header which are not modi ed during transit are authenti- cated; i.e, covered by the integrity check. AH Header Format Next Header (8) j Payload Len (8) j Reserved (16) Security Parameter Index or SPI (32) Sequence Number Field (32) Authentication Data (variable number of 32-bit words) IP Layer Security ESP Header - Con dentiality Provides con dentiality, connectionless integrity, data origin authentication, anti-replay services and limited control con dentiality. The services depend on the SA and tunnel or trans- port modes. ESP Header Format Security Parameter Index or SPI (32) Sequence Number Field (32) Payload data (variable length) Padding (0-255 bytes) opt. Pad Length j Next Header (8) Authentication Data (variable - max 96 bits) opt. Transport Mode for IPv4 IP header j ESP j TCP j Data j ESP trailer j ESP Auth. encryption ! authentication ! Encryption is performed before authentication on outbound packets. ESP assumes a symmetric encryption system. IP Layer Security ESP Header - Con dentiality For ESP Transport Mode: The authenticated data includes all of the ESP elds except the Authentication Data eld. (Not the IP header.) Encryption covers the Payload Data, Padding, Pad Length and Next Header elds. ESP Header Format Tunnel Mode for IPv4 NEW IP j ESP j Old IP j TCP j Data j ESP trailer j ESP Auth. encryption ! authentication ! The \inner" IP packet carries the ultimate source and destination addresses. The \outer" IP header may contain di erent IP addresses. Encryption is now over the Old IP header, TCP, Data and ESP trailer elds. Authentication is over all of these plus the ESP eld. IP Layer Security Key Negotiation * ISAKMP, Internet Security Association and Key Management Protocols, is a framework for security association management and cryp- tographic key management protocols. * ISAKMP assumes that all users have access to public keys. BIG assumption. At the least there needs to be an Internet-standard scalable key management protocol. * It is assumed that key management data is carried by higher layer protocols like TCP/UDP. * Host-oriented vra. user-oriented keying. * A few public-key options: (1) DNS - signed public keys added to the Domain Name Server. (2) DNSSEC - Secure Domain Name Servers. (3) Certi cate Infrastructure. ChaĆng and Winnowing From the paper ChaĆng and Winnowing: Con- dentiality without Encryption, by R. L. Rivest (MIT)  Winnowing can be used to develop a new con dentiality scheme that does not fall un- der the same de nition as cryptography.  No encryption so no decryption key needed. Circumvents export laws on cryptography. The regulation of cryptography does not cover regulation of steganography and win- nowing.  To winnow is to \separate out or eliminate (the poor or useless parts)". ChaĆng and Winnowing ChaĆng Scheme Two Parts to sending a message:  Authentication (add a MAC - for example HMAC or SHA1).  Adding chaĆng. Note: Authentication algorithms are all approved for export even if they are keyed with a shared secret key. Authenticated DiĆe-Hellman can be used by two users to get a shared secret key. ChaĆng and Winnowing ChaĆng - Sender  Break the message into packets.  Authenticate each packet using a secret au- thentication key. Compute h(K; Packet) = MAC to get Packet; MAC). The packet is still \in the clear".  In general, a packet will also carry a unique sequence number which is used to delete duplicate packets, detect missing packets, reorder received packets. The MAC for a packet is computed as a functions of the packet sequence number also. h((number; data); K) = MAC  Add cha to the packet stream. ChaĆng and Winnowing ChaĆng - Sender  Add cha to the packet stream. Add fake packets with bogus MACs.  Construct a series of extra, reasonable pack- ets and sequence numbers. The sequence numbers can duplicate already existing se- quence numbers.  Add fake MACs to the extra packets. In- clude these packets in the packet stream. h((1; data); K) =MAC 1 send ((1; data); MAC 1 ) send ((1; fake data); Random String 1 ) h((2; data); K) =MAC 2 send ((2; data); MAC 2 ) send ((2; fake data); Random String 2 ) ChaĆng and Winnowing Winnowing - Receiver  Compute the MAC of every packet that is received using the agreeded on secret key.  Discard any packet for which the MAC is incorrectly computed, the \cha "'.  Order the remaining packets - these are the \wheat".  Note: this is the typical behavior on receiv- ing a packet with an incorrect MAC.  An adversary must determine what is cha and what is wheat which might be indepen- dent of nding the shared secret key. ChaĆng and Winnowing How to make the Adversary's job hard  Break the message into packets containing 1 bit each.  Authenticate each packet using a secret au- thentication key. Compute a MAC over the data and packet sequence number.  Add cha to the packet stream. If a packet with sequence number s contains a 0 as the data then create a new packet with the same sequence number but with a 1 as the data.  Add a fake MAC to this packet. Include these packets in the packet stream. ChaĆng and Winnowing Claim: This scheme provides con dentiality with- out using encryption - the message is in the clear. Claim: Used with 1 bit messages, separating the wheat from the cha requires either break- ing the MAC algorithm or knowing the secret authentication key.