WIXLIB

User Authentication: ID protocolsD. Boneh

The Setupvk either publicor secretAlg. GskUser P(prover)no key exchangevkServer V(verifier)yes/no2

Applications Physical locks:(friend-or-foe) Wireless car entry system (e.g. KeeLoq) Opening an office door or a garage door Login at a bank ATM or a desktop computer Login to a remote web site once key-exchange withone-sided authentication completes (e.g. SSL)3

ID Protocols: how not to useID protocol do not establish a secure sessionbetween Alice and Bob !! Not even when combined with anonymous key exch. Vulnerable to man in to the middle attacksskvkProveranon. key exchangeVerifierkkID protocolAliceInsecure!4

ID Protocols: how not to useID protocol do not set up a secure sessionbetween Alice and Bob !! Not even when combined with anonymous key exch. Vulnerable to man in to the middle attackskvkProverkakey exch.key exch.kakbVerifierkbproxy ID protocolAlice5

ID Protocols:Security Models1. Direct Attacker: impersonates prover with noadditional information (other than vk) Door lock2. Eavesdropping attacker: impersonates proverafter eavesdropping on a few conversationsbetween prover and verifier Wireless car entry system3. Active attacker: interrogates prover and thenattempts to impersonate prover Fake ATM in shopping mall6

ID protocols secure against direct attacksa.k.a Password Systems

Basic Password ProtocolPWD:(incorrect version)finite set of passwordsAlgorithm G (KeyGen): choose pw PWD.User P(prover)skskoutput sk vk pw.Server V(verifier)vkyesiff sk vk8

Basic Password Protocol(incorrect version)Problem: VK must be kept secret Compromise of server exposes all passwords Never store passwords in the clear!password file on serverAlicepwaliceBobpwbob 9

Basic Password Protocol: version 1H: one-way hash function from PWD to X “Given H(x) it is difficult to find y such that H(y) H(x)”User P(prover)skskServer V(verifier)vk H(sk)password file on serverAliceH(pwA)BobH(pwB) yes iff H(sk) vk1

Weak Passwords and Dictionary AttacksPeople often choose passwords from a small set: The 6 most common passwords(sample of 32 106 pwds):123456, 12345, Password, iloveyou, princess, abc123(‘123456’ appeared0.90% of the time) 23% of users choose passwords in a dictionaryof size 360,000,000Online dictionary attacks: Defeated by doubling response time after every failure Harder to block when attacker commands a bot-net1

Offline Dictionary AttacksSuppose attacker obtains vk H(pw) from server Offline attack: hash all words in Dict until a word wis found such that H(w) vk Time O( Dict ) per passwordOff the shelf tools 2,000,000 guesses/sec Scan through 360,000,000 guesses in few minutes Will recover 23% of passwords1

Password CrackersAlgorithmMany tools for this Speed/secDES2 383 000MD54 905 000LanMan12 114 000John the ripperCain and AbelPassware(Commercial)13

Batch Offline Dictionary AttacksSuppose attacker steals pwd file F Obtains hashed pwds for all usersAliceH(pwA)BobH(pwB) Batch dict. attack: Build list L containing (w, H(w)) for all w Dict Find intersection of L and FTotal time: O( Dict F )Much better than a dictionary attack on each password1

Preventing Batch Dictionary AttacksPublic salt: When setting password,pick a random n-bit salt S When verifying pw for A,test if H(pw, SA) hAidShAliceSAH(pwA , SA)BobSBH(pwB , SB) Recommended salt length, n 64 bits Pre-hashing dictionary does not helpBatch attack time is now:O( Dict F )1

Further DefensesSlow hash function H:(0.1 sec to hash pw) Example:H(pw) SHA1(SHA1( SHA1(pw) )) Unnoticeable to user, but makes offlinedictionary attack harderAlice SA H(pwA , SA , rA)Secret salts:Bob SB H(pwB , SB , rB) When setting pwd chooseshort random r (8 bits) When verifying pw for A,try all values of rA: 128 times slow down on average 256 times slow down for attacker1

Case study: UNIX and WindowsUNIX: 12-bit public salt Hash function H: Convert pw and salt and a DES key k Iterate DES (or DES’) 25 times:0DESDESDESkkkhWindows: NT and later use MD4 Outputs a 16 byte hash No public or secret salts1

BiometricsExamples: Fingerprints, retina, facial recognition, Benefit: hard to forgetProblems: Biometrics are not generally secret Cannot be changed, unlike passwords Primarily used as a second factor authentication1

The Common Password ProblemUsers tend to use the same password at many sites Password at a high security site can be exposed bya break-in at a low security siteStandard solution: Client side software that converts a commonpassword pw into a unique site passwordpw’ H( pw, user-id, server-id )pw’ is sent to server1

ID protocols secure againsteavesdropping attacksa.k.a One-time Password Systems

Eavesdropping Security ModelAdversary is given: vk, and the transcript of several interactions betweenhonest prover and verifier.adv. goal is to then impersonate prover to verifierA protocol is “secure against eavesdropping” if noefficient adversary can win this gameThe password protocol is clearly insecure We discuss two secure stateful protocols (one-time pwd), and one stateless protocol (challenge-response)2

The SecurID system(secret vk, stateful)Algorithm G: (setup) Choose random key k K Output sk (k,0) ; vk (k,0)Identification:vascoproversk (k,0)r0 F(k,0)sk (k,1)r1 F(k,1)verifiervk (k,0) Yes iffr F(k,0)vk (k,1)2

The SecurID system(secret vk, stateful)“Thm”: if F is a secure PRF then protocolis secure against eavesdroppingRSA SecurID uses a custom PRF:64 bit key24 bit ctrF6 digit outputvascoAdvancing state:sk (k, i 1) Time based: every 60 seconds User action: every button pressBoth systems allow for skew in the counter value2

The S/Key systemNotation:H(n)(x) (public vk, stateful)H(H( H(x) ))n timesAlgorithm G: (setup) Choose random key k K Output sk (k,n) ; vk H(n 1)(k)Identification:kH(n-2)(k)H(k)pwd #4pwd #3H(n-1)(k)pwd #2H(n)(k)pwd #1H(n 1)(k)vk2

The S/Key system(public vk, stateful)Identification (in detail): Prover (sk (k,i)):send t H(i) (k) ; set sk (k,i-1) Verifier( vk H(i 1)(k) ): if H(t) vk then vk t, output “yes”Notes:vk can be made public;but need to generate new sk after n logins (n 106 )“Thm”:S/Keyn is secure against eavesdropping (public vk)provided H is one-way on n-iterates2

SecurID vs. S/KeyS/Key: public vk,limited number of auths often implemented using pencil and paperSecurID: secret vk,unlimited number of auths often implemented using secure token2

ID protocols secure against active attacksa.k.a Challenge-Response Protocols

Active AttacksvkUser P(prover)probe #1Server V(verifier)probe #qskimpersonatevkOffline fake ATM: interacts with user; later tries toimpersonate to legit. ATMOffline phishing: phishing site interacts with user;later authenticates to real siteProtocols so far are vulnerable2

MAC-based Challenge Response(secret vk)k KUser P(prover)sk kvk km Mskt SMAC(k, m)Server V(verifier)vkVMAC(k, m, t)“Thm”:Protocol is secure against active attacks (secret vk),provided (SMAC , VMAC) is a secure MAC2

MAC-based Challenge ResponseProblems: vk must be kept secret on server dictionary attack when k is a human pwd: Given [ m , SMAC (pw, m) ] eavesdropper cantry all pw Dict to recover pwMain benefit: Both m and t can be short CryptoCard: 8 chars each3

Sig-based Challenge Response(public vk)Replace MAC with a digital signature:(sk, vk) GSIGUser P(prover)skvkServer V(verifier)m Mskt Sign(k, m)vkVerify(k, m, t)“Thm”:Protocol is secure against active attacks (public vk),provided (GSIG ,Sign,Verify) is a secure digital sig.but t is long ( 20 bytes)3

Summary ID protocols: useful in settings where adversary cannotinteract with prover during impersonation attempt Three security models: Direct:passwords (properly salted and hashed) Eavesdropping attacks: One time passwords SecurID: secret vk, unbounded logins S/Key:public vk, bounded logins Active attacks: challenge-response3

THE END

The SecurID system (secret vk, stateful) "Thm": if F is a secure PRF then protocol is secure against eavesdropping RSA SecurID uses a custom PRF: F 64 bit key 6 digit output Advancing state: sk (k, i 1) Time based: every 60 seconds User action: every button press Both systems allow for skew in the counter value 2 vasco 24 bit ctr