Math to the Rescue

Through the use of cryptographic hash functions, Alice (the user) can prove to Bob (the authenticating server) that she possesses a secret which is shared between Alice and Bob. In practice, this means that the user can convince the server that he and the server know the same large number (secret key). (This satisfies the something you have requirement by being large enough that most humans cannot remember it.)

How Does It Work?

Let’s consider the requirements of useful one-time passwords:

• Deterministic, so both the user and the authenticating server know the next password
• Prohibit replay (“one-time”)
• Hard-to-guess (“password”)
• Short enough to use

These requirements led the HMAC-Based One-Time Password (HOTP) team to reach the following design decisions:

• A shared secret as the information common to both parties
• A counter that is incremented each time a password is created to prohibit replay
• A Hash-Based Message Authentication Code (HMAC) to hide the shared secret and authenticate the count
• A custom truncation function to shorten the final value

When you sign-up for “two-step verification” with Google or Dropbox, you get a secret key. Since you’re probably using a smartphone, you get the secret key in a QR code (or you can view it and type it in by hand.) Because smartphones tend to know the current time, these services use the Time-Based version of HOTP, called TOTP. In TOTP, the current time is used as the counter value. (Specifically, the counter is current number of seconds since January 1st, 1970 at midnight, UTC, divided by 30, with the remainder dropped.)
At this point, you have the secret key and the counter value. All that left is some math and truncation. Wikipedia has a great explanation of HMAC, so I’ll let you read it there. Note that most HOTP and TOTP implementations use SHA-1. The custom truncation function sounds complex, but is quite simple.
Given a block of 20 bytes from the HMAC-SHA1 function, take the last nibble. Recalling that the possible range of a nibble is zero to 15, use the value of the nibble as an offset. Pull 32 bits from the block of 20 bytes, starting at the byte offset given in the last nibble. Ignore the most-significant bit of the 32 bits you pulled to avoid any sign-related issues. Decide how many digits will be displayed—most implementations use six. Take the remaining 31 bits modulo 10^(number of digits to display). The result is the one-time password.
The a working demonstration is available. You can browse the code for my JavaScript implementation which uses the excellent Stanford JavaScript Crypto Library.