SESSION ID: CRYP-W02 Tickets, Please! Ticket Mediated Password Strengthening John Kelsey1,2, Dana Dachman-Soled3, Meltem Sönmez Turan1, Shweta Mishra1,4 1National Institute of Standards and Technology, Gaithersburg MD, USA 2Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Belgium 3University of Maryland, College Park MD, USA 4Department of Computer Science & Engineering Shiv Nadar University, Greater Noida, India #RSAC #RSAC Overview and Background General Problem: Accessing Local Encrypted Data Encrypted data is on my device (laptop, phone, etc.) – Probably also extra information: salt, check values, etc. Only I should be able to unlock it. – In practice, this means using a password. Right password =⇒ unlock the data Wrong password =⇒ fail 3 #RSAC Usual Approach: Password-Based Key Derivation I have a password—need to turn it into an encryption key. Applications: – – – – – Disk encryption (laptop) Device encryption (phone, tablet) File encryption (anything) Bitcoin private keys Other cryptographic keys 4 #RSAC What Goes Wrong: Password Guessing Attacks Suppose someone steals my device! Can they get my files? Online Attack: (User authentication) – Each password guess goes through some trusted entity – Limit on guesses = how many they will check – Easy to rate-limit guesses or lock accounts Offline Attack: (Password-based key derivation) – Attacker moves attack to his own machines – Limit on guesses = limit on processors * speed of guessing – No way to rate-limit guesses or lock accounts Same as password guessing after stealing a password file 5 #RSAC #RSAC Potential Solutions Mostly targeted at logging in, not deriving keys. PAKE schemes – User and Server establish a shared key from a shared password. Password-protected secret sharing – User splits secret into shares, gives to many different servers. – Password is used along with shares to reconstruct secret. Password strengthening – Use a hardened backend machine to add security 6 #RSAC Password Strengthening User: pwd -> Server Server: F(pwd) -> Backend Backend: G(F(pwd)) -> Server Server: 7 Check pwd file OK or ⏊ -> User #RSAC TMPS Ticket Mediated Password Strengthening #RSAC TMPS: Elevator Pitch Involve server in password-based key derivation. – Prevents offline attack, but requires being online to unlock files. Interact with server to get tickets. Tickets – Entitles me to help from server with one specific computation. – Server will not accept same ticket twice – Result: One ticket = one password guess Later: Use tickets to unlock my payload key K*. – Have to interact with server to unlock. Steal my laptop with 100 tickets on it – You can try 100 guesses for my password – After that, no way to unlock my files 9 #RSAC The Big Idea User device has encrypted data and tickets. – Tickets can't be used without help of Server. – Each ticket bound to specific password and payload key. To decrypt data, user device uses password + ticket – Interact with Server to decrypt data – Server won’t allow ticket to be reused – Server learns nothing about password, key, or who’s using ticket. 10 #RSAC TMPS: The Protocols In order to make a TMPS scheme work, we need: Setup – Server establishes its signing and encryption keys. REQUEST – User starts with password P and key K* – User ends with t new tickets bound to (P, K*) UNLOCK – User starts with password P’ and a ticket. – User interacts with Server. – User recovers K* only if P’ = P, and ticket valid. 11 REQUEST • #RSAC User device must know: • K* (payload key) • P (password) • User forgets B, C, D at end. 12 What does a ticket look like? Ticket is S,E,F,Z. S = random salt (different for each ticket) – So password hashes sent to server all look different! E = Secret value B encrypted under Server’s public key – B is also different for each ticket F = blind signature on E – So Server can’t link tickets with users Z = Verifiable encryption of K* under D – Reminder: D is function of salt, password, and B – Decrypting verifies correctness of password 13 #RSAC UNLOCK • Start with ticket and password P’. • Expend one ticket to test a password guess. #RSAC 14 UNLOCK security 1. Random S for each ticket: C’ different for each ticket. 2. Wrong P’ means wrong C’. 3. Repeated or invalid tickets rejected. 4. Wrong C’ -> wrong D’ -> failed decryption #RSAC 15 Getting tickets, limiting guesses Can only REQUEST new tickets when you know P