Thursday, December 6, 2007

Salting your Hash with URLs

So, when I was reading this post on Light Blue Torchpaper (Cambridge University' Computer Security Lab's blog) a few weeks back, I, like many others (including this Slashdot thread), was reminded about the importance of salting your password hashes ... As it turns out, you really can ask Google for a hash value and it really will return significant results-- like a gigantic, easy-to-use Rainbow Table. Steven Murdoch managed to find "Anthony" with this simple search.

Of course, though, if my story stopped there it would not be that interesting. Security professionals have known about salting hashes to get around known hash values in tables for a long time. But as I thought about the salt hashing, it dawned on me the parallels with some password management tools.

I had been wanting to reduce the number of passwords I have to keep track of for all of the various web applications and forums that require me to have them. I have used Schneier's Password Safe for years now and find it nice, but not portable to other platforms (e.g. mac/linux). Even moving between different PCs is difficult because it requires keeping my password safe database in synchrony. Of course, several browsers have the ability to store passwords with a "master password", but I have several objections to them. First, they are part of the browser's stack, so I have to trust that my browser and the web applications I use won't result in an opportunity for malware to exploit a client-side bug to steal my passwords. Second, they don't tend to work well when moving from machine to machine, so there's a synchrony problem. So, I am always on the lookout for a good alternative. Perhaps one day an authentication system like Info Cards will become a reality in the consumer-space ...

So, when I first stumbled upon Password Maker, an open source password management tool, I wanted to like it. How does it work? From their description:
You provide PASSWORDMAKER two pieces of information: a "master password" -- that one, single password you like -- and the URL of the website requiring a password. Through the magic of one-way hash algorithms, PASSWORDMAKER calculates a message digest, also known as a digital fingerprint, which can be used as your password for the website. Although one-way hash algorithms have a number of interesting characteristics, the one capitalized by PASSWORDMAKER is that the resulting fingerprint (password) does "not reveal anything about the input that was used to generate it." 1 In other words, if someone has one or more of your generated passwords, it is computationally infeasible for him to derive your master password or to calculate your other passwords. Computationally infeasible means even computers like this won't help!
But, as I said: "I wanted to like it." After all, there is nothing that has to be stored ever-- you just have to remember the main password and the algorithm does the rest. There is nothing that has to be installed directly into the browser (unless you want to), not too mention it's very portable from platform to platform. And since there is no password database or safe to move around, there's no synchronization problem-- the site specific passwords are re-created on the fly. It sounds like a panacea. In the algorithm, the URL essentially becomes a salt with the master password as the hash input. The resulting hash [sha1 (master password + URL)] is the new site-specific password. It sounded like a great solution, but I have a couple potentially show-stopping concerns over it.
  1. There are varying opinions, but it is a prudent idea to keep salt values secret. If the salt value becomes known, a rainbow table could be constructed that employs the random password key-space concatenated with the salt. Granted, it might take somebody several days to create the rainbow tables, but it could be done-- especially if there were economic incentives to do so. Imagine that an adversary targets the intersection of MySpace and Paypal users, also assuming (of course) that this Password Maker is at least somewhat popular. Sprinkle in some phishing, XSS, or whatever is needed today to capture some MySpace passwords (which are of considerably lower value than, say, PayPal) to compare against the rainbow tables, and ... Voila ... the adversary now has the master password to input into the Password Maker's scheme to get to access to PayPal.
  2. I am not a mathematical/theoretical cryptographer, but I know better than to take the mathematics in cryptographic hash functions for granted. There has not been much research in hashing hash values, at least not much that has entered the mainstream. And as such, it may be possible to create mathematical shortcuts or trapdoors when hashing the hash values, at least potentially with certain types of input. That is not to be taken lightly. I would not build any critical security system on top of such a mechanism until there was extensive peer review literature proclaiming it a safe practice (also read the section entitled "Amateur Cryptographer" of this Computer World article).
In summary, the Password Maker is an intriguing idea, perhaps even novel, but I wouldn't use it for passwords that get you access to anything of high value. For mundane sites (ones where a compromised password is not a huge deal), it's probably a decent way to manage passwords, keeping separate passwords for each site.


Vince said...

Have you tried KeePass?

It runs very well on Windows. For Linux/Mac you can run KeePassX which is not as nice

For synchronization, I rely on Subversion over SSH until there is a Windows port of Git.

securology said...

Thanks, Vince. I'll check keepass and keepassx out. I've heard of it before and avoided it, if for no other reason than I don't take crypto-rich applications lightly. PasswordSafe passes the WWBSD (What Would Bruce Schneier Do) test. I don't know if keepass can do the same.

Peter said...

I just found Passwordmaker and also your post. The current versions have the ability to add a secret salt to the algorithm, so the salt is not simply the hostname of the website you are accessing.

I believe this defeats the vulnerability you mention.

securology said...

Thanks, Peter, for bringing this to my attention. It's good to know they are fixing these issues.