Slide 1Login ProcessPassword ProblemsHashed PasswordsDictionary Attacks(at least) 86% of users are dumb and dumberSalt of the EarthSending PasswordsSlide 9Slide 10Modern Symmetric CiphersModern CiphersSlide 13Key Agreement DemoAsymmetric CryptosystemsOne-Way FunctionsRSA [Rivest, Shamir, Adelman 78]Security of RSASlide 19Public-Key Applications: PrivacySignaturesSlide 22Key ManagementApproach 1: Meet SecretlyApproach 2: Public AnnouncementApproach 3: Public DirectoryApproach 4: CertificatesSSL (Secure Sockets Layer)Slide 29Slide 30Slide 31Slide 32How do you make your web site password form encrypt its input?Exam 2: Requested TopicsChargeAnimated version of Asymmetric Cryptography DemoPadlocked BoxesSlide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44David Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceClass 36:Public Key Crypto2CS150 Fall 2005: Lecture 36: Public Key CryptographyLogin: alyssaPassword: fidoTerminalTrusted SubsystemEveLogin Processlogin sends <“alyssa”, “fido”>3CS150 Fall 2005: Lecture 36: Public Key CryptographyPassword Problems•Need to store the passwords–Dangerous to rely on database being secure•Need to transmit password from user to host–Dangerous to rely on Internet being confidentialLecture 31, Recap NowToday4CS150 Fall 2005: Lecture 36: Public Key CryptographyHashed PasswordsUserID Passwordalyssa f (“fido”)ben f (“schemer”)dave f (“Lx.Ly.x”)5CS150 Fall 2005: Lecture 36: Public Key CryptographyDictionary Attacks•Try a list of common passwords–All 1-4 letter words–List of common (dog) names–Words from dictionary–Phone numbers, license plates–All of the above in reverse•Simple dictionary attacks retrieve most user-selected passwords•Precompute H(x) for all dictionary entries6CS150 Fall 2005: Lecture 36: Public Key Cryptography(at least) 86% of users are dumb and dumberSingle ASCII character 0.5%Two characters 2%Three characters 14%Four alphabetic letters 14%Five same-case letters 21%Six lowercase letters 18%Words in dictionaries or names 15%Other (possibly good passwords)14%(Morris/Thompson 79)7CS150 Fall 2005: Lecture 36: Public Key CryptographySalt of the EarthUserID Salt Passwordalyssa 1125crypt (“Lx.Ly.x”, 1125)ben 2437crypt (“schemer”, 2437)dave 932 crypt (“Lx.Ly.x”, 932)How much harder is the off-line dictionary attack?In HooRides.net we use the user name as the salt.Is this better or worse?Salt: 12 random bits8CS150 Fall 2005: Lecture 36: Public Key CryptographySending PasswordsEncryptUserServerThe InternetThe Internet9CS150 Fall 2005: Lecture 36: Public Key CryptographyEncryptDecryptPlaintextCiphertextPlaintextUserServerC = EncryptK (P)P = DecryptK (C)K KThe InternetThe Internet10CS150 Fall 2005: Lecture 36: Public Key CryptographyFrom http://www.codesandciphers.org.uk/lorenz/fish.htmPS4: Lorenz Cipher11CS150 Fall 2005: Lecture 36: Public Key CryptographyModern Symmetric Ciphers A billion billion is a large number, but it's not that large a number. Whitfield Diffie•Same idea but:–Use digital logic instead of mechanical rotors–Larger keys (random bits, not rotor alignments)•PS4 = 53; Lorenz  512 < 109•Modern  128 bits > 1037–Encrypt blocks of letters at a time12CS150 Fall 2005: Lecture 36: Public Key CryptographyModern Ciphers•AES (Rijndael) successor to DES selected 2001•128-bit keys, encrypt 128-bit blocks•Brute force attack (around 1030 times harder than Lorenz)–Try 1 Trillion keys per second–Would take 10790283070806000000 years to try all keys! –If that’s not enough, can use 256-bit key•No known techniques that do better than brute force search13CS150 Fall 2005: Lecture 36: Public Key CryptographyEncryptDecryptPlaintextCiphertextPlaintextUserServerK KThe InternetThe InternetHow do User and Server agree on K (without sending it over the Internet)?14CS150 Fall 2005: Lecture 36: Public Key CryptographyKey Agreement Demo(Animated version atend of slides.)15CS150 Fall 2005: Lecture 36: Public Key CryptographyAsymmetric Cryptosystems•Need a hard problem (like symmetric cryptosystems)•With a trap door: if you know a secret, the hard problem becomes easy16CS150 Fall 2005: Lecture 36: Public Key CryptographyOne-Way Functions•Easy to compute, hard to invert•Trap-door one way function:–D (E (M)) = M–E and D are easy to compute.–Revealing E doesn’t reveal an easy way to compute D.–Hence, anyone who knows E can encrypt, but only someone who knows D can decrypt17CS150 Fall 2005: Lecture 36: Public Key CryptographyRSA [Rivest, Shamir, Adelman 78]One-way function: multiplication is easy, factoring is hardTrap-door: number theory (Euler and Fermat)18CS150 Fall 2005: Lecture 36: Public Key CryptographySecurity of RSA•n is public, but not p and q where n = pq •How much work is factoring n?n ~200 digits – would take quintillions of years Number Field Sieve (fastest known factoring algorithm) is:O(e1.9223((ln (n))1/3 (ln (ln (n)))2/3)The movie Sneakers is about what happens if someone discovers a O(nk) factoring algorithm.19CS150 Fall 2005: Lecture 36: Public Key CryptographyAsymmetric Cryptosystems•Encryption and Decryption are done with different keys•Keep one of the keys secret, reveal the otherEKRA (EKUA (M)) = MAlice’s Public Key: KUA Alice’s Private Key: KRAOnly KRA can decrypta message encryptedusing KUA.20CS150 Fall 2005: Lecture 36: Public Key CryptographyPublic-Key Applications: Privacy•Alice encrypts message to Bob using Bob’s Private Key•Only Bob knows Bob’s Private Key  only Bob can decrypt messageEncryptDecryptPlaintextCiphertextPlaintextAliceBobBob’s Public KeyBob’s Private Key21CS150 Fall 2005: Lecture 36: Public Key CryptographySignatures•Bob knows it was from Alice, since only Alice knows Alice’s Private Key•Non-repudiation: Alice can’t deny signing message (except by claiming her key was stolen!)•Integrity: Bob can’t change message (doesn’t know Alice’s Private Key)EncryptDecryptPlaintextSignedMessagePlaintextAliceBobAlice’s Private KeyAlice’s Public Key22CS150 Fall 2005: Lecture 36: Public Key CryptographyEncryptDecryptPlaintextCiphertextPlaintextUserServerKUSKRSThe InternetThe InternetPublic Key Private KeyHow does User know the public key to use?23CS150 Fall 2005: Lecture 36: Public Key CryptographyKey Management24CS150 Fall 2005: Lecture 36: Public Key CryptographyApproach 1: Meet Secretly•User and Server Operator meet