Slide 1MenuPermutation CipherKey Space8! MessagesFeistel Cipher RecapDESDES AlgorithmDES’s FS-BoxesDES AvalancheKey ScheduleDES KeysIs DES a perfect cipher?Attacking DES: Brute ForceBrute Force AttacksMultiple EncryptionSlide 18Double-VigenèreSlide 20Double DESKnown Plaintext AttackMeet-in-the-Middle AttackHmmm…maybe thrice?2-Key Triple DESHow secure is Triple-DES3-Key Triple DESCracking DES (1998)Cracking DES (2001)Cracking DES (2005)POWER ANALYSIS ATTACKSThe ProblemThe Power consumption side-channelDPA attack on DESDES attack contd.S[k] with Correct GuessS[k] with Incorrect GuessSubkey for SBOX-5Existing CountermeasuresSlide 40Suppression circuitResult of SuppressionDPA on Protected DeviceChargeDavid Evanshttp://www.cs.virginia.edu/evansCS588: Security and PrivacyUniversity of VirginiaComputer ScienceLecture 6: Striving for ConfusionStructures have been found in DES that were undoubtedly inserted to strengthen the system against certain types of attack. Structures have also been found that appear to weaken the system.Lexar Corporation, “An Evalution of the DES”, 1976.8 February 2005 University of Virginia CS 588 2Menu•PS1 Question 4b –Will return PS1 Thursday•DES•Strengthening DES•Breaking DES8 February 2005 University of Virginia CS 588 3Permutation CipherHow much information can be transmitted with perfect secrecy using symbols from the English alphabet (26 letters) with a transposition cipher with block size 8 and a permutation chosen randomly from all possible permutations?8 February 2005 University of Virginia CS 588 4Key Space1 2 3 4 5 6 7 8Random Permutation8! KeysPerfect Cipher Keyspace Theorem:Cannot transmit more than 8! different message securely8 February 2005 University of Virginia CS 588 58! MessagesM = { ABCDEFGH, BACDEFGH, CABDEFGH, DABCEFGH, EABCDFGH, … }Why couldn’t youalso includeIJKLMNOP?What if therewere only 2 alphabetsymbols?(Note: can transmit as many blocks as you want)Midterm Question8 February 2005 University of Virginia CS 588 6Feistel Cipher RecapPlaintextRoundL0R0FK1L1R1Last time:- Decryption works, as long as the keys are used in reverse order- Can provide confusion and diffusion (because of permutation), but only if F is confusingSubstitutionPermutation8 February 2005 University of Virginia CS 588 7DES•NIST (then NBS) sought standard for data security (1973)•IBM’s Lucifer only reasonable proposal•Modified by NSA–Changed S-Boxes–Reduced key from 128 to 56 bits•Adopted as standard in 1976•More bits have been encrypted using DES than any other cipher8 February 2005 University of Virginia CS 588 8DES Algorithm•Feistel cipher with added initial permutation•Complex choice of F•16 rounds•56-bit key, shifts and permutations produce 48-bit subkeys for each round8 February 2005 University of Virginia CS 588 9DES’s FExpand and Permute (using E table)32 bits48 bitsKnSubstitute (using S boxes)32 bitsPermutationThe goal is confusion!8 February 2005 University of Virginia CS 588 10S-BoxesS-Box6 bits4 bitsExample: 1100111001Critical to securityNSA changed choice of S-BoxesOnly non-linear step in DES64 entry lookup tableE(11)  E(01) + E(10)8 February 2005 University of Virginia CS 588 11DES AvalancheInput: ...............................................................* 1 Permuted: .......................................*........................ 1Round 1: .......*........................................................ 1Round 2: .*..*...*.....*........................*........................ 5Round 3: .*..*.*.**..*.*.*.*....**.....**.*..*...*.....*................. 18Round 4: ..*.*****.*.*****.*.*......*.....*..*.*.**..*.*.*.*....**.....** 28Round 5: *...**..*.*...*.*.*.*...*.***..*..*.*****.*.*****.*.*......*.... 29Round 6: ...*..**.....*.*..**.*.**...*..**...**..*.*...*.*.*.*...*.***..* 26Round 7: *****...***....**...*..*.*..*......*..**.....*.*..**.*.**...*..* Round 8: *.*.*.*.**.....*.*.*...**.*...*******...***....**...*..*.*..*... Round 9: ***.*.***...**.*.****.....**.*..*.*.*.*.**.....*.*.*...**.*...** Round 10: *.*..*.*.**.*..*.**.***.**.*...****.*.***...**.*.****.....**.*.. Round 11: ..******......*..******....*....*.*..*.*.**.*..*.**.***.**.*...* Round 12: *..***....*...*.*.*.***...****....******......*..******....*.... Round 13: **..*....*..******...*........*.*..***....*...*.*.*.***...****.. Round 14: *.**.*....*.*....**.*...*..**.****..*....*..******...*........*. Round 15: **.*....*.*.*...*.**.*..*.*.**.**.**.*....*.*....**.*...*..**.** Round 16: .*..*.*..*..*.**....**..*..*..****.*....*.*.*...*.**.*..*.*.**.* Output: ..*..**.*.*...*....***..***.**.*...*..*..*.*.*.**.*....*.*.*.**. Source: Willem de Graaf, http://www-groups.dcs.st-and.ac.uk/~wdg/slides/node150.html8 February 2005 University of Virginia CS 588 12Key Schedule•Need 16 48-bit keys–Best security: just use 16 independent keys–768 key bits•56-bit key used (64 bits for parity checking)–Produce 48-bit round keys by shifting and permuting8 February 2005 University of Virginia CS 588 13DES KeysKi = PC (Shift (Left (Ki-1)) || Shift (Right (Ki-1)))KeyShift (1 or 2 bits)Shift (1 or 2 bits)56 bits28 bits28 bitsCompress/PermuteKnNext roundAre there any weak keys?8 February 2005 University of Virginia CS 588 14Is DES a perfect cipher?•No: more messages than keys•Even for 1 64-bit block 264 messages > 256 keys8 February 2005 University of Virginia CS 588 15Attacking DES: Brute Force•Key is 56 bits•256 = 7.2 * 1016 = 72 quadrillion•Try 1 per second = 9 Billion years to search entire space•Distributed attacks–Steal/borrow idle cycles on networked PCs–Search half of key space with100000 PCs * 1M keys/second in 25 days8 February 2005 University of Virginia CS 588 16Brute Force Attacks•RSA DES challenges:–1997: 96 days (using 70,000 machines)–Feb 1998: 41 days (distributed.net)8 February 2005 University of Virginia CS 588 17Multiple Encryption8 February 2005 University of Virginia CS 588 18Multiple Encryption•C = EK2 (EK1 (P))•Does it double the key space?•Monoalphabetic cipher Ci = K2[K1[Pi]] = K3[Pi] for some K38 February 2005 University of Virginia CS 588 19Double-VigenèreC = EK2 (EK1 (P)) Vigenère: Ci = (Pi + Ki mod N) mod Z Ci = ((Pi + K1i mod N1 mod Z) + K2i mod N2) mod Z = (Pi + K1i mod N1 + K2i mod N2 ) mod Zif N1 = N2: = (Pi + K3i mod N) mod Z (K3 = K1 + K2)what if N1  N2?8 February 2005 University of Virginia CS 588 20Double-Vigenère•K1 =