Cryptography -- Block CiphersOverviewA few termsSymmetric ciphersBackgroundBasis of modern ciphersShannon’s strategyShannon’s building blocksSlide 9S-box (substitution)P-box (permutation)S-P networksFeistel cipherSlide 14Slide 15Feistel cipher dependenciesFeistel decryptionHistory of DESDES CharacteristicsSlide 20DES cipherSlide 22Key propertyDES controversyDES statusCryptanalysis of DES1997 breakSlide 28Model for cryptography-revisitCryptography -- Block CiphersAnita JonesCS451 Information SecurityCopyright(C) Anita JonesSeptember, 2006 Overviewterms and principlesClaude ShannonFeistel cipherDESSeptember, 2006 A few termsblock cipher block of plaintext is treated as a whole & used to produce a ciphertext block of equal length typical size: 64 bitsmost modern ciphers are block ciphersstream cipher digital data is encrypted one bit (or one unit) at a time In both cases, plaintext is transformed incrementallySymmetric ciphersSymmetric implies ONE keySecret key shared by sender & receiverSeptember, 2006 Backgroundideally want one extremely large substitution not practical since would need a table with 264 entries in it for a 64-bit block so approximate the ideal by constructing from smaller building blocksSeptember, 2006 Basis of modern ciphersClaude Shannon (‘45) - information theoryproduct cipherperform two or more ciphers in sequence so that result (product) is cryptographically stronger than any component cipheralternate confusion & diffusionvirtually all significant symmetric block ciphers currently in use are of this typeSeptember, 2006 Shannon’s strategythwart cryptanalysis that is based on statistical analysishacker has some knowledge of statistical characteristic of plaintextif statistics are reflected in ciphertext, then analyst may be able to deduce encryption key, or part of itin Shannon’s ideal cipher, statistics of ciphertext are independent of plaintextSeptember, 2006 Shannon’s building blocksconfusionmake relation between statistics of ciphertext and the value of the encryption key as complex as possiblediffusiondiffuse statistical property of plaintext digit across a range of ciphertext digitsi.e. each plaintext digits affects value of many ciphertext digitsSeptember, 2006 Shannon’s building blocksShannon proposed product ciphers with two components S-Boxes -- substitutionproviding confusion of input bits P-Boxes -- permutationproviding diffusion across S-box inputsn rounds of S-P boxesSeptember, 2006 S-box (substitution)012345673 bitinput01001234567 1103 bitoutputWord size of 3 bits => mapping of 23 = 8 valuesNote: mapping can be reversedSeptember, 2006 P-box (permutation)4 bitinput1101101111011011Example 1 Note: reversibleExample 2 - swap twohalves of inputSeptember, 2006 S-P networksalternate S and P boxesBUT, in practice we must decrypt as well as encryptso define the sequence of boxes so that precisely the same system will decrypt as well as encryptjust run it backwardsSeptember, 2006 Feistel cipherinput plaintext of 2w bits key K = n sub-keys: K1, K2, …, Knsequence of n “rounds” each using Kisubstitution followed by a permutationapply function F(Ki) to right half of data, then exclusive-OR it to left half of datapermutation: interchange two result halves of dataDES is essentially a Feistel cipherSeptember, 2006 Feistel cipherMultiple roundsround i input is Li-1, Ri-1Li = Ri-1Ri = (Li-1 XOR F(Ri-1 , Ki))L – left portion of intermediate dataR – right …..plaintext (2w bits)w bits w bitsL0R0Round 1K1L1R1F+KnLnRnF+Round n. . .. . .Ln+1Rn+1ciphertext (2w bits)September, 2006 Feistel cipher dependenciesblock size – increasing size increases security – 64 bits commonkey size – increasing size improves security, – 128 bits commonnumber of rounds – 16 is typicalsubkey generation – complex generation makes cryptanalysis harderround function – complex function is stronger… but all increases slow the implementationSeptember, 2006 Feistel decryptionsame as encryption, exceptciphertext is inputuse keys in reverse orderat each round the output is equal to the corresponding value of the encryption process with the two halves of the value swappedfinal permutation (swap) realigns 2 halvesSeptember, 2006 History of DESDES – Data Encryption StandardHorst Feistel at IBM developed LUCIFERabout 1971, sold to Lloyds of LondonNat’l Bureau of Standards issued request for national cipher standardIBM submitted (refined) LUCIFERNSA worked with IBM to refine cipheradopted in 1977 by Nat’l Bureau of Stds.September, 2006 DES CharacteristicsPlaintext is 64 bits long16 roundsKey length is 56 bits16 sub-keys generated, one used in each roundDES algorithm is a variant of the Feistel algorithmplaintext (64 bits)init permutation round 1K1 round 2K2 round nKninverse permutationciphertext (64 bits)32 bit swap56 bit key. . .permuteleft circ shiftpermleft circ shiftpermleft circ shiftperm. . .September, 2006 DES cipherround i input is Li-1, Ri-1Li = Ri-1Ri = (Li-1 XOR F(Ri-1 ,Ki))<----32 bits------>Li-1 exp/perm to 48 S-boxpermutationRi-1<----32 bits------>xKixLiRi--- 48 bits--- 48 bits--- 32 bits--- 32 bitsOne DES RoundSeptember, 2006 Key propertyavalanchesmall change in plaintext or in key produces significant change in ciphertexttest for avalancheencrypt two plaintext blocks that differ only in one bitabout half the (ciphertext) bits will differSeptember, 2006 DES controversyDES choice was intensely criticized:original LUCIFER key length was 128 bits, and DES used 56 bit key (to fit on chip, they said)critics feared brute force attacksdesign criteria for the S-boxes was classified, so users not sure that internal structure was free of hidden weak points that might let NSA break cipherSeptember, 2006 DES statusno weak points have surfacedDES is widely used1994, NIST reaffirmed DES for federal use NIST recommends DES use for all except classified informationgenerally considered a sound standardNeed more security: use Triple DESFuture: Adv.d Encryption Standard (AES)September, 2006 Cryptanalysis of DESincreased computing speed has made a 56 bit key susceptible to exhaustive key searchdemonstrated breaks: 1997 – taking a few months, a large