Cracking-Resistant Password Vaults Using Natural Language Encoders

Cracking-Resistant Password Vaults Using Natural Language Encoders Rahul Chatterjee UW-Madison & Cornell University (Fall 2015) Joseph Bonneau Stanford University Ari Juels Thomas Ristenpart UW-Madison & Cornell Tech (next week) Cornell Tech (Jacobs Inst.)

Password Vaults (a.k.a Password Manager) Cloud Storage Plaintext Vault Encrypted Vault PKCS#5 encryption 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a family00 family01 family.1 qwerty poiuyt.12 mypass4 Master password

Password Vaults Increasing in Popularity And many more .

Stealing Password Vaults Cloud Storage Plaintext Vault Encrypted Vault PKCS#5 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a family00 family01 family.1 qwerty poiuyt.12 mypass4 Stealing Vault 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Server Compromise o L. Whitney, LastPass CEO reveals details on security breach, CNet, May 2011. Exfiltration from Client Machine o Z. Li et al., The emperor s new password manager: Security analysis of web-based password managers, USENIX Security, 2014.

Offline Brute Force Attack 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Vault Ciphertext Attacker s guesses 123456 password iloveyou ?%?U? sU %a ? Decryption (PKCS#5) mypass4 abc123 nicole Daniel Output of Decryption Random Junk . . .

Offline Brute Force Attack 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Vault Ciphertext Attacker s guesses 123456 password iloveyou ?%?U? ?a sU% ?%a Decryption (PKCS#5) mypass4 abc123 nicole Daniel Output of Decryption Random Junk . . .

Offline Brute Force Attack 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Vault Ciphertext Attacker s guesses 123456 password iloveyou 70&c#a&a33 9019f*a ? U % 7 Decryption (PKCS#5) mypass4 abc123 nicole Daniel Output of Decryption Random Junk . . .

Offline Brute Force Attack 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Vault Ciphertext Attacker s guesses 123456 password iloveyou family00 family01 family.1 qwerty poiuyt.12 Decryption (PKCS#5) mypass4 abc123 nicole Daniel Output of Decryption Yes, this is it. Runtime of the attack = # of decryption attempts Offline Work* . . . [*] Hashing and salting slows down by small factor.

So What ?!? = Lose Your Vault Lose Your Passwords 70% of passwords can be cracked <1bn guesses [3] [3] R. Veras, C. Collins, and J. Thorpe, On the semantic patterns of passwords and their security impact, in NDSS, 2014.

Our Contribution Goal: Prevent offline attack on password vaults How ? Decoy Techniques Show existing decoy techniques have a subtle vulnerability Kamouflage by Bojinov et al. can degrade security compared to standard password-based encryption Build a new mechanism: Natural Language Encoder (NLE) Honey Encryption NoCrack: new password vault system with decoys

Kamouflage 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a abcdef12 abcdef02 abcdef#1 thomas temple#00 Vault Ciphertext shishi1 PKCS#5 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a travis99 travis12 travis@7 soccer smiles@33 violet9 PKCS#5 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a family00 family01 family.1 qwerty poiuyt.12 mypass4 PKCS#5 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a scooby33 scooby45 scooby@3 vanbus weiwei!69 zxcvbn9 N = 4 (3 decoy vaults) PKCS#5

Kamouflage 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Real Vault, when mpw = real password 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Decoy Vault, when mpw decoy passwords Kamouflage Decryption 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Junk None of the above mpw 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a N = 4 (3 decoy vaults)

Brute-Forcing Kamouflage Kamouflage Vault Ciphertext Attacker guesses 123456 password Iloveyou 0&c#a&a 339019f*a2; 19dd229 6%7a'82c0% s? Kamouflage Decryption violet9 mypass4 abc123 nicole Daniel . . .

Brute-Forcing Kamouflage Kamouflage Vault Ciphertext Attacker guesses 123456 password Iloveyou travis99 travis12 travis@7 soccer smiles@33 Kamouflage Decryption violet9 mypass4 abc123 nicole Daniel . . .

Brute-Forcing Kamouflage Kamouflage Vault Ciphertext Attacker guesses 123456 password Iloveyou family00 family01 family.1 qwerty poiuyt.12 Kamouflage Decryption violet9 mypass4 abc123 nicole Daniel . . .

The Nave Attack shishi1 violet9 mypass4 zxcvbn9 scooby33 scooby45 scooby@3 vanbus weiwei!69 abcdef12 abcdef02 abcdef#1 thomas temple#00 travis99 travis12 travis@7 soccer smiles@33 family00 family01 family.1 qwerty poiuyt.12 ? To check if vault is real or decoy: login attempt using password Runtime of the Attack = Offline Work of PBE + N/2 Online Work (N = # of explicitly stored vaults) Kamouflage security claim: na ve attack is the best possible

But... WE FOUND A PROBLEM IN THE DECOY GENERATION family00 family01 family.1 qwerty poiuyt.12 mypass4 Real { abcdef12 abcdef02 abcdef#1 thomas temple#00 travis99 travis12 travis@7 soccer smiles@33 violet9 scooby33 scooby45 scooby!3 vanbus weiwei!69 Decoys .... zxcvbn9 shishi1

Attacking Kamouflage Kamouflage Vault Attacker guesses ?%U veronica viper01 violet9 whatsup! Wlidcat2 year2012 secret7 mypass4 Kamouflage Decryption Random Junk

Attacking Kamouflage Kamouflage Vault Attacker guesses travis99 travis12 travis#7 soccer smiles#33 veronica viper01 violet9 whatsup! Wlidcat2 year2012 secret7 mypass4 Kamouflage Decryption Master Password has 6 characters, followed by 1 digit. Big speed up Check violet9 with online query If not, move to next master password w/ structure

Attack Results Kamouflage claimed (for N=103): 100% offline work of standard Password Based Encryption + N/2 = 500 expected online queries Simulations with Yahoo password leak: 50% offline work of standard Password Based Encryption + 11 expected online queries

The situation so far Standard encryption vulnerable to brute force attacks Kamouflage can be less secure than standard encryption

Honey Encryption by Juels and Ristenpart, EUROCRYPT 2014 Decryption with any key outputs plausible plaintext m Bit string Encode s key Encrypt C

Honey Encryption by Juels and Ristenpart, EUROCRYPT 2014 Decryption with any key outputs plausible plaintext C Decrypt key Decrypt key S S Decode Decode m m

Honey Encryption by Juels and Ristenpart, EUROCRYPT 2014 Decryption with any key outputs plausible plaintext C m Encode Decrypt key S s Decode key Encrypt C Key technical challenge: building secure encoders m

Natural Language Encoder (NLE) S pw Decode Encode pw S Bit-string Security (informally): No attacker can distinguish between decode of random S and a true, freshly chosen plaintext

Modern Password Crackers [Weir et al. 2010] [Veras et al. 2014] Password Leaks Training Model of password distribution 123456 password iloveyou Cracker Use model to sample passwords in the order of their likelihood Better Password Model Better Crackers

Password-model Based NLEs We show how to use common password models to build NLEs N-gram Markov models Probabilistic Context-Free Grammars (PCFGs) Handling related passwords in vaults S Decode High level idea: Encode random path through PCFG as uniform-looking bit string S pw W6 D1 Decode uses input to choose a random parse tree from PCFG See paper for details violet 9 Better Password Model Better Decoys

NoCrack (a new kind of password vault) 1. NLE + HE = decrypt w/ wrong master password gives realistic password vault 2. Supports machine generated random passwords 3. Domain privacy, easy online sync etc.

Security of NoCrack Security goal: output of Decrypt should look real Machine learning classifiers Yahoo leak dataset, 50% attack success: NoCrack Kamouflage Offline work 20,000 10,000 Online work 6,666 11 Attacker will have to make many online queries

Limitations/Future Work Side information about the victim might decrease online work significantly Master password related to the passwords inside the vault Website password restrictions Improved attacks Note: securitynever worse than standard password-based encryption

Summary We showed an effective attack against only prior work on decoy techniques. #KamouflageVulnerable We devised a new mechanism to create decoys. #NaturalLanguageEncoder Prototype of a Password Vault that utilizes NLE and HE, and offers most of the functionalities of modern password vaults. #NoCrack Code and data available at: https://pages.cs.wisc.edu/~rchat/projects/NoCrack.html

Bibliography [1] H. Bojinov, E. Bursztein, X. Boyen, and D. Boneh, Kamouflage: Loss-resistant password management, in ESORICS, 2010 [2] Joseph Bonneau. The science of guessing: analyzing an anonymized corpus of 70 million passwords. In SP, 2012 [3] R. Veras, C. Collins, and J. Thorpe, On the semantic patterns of passwords and their security impact, in NDSS, 2014. [4] M. Weir, S. Aggarwal, B. de Medeiros, and B. Glodek, Password cracking using probabilistic context-free grammars, SP09, 2009 [5] A. Juels and T. Ristenpart, Honey Encryption: Beyond the brute-force barrier, in EUROCRYPT, 2014

Issues with Kamouflage All master passwords share same template Learning the template of the master password is N times more likely After learning the template only try the passwords that matches the template Replacements are selected with uniform probability real master password is way more probable than decoys, needs very few online queries only. Kamouflage+ also fails.

But... WE FOUND A PROBLEM IN THE DECOY GENERATION W6D2 W6D21 W6S1D1 W61 W62S1D22 Templates family00 family01 family.1 qwerty poiuyt.12 Real W6D1 mypass4 { All master passwords share the abcdef12 abcdef02 abcdef#1 thomas temple#00 same template! travis99 travis12 travis@7 soccer smiles@33 violet9 scooby33 scooby45 scooby!3 vanbus weiwei!69 Decoys .... zxcvbn9 shishi1

Honey Encryption Plaintext mpw* HE-Encrypt Ciphertext mpw1 mpw3 HE-Decrypt HE-Decrypt mpw2 mpw2 HE-Decrypt HE-Decrypt

Decoy Technique Vault Ciphertext 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Attacker s ordering of master passwords 123456 password iloveyou password iloveyou pass4ever iloveyou password1 Decryption (Decoy) mypass4 abc123 nicole Daniel Output of Decryption . . .

Decoy Technique Vault Ciphertext 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Attacker s ordering of master passwords 123456 password iloveyou letmein treehouse letme1n l3tmein! tr33h0us3 Decryption (Decoy) mypass4 abc123 nicole Daniel Output of Decryption . . .

Decoy Technique Vault Ciphertext 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Attacker s ordering of master passwords 123456 password iloveyou Madona12 Madona12 123456 m@dona1 123456789 Decryption (Decoy) mypass4 abc123 nicole Daniel Output of Decryption . . .

Decoy Technique Vault Ciphertext 0xe1f3f4a 0x73bc52e 0x4e5e373 0x3c8b8ea 0xe33188a Attacker s ordering of master passwords 123456 password Iloveyou family00 family01 family.1 qwerty poiuyt.12 Decryption (Decoy) mypass4 abc123 nicole Daniel Output of Decryption . . .

New Decoys Technique Honey EncryptionbyJuels and Ristenpart, EUROCRYPT 2014. Decryption Never Fails! Wrong pass Decoy Text (fresh sample) Cool Idea , But needs an encoder to covert between uniform bit- string and plain text distribution Showed for toy distribution. For real distributions, it was left as an open problem. We show how to build the encoder for Natural Languages, e.g., Password Vaults

NLE for Single Password (using PCFG) W6 0.20, 0.20 W6D1 0.12, 0.32 D6 0.10, 0.42 W8 0.09, 0.51 . Y8 S (pdf) (cdf) 0.001, 1.00 . abcdef qwerty greats horror invent W6 (pdf) (cdf) 0.15, 0.15 0.11 , 0.26 0.095 , 0.355 0.09, 0.445 .002, 1.00 Base PCFG Base PCFG (this one was proposed by Weir et al., SP09)

Password Model to NLE (using PCFG) We give ways to convert password sampler techniques to secure NLEs n-gram PCFG Encode every branch in the parse tree encode( family00 , PCFG) : S decode(random bit-string, PCFG) : reconstruct the parse tree and output the string it parses. W8 Y decode(another random bit-string, PCFG): a random parse tree and a random password password ! Parse Tree of password!

NLE for Single Password (using PCFG) W6 0.20, 0.20 W6D1 0.12, 0.32 D6 0.10, 0.42 W8 0.09, 0.51 . Y8 S (pdf) (cdf) 0.001, 1.00 . abcdef qwerty greats horror invent W6 (pdf) (cdf) 0.15, 0.15 0.11 , 0.26 0.095 , 0.355 0.09, 0.445 .002, 1.00 Encode a rule (e.g. S W8 ): choose a random number between [0.42, 0.51)

NLE for Single Password (using PCFG) W6 0.20, 0.20 W6D1 0.12, 0.32 D6 0.10, 0.42 W8 0.09, 0.51 . Y8 S (pdf) (cdf) 0.001, 1.00 . abcdef qwerty greats horror invent W6 (pdf) (cdf) 0.15, 0.15 0.11 , 0.26 0.095 , 0.355 0.09, 0.445 .002, 1.00 Decode a rule (e.g. S, 0.29): /* Inverse Transform Sampling */ 0.20 0.29 < 0.32 W6D1

NLE for Single Password (using PCFG) Encode( pw ): Create a parse tree of the password in the base PCFG Encode each rule in the parse tree pad with random numbers (if needed) Parse Tree Encoding S W8D2; W8 password ; D2 12 ; 0.23, 0.12, 0.20, 0.13, 0.93, . passwrod12

NLE for Single Password (using PCFG) Decode ( list of bit-string ): Decode each bit-string into rules and construct the parse tree from S (stop when it is complete) Get the string that is generated by the parse tree. Parse Tree Encoding S W8D2; W8 password ; D2 12 ; 0.23, 0.12, 0.20, 0.13, 0.93, . passwrod12

Evaluating Single Password NLE Classifiers for decoy and real passwords Trained the Base PCFG with RY-tr leak (#Decoy) Tested with RY-ts, MySpace , Yahoo leaks (#Real) 1-in-q experiment Metric of Evaluation: 1. Accuracy of classification ( ) 2. Rank-of-real based on classifier s confidence (r) Report average over all the passwords in each of the test leaks

Results 50% Best NLE 50% 60% NLE using PCFG (by Weir et al.) 35% Classifier thinks 35% of the decoy passwords are more realistic than the real one! Worst NLE 0% 100% r Rank-of-real Classification accuracy

Evaluating Single Password NLE MySpace Yahoo RY-ts r r r Weir PCFG n-gram 63% 35% 54% 36% 60% 25% 70% 22% 68% 41% 61% 41% For best NLE and r both should be close to 50%. r denotes the amount of online work attacker has to do.