1David 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 Passwordsf(“schemer”)benPasswordUserIDf(“Lx.Ly.x”)davef(“fido”)alyssa5CS150 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 dumber14%Other (possibly good passwords)15%Words in dictionaries or names18%Six lowercase letters21%Five same-case letters14%Four alphabetic letters14%Three characters2%Two characters0.5%Single ASCII character(Morris/Thompson 79)27CS150 Fall 2005: Lecture 36: Public Key CryptographySalt of the Earth93224371125Saltcrypt (“schemer”, 2437)benPasswordUserIDcrypt (“Lx.Ly.x”, 932)davecrypt (“Lx.Ly.x”, 1125)alyssaHow 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 CiphersA 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 1030times 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 search313CS150 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 yearsNumber 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.419CS150 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 secretly and swap public keys– If you can do that, might as well agree on a secret (symmetric key) instead– Doesn’t work for Internet transactions525CS150 Fall 2005: Lecture 36: Public Key CryptographyApproach 2: Public Announcement• Publish public keys in a public forum– Append to email messages– Post on web site– New York Time classifieds• Easy for rogue to pretend to be someone else– Forge email, alter web site, lie to New York Times26CS150 Fall 2005: Lecture 36: Public Key CryptographyApproach 3: Public Directory• Trusted authority maintains directory mapping names to public keys• Entities register public keys with authority in some secure way• Authority publishes directory– Print using watermarked paper, special