Doing the two-step until the end of time

Enigma machineIn my discussion of Dropbox’s new two-step authentication, I skimped on the cryptography. Because we had to move quickly, I wanted to focus at the time just on our recommendations, so I told a few fibs about how the way the six digit codes “get” to your phone. Now I want to explain how it really works.

Not only that, but I will sneak in a little introduction to Message Authentication Codes (MAC), which plays a major role in our newest version of the 1Password data format. This topic is also worth revisiting because our new release, 1Password4 for iOS, works well with Dropbox’s two-step verification.

Speaking of, let’s start with Dropbox’s two-step authentication system. I did try to warn readers that I was being less than forthcoming about the full truth when I suggested that a six digit code is sent from Dropbox (or Google) to your phone:

There are also some really cool things about how the protocols for two-factor authentication work, but I will bite my tongue and leave that discussion for another day. What this means, however, is that a great deal of what I say in describing the system below is a pack of lies.

Even my word “protocol” could be confusing, as it might imply some network activity. The magic of the system is that anything using this type of Time-based One Time Password (TOPT) tool will compute the same six digit code at a particular time with the initial set-up secret. Dropbox’s login system will calculate the six digit code on its own; and a tool that you use, such as Google Authenticator, will also calculate the six digit code on its own. No network connection is needed after the first time setup.  In my example below, I’ll use Google Authenticator, but it isn’t the only TOPT tool out there.

Initial set up

When you first set up something like the Google Authenticator you scan in a QR code. It might look something like this:Sample QR code for setting up authenticator

The code contains a label that will typically be “Dropbox:your-email@example.com”, and it contains a secret that is randomly generated and unique for each account. The secret might look like “MQZDKZRZGBRWMMZXMI4TCMZUMYYDKYTC”. Putting this inside of a QR code just saves you a lot of typing. If you don’t have a camera that can be used to scan the code, there is even a link for getting the information that you should type in. Scanning this in is the only time that information will be transmitted (in this case, transmitted via your phone’s camera) from Dropbox to Google Authenticator.

Google Authenticator on your phone will keep a copy of the secret, and so will the Dropbox servers. That shared secret allows both Google Authenticator and Dropbox to calculate the same six digit codes when needed.

Counting on time

When you log into Dropbox with your username and password you will then be prompted for the six digit code if you have enabled two-step verification. You will then open Google Authenticator on your phone and you will see six digits. Those six digits are computed from a combination of the the shared secret and the current time. The current time is the number of seconds since the first instant of 1970. It is rounded down to the nearest half minute. This is why the number changes every thirty seconds.

Dropbox website prompting for security codeWhen you enter the six digit code during Dropbox’s login process, Dropbox will perform the same calculation. It has a copy of the secret that was first shared, and it too knows the current time. If what you enter matches what it has calculated, you’re in.

Your phone will not need any network connection as long as its clock is reasonably accurate. Fun fact: your phone actually makes minor adjustments to its clock pretty much every time it connects to any kind of network that allows it to check a time server on the internet. Today, most networked computers and devices know the current time to within less than one 10th of a second.

Because the code depends on both the time and on the shared secret, we end up with a different code during each 30 second period. This makes it a one time password.

Beyond the end of the world (January 19, 2038)

Ancient eunuchs foretold global catastrophe on January 19, 2038, as their long count calendar comes to an end and starts a new cycle from zero

—Anonymous

Aztec sun stone (replica)

Replica of the Aztec sun stone. This has nothing to to with Unix or Mayan time keeping.

The number of seconds since the very beginning of 1970, known as Unix time, is often maintained in a single variable in the computer’s operating system. When Unix was first designed, this number was stored in 32 bit variable. That means that the number could range from 0 to 232. Zero corresponds to the midnight January 1, 1970 (UTC). So what time does 232 correspond to? That will be 3:14:07 (UTC) on January 19, 2038. Bad things will happen then to computers that still are still using 32 bit integers to store Unix time.

So will Google Authenticator stop working in 2038? No, it should be fine. Even though iOS devices – based on 32-bit ARM chips – do just use 32 bit “long” integers, Google Authentication doesn’t rely on that. It uses NSDate to get Unix time on iOS.

Indeed, the actual standard defining the TOPT states:

The implementation of this algorithm MUST support a time value T larger than a 32-bit integer when it is beyond the year 2038.

Another wrinkle in time

Unix Time really is the number of seconds since the very beginning of 1970, but that number ignores leap seconds. Twisted clockLeap seconds are added (or subtracted) on occasion to account for the fact that the speed of the Earth’s rotation can change slightly due to earthquakes, other seismic activity, and even tidal activity (not only do I get to talk about a calendar system reaching its end and resetting, I get to talk about earthquakes and tidal waves in the same post!). A leap second was added at the end of June 2012, so noon (leap second adjusted) on July 1 was actually only 86399 seconds later (by Unix time) than June 30 instead of 86400 seconds later as you would normally get between two days.

The TOPT standard requires the use of Unix time, which is defined to ignore leap seconds. This way, everyone who follows the standard will be using the same clock and calendar. Also, keep in mind that Unix time isn’t just for Unix-based operating system like OS X, iOS, and Android. Windows has a similarly defined FILETIME, which differs in its start time and that it counts in nanoseconds instead of seconds, but it can be converted to Unix time easily enough for use in the TOPT protocol.

Time to meet MAC

Earlier, I said that the code, or one time password, is computed from the secret key and the time, but not just any old computation will do. For the system to work securely, we need the computation to meet some requirements which include:

  1. It must be easy to calculate the code from the key and the time, but it must be completely unfeasible to calculate the key from the code and the time.
  2. It must be unfeasible to predict without knowledge of the key what the code will be at some particular time even if you have observed what the code is at many other times.
  3. The calculation will always give the same result if given the same key and time (it is a function).

These look similar to some of the requirements we wanted for a good cryptographic hash function. And a cryptographic hash function will play a central role in how this is all done.

This also looks as if we are using a shared secret key to create a digital signature on the time. Digital signatures also involve hash functions. But “digital signature” isn’t really the right term here because those are based off of public/private key systems. With TOTP, we have a shared secret.

In place of a digital signature, we have a Message Authentication Code (MAC). This is not to be confused with “MAC” of “MAC address” that you see as hardware addresses for networking equipment, and certainly not to be confused with “Mac” (Apple’s family of computers) or “mac” (the mackintosh raincoat). Maybe this will help keep things clear:

A lowercase mac, for when you need wet wear
And an all-caps MAC is made by software
You’d be just as cool as the great Ry Cooder
If  you never confound these with a Mac computer

One of the ways to use a cryptographic hash to create a MAC is the HMAC. You will hear more about HMAC in the not-so-distant future.

Keeping time, time, time

One consequence of this sort of system is that it makes the computers’ knowledge of the time part of the security system. This isn’t anything new; this requirement has been part of the Kerberos system for decades. Indeed, one of my first roles in system administration was keeping clocks in sync with each other, specifically for Kerberos.

TARDIS

Unfortunately, this means that if someone can tamper with the time signals a computer receives from outside, then they can do damage to other aspects of security. We need systems to verify that the messages they get about the time are authentic, but the less-than-ideal state of secure time synchronization could be the subject for a new series of rant posts. Fortunately, I’ll spare you.

It is also not clear at this point what forms of time travel this or other security protocols can resist. I believe that there is a research paper in this question somewhere for an adventurous student and a flexible professor.

Six digits from 160 bits

Let’s now put all of these pieces together. Dropbox and Google Authenticator each have the shared secret from when you set up your two-step verification. And each know the correct time at the moment. So when each calculate the HMAC of the current time, using the shared secret as a key, they will calculate the same number. If they use SHA-1 for the hash function (as they do in the current system) the number that they calculate will 160 bits long, or roughly 48 digits. The final step is to compute a 6 digit number from that 160 bit number. But let’s save time and skip those final details.

Time for closing remarks

Dropbox’s two-step authentication is a great thing, and 1Password for iOS now works more smoothly with it. But it does the most good for people who are using weak or re-used passwords to log into Dropbox. Thankfully, 1Password users don’t really need to worry about that problem.

Other posts in this series

  1. Guess why we're moving to 256-bit AES keys (March 9, 2013)
  2. Authenticated Encryption and how not to get caught chasing a coyote (January 18, 2013)
  3. Doing the two-step until the end of time (December 20, 2012)
  4. Alan Turing's contribution can't be computed (December 8, 2012)
  5. Hashing fast and slow: GPUs and 1Password (December 5, 2012)
  6. Credit card numbers, checksums, and hashes. The story of a robocall scam (October 18, 2012)
  7. Flames and collisions (June 7, 2012)
  8. A salt-free diet is bad for your security (June 6, 2012)
  9. Cipher of Advanced Encryption Substitution And Rotation (April 1, 2012)
  10. Do you know where your software comes from? Gatekeeper will help (March 1, 2012)
  11. AES Encryption isn't Cracked (August 18, 2011)