A technology called repeated hashing provides user authentication that can only be defeated by guessing the user’s secret or traveling back in time. Since the second is impossible, this is as good as user authentication security can get.
In Learning Tree’s System and Network Security Introduction course we explain hash functions.
They are easy to calculate but impossible to reverse. I can give you a piece of data and ask “Please calculate its hash.” You could easily do that with a fairly simple computer program. But if I gave you a hash function output and asked “Please tell me what I used as input to generate this”, it is impossible to do that and it is impractical to sequentially try enough possible inputs to find something that generates that output.
Let’s say that you have some randomly generated secret string. We could send our secret through a SHA-1 hash function to generate an output:
The output will look something like this:
Now, one of the attributes needed for a hash function to be practical is that it must be fast to calculate. So, we would send the output into a second hash function, and the output of that into a third hash function, like so:
In order to keep the discussion reasonable, instead of “the hash of the secret” I’ll write H(s), and instead of “the hash of the hash of the hash of the secret” as shown above, I’ll write H3(s).
Our user, Alice, has to log in to a remote server from time to time. She worries that someone might break into that server. And who knows, its administrators might go rogue. She doesn’t want anyone pretending to be her somewhere else. So she doesn’t want that server to know what her secret is.
She tells us she might have to log in to that server once or twice a day over the coming year. We have her generate a highly random password string using a tool like KeePassX, which we discussed last week. Then we have her calculate the result of sending her secret through a pipeline of 1000 hash functions in a row. That should go quickly.
Then on the server we record that there is a user named Alice, her number n is 1000, and her current hash value is that H1000(s) she just calculated.
Later that day, Alice needs to log in. She connects, saying “I am Alice”.
The server responds with n-1, or 999 this first time.
Alice calculates H999(s) and sends that back.
The server calculates the hash of what she sent. Alice sent her secret through first 999 hashes, the server does one more, and the result should be the currently stored value, H1000(s).
If it matches, it must have been Alice, so she is allowed in. The server updates her record. Her number is now 999, and her current hash value is what she just sent in that successful authentication, H999(s). The server still has no information about what her secret is, just some unreversable information about what happens when you send that sequence through a pipeline of 999 hash operations.
The next time, Alice will get a challenge of 998, and this continues. The server must always count down.
Meanwhile the would-be attacker watching this gains nothing but frustration. “Oh! If only I had known a few seconds ago what she just sent, I could have pretended to be her!”
We know that the attacker doesn’t have a time machine, so he can’t jump back in time to use what he just observed. Time machines don’t exist. If they did, it would make far more sense to use your visit to the past to buy stock or bet on sporting events. Re-using (pre-using?) one-time passwords would be a waste of time travel.
Of course, Alice’s secret must be impractical to discover. If Alice thinks it up, an attacker can probably discover it with a password-cracking attack that selectively tries strings humans are likely to use. She needs a highly random string generated and stored with a tool like KeePassX.
Repeated hashing is a form of strong authentication, in which you prove that you know a secret without exposing what that secret is.
It’s an especially useful form of strong authentication, because the server can accurately decide whether the user knows Alice’s secret or not, but the server doesn’t know what her secret actually is.
We can! But not this week as I’m out of space. Check back next week to see how to apply repeated hashing on multiple operating systems.