Website specific password manager

Following on from my post about what the benefits would be if websites would enforce unique passwords for users, I thought I would try to come up with a better scheme that avoided the dichotomy of the ability of users to remember passwords and password complexity.

My goal was to devise a way a website could allow users to choose a password they could remember and gain the same benefits as if users chose unique passwords.  Additionally, the security of the scheme should ideally be better, but at least no worse than what (a well designed) password authentication scheme is today.

The basic idea is the same as the way a password manager works.  Password managers allow a user to choose a strong local password that is used on their client machine to protect a password for a certain website.  When a user enters their local password in their password manager, it decrypts the website password, and then that is sent to the website to authenticate the user.  Usually the encrypted password(s) are stored online somewhere so the password manager can be used on multiple devices.

The problem (I use this term loosely) with password managers is it requires users to go to the effort of using one, or perhaps understanding what it is and trusting it with their passwords.  It would be preferable to get some of the benefits of a password manager on a website without requiring the user to know or even be aware one was being used.

So what I describe below is effectively a website specific password manager (that manages just 1 password, the password of the website).  The password management will happen behind the scenes and the user will be none the wiser.  The basic idea is that when a user registers with a website and chooses a password, that password will actually be a local password used to encrypt the actual website password.  The actual website password will be chosen by the website, be very strong and be unique (to the website).  When a user tries to log on, the following would happen:

• The user will be prompted for their username and (local) password,
• The entered username will be sent to the website and used to recover the encrypted password store (encrypted with the local password and containing the actual website password) for that user, which is then sent to the client
• On the client the local password is used to decrypt the encrypted password store to recover the website password
• The website password is sent to the website to authenticate the user.

Ignoring security for a second, we can improve the efficiency of the scheme by caching the encrypted password store on the client.  In fact the only reason the encrypted password store is stored on the server is to accommodate login from multiple devices.  It's an assumed requirement that login from multiple devices is necessary and that registering a device with a website doesn't scale sufficiently for it to be an option.

To examine the security of the scheme we need more details, so I provide those below.  But first I will say what security threats we are NOT looking to mitigate.  This scheme doesn't concern itself with transport security (so it's assumed HTTPS is used for communications), doesn't protect against XSS attacks (attacker script in the client will be able to read passwords when they are entered), doesn't protect against online password guessing attacks (it's assumed the website limits the number of password guesses).

The threats we are concerned about though are:

• An attacker that gets an encrypted password store for a user should not be able to recover the user's local password in an offline attack.
• An attacker that gets a DB dump of password hashes should not be able to recover either the website password or the local password.

So let's get into the detail of the scheme.  Here is a description of the algorithms and parameters involved.

• Hash(), a password hashing algorithm like PBKDF2, bcrypt or scrypt. It's output size is 256 bits.
• HMAC_K(), this is HMAC-SHA256 using a secret key K.
• K, a 256 bit secret key used by the website solely for password functionality, it is not per-user, it is the same for all users.
• xor, this means the binary exclusive-or of two values.
• PwdW, the website password, a 256 bit strong random value.
• PwdL, the local password, chosen by the user.

Let's start with the registration process, a new user signs up:

• A user chooses to register with the website.
• The website generates a new PwdW and returns this to the client.
• The user chooses a password (and username if appropriate), this is PwdL.
• The client sends to the website, PwdW xor Hash(PwdL).
• The website stores (against the username), PwdW xor Hash(PwdL) and also PwdW xor HMAC_K(PwdW).

I've skipped over some of the implementation details here (like the Hash parameters etc), but hopefully provided enough details for analysis.  One important point is that the website does not store the value PwdW anywhere, it only stores the 2 values in the last step, namely:

• PwdW xor Hash(PwdL)      (this is the encrypted password store from the description above)
• PwdW xor HMAC_K(PwdW)  (this is the equivalent of the password hash in most schemes, it is used to verify that any PwdW submitted by a client is correct)

Now let's see what happens during login:

1. User visits the website and enters their username and PwdL
2. The client sends the username to the website, which looks up the encrypted password store, PwdW xor Hash(PwdL) and returns it to the client
3. The client generates Hash(PwdL) and uses this to recover PwdW by calculating (PwdW xor Hash(PwdL)) xor Hash(PwdL) = PwdW
4. The client sends PwdW to the website
5. The website recovers HMAC_K(PwdW) by calculating (PwdW xor HMAC_K(PwdW)) xor PwdW = HMAC_K(PwdW) (let's call this Recovered_HMAC).
6. The website calculates HMAC_K(PwdW) using the received value of PwdW from the client (let's call this Calculated_HMAC).
7. If Recovered_HMAC = Calculated_HMAC the user is successfully authenticated.

So let's address the threats we are concerned about, the first is "An attacker that gets an encrypted password store for a user should not be able to recover the user's local password in an offline attack."  Let's assume an attacker knows the username they want to target, and that they download the encrypted password store (PwdW xor Hash(PwdL)) for that user.  If we accept that PwdW is a random 256-bit value, then an attacker is unable to determine the value of Hash(PwdL) because there is a value of PwdW that gives every possible hash value of every possible local password that could be chosen.  This is the security property of the one-time pad.  Of course an attacker could instead generate Hash(PwdL) (by guessing PwdL) and calculate PwdW, but they have no idea if they are correct and would have to submit it to the website to determine if it was correct, however we are assuming there are controls in place that limit the number of online password guessing attempts.

The other threat we consider is "An attacker that gets a DB dump of password hashes should not be able to recover either the website password or the local password."  There are 2 scenarios we want to consider, when the attacker does not have access to the secret key K, and when they do.

If the attacker does not have access to K, then in this case the attacker has access to (PwdW xor Hash(PwdL)) and (PwdW xor Enc_K(PwdW)).  If the attacker tries to offline guess PwdW they have the problem of having no way to determine if a guess is correct, because they cannot verify the HMAC without the key K.  They can of course guess PwdW online by submitting it to the website, but we assume controls that mitigate this attack.  If the attack tries to guess PwdL, then they have exactly the same problem of being unable to offline verify if the calculated PwdW is correct.

If the attacker does have access to K then they have the same information that the website has and so can perform an offline (dictionary) attack against the local password PwdL.  How successful this attack is depends on the parameters of the password hashing scheme (Hash()) that were chosen and the complexity of the user chosen password PwdL.  For the purposes of this scheme though the attacker in this scenario has the same chance of success as they would have against the current industry best practice of storing a password hash in the DB (in a scenario where those hashes were extracted by the attacker and attacked offline).

So that's a quick and dirty description and security analysis of a novel password authentication and protection scheme for a website.  The benefits of this scheme are:

• The website never gets to see the local password chosen by the user.  But this is not an absolute, it assumes a trusted website (and trusted 3rd party resources the website requests).  This is a benefit because:
• Websites cannot accidentally expose the user's local password, either internally or externally.
• A malicious insider working for the website would have a much more difficult task in obtaining local passwords with an intent of using those passwords on other websites.
• A successful SQL Injection attack that dumped out the password hash DB table would not allow an attacker to compromise any accounts.
• If the encryption key K was stored and used in an HSM, then it would be impractical under any circumstances for an attacker to mount an offline attack (short of physical access to the user!)

But let's also be clear about the problems:

• You probably shouldn't be implementing any scheme you read about in a blog.  Such things need to be reviewed by experts and their acceptance needs to reach a level of consensus in the security community.  Anyone can create security system that they themselves cannot break.
• Lack of implementation details.  Even if the theory is sound there are several pitfalls to avoid in implementing something like this.  This means it's going to be difficult to implement securely unless you are very knowledgeable about such things.
• If you are using a salted password-hash scheme now and went through and encrypted those hashes (as another layer of security), you basically get the same level of security as this scheme proposes. The benefit of this scheme is that the user's password is not sent to the website.
• Password changing.  It may be more difficult to mandate or enforce user's change their local password because the change must be done on the client side.
• JavaScript crypto.  The Hash() algorithm would need to be implemented in JavaScript.  The first problem is implementing crypto algorithms in JavaScript in the browser raises several security concerns.  The second is the Hash algorithm is computationally expensive which means performance might negatively affect usability, perhaps more so when implemented in JavaScript, and perhaps even more so on certain devices e.g. mobile.
• Lastly, I didn't quite achieve my goal of allowing users to choose weaker passwords as in the worst case attack (attacker has access to the secret key), the use of weak passwords would make recovering those passwords relatively simple.

But hey, it's a novel (as far as I know) approach, and it might be useful to someone else designing a solution for website authentication.

Removing usernames and enforcing unique passwords

I often have "ideas" that, in the haystack of my mind, are usually straws rather than that elusive needle. One recent one was whether the username is necessary to login to a website.  Usually the Internet is excellent at helping identifying straws, and this idea is no exception, see http://blog.codinghorror.com/why-do-login-dialogs-have-a-user-field/.  But let's follow through on the idea and see where it takes us.

So the basic idea is that when a user wants to authenticate to a website, all they do is provide their password and the website will use that information to identify them.

The draw of removing usernames for me is really an efficiency one, as it's not immediately clear that usernames are required to authenticate to a website.

The obvious problem though is if someone tries to register with the same password as an existing user.  Since we can't have 2 users with the same password (more on unique passwords later), we must reject the registration and reveal that the chosen password is a valid credential for another user.  We can overcome this problem by forcing the existing user with that password to change their password (using (an assumed pre-existing) out-of-band password reset mechanism e.g. email).  Which highlights one benefit of authenticating with the password only, it creates an incentive for the user to choose a strong password (as otherwise they will continually have to change their password when new users attempt to register with the same password).

From the website's perspective there is a problem though, how do you identify the user?  If passwords are being stored using a salted password-hashing algorithm, then it would be too inefficient for the website to, for each row in the password hash DB table, fetch the salt for that row, then generate the password hash (using the password of the user trying to authenticate), and the compare it against the stored password hash in that row.  That approach simply does not scale.  We certainly don't want to use a password hash without a salt or with a fixed salt (as this makes dictionary attacks on the password hash DB table much quicker in the event the table is exposed).

One option is to encrypt the password and use that as the salt for the password hash.  To verify a login attempt the website would encrypt the password to create the salt, calculate the password hash (using the salt) and compare with the list of stored password hashes (potentially sorted for efficient searching).  It's important to point out this encrypted password, which we are using as the salt, is not stored, but calculated during the login attempt.

If the password hash store was ever compromised (and we always assume it will be) then it will be impossible to brute-force the passwords without the encryption key as well (as the salt will not be known and not be practical to guess).  Thus the security of this approach relies on protecting the encryption key.  The key should not be stored in the DB, as the likely extraction method of the password hash DB table is SQL Injection, meaning if the key was in the DB it too could be extracted.  The key should be stored somewhere the DB cannot access (the goal is to require the attacker to find a separate exploit to obtain the key).  It could be stored in configuration files, but the best option would be an HSM, with encryption done on-board.  At the stage an attacker has code executing talking to the HSM, it's game over anyway.  If the encryption key was obtained by an attacker then they could more efficiently (than attacking traditional salted passwords hashes) perform a dictionary attack on the password hash DB table.

We can make another optimisation for security as well.  We should keep track of the passwords that more than one user has chosen in the past i.e. password collisions discovered during user registration.  After all, we don't want to force a user to change their weak password, only for that password to become available for use again!  This way we will avoid the re-use of weak passwords e.g. 123456.  Now imagine we had a list of passwords that we know more than one person had thought of.  Now imagine we publicly shared that list (so other websites could avoid letting users choose those passwords as well).

So let's imagine we now have an application that doesn't require usernames for authentication and all users have unique passwords.  What are the threats?  Well a distributed dictionary attack against our application is a problem because every password guess is a possible match for every user.  Annoyingly the more users we have the better the chances of the guess being right.  Additionally, limiting the number of guesses is more difficult since authentication attempts are not user specific.  This makes clear the benefit of having usernames; they make online authentication attacks much harder.

So my conclusion was that although usernames might not be strictly necessary, they do offer significant security benefits.  From a user perspective as well there is minimal burden in using usernames as browsers (or other user agents) often remember the username for convenience.

But what about the benefits of unique passwords!  What about the incentive we gained when users were forced to choose strong passwords?  Well what if we keep usernames AND still forced passwords to be unique?  Could this be the best of both worlds?  Might I have just pricked my finger on a needle?

The 'sticking point' for me is the user acceptability of forcing unique passwords.  It may drive the uptake of password managers or strong passwords, or it might annoy the hell out of people.  Perhaps for higher security situations it could be justified.

Zero Knowledge Password schemes

So in my previous post I was lamenting that as it stands today, for the majority of the Internet, when I authenticate to a website I have to send them my password.  It's obvious that if that wasn't a requirement then this would be better.

This caused me to read up more on Zero-Knowledge Password authentication schemes, and I came across the Secure Remote Password (SRP) Protocol (very nicely summarised here).  However, in the security analysis (given on the linked page) of SRP there was the following property:

"If the host's password file is captured and the intruder learns the value of v, it should still not allow the intruder to impersonate the user without an expensive dictionary search."

To me, this is not good enough.  Or at least if I am giving my list of all criteria I would like my authentication protocol to meet, one of them would be that "even if the password file is captured an attacker cannot recover the password".  This sounds like an impossible dream, but I hope it is not. 

Initially I imagined a change to SRP that I thought might do the job.  If we had 2 generators for the group, g1 and g2 (so in the current scheme replace references to g with g1), and 2 passwords, P1 and P2, then we could construct v as:

1. x1 = H(s1, P1)
2. x2 = H(s2, P2)
3. v = g1^x1 . g2^x2

The rest of the protocol could be minimally altered to accommodate this.  Hopefully you can see that an attacker with access to v, s1 and s2, could in fact hit upon multiple P1 and P2 values that create the same v value.  So even if the attacker was able to create all possible P1 and P2 values, they would not be able to tell if they were the actual password values.

But the suggestion has a drawback.  Well it has a couple.  Firstly it requires the use of 2 independent passwords.  Secondly, if an attacker got the password files for 2 different sites using the same g1 and g2 (and using the same group) then they could solve for P1 and P2 (from a list of candidates after a brute-force attack).  Lastly, my analysis is optimistic in saying that multiple solutions exist because the range of possible passwords is so much smaller than the range of possible x values.

Still, it's fun to play with these ideas, and you never if you might hit on the right combination :)

Passwords - the worst kept secret

So I'm writing some training material and I'm making a note that we don't use HTTP Authentication on the Internet anymore, it has loads of disadvantages.  Well it is supposed to anyway, I really couldn't find much detail on exactly what those disadvantages were?  I mean sure if there is a MITM then if you use Basic Auth then the MITM will get your password, or if you use Digest Auth then a MITM can downgrade to Basic Auth, or perhaps mount a dictionary-attack on your password.

Still, since the vast majority of web sites use forms-based authentication, what is the real difference (assuming you are using SSL/TLS)?  You are still sending your password over the inter-tubes.  Maybe I am missing something, I don't know.

To me though both Basic and Digest Auth had one advantage, the browser asked for my password and not the web page.  Why is that important?  Well there are a lot of spoofing attacks out there that try to fool users into entering their passwords into fake pages.

Entering passwords into fake pages is clearly a problem but really it isn't the fundamental problem.  The fundamental problem is that I am entering my password into a web page and that my password is being sent to the server at all.  Authentication is based on something you know, have or are, and so passwords fall into something you know, which means they should be a secret.  It's much easier to keep a secret if you never have to enter it into a web page and send it across the Internet and have it processed and stored (in some form) by someone else.

The 'what you know' requirement is merely proving that you know something, and while telling someone what you know does prove it, there are other ways to prove you know something without giving it away (see zero-knowledge password proof).

This does of course assume that a user and a site have agreed on a password already, and although I couldn't dig up much on schemes that don't have this requirement, I don't see why it shouldn't be possible.  A user could register a f(password) (a function of their password) and then authenticate at any time by providing g(password) where the site can convert f to g.  Note, I say possible, not easy, I haven't really given this much thought.

If the browser could be relied upon to do this securely on behalf of the user then it would eliminate many authentication concerns plaguing the Internet today, such as; spoofing authentication pages, MITM authentication attacks, server-side password or password hash disclosure, user password re-use.

Seems like it is definitely worth some more investigation ...

The ghost of password future

I was reading about Pico and it raised an excellent point regarding the recommended length of passwords that got me thinking about the long term feasibility of passwords.  For as long as I have been in the security industry (just over a decade) an 8 character password (involving 3 character sets) has been considered, in rough terms, 'good enough'.  The reason that 8 characters is 'good enough' is if you do the math on how long it would take to brute force then the resulting time it would take is 'long enough'.

So what about Moore's Law?  Moore's Law says that we will double the number of computations every 18 months (the actual law is transistor count every 2 years), and these days the law relies on multiprocessor cores in order to be true (which is fine for this discussion since brute forcing passwords can be done in parallel). 

So according to Moore's Law, we need to increase the length of passwords by 1 bit every 18 months to keep constant the time it would take to brute force a password.  Unfortunately we use 8 bit bytes to represent characters in passwords (actually only 7 bits are used).  So this means every 10.5 years (7 bits x 1.5 years), call it a decade,  we need to add a another character to our passwords in order to protect them from brute-forcing. 

So in 2050 the recommended password length will be 13 characters.

A quick Google did not reveal a definitive answer to the length of password that people can typically remember, but I don't think it's a stretch to go with; shorter easier, longer harder.

So what does the future hold for passwords?  It looks pretty grim.  The length of passwords will need to go up, but our ability to remember long strings of characters is unlikely to change.  People will do what they always do and find a way to satisfy the password length requirement by creating a password that is easy to remember but which does not necessarily gain any security benefit from being longer.

[I have glossed over many of the technical details of brute-forcing, Moore's Law, processor power, character sets, etc. because I wanted to focus the point of the post on the fact that password lengths seemingly must get longer.]

Password changing needs to change

Companies tell people they need to change their passwords but I think companies are the ones who need to change. 

In many enterprises users must change their passwords every 3 months or so.  When was the last time a website asked you to change your password?  What about your banking website, how often do they tell you to change your password?  It's funny isn't it, there seems to be a real double standard about changing passwords.

So why do companies tell people to change their passwords?  Well the thinking is that if you change your password then if it has been exposed at some stage you have minimised the opportunity to brute force it, and if cracked then you minimise the opportunity to use it.  You can't really argue with the logic, those are sensible reasons to change you password.

What you can argue with is why is the burden on users to mitigate the risks of their password being exposed?  The answer is clearly that we don't have any other good mitigations to those risks other than users changing passwords.  Hold on ... we just established that websites don't make users change their passwords, so websites are either mitigating the risk or accepting it.  So who is right, the companies or the websites?

Well as much as I would like to argue the merits of the security of either approach, or have a detailed discussion of risk as a function of the assets the passwords are protecting, I think I would be missing the point.  Websites don't ask users to change passwords because it's a usability issue, it would put too much burden on the user and that might drive the user to a competitors website.  Companies have a captive audience, and they aren't trying to make users happy, they are trying to secure business assets.

For some people this might be a perfectly reasonable justification, and clearly it is not without merit, but all decisions have consequences.  One of the consequences, and this is pretty common knowledge, when users have to change passwords they often choose related passwords, marginally different from their old one, so it is easy for them to remember.  The irony of this it circumvents the mitigation of changing passwords, as changing the password doesn't require the attacker to start from scratch again.

So what's the solution?  Well clearly there isn't a well known one otherwise more companies would be using it.  I think there is a lot that companies can learn from the web experience though:

• Get users to use a local password manager, since their password never leaves their machine the risk of exposure is substantially minimised and the enterprise can still enforce a rule of changing passwords.  Moreover the quality to passwords used can be increased exponentially.  I'm not up to speed on password managers for the OS, but if they don't exist then someone out their should create the market for them.
• Use mechanisms to identify the fraudulent use of passwords.  I'm not sure how mature this market is for systems within an intranet, but web sites have mechanisms, so there is at least some framework for new solutions.
• Use Single Sign-On.  I'd be the first to admit that this can create more security issues if not implemented correctly, but done well it definitely helps minimise risk and is the ultimate in convenience for users.

 With most companies intranets resembling a mini-Internet of web applications it makes sense for companies to start incorporating some of the hard fought lessons web sites have learnt when it comes to the balance between usability and security.