Secret Key Cryptography Raj Jain Washington University in Saint Louis Saint Louis MO 63130 Jain cse wustl edu Audio Video recordings of this lecture are available at http www cse wustl edu jain cse571 07 Washington University in St Louis CSE571S 5 1 2007 Raj Jain Overview 1 2 3 4 Data Encryption Standard DES International Data Encryption Algorithm IDEA Advanced Encryption Standard AES Ron s Cipher 4 RC4 Ref Chapter 3 of the textbook Washington University in St Louis CSE571S 5 2 2007 Raj Jain Encryption Schemes Symmetric Ciphers Block Ciphers Asymmetric Ciphers Stream Ciphers Synchronous Self Synchronous Symmetric 1 Key 2 users Secret Key Asymmetric Public Key Public and Private Keys Block Message broken in to fixed size blocks Synchronous Key stream depends on the key and IV Asynchronous Key stream depends on key IV and previous cipher text Washington University in St Louis CSE571S 5 3 2007 Raj Jain Secret Key Encryption Also known as symmetric encryption Encrypted Message Encrypt Key Message Message Decrypt Key Encrypted Message Example Encrypt division 433 48 R 1 using divisor of 9 Washington University in St Louis CSE571S 5 4 2007 Raj Jain Secret Key Cryptography Block Encryption KPS Fig 3 1 Washington University in St Louis CSE571S 5 5 2007 Raj Jain Block Encryption Cont Short block length tabular attack 64 bit block Transformations Substitution replace k bit input blocks with k bit output blocks Permutation move input bits around 1 13 2 61 etc Round Substitution round followed by permutation round and so on Washington University in St Louis CSE571S 5 6 2007 Raj Jain Data Encryption Standard DES Published by National Bureau of Standards in 1977 For commercial and unclassified government applications 8 octet 64 bit key Each octet with 1 odd parity bit 56 bit key Efficient hardware implementation Used in most financial transactions Computing power goes up 1 bit every 2 years 56 bit was secure in 1977 but is not secure today Now we use DES three times Triple DES 3DES Washington University in St Louis CSE571S 5 7 2007 Raj Jain DES Steps Total 18 steps Initial permutation 16 mangler rounds Inverse of initial permutation KPS Fig 3 2 Washington University in St Louis CSE571S 5 8 2007 Raj Jain Initial and Final Permutation Input bit 58 goes to output bit 1 Input bit 50 goes to output bit 2 Washington University in St Louis CSE571S 5 9 2007 Raj Jain DES Round KPS Fig 3 6 Washington University in St Louis CSE571S 5 10 2007 Raj Jain Mangler Function 32 bit Rn and 48 bit Kn 32 bit Rn 8 4 bits 8 6 bits 48 bit key 8 6 bits KPS Fig 3 7 Washington University in St Louis CSE571S 5 11 2007 Raj Jain DES Substitution Box Xor and S Box Washington University in St Louis CSE571S 5 12 2007 Raj Jain DES S Box Cont S Box KPS Fig 3 9 3 Permutation 16th input bit is the 1st output bit Washington University in St Louis CSE571S 5 13 KPS Fig 3 17 2007 Raj Jain Generation of Per Round Keys Divide in to 28 bit halves Initial permutation 57th bit of key becomes the 1st bit of output 49th bit of key becomes the 2nd bit of output Washington University in St Louis CSE571S 5 14 2007 Raj Jain Generation of Per Round Keys Cont Rotate left by 1 or 2 bits In rounds 1 2 9 and 16 rotate 1 bit left in other rounds rotate 2 bit left KPS Fig 3 5 Washington University in St Louis CSE571S 5 15 2007 Raj Jain Generation of Per Round Keys Cont Final permutation 4 bits are discarded from each half 24 bits Left Half Right Half 14th input bit becomes the 1st output bit Bits 9 18 22 25 of left half are discarded Bits 35 38 53 and 54 of right half are discarded Washington University in St Louis CSE571S 5 16 2007 Raj Jain DES Decryption Identical to Encryption Keys are used in reverse order Washington University in St Louis CSE571S 5 17 2007 Raj Jain International Data Encryption Algorithm IDEA Designed for software implementation Encryption and Decryption are identical as in DES KPS Fig 3 18 Washington University in St Louis CSE571S 5 18 2007 Raj Jain International Data Encryption Algorithm 128 bit key is converted to 52 16 bit keys Inverse of the encryption key is used for decryption in the reverse order Has patent protection Washington University in St Louis CSE571S 5 19 2007 Raj Jain Advanced Encryption Standard AES Published by NIST in Nov 2001 Based on a competition won by Rijmen and Daemen Rijndael Rijndael allows many block sizes and key sizes AES restricts it to Block Size 128 bits Key sizes 128 192 256 AES 128 AES 192 AES 256 Washington University in St Louis CSE571S 5 20 2007 Raj Jain Basic Structure of Rijndael Number of Rounds Nr 6 max Nb Nk Nb 32 bit words in the the block Nk 32 bit words in key 4 rows Nb columns Nb 4 for AES KPS Fig 3 23 Washington University in St Louis CSE571S 5 21 2007 Raj Jain Key Expansion Key flows in octet by octet in 4 octet columns Nr 1 Nb columns Key expansion uses the same kind of primitive operations as the rounds Rows columns round keys are numbered starting at 0 round numbers start at 1 Washington University in St Louis CSE571S 5 22 2007 Raj Jain AES Primitive Operations Xor Substitution box Rotation column or row MixColumn Replace 32 bit word with another 32 bit word Washington University in St Louis CSE571S 5 23 2007 Raj Jain Rijndael S Box KPS Fig 3 27 Washington University in St Louis CSE571S 5 24 2007 Raj Jain MixColumn 4 Input octets are used as an index to retrieve a column from the table KPS Fig 3 26 Washington University in St Louis CSE571S 5 25 2007 Raj Jain MixColumn Cont Retrieved column is rotated vertically so that its top octet is in the same row as the input octet Four rotated columns are xor ed KPS Fig 3 25 Washington University in St Louis CSE571S 5 26 2007 Raj Jain AES Decryption Inverse MixColumn Inverse S Box Inverse Xor Xor Washington University in St Louis CSE571S 5 27 2007 Raj Jain AES Key Expansion Column 0 of the ith set is obtained by rotating the last column of i 1 th set upward by one cell applying the S Box to each octet then Xor ing a constant based on i into octet 0 and Xoring it with 0th column of i 1 th set Column j of the ith set is obtained by Xor ing j 1 th column with jth column of i 1 th set Set i 1 Set i KPS Fig 3 30 Washington University in St Louis CSE571S 5 28 2007 Raj Jain AES Key Expansion Cont If Nk 6 then Column 4 is generated by applying Sbox to each octet of the column KPS Fig 3 32 Constants KPS Fig 3 31 Washington University in St Louis CSE571S 5 29 …