Wednesday, April 30, 2008

Can you hit a moving target?

Despite slanderous reports to the contrary, I remained sober at Infosec last week long enough to hear a number of skilled sales professionals peddling their wares. In amongst the vulnerability scanners that can find all known and unknown bugs, and the identity management solutions that will put hackers out of business, was an unbreakable authentication mechanism - "unbreakable" because it employs a device that changes the user's password every 60 seconds.

Can you guess a password that changes every 60 seconds?

Some would suppose that you cannot, or at least that you would be highly unlikely to do so. The intuition here is that each time a password is generated, you will only have a few chances to guess it before it changes. If you don't guess it in that time (which is very unlikely), you are back to square one. The situation, it seems, stands in stark contrast to that of a static password, where you can continue guessing indefinitely until you are successful.

This intuition, however, is mistaken, and employing a rapidly changing password in itself does not add much to the security of an authentication mechanism. To see why, let's compare two mechanisms that are equivalent in all other respects.

Suppose that a "changing password" mechanism employs a device that generates six-digit decimal numbers for passwords, which is fairly typical. To keep things simple, let's also suppose that an attacker only has time to make a single guess at each password before it changes.

In the equivalent "static password" mechanism, let's suppose that each user has a six-digit decimal number as a password, and that this never changes.

First, our attacker targets the static password mechanism. There are 1,000,000 possible passwords, so his first guess has a one in 1,000,000 chance of success - very unlikely. Assuming this guess is wrong, he has eliminated one possible password, so his next guess has a one in 999,999 chance of success. And so on. After 500,000 unsuccessful guesses, the attacker has eliminated half of the possible passwords, and so his next guess has a one in 500,000 chance of success - still very unlikely. But, significantly, at the outset of the exercise, the attacker may expect that, on average, he will have guessed the correct password by this point. If there are 1,000,000 possible passwords, and you try half of them, you have a 50% chance of success. Half the time, you will have guessed the password by this point - the other half, you will need to continue guessing.

Next, our attacker targets the changing password mechanism. Again, there are 1,000,000 possible passwords, so his first guess has a one in 1,000,000 chance of success. Assuming this guess is wrong, he tries again. But because the password is regenerated, he has not eliminated any outcomes for the second guess, so his next guess still has a one in 1,000,000 chance of success, and this remains the same no matter how many unsuccessful guesses he makes. He appears to have very little chance of guessing the password - hence the intuition.

However, as we saw in the case of the static password, after 500,000 unsuccessful guesses the attacker still has only a one in 500,000 chance of success in his next guess; nevertheless, at the outset of the exercise he may expect to have guessed the correct password by this point. So we may ask: what is the corresponding point at which the attacker targeting the changing password mechanism may expect to succeed?

Each time the attacker tries to guess a changing password, he has a 999,999 out of 1,000,000 chance of guessing incorrectly. So, the probability that he will fail to have guessed the password after one attempt is 0.999999. The probability that he will have failed after two attempts is 0.999999 * 0.999999. And so on. At the outset of the exercise, the probability that the attacker will have failed after N attempts is 0.999999 ^ N (where ^ means "to the power of").

So in a head-to-head challenge, what is the probability that the attacker targeting the changing password mechanism will have failed after 500,000 attempts? It is 0.999999 ^ 500,000, which is 0.606. That's right, there is nearly a 40% chance that the password will have been guessed by this point. With a bit of maths, we can work out that at the outset the attacker may expect that, on average, he will have guessed the correct password after 693,147 guesses - this is the point at which 0.999999 ^ N falls below 0.5.

Clearly, the changing password mechanism fared better, on average, than the static password mechanism - but by how much? In our scenario, the dynamic password takes on average 39% more attempts to guess than the static password - a relatively modest difference, of the same order of magnitude, and nothing like enough to justify the "unbreakable" intuition, or the likely expense of the password-generating device.

Now, in the real world there would of course be more factors in play than in my simplified scenario. Users may choose alphanumeric passwords with a larger range of possible values; but they may choose them non-randomly. They may write down their passwords; equally, they may leave their device lying around. Either mechanism may implement defences to frustrate brute force attacks. I don't want to suggest that password-generating devices are pointless - in many situations they can play a beneficial role in conjunction with other controls like conventional passwords, biometrics and account lockout. But if you hear the claim "It changes so it can't be broken", think "snake oil" and head for the bar.


The Mighty Gnit! said...

Being in the casino industry, I have to say that I think you are incorrect in this statement.
Roulette wheels are the equivalent of the constantly-changing password. Each spin, they have a 1/37 (depending upon the wheel, double-zero etc.) of hitting any number.
Blackjack (shoe game without a continuous shuffling machine) is a much easier beast. Because you know which cards have been discarded (i.e. which passwords have failed) you can predict the makeup of the remaining cards (passwords) so that you don't have to try any which you know will fail (bit wobbly on the analogy here, forgive me - I'm rushing to get ready for work).
In the continuously-changing password world (roulette), you have the same probability each attempt (1/37) to get it right, whereas in the fixed password world, the odds of success increase with each failed password.
After all, you don't try the same password twice if you know the password hasn't changed.
Try the analogy with a deck of cards:

Fixed password example

Try to guess a card, e.g. 4 of hearts.
Turn over the top card. If it isn't the 4 of hearts, discard it and check the next card. Repeat until you have ran through the deck & found the 4 of hearts (odds 1/52 + 1/51 + 1/50 + ...)

Continuously changing password example

Try to guess a card, e.g. 4 of hearts.
Turn over the top card. Is it a 4 of hearts? No. Shuffle the deck & try again. Is it the 4 of hearts? No. Keep trying until you get the 4 of hearts. I can guarantee that it will (on average) a significantly longer period of time to get the 4 of hearts this way (each guess has a 1/52 chance of success).

Sorry if it's a bit garbled, I'm in a heck of a rush to get ready for work...

PortSwigger said...

@The Mighty Gnit

I didn't deny that the odds of guessing a changing password are the same on each attempt - in fact, I asserted it.

The point is that the fact of the password's changing doesn't make it very much harder to guess, compared with a static password.

To pursue your analogy, if a roulette wheel has 37 possible outcomes, and I only get one guess per outcome, then on average I will get a hit after 26 attempts (I won't repeat the maths). This is a little more than the average 19 attempts that it would take if the outcome didn't change, as I observed. But not "significantly more" as you contend, and certainly not unbreakable.

The Mighty Gnit! said...


I suspect an error in your math or reasoning.
To continue the Roulette analogy:

If you were successfully predicting a single number on a roulette wheel with greater than 1 in 37 chance (on average), then I would say with certainty that either:
a: you are cheating, or
b: the rng/wheel has a bias.
The whole point of a 1/37 chance of success on any particular prediction means exactly that: You will successfully predict (on average) one number every 37 spins.
The payout (in Europe, anyway) for a winning number is 35 pieces + your original stake (for a total of 36 chips). If you can get such a payout on average every 26 spins then you will quickly become a very rich man indeed.

For anybody else reading this, a nice introduction to probability math, especially related to casinos can be found here.

Note, I am not affiliated in any way with that site, but did like the clean way it explained the odds

PortSwigger said...

@The Mighty Gnit

You are confusing two different things. I am not saying that you can expect to win at roulette "every 26 spins", nor am I aware of a way to beat the house.

To repeat, if there are 37 possibilities and the outcome is fixed, then I will probably have guessed it after 19 attempts. This is the point at which the probability of my not having guessed it falls below 0.5. Half the time, I will guess with less than 19 attempts; the other half it will take me longer.

If the outcome changes on each guess, then I will probably have guessed it after 26 attempts. This is the point at which the probability of my not having guessed it falls below 0.5. Half the time, I will guess with less than 26 attempts; the other half it will take me longer.

This like-for-like comparison shows that guessing a changing outcome is not too much harder than guessing a fixed outcome.

Of course, the maths don't present any way to beat the house in a casino. Paying 26 chips for a 50% chance of a 36 chip payout is not a promising strategy!

The Mighty Gnit! said...


The whole point of a 37-to-1 shot is that you probably will guess/predict correctly on average once every 37 spins. This is immutable.

Each prediction is independent of the previous one.

There is no way around this.

The odds don't stack.
You will not guess the correct combination or number on average once every 26 spins. If you were guaranteed that that particular number would not come up again, then you could use such logic to state that you will have hit the correct prediction after n/2 trials on average (where n is the total guesses). On a continuously-variable system, you can only say that you will predict, on average correctly once every n times.

I have seen tens of thousands of people come to the casino with the 'I can guess on average the correct number once every 26 spins' mentality. I have also seen every one of them leave unfulfilled.

You are contradicting yourself when you say that you are not trying to beat those odds, yet you state that you expect to correctly predict the correct number in a shorter time, on average than the odds give you.

I wrote a small program in python to test your theory, out of 1,000,000 random trials, it correctly guessed a 1-in-37 shot number 27,108 times, which is 2.7108% success. The actual odds of correctly guessing 1-in-37 is 2.7027%.
The code is here, feel free to examine it & play :)

PortSwigger said...

@The Mighty Gnit

You are still asking the wrong question. To repeat, I am not claiming that someone can guess "every 26 spins", but rather that this is the point at which the probability of your not having guessed falls below 0.5.

To prove this point in code (rather than your different one), use the following (in C#). It shows that half the time we can guess a 1-in-37 random number correctly after 26 or fewer guesses. Try it - it appears that you will be surprised.

int twentySixOrLess = 0;
int moreThanTwentySix = 0;
Random r = new Random();

for (int i = 0; i < 1000000; i++)
int count = 0;
while (r.Next(37) != r.Next(37))

if (count <= 26)
else moreThanTwentySix++;

System.Console.WriteLine("twentySixOrLess: " + twentySixOrLess);
System.Console.WriteLine("moreThanTwentySix: " + moreThanTwentySix);

Allan said...

I've been on a number of sites with the 60-second keyfob solution from RSA. I believe that in all cases, the six-digit number was not intended for use as a password. The freshest instance in my memory was a site where first you used the number appended to your phone extension to access the corporate VPN, after which you provided your password to get to your Citrix desktop. In a couple of other instances several years ago, I believe it was used after having authenticated to corporate systems, to access specific network resources, though I cannot recall the details, as I was observing the network guys while waiting for them to fulfill my request.

PortSwigger said...


Sure, changing passwords can be (and perhaps typically are) combined with other controls like static passwords. But what interested me was the intuition that a password which changes is much harder to guess than one which does not. That intuition is traded on by salesmen, and people evidently find it compelling. The problem is that it is mistaken.