Skip to main content

Alice strikes back against Bob's 'reverse dictionary'

This is part 3 of a series of blog posts about one way functions and their use in securing passwords. If you haven't read the first two parts start here.

Now Alice is angry. She realizes that Bob has defeated her clever one way function with his reverse dictionary and that now that Bob's created it he can use it over and again. All his initial effort will be amortized day after day as he steals crossword answers from Alice.

And so Alice strikes back.

The following day she calls Bob and says that she's making a small change to her one way function. It'll still involve looking up five words in the dictionary and following the definitions, but the order will change. In fact, she'll get to pick the order.

In the original scheme the first word of the first definition was used, the second word of the second and so on. Alice proposes to verify that she knows the answer to 4D (TANGLE) by giving Bob the final word (just as before) but also five numbers indicating which word to pick from each definition. In the original scheme the order was 1,2,3,4,5 (indicating the first word from the first definition, the second word from the second definition and so on).

But today she tells Bob that the answer is HUMAN and the order is 2,2,4,5,1. So Bob has to start from TANGLE (if he knows it!) follow the second word of the first definition, the second word of the second definition, the fourth word of the third, the fifth word of the fourth and take the first word of the fifth definition (which should be HUMAN).

This renders Bob's reverse dictionary useless. It's only good for the original order; 1,2,3,4,5. Now Alice is free to pick any five numbers from 1 to 5 before working out her one way function. Bob can still easily verify that Alice knows TANGLE, as long as she gives him the order, because he too can follow the definitions from TANGLE to HUMAN. But, of course, he has to have solved TANGLE by himself!

And five numbers in the range 1 to 5 gives Alice 5 * 5 * 5 * 5 * 5 = 3,125 possible orders in which to follow definitions. That would force Bob to create 3,125 reverse dictionaries for each of the possible combinations that Alice could use. He doesn't have the room in his house for that.

And Alice is free to pick a new sequence for every word Bob wants to verify. So Bob has to either work backwards through the one way function (which is really hard/almost impossible) or go through the entire dictionary trying to find which word Alice started with.

Because Alice can pick a different order each time she wants to disguise a word she can even make the same word turn into completely different words. With the order 2,2,4,5,1 TANGLE became HUMAN, but with 1,4,5,3,2 TANGLE becomes AUTOMATIC. So, Bob won't even be able to learn from past words.

In the real, mathematical world of one way functions and passwords the extra piece of information that Alice has chosen (the numbers) is called salt. It is typically chosen randomly and either added to the password to be stored or used as a parameter to the encryption used to store the password. It need not be numbers; in fact it's often just random characters.

The password database will contain both the salt and the result of the one way function applied to the salt and password combined. It's still possible to check a password when the user types it in (the web site computes the one way function of the salt and typed in password combination and compares it with what's stored in the database).

But if the password database is stolen an attacker is frustrated because each password will have a different salt and cracking passwords will be greatly slowed down. Pre-calculated 'reverse dictionaries' or rainbow tables will be useless and each password will have to be cracked individually (without salt if two or more people have the same password it only has to be cracked once). This means an attacker has to run through all possible passwords for each entry in the database as the salt is different for each one.

The salt value that goes along with each password is not a secret. All it needs to be is long and different for each password stored in the database. Just as Alice tells Bob the salt 'order', a well designed password system will not relying on the secrecy of the salt: the strength of the system relies on the strength of the one way function (i.e. how hard it is to calculate 'backwards').

Fortunately, or unfortunately, this isn't the end of the story. Even with salt it's possible to crack passwords.

PART 4: Bob's wife Carla lends a speedy mind

PS There's actually a way round the need to create 3,125 dictionaries which is entirely separate from what Carla's going to do! Either see if you can figure this out yourself or read this comment.

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


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