Yesterday, I took a critical look at the difficulty of interpreting progress in password cracking. Today I’ll make a broader argument that even if we had good data to evaluate cracking efficiency, recent progress isn’t a major threat the vast majority of web passwords. Efficient and powerful cracking tools are useful in some targeted attack scenarios, but just don’t change the economics of industrial-scale attacks against web accounts. The basic mechanics of web passwords mean highly-efficient cracking doesn’t offer much benefit in untargeted attacks. (more…)
Posts filed under 'Authentication
Password cracking has returned to the news, with a thorough Ars Technica article on the increasing potency of cracking tools and the third Crack Me If You Can contest at this year’s DEFCON. Taking a critical view, I’ll argue that it’s not clear exactly how much password cracking is improving and that the cracking community could do a much better job of measuring progress.
Password cracking can be evaluated on two nearly independent axes: power (the ability to check a large number of guesses quickly and cheaply using optimized software, GPUs, FPGAs, and so on) and efficiency (the ability to generate large lists of candidate passwords accurately ranked by real-world likelihood using sophisticated models). It’s relatively simple to measure cracking power in units of hashes evaluated per second or hashes per second per unit cost. There are details to account for, like the complexity of the hash being evaluated, but this problem is generally similar to cryptographic brute force against unknown (random) keys and power is generally increasing exponentially in tune with Moore’s law. The move to hardware-based cracking has enabled well-documented orders-of-magnitude speedups.
Cracking efficiency, by contrast, is rarely measured well. Useful data points, some of which I curated in my PhD thesis, consist of the number of guesses made against a given set of password hashes and the proportion of hashes which were cracked as a result. Ideally many such points should be reported, allowing us to plot a curve showing the marginal returns as additional guessing effort is expended. Unfortunately results are often stated in terms of the total number of hashes cracked (here are some examples). Sometimes the runtime of a cracking tool is reported, which is an improvement but conflates efficiency with power. (more…)
With the launch of Mac OS X 10.7 (Lion), Apple has introduced a volume encryption mechanism known as FileVault 2.
During the past year Joachim Metz, Felix Grobert and I have been analysing this encryption mechanism. We have identified most of the components in FileVault 2’s architecture and we have also built an open source tool that can read volumes encrypted with FileVault 2. This tool can be useful to forensic investigators (who know the encryption password or recovery token) that need to recover some files from an encrypted volume but cannot trust or load the MAC OS that was used to encrypt the data. We have also made an analysis of the security of FileVault 2.
UPDATE 2012-06-07: LinkedIn has confirmed the leak is real, that they “recently” switched to salted passwords (so the data is presumably an out-of-date backup) and that they’re resetting passwords of users involved in the leak. There is still no credible information about if the hackers involved have the account names or the rest of the site’s passwords. If so, this incident could still have serious security consequences for LinkedIn users. If not, it’s still a major black eye for LinkedIn, though they deserve credit for acting quickly to minimise the damage.
LinkedIn appears to have been the latest website to suffer a large-scale password leak. Perhaps due to LinkedIn’s relatively high profile, it’s made major news very quickly even though LinkedIn has neither confirmed nor denied the reports. Unfortunately the news coverage has badly muddled the facts. All I’ve seen is a list 6,458,020 unsalted SHA-1 hashes floating around. There are no account names associated with the hashes. Most importantly the leaked file has no repeated hashes. All of the coverage appears to miss this fact. Most likely, the leaker intentionally ran it through ‘uniq’ in addition to removing account info to limit the damage. Also interestingly, 3,521,180 (about 55%) of the hashes have the first 20 bits over-written with 0. Among these, 670,785 are otherwise equal to another hash, meaning that they are actually repeats of the same password stored in a slightly different format (LinkedIn probably just switched formats at some point in the past). So there are really 5,787,235 unique hashes leaked. (more…)
Over a year ago, we blogged about a bug at Gawker which replaced all non-ASCII characters in passwords with ‘?’ prior to checking. Along with Rubin Xu and others I’ve investigated issues surrounding passwords, languages, and character encoding throughout the past year. This should be easy: websites using UTF-8 can accept any password and hash it into a standard format regardless of the writing system being used. Instead though, as we report a new paper which I presented last week at the Web 2.0 Security and Privacy workshop in San Francisco, passwords still localise poorly both because websites are buggy and users have been trained to type ASCII passwords only. This has broad implications for passwords’ role as a “universal” authentication mechanism. (more…)
I’ve written quite a few posts about passwords, mainly focusing on poor implementations, bugs and leaks from large websites. I’ve also written on the difficulty of guessing PINs, multi-word phrases and personal knowledge questions. How hard are passwords to guess? How does guessing difficulty compare between different groups of users? How does it compare to potential replacement technologies? I’ve been working on the answers to these questions for much of the past two years, culminating in my PhD dissertation on the subject and a new paper at this year’s IEEE Symposium on Security and Privacy (Oakland) which I presented yesterday. My approach is simple: don’t assume any semantic model for the distribution of passwords (Markov models and probabilistic context-free-grammars have been proposed, amongst others), but instead learn the distribution of passwords with lots of data and use this to estimate the efficiency of an hypothetical guesser with perfect knowledge. It’s been a long effort requiring new mathematical techniques and the largest corpus of passwords ever collected for research. My results provide some new insight on the nature of password selection and a good framework for future research on authentication using human-chosen distributions of secrets. (more…)
As any computer user already knows, passwords are a usability disaster: you are basically told to “pick something you can’t remember, then don’t write it down“, which is worse than impossible if you must also use a different password for every account. Moreover, security-wise, passwords can be shoulder-surfed, keylogged, eavesdropped, brute-forced and phished. Notable industry insiders have long predicted their demise. Over the past couple of decades, dozens of alternative schemes have been proposed. Yet here we are in 2012, still using more and more password-protected accounts every year. Why? Can’t we do any better? Don’t the suggested replacements offer any improvements?
The paper I am about to present at the IEEE Symposium on Security and Privacy in San Francisco (Oakland 2012), grown out of the “related work” section of my earlier Pico paper and written with coauthors Joe Bonneau, Cormac Herley and Paul van Oorschot, offers a structured and well-researched answer that, according to peer review, “should have considerable influence on the research community”. It offers, as its subtitle says, a framework for comparative evaluation of password replacement schemes.
We build a large 2D matrix. Across the columns we define a broad spectrum of 25 benefits that a password replacement scheme might potentially offer, starting with USABILITY benefits, such as being easy to learn, or not requiring a memory effort from the user, and SECURITY benefits, such as resilience to shoulder-surfing or to phishing. These two broad categories, and the tension between them, are relatively well-understood: it’s easy to provide more usability by offering less security and vice versa. But we also introduce a third category, DEPLOYABILITY, that measures how easy it would be to deploy the scheme on a global scale, taking into account such benefits as cost per user, compatibility with deployed web infrastructure and accessibility to people with disabilities.
Next, in the rows, we identify 35 representative schemes covering 11 broad categories, from password managers through federated authentication to hardware tokens and biometric schemes. We then carefully rate each scheme individually, with various cross-checks to preserve accuracy and consistency, assessing for each benefit whether the given scheme offers, almost offers or does not offer the benefit. The resulting colourful matrix allows readers to compare features at a glance and to recognize general patterns that would otherwise be easily missed.
Contrary to the optimistic claims of scheme authors, who often completely ignore some evaluation criteria when they assert that their scheme is a definite improvement, none of the examined schemes does better than passwords on every benefit when rated on all 25 benefits of this objective benchmark.
From the concise overview offered by the summary matrix we distil key high level insights, such as why we are still using passwords in 2012 and are probably likely to continue to do so for quite a while.
How can we make progress? It has been observed that many people repeat the mistakes of history because they didn’t understand the history book. In the field of password replacements, it looks like a good history book still needed to be written! As pointed out during peer review, our work will be a foundational starting point for further research in the area and a useful sanity check for future password replacement proposals.
An extended version of the paper is available as a tech report.
Using a multi-word “passphrase” instead of a password has been suggested for decades as a way to thwart guessing attacks. The idea is now making a comeback, for example with the Fastwords proposal which identifies that mobile phones are optimised for entering dictionary words and not random character strings. Google’s recent password advice suggests condensing a sentence to form a password, while Komanduri et al.’s recent lab study suggests simply requiring longer passwords may be the best security policy. Even xkcd espouses multi-word passwords (albeit with randomly-chosen words). I’ve been advocating through my research though that authentication schemes can only be evaluated by studying large user-chosens distribution in the wild and not the theoretical space of choices. There’s no public data on how people choose passphrases, though Kuo et al.’s 2006 study for mnemonic-phrase passwords found many weak choices. In my recent paper (written with Ekaterina Shutova) presented at USEC last Friday (a workshop co-located with Financial Crypto), we study the problem using data crawled from the now-defunct Amazon PayPhrase system, introduced last year for US users only. Our goal wasn’t to evaluate the security of the scheme as deployed by Amazon, but learn more how people choose passphrases in general. While this is a relatively limited data source, our results suggest some caution on this approach. (more…)
Note: this research was also blogged today at the NY Times’ Bits technology blog.
I’ve personally been researching password statistics for a few years now (as well as personal knowledge questions) and our research group has a long history of research on banking security. In an upcoming paper at next weel’s Financial Cryptography conference written with Sören Preibusch and Ross Anderson, we’ve brought the two research threads together with the first-ever quantitative analysis of the difficulty of guessing 4-digit banking PINs. Somewhat amazingly given the importance of PINs and their entrenchment in infrastructure around the world, there’s never been an academic study of how people actually choose them. After modeling banking PIN selection using a combination of leaked data from non-banking sources and a massive online survey, we found that people are significantly more careful choosing PINs then online passwords, with a majority using an effectively random sequence of digits. Still, the persistence of a few weak choices and birthdates in particular suggests that guessing attacks may be worthwhile for an opportunistic thief. (more…)
Earlier this month, I blogged about monitoring password-guessing attacks on a server, via a patched OpenSSH. This experiment has now been running for just over two weeks, and there are some interesting results. I’ve been tweeting these since the start.
As expected, the vast majority of password-guessing attempts are quite dull, and fall into one of two categories. Firstly there are attempts with a large number of ‘poor’ passwords (e.g. “password”, “1234″, etc…) against a small number of accounts which are very likely to exist (almost always “root”, but sometimes others such as “bin”).
Secondly, there were attempts on a large number of accounts which might plausibly exist (e.g. common first names and software packages such as ‘oracle’). For these, there were a very small number of password attempts, normally only trying the username as password. Well established good practices such as choosing a reasonably strong password and denying password-based log-in to the root account will be effective against both categories of attacks. Surprisingly, there were few attempts which were obviously default passwords from software packages (but they perhaps were hidden in the attempts where username equalled password). However, one attempt was username: “rfmngr”, password: “$rfmngr$”, which is the default password for Websense RiskFilter (see p.10 of the manual).
There were, however, some more interesting attempts. (more…)