1Computer SecurityCS 426Lecture 4Cryptography Basics - 2Elisa BertinoPurdue UniversityIN, [email protected]•DES– Data Encryption Standard– adopted in 1977 by NBS (now NIST) as FIPS PUB 46– controversy over its security– Strength of DES: with a 128 bits key, it takes 1018 years to break the cipher•TDES- Triple DES –– based on TDEA algorithm (3 keys and 3 different executions of DES)• AES – Advanced Encryption Standard– Approved in 2001 as FIPS 197Symmetric encryption standardsSymmetric encryption standards•IDEA(128-bit keys)• Blowfish (Schneier, up to 448-bit keys)Block Ciphers• Map n-bit plaintext blocks to n-bit ciphertext blocks (n: block length), each of which is then encrypted (ie like a substitution on very big characters - 64-bits or more)• Main difference with stream ciphers:– In stream ciphers the way a character is encrypted depends only on the character itself (and on the position of the character – Vigenere)– In block ciphers the way a character is encrypted depends on the other characters in the same block– Advantages/disadvantages:• Stream ciphers are efficient and have low error propagation; however they have low diffusion and are susceptible to malicious insertions and modifications• Block cyphers have high diffusion and are more resistant against malicious insertions and modifications; however they are slower and prone to error propagation2Block Ciphers Features• Block size: in general larger block sizes mean greater security.•Key size: larger key size means greater security (larger key space).• Number of rounds: multiple rounds offer increasing security.• Encryption modes: define how messages larger than the block size are encrypted, very important for the security of the encrypted message.History of Data Encryption Standard (DES)• 1967: Feistel at IBM– Lucifer: block size 128; key size 128 bit• 1972: NBS asks for an encryption standard• 1975: IBM developed DES (modification of Lucifer)– block size 64 bits; key size 56 bits• 1975: NSA suggests modification• 1977: NBS adopts DES as encryption standard in (FIPS 46-1, 46-2).• 2001: NIST adopts Rijndael as replacement to DES.DES Features• Features:–Block size = 64 bits–Key size = 56 bits–Number of rounds = 16 –16 intermediary keys, each 48 bitsDES Rounds3Left Data HalfRight Data HalfKey ShiftedKey PermutedSubstitutionPermutationA Cycle in DESNew Left Data Half(Old Right Half)New Right Data HalfDES – DetailsKey Scheduling• Although the input key for DES is 64 bits long, the actual key used by DES is only 56 bits in length. • The least significant (right-most) bit in each byte is a parity bit, and should be set so that there are always an odd number of 1s in every byte. • These parity bits are ignored, so only the seven most significant bits of each byte are used, resulting in a key length of 56 bits. • The first step is to pass the 64-bit key through a permutation called Permuted Choice 1, or PC-1 for short. The table for this is given in next slide. • Note that in all subsequent descriptions of bit numbers, 1 is the left-most bit in the number, and n is the rightmost bit. DES – DetailsPC-1: Permuted Choice 141220285132150293745536161443223038465462736152331394755632936445260311192259504122584911015702735435115182634428917253316543BitDES – Details Key Scheduling• Example: use the PC-1 table to determine how bit 30 of the original 64-bit key transforms to a bit in the new 56-bit key. 1) Find the number 30 in the PC-1 table, and notice that it belongs to the column labeled 5 and the row labeled 36. 2) Add up the value of the row and column to find the new position of the bit within the key. For bit 30, 36 + 5 = 41, so bit 30 becomes bit 41 of the new 56-bit key. • Note that bits 8, 16, 24, 32, 40, 48, 56 and 64 of the original key are not in the table. These are the unused parity bits that are discarded when the final 56-bit key is created. • Now that we have the 56-bit key, the next step is to use this key to generate 16 48-bit subkeys, called K[1]-K[16], which are used in the 16 rounds of DES for encryption anddecryption. • The procedure for generatingthe subkeys - known as key scheduling – has the following steps: 1. Set the round number R to 1. 2. Split the current 56-bit key, K, up into two 28-bit blocks, L (the left-hand half) and R (the right-hand half). 3. Rotate L left by the number of bits specified in the subkey rotation table, and rotate R left by the same number of bits as well. 4. Join L and R together to get the new K. 5. Apply the Permuted Choice 2 (PC-2) table to K to get the final K[R], where R is the round number we are on. 6. Increment R by 1 and repeat the procedure until we have all 16 subkeys K[1]-K[16].4DES Subkey Rotation Table and PC-2322936504246435334563949443748334551403031554737315241252132027716191215112192817123314082641310216751241543BitPC-221321221121019214215252627281162211NBR4321RNSubkey Rotation TableRN: round numberNBR: number of bits to rotate • Once the key scheduling has been performed, the next step is to prepare the plaintext for the actual encryption. • This is done by passing the plaintext through a permutation called the Initial Permutation, or IP for short. • This table also has an inverse, called the Inverse Initial Permutation, or IP^(-1). Sometimes IP^(-1) is also called the Final Permutation. DES Plaintext Preparation753186427151311916141210623313947556357212937455361491927354351594117253341495733243240485664254644422545250162605802230381720283691826341543BitDES – IP and IP^(-1) TablesIPIP^(-1)252627282930313275758596061626364617499411335718501042234491951114333541205212444363321531345537254647482678138394002254141723551592456161543Bit• IP and IP^(-1) are one the inverse of the other• For example, let's look how bit 32 is transformed under IP. In the table, bit 32 is located at the intersection of the column labeled 4 and the row labeled 25. So this bit becomes bit 29 of the 64-bit block after the permutation. • Now let's apply IP^(-1). In IP^(-1), bit 29 is located at the intersection of the column labeled 7 and the row labeled 25. So this bit becomes bit 32 after the permutation. And this is the bit position that we started with before the first permutation. • If we run a block of plaintext through IP and then pass the resulting block through IP^(-1), we obtain with the original block. DES – IP and IP^(-1) Tables5The 64-bit block of input