This preview shows page 1-2-3-4-5-6-7-49-50-51-52-53-54-55-99-100-101-102-103-104-105 out of 105 pages.
Cipher Techniques CS498SH Fall 2005 Based on slides provided by Matt Bishop for use with Computer Security Art and Science Slide 11 1 Reading Chapter 11 in Computer Science Art and Science Chapter 10 in Introduction to Computer Security Can also look at Standards Documents Slide 11 2 Overview Problems What can go wrong if you naively use ciphers Cipher types Stream or block ciphers Networks Link vs end to end use Examples Privacy Enhanced Electronic Mail PEM Secure Socket Layer SSL Security at the Network Layer IPsec Slide 11 3 Problems Using cipher requires knowledge of environment and threats in the environment in which cipher will be used Is the set of possible messages small Do the messages exhibit regularities that remain after encipherment Can an active wiretapper rearrange or change parts of the message Slide 11 4 Attack 1 Precomputation Set of possible messages M small Public key cipher f used Idea precompute set of possible ciphertexts f M build table m f m When ciphertext f m appears use table to find m Also called forward searches Slide 11 5 Example Cathy knows Alice will send Bob one of two messages enciphered BUY or enciphered SELL Using public key eBob Cathy precomputes m1 BUY eBob m2 SELL eBob Cathy sees Alice send Bob m2 Cathy knows Alice sent SELL Slide 11 6 May Not Be Obvious Digitized sound Seems like far too many possible plaintexts Initial calculations suggest 232 such plaintexts Analysis of redundancy in human speech reduced this to about 100 000 217 This is small enough to worry about precomputation attacks Slide 11 7 Attack 2 Misordered Blocks Alice sends Bob message nBob 77 eBob 17 dBob 53 Message is LIVE 11 08 21 04 Enciphered message is 44 57 21 16 Eve intercepts it rearranges blocks Now enciphered message is 16 21 57 44 Bob gets enciphered message deciphers it He sees EVIL Slide 11 8 Notes Digitally signing each block won t stop this attack Two approaches Cryptographically hash the entire message and sign it Place sequence numbers in each block of message so recipient can tell intended order Then you sign each block Slide 11 9 Attack 3 Statistical Regularities If plaintext repeats ciphertext may too Example using DES input in hex 3231 3433 3635 3837 3231 3433 3635 3837 corresponding output in hex ef7c 4bb2 b4ce 6f3b ef7c 4bb2 b4ce 6f3b Fix cascade blocks together chaining More details later Slide 11 10 What These Mean Use of strong cryptosystems well chosen or random keys not enough to be secure Other factors Protocols directing use of cryptosystems Ancillary information added by protocols Implementation not discussed here Maintenance and operation not discussed here Slide 11 11 Stream Block Ciphers E encipherment function Ek b encipherment of message b with key k In what follows m b1b2 each bi of fixed length Block cipher Ek m Ek b1 Ek b2 Stream cipher k k1k2 Ek m Ek1 b1 Ek2 b2 If k1k2 repeats itself cipher is periodic and the kength of its period is one cycle of k1k2 Slide 11 12 Examples Vigen re cipher bi 1 character k k1k2 where ki 1 character Each bi enciphered using ki mod length k Stream cipher DES bi 64 bits k 56 bits Each bi enciphered separately using k Block cipher Slide 11 13 Stream Ciphers Often try to implement one time pad by xor ing each bit of key with one bit of message Example m 00101 k 10010 c 10111 But how to generate a good key Slide 11 14 Synchronous Stream Ciphers n stage Linear Feedback Shift Register consists of n bit register r r0 rn 1 n bit tap sequence t t0 tn 1 Use Use rn 1 as key bit Compute x r0t0 rn 1tn 1 Shift r one bit to right dropping rn 1 x becomes r0 Slide 11 15 Operation r0 rn 1 bi ci r0 r0t0 rn 1tn 1 rn 1 ri ri 1 0 i n Feedback Function Slide 11 16 Example 4 stage LFSR t 1001 r kinew bit computation new r 0010 0 01 00 10 01 0 0001 0001 1 01 00 00 11 1 1000 1000 0 11 00 00 01 1 1100 1100 0 11 10 00 01 1 1110 1110 0 11 10 10 01 1 1111 1111 1 11 10 10 11 0 0111 1 00 11 10 10 11 1 1011 Key sequence has period of 15 010001111010110 Slide 11 17 LFSR Period For n bit register Maximum possible period is 2n 1 1 because 0 s will only yield 0 s Not all tap sequences will yield this period Large theory on computing maximal period feedback functions Slide 11 18 NLFSR n stage Non Linear Feedback Shift Register consists of n bit register r r0 rn 1 Use Use rn 1 as key bit Compute x f r0 rn 1 f is any function Shift r one bit to right dropping rn 1 x becomes r0 Note same operation as LFSR but more general bit replacement function Slide 11 19 Example 4 stage NLFSR f r0 r1 r2 r3 r0 r2 r3 r ki new bit computation new r 1100 0110 0011 1001 1100 0110 0011 0 0 1 1 0 0 1 0110 0011 1001 1100 0110 0011 1001 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 Key sequence has period of 4 0011 Slide 11 20 Eliminating Linearity NLFSRs not common No body of theory about how to design them to have long period Alternate approach output feedback mode For E encipherment function k key r register Compute r Ek r key bit is rightmost bit of r Set r to r and iterate repeatedly enciphering register and extracting key bits until message enciphered Variant use a counter that is incremented for each encipherment rather than a register Take rightmost bit of Ek i where i is number of encipherment Slide 11 21 OFB Mode Pi Pi 1 Ek Si 1 Ci 1 Pi 1 Ek Ci Ci 1 Slide 11 22 Counter Mode Pi Pi 1 Ek Ctri 1 Ci 1 Pi 1 Ek Ek Ctri Ctri 1 Ci Ci 1 Slide 11 23 Issues with OFB Counter Additional standard modes for DES AES Losing Synchronicity is fatal All later decryptions will be garbled OFB needs an initialization vector Counter mode lets you generate a bit in the middle of the stream RC4 is a well known stream cipher that uses OFB Used in WEP Slide 11 24 Self Synchronous Stream Cipher Take key from message itself autokey Example Vigen re key drawn from plaintext key XTHEBOYHASTHEBA plaintextTHEBOYHASTHEBAG ciphertext QALFPNFHSLALFCT Problem Statistical regularities in plaintext show in key Once you get any part of the message you can decipher more Slide 11 25 Another Example Take key from ciphertext autokey Example Vigen re key drawn from ciphertext key XQXBCQOVVNGNRTT plaintext THEBOYHASTHEBAG ciphertext QXBCQOVVNGNRTTM Problem Attacker gets key along with ciphertext so deciphering is trivial Slide 11 26 Variant Cipher feedback mode 1 bit of ciphertext …
View Full Document
Unlocking...