Monday, September 29, 2014

It's all in your head: Adventures in Generating Site Specific Passwords

The Blums Mental Hash (BMH) algorithm, a programming exercise I worked on this last weekend, won't let me go. Quick review, the BMH is supposed to be a mental exercise you can go through to generate a unique password for any website. The algorithm and its intentions are explained here:

Good passwords are hard to remember. A pattern that makes a password memorable is likely to make it vulnerable to attack. If remembering one secure password is hard, remembering many such passwords is entirely impractical. So people who have gone to the effort of creating one good password use it for many different accounts. A security breach anywhere that password is used means that the password is vulnerable everywhere else it is used.

It is much safer to have different passwords for every account. Then if one password is compromised, the damage is limited to a single account. One way to accomplish this would be to have software compute a password for each account by encrypting the name of the account. For example, your password for Home Depot could be the result of encrypting the text "homedepot." This way accounts with different names would automatically have different passwords. (In practice, it might be possible but highly unlikely for two account names to result in the same password.)
Is it possible to create encryption algorithms that a human can execute but that a computer cannot break? It doesn't seem at first that this should be possible, but Turing Award winner Manuel Blum believes it may be. He presented his proposed algorithm at the Heidelberg Laureate Forum. He emphasized that his method takes a lot of up-front effort to learn but then it can be carried out quickly. To prove this claim, he demonstrated that at least one person has in fact used the method, namely himself! He said he can usually come up with a password in under 20 seconds.

There are a couple of questions that keep floating around in my head?

The problem of generating passwords on a per-site-basis is monumentally difficult. Yet, Blum's algorithm is pretty simple. It's still beyond what most (anyone?) would go through to generate a password, but it shows huge promise. It makes me wonder if the problem of generating passwords doesn't have some solution analogous to what the CAPTCHA provided against SPAM bots. In that case, most SPAM bots were stopped in their tracks all by using a technique that a PHP programmer could whip up in a couple hour's worth of work. (Hint: learn GD).

Another thought: the BMH works by walking through each letter in the domain name, and generating a unique password entry for it. At the core is a key which says how digits should be mapped to numbers, and from there, how they should be shuffled. I wonder if a physical device--think stack of cards, or string of beads--could be used to assist. Imagine if your key was a set of colored beads on a lanyard, and you used them to translate a domain name to a password. Crazy, but it almost seems possible.

And another: I always think of cryptography as requiring mind bending math skills. But the BMH shows that this doesn't need to be the case. You should study this algorithm, if only to appreciate that security doesn't need to come at the cost of complexity.

Finally, I was wondering if there's a way to put the BMH code I've written to use. While I couldn't think of a way to leverage the Scheme version of the code, it occurred to me that if I had a JavaScript version I may be able to write a bookmarklet that uses the code. So that's what I did. Here's a JavaScript version of the BMH algorithm and here's a Bookmarklet:

(Huge thanks to Peter Coles for the Bookmarklet generator -- man that's awesome!)

With the Bookmarklet in place, I can click my toolbar and be provided with a password that corresponds to the domain name in use. (Ssssh, don't tell anyone: my "password" for is @TuZeMe@NiWaZe--Ni3).

There are a number of issues with the Bookmarklet, but the obvious (and fatal) one is that the keys are stored in the source code. That means that if you drag the Bookmarklet to your browser, you'll get the same passwords I do. Which is not what you intended. The solution would be to store the key parameters in the bookmarklet itself. But that would be messier than I need for this trivial example. Perhaps if I'm still infatuated with this algorithm next week, I'll add support for this.


  1. Thanks again for mentioning my blog.

    There are some problems with your suggestion. First, each web site has rules about what passwords are acceptable (mix of upper and lower case, digits, punctuation, length), so a one-size-fits-all approach probably won't work. Second, sometimes you have to change passwords (expiration rules, passwords get hacked and everybody has to change). Third, as you mention, where do you store the keys, and how do you keep them synced between different machines (your phone, your laptop).

    Although I am intrigued by Blum's algorithm, as you are, the problem is that it's an algorithm, not a solution. Bruce Schneier has the best answer. You have spent your life developing a procedure to keep small bits of paper secure -- money in your wallet (and debit/credit cards, nowadays). So the default password storage method is to write down your password and put it in your wallet. Anything else you propose has to be better than that to be considered.

    If that's not good enough for you, look at, which is an alternative somewhere between Blum and Schneier.

  2. > There are some problems with your suggestion ...

    All fair points.

    > Although I am intrigued by Blum's algorithm, as you are, the problem is that it's an algorithm, not a solution. ...

    Yeah, it's entertaining and a novel approach.

    > So the default password storage method is to write down your password and put it in your wallet. Anything else you propose has to be better than that to be considered.

    I'm not sure I completely buy Bruce's logic (credit cards are kept in wallets, but are far from secure), but I do think he's probably right: no matter where you store the information, it's vulnerable (and if you don't store it, it can be forgotten). A paper notepad is reliable, and safer than cloud storage, a thumb drive or carrying the data on a mobile phone. (But of course, you can lose the notebook...)

    Still, it's an interesting problem and one that's fun to mull over.

    Thanks for the info!