Two-factor authentication is a vital part of securing any account. By requiring a secondary code to be generated locally and entered when signing in, the account is protected even in the event of a compromised password. But how does it actually work behind the scenes?
In this blog post, I’ll be discussing the algorithms that make up the time-based one-time password two-factor authentication (TOTP). This was the topic of my Exeter Mathematics Certificate research project, so you can read a more academic write-up in my report if you’re interested.
Overview of Two-Factor Authentication
When a user wants to authenticate with a server using two-factor authentication, they need to enter their password as well as a one-time code generated by the TOTP algorithm. When 2FA is first set up, the server generates a secret key and shares it with the client in the form of a QR code, which the client scans using an authenticator app, such as Authenticate. This key, along with the current time, is used each time the user generates a code, and the server uses the same key and the current time to independently verify the code. If successful, the authentication process is complete and the server can supply the user with a token or something else.
SHA-1 Hashing
At the heart of the algorithm is the SHA-1 cryptographic hash function. A hash function takes a variable-length string of bytes, performs a number of one-way operations on them, often over a number of iterations, then produces a fixed-length string of bytes. A vital property of a hash function is that the same input will produce the same output, and that the probability of two different inputs producing the same output (a “collision”) is almost impossible.
I’m not an expert in cryptography, but I’ll do my best to explain the basics of the algorithm. RFC 3174 is a useful resource to explore the algorithm further and refer to for implementation, as it contains the text of the original document defining SHA-1.
After some pre-processing to ensure that the input is a multiple of 64 bytes by way of padding, the input is split into chunks of 64 bytes or 512 bits. Each chunk is then further broken down into sixteen 32-bit integers, which are used to generate additional integers using bitwise operations to bring this number up to eighty. Five state variables are assigned specific starting values as follows:
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0
These values are then used to generate some further values by performing eighty rounds of bitwise operations based on the chunk values. This continues until all chunks have been processed, and finally, the five state variables are combined into a single 160-bit hash value.
Implementation
I’ve implemented SHA-1 twice, once in TypeScript for my authenticator app, and once in Rust as part of my implementation of the WebSocket protocol. I referred to the RFC for guidance both times, and it was fairly straightforward to implement. However, the TypeScript implementation was significantly more difficult due to its limited support for low-level bitwise operations, in particular with working with integers.
I won’t reproduce all the code here, but I’ll show some of the key operations from my Rust implementation.
Breaking the chunk into sixteen 32-bit integers and then extending into eighty:
for i in 0..16 {
chunk[i] = u32::from_be_bytes(
message[(chunk_id * 64) + (i * 4)..(chunk_id * 64) + (i * 4) + 4]
.try_into()
.unwrap(),
);
}
for i in 16..80 {
chunk[i] = chunk[i - 3] ^ chunk[i - 8] ^ chunk[i - 14] ^ chunk[i - 16];
chunk[i] = chunk[i].rotate_left(1);
}
The main loop: (I was particularly pleased with how concise Rust’s match statement makes this bit)
for (i, tem) in chunk.iter().enumerate() {
let (f, k) = match i {
0..=19 => ((b & c) | (!b & d), 0x5A827999),
20..=39 => (b ^ c ^ d, 0x6ED9EBA1),
40..=59 => ((b & c) | (b & d) | (c & d), 0x8F1BBCDC),
60..=79 => (b ^ c ^ d, 0xCA62C1D6),
_ => panic!("Invalid chunk index"),
};
let temp = a
.rotate_left(5)
.wrapping_add(f)
.wrapping_add(e)
.wrapping_add(k)
.wrapping_add(*tem);
e = d;
d = c;
c = b.rotate_left(30);
b = a;
a = temp;
}
Hash-Based Message Authentication Code (HMAC)
SHA-1 is used in the HMAC algorithm, which simply introduces the use of a secret key into the hash. To generate the same hash from the same message, the same key must also be used. This is called a “keyed hash” and is used to verify both the integrity and authenticity of a message.
In the above diagram, opad refers to the hexadecimal value 0x5C and ipad refers to the hexadecimal value 0x36.
Implementation
The following implementation is in TypeScript for Deno. As you can see, HMAC is a fairly simple algorithm, but a very useful one nonetheless. We’re using the SHA-1 implementation from my Authenticate authenticator app.
import SHA1 from "https://raw.githubusercontent.com/w-henderson/Authenticate/master/src/crypto/sha1.ts";
function hmac_sha1(key: number[], message: number[]): number[] {
const blockSize = 64;
// Pad or hash the key to the block size
if (key.length > blockSize) key = new SHA1(key).hash();
if (key.length < blockSize) key = key.concat(new Array(blockSize - key.length).fill(0));
// Calculate the inner and outer padded keys
let outerPaddedKey = key.map(value => value ^ 0x5C);
let innerPaddedKey = key.map(value => value ^ 0x36);
// Calculate the hashes
let innerHash = new SHA1(innerPaddedKey.concat(message)).hash();
let outerHash = new SHA1(outerPaddedKey.concat(innerHash)).hash();
return outerHash;
}
let message = [0x68, 0x65, 0x6C, 0x6C, 0x6F]; // "hello"
let key = [0x6B, 0x65, 0x79]; // "key"
let hmac = hmac_sha1(key, message);
let hex = hmac.map(value => value.toString(16).padStart(2, "0")).join("");
console.log(hex); // "b34ceac4516ff23a143e61d79d0fa7a4fbe5f266"
HMAC-Based One-Time Password (HOTP)
HMAC can be used to generate a one-time password by using a secret key and a counter. The counter is simply a number, initialised to zero, that is incremented for each one-time password generated. The secret key is used as the HMAC key, and the counter the HMAC message. The one-time password is then extracted from the hash at the bit offset specified by the end of the hash.
The drawback of this approach is that it can be hard to keep the counter in sync between the client and the server, so it is not often used.
Implementation
Again, this implementation is in TypeScript for Deno.
import SHA1 from "https://raw.githubusercontent.com/w-henderson/Authenticate/master/src/crypto/sha1.ts";
import HMAC from "https://raw.githubusercontent.com/w-henderson/Authenticate/master/src/crypto/hmac.ts";
function hotp(key: number[], counter: number[]): number {
// Calculate the HMAC
let hashFunction = (bytes: number[]) => new SHA1(bytes).hash();
let mac = new HMAC(key, counter, hashFunction).calculate();
// Truncate the hash using the algorithm
let offset = mac[19] & 0xf;
let bits = ((mac[offset] & 0x7f) << 24)
| ((mac[offset + 1] & 0xff) << 16)
| ((mac[offset + 2] & 0xff) << 8)
| (mac[offset + 3] & 0xff);
return bits % 10 ** 6;
}
let key = [0x6B, 0x65, 0x79]; // "key"
let counter = [0, 0, 0, 0, 0, 0, 0, 0]; // 0 as a 64-bit integer
let code = hotp(key, counter);
console.log(code);
Time-Based One-Time Password (TOTP) at last!
Now we’ve finally discussed all the algorithms required for TOTP. It’s a bit of an anticlimax though, as TOTP is very simply just HOTP, but using the current UNIX timestamp as the counter. The timestamp is divided with integer division by the period to allow for small discrepancies between the clocks of the client and server.
And that’s it!
Conclusion
The time-based one-time password algorithm is a very interesting and not-too-complicated algorithm which is used by countless applications to provide secure two-factor authentication. Implementing it from scratch has taught me a lot about cryptography, and I hope this post has given you a good introduction to the algorithm and some ideas for implementing it yourself. If you found this post useful, please consider sharing it with others who may be interested!