Network Security - Lecture 15

Network SecurityLecture 15Presented by: Dr. Munam Ali Shah Part 2 (c)Symmetric Key CryptographySummary of the previous lectureWe had a discussion on block cipher and stream cipher. We discussed in detail the symmetric key cryptography.We explored Feistel Cipher and its structure The DES was also discussed in detail Feistel CipherThe plaintext is divided into two halves The two halves pass through n rounds of processing then combine to produce the cipher block.Each round has as input and derived from the previous round as well as a sub-key derived from the overall All rounds have the same structureA substitution is performed on the left half of the data. This is done by applying a round function F to the right half of the data followed by the XOR of the output of that function and the left half of the data.Design Features of Feistel NetworkBlock Size: (larger block means greater security) 64 bits.Key Size:56-128 bits.Number of Rounds: a single round offers inadequate security, a typical size is 16 rounds.Sub-key Generation Algorithms: greater complexity should lead to a greater difficulty of cryptanalysis.Round function: Again, greater complexity generally means greater resistance to cryptanalysis.A simple way to represent DESClassical Feistel NetworkOutlines of today’s lectureBlock Cipher Principles We will explore the limitations of DESAnother symmetric key cryptography that is Advanced Encryption Standard (AES) will also be discussed. ObjectivesYou would be able to present an understanding of Symmetric Key Cryptography.You would be able use understand the phases involved in DES.Block Cipher PrinciplesMost symmetric block ciphers are based on a Feistel Cipher StructureInput: n bits plaintext block Output: n bits ciphertext blockFor 2 bits, there are 2n possible plaintext blockReversible mappingPlaintext Ciphertext0011011010001101Irreversible mappingPlaintext Ciphertext0011011010001110Ideal Block Cipher12Ideal Block Cipher: Practical problemSmall block size e.g. n = 4 is used => equivalent to classical substitution cipherVulnerable to statistical analysis attackWeakness is not in substitution but rather in small block sizen should be sufficiently large and substitution is reversible then Statistical characteristics of plaintext are masked so that cryptanalysis is infeasible13Ideal block cipher: key lengthMapping from plaintext to ciphertext constitutes the keyFor n = 4, the required length of key is 4 bits x 2n rows = 64 bitsFor n = 64, the required key length is 64 x 264 = 270 14Advanced Encryption StandardA new standard was needed primarily because DES has a relatively small 56-bit key which was becoming vulnerable to brute force attacks. In addition, the DES was designed primarily for hardware and is relatively slow when implemented in software. While Triple-DES avoids the problem of a small key size, it is very slow even in hardware; it is unsuitable for limited-resource platforms; and it may be affected by potential security issues connected with the (today comparatively small) block size of 64 bits.Origins: AESClearly a replacement for DES was neededhave theoretical attacks that can break ithave demonstrated exhaustive key search attackscan use Triple-DES – but slow, has small blocksUS NIST issued call for ciphers in 199715 candidates accepted in Jun 98 5 were shortlisted in Aug-99 Rijndael was selected as the AES in Oct-2000Issued as FIPS PUB 197 standard in Nov-2001 16AES RequirementsPrivate key symmetric block cipher 128-bit data, 128/192/256-bit keys Stronger & faster than Triple-DES Active life of 20-30 yearsProvide full specification & design details Both C & Java implementations AES Evaluation CriteriaSecurityEffort required to crypt-analyze an algorithmSince key size is 128 bits so cryptanalysis other than brute force is considered CostMust have high computational efficiencyAlgorithm and implementation characteristicsSuitable for software and hardware implementation Simplicity: which will make an analysis of security more straightforwardThe AES Cipher - Rijndael Designed by Rijmen and Daemen in Belgium has 128/192/256 bit keys, 128 bit data processes data as block of 4 columnsoperates on entire data block in every rounddesigned to be:resistant against known attacksspeed and code compactness on wide range of platformsdesign simplicityOverviewOpen call for the algorithm by NISTStandardized in May 26, 2002Winner: Rijndael algorithmDeveloped by two Belgian CryptographersDr. Joan Daemen Dr. Vincent Rijmen3DES ProblemsIn-efficientUsed only 64 bit blockFixed block size of 128 bitsKey size of 128, 192 or 256 bitsAES StagesFour stages of AES: (Permutation, Substitution)Substitute Byte : Each byte of the block is replaced by its substitutionShift Rows : 1-byte circular shift is performedMix columns : each byte of a column is mapped in to a new value. Add round key: The block is XOR with subkeyAES StructureFor Both encryption and decryption the cipher begins withAn add round key stageNine rounds that each include four stagesTenth round of three stages (excluding mix columns)231- Substitute Byte TransformationAES defines a 16 x 16 matrix of byte values called S-box.Each individual byte of the state is mapped into new byte as followsLeftmost 4 bits are used as row valueRight most 4 bits are used as column valuesNote: rows and column values serve as indexes into the S-box to a selected 8-bit value2- Shift Row Transformation2587F24D97EC6E4C904AC346E78CD895A687F24D976E4C90EC46E74AC3A68CD895First row in the state is not altered1 byte circular shift is performed for second row2 byte cicular shift is performed with third row3 byte circular shift is performed with fourth rowForward shift row transformation --- left shiftInverse shift row transformation --- right shift3- Mix Column TransformationEach byte (new) in the column is a function of all four bytes in the columnEach 128 bit block would be multiply withEach element in the product matrix is the sum of the product of the elements of one row and column of other matrix.Multiplication with 2 is one bit left shiftIf leftmost bit of original value is 1, a bitwise XOR with 0001 1011 will be performed020301010102030101010203030101024- Add Round key128 bits of the block are XORed with 128 bits of round key4740A34C37D4709F94E43A42EDA5A6BCAC19285777FAD15C66DC2900F321416AEB598B1B402EA1C3F23813421E84E7D2=Key expansion algorithm takes input 4 words (16 byte) and produce 44 words (156 byte)4 words round key is used for each round.AES ProcessAdd round keySubstitute byteShift rowsMix columnsAdd round keySubstitute byteShift rowsAdd round keyInitial round9 roundsfinal roundsPlain textCipher textCipher keyRound keyRound keyKey Expansion 1/2Input is cipher key = 128 bits = 16 bytes = 4 words Output = 1248 bits = 156 bytes = 44 wordsThe key expansion algorithm reduced cryptoanalysis attacks, it eliminates the symmetry.Cipher key is used in initial round.Cipher ExampleInput = 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34Cipher Key = 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3cRoundNumberStart ofRoundAfterSub BytesAfterShift RowsAfterMix ColumnsRound KeyValue==3243f688a85a8d30319831a237e007342b7e152816aea6d2f78815ab09cf4f32392584021ddcfb09dc8511976a190b32193de3a0bef42be29a8dc62af8e94808d42711e0aebff198b85db4e5411e5230d42711e0aebff198b85db4e5411e5230046681e0e5cb9a1948d3f87a0628264ca0fafe881754b12c2339a3396c2a7605a49c7f68f29f2b356bea5b436a025049Input1st2ndOutput10theb40f2591e2e84388b13a1e7c31b42d2e90989cb72315f073d7d32942eaf2cb5e90989cb72315f073d7d32942eaf2cb5d014f9c9a8ee8925e10c3fc863b60ca6Implementation Aspectscan efficiently implement on 8-bit CPUbyte substitution works on bytes using a table of 256 entriesshift rows is simple byte shiftadd round key works on byte XOR’smix columns requires matrix multiply in GF(28) which works on byte values, can be simplified to use table lookups & byte XOR’sImplementation Aspectscan efficiently implement on 32-bit CPUredefine steps to use 32-bit wordscan precompute 4 tables of 256-wordsthen each column in each round can be computed using 4 table lookups + 4 XORsat a cost of 4Kb to store tablesdesigners believe this very efficient implementation was a key factor in its selection as the AES cipherSummary of today’s lectureWe discussed the Block Cipher Principles We also explored the limitations of DESAnother symmetric key cryptography that is Advanced Encryption Standard (AES) will discussed in detail .Next lecture topicsOur discussion on symmetric key cryptography will continue and we will see some example of stream ciphers such as RC4.The End