### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# CS 5788 CS 5788

UVA

GPA 3.71

### View Full Document

## 21

## 0

## Popular in Course

## Popular in ComputerScienence

This 55 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 5788 at University of Virginia taught by David Evans in Fall. Since its upload, it has received 21 views. For similar materials see /class/209645/cs-5788-university-of-virginia in ComputerScienence at University of Virginia.

## Reviews for CS 5788

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15

Lecture 7 Key Distribution The era of electronic mailquot Potter1977 may soon be upon us we must ensure that two important properties ofthe current paper mailquot system are preserved a messages are private and b messages can be 539 ned R Rivest A Shamir and L Adleman A Method for Obtaining Digital Signatures and PublicKey Cryptosystems Communications of the ACM January 1978 The original RSA paper i C5588 Security and Privacy 1 iv39 University ofVirginia David Evans puter Science http VWWV cs virginia EduEvans Traditional Cryptology Given a secure channel to transmit a shared secret key symmetric cryptosystems amplify and timeshift that channel Can transmit bigger secrets over an insecure channel except onetime ad Can transmit later secrets over an insecure channel But the initial secure channel is required tgsevtzum Unweis vatVilviniaES EE 2 Key Distribution All the cryptosystems we have seen depend on two parties having a shared secret Distributing secret keys is hard and expensive Can two people communicate securely without having to meet first and establish a key tgsevtzum Unweis vatVilviniaES EE a Trust a Third Party Keys R Us knows KA KE enerates random KAB Alic E Bob KA E Kiai Ki E gt E M K B b Alice How can Alice and Bob securely provide their keys to Keys R Us tgsevtzum Unweis vatVilviniaES EE 4 Merkle s Puzzles Ralph Merkle 1974 Alice generates 220 messages This is puzzle x The secret is y x and y are random numbers Encrypts each message using symmetric cipher with a different key Sends all encrypted messages to Bob tgsevtzum Unweis vatVilviniaES EE 5 Merkle s Puzzles cont Bob chooses random message performs bruteforce attack to recover plaintext and secret y Bob sends x clear to Alice Alice and Bob usey to encrypt messages tgsevtzum Unweis vatVilviniaES EE a Is this secure Alice symmetric cipher DES 255 expected brute force work to break DES Eve has to breakthe 22 to nd which one matches x 2la 255 expected work Alice and Bob change keys frequently enough since it is less work to agree to a new key Why not increase number of puzzle messages 195epi2uu1 Unweis yatVilvimaES ES Padlocked Boxes Alice 195epi2uu1 Unweis yatVilvimaES EE Padlocked Boxes EAM Ali lock Alice N Alice s Padlock Key 195epi2uu1 Unweis yatVilvimaES ES Padlocked Boxes Alice s Padlock Key 195epi2uu1 Unweis yatVilvimaES EE Padlocked Boxes Alice Alice s Padlock Key Bob s Padlock Key 195epi2uu1 Unweis yatVilvimaES ES M Padlocked Boxes N Bob Bob s Padlock Key Alice s Padlock Key 195epi2uu1 Unweis yatVilvimaES EE 2 Padlocked Boxes DAEEEAM EEUW 9 Alice g N Bob Bob s Padlock Key N Alice s Padlock Key gsmzum Unweis vatvuvlmacs 13 Padlocked Boxes Alice N Bob s Padlock Key gsmzum Unweis vatvuvlmacs 4 Padlocked Boxes 6 Bob s Padlock Key gsmzum Unweis vatvuvlmacs 15 AnalUEv due tn Slmun swam The Code Book Secret Paint Mixing Alice Yellow paint public E CE Yello d g Eve K Yellow Red Purple K Yellow Purple Red gsmzum Unweis vatvuvlmacs a Birth of Public Key Cryptosystems 1969 ARPANet born 4 sites Whit eld DilTIe starts thinking about strangers sending messages securely I 1974 Whitfield Dif e gives ta k at IBM lab Audience member mentions that Matrin Hellman Stanford prof had spoke about key distribution That night Dif e starts driving 5000km to Palo Alto Dif e Hellman and Ralph Merkle work on key distribution problem gsmzum Unweis vatvuvlmacs 7 We stand today on the brink of a revolution in cryptography The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote cash dispensers and computer terminals In turn such applications create a need for newt s of cryptographic systems which minimize the necessity of secure key distribution channels and su p y he equivalent of a written signature At the same time theoretical developments in information theo a computer science show promise of providing provably secure cryptosystems changing this ancient art into a science Diflie and Hellman November 1976 manual Unweis vatvuvlmacs 1a DiffieHellman Key Agreement 1 Choose public numbers q large prime number uprimitive root ofq 2 Agenerates random XAand sends B A 0 q 3 B generates random XB and sends A YB on XE mod q 4 A calculates secret key K YB XAmod q 5 B calculates secret key K YA XE mod q 952mm Unweis vatVilvimaES EE Q What s a primitive root on is a primitive root ofq if for all lg n ltq there is some m 1 g m ltq such that on n mod q Given on n and qcan we solve for m Yes there is only one possible In But it might be hard to nd Discrete logarithm given on n andqfind 0 S m ltq SUCh that on n modq 952mm Unweis vatvuvimacs 2n Example at isa primitive root forq11 21 2 2 26 64 2 9 22214 271282117 23 2 8 28 256 2 3 24162115 29512 2116 25 32310 2101024 1 711 952mm Unweis vatVilvimaES EE 21 Finding Primitive Roots Theorem All prime numbers have primitive roots Book proves this using Proof by Forward Reference Prodlaterquot p 137 and this will beproven later p 230 which will be proven only late p 231 which is known to existquot p 445 We ll use the same technique In practice it is easy to nd primitive roots for prime mbers by guessing Almost 12 of guesses will work next class we will see why 952mm Unweis vatvuvimacs 22 DiffieHellman Example 1 Choose public numbers q large prime number ugenerator mod q q 1 7 2 A generates random XAand sends B YA 06 mod q XA4 YA 24mm 11 16mod 11 5 3 B generates random XB and sends A YB on XE mod q XB6 YB2 mod 11 64mod 11 9 Empmmm91mm WWW m MWm autumn 952mm Unweis vatVilvimaES EE 21 DiffieHellman Example cont q 11 112 YA5 XE 6 YB9 4 A calculates secret key K YBXA modq K 94mm 11 6561 mod 11 5 5 B calculates secret key K YAXB mod I K55mod1115625mod115 952mm Unweis vatvuvimacs 24 Is it magic Things to Prove 1 They generate the same keys K YB XA mod q YA XE modq 2 An eavesdropper cannot find Kfrom any transmitted value 1 0 YA YB 952mm Unweis yatVilvimaES ES 25 1 Keys Agree Prove K YBXA modq YAXB mod q YRXAmod q Y XB mod q t 0cXE mod qXA mod q 0cXA mod qXE mod q 083XA mod q 0899593 mod q XBXAmodq XAXB modq QED 952mm Unweis yatVilvimaES EE 2a Modular Exponentiation amodqjl modq abmodq 7 mod 6Zmod67zmod6 Izmod649mod6 Proof by example 952mm Unweis yatVilvimaES ES 27 Modular Exponentiation First prove a bmodq amodq bmodqmodq Then by induction amod quodq abmodq since ab a abquot and a1 a 952mm Unweis yatVilvimaES EE 2a Modular Arithmetic abmodnx xnd0ab xab7nd0 amodnygtyaind1 bmodnz gtzb7 nd2 amod n b modn modn a7 nd1 b7nd2modn aband2 7b nd1nd1nd2modn abmodn all terms with n areOmodn 952mm Unweis yatVilvimaES ES 2g 2 Secure from Eavesdropper An eavesdropper cannot nd K YBXAmod q YAXB mod q from any transmitted value q on YA oLXAmod q YB on XEmod q Attacker needs to solve YA 06 mod q for XA Finding discrete logarithms is probably hard Best known algorithm eltlt1nql31n1nqZ3 952mm Unweis yatVilvimaES EE cm Secure from Active Secure from Active Eavesdropper Eavesdropper Public q on r 39 Y oLXAmod q DLXA mod N Bob Bob Y on XE mod Alice Erq39 Public q on Alice Secret XB Secret XB Secret XA YB 1 XE mod Secret XA YB a XE mod q X KAE YEyAmOd 1 K YBXAm0d q K YA B mOd q KEB YEXB mOd 1 Secret XE DiffieHellman Use PublicKey Cryptography Same paper introduced concept of SSL PublicKey Cryptography Cisco encrypting routers Public algorithm E Sun secure RPC Private algorithm D etc ldentityi EDmDEmm Secure cannot determine E from D But didn t know how to find suitable E and D lgsevtzuul Unwtlsnmwvml saaa as lQSethuul Unwtlsnmwvml saaa 34 Knapsack Ciphers Merkle Hellman 78 Knapsack Problem Message x1 x bit vector Given positive integers a1 a2 a and a Knapsack Vector a a1 an positive integer I find a subset ofas that sum Ciphenext b xlal 2 12 x a to b Decrypt by finding subset ofa s that sum to In general this is NP complete b M l essa e blts corres ondln to s are 1 Can try 2quot possible subsets check each one in g p g I Encryption polynomial tlme Unique decryption lfwe could solve it in polynomial time we could Depends on choice of knapsack can t have SOIVS 3 Other NP Pmblems lquot P also duplicate elements can t have elements equal to Proof reduce to satis ability vehement sum of subset of other elements assertion lgsevtzuul Unwtlsnmwvml saaa 35 lQSethuul Unwtlsnmwvml saaa as Lecture 8 Nonsecret Key Cryptosystems How Euclid Fermat and Euler Created ECommerce Real mathematics has no effects on war No one has yet discovered any warl ke purpose to be serve by the t eory of numbers m cssss Security and Privacy 7 University afo g d Evans camping 5mm G H Hardy The Mathematicians Apology 1940 Davi mm iWWN cswginia eduievans PublicKey Applications Privacy Alice Piairitext Elub s Public Key Elub s Private Key Alice encrypts message to Bob using Bob s Private Key Only Bob knows Bob s Private Key only Bob can decrypt message usavunni umwivavviwimcssxx Signatures M P M K C h Signed u Ic ey ryptograp y Piaintext bF39iairitEXI Aiice s Private key Alice s Pubiic key Bob knows it wasfrom Alice since only Alice knows Alice39s Private Key Nonrepudiation Alice can39t deny signing message except by claiming her key was stolen Integrity Bob can39t change message doesn39t know Alice39s Private Key usavunni unuaixmavviigimcssxx Private procedure E Public procedure D Identity EDm D Emm Secure cannot determine E 39om D But didn t know how to nd suitable E and D usavunni umwivavviwimcssxx Properties of E and D Trapdoor one way function 1 D EM M 2 E and D are easyto comput 3 Revealing E doesn39t reveal an easy way to compute D Trapdoor one way permutation also 4 E D M M usavunni unuaixmavviigimcssxx RSA EdiI Mquot mod n DC Cd mod n red secret n pq p q are prime dis relativer prime to p 71q71 ed 1 modp71q71 usavunni umwivavviwimcssxx RSA m Per mama ampquot m ummnznnn mummummmmw NW mum mm mama mm FH St Amendm ent cumpmevsuuvce nude 5 an Mama s Am m mm mm mm Petey Jungev cm past RSA sauvue Dude an msvve SM Propemes of and D Property 1 D E M M M M39 mod DEM M39 mod my mod n Dl m av e w p 3 Reveahngldaem nevea anessvv v r M39dmodn as m DVH pruur mp 353 pevmmatmn a su ca WE mm 39239 d and s r a a WWW M M39modn 1 M39 modn Euler s totient phi function a n number of posmve mtegers lt 1 mm are re atwe y m WK 5 pnme 4201 1 iPruuf by untramctmn Tohent Products Fuzpnme andq wipq 447Wlt47Pq W has lt nnnl relatively puma tapq p171 mxnbexslessthmpq Euler s Theorem For a and n relatively prime aw 1 mod n Recall we are looking for e dand n such that MZ I 1 E 1 mod n 24sepl2um Unwers yatvnvimacs 13 Fermat s Little Theorem lfn is prime and a is not divisible by n aquot3915 1 mod n Stronger version in MBC p 200 lfn is prime for any a aquot5 a mod n 24sepl2um Unwers yatvnvimacs 4 Fermat s Little Theorem Proof a mod n Zamod n n 1amod n 12n71 ifabmodnacmodn and a is relatively prime to n then b 0 mod n 24sepl2um Unwers yatvnvimacs 15 Fermat s Little Theorem Proof a mod n Zamod n n 1amod n 12 n71 a x 2ax xn71a2n71lmodn n71la 3912n71lmodn a 1 mod n 24sepl2um Unwers yatvnvimacs a Euler s Theorem Fora and n relatively prime 114quot 1 modn Proof If n is prime pn n71 and aquot 12 1 modn by Fermat s Little Theorem What if n is not prime 24sepl2um Unwers yatvnvimacs 7 Euler s Theorem cont For a and n relatively prime aw 1 mod n p n number of numbers lt n not relatively prime to n We can write those numbers as Rx1x2 xw 24sepl2um Unwers yatvnvimacs 1a Proving Euler s Theorem Proving Euler s Theorem R xhxb Jam multiply by a mod n x1gtlt xZ gtlt xwm s 1 qu n mZmOd n axltprim0d n axlmod n X axzmod n gtlt axwmmod n S is a permutation of R 7 a is relatively primeto n and x so ax is 3M1X axz gtlt LDCWQ mod n relatively prime to n hence all elements of S are inR Ea p gtltx1gtltxzgtltxwmmodn There are no duplicates in S If axme n ax modn then ij since a is relatively prime to n 1 E awquot mOd n QED 24Swt2um Unweis yatViiviniaES EE g 245evt2uu1 Recap n Suppose Mand 71 not relatively pn39me E I lt0 0dn god Mn 1 39fM 395 quot Since 71 pq andp and q are prime relatively prime to n Ifn is prime p n n 71 g0dMgtP 10RngMgtq 1 Case 1M Cp Forp and q prlmei 4 pg p q god M q 1 otheIWiseMis multiple of We are looking for e d and n such that b03111 andqbut1 1ltPq SoMW7gtElmodq M 1 mOd n by Euler s theorem sinceMandq are edi 1 p n p1q 1 relativelyprime Mand 1 cont Mand n c M 2 SD 331 dmemsemis muiupieufbumpanaq butMltpq MWquot E 1 mod q by EulastheurEmsinceMzndqzrerelamelypnme MWquot 1 kg for some k 79 E M lmOd q M cp recallgcd Mp 1 MWQDW 1 med q M XM Nquot 1 k c M MQWW 1 mod q 1 q p MW cp chp M kcn MW 2 1 mod q A4431 5M mod n 24Sevt2um Unweis yatViiviniaES EE 2 245evt2uu1 Unweis yatViiviniaES EE Where s ED 66171 W lm1 So we need to choose e and d ed pn1n7pq Pick random d relatively prime to p n god d 01 1 Since dis relatively prime to p n it has a multiplicative inverse e de E 1 mod pn 2452mm Unweis vatvnvimacs 25 Ide ntity de E 1 mod ltpn 80 d ek ltpn1for some k Hence MWI 1 mod n Mk Wquot mod 7 2452mm Unweis vatvnvimacs 2a D EUW M M 391 mod n M pquotm0d n Euler says 12M quotmod n So 1 EM pquotmod n 1 2 MM391 mod n MEMM mod n QED 2452mm Unweis vatvnvimacs 27 Properties of E and D Trapdoor one way function I 1 D E M M E and D are easy to compute 3 Revealing E doesn t reveal an easy way to compute D Trapdoor one way permutation also 4 E D M M 2452mm Unweis vatvnvimacs 2a Property 2 Easy to Compute EQM Mzmod n Easy every 4th grader can to exponents every kindergartner can do mod n How big are M e and n 7M 2quot where n is the number of bits in M 7M and n must be big 10200 for security 2452mm Unweis vatvnvimacs 2g Fast Exponentiation amnam an o ab amquot a if 2 divides b So can compute Me in about logze multiplies 10l50lt 25 512 multiplies is doable by a computer not a kindergartner Faster bitwise algorithms known 2452mm Unweis vatvnvimacs cm Anything else hard to compute We need to nd large prime numbersp and q Obvious way Pick big numberx fori 2 to 5th x if i divides x its not prime start over withx 1 done x is prime usamznm University uWimima cs 588 31 How many prime numbers Infinite proved by Euclid SOOBC Proof by contradiction Suppose that there exist only nitely many primes p1 ltp2lt ltPy LetN11112 py1 N gt11y so it is composite Np M pr p for some 1r then N 1 MP111112 P171P1 L 1 139 MIIIXIIZ P11M p 1 Contradiction p gt1 Hence there must be infinitely many primes usapiznm Universitvufvugima03588 32 Density of Primes 1X for 05x 51000 7rx is the number of primes x From http WWW utrn eduresearchpnrneshowrnanyshtrnl usamznm University uWimima cs 588 33 Approximating 7106 The Prime Number Theorem Tnx xln x 80 to find a prime biggerthan x we need to make about In x2 guesses Na39IVer Each guess requires sqrtx work For 200 digits worst imaginable case 230 guesses 10100 More work than breaking 3DES useptznm Universltvufvugima03588 36 Need a faster prime test 0 There are several fast probabilistic prime tests 0 Can quickly test a prime with high probability with a small amount of work 0 lfwe pick a nonprime its not a disaster exercise for reader will be on PS3 usamznm University uWimima cs 588 35 Fermat Test Recall Fermat s Little Theorem ifn is prime and a is not divisible byn then a lmo n Prove n is composite by finding 111 lmodn Showing a lmod n does not prove it is prime But if it holds for many a s it is likely than n is prime Holds for all a sfor some nonprimes known as Carmichael Numbers 561 645 1105 useptznm Universltvufvugima03588 35 Properties of E and D Trapdoor one way function I 1 D E M M l 2 E and D are easy to compute 3 Revealing E doesn t reveal an easy way to compute D Trapdoor one way permutation also 4 EDMM 24sepi2um Unwtisnmvimm saaa 37 Property 4 ED M M DOW M mod n ED4 1 mod n2 mod n M mod n Mzdmod n M from the property 1 proof 24sepi2um Unweis yatVilvimaES EE 3a Applications of RSA Privacy Bob encrypts message to Alice using EA Only Alice knows DA Signatures Alice encrypts a message to Alice using DA Bob decrypts using EA Knows it was 39om Alice since only Alice knows DA Things you use every day ssh SSL DNS etc 24sepi2um Unwtisnmvimm saaa 39 Two Questionable Statements in RSA Paper 1 The need for a courier between every pair of users has thus been replaced by the requirement for a single secure meeting between each user and the public file managerwhen the user joins the system P 6 24sepi2um Unweis yatVilvimaES EE 40 Two Questionable Statements in RSA Paper The NBS scheme DES is probably somewhat faster if specialpurposed hardware encryption devices are used our scheme may be faster on a generalpurpose computer since multiprecision arithmetic operations are simpler to implement than complicated bit manipulations P 4 24sepi2um Unwtisnmvimm saaa 41 N Who really invented RSA General Communications Headquarters Cheltenham formed from Bletchley Park after VWVII 1969 James Ellis asked to work on key distribution problem Secure telephone conversations by adding noise to ine Late 1969 idea for PK but function 24sepi2um Unweis yatVilvimaES EE 42 Lecture 4 Striving for Confusion found in ucomat und quot i 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 19 76 C5588 Security and Privacy University of Virginia Computer Science David Evans min NW cs Virginia eduevans Menu Projects Enigma Continued Block Ciphers in Sept 2mm unweisny mvimiiiia cs 588 2 Operation Day key distributed in code book Each message begins with message key randomy choosen by sender encoded using day key Message key sent twice to check After receiving message key reorient rotors according to key in 5m 2m unweisny mvimiiiia cs 588 3 Letter Permutations Symmetry of Enigma if EDOS X ywe know EDOS y X Given message openings DMQ VBM E1 m 7 D E4m7 v VON my E1m2 v E4m2 P PUC FMQ With enough message openings we can build complete cycles for each position pair EWE4 DVPFKXGZYO EIJMUNQLHT BC RW A s Note Cycles must come in pairs of equal length Examples in Code Book had pairs of unequal length 6 in Sept 2mm unweisny mvimiiiia cs 588 Composing Involutions Elan d E4are involutions x a y ya x Without loss of generality we can write Eicontains 3132 3334 a2wa2i EZcontains a2a3 a4a5 aZlgl E1 E2 319 a2 a2lt gtx a3 orx a1 age a4 a4lt gtx a5 orx a1 in Sept 2mm unwan mvmlma cs 588 Rejewski s Theorem Eicontainsa1a2a3a4 awa E4 contains a2a3 a4a5 away E1E4 contains a1a3a5 a2k1 a2ka2k2 a432 The product of two involutions consists of pairs cycles of the same length For cycles of length n there are n possible factorizations in Sept 2mm unwan mvmlma cs 588 Factoring Permutations E1E4 DVPFKXGZYO EIJMUNQLHT BC RVV A S insemzn A S AS 0 SA BC W BRXCW 0 BVVCR or BVRC 0 we BR m unwan mvmlma cs 588 How many factorizations DVPFKXGZYO EIJMUNQLHT E1 E2 D932 Azev Vlt gta4lt a4lt gtP Once we guess a everything else must follow So only n poss ble factorizations for an n letter cycle Total totry 2 10 20 E2E5and E3E6 likelyto have about 20 to try also 2 About 203 8000 factorizations to try still too many in precomputer days 10 Sam ZEIEIl Uni215W UlVlVElnla CS 588 Luckily Operators picked guessable message keys cillies Identical letters Easy to type eg QWE If we can guess P1 P2 P3 or known relationships can reduce number of possible factorizations If we re lucky this leads to E1 E6 1U Sam 2mm unwsny mvimmia cs 588 a 1939 Early 1939 Germany changesscamblers and adds extra plugboard cables stop doubletransmissions Poland unable to cryptanalyze July 1939 Rejewski invites French and British cryptographers It is actually breakable Gives England replica Enigma machine constructed from plans 1U Sam 2mm unwsny mvimmia cs 588 1U Bletchley Park Alan Turing leads British effort to crack Enigma Use cribs WEI39TER transmitted every day at 6am Still needed to brute force check 1 M keys Built bombes to automate testing How many people worked on breaking Enigma 30000 people worked at Bletchley Park on breaking Enigmar 100000 for Manhattan Project tn Sept 2mm Unwers y mvimmia cs 588 M Enigma Cryptanalysis Relied on combination of sheer brilliance mathematics espionage operator errors and hard work Huge impact on WWII Britain knew where German Uboats were Advance notice of bombing raids Butkeeping code break secret more important than shortterm uses 1U Sam 2mm unwsny mvimmia cs 588 12 Goals of Cipher Diffusion and Confusion Claude Shannon 1945 Diffussion Small change in plaintext changes lots of ci hertext Statistical properties ofplaintext hidden in A billion billion is a large number but it39s not that C39Phef e a a num Confuswn Whit ed Dif e Statistical relationship between keyand ciphertext as complex as possible End of classical ciphers 80 need to design functions that produce output that is diffuse and confused in Sept 2mm unwan UfViVEima cs 588 13 in Sept 2mm unwan UfViVEima cs 588 M Ideal Block Cipher 64 bit blocks 25quot possible plaintext blocks must have at least264 corresponding ciphertext blocks Block Ciphers Stream Ciphers Encrypts small bit or byte units one at a time BI kc h There are 264 poss ble mappings 00 I ers Why notjust create a random mapping Encrypts large chunks 64 bits at once x Need a 264 64bit table e10 bits Ciphers we have seen so far Changing one letter ofmessage only changes one 14 quadvll39w letter of ciphertext Need to distribute new table if compromised There were classical ciphers that had some Approximate ideal random mapping using diffusion Vigen ere autokey Hill cipher 2letter chunks components controlled by a key in Sept 2mm Unwers v UfViVEima cs 588 15 in Sept 2mm unwan UfViVEima cs 588 we Feistel Cipher Structure L0 Ie half of plaintext One Round Feistel R0 right half ofplaintext E L0 H R0 1 7 L F g Kl L1 R0 5 L1 RH R EB F K RL71 FltR71Kgt 1 L R0 1 egg CR1HL1L0 FR0K1HR0 g C Rn H I E n is number of rounds I J JR undo last permumtion 1U Sam ZDEH Urn215W mvrmrma CS 588 17 1D 32m ZDEH Unwers v mvrmrma CS 588 1B D1 RDxrl Decryption Decryption 17 171 171 n711 LD Ie half of ciphertext RDOO righthalfofciphertext D EB F R09 K1 war LD0LO FR0 K1 RD0R0 Kn LD 7 L 1 RD m RD1 LD0 ea F RDO K1 1 171 FRD71Knm IE0 FRo K1F RD0K1 0 L R PRDanDn PRD1HLD1 L0H R0 1 1 n ls number of rounds Yippee 1m 3m 2mm Unwan Mme CS 588 15 m Sam 2mm Unwan Mme CS 588 Multiple Rounds The entire round is a function fKL H R RllL lt9 F R K swapLllRRllL 0 E swap 0 swap 0 fKK swap 0 pr1 fK2 swap 0 le DfK1 swap fK2O pr1 swap 0 fK swap 0 swap 1U 52m 2mm unwan mVimima cs 588 21 Decryption Swap fKSwap fK L ll R swap fK swap R H L F R K swap fK L 9 F R K ll R SW2117Rll L lt9 F K K lt9 F K K SwaPRllLLllR So swap fK its own inverse 1U 52m 2mm unwan mVimima cs 588 22 F o What are the requirements on F For decryption to work none For security Hide patterns in plaintext Hide patterns in key Coming up with a good F is hard 1 5m 2m unwan mVimima cs 588 23 DES NIST then NBS sought standard for data security 1973 IBM s Lucifer only reasonable proposal Modified by NSA ChangedSBoxes Reduced key from 128 to 56 bits Adopted as standard in 1976 o More bits have been encrypted using DES than any other cipher 1U 52m 2mm unwan mVimima cs 588 2o DES Algorithm Feistel cipher with added initial permutation Complex choice of F o 16 rounds 56bit key shifts and permutations produce 48bit subkeys for each round in Sept 2mm unwsny myimima cs 588 25 in Sept 2mm DES s F I32 bits Expand and Permute using E table 8bits Kn Substitute using 8 boxes 2 bits erm utation The goal is confusion Unwers y myimima cs 588 25 SBoxes 110011 64 entry lookup table 4bits V 1001 Critical to security NSA changed choice of SBoxes Only nonlinear step in DES E11 E01 E10 in 5m 2m Unwers y myimima cs 588 DES Avalanche Suurce Wilemde Great huniwwwuruupsdcs stand at ukIWdWslidesmudei mi in Sept 2mm Unwers y myimima cs 588 Key Schedule Need 16 48bit keys Best security just use 16 independent keys 768 key bits 56bit key used 64 bits for parity checking Produce 48bit round keys by shifting and DES Keys Next round he 39 hi 39n orr52 bits empressPerm ute v Ki PC Shift Left Km Kn permutm ii Shift Right Ki1 Are there any weak keys in Sam Z l UnNEvS V mVlmlma CS 588 25 in 32m Z l UnNEvS V mVlmlma CS 588 3D ls DES a perfect cipher No more messages than keys Even for 1 64bit block 264 messages gt 256 keys in Sept 2mm Unwers y mytmtma cs 588 31 in Sept 2mm Attacking DES Brute Force Key is 56 bits 256 72 1016 72 quadrillion Try 1 per second 9 Billion years to search entire space Distributed attacks Stealborrow idle cycles on networked PCs Search half of key space with 100000 PCs 1M keyssecond in 25 days Unwers y mytmtma cs 588 32 Lecture 5 DES Use and Analysis C5588 Security and Privacy University ofVirgma Computer Science David Evans http NW 1 Virginia eduevans Menu Today s manifest on line only DES Review Modes of Operation 3DES DES Attacks Return PS1 zsepizum Unwevs vatvuvimacs DES Structure Plaivltext LU left half of plaintext RU right half of plaintext v 12 39 K g a LliRtrl KL1 FltK 112 5 C Rn ii Ln I I n is number of mun L V v R undo last permutation a 1 zsepizum Unwevs vatvuvimacs D E S s F 32 bits Expand and Permute using E table 8 bits v 4 Substitute using 3 boxes ermutation Unweis v mum 5 513a zsepizum ExpansionPermutation 011 11 12 13 14 15 16 17 I48bits 101101010 zsepizum Unwevs vatvuvimacs SBq3xes 48 bits 7 more different Sboxes for bits 7 11 1 1 39 Nothing secret about the SBoxes but they are confusing 12mm uquot m a 125w Neis vatvuvimacs Modes of Operation lzsevtzum Unwtisnwwimm saaa Modes of Operation Transmitting a long plaintext using DES 13131 ll lel ll PN Electronic Codebook Mode C F4131 ll EK P2 ll ll FMPN Problems Any identical blocks encrypted identically 64 bits 8 ASCII characters Lots of cipheitext encrypted with same K lzsevtzum Unwtisnwwimm saaa a Cipher Block Chaining Pl 1 IVgt gt C C to receiver to receiver lzsevtzum Unwtisnwwimm saaa g Cipher Block Chaining CiEKPi Ci1 01 EKP1 IV Decrypt Mi DK Ci BCH M1 DK C1 BIV DKEKPi Ci1 Ciel PiCBCi1 Ci1Pi lzsevtzum Unwtisnwwimm saaa 1D Cipher Feedback Mode bllS39 bllS39 r ck r C P to receiver P2 to receiver lzsevtzum Unwtisnwwimm saaa Output Feedback Mode sh39 bits bits ea r c eel r c A A P to receiver P2 to receiver lzswtzum Unwtisnwwimm wag 2 CipherOutput Feedback 1bit transmission error Active eavesdropper Performance tzsevtzum Unwtisnwwimm sam 13 Multiple Encryption tzsevtzum Unwtisnwwimm sam 4 Multiple Encryption C E142 Eu 1 Does it double the key space Monoalphabetic cipher Ci K2K1Pi K3Pi for some K3 tzsevtzum Unwtisnwwimm sam 15 DoubleVigenere C E142 Eu 1 Vigenere C PKmodN modZ C P Kl m001M mod Z K2 modm modZ PK1modMK2modNZ modZ ile N22 mm modZ K3 K1K2 what ile N2 tzsevtzum Unwtisnwwimm sam a DoubleVigenere 0 K1 quotBONDquot K u BONDBONDBONDBONDBONDBONDBOND JAMESJAMESJAMESJAMESJ JAM KOZHTXNPFGWDNSFMBARVKOZHTXNP Effective key length LCM N1 N2 20 tzsevtzum Unwtisnwwimm sam 7 Double DES 39 C Em Em 1 Is there a K3 such that C EKK P There are 256 keys and 26 mappings If DES is good keys map randomly to mappings Probability that a randomly chosen mapping rresponds to a DES key 255 25 ltlt1 253 Effective key size of Double DES 56 25B 2112 WRONG Unwtisnwwimm sam 1a tzsevtzum Known Plaintext Attack Xian mes One XK YKJ means K K and K2 KJ 252mm Unweis yatVilvimaES EE g Meetinthe Middle Attack C EKZ EKI X EK1P DKZ C Brute force attack given one PC pair calculate EK1 P for all keys 256 work calculate DK2 C for all keys 256 work the match gives the keys Total work 2 256 257 252mm Unweis yatVilvimaES EE 2n 2 Key Triple DES C EKI DKZ Em Why DK2 not EKZ Backwards compatibility with DES K23 C Em Dm Eki 1 En P Actual key size 56 56 bits 112 bits Meetinthemiddle 7 X Em DK1EKZ 25B need to try 2 252mm Unweis yatVilvimaES EE 21 How secure is TripleDES Brute force search 2Wkeys Best DES attack 245 B keyssecond m 67 1014 years compared to 22 hours 10ll years total lifetime of universe closed universe theory Best known attack reduces to ZW OQZ n number of known P C pairs n 264 work is 25B Realistic 252mm Unweis yatVilvimaES EE 22 3Key Triple DES C EK3 DKZ Em HK 168 Used by PGP SMIME How much work to bruteforce Meetinthemiddle X Dm C DKZ Em 1 255 2112 252mm Unweis yatVilvimaES EE 23 DES Attacks Last time brute force Best result 22 hours But no where near good enough for 3DES Differential Cryptanalysis Power Cryptanalysis 252mm Unweis yatVilvimaES EE 24 Differential Cryptanalysis Biham amp Shamir 1990 Choose plaintext pairs with fixed difference A X X G X Use differences in resulting ciphertext to guess key probabilities V th enough work 247 and enough chosen plaintexts 247 can find key com pared to 266 brute force work One Round X X AX X e X 32 bits 32 bits AX 0 lffX X X1 V 8 bits Xl 8 bits 4 K EP preserves values X2 X2 I X 0 2 X16 gt Xlem Where ep115 a functlori de ned by x3 2 bits x3 2 bits We E table 6 preserves values X2 AX 0 X26 gt X26 gt X4 X4 gt61 X3 2 X4p1gt X4pxgt Sboxes e onlinear Kquot Wquot fr m ciPhel tEXt AX 03XX3 X AX 0 3 pX35egtgt XSWO gt 5 pX35eplgtgt X35eplgtgt lt 5 Its a function of the key p determined experimentally 252mm Unweis yatvuvimacs 27 X4 X4 X2X1 Kn X2 X1 Kn Takes 3 years of 1 5Mbps encrypting chosen plaintext 39 A X 0 D XZepm X2 pgt 252mm Unwusnmwwm ESSEE 25 12mm magnum ESSEE 25 One Round cont Sbox 81 X2 6 bits xixir3xyx5x5 4 inputs to S1 produce 0 011100 000001 111110 111011 252mm Unweis yatvuvimacs 2a 252mm Unweis yatvuvimacs 2g Sbox S1 Difference in last input bit difference in output bits 0101 0001 0101 0100 1 XOR 5 1 1011 0101 1110 BXOR 5 E 252mm Unweis yatvuvimacs cm Dwffererma Cryptana ysws Pvupagate expenmenm yebammesmy 1 mundthmugME mun s nuugh PVC pave une key benm25mus1pvubabe mummy depends heava un seam chutes 1 H151pubhshedMBBU meSAknw abum m m 1973 Dwffererma Cryptana ysws SuccessM un DES up m 15 mums benenhan exhauswe seavch By 15 mm chavactenshcs pmbab mes ave 26 Evysuccessm unDESvanams bveaks GDES W a chasequot p amtexts Veyysueeessm un FEALFEALVA FEALVE FEALVN FEALVNX Eumm mm DES Power Consumpuon 75 2 us a 1x m1 lgm l x n wwwww hwwwmvw m We ms um we Mmpmsm use dmmm e devendmv an wmmev e PowerAna ysws Scenano Anackev hasphysm eme 0m encvypts and eeeyyms usmg 3 seem key 5 W5 veahs1m7 mLwww smancamswnnaex a Swde Channe Cryptana ysws E Pagu avcvyplana ysws ma hemalm wevseesmpms ampms emmeyseessme mnee se pew mnsmmmm enavmmndeavmmn me vadxmmn eh Dependsun rwememanon e1 a gumhm Lecture 3 Captain Ridley s Shooting Party Con 39onted with the prospect of defeat the Allied cryptanalysts had worked night and day to penetrate German ciphers It would appear that fear was the main driving force and that adversity is one of the foundations of successful codebreaking Simon Singh The Code Book 1 C5588 Security and Privacy t University of Virginia David Evans http VWWV cs Virginia EduEvans Menu Projects Phil Vamer Vigenere Le Chiffre lnd chiffrable Enigma 502am Unwers yatvuvmiacs P rOjects Preliminary Proposals due Oct 1 Team assignments will be decided by Friday Open ended proposal will lead to an agreement Different types of projects DesignImplement Analyze Research Survey List of ideas on web Just a starting point don t limit yourselfto ideas on list 502am Unweis yatVilvimaES EE a Project Evaluation Need not be 100 technical politics psychology law ethics history etc but shouldn t be 0 technical DesignImplementation projects less focus on quality and organization of writing but still important All team members get same project grade Unless there are problems tell me ear1y 502am Unwers yatvuvmiacs 4 Vigenere Invented by Blaise de Vigenere 1550 Considered unbreakable for 300 years Broken by Charles Babbage but kept secret to help British in Crimean War Attack discovered independently by Friedrich Kasiski 1863 502am Unweis yatVilvimaES EE 5 Vigenere Encryption Key is a N letter string 0 c1 e E mod 26 1 502am Unwers yatvuvmiacs a Babbage s Attack Use vepetmun e guess key englh Sequence XFO appears at 55 71 122 Key ength 7 Frequency Onceyuuknuwkey eng h canshce mphenex and use yeeuenees 17E Spacmgs71435E3 2 E 122 755 57 19 17B 712 A 18 Kay 5 pmbamya e evs ung Someumes not so ucky 2ng madZ gt K new we mum M 5 5n ngenere Swmph canon Use bmavy a phabe c mew m c p w Use a key as mm as P c e e Onerumepadrpe emmphe n g m a mm mmmevua w 1923 Adapted bv Nan s mm smu meme 55 Emgma Mechamcs theevmm 555 555 5 summed e evs om vmms Wmm 5555555555555551995 mg 5 55555555 5555555 Semngs pace 5555 5 swap 5555555555 5555555555 and s 5 555 mu uvm m m 55m 55m mu 4m 5555555555 5515 my 7 555555 3 m 555 m5 mmrs Dnemzlmns 75555555555555555 3 m5 555 55mg 7555quot Mm 555m Rene m ma 5mm 555555550155 5 5 a Pm Key 5 WWWWWVM aw Mes r515 wave 555 mn 515m nme unwevse N39m kudamknawve edm Gnzsz39m3923239 5 x m x 55555 W 5 mugs amm 39m szwmm z 575 757 55515555 25 55M 252 MW 39G39mm Capturmg a Machme 55555555555Wym555 m awm kudamknawvenemm anusn39m39nIV xmu 555555555555 55555 unzm 39m szwmrm s 25 r 75 5 hmw39re enar 555551555 Mes geKev 2 Emgma Schem auc c B L W39W39WNMLEW Does Decryption Work C BlL39lM39lN39lRNMLBP P B39lL39lM39lN39lRNMLBC R is an involution AaB Be A Plugless Enigma Plaintext Ciphertext lt c L lM lN lRNMHP Used in Spanish Civil War 193839 by all sides 502am Unweis vatvnvimacs Ciphertext lt Roamquot Re ector Probable words 410 letters C LriZLP Wl atRijtthzi 39obaobility that Rtoltot 2 b an or o n move In e er cn LC ZL P 2226 85 Unweisnyatvuvimacs 21 Pluless niq a Pluq ss Enigma Plaintext 1 mm L N R R C UZLP Z LC ZL P Guess a crib have C and Pguess LC ZL Palm Try possible rotors and starting positions for L 3 r tor choices 26 starting positions 78 L effect of Rotor 1 in he 1 rotation position Z is a fxed substitution monoalphabe ic is R286 don t move 502am Unweis vatvnvimacs 502am Batons Attack C XTSWVUINZ Pgugss wehrmacht L1 XZL1 W L7 1 Z L7 C IveforZ I Y mng ar starting rotor setting so 1R B 2sZF m4 P 5UZV 6HZI 7M B Batons Attack We know Z is Function contradiction ifZx Zx Involution contradiction if Zx y amp Zy x Find a rotor setting with no contradictions Long enough crib there w39 But if crib is too long need to deal with R2 moving 502am Unweis vatvnvimacs 502am Unweis vatvuvimacs Catalog to map Z to rotor settings for R2 and R3 Enter the Plugboard c BlLlZLBP BLC ZLB P 6 plugs 26252 24232 16 152 6 10lltimes harderatleast Ideas for making Batons attack harder without plugboard 502am Unweis yatvuvimacs C BlL lM lN lRNMLBP Operation Day key distributed in code book Each message begins with message key randomly choosen by sender encoded using day key Message key sent twice to check After receiving message key re orient rotors according to key 502am Unweis yatVilvimaES EE Repeated Message Key P P1P2P3P1P2P3 Cl E Pl B lLl39lM lN lRNMEBPO 04 E4030B 1L4 1M 1N 1RNMLABP1 Pl Ii C B lLrlM lN39lRNMLmey C 0 Pl E4 4 B lLrlM lNlRNMLAB 4 EE CE4Pc EnEl E14 L1 39lMlNTl RNMtlm 39lM39lNlRNMLAB B39lL M4 N1 RNMLWLA39l M39AlNl RNMLAB 502am Unweis yatvuvimacs Letter Permutations Symmetry of Enigma if Ema ywe know Emsy x Given message openings DMQ VBM Em7 D E4m7 V VON PUY Em2 V E4m2 P PUC M V th enough message openings we can build complete cycles for each position pair E E4 DVPFKXGZYO EIJMUNQLHT BC Win A 3 Note Cycles must come in pairs of equal length Examples in Code Book had pairs of unequal length Composing Involutions E and Eare involutions x gt y gty ex Wthout loss ofgenerality we can write E contains ayaz a3a4 aMaZk E contains azaa a4a5 away E2 El aye aZ aZlt gtx a3 orx a1 age a4 a4lt gtx a5 orx a1 502am Unweis yatvuvimacs Rejewski s Theorem E contains awaz a3a4 aMaZk E contains azaa a4a5 away ElEAContains ala3a5a2w a aZkZH 3432 o The product of two involutions consists of pairs cycles of the same lengt For cycles of length n there are n possible factorizations 502am Unweis yatVilvimaES EE Factoring Permutations E4 DVPFKXGZYO EIJMUNQLHT BC E1 RW A s A S A8 0 SA C RW BRXCW 0 BWXCR or vaqu 0 we BR 6 502am Unweis vatvuvlmacs 1 How many factorizations DVPFKXGZYO EIJMUNQLHT El E2 Dlt gta2 2lt gtV Vlt gtay a lt gtP Once we guess a2 everything else must follow 30 only n possible factorizations for an nletter cycle Total to try 2 10 20 E2 E5 and ESE6 likely to have about 20 to try also 2 About 203 8000 factorizations to try still too many in pre computer days wwwcsm 502am Luckily Operators picked guessable message keys clllles Identical letters Easy to type eg QWE If we can guess P1 P2 P3 or known relationships can reduce number of possible factorizations If we re lucky thls leads to E1E6 502am Unweis vatvuvlmacs 33 Solving E1 B 1L1o LB E2 B391L392QLZB 6 equations 3 E 3 B1L3QLsB unknowns N k b E4 B 1quot 4QL4B sailigrft llynsgl vaile E5 B391L5QL5B E6 B1LGQL6B 502am Unweis vatvuvlmacs 34 Solving E B391L391Q O en knew plugboard 1 settings didn t change BE1B391 L391Q L frequently Six equations two unknowns is solvable 502am Unweis vatvuvlmacs 35 1939 Ear1y 1939 Germany changes scamblers and adds extra plugboard cables stop doubletransmissions Poland unableto cryptanalyze July 1939 Rejewski invites French and British cryptographers It is actually breakable Gives England replica Enigma machine constructed from plans 502am Unweis vatvuvlmacs as 08588 Cryptology Principles and Applications Lecture 1 Introduction With a magnetic card and his dog Buddy39s name as a password President Clinton esigned a bill Friday that will make electronic signatures as real as those on paper FoxNews 30 June 2000 3 C5588 Cryptology Menu Course Introduction Why you should or shouldn t take this course Course Logistics details on Syllabus Introduction to Cryptology Terminology A simple substitution cipher Brief history of 4000 years of Cryptology Send registration email by noon Friday r i University ofvirgmia avid Evans mputer Science mm lvvvvvv cs Virginia edulevans 25 mm WWW WWW CS 5 1 Resources Why you should take this course David Evans call me Dave devansvirginiaedu Of ce Hours 236A Tuesdays 10301130am Weds atter class Research code safety static analysis programming and reasoning about swarms TAs Danny Lof 39edo dgl4biirginiaedu CS Reading Room Tuesdays 330430 Anthony Wood adw5pvirginiaedu TBA Web httpwwwcsvirginiaeduc5588 mm mm unweian UlVilEinia cs 588 3 Reason 1 Fate of Humanity Cryptology plays a central role in human history More than anything else survival of humanity depends on computer security ZBAug 2mm UHNEVSW UlVilEinia cs 588 t Why you should take this course Reason 2 Intellectual Cryptology is about making and solving puzzles Puves1 mm at intellectual endeavuv Why you Rea Mr Jellerson would have muted you to should take this course son 3 Be like Tom Bad reasons to take this class Yuu Wanttu Write the ultimate destruttme virus ClA s i yuur bank s cumputer systems Pvublem Set5 utmuuuuuut Pmlectanam Teams um M Cla Howto get an A in C8551 mam term l USduE 1 u gem u CanimuNesuNEvanalvsis Exam 5 s cm l lElN r mal ss Contribution mm M Easy ways to get an A in C8551 Break into my grades file on my home computer and change your grade to Haha Physical attacks on my house car or of ce are NOT elig ble And NOT encouraged Don t try to break into UVA s grade records Too eas probably onlyworth a a or c7 forsocial engineering attack Honor code violation Discover a security flaw important enough to get reported in the New YorkTimes ctor RSA 300 276531aaemnaomaanzaeaanm6o7233n922376n8363ax395azaonnanammnaaraazmo awaaomannenzw875625512m71865731namanuaoezaaazmmInneammmamaae oaaem836aaaaranaeamamuzuenmBaamaaaanaawanmneeaomeemmazawzaem maer7moaoozzmmr2mmaaaamwomaoovaamoaom5mm mm mm Unwersnv orvrmrma cs 588 a Bonus Points Demerits 100 points 1 problem set 100 Posting in RISKS varies Solving a challenge problem 100 Send me a virus 200 Get arrested for computer attack 1000 Get convicted for computer attack 100000 get arrested for something you do mm mm Unwersnv orvrmrma cs 588 m Challenge Problems Open until solved or last day of class Usually only first satisfactory answer gets bonus Better later answer might still get bonus Solve in groups each member gets Nn n value eg 2 people 122 07 First challenge problem starts tomorrow Jefferson wheel cryptogram see course web 6 mm mm Unwersnv orvrmrma cs 588 M Decrypting the Honor Code Learn from your fellow students they are your best resource Write down who you discussed assignments with all external sources you use Don t use answers from last year s class Be honest you know what cheating is and isn t Don t pledge your assignments but let me know if you plan to cheat mm mm Unwers v orvrmrma cs 588 12 Logistics Questions mm mm Unwevs y myimima cs 588 13 What is cryptology Greek krypto hide Cryptology science of hiding cryptography cryptanalysis steganography Cryptography secret writing Cryptanalysis analyzing breaking secrets Cryptanalysisis what attacker does dDecipheror Decryption is what legitimate receiver 065 Kryptonite breaking ciphers all night mm mm Unwevs y myimima cs 588 w Cryptology and Security Cryptology is a branch of mathematics Security is about people mm mm Unwevs y myimima cs 588 15 Terminology ecure Channe Plaintext gt Plaintext 90 V Eve Alice C 503 Bob P 00 E must be invert ble ZBAug 2mm Unwevs y myimima cs 588 we Kerckhoff s Principle Cryptography always involves n io Secret Security should depend only on the key Don t assume enemy won t know algorithm Can capture machines disassemble programs etc Too expensive to invent new algorithm if it might have been com prom39sed Alice and Bob i i hertext Plaintext r ncrypt gt laintext 00 KE KB 00 v Security through obscurity isn t NICE C EKEi P EKE P B b Look at history of examples P DKDv C D KD C Better to have scrutiny by open experts If Kg KD it iS symmetric encryption The enemy knows the system being used If KE KD 39t 395 asymmetric encryptlon Claude Shannon 2mm mm mm Emma cs m a mm mm mm Emma cs m a Substitution Cipher C EKP Ci 2 Kpi Key is alphabet mapping aeaJb4gtLpu Suppose attacker knows algorithm but not key how many keys to try 26 If every person on earth tried one per second it would take SB years mm mm unwsnv MVlVElnla cs 588 15 Monoalphabetic Cipher XBW HGQW XS ACFPSUWG FWPGWXF CF AWWKZV CDQGJCDWA CD BHYJD DJXHGW WUWD XBW ZWJFX PHGCSHF YCDA CF GSHFWA LV XBW KGSYCFW SI FBJGCDQ RDSOZWAQW OCXBBWZA IGSY SXBWGF mm mm Unwers v MVlVElnla cs 588 m Frequency Analysis XBW HGQW XS ACFPSUWG FWPGWXF CF AWWKZV CDQGJCDWA CD BHYJD DJXHGW WUWD XBW ZWJ FX PHGCSHF YCDA CF GSHFWA LV XBW KGSYCFW SI FBJGCDQ RDSOZWAQW OCXBBWZA IGSY SXBWGFquot W 20 Normal English Pattern Analysis XBe HGQe XS ACFPSUeG FePGeXF CF AeeKZV CDQGJCDeA CD BHYJD DJXHGe eUeD XBe ZeJFX PHGCSHF YCDA CF GSHFeA LV XBe KGSYCFe SI FBJGCDQ RDSOZeAQe OCXBBeZA IGSY SXBeGF XBe the C 11 e 12 Most common trigrams in English F 11 t 9 the 54 G 11 a 8 and34 2mm 2mm Unwsll Wilma CS 588 21 mm mm Unwsll Wilma CS 588 22 Guessing Guessing the HGQe tS ACFPSUeG FePGetF CF AeeKZV CDQGJCDeA CD hHYJD DJtHGe eUeD the ZeJFt PHGCSHF YCDA CF GSHFeA LV the KGSYCFe SI FhJGCDQ RDSOZeAQe OCthheZA IGSY StheGF S on mm mm unwan mvvgima cs 588 the HGQe to ACFPoUeG FePGetF CF AeeKZV CDQGJCDeA CD hHYJD DJtHGe eUeD the ZeJFt PHGCOHF YCDA CF GoHFeA LV the KGOYCFe OI FhJGCDQ RDoOZeAQe OCthheZA IGoY otheGF otheG F others mm mm unwan mvvgima cs 588 Guessing the HrQe to ACsPoUer sePrets s AeeKZV CDQrJCDeA CD hHYJD DJtHre eUeD the Zert PHrCoHs YCDA CS roHseA LV the KroYCse oI sthCDQ RDoOZeAQe OCthheZA IroY others sePrets secrets mm mm unwan mmwa cs 588 Guessing the HrQe to ACscoUer secrets Cs AeeKZV CDQrJCDeA CD hHYJD DJtHre eUeD the Zert cHrCoHs YCDA CS roHseA LV the KroYCse oI sthCDQ RDoOZeAQe OCthheZA IroY others ACscoUer discover mm mm unwan mmwa cs 588 Guessing the HrQe to discover secrets 39is deeKZV 39iDQrJ39iDed 39iD hHYJD DJtHre eveD the Zert cHr39ioHs Y39iDd 39is roHsed LV the KroY39i se oI sth39iDQ RDoOZedQe O39i thheZd IroY others mm mm unwan mmwa cs 588 Monoalphabetic Cipher The urge to discover secrets is deeply ingrained in human nature even the least curious mind is roused by the promise of sharing knowledge withheld from others John Chadwick The Decipherrnent of Linear B ZBAug 2mm unwan mmwa cs 588 Why was it so easy Doesn t hide statistical properties of plaintext Doesn t hide relationships in plaintext EE cannot match dg English and all natural languages are very redundant about 13 bits of information per letter Compress English with gzip about 16 mm mm Uni215W mVimmia cs 588 29 How to make it harder Cosmetic Hide statistical properties Encrypt e with 12 different symbols t with 9 different symbols etc Add nulls remove spaces Polyalphbetic cipher Use different substitutions Transposition Scramble order of letters mm mm Uni215W mVimmia cs 588 an Types of Attacks Ciphertextonly How much Ciphertext Known Plaintext often Guessed Plaintext Chosen Plaintext get ciphertext 39 Not as uncommon as it sounds m n l e e e I e p e em epae DumpsterDiving Not recommended in 08588 Social Engineering Rubberhose cryptanalysis Cryptanalyst uses threats blackmail torture HIM 391 a UH n 2aAue 2mm Uni215W mVimmia cs 588 31 Really Brief History First 4000 years Babbage breaks yieeneye Kasiskl 1863 publishes Cryptographer Albanir r pulyalphabelic cipher munualphabelics annnac ann wen mm mm mm unuevsnv mVimmia cs 588 32 Really Brief History last 100 years Maubumne runetrmE pad Quantum Cryptu Lineal Differential CNManavsrlt Ferstel pluck cipher DES Enigma adds minis stuns repealed kEv mm m mm P h K r u re ev Culussus WE Rerem rEpeated prtanawsts messauekw attack Mechanical ciphersr Enigma cwpregraphers 5 18m W 1939 me 1973 1895 ilnventrun ur Rama mm mm Unwers v varmrma ca 588 33 e m es Arms race between cryptographers and cryptanalysts But o en disconnect between two eg Mary Queen of Scots uses monoalphabetic cipher long after known breakable Motivated by war more recently commerce Driven by advances in technology mathematics Multidisciplinary field Linguists classicists mathematicians computer scientists physicists Secrecy often means advances rediscovered and miscredited mm mm Unwersnv varmrma ca 588 so Security vs Pragmatics Tradeoff between security and effort onetime pad perfect security but requires distribution and secrecy oflong key DES short key fast algorithm but breakable quantum cryptography perfect security guaranteed secrecy of key slow requires expensive hardware Don t spend 10M to protect 1 M Don t protect 1 B with encryption that can be broken for 1 M mm mm Unwers v varmrma ca 588 35 Perfectly Secure Cipher OneTime Pad MauborgneNernam 1917 XOR e 0 0 0 169 0 1 0 911 1 1 o EPKP K DCKC KP K KP mm mm Unwers v varmrma ca 588 35 Why perfectly se cure Fm aw 9N2quot c phenext aH mammm ave euuauv pussm e 0mm Go to the beach CarmmveuseK Whahhecewuhas n1nn11111n1n1 0 P Wamcz zw KEN MEIEIEIEIEHEIEIM E szw P amlem 1nanmnnM cs 97 Ken MEIEIEHEHEIEIMEI mg valetvmvvandumbnsequence mammm mum m m asmnu asaH massam Mmumma pWHEmWE Neemusecmewmannmekey cmussus 7 erst Programmame umputer awe cmevpawau Readmphenzxtan Luvenz may panems Yvumtapes Tned each ahunment cammateu cune a mn wnh Germa Deemed messages 63M Mmst m oumssus macmnes m1 enamed Amesm knw Gevman uuup ucahunstuma Dr 0251mm m 1 am kem seem mm was Lecture 6 Two Fish on the Rijndael The algorithm might look haphazard but we did everything for a reason Nothin is in Twolish by chance Anything in he algorithm that we couldn39t justify we removed The result is a lean mean algorithm that is strong and conceptually simple Bruce Schneier C5588 Security and Privacy University of Virgnia David Evans Computer Science http VWWV cs Virginia EduEvans Menu Clipper AES Program R06 Blowfish AES V nner Rijndael 17Swt2uu1 Unwers yafvrlvimacs Breaking Grades File Not in my office or any UVA computer Do not try to break into any UVA com u p ter Home PC C cs588gradestxt encrypted If you obtain that le it tells you what to do Adelphia Cable Modem My browser is set to disallow ActiveX allow Java and JavaScript 17Swt2uu1 Unwers yafvrlvimacs 3 Clipper 1993 ATampT markets secure telephony device Law enforcement US courts can authorize wire taps must be able to decrypt NSA proposes Clipper Chip Secret algorithm Skipjack only implemented in hardware 17Swt2uu1 Unwers yafvrlvimacs 4 Key Escrow NSA has copy of special key can get with a court order Sender transmits E Mk ll LEAF law enforcement agents field Holder of special key can decrypt LEAF to find message key and decrypt message 17Swt2uu1 Unwers yafvrlvimacs 5 LEAF LEAF E E k u H n H a k message key u 80bit special key unique to chip n 30bit identifier unique to chip a escrow authenticator f 80bit key same on all chips nown by FBI 17Swt2uu1 Unwers yafvrlvimacs a Wire Tap FBI investigating Alice intercepts Clipper communication Usesfto decrypt LEAF D EEk ulln ll afEk u ll n lla Delivers n and court order to 2 escrow agencies obtains u Decrypts E k u to obtain message key and decrypt message t75 vt2uut Unwels yatVllvlnlaES EE 7 Two Escrow Agencies Proposal didn t specify who one probably NSA Divide u so neither one can decrypt messages on their own even if they obtain f One gets u X other getsX t75 vt2uut Unwels yatVllvlnlaES EE a Clipper Security How do you prevent criminals from transmitting wrong LEA 7 NSA solution put it in hardware inspect all Clipper devices Still vulnerable to outofthe box device t75 vt2uut Unwels yatVllvlnlaES EE a Clipper Politics Not widely adopted administration backed down Secret algorithm Public relations disaster Dldrl t involve academic cryptographers early Proposal was rushed ll l particular hadn t gured out who would be escrow agencies I See mm vvvvvv err urgpubF rlvacyKeyiescruvvCllpper Future Senators have called for new Clipperl ke restrictions on cryptography Lessons learned well forAES process t75 vt2uut Unwels yatVllvlnlaES EE 1D AES 1996 NIST initiates program to choose Advanced Encryption Standard to replace DES Requests algorithm submissions 15 Requirements Secure for next 50100 years Performance faster than 3DES Support 128 192 and 256 bit keys Brute force Search of 212E keys at l Trillion keysSecond would take low years 109 age of urllverse Must be a block cipher t75 vt2uut Unwels yatVllvlnlaES EE M AES Process Open Design DES design criteria for Sboxes kept secret Many good choices DES only one acceptable algorithm Public cryptanalysis efforts before choice Heavy involvements of academic community leading public cryptographers Conservative but quick 4 year process t75 vt2uut Unwels yatVllvlnlaES EE 12 AES Round 1 Breaking a Cipher 15 submissions accepted ReaI World standard Weak ciphers quickly eliminated Attacker can decrypt secret messages Magenta broken at conference Reasonable amount ofwork actual amount of 5finalists selected MARS IBM R06 H Phe Rivest et al Rijndael top Belgium 39 Academlc Standard cryptographers Serpent Anderson Bihamy Attacker can determine something about the Knudsen Twofish Schneier et al security V Performance is main videoquot Given unlimited number of chosen plaintext How do you measure Security Spherte Pa s I b f t f an er rm a very arge num er 0 compu a ions Slmphuzjr bggggfgzwon up to but not including 2quot where n isthe key size in Need SW on to be we to and e and m emem bits is assume that the attacker can t mount a brute emClean y W p force attack but can get close 17Sevt2uu1 Unweis yatViiviniaES EE 13 175evt2uu1 Unweis yatViiviniaES EE 4 AES Evaluation Criteria 1 Security Most important buthardest to measure From to Resistance to cryptanalysis randomness of output in seven easy Steps 2 Cost and Implementation Characteristics Licensing Computational Memory Flexibility different keyblock sizes hardware implementation Frurn Rives t s RC6 talk http vvvwv rsasecurity curnrsalabsaes Description of RC6 Design Philosophy ROGWrb Parametemi Leverage experience with R05 use Word sizein bits w 32 lgw 5 datadependent rotations to achieve a Number of rounds r 20 high level of security Number of key bytes b 16 24 or 32 Adapt R05 to meet AES requirements Key Expansmni Take advantage of a new primitive for Produces array Slot 2r 3 0f Wbit round increased security and efficiency 32x32 k s 6y multiplication which executes quickly on EmitDUO and Decryptloni modern processors to compute rotation InputOutput in 32bit registers ABCD amounts 17Sevt2uu1 Unweis yatViiviniaES EE 7 175evt2uu1 Unweis yatViiviniaES EE 1a DataDependent Rotations ltlt 3 nannu X 9 X A X X1 XltltfX k X1 X ltltfX k Can we say anything about AX1 X1 9 X1 Same number of bits are still different but can t tell which ones ltltlt 71 means rotate left by amount in low order loampw bits ofn word size w 32 5 bits Unwers vatvrlvimacs 19 17Sevt2DD1 1 Start with R05 RC5 encryption inner loop for i 1 to r do AA B ltltlt BSi AYBBYA ltltlt only depends on 5 bits of B Can RC5 be strengthened by having rotation amounts depend on all the bits of B 17Sevt2DD1 Unwers vatvrlvimacs Better rotation amounts Moduo function Use loworder bits of B mod d Too slow Linear function Use highorder bits of c X B Hard to pick 0 well Unwers y mum cs m 17Sevt2DD1 Properties B x ZB1 should have Onetoone can invert for decryption Good distribution if B is well distributed so is B X 2B 1 High order bits depend on all bits of B diffusion Easy to calculate efficiently if your hardware has 32bit multiplies M4 0 5 17Sevt2DD1 Unwers vatvrlvimacs B x ZB1 is onetoone mod 2 Proof By contradiction Assume B C ande2B1Cx201mod2w then Bgtlt2B1Cgtlt2010mod2w 2BZB 27C 0mod2w B o X 232c1 0 mod 2w But BC is nonzero and 2BZC1 is odd their product can t be zero Corollary B uniform 9 B X 2B1uniform and highorder bits are uniform too 17Sevt2DD1 3 Highorder bits of B x ZB1 depend on all bits of B diffusion B 831830829 8180 in binary 831830829 8180 33831830829 BWB0 83831830829 BWB0 fB F31F30F29 F1F0 E 1 X B 2Bjgtlt Bw C rlmod 2 0 11 17Sevt2DD1 Unwers vatvrlvimacs Diffusion cont FBZBJxBWVQVmod2 70 f Q BZBJX B117CVdiv2 1014 39 Flipping bit B Leaves bits FD F1 of B unchanged Flips bit F always Flips bit F for gt1 with probability approximately V2 39 Different for dlfferel itl s but F depends on B forall rgtf ls likely to change some highorder bits 17sep12um Unweis vatvuvimacs 2 Quadratic Rotation Amounts 1 to rdo tBx2B1ltltlt5 AA B ltltltt Si A BBA But now much of the output of multiplication is being wasted only 5 top bits used 17sep12um Unweis vatvuvimacs 3 Use t not B as xor input for i 1 to rdo tBx2B1ltltlt5 A A6 0 ltltlt t Si A BBA R05 used 64 bit blocks AES requires 128bit blocks Double size ofA and B 64bit registers and operations are poorly supported by typical compilers and hardware 17sep12um Unweis vatvuvimacs 4 Do two RCS s in parallel M ADBDABAZBZA3B3 M ADBDCDDDABCD X 23 1ltltlt 5 ltltlt t spa ame thing or next 64 39 Unweis v mum 5 m 17sep12um 5 Mix up data between copies Switch rotation amounts between copies and cyclically permute registers instead of swapping for i 1 to r do Bx 2B 1ltltlt 5 u Dx2D1ltltlt5 A A G t ltltlt u S2i CC u ltltlttS2i 1 A B C D B C D A 17sep12um Unweis vatvuvimacs One Round of R06 17sep12um Unweis vatvuvimacs Key Expanswon Same as Rcs s npm mum mmpmmm ompm w m m ammemm pmme 5 El UxB7E15153 Odd lri n 1m 11 umslwkslml39U E WSBS EI Odd rn2gt 32m smvoaltltlt3 LyvoBltltltAoB WM mad2 Nhat do ned have to do thh or to 7 UsedbyR CS R CE Ewash 2 m magmcumam Mammaucaxcuman shmguuu pseuduvandum mmmmn Smce heyave pubh and WeHrknuwn nu eavthat than 5 amp my 6 Add Pre and Postertemng 2 201ltlt5 7 Set r 20 for mgh secunty based an ana vss ultltltt sum B C D A 1 RC6 Dec hon forAES ryp B oW Sh gamma 547 Nb uckmphev A Much151enhan DES Ag Vaname key ength 3 327mm Many anemmed cvylana yses nune successm ye kuey used ssh OpenESD PGPFune KeyrDependent SBoxes DMeverma cyyp1ana1ys1saepems un pmbammes ChangemeSrbuxessuyuucan tdu ana1ys1s B10W 5h TWO SH Emmy vuns emypnun 521 11mm pmduce sbuyes memaw my man mm Mum vades Dmmns 1m hawmanv key depengam Srhaxes mm Sammyme Mm werease mm 5112 125 rammed by AE s mange yey smedme eh mgaye emm AES VW mer RUNdae 1mm hymn mmquot m yum mm Pundae Ayanam MSquaveJhe ch12 mawbackmm mphensme dmwhy Amencans have pmnuuncmg 11 Emma Schnemv mm as AES mm mm Rundae1 Oyery1ew K2ys1zes 128119212513 bns a1uc1lts1zes 128119212513 bns 1n mums mammng mma AddKey muem hveak an 9 mm 255m yey E1ves ety s ma m1 mms 23mm 2 may Wane15 my 15m Mama 3 my M m m mm m m m yeya mummy quota mm M mm mm 1 mm mm Shannan Wm 2am um Em Menu 5 Pe em prhevs Emmpyand Umcny Survey Resuns new mu 7mm mmwm hm mhevdm mm wmuv Wu mum quotmm m Mm n m emu yequueumnmauyse m Nmma Ha eyswwunxmMemuvmsmggLCrvmg maxeuamsnemy 5 Egg Maxxmum Semn v YheNeLDv swings Omcespace Sv md sh vusvea Survey Requested Topwcs SSL PGP R SA Nemmk and Web secumy ecummeme ouamum Cumpmmg HamATM We NSAsecvet Last T me E g keyspace snmnecessan ya sunny mphev exam Onemme Pad 5 pu39letl cipher K mamm mamas usuaH N LavenzMa we Tud W Hueswsmeanmbeape em We 5 to Conwnce unemummmmummy mum m m when camd m u mama s kn wmv mu manaa vhabmcsecum mm m mm mm nu 1139 mm n uncmanYheDW mama wked nan manwe nvemed mck rpav eved Fvshee we May s W 2 mm baHsz e nmng an a Entropy Maum mmmmmmn m a mesEge mm 2 m log PM m lt 1 m rumwing Base mm 5 mam 5 mm mm mm sme number 39vass b e meamnvs Entropy Examp e Mmumnsunne yea H M 1 2 35 need a bum encade a yeav Rate Absu me vate nuw mucn nmnnauun can be 2mm 1 log Esmumyluhe lag126247h39slenex ua vate Ma anguage PH m M s anNenevmessage munumnsspeueu um usmgASCH anus 2 busmm n n6 x ate of Enghsh Enghgnhsaham zam emem 3 msnenev my an y e m m nawnanyneannw Zme ev mes ges m Engh w x mm m 21 Human Hum ha 25 Elmw of2 lmxyossfbk mummy 2n mersam sensb e Ewhsn 5 y n 2 m Redundancy Redundancthsde ned D R 1 RwandanWm mm D 1 r 28 2 enevs enev D 4 7 713 busbug Each e ens 1 3 bus munan and 34 bus uhedundancy 42 LmAscH 074 3 57 51 redundanw 19mvmm shun Unicity Distance Entropy of cryptosystem K number of possible keys logAlphabet size K if all keys equally likely H64 bit key logZ 2M 64 Unicity distance is defined as U HKD Expected minimum amount of ciphertext needed for bruteforoe attack to succeed mum Unweis yatVilvimaES SS 13 Unicity Examples OneTime Pad HK in nite n ite Monoalphabetic Substitution HK log2 26 e87 D 3 4 redundancy in English U HKD e25 5 Intuition ifyou have 25 letters probably only he possible plaintext D 0random bit stream U HK in nite mum Unweis yatVilvimaES EE 4 Unicity Distance Probabilistic measure of how much ciphertext is needed to determine a unique plaintext Does not indicate how much ciphertext is needed for cryptanalysis If you have less than unicity distance ciphertext can t tell if guess is right As redundancy approaches 0 hard to cryptanalyze even simple cipher mum Unweis yatVilvimaES SS 15 Shannon s Theory 1945 Message space MPMZWMH Assume nite number of messages Each message has probability pMiIIMz pMn1 Key space K1KZKI Based un Ell Eiham s mes mum Unweis yatVilvimaES EE a Perfect Cipher Definition A perfect cipher ciphertext with equal probability 1 p Mlq p M Conditional Probability P B lA The probability ofB given thatA occurs P coin ip is tails 2 P coin ip is tails l last coin ip was heads 2 P today is Monday l yesterday was Sunday 1 P today is a Weekend day l yesterday was a Workday 15 mum Unweis yatVilvimaES EE a Calculating Conditional Probability PBlAPAnB P A P coin ip is tails l last coin ip was heads P coin ip is tails and last coin ip was heads Plast coin ip was heads 2 2 2 mum Unwers yatvrivrmacs g P today is a Weekend day l yesterday Was a Workday P today is a Weekend day and yesterday was a workda P esterda was a workday P today is a weekend day Pyesterday was a workday P yesterday was a workday 27 57 57 27 Wrong PA m B PA PB only ifA and B are independent events mum Unwers yatvrivrmacs 2n Perfect Cipher Definition V i j P Mlq P M A cipher is perfect iff VMC PClMPC Or equivalently VMC PMlCPM mum Unwers yatvrivrmacs 21 Perfect Cipher VM C P C illI P C VMC PC PK EMC Or VC ZPK is independent ofM EK EM lWhout knowing anything about the key any ciphertext is equally likely to match and plaintext mum Unwers yatvrivrmacs 22 Example Monoalphabetic Random monoalphabetic substitution for one letter message v CM pC pC i M 126 mum Unwers yatvrivrmacs 23 Example OneTime Pad For each bit pc0pcolM0pc0lM1 sincecK M PK M0PK 1P M1 pK0p M0 Truly randomK meanSpK1pI 0 V2 Vz P N1 2PNI0 V2 PM1PM0 2 All key bits are independent so pC pC lM QED mum Unwers yatvrivrmacs 24 Perfect Cipher Keyspace Theorem Theorem If a cipher is perfect there must be at least as many keys I are there are possible messages n asepzum Unweis yatVilvimaES ES 25 Proof by Contradiction Suppose there is a perfect cipher with llt n More messages than keys Let CO be some ciphertext with pC0 gt 0 There exist mmessages M such that M DKCO n mmessagesM0 such that M0 DKC0 We know 1 ml lt nsOn mgt Oand there is at least one message M0 asepzum Unweis yatVilvimaES ES Proof cont Consider the message Mo where M0 DKCO for any K 80 P Co l Mo 0 In a perfect cipher P ColMo P Cogt 0 Contradiction It isn t a perfect cipher Hence all perfect ciphers must have 211 SW Wm 27 Example Monoalphabetic Random monoalphabetic substitution is not a perfect cipherfor messages of up to 20 letters 1 26 n 262D llt 71 its not a perfect cipher In previous proof could choose CU AB and ME ee and p CU lMU 0 asepzum Unweis yatVilvimaES ES 2a Example Monoalphabetic ls random monoalphabetic substitution a perfect cipher for messages of up to 2 letters 126 rl26Z 1271 No Showing 12 71 does not prove its perfect asepzum Unweis yatVilvimaES ES Summary Cipher is perfect VLj1p MlCJ p M Given any ciphertext the probability that it matches any particular message is the same Equivalently v Lj p CM11 C Given any plaintext the probability that it matches any particular ciphertext is the same asepzum Unweis yatVilvimaES ES

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.