PowerPoint PresentationMenuFinding Problem Set PartnersUse a Universally Trusted Third PartySlide 5HashMaker.com?Untrusted Third PartySlide 8How can we send a message to HashMaker without it knowing who sent it?Onion RoutingSlide 11Slide 12Slide 13Problems with this ProtocolProof-Carrying Code Amy Felty, University of Ottawa Foundational Proof-Carrying Code for Software Safety Today at 3:30 (right here)Proof-Carrying CodeTamper with CodeTamper with BothHow many PCC systems in active use?AuthenticationHow do you authenticate?Early Password SchemesLogin ProcessAuthentication ProblemsEncrypted PasswordsHashed PasswordsEncrypted Passwords Try 1Encrypted Passwords Try 2First UNIX Password SchemeMaking Brute Force Attacks HarderDictionary Attacks86% of users are dumbMaking Dictionary Attacks HarderProblems with User RulesTrue AnecdoteEverybody loves BuddySalt of the EarthSecurity of UNIX PasswordsWhat about Eve?sshhhhh....David Evanshttp://www.cs.virginia.edu/~evansCS588: Security and PrivacyUniversity of VirginiaComputer ScienceLecture 12:Public-Key Protocols8 Oct 2001 University of Virginia CS 588 2Menu•Humilation-Free Matchmaking Protocol•Proof Carrying Code–Plug for Amy Felty’s talk: 3:30 Today•Authentication8 Oct 2001 University of Virginia CS 588 3Finding Problem Set Partners•Simple way:–Ask people in the class if they want to work with you•Problems:–You face rejection and ridicule if they say no•Can you find partners without revealing your wishes unless they are reciprocated?–Identify people who want to work together, but don’t reveal anything about anyone’s desires to work with people who don’t want to work with them8 Oct 2001 University of Virginia CS 588 4Alice is your best matchUse a Universally Trusted Third PartyAliceBobBob would like to work with:Ron RivestSandra BullockAliceAlice:Thomas JeffersonColleen HackerBobMatchMaker.com8 Oct 2001 University of Virginia CS 588 5Use a Universally Trusted Third PartyBobEKUM [EKRB [“Bob would like …”]]MatchMaker.comEKUB [EKRM [“Alice”]]8 Oct 2001 University of Virginia CS 588 6HashMaker.com?•Bob writes H(“I am looking for someone who wants to play with Euler’s totient function.”) on the board.•No on else can tell Bob’s deepest darkest desires (H is one-way)•If someone else writes the same hash on the board, Bob has found his match•How well does this work?8 Oct 2001 University of Virginia CS 588 7Untrusted Third PartyBobEH(W) [W]HashMatcher.comUse the hash of the wish as the encryption key so some symmetric cipher: HashMatcher can’t determine the wish Someone with the same exact wish will match exactly8 Oct 2001 University of Virginia CS 588 8Untrusted Third PartyBobEH(W) [W]HashMatcher.com8 Oct 2001 University of Virginia CS 588 9How can we send a message to HashMaker without it knowing who sent it?To: HashMakerFrom: AnonymousTo: Router4To: Router3To: Router2To: Router1From: Bob8 Oct 2001 University of Virginia CS 588 10Onion RoutingR5R4R3R2R1BobHashMatcher.comPick n random routers, Ri1…RinRik gets a message Mk:EKURik (To: Rik+1 || Mk+1)8 Oct 2001 University of Virginia CS 588 11Onion RoutingR5R4R3R2R1BobHashMatcher.comPick 1 random router: R2Send R2: EKUR2 (To: HashMatcher.com || M)8 Oct 2001 University of Virginia CS 588 12Onion RoutingR5R4R3R2R1BobHashMatcher.comPick 2 random routers: R2, R5Send R2: EKUR2 [To: R5 || EKUR5 [To: HashMatcher.com || M]8 Oct 2001 University of Virginia CS 588 13Finding Problem Set Partners•If Bob wants to work with Alice, he constructs W = “Alice + Bob” (all students agree to list names in this way in alphabetical order)•Using onion rounting, sends HashMaker: EH(W) [W] •Using onion rounting, queries HashMaker is there is a matching item–If so, Alice want to work with him8 Oct 2001 University of Virginia CS 588 14Problems with this Protocol•Cathy could send W = “Alice + Bob” •Anyone can query “x + Bob” for all students to find out who Bob wants to work with (or who wants to work with Bob, can’t tell the difference)•If Sandra B. wants to work with Bob too, how do matches reflect preferences without revealing them?•Challenge Problem #2: Design a good matchmaking protocol8 Oct 2001 University of Virginia CS 588 15Proof-Carrying CodeAmy Felty, University of OttawaFoundational Proof-Carrying Code for Software SafetyToday at 3:30 (right here)8 Oct 2001 University of Virginia CS 588 16Proof-Carrying CodeProgramCertifying CompilerNative CodeProofCode ProducerCode ConsumerNative Code ProofProof CheckerCPUOkPolicy8 Oct 2001 University of Virginia CS 588 17Tamper with CodeProgramCertifying CompilerNative CodeProofCode ProducerCode ConsumerTampered Code ProofProof CheckerCPUWily HackerNo!No!Policy8 Oct 2001 University of Virginia CS 588 18Tamper with BothProgramCertifying CompilerNative CodeProofCode ProducerCode ConsumerTampered Code Tampered ProofProof CheckerCPUNo!No!Wily P. HackerOkBut it means thedesired propertystill holds!Policy8 Oct 2001 University of Virginia CS 588 19How many PCC systems in active use?•2•100•1000•1 Million•10 Million•> 20 MillionJava byte code verifier isa limited implementation of PCC:• Bytecodes include extra information on typing, stack use, etc. • Bytecode verifier checks it toenforce low-level code safety propertiesPeter Lee claims most linkers areinstances of PCC also.8 Oct 2001 University of Virginia CS 588 20Authentication8 Oct 2001 University of Virginia CS 588 21How do you authenticate?•Something you know–Password•Something you have–SecureID, physical key•Something you are–Biometrics (voiceprint, fingerprint, etc.)•Decent authentication requires combination of at least 2 of these8 Oct 2001 University of Virginia CS 588 22Early Password SchemesUserID Passwordalgore internalcombustionclinton buddygeorgew gorangersLogin: algorePassword: tipperFailed login. Guess again.Login does direct password lookup and comparison.8 Oct 2001 University of Virginia CS 588 23Login: algorePassword: internalcombustionTerminalTrusted SubsystemEveLogin Processlogin sends <“algore”, “internalcombustion”>8 Oct 2001 University of Virginia CS 588 24Authentication Problems•Need to store the passwords somewhere – dangerous to rely on this being secure–Encrypt them? But then, need to hide key•Need to transmit password from user to host–Use a secure line (i.e., no remote logins)–Encrypt the transmission (what key?)8 Oct 2001 University of Virginia CS 588 25Encrypted