Authenticators! How Do They Work?

Have you ever used one of those authenticator thingies that have become popular over the last few years? The ones that add an additional password to your account when you log in, a random 6-to-8 digit number that changes every 30 seconds or so? I sure hope you have, because those things add an additional layer of security to your account that can be very helpful to ward off account stealing attempts.

But have you ever wondered how they actually work? When I looked around for some information on the more technical details when I wrote my last post, I realized that there isn’t a lot of easily available and understandable information around. Or at least I couldn’t find it. When you search for “how does the blizzard authenticator work”, for example, you get a lot of results that explain to you how to use it (buy/download, attach to your account, additional passcode field shows up when you log in), but no information of how the authenticators themselves work. he closest I got was this article on WoWWiki, which itself doesn’t cite any sources. You can also find some technical information of how SecurID works, which (as far as I know) all the key fob style authenticators are modeled after. T But that information is probably not an easy read for someone without any background in cryptography.

I don’t think that’s a good state of affairs, because people should have a chance to at least roughly understand how their security technology works. That way, authenticators are less of a voodoo black box, you can understand what actually makes those authenticators secure, and most importantly perhaps, you can make an informed decision whether you’d rather use the key fob style or the smartphone app style.

So, since I couldn’t find any explanation of the technical workings of authenticators, explained on a basic level, I decided to write my own. Now, I have to add an important disclaimer to this post:

  1. I’m a computer scientist. I hope I broke down the information in a way that makes it accessible to non-computer scientists. If you don’t understand an explanation, please tell me, and I’ll try to fix it.
  2. While I’m a computer scientist, I’m not a cryptography or security expert. I hope I didn’t get any of the details wrong, or put them the wrong way. If you are an expert and can show that I presented something wrongly, please tell me, and I’ll try to fix it.
  3. Most technical information that’s the basis of this explanation was pieced together from sources on the Internet. For a few details, I even used reasonable guesses. Again, if you know better than me and can show that I got something wrong, please tell me, and I’ll try to fix it.

Definitions (a.k.a., the boring part)

Let’s first run through a few short definitions. I’ll use them later on, and I’ll make this part short and hopefully easy to understand. The links lead to wikipedia for people who want to dig deeper.

Algorithm: The exact definition is much deeper and quite philosophical, but for this text, you can think of it as “a piece of computer code that calculates a result from some given input”.
One-way function: A one-way function is an algorithm that transforms an input into an output, with calculations that are easy enough to run very fast. However, the opposite is not true: given the output, it’s extremely hard (and practically impossible) to calculate the input. Like a one-way street, you can only go in one direction, but not the other. This is very useful for some types of encryption or authentication.
Pseudorandom number generator (PRNG): Computers suck at being random. They are built to calculate, and to produce the same output for the same input every time. True randomness is actually a very hard problem. Radioactive decay is considered a true random process, but for obvious reasons, people aren’t too keen on putting a plutonium reservoir into their PCs. The next best thing are PRNGs: they produce output that looks random, but isn’t really: they’re just algorithms that take a single number (a seed) as input, and from that produce one or a sequence of numbers that look sufficiently random (as defined by probability theory, but we’ll leave that to the mathematicians). Given the same seed, a PRNG will always produce the same sequence of numbers. We’ll see why this can be useful.
Cryptographically secure PRNG: It’s simply a PRNG that fulfills some extra requirements. In easy terms, an attacker who looks at a sequence of numbers from a PRNG must not have a chance to deduce any information that could lead to the PRNG’s seed.
Public-key cryptography is one of the wonders of modern encryption. It used to be that an encryption key was a shared secret between two parties. You used a key to encrypt your data, and you needed the same key to reverse the encryption. That had the huge problem that you needed to get the key to the other party securely by some means, because whoever learned the key could decrypt your communication. Public-key cryptography uses two keys, a public one that you can tell everybody, which is only good for encrypting data. To decrypt the data again, you need a private key which you keep confidential. This works by using certain one-way functions. This means you get out of the key distribution problem, because you can distribute public keys and still have encrypted communication.

OK, I promise that was the hardest past. Now on to pretty pictures! I’ll use different colors to denote different keys used in the authentication process. Obviously, they’re not really colored, but it’s maybe easier to keep track if each key has an assigned color.

Key fob style authenticators

authenticator-scaledSo you have an authenticator. It has a button, a display, and a battery. It also has a pretty picture on the front.


blizzard-authenticator-backThe back looks less interesting, but has a very important piece of information: the serial number. (Mine has become partly unreadable over the years. This is bad.)


authenticator-keyApart from a microcontroller (the kind of computer that runs your washing machines, dishwashers, etc.), the key fob also contains a battery, a battery-buffered clock, and a key, that is, a piece of secret data that is used to calculate the numbers that appear when you push the button. This key is unique to this key fob: no other produced authenticator shares this key. This is the “secret sauce” that makes your authenticator work: if anybody ever was able to extract the key from the fob, they could create the same one-time passwords, and log into your account. Thankfully, those key fobs are very sturdy, and extraction is extremely complicated, expensive, and very much destructive to the device.


blizzard-masterkeyBlizzard holds a special master key. This master key was used to create all keys in all fobs (of a specific production run; there are good chances that Blizzard changes them from run to run). To create each fob key, the master key is combined with a number via a one-way function. And that number? That’s the S/N on the back of your authenticator. (It was pointed out to me in the comments that some key fob producers do not actually use a master key to create the fob keys, but instead create random fob keys and then provide Blizzard or other company customers with a lookup list that contains for each fob its key and the S/N. From a security point of view, this doesn’t make much of a difference, though such a list should have a very light theoretical security advantage.)

To register your authenticator with Blizzard, you log in and enter the serial number on the back of your authenticator. Blizzard takes that serial number, combines it with the master key and computes your fob key. It then puts that key information with the rest of your account information. Now you both have a copy of that key. We’re almost done!

register-keyfob

Note something very nifty: The secret key was never sent over your Internet connection, or entered on your keyboard. That way, if your computer is compromised by spyware, or someone is eavesdropping your connection, they don’t learn anything useful. They know your authenticator’s serial number, but to create your one-time passwords, they’d need the (silver) key. But to calculate that from your S/N, they would need Blizzard’s (golden) master key! And that one is stowed away as securely as possible. If an attacker managed to get their hands on that one, all authenticators would suddenly be vulnerable. Then again, if they got that, you’d probably be screwed anyway, because chances are they also made away with your main password as well as credit card and other sensitive information. (In the case of a lookup list, the S/N is just searched in the list, and the corresponding “silver” key information taken from that list. Again, no key information is transmitted, and if the list ever got stolen, key fobs would be compromised.)

Now what if we want to authenticate? We have a key, but if we simply use that as input to a pseudorandom number generator (cryptographically secure or not), we will only ever get one password: same input, same output. Not very secure, is it? That’s where the battery-buffered clock in the authenticator comes in. Instead of simply using the key as the input, the key is combined with the current date and time, and that is used as input. Your authenticator knows what time it is, Blizzard knows what time it is. As long as they agree on that time, both will calculate the same result, which to an outsider looks like random gibberish and doesn’t give any information about the key that was used.

keyfob-authenticate

This has the nice side effect that each authenticator passcode is only valid for a short amount of time. That prevents an attacker from eavesdropping and recording the password, or pushing the button and recording the output when you aren’t looking, and using the authenticator code later on when they got a hold of your main password. Incidentally, the clock is also the reason those key fobs are pretty much broken beyond repair once the battery runs out: even if you could exchange the battery, there is no way to set the time after power is restored. Server and authenticator are out of sync and won’t produce the same numbers any more.

Mobile Authenticators

Those key fobs have a couple of downsides. First, you have to pay for them, while the mobile authenticator is a free download from Google’s or Apple’s app store. Second, you have to order the key fob and then wait until it arrives at your door via snail mail, while you could use the mobile authenticator within a couple of minutes. Third, if you need to access your account from outside home, you have to remember to take your key fob with you, while you’re probably carrying around your phone anyway.

So you decide to use the mobile authenticator. How does that work? How is it different from the key fob?

mobile_authenticator_keysThe different (and most complicated) part is the initial setup. Since you download the app from Google’s or Apple’s app store, every version of the app is the same. It doesn’t contain a unique secret key like the key fob does. What it does come with though, is a public key from Blizzard (golden). Remember that such keys that consist of a pair of public and private key are special: Blizzard can safely tell everybody public key and still keep its corresponding private key secret. Also note that this “golden” key is not the same as the “golden” key in the key fob explanation. I’m sorry if that is confusing, but I ran out of cool colors, and what says coolness more than gold?

Anyway, in addition to Blizzard’s public key that was provided, the app creates a random “session key” (red) when it is started for the first time. After that, it will connect to the Blizzard server to create a key just like the secret key that resides inside the key fob. To do this, it uses the session key, encrypts it with Blizzard’s public key, and sends the encrypted session key to Blizzard. (This is denoted by the red key in a golden box.)

mobile_authenticator_session_key_exchange

Blizzard decrypts the session key with its private key. Note that nobody else can get the red key out of the golden box: the public key is only good for “locking the box”, so to speak, not for unlocking it. Now both sides have the (red) session key and can use it to talk to each other securely. Blizzard now creates a secret key, just like the (silver) one that resides in a key fob. It encrypts that key with the session key, and sends that to you (silver key in a red box).

mobile_authenticator_secret_key_exchange

Since your authenticator also knows the red key, it can decrypt the secret key. Voila! Now both Blizzard and your authenticator know the secret (silver) key. Setup is over, the red key isn’t needed any more and thrown away, and the day-to-day authentication works exactly the same as with the key fob authenticator:

mobile-authenticate

You don’t even need any Internet connection while you’re creating authentication codes. All you need is a reasonably accurate clock. If your phone gets out of sync for whatever reason (which it typically shouldn’t, if your phone network provides time information), the authenticator has a button to resynchronize to Blizzard’s servers. Synchronization, of course, requires an Internet connection.

Threats

So let’s look at a couple of threat scenarios, and which type of authenticator fares better in each.

Attacker taps my Internet connection: during normal operation, all the attacker can learn that way are the short-term passwords. If they already know your normal password and are very fast, you’re screwed in both cases. If they don’t, there’s nothing to learn for them: the 6-to-8-digit passwords do not provide any useful information about your secret key. The main difference is that the mobile authenticator doesn’t come with a pre-installed secret key, so it needs the key exchange described above to get it. You’ll note that the red session key is created “randomly”. Now, as I said, true randomness is hard to achieve for computers. So there is some theoretical risk if an attacker could figure out how your phone’s random number generator was initialized, and therefore could figure out what session key (red) you created. Then, the attacker could eavesdrop on your connection, capture Blizzard’s response, and decrypt the (silver) secret key with the guessed session key. Winner: both are secure, key fob has the edge.

Attacker learns my secret key: With a key fob, this is pretty much impossible. Getting to know your secret key involves opening your device and doing some serious hardware hacking. At the very least, you’d notice it immediately after it’s done, because an attacker would have to break it open. With a mobile authenticator, this is much easier: the attacker would have to (get you to) install some spyware on your phone that reads your secret key and sends it to them. Winner: key fob.

Losing / breaking your phone / fob: During the initial setup of the mobile authenticator, the app shows you a recovery key that you are supposed to keep in a very secure place. If you ever lose your phone or need to reinstall the app, you can use that key create a replacement authenticator. With your key fob, if you lose or break it, you’re out of luck. Off to Blizzard’s phone line you go. Have some government-issued ID or similar documents ready to mail them to unlock your account. Winner: mobile authenticator.

Attacker steals or “borrows” phone / fob: Like all other attacks, this only gives the attacker a chance to compromise your account if they also know your main password. If an attacker gets physical access to your authenticator, you’ve pretty much lost the fight. With a fob, the attacker can immediately log into your account and, for example, detach your fob and attach another authenticator, locking you out. With a phone, a screen lock might delay an attacker, but those things are not very secure. Winner: you are screwed regardless, mobile has the edge.

Attacker “persuades” you: That’s up to you. It’s your decision how much of your health your account is worth to you…

Yeah, not even a Thunderfury is worth going through that. [source: xkcd.com]

Yeah, not even a Thunderfury is worth going through that. [source: xkcd]

To summarize, the tradeoff is a pretty classical one between security and convenience. The key fob is the more secure device, but if you lose or break it, you can expect a lot more work (and time!) until you get access to your account again. On the other hand, the mobile authenticator’s most glaring risk is that the secret key can be stolen by spyware, which should not be underestimated. Mobile phones are not that secure, after all. But if something happens to your phone, you can use your recovery key to authenticate yourself from a replacement phone, which is both faster and a lot less hassle. Which one you chose is ultimately up to you.

8 thoughts on “Authenticators! How Do They Work?

  1. One detail that might be worth adding: to remove an authenticator from your account, if I recall correctly, you need to enter TWO codes in a row. So this specifically prevents anyone who taps your internet connection and eavesdrops a code from being able to instantly use it to remove the authenticator from the account.

    1. Indeed, you need two consecutive codes, and what you say is most probably the reason. I’ll try and see where I can put that into the text. Thanks!

    1. Thanks! You might be right. My half-assed PS Vita “test” post I wrote in 2011 after I came back from Japan, and which took about half an hour to piece together, is one of my all-time top posts.

      I think this one’s a lot better than that one. (Not that it takes much.) Definitely took more time to write!

  2. First off, very nice post and I will now be following ;)

    Secondly, let me put the full disclaimer out there. I work for VASCO, i have worked for VASCO for a long time and I’m a technical person, some would even call me an engineer, although today I do a lot less engineering than I previously have. The comments I make here are my own personal views. I can not comment directly on what any of our customers use or do not use, so I can’t directly comment on the Blizzard devices.

    Ok with those things out of the way, the one big comment I have for you is with regards to the hardware tokens. You mention that the devices use a “master key” and that the serial number is used in combination to generate each device’s unique key. In some token manufacturers this is correct. With VASCO, this is not correct. Instead VASCO programs every single device with its own unique key right from the factory. This has a few advantages. First, there is no master key you can use or you can find to try and reverse the password generation algorithms. Second, if you manage to get the secret key of a single device, it will not work and has no relation to any secrets on any other device. I’m sure you can find other advantages to this method, but just to set the record straight, these are the ones I will toss out there.

    I think you have hit the nail on the head with this post. The end result being, the convenience verse security. The choice for any person is how much convenience do I need verse how much security do I want, and in the end how much will it cost me to do one thing over another. Hopefully after people read your post they will have more than enough information to make that informed decision.

    Thanks for the post and for letting me comment on it.
    -Will

    1. Hey Will,

      thank you for the detailed feedback!

      So the way I understand you, with VASCO, the “master key” is more like a “master list” that the customer (Blizzard or whichever company) gets, that lists for each device the relation between the serial number and the device key? I thought that might be another possibility when I wrote the text, so I just guessed which version I found more likely. It makes sense that way too, though. So it’s a bit like a one-time pad. Though in an abstract way, it’s pretty much the same: the “master key” is not a single key, but a list, but it still gives the company a way to get from S/N to key, and if the key/list is compromised… well, bad things happen.

      Though from a theoretical point, a list (which is just like a one-time pad) is of course safer in than any key-based cryptography, because if I remember my basic classes right, it’s provably unbreakable… if the list is truly randomly generated, but at that point it gets complicated again, of course. I wouldn’t be surprised if a company like VASCO takes the random-number generation part for those lists very seriously.

      I hope you’ll enjoy other posts on this blog too! Though they’re rarely that technical and howto-ish.

  3. Well I don’t know if I would call it a master list, but certainly there is an exchange of records between VASCO and our customers. As a point of discussion, it’s generally not a good idea to keep lists around, so generally speaking we don’t keep lists (nor should anyone) and the details should only every be located in one location, which is usually the companies security infrastructure. In most cases the serial number is just a unique identifier for a specific record, kinda like a user name. The record itself can then be further modified and stored completely separately. I know people that don’t use the serial number at all and just use the code generated by the device as a mapping identifier.

    The codes generated are always random and can be generated more than one time, so keeping a list of passcodes generated doesn’t help. They aren’t like the old scratch lists where you can just scratch them off as you use them (I would consider those lists to have passcodes that are more Event based rather than time based). The probability of how often a passcode comes up is as random as possible given the algorithms used.

    1. Yeah, that’s what I basically meant. I didn’t mean that there’s a list of possible passcodes from a device, that would indeed be silly. I just meant there is an entry in a list, or a record, for every single device, to allow initial setup.

Leave a Reply