Recently when logging into one of my credit card providers, I was greeted by a familiar screen. After entering in my username, the service asked me to supply 3 random characters from my password to validate ownership of my account.
It is increasingly common knowledge in the InfoSec community that this practice is the antithesis of, what we now understand to be, secure password management.
For starters; sites prompting you for Partial Password Validation cannot store your passwords securely using algorithms like BCrypt or Argon2. If the service provider is ever breached, such plain-text passwords can be used to login to other sites where the account holder uses the same password (known as a Credential Stuffing attack).
Increased difficulty using long, randomly-generated passwords from Password Managers, leads to users favouring their memory over securely generated unique passwords. Those using Password Managers must extract their password from their vault, paste it somewhere else and then calculate the correct characters to put in. With this increased complexity, it further incentivises users to (re-)use simple passwords they can remember and count off on their fingers (and likely repeatedly use on other sites).
This is not to distinct thinking that originally bought us complex password composition rules, which would also ultimately incentivise password re-use. I have previously written how broken password management policies came about and the collaborative solution I worked on with security researcher, Troy Hunt, to dissuade password reuse (examples of this implementation can be found on Troy’s blog).
However, in this blog post I want us to follow through some of the logic of Partial Password Validation that is used by so many websites, including banks and services which certainly contain sensitive data. Let’s see how effective this strategy really is.
How secure is partial password data?
In one data breach, we saw that 86% of users were using passwords already in data breaches. So, if we have certain characters of a password, how easy is it to identify that password from a data breach?
So; how much information can 3 characters provide us about a password a user logs in with (assuming such a password is breached)?
By selecting 10,000 passwords randomly from a public database of 488,129 breached passwords (after excluding passwords less than 8 characters long), I selected 3 random characters from each password and saw how many passwords in the complete dataset had the same characters in the same place as the original password. This simulation was run 11 times per password considered.
In the 110,000 simulations, 58% of tested 3-character password segments were only valid for that password in the database. Additionally, 28% could be associated with only one other password and 8% with two other passwords.
As such, we can demonstrate that in this database, the presence of only 3 characters of a password is sufficient to let us breach a significant proportion of such accounts. Using slow brute force attacks, hundreds of passwords can be checked against an account before triggering any form of rate limiting (if any), combining password segments with common password databases allows us to bring down the search candidates substantially.
Research for these tactics exists outside the scope of simulations alone. Prior work by the University of Edinburgh and the University of Aberdeen in a paper on Partial Password implementations and attacks, created a password projection dictionary using a larger data breach (RockYou) alongside recording credentials during login attempts to user accounts. Result collection was based on a survey of user logins to online banking sites and showed a worryingly high success rate of being able to predict solutions to challenge pages (in particular, against banking websites which required no, or a weak, second credential):
We find that with 6 guesses, an attacker can respond correctly to 2-place challenges on 6-digit PINs with a success rate of 30%. Recording up to 4 runs, an attacker can succeed over 60% of the time, or by combining guessing and recording, over 90%. Alphanumeric passwords do somewhat better: responding to 3-place challenges on 8-character alphanumeric passwords, with up to 10 guesses, the attacker can achieve a success rate of 5.5%. Combining guessing and recording increases that to 25% with one recorded run and at least 80% with four runs.
Partial Password Validation arguably exists to prevent key loggers (either in software or hardware form) from learning your complete password; however now let's put this hypothesis to the test next.
Getting the full password
Every time my banking site asks for a set of random characters of my password on login, someone who knows my keystrokes can learn even more. With personal computer ownership at an all time high (e.g. household computer ownership at 88% in the UK) it is increasingly likely such users will repeatedly login to their services using a single device.
Let's consider the threat model of whether Partial Password Validation actually helps. How many times would a user need to repeatedly login until their password is fully breached? This problem represents a modified form of the coupon collector's problem (except with multiple selections), and as such approximations can be calculated in mathematical terms; but instead, here I'll demonstrate this using real password data and simulations.
It is trivial to calculate how many possible ways 3 random characters can be selected from a password using binomial coefficients; there are 220 ways of selecting 3 characters from a 12 character password, but it is fundamentally important to know that, at the end of the day, you only need 12 characters to breach a password. Every time a user is prompted for more random characters, we have more chance of finding out what their password is.
By repeatedly taking the lengths of random passwords (over 8 characters in lengths), I ran a simulation to see how many times it would take for the entire password to become known. 110,000 simulations were run collectively on 10,000 passwords.
In simulation, 58% of passwords are revealed in entirety after 7 logins, 90% after 12 and 99% after 19 logins. These results would be even more garish, with a maximum password length constraint (and/or including passwords less than 8 characters); as is implemented by many online banks using such an approach.
The Road to Multi-Factor Authentication
There we have it; there is no substantive keylogger protection from Partial Password Validation; all you get is a guarantee that the service you're dealing with isn't capable (or is too lazy) to properly secure your passwords.
Password Managers are a blessing and they provide a huge boost in security by allowing users to set strong, unique passwords on a per site basis and Partial Password Validation poses a massive usability frontier to users adopting such practices. In the words of the British National Cyber Security Centre: "Let them paste passwords".
So what do you do instead? Instead of merely using what your customers know to secure their accounts, additionally use something they have. The industry standard for key logger protection is Two Factor Authentication (or Multi Factor Authentication); using either apps on your users smartphones to generate cryptographically secure tokens, or, as is increasingly the case of banks, giving your customers hardware Two Factor token generators to validate their login attempts. Hardware token generators provide a distinct piece of hardware to generate secure tokens, that users cannot use to login to their online accounts.
Increasingly SMS is used to send a user a password to validate their login attempt, in addition to a password the users enters. SMS isn't technically Second Factor Authentication, and instead represents a One Time Password. This can also be said for users logging in to a site, using a password, on the same device they use to generate their one time token. Additionally, SMS tokens are not cryptographically generated on the device itself, using the RFC 6238 standard that's employed by 2FA apps, but are sent over a protocol with numerous security shortcomings. In practice, this means that interception can reveal the One Time Password that you receive.
Whilst there are better alternatives to SMS, and indeed users who are educated to use such tactics should be allowed to do so, there is a usability gap to setting up Two Factor Authentication and somewhat of a cost and operational barrier to issuing users hardware devices. However; in a time where the vast majority of users guard their secure accounts using nothing more than their passwords, it is somewhat excusable to default opt-in users to SMS One Time Passwords, whilst providing the option for Two Factor Authentication if desired. The UK tax office (Her Majesty's Revenue & Customs) have gone down this route, requiring users to set-up some form of Multi-Step Verification before being able to proceed with managing their accounts; either via SMS, landline or an authenticator app.
In conclusion; whilst SMS isn't the most secure way of generating a One Time Password, it offers huge advantages over a user only using a password. Any form of One Time Password is better than none at all, and it provides a path for users to handle the security threats that Partial Password Verification promises, but falls short on.
Want to help businesses, small and big, protect their users from security threats, small and large? The Cloudflare technical support team is hiring.