Harry Potter and the Magic Code.
This is a picture of the special-edition Blizzard Authenticator, which was in the goodie bags given out at this year's BlizzCon. It is an ingenious device that prevents hacking by generating a 6-digit one-time password (OTP) that you must enter into a dialog in order to log in to your account. It protects you from Trojans and keyloggers in that, even if a hacker obtains your account name and password, they will not be able to log in without the one-time code, and since you need the Authenticator to generate a new one at each log in, they will be unable to compromise your account.
In theory, it's awesome, but there are just a few nagging things about how it works, which are driving me nuts.
Let's take a look at how it works. You press a the button on the Authenticator, and it generates a pseudo-random number. Well, pseudo-random to you; perfectly predictable to it. You enter this into a dialog when starting the game, and the server checks it and if it's valid, allows you to log in. This all happens with no communication between the Authenticator and the server. Well, minimal communication I should say. There is a one-time communication that happens when you configure your WoW account to use the Authenticator: you enter the serial number on the back of the Authenticator into your account management page and I will assume this gives the WoW authentication server all the information it needs to know about your Authenticator and the set of pseudo-random numbers it will generate.
This Wikipedia article gives a basic explanation of the underlying technology. For an inital seed,
s, the Authenticator will generate a random number,
f(s), which is your one-time password. The Blizzard authentication servers know the inverse function,
f-1(s), and given
f(s) can calculate
f-1(f(s)) =
s. It then compares the
s that you gave it to the
s it expects (from the serial number). If they match, you are allowed to log in.
Also from that article, I expect the Authenticator works in one of two ways: it is either a time-synchronized or non time-synchronized. Let's take a look at how each of these would work (and the problems I foresee with each).
Time Synchronized.
In this case, the seed, s, is the current time. When you press the button, the Authenticator calculates f(s), which you enter into the dialog. The server, which knows the function f-1(s) from the serial number you gave it when you initially added the authenticator on to your account, calculates s, then compares it to the current time. If it's close enough—say within a minute—then you are allowed to log in.
My question with this method is then what exactly do you use for the seed? I mean, more specifically than "the current time". Most computer pseudo-random number generators use the number of milliseconds ellapsed since midnight as the inital seed. This is very obviously inadequate here: the same time will produce the same OTP two days in a row. For instance, if a OTP worked at five o'clock yesterday, it will work at five o'clock today. All a hacker with a keylogger needs to do is log in at the same time of day you did.
An obvious solution would be to use a more robust time, for instance the number of seconds ellapsed since January 1st, 2001. This way, the seed,
s, will never be repeated. The problem we run into here is sample size. The OTP is a six-digit number, giving a sample size of one million possible passwords. Assuming the
cryptographic hash function is perfectly efficient, and will use all possible values before repeating itself, this means that it will be a maximum time of a little over 11.5 days (one million seconds) before a OTP is guaranteed to repeat. That means that all a hacker who has obtained your login, password, and an OTP through a keylogger has to do is set up a script to try logging in once per minute (the previously-assumed time for which the OTP is good), and guaranteed, he'll have hacked your account within 12 days. Actually, if every member of the sample set is used, the hacker doesn't even
need an OTP. He can choose just any old six-digit number, and it's guaranteed it will come up within 12 days. Obviously, limiting the sample size, say only using half the possibilities, prevents this, but also cuts down the time elapsed before values are repeated, and thus the time required to hack, from 12 to 6 days.
This may be a little more effort than most Chinese gold farmers are willing to put into it, but since this type of authentication is used in many other industries, particularly government, it seems a little weak (the Resident Murloc reported using these at Raytheon). All I have to do to steal the schematics of the B-2 Stealth Bomber are set up a script to log in every minute, and I'll have hacked the system in two weeks? Sign me up!
One obvious way of alleviating this is to change the seed to something that takes longer to use up the sample space. For instance, if we use the number of minutes, hours, or days, elapsed since our arbitrary start date, it will take 1.9, 114, and 2740
years, respectively, to use up the sample space. Obviously, this is much more secure, but the problem comes in the time for which a given OTP is good. If we only have one OTP for a given day, any information a hacker steals will still be good for the rest of that day. A good trade-off might be to have a minute-based seed, since we've previously stated that OTPs are good for a minute after they are generated. But again, this might be good enough to thwart gold farmers, who take on average a couple days between when they obtain your information and hax0rs your account, but the Chinese agents with a key logger on
Ronald D. Sugar's computer will surely be a little faster than that.
Of course, there's a work around for that as well, and that's to have them as, literally, one-time passwords, i.e., once you've used it to log on, it can't be used again that minute. So even if Kim Jong-il is just waiting for his keylogger to get the secret nuclear OTP, it won't be usable again, because it was just used to log in. The problem I see here is what if you try to log in twice in one minute? For government computers, I could understand it saying "sorry, nope. Try again in a minute," but since WoW has no such restrictions, I must assume that it isn't doing this.
You could set up the Authenticator to generate a different OTP, even when using the same minute as a seed. This would also require that the Authenticator track the number of times the button was pressed in a minute, and this value be included in the seed (if the Blizzard Authenticator uses a time-synchronized method, it must be doing this, because pushing the button twice in a row generates different OTPs). So now the seed is the number of minutes elapsed since
2:14am EDT, August 29th, 1997, plus the number of log in attempts made. But this creates a new set of problems in client-server synchronization. Since the server doesn't know how many times you've pressed the button on your authenticator before your first log in attempt, it must allow any value for the number of log in attempts (verified: if you generate two OTPs with the Blizzard Authenticator, and only enter the second, it will allow it). This means if you press the button a million times in a minute,
all possible OTPs will be generated and since the system will accept any of them, it is worthless. Obviously, it's practically impossible to press it a million times, so we can put an upper limit on the number of times one could
reasonably be expected to be able to press it in a minute. Say we put that limit at sixty (once per second). This could work, but now we're limiting our sample size further. Since now for any given minute, there are sixty valid OTPs, our difficulty for cracking has essentially gone from one in a million to sixty in a million, or one in 16,667. Not only
that but we've reduced the amount of time it takes before we begin repeating values by a factor of 60. So the time it takes before we use up our sample space is down from 1.9 years to 11.5 days, the same time that it takes to repeat when using seconds as the seed.
Even with all these problems, there are still a couple issues I foresee with a time-synchronized OTP. Firstly, the Authenticator would have to have a super accurate clock. I'm talking about GPS sattelite-like precision. At the time of manufacture, it would have to be synchronized exactly with the authentication server, and the time could not vary by more than a certain amount (that amount depends on the life expectancy of the Authenticator). If you expect a ten year life span, it could not vary by more than 1 minute in ten years, or 0.0164 seconds per day. By contrast, my digital watch varies by as much as 1 second a day, so it would be more than a minute off in less than two months.
The second problem is that since, no matter what we choose as our seed unit, f(s) is a periodic function, i.e., the values repeat. This means it is not a one-to-one function and its inverse, f-1(s), technically, does not exist or at least is a multi-valued function, which would give an infinite number of output values for any one input value. Despite that, this is not as big a problem as it would seem, as you could just define f-1(s) as the first period of f(s). Then when the authentication server deciphers the time s, it simply needs to check if the current time is divisible by s.
But based on all this, I'm reasonably certain the Blizzard Authenticators are not time-synchronized. Which leaves the other possibility of...
Sequential (non time-synchronized).
In this case, when you configure your Authenticator on the account management page, and enter your Authenticator's serial number, the authentication server learns two things: the cryptographic hash function* and the initial seed used. The first time you press the button on your Authenticator, it generates f(s). That value is then used as the seed for the second time you press it, which generates f(f(s)) which is in turn used as the seed for the third time. In general, the n-th press generates the value fn(s). All the authentication server has to do is work backwords, using f-1(s) to compare the value you entered with the previous value you entered. In this case, the limiting factor on repitition is the number of log-ins, not time. If you log in on average once per day, it will take you 2740 years before you start repeating values, again assuming you use the entire sample space.
The problem here comes, again, with client-server synchronization. What if the user presses the button on the Authenticator twice, but doesn't enter the first one? Obviously, the authentication server must accept a certain number of values past the previous seed. For instance, if it applies f-1(s) to find s, but that doesn't match the seed of your last login, but f-1(f-1(s)) does, obviously it knows that you skipped one.
The issue here is the trade-off of hassle vs. security: how many OTPs in the sequence can the user skip? If this value is low, you risk having the user being completely unable to log into his account (either in game or the accounts manager) if he skips too many values (for instance his cat or kid got a hold of the thing and pressed it a bunch). Too high, and you lower your sample size and make it less secure. For instance, if you allow the user to skip 100 values, you essentially have moved from one in a million values being acceptable to one in 10,000. For a dedicated hacker, that is well within the realm of a brute-force attack. Ten thousand logins for an automated script is trivial. Granted, Blizzard might notice that something that looks like a DoS attack is being made on their authentication servers, but how are they going to stop it without locking out the legitimate user from his account? And while a gold farmer might not go through all this hassle, this is hardly secure enough for a government server.
When I first pressed the button on it, I was somewhat surprised that it was only six digits long. How is that a secure sample space, that provides enough room for skipped OTPs? I would think that any government-used authenticator would have to use at least nine, preferably twelve, maybe even sixteen digits. While I'm fairly convinced it uses the sequential method, I'm not convinced of its security or functionality. The engineer in me just wants to keep pressing the button to see how many skipped attempts can be made. In fact... I just might do that. *Begins furiously pressing the button*
*I'm almost positive the hash function must vary between Authenticators. If they were all the same, with only a million possible seeds and three to four million WoW accounts in the US alone, if everyone had an authenticator, each one would work, on average, for three or four different accounts. At least, until the login discrepency made the server think too many values had been skipped.
