Computer Science CSC/ECE 574 Computer and Network Security Topic 3.1 Secret Key Cryptography – Algorithms CSC/ECE 574 Dr. Peng Ning 1 Computer Science Outline • Introductory Remarks • Feistel Cipher • DES • AES CSC/ECE 574 Dr. Peng Ning 2 Computer Science Introduction CSC/ECE 574 Dr. Peng Ning 3Computer Science Secret Keys or Secret Algorithms ? • “Security by obscurity” – “hide” the details of the algorithms – drawback: hard to keep secret if cipher is used widely, or implementation can be reverse engineered • Alternative: publish the algorithms – fewer vulnerabilities will result if many smart people try and fail to break the cipher – security of the cipher depends on the secrecy of the keys, instead CSC/ECE 574 Dr. Peng Ning 4 Computer Science Secrets? (Cont’d) • Commercial world relies upon standardized, public algorithms, and secret keys • Government tends to also rely on secret algorithms CSC/ECE 574 Dr. Peng Ning 5 Computer Science Secret Key Cryptography • Same key is used for both encryption and decryption – this one key is shared by two parties who wish to communicate securly • Also known as symmetric key cryptography, or shared key cryptography CSC/ECE 574 Dr. Peng Ning 6 plaintext Encryption ciphertext Decryption plaintext keyComputer Science Applications of Secret Key Crypto • Communicating securely over an insecure channel – Alice encrypts using shared key – Bob decrypts result using same shared key • Secure storage on insecure media – Bob encrypts data before storage – Bob decrypts data on retrieval using the same key CSC/ECE 574 Dr. Peng Ning 7 Computer Science Applications… (Cont’d) • Message integrity – Alice computes a message integrity code (MIC) from the message, then encrypts with shared key – Bob decrypts the MIC on receipt, and verifies that it agrees with message contents • Authentication – Bob can verify Alice sent the message – how is that possible? CSC/ECE 574 Dr. Peng Ning 8 Computer Science Generic Block Encryption • Converts one input plaintext block of fixed size k bits to an output ciphertext block also of k bits • Benefits of large k? of short k? CSC/ECE 574 Dr. Peng Ning 9 block 0 Encryption key block 1 block 2 … block 0 block 1 block 2 … plaintext ciphertextComputer Science Key Sizes • Keys should be selected from a large potential set, to prevent brute force attacks • Secret key sizes – 40 bits were considered adequate in 70’s – 56 bits used by DES were adequate in the 80’s – 128 bits are adequate for now • If computers increase in power by 40% per year, need roughly 5 more key bits per decade to stay “sufficiently” hard to break CSC/ECE 574 Dr. Peng Ning 10 Computer Science Notation Notation Meaning X ⊕ Y Bit-wise exclusive-or of X and Y X | Y Concatenation of X and Y K{m} Message m encrypted with secret key K CSC/ECE 574 Dr. Peng Ning 11 Computer Science Two Principles for Cipher Design • Confusion: – Make the relationship between the <plaintext, key> input and the <ciphertext> output as complex (non-linear) as possible • Diffusion: – Spread the influence of each input bit across many output bits CSC/ECE 574 Dr. Peng Ning 12Computer Science Exploiting the Principles • Idea: use multiple, alternating permutations and substitutions, e.g., – SPSPS… – PSPSP… • Do they have to alternate? e.g…. – SSSPPPSS…?? • Confusion is mainly accomplished by substitutions • Diffusion is mainly accomplished by permutations • Example ciphers: DES, AES CSC/ECE 574 Dr. Peng Ning 13 Computer Science Secret Key… (Cont’d) • Basic technique used in secret key ciphers: multiple applications of alternating substitutions and permutations CSC/ECE 574 Dr. Peng Ning 14 plaintext S P S P S ciphertext … key … Well-known examples: DES, AES Computer Science Basic Form of Modern Block Ciphers CSC/ECE 574 Dr. Peng Ning 15 Plaintext block Key Preprocessing Postprocessing Ciphertext block Rounds of Encryption i=1,2,…,n Sub-Key Generation Sub-Key #1 Sub-Key #2 Sub-Key #3 … Sub-Key #nComputer Science Feistel Ciphers CSC/ECE 574 Dr. Peng Ning 16 Computer Science Overview • Feistel Cipher has been a very influential “template” for designing a block cipher • Major benefit: can do encryption and decryption with the same hardware • Examples: DES, RC5 CSC/ECE 574 Dr. Peng Ning 17 Computer Science One “Round” of Feistel Encryption 1. Break input block i into left and right halves Li and Ri 2. Copy Ri to create output half block Li+1 3. Half block Ri and key Ki are “scrambled” by function f 4. XOR result with input half-block Li to create output half-block Ri+1 CSC/ECE 574 Dr. Peng Ning 18 Li Ri Input block i f Ki ⊕ Li+1 Ri+1 Output block i+1Computer Science One “Round” of Feistel Decryption • Just reverse the arrows! CSC/ECE 574 Dr. Peng Ning 19 Li Ri Output block i+1 f Ki ⊕ Li+1 Ri+1 Input block i Computer Science Complete Feistel Cipher: Encryption CSC/ECE 574 Dr. Peng Ning 20 Ciphertext (2w bits) … Ln Rn Ln+1 Rn+1 note this final swap! f Round 1 K1 ⊕ f … Round i K2 L2 R2 ⊕ f Round n Kn ⊕ Plaintext (2w bits) L0 R0 Computer Science Feistel Cipher: Decryption CSC/ECE 574 Dr. Peng Ning 21 f f f Ciphertext (2w bits) Plaintext (2w bits) … … Round 1 Round i Round n Kn Kn-1 K1 L0 R0 L2 R2 Ln Rn Ln+1 Rn+1 ⊕ ⊕ ⊕ note this final swap!Computer Science Parameters of a Feistel Cipher • Block size • Key size • Number of rounds • Subkey generation algorithm • “Scrambling” function f CSC/ECE 574 Dr. Peng Ning 22 Computer Science Comments • Decryption is same as encryption, only reversing the order in which round keys are applied – Reversability of Feistel cipher derives from reversability of XOR • Function f can be anything – Hopefully something easy to compute – There is no need to invert f CSC/ECE 574 Dr. Peng Ning 23 Computer Science DES (Data Encryption Standard) CSC/ECE 574 Dr. Peng Ning 24Computer Science DES (Data Encryption Standard) • Standardized in 1976 by NBS – proposed by IBM, – Feistel cipher • Criteria (official) – provide high level