CSC 316 Chapter 2e, Spring 2004

Chapter 2 Encryption Algorithms (Part E) V. Sawma, Computer Security 2 Outline NP-completeness & Encryption Symmetric (secret key) vs Asymmetric (public key) Encryptions Popular Encryption Algorithms  DES  AES  RSA Encryption  El Gamal Algorithms Hashing Algorithms V. Sawma, Computer Security 3 ADVANCED ENCRYPTION STANDARD V. Sawma, Computer Security 4 • U.S. government has selected to replace the current Data Encryption Standard with Advanced Encryption Standard . • The National Institute of Standards and Technology (NIST) in October selected Rijndael (pronounced "rain doll"), the combined work of Vincent Rijmen and Joan Daemen, as the basis for AES. • Rijndael was selected from among five finalists in a process that took more than three years. Some Facts V. Sawma, Computer Security 5 Although a fundamentally sound algorithm, the older DES, which dates back to the 1970s, has been proven to be breakable through brute-force attacks because it uses a relatively small key size (56 bits). Some Facts(contd.) V. Sawma, Computer Security 6 AES vs. Triple-DES AES Triple-DES Type of algorithm Symmetric, block cipher Symmetric, feistel cipher Key size (in bits) 128, 192, 256 112 or 168 Speed High Low Time to crack (assume a machine could try 255 keys per second — NIST) 149 trillion years 4.6 billion years Resource consumption Low Medium NIST standard number FIPS PUB 197 FIPS 46-3 AES vs. Triple DES The big differentiators between AES and Triple-DES are not strength of security, but superior performance and better use of resources. V. Sawma, Computer Security 7 Rijndael - The Proposed Algorithm • Block cipher with a variable block length and a variable key length. • The block length and the key length can be independently chosen as 128, 192 or 256 bits. • The block to which the operations are applied is called a state. • A state is organized as an array of bytes (8 bits) with four rows. The number of columns is equal to the block length divided by 32. V. Sawma, Computer Security 8 Rijndael - The Proposed Algorithm(contd.) The Cipher Key is organized in the same form. E.g., for a state with 192 bits the array looks like this: V. Sawma, Computer Security 9 Like DES, Rijndael consists of a number of equivalent rounds. The number of rounds depends on the used block and key lengths according to the following table. Rijndael - The Proposed Algorithm(contd.) V. Sawma, Computer Security 10 The Process Stages Initial round: Add round key Intermediate rounds: Byte Sub, Row Shift, Mix Column, Add round key Final round: Byte Sub, Row Shift, Add round key V. Sawma, Computer Security 11 The Round Transformation The transformation in each round is composed of four different transformations in the following order: Byte substitution Row shifting (ShiftRow) Column mixing (MixColumn) Round key addition (AddRoundKey) V. Sawma, Computer Security 12 This is a non-linear byte substitution realized by an 8- to-8 S-Box. It is executed on each byte (cell) in a state. Byte substitution V. Sawma, Computer Security 13 S – Box V. Sawma, Computer Security 14 The four rows of the state are cyclically shifted over different offsets. Row shifting (ShiftRow) V. Sawma, Computer Security 15 In this step every column of a state is transformed using a matrix multiplication. Column mixing (MixColumn) V. Sawma, Computer Security 16 A round key is applied to the state by a bitwise XOR. Round key addition (AddRoundKey) V. Sawma, Computer Security 17 The complete Rijndael Encryption consists of •An initial round key addition, • Several rounds of ByteSub, ShiftRow, MixColumn, AddRoundKey, • And a final round of ByteSub, ShiftRow and AddRoundKey. The Encryption Algorithm V. Sawma, Computer Security 18 • The inverse of a round is given by AddRoundKey, InvMixColumn, InvShiftRow and InvByteSub. • The inverse of a final round is given by AddRoundKey, InvShiftRow and InvByteSub. • A final AddRoundKey has to be done. The Decryption Algorithm