CSC 474/574 Dr. Peng Ning 1Computer ScienceCSC 474/574Information Systems SecurityTopic 2.2 Secret Key CryptographyCSC 474/574 Dr. Peng Ning 2Computer ScienceAgenda• Generic block cipher• Feistel cipher• DES• Modes of block ciphers• Multiple encryptions• Message authentication through secret keycryptography.CSC 474/574 Dr. Peng Ning 3Computer ScienceGeneric Block CipherCSC 474/574 Dr. Peng Ning 4Computer ScienceGeneric Block CipherSecret keyPlaintextblockof length NCipherblockof length N EncryptDecryptCSC 474/574 Dr. Peng Ning 5Computer ScienceGeneric Block Encryption (Cont’d)• Convert one block to another: one-to-one• Long enough to avoid known-plaintext attack,but not too long (performance).– 64 bit typical• Naïve: 264 input values, 64 bits each• Output should look random– No correlation between plaintext and ciphertext– Bit spreadingCSC 474/574 Dr. Peng Ning 6Computer ScienceGeneric Block Encryption (Cont’d)• Achieve by substitution:– Need to know how to substitute each plaintext message.– How many bits for k-bit blocks: _________bits• Achieve by permutation:– Need to know which position each bit is placed.– How many bits for k-bit blocks: _________bits• Achieve by combinations of substitutions andpermutations– How about SPSSP…– How about SPPS…– Lesson? ___________________________CSC 474/574 Dr. Peng Ning 7Computer ScienceFeistel CipherCSC 474/574 Dr. Peng Ning 8Computer ScienceFeistel Cipher• Confusion– Make the relationship between the plaintext/key and theciphertext as complex as possible– Achieved by complex substitution algorithm.• Diffusion– Dissipate the statistical structure of the plaintext– Achieved by having each plaintext digit affect manyciphertext digit– Equivalently, having each ciphertext digit affected bymany plaintext digit.CSC 474/574 Dr. Peng Ning 9Computer ScienceFeistel Cipher (cont’d)• Alternate diffusion and confusion• Equivalently, alternate substitution andpermutationCSC 474/574 Dr. Peng Ning 10Computer ScienceFeistel Cipher StructurePlaintext (2w bits)FFFCiphertext (2w bits)……… …Round 1Round iRound nK1KiKnL0R0LiRiLnRnLn+1Rn+1Encryption:CSC 474/574 Dr. Peng Ning 11Computer SciencePlaintext (2w bits)Decryption:FFFCiphertext (2w bits)……… …Round 1Round iRound nKnKiK1L0R0LiRiLnRnLn+1Rn+1Feistel Cipher Structure (cont’d)CSC 474/574 Dr. Peng Ning 12Computer ScienceOne Round Feistel CipherFEncryptionL1R1L2R2Plaintext (2w bits)L0R0K1Ciphertext (2w bits)FL’0R’0L’1R’1L’2R’2K1DecryptionCSC 474/574 Dr. Peng Ning 13Computer ScienceRealization of Feistel Cipher• Parameters– Block Size: typically 64 bits– Key Size: commonly 128 bits– Number of Rounds: 16– Subkey Generation algorithm– Round FunctionCSC 474/574 Dr. Peng Ning 14Computer ScienceDES (Data Encryption Standard)CSC 474/574 Dr. Peng Ning 15Computer ScienceDES (Data Encryption Standard)• Published in 1977, standardized in 1979, expired in1998.• Similar structure to Feistel cipher• Key: 64 bit quantity=8-bit parity+56-bit key– Every 8th bit is a parity bit.• 64 bit input, 64 bit output.DESEncryption64 bit M 64 bit C56 bitsCSC 474/574 Dr. Peng Ning 16Computer ScienceDES Top ViewPermutationPermutationSwapRound 1Round 2Round 16Generate keysInitial Permutation48-bit K148-bit K248-bit K16Swap 32-bit halvesFinal Permutation64-bit Output64-bit Input56-bit Key…...CSC 474/574 Dr. Peng Ning 17Computer ScienceBit Permutation (1-to-1)…….…….. 1 2 3 4 3222 6 13 32 3Input:Output 0 0 1 0 1 1 0 1 1 11 bitCSC 474/574 Dr. Peng Ning 18Computer ScienceInitial and Final Permutations• Initial permutation (IP)• View the input as M: 8-byte X 8-bit matrix• Transform M into M1 in two steps– Transpose row x into column (9-x), 0<x<9– Apply permutation on the rows:• For even row y, it becomes row y/2• For odd row y, it becomes row (5+y/2)• Final permutation FP = IP-1– Why?CSC 474/574 Dr. Peng Ning 19Computer SciencePer-Round Key Generation28 bits 28 bits48 bitsKiCircular Left Shift Circular Left Shift28 bits 28 bitsPermutationwith DiscardInitial Permutation of DES keyC i-1D i-1C iD iRound 1,2,9,16: single shiftOthers: two bitsCSC 474/574 Dr. Peng Ning 20Computer ScienceA DES Round48 bits32 bits32 bits 32 bits32 bits 32 bitsES-BoxesPKiOne RoundEncryptionManglerFunctionCSC 474/574 Dr. Peng Ning 21Computer Science…….…….. 1 2 3 4 5 32Input:Output 0 0 1 0 1 1 1 2 3 4 5 6 7 8 481 0 0 1 0 1 0 1 1 0Bits ExpansionCSC 474/574 Dr. Peng Ning 22Computer ScienceE Box of DES129252117139529 30 31 3225 26 27 2821 22 23 2417 18 19 2013 14 15 169 10 11 125 6 7 81 2 3 428242016128432• How is the E Box defined?CSC 474/574 Dr. Peng Ning 23Computer ScienceMangler Function4444444 46666666 6+ + +++ ++ +6666666 6S8S1 S2 S7S3 S4 S5 S64444444 4PermutationThe permutationproduces “spread” amongthe chunks/S-boxes!subkeyCSC 474/574 Dr. Peng Ning 24Computer Science2 bitsrowSii = 1,…8.I1I2I3I4I5I6O1O2O3O44 bitscolumnan integer between0 and 15.S-Box (Substitute and Shrink)• 48 bits ==> 32 bits. (8*6 ==> 8 *4)• 2 bits used to select amongst 4 permutationsfor the rest of the 4-bit quantityCSC 474/574 Dr. Peng Ning 25Computer ScienceS1: (p. 71)0 1 2 3 4 5 6 … 150 14 4 13 1 2 15 111 0 15 7 4 14 2 132 4 1 14 8 13 6 23 15 12 8 2 4 9 1Each row and column contain different numbers.Example: input: 100110 output: ???CSC 474/574 Dr. Peng Ning 26Computer ScienceDES Standard• Cipher Iterative Action– Input: 64 bits– Key: 48 bits– Output: 64 bits• Key Generation Box– Input: 56 bits– Output: 48 bitsOne round (Total 16 rounds)CSC 474/574 Dr. Peng Ning 27Computer ScienceAvalanche Effect• A small change in either the plaintext or the keyshould produce a significant change in the ciphertext.• DES has a strong avalanche effect.• Example– Plaintexts: 0X0000000000000000 and0X8000000000000000– Same key: 0X016B24621C181C32– 34 bits difference in cipher-texts– Similar result with same