How one-time passwords work

Introduction

As practice shows, there is a certain lack of understanding of the principles 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 are based on hashes , and at the same time write a small program in Python that can calculate passwords for Google two-step authentication.

Hash function

The hash function allows you to take any data of any length and build a short “digital fingerprint” on it. The length of the hash 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 the value always has the same length and does not depend on the source text, you can simply imagine the hash function as a combination lock with wheels. First, we put all the wheels in a “zero”, then we go through the text and for each letter we scroll the wheels in accordance with some rules. The number that will be at the end of the lock is the value of the hash function. Examples of such functions are MD5, SHA-1, GOST_R_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 only in one direction: it is very easy to calculate it for War and Peace, but it is almost impossible to find a document that gives the same value using the ready-made hash value. Even if you change only one letter in the document, the hash changes 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 value of SHA-1 for each message and puts it into an envelope; Bob, having independently counted the SHA-1 text, can compare his result with Alisin and make sure that the message was not 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 can easily change the message, then calculate SHA-1 for him and attach it to the letter; Bob will check the values ​​and notice nothing.

Authentication

Thinking, Alice and Bob agree upon meeting that when calculating SHA-1 they will temporarily add a secret word to the text, for example, “Secret” (of course, in reality Alice and Bob decided to use a much longer word to make it difficult to find) . Mallory does not know this word, and therefore, even if he changes the message, he will not be able to correct his hash, will he?

Example:

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

: 99beeff3ef1971d2cb1be129f986739f6bcba8cc

Unfortunately, there are problems. Yes, Mallory cannot change the body of the message, but (since he knows the hash from the current text) he can always finish writing “PS In fact, all this is rubbish, it's time for us to leave, Bob” and just count the hash from the rest (recall the analogy with combination lock).

To protect against this, we will slightly complicate our function:

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

: 3f51e9fc540676bc3ce54367fd3e467f3299c743

Now adding something to the end of the message will completely change the source data for the “external” call to SHA-1, and Mallory remains out of the game.

Alice and Bob have just come up with what is called an HMAC (or hash-based message authentication code ): a hash-based message authentication code . In reality, HMAC, adopted as the RFC2104 standard, looks a bit more complicated by aligning the key length, a pair of XORs inside, key participation 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 is useless to intercept using a keylogger, peeping over your shoulder or listening to the phone line - because This password is used exactly once.

How could this scheme be implemented? For example, Alice can generate hundreds of random passwords and give a copy to Bob. The next time Bob calls, he will dictate the topmost password on the list, Alice will verify it with hers, after which both will delete it. The next time they call, they use a regular 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, the password is its number in order, multiplied by the 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. Mallory, 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 difficult. Alice recalls about HMAC and suggests that Bob read the password number N according to the formula: HMAC (“Secret”, password number) . After that, they need to agree on a key (in this case, it is “Secret”), but then Bob needs only to remember what account 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. She and Alice agree that they will use only a part of it, for example, the last 6 characters.

For a while everything goes well. Until Bob and Alice are bored of counting which password they use for the account. Someone tells them that instead of a number, everything that Alice and Bob have simultaneous access to can be used as an argument of HMAC () ... for example, the current time!

Our heroes synchronize their watches and agree that they will use unix time as the HMAC argument () - the number of seconds elapsed since the onset of the UNIX era (in UTC). To enter the password without haste, 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 using the password again (just by remembering it) and thus 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 current time . Only those who hold the key can generate and verify these passwords (“Secret” in the example above); in other words, server and user.

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

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

So, we just described the basic ideas underlying:

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, which aims to standardize authentication methods.

Google two-step authentication

Time-based one-time passwords (and calculated based on the TOTP RFC 6238 algorithm) are also used by Google in the Google Authenticator application, which can be set on iOS, Android, and 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 log in to the system without another one-time password. Conveniently.

ATTENTION : I AM NOT RESPONSIBLE FOR ANY RESPONSIBILITY FOR YOUR ACTIONS WITH TURNING ON AND OFF THE TWO-STAGE AUTHENTICATION OF GOOGLE; YOU AGREE THAT YOU PERFORM THEM AT YOUR OWN RISK .

In fact, there is nothing scary there (there are instructions, there are trusted computers, there are backup codes, etc.), but if you try yourselves from the heart, mindlessly pressing buttons, you can easily lose access to your account. And yet: if you are not ready to experiment, do not touch Gmail; just download the Google Authenticator application to your phone, manually add a “key by time” (for example, “a abc def abc def abc” or simply scan the QR code below).

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



Please note that if two-step authentication is already enabled, the old key cannot be found: 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 digits print str(result)[-6:] 

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

upd: JavaScript implementation example (thanks roman_pro )

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

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 ).