Cryptography--BlockCiphers

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,September, 2006,*,Cryptography - Block Ciphers,Anita Jones,CS451 Information Security,Copyright(C) Anita Jones,1,Overview,terms and principles,Claude Shannon,Feistel cipher,DES,A few terms,block cipher,block of plaintext is treated as a whole & used to produce a ciphertext block of equal length,typical size: 64 bits,most modern ciphers are block ciphers,stream cipher,digital data is encrypted one bit (or one unit) at a time,In both cases, plaintext is transformed incrementally,Symmetric ciphers,Symmetric implies,ONE,key,Secret,key shared by sender & receiver,4,Background,ideally want one extremely large substitution,not practical since would need a table with 2,64,entries in it for a 64-bit block,so approximate the ideal by constructing from smaller building blocks,Basis of modern ciphers,Claude Shannon (45) - information theory,product cipher,perform two or more ciphers in sequence so that result (product) is cryptographically stronger than any component cipher,alternate,confusion,&,diffusion,virtually all significant symmetric block ciphers currently in use are of this type,Shannons strategy,thwart cryptanalysis that is based on statistical analysis,hacker has some knowledge of statistical characteristic of plaintext,if statistics are reflected in ciphertext, then analyst may be able to deduce encryption key, or part of it,in Shannons,ideal,cipher, statistics of ciphertext are,independent,of plaintext,Shannons building blocks,confusion,make relation between statistics of ciphertext and the value of the encryption key as complex as possible,diffusion,diffuse statistical property of plaintext digit across a range of ciphertext digits,i.e. each plaintext digits affects value of many ciphertext digits,Shannons building blocks,Shannon proposed product ciphers with two components,S-Boxes -,substitution,providing confusion of input bits,P-Boxes -,permutation,providing diffusion across S-box inputs,n rounds of S-P boxes,S-box (substitution),0,1,2,3,4,5,6,7,3 bit,input,0,1,0,0,1,2,3,4,5,6,7,1,1,0,3 bit,output,Word size of 3 bits = mapping of 2,3,= 8 values,Note: mapping can be reversed,P-box (permutation),4 bit,input,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,Example 1,Note: reversible,Example 2 - s,halves of input,S-P networks,alternate S and P boxes,BUT, in practice we must decrypt as well as encrypt,so define the sequence of boxes so that precisely the same system will decrypt as well as encrypt,just run it backwards,Feistel cipher,input plaintext of 2w bits,key K =,n,sub-keys: K,1, K,2, , K,n,sequence of,n,“rounds” each using K,i,substitution followed by a permutation,apply function F(K,i,) to right half of data, then exclusive-OR it to left half of data,permutation: interchange two result halves of data,DES is essentially a Feistel cipher,Feistel cipher,Multiple rounds,round i input is L,i-1, R,i-1,L,i,= R,i-1,R,i,= (L,i-1,XOR,F(R,i-1, K,i,),L left portion of intermediate data,R right .,plaintext (2w bits),w bits,w bits,L,0,R,0,Round 1,K,1,L,1,R,1,F,+,K,n,L,n,R,n,F,+,Round n,. . .,. . .,L,n+1,R,n+1,ciphertext (2w bits),Feistel cipher dependencies,block size,increasing size increases security,64 bits common,key size,increasing size improves security,128 bits common,number of rounds,16 is typical,subkey generation,complex generation makes cryptanalysis harder,round function,complex function is stronger, but all increases slow the implementation,Feistel decryption,same as encryption, except,ciphertext is input,use keys in reverse order,at each round the output is equal to the corresponding value of the encryption process with the two halves of the value s,final permutation (swap) realigns 2 halves,History of DES,DES,Data Encryption Standard,Horst Feistel at IBM developed LUCIFER,about 1971, sold to Lloyds of London,Natl Bureau of Standards issued request for national cipher standard,IBM submitted (refined) LUCIFER,NSA worked with IBM to refine cipher,adopted in 1977 by Natl Bureau of Stds.,DES Characteristics,Plaintext is 64 bits long,16 rounds,Key length is 56 bits,16 sub-keys generated, one used in each round,DES algorithm is a variant of the Feistel algorithm,plaintext (64 bits),init permutation,round 1,K1,round 2,K2,round n,Kn,inverse permutation,ciphertext (64 bits),32 bit swap,56 bit key,. . .,permute,left circ shift,perm,left circ shift,perm,left circ shift,perm,. . .,DES cipher,round i input is L,i-1, R,i-1,L,i,= R,i-1,R,i,= (L,i-1,XOR,F(R,i-1,K,i,),L,i-1,exp/perm to 48,S-box,permutation,R,i-1,x,K,i,x,L,i,R,i,- 48 bits,- 48 bits,- 32 bits,- 32 bits,One DES Round,Key property,avalanche,small change in plaintext or in key produces significant change in ciphertext,test for avalanche,encrypt two plaintext blocks that differ only in one bit,about half the (ciphertext) bits will differ,DES controversy,DES choice was intensely criticized:,original LUCIFER key length was 128 bits, and DES used 56 bit key (to fit on chip,they,said),critics feared brute force attacks,design criteria for the S-boxes was classified, so users not sure that internal structure was free of hidden weak points that might let NSA break cipher,DES status,no weak points have surfaced,DES is widely used,1994, NIST reaffirmed DES for federal use,NIST recommends DES use for all except classified information,generally considered a sound standard,Need more security: use Triple DES,Future: Adv.d Encryption Standard (AES),Cryptanalysis of DES,increased computing speed has made a 56 bit key susceptible to exhaustive key search,demonstrated breaks:,1997,taking a few,months, a large network of computers broke DES,1998,Electronic Frontier Foundation broke DES in a few,days,on dedicated hardware,1999,break accomplished in 22,hours,in practice DES is used, and works,1997 break,RSA issued reward of $10,000 for finding a DES key, given ciphertext for known and unknown plaintext,solution found in 96 days,involved 70,000 computers on the Internet,an,embarrassingly parallel problem,just divide the key space being searched (brute force) each time a new computer joins in,found the key after searching 1/4 key space,So, how does the Prez talk?,STU-III:,“,A STU-III operates by taking an audio signal and digitizing it into a serial data stream (usually 8,000 bits per second).,This is then mixed with a keying stream,of data created by an internal ciphering algorithm. This mixed data is them passed though an internal CODEC to convert it back to audio so it can be passed over the phone lines. STU-IIIs also allow a serial data stream to pass though the phone and into the ciphering engine to allow its usage as an encrypted modem when not being used for voice.,The keying stream is a polymorphic regenerating mathematic algorithm which takes a initialization key and mathematically morphs it into a bit stream pattern.,The keying stream is created by the Key Generator and is the actual heart of the STU. A portion of the keying stream are then mixed back into to the original key, and process repeated. The results is a pseudo-random bit stream that if properly implemented is extremely difficult (but not impossible) to decrypt.”,Source:,Model for cryptography-revisit,Principal,Principal,Message,Secret,Information,Security,Transform,Security,Transform,Message,Secret,Information,Trusted 3rd Party,(arbitrates, distributes,secret information),Opponent,Info channel,