How one-time passwords work

Introduction

As practice shows, there is a certain lack of understanding of the principles of operation of one-time passwords (these are the ones that are used in GMail, in special tokens of payment systems, and so on).

After reading this short article, you will understand how one-time passwords based on hashes work , and at the same time write a small program in Python that can calculate passwords for Google’s two-step authentication.

Hash function

The hash function allows you to take any data of any length and build on them a short "digital fingerprint". The length of the hash function value does not depend on the length of the source text; for example, in the case of the popular SHA-1 algorithm, the length of this fingerprint is 160 bits.

To understand why a value always has the same length and does not depend on the source text, you can simplify the hash function in the form of a code lock with wheels. First we set all the wheels to “zero”, then go through the text and scroll the wheels for each letter in accordance with some rules. The number that will be locked at the end is the value of the hash function. Examples of such functions are MD5, SHA-1, GOST_P_34.11-94.

Do not invent your own hash functions, use standard implementations (for example, in the case of Python):

import hashlib
print hashlib.sha1("Hello, Bob!").hexdigest()

Результат: 88192e3e2e83243887410897efd90287b8e453a7

The idea of ​​a hash function is that it works in only one direction: it is very easy to calculate for War and Peace, but it is almost impossible to find a document that gives the same value from the already prepared value of the hash function. Even if you change only one letter in the document, the hash will change completely :

import hashlib
print hashlib.sha1("Hello, Bob?").hexdigest()

Результат: cbad4b0e05703acf2e8572be7438830fe7f8ddf5


In this regard, there is a natural desire to use the hash function to control the integrity of the messages that Alice sends to Bob: Alice calculates the SHA-1 value for each message and puts it in an envelope; Bob, having independently calculated the SHA-1 of the text, can compare his result with Alisin and make sure that the message has not been changed somewhere along the way.

However, we forgot about Mallory, who is somewhere between Alice and Bob, intercepts their correspondence and opens the envelopes! He may well change the message, and then calculate SHA-1 for him and attach to the letter; Bob will compare the values ​​and not notice anything.

Authentication

After thinking, Alice and Bob agree at the meeting that when calculating SHA-1, they will temporarily add a secret word, for example, “Secret” to the text (of course, in reality Alice and Bob decided to use a much longer word so that it would be difficult to find) . Mellory does not know this word, and therefore, even if she changes the message, she will not be able to adjust its hash, right?

Example:

import hashlib
print hashlib.sha1("Secret" + "Hello, Bob").hexdigest()

Результат: 99beeff3ef1971d2cb1be129f986739f6bcba8cc

Unfortunately, there are problems. Yes, Mellory cannot change the body of the message, but (since he knows the hash from the current text), he can always add at the end of “PS In fact, this is all rubbish, we have to leave, Bob” and just count the hash from the remainder (remember the analogy with combination lock).

To protect against this, we will complicate our function a little:

print hashlib.sha1("Secret" + hashlib.sha1("Hello, Bob").hexdigest()).hexdigest()

Результат: 3f51e9fc540676bc3ce54367fd3e467f3299c743

Now appending something to the end of the message will completely change the source data for the “external” call to SHA-1 and Mellory will remain out of the game.

Alice and Bob just came up with what is called HMAC (or hash-based message authentication code ): a hash-based message authentication code . In reality, the HMAC, adopted as the RFC2104 standard, looks a little more complicated due to alignment of the key length, a pair of XORs inside, the participation of the key in the “internal” hash, but the essence does not change.

Do not invent your own HMAC implementations, use standard implementations, for example, HMAC-SHA1:

import hmac
import hashlib
print hmac.new(key="Secret", msg="Hello, Bob", digestmod=hashlib.sha1).hexdigest()

One-time passwords

What is a one-time password ? This is a password that it is useless to intercept using a keylogger, peeking over your shoulder or listening to a telephone line - as this password is used exactly once.

How could this scheme be implemented? For example, Alice can generate a hundred random passwords and give a copy to Bob. When Bob calls next time, he will dictate the highest password in the list, Alice will verify it with her, after which both will delete it. At the next call, they use the next password and so on until they run out. This is not very convenient: storing lists, generating new passwords, and so on.

It is better to implement this scheme in the form of an algorithm. For example, a password is its number in order, multiplied by a secret number. Let Alice and Bob agree that the secret number is 42; then the first password will be 42, the second 84, the third 126 and so on. Mellory, who does not know the algorithm and the secret number, will never guess which password will be next!

Of course, the algorithm is better to choose more complicated. Alice recalls HMAC and offers Bob to read password number N according to the formula: HMAC ("Secret", password-number) . After that, they need to agree on a key (in this case, “Secret”), but then Bob only needs to remember what kind of password he generates (for example, the twentieth):

import hmac
import hashlib
print hmac.new(key="Secret", msg="20", digestmod=hashlib.sha1).hexdigest()

Результат: 393e9efaae1a687bc2dcc257c8e9e2a61f26fe4b

However, Bob does not smile at all every time to dictate such a long password. They agree with Alice that they will use only part of it, for example, the last 6 characters.

For a while, everything is going well. Until Bob and Alice get tired of counting what kind of password they use. Someone tells them that as an argument to HMAC (), instead of the number, you can use everything that Alice and Bob have simultaneous access to ... for example, the current time!

Our heroes synchronize their clocks and agree that they will use unix time as the argument to HMAC () - the number of seconds that have passed since the UNIX era(in UTC). To enter the password in no hurry, they decide to divide the time into 30 second “windows”; thus, the same password is valid for 30 seconds. Naturally, Alice, who checks passwords, for 30 seconds does not allow the password to be used again (just remembering it) and thereby leaves it truly “one-time”.

Now the password is calculated using the following formula: HMAC ("Secret", unix_timestamp / 30) .

We received one-time passwords based on the current time . Only those who have the key can generate and verify these passwords (“Secret” in the example above); in other words, the server and user.

It should be noted that one-time passwords can be calculated using other algorithms; the main thing is that the algorithm and the secret are known to both parties. But since we have a standard, then we will talk specifically about it

OATH, TOTP, HOTP, RFC ... WTF?

So, we just described the basic ideas that underlie:

1) HMAC, hash-based message authentication code: RFC2104
2) HOTP, hash-based one-time password: RFC4226
3) TOTP, time-based one-time password: RFC6238

These ideas are one of the cornerstones of the Initiative For Open Authentication (OATH) initiative to standardize authentication methods.

Google 2-step verification

One-time passwords based on time (and calculated based on the TOTP RFC 6238 algorithm) are also used by Google in the Google Authenticator application , which can be installed on iOS, Android, BlackBerry. This application automatically generates one-time passwords every 30 seconds (in addition to the main password on Google Account). This means that even if someone snoops or intercepts your primary password, it will be impossible to enter the system without the next one-time password. Conveniently.

ATTENTION : I DO NOT HAVE ANY RESPONSIBILITY FOR YOUR ACTIONS WITH TURNING ON AND OFF THE TWO-STEP AUTHENTICATION OF GOOGLE; YOU AGREE THAT YOU FULFILL THEM AT YOUR OWN RISK .

In fact, there is nothing to worry about (there are instructions, there are trusted computers, there are backup codes, etc.), but if you try hard by thoughtlessly clicking on the buttons, you can completely lose access to your account. And yet: if you’re not ready to experiment, don’t touch Gmail; just download the Google Authenticator app on your phone, manually add a “key by time” (for example, “a abc def abc def abc” or just scan the QR code below).

First, we need to get the secret key, which is used to create a one-time password. You can see it on the page for adding Google Authenticator in the account settings, it is located under the QR code:



Please note that if two-step authentication is already enabled, then you cannot find out the old key: you will have to delete the old one and generate a new one. It is not difficult; most importantly, do not forget to immediately update the key in Google Authenticator, if you use it.

The key is encoded in Base32 (for convenience, remove the spaces and translate the letters in upper case).

A program that calculates the current one-time password:

import time
import hmac
import hashlib
import base64
### TOTP-key (get it from Google)
secret = base64.b32decode("AABCDEFABCDEFABC")
### Calc counter from UNIX time (see RFC6238) 
counter = long(time.time() / 30)
### Use counter as 8 byte array
bytes=bytearray()
for i in reversed(range(0, 8)):
  bytes.insert(0, counter & 0xff)
  counter >>= 8### Calculate HMAC-SHA1(secret, counter)
hs = bytearray(hmac.new(secret, bytes, hashlib.sha1).digest())
### Truncate result (see RFC4226)
n = hs[-1] & 0xF
result = (hs[n] << 24 | hs[n+1] << 16 | hs[n+2] << 8 | hs[n+3]) & 0x7fffffff### Print last 6 digitsprint str(result)[-6:]

Now you can put the running Google Authenticator next and compare the values.

upd: an example implementation in JavaScript (thanks roman_pro )

upd # 2: if you want to play with 2-step verification from dropbox, add "======" at the end of the secret (this is necessary for padding and the base32 decoder to work correctly).

findings

1. One-time passwords are easy.
2. Standards are good.
3. If desired, they can be embedded in your application (use ready-made libraries; for example, from the source code of the same Google Authenticator ).