A brief analysis of the working principle of the newly introduced Google Authenticator verification system in Android

In order to improve Android security issues, Google introduced Google verification application in Android system (Google Authenticator) to ensure the security of the account. The method of using Google verification applications is: the user installs the mobile client, generates a temporary authentication code, and submits it to the server to verify the identity. Similar verification systems also include Authy. Robbie in itGitHubThe page published its own version of Go and wrote an articleBlog Postto explain how it works.

Generally speaking, the authentication system implements a time-based one-time password algorithm, namely the famous TOTP (Time-Based One-Time Password). The algorithm consists of three parts:

1. A shared secret key (a series of binary data)
2. An input based on the current time
3. A signature function

1. Shared secret key

Users need to obtain a shared secret when creating a mobile authentication system. The way to obtain includes scanning a given QR code with an identification program or entering it manually directly. The key is thirty-two-bit encryption. As for why it is not 64-bit, you can refer to it.Wikipedia's explanation。

For those users who enter manually, the shared secret given by Google Authentication System has the following format:

256-bit data, of course other verification systems may be shorter.

For scanned users, QR recognition will be followed by URL links similar to the following:

otpauth://totp/Google%3Ayourname@?secret=xxxx&issuer=Google

2. Input based on the current time

This input is generated based on the user's mobile phone time. Once the user completes the first step of key sharing, it has nothing to do with the authentication server. But what is more important here is that the user's mobile phone time must be accurate, because from the perspective of algorithmic principles, the authentication server will repeatedly perform the user's mobile phone operations based on the same time. Furthermore, the server will calculate the token within a few minutes before and after the current time and compare it with the token submitted by the user. So if the time difference is too much, the authentication process will fail.

3. Signature function

Google's signature function uses HMAC-SHA1. HMAC is a hash-based message verification code, which provides an algorithm that can generate signatures using a relatively safe one-way hash function (such as SHA1). This is the principle of the verification algorithm: only the shared key owner and the server can get the same output signature based on the same input (time-based). The pseudo-code is as follows:

The principles of TOTP and HMAC mentioned at the beginning of this article are similar, except that TOTP emphasizes that the input must be related to the current time. Similarly, HOTP uses incremental counters and needs to be continuously synchronized with the server.

Introduction to the algorithm process

First, you need to use base32 to decode the key. In order to make it easier for users to enter, Google uses spaces and lowercase to represent the key. However, base32 cannot have spaces and must be capitalized. The pseudo-code is as follows:

Next, you need to obtain input from the current time, usually using Unix time, that is, the number of seconds from the beginning of the current cycle to the present

Here is one thing to be explained. The verification code has a time limit, which is about 30 seconds. This design is for the sake of user input, and it is difficult for users to enter quickly and accurately with the verification codes that change every second. In order to achieve this timeliness, it can be achieved by dividing 30, i.e.:

The last step is the signature function, HMAC-SHA1, all pseudo-codes are as follows:

After completing these codes, you have basically implemented the function of two verifications. Since HMAC is a standard-length SHA1 value with a length of forty characters, it is difficult for users to enter correctly at one time, so some formatting processing is also required. You can refer to the following pseudocode: