Skip to main content

Bob's wife Carla lends a speedy mind

This is part 4 of a series of blog posts about one-way functions and their use in securing passwords. If you have not read the other parts start here.

Bob doesn't usually let his wife Carla help him with crosswords. That's because, due to some unusual quirk of brain topology, Carla is a savant and she's memorized the entire Shorter Oxford English Dictionary. So, she's able to recall the definition of any word almost instantly. But, like many people with similar abilities, her talent is limited, she can't perform the opposite: given a definition she's just as slow as her husband at finding the corresponding word.

Carla's ability means that she can calculate Alice's one-way function from crossword solution through five definitions very quickly. She's about 100 times faster than Bob because she has no need to find words in the physical book. But she's no faster at performing the reverse.

Alice calls and Bob challenges her for the solution to 25A. Alice knows that it's WITTINESS but Bob does not. As before Alice picks some salt, she chooses 4,3,4,5,1 and works out the word given by her one-way function (it's SINGLE, WITTINESS -> QUICK -> DOING -> PARTICULAR -> INDIVIDUAL -> SINGLE). Alice thinks her salt value means that Bob will have a hard time figuring out that the answer to 25A is WITTINESS.

But she's forgotten about Carla. Carla sits quietly and runs through the entire dictionary in her head. Starting from each word she performs Alice's one-way function using the salt 4,3,4,5,1 until (sometime after lunch) getting the answer WITTINESS. She hasn't worked backwards, she's simply worked through every word in the dictionary performing Alice's one-way function (with salt) on each word in turn.

Aside: this is the current state of the art in password cracking. Carla is replaced by a computer (or more than one computer) capable of calculating the one-way function of a long list of passwords (usually starting with the poor passwords, like 123456, that people commonly pick and then making up passwords from mixtures of letters, numbers and symbols). Even with salt it's possible to crack passwords because computers are fast, and many real, mathematical one-way functions can be computed very quickly.

In fact, many real, mathematical one-way functions were designed to be quick to compute (in one direction) and impossible to reverse. This speed of computation makes them a poor choice for password protection because a fast computer can run through millions of password and salt combinations to crack passwords. They were not actually designed for the task of protecting passwords: they are used because their one-way nature means that password databases never store actual passwords.

While Alice is on the phone she overhears Carla whispering in the background. It doesn't take her long to realize that Bob has asked for Carla's assistance and that, because her one-way function is quite quick to work out, Carla will be able to run through the dictionary and determine crossword clues from the supposedly secure words Alice gives to Bob.

Luckily, Alice has a simple solution to this. She just needs to extend the time it takes Carla to work through each individual word in the dictionary. She does that by adding a wrinkle to her one-way function: she tells Bob that the one-way function must be performed multiple times. Given that Carla took half a day to crack a single word, she tells Bob that for any word she gives (with its corresponding salt) he must perform her one-way function 10 times.

So, for WITTINESS she would give Bob the salt 4,3,4,5,1 and the end word (which is now CHEMICAL). Bob must first follow WITTINESS to SINGLE, and then start again with the same salt and work forward from SINGLE to INCLUDING, and then start again with the same salt and work forward from INCLUDING to HAVING, and so on ten times ending up at CHEMICAL.

This forces Carla to do ten times as much work; so it will take her days to crack a single word. But it only slows Bob down a little. If he actually knows the answer is WITTINESS and just wants to verify that Alice has solved the same clue, he just has to perform Alice's one-way function 10 times starting from WITTINESS (Carla's forced to do the same thing for the entire dictionary).

And that is the current state of the art in password protection. A password is entered by a user, some random salt is chosen and then a one-way function of the password and salt combination is computed many times (often 10,000 or 100,000 times since computers are fast). Or a specially designed one-way function with a 'cost': a number that tells it how hard to work in computing its result (the cost can be increased as computers get faster) is used.

This causes a small delay when you enter your password at a web site or on your smartphone since a one-way function must be computed over and over again. But that small delay adds up to a huge delay for anyone who wants to crack passwords because for every password they try they incur the small delay of repeated calculations.

And that's where this series ends. I hope it's been enjoyable and informative.

PS From time to time you hear of companies that have had their password database stolen. You might be very surprised to learn that many do not use the state of the art in password storage. Be on the look out when a password database is reported to stolen to see if the press reports that the passwords were 'salted' and 'hashed' (the term typically used for the one-way function). And even when they are salted and hashed it's worth asking (or wondering) whether they used a scheme that could beat Carla's computer equivalent by hashing multiple times. (A comment on Hacker News points out that I should really be educating people to ask if a key derivation function was used, instead of salting and hashing, since those have been designed for this purpose).

PPS Don't pick a poor password (such as secret, 123456 or iloveyou). The first thing a competent password cracker will try is a list of common passwords. Even with the best salted and repeatedly hashed password systems a password like 123456 is going to get broken.

This entire series of blog posts is available for purchase as an illustrated PDF or eBook for $1.99.

Comments

Olog-hai said…
"While Alice was on the phone she overheard Carla whispering in the background. It doesn't take her long to realize that Bob has asked for Carla's assistance [...]"

Why do you keep switching between past and present tense? It makes your writing difficult to comprehend.
@Olog-hai: thanks for pointing that out. I've edited that paragraph.
Ollie said…
Hi John,

I bought the Geek Atlas a while ago, I've slowly been ticking things off the list. I did Bletchley the other week, brilliant place!

I looked for a group on Google+ to share progress and images with but noticed there's nothing of the sort. I went and created a community (https://plus.google.com/communities/112607500383814371727)
But thought I'd better try check with you first before doing anything with it or hand it over to you if you'd rather have control of it?

kind regards
@Oliver: Go for it!
Mo said…
This series was excellent, thank you.
John Bandela said…
Great series, thanks for publishing
zeitcorps said…
Clever stuff. Still a wee bit confused.

So the database doesn't contain passwords, instead it contains a string for each password that can be reached by following a one way function?

But if the one way function is salted then this would lead to a different string for each salt? (which in your example is about 3000 strings)

Does this mean that a password database would contain 3000 different strings for each password each referring to a different salt?
Matthew said…
Great series. I have a question: how do banks do it, where they ask for a different set of characters from your password each time you log in. Do they have to store the password itself?

Thanks!

Popular posts from this blog

Your last name contains invalid characters

My last name is "Graham-Cumming". But here's a typical form response when I enter it: Does the web site have any idea how rude it is to claim that my last name contains invalid characters? Clearly not. What they actually meant is: our web site will not accept that hyphen in your last name. But do they say that? No, of course not. They decide to shove in my face the claim that there's something wrong with my name. There's nothing wrong with my name, just as there's nothing wrong with someone whose first name is Jean-Marie, or someone whose last name is O'Reilly. What is wrong is that way this is being handled. If the system can't cope with non-letters and spaces it needs to say that. How about the following error message: Our system is unable to process last names that contain non-letters, please replace them with spaces. Don't blame me for having a last name that your system doesn't like, whose fault is that? Saying "Your

How to write a successful blog post

First, a quick clarification of 'successful'. In this instance, I mean a blog post that receives a large number of page views. For my, little blog the most successful post ever got almost 57,000 page views. Not a lot by some other standards, but I was pretty happy about it. Looking at the top 10 blog posts (by page views) on my site, I've tried to distill some wisdom about what made them successful. Your blog posting mileage may vary. 1. Avoid using the passive voice The Microsoft Word grammar checker has probably been telling you this for years, but the passive voice excludes the people involved in your blog post. And that includes you, the author, and the reader. By using personal pronouns like I, you and we, you will include the reader in your blog post. When I first started this blog I avoid using "I" because I thought I was being narcissistic. But we all like to read about other people, people help anchor a story in reality. Without people your bl

The Elevator Button Problem

User interface design is hard. It's hard because people perceive apparently simple things very differently. For example, take a look at this interface to an elevator: From flickr Now imagine the following situation. You are on the third floor of this building and you wish to go to the tenth. The elevator is on the fifth floor and there's an indicator that tells you where it is. Which button do you press? Most people probably say: "press up" since they want to go up. Not long ago I watched someone do the opposite and questioned them about their behavior. They said: "well the elevator is on the fifth floor and I am on the third, so I want it to come down to me". Much can be learnt about the design of user interfaces by considering this, apparently, simple interface. If you think about the elevator button problem you'll find that something so simple has hidden depths. How do people learn about elevator calling? What's the right amount of