Using Hashes in Computer Security

September 5, 2013 by

Dawid Czagan

1. Introduction

Hashes are often used in computer security. This article presents how data integrity, authenticated data integrity and non-repudiation can be achieved using hashes. Finally it shows how to build a one-time password system using Lamport hash chain.

Note: See our related article, How does hashing work?

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

2. Hash and HMAC

Let's assume that Alice wants to talk to Bob. Bob wants to be sure that the message he has received is exactly the same as the one sent by Alice. For this, Alice might send the message with its hash (also called a message digest) appended at the end. Hashing is used to achieve data integrity and there isn't a key involved.

The hash of the message M is denoted by H(M). The ideal hash function is irreversible (one can't get the message from the hash) and there aren't two different messages M1 and M2 such that H(M1)=H(M2). MD5 and SHA-1 are exemplary hash functions. The longer the hash, the less probable the occurrence of collision. A collision takes place when the same hash is created for two different messages.

When Bob gets the message from Alice with the appended hash of the message, he calculates the hash of the message and compares it with the appended hash.If they match, Bob can assume that the message was not changed. The problem though is the man-in-the-middle attack. An attacker can grab the message, change it, and append the new hash at the end. That's why the appended hash needs to be authenticated.

Alice and Bob share a key. The HMAC is a hash of the message and the key. Alice calculates HMAC, appends it to the message and sends to Bob. Bob then calculates the HMAC (hash of the message he received and the key he shares with Alice). Then he compares this HMAC with the HMAC appended to the message. When they match, Bob knows that it was Alice who sent this message. If the attacker changed the message and HMAC, it would be detected by Bob since the attacker doesn't know the key. This way, message integrity and authentication can be verified by Bob.

3. Digital signature

Let's continue the story with Alice and Bob. HMAC is used to provide message integrity and authentication. The problem is that HMAC doesn't provide non-repudiation, because Alice and Bob share the key.

Digital signature provides non-repudiation. Alice's private key is used to encrypt the hash of the message. This encrypted hash is called a digital signature. Alice sends the message with an appended digital signature to Bob. Bob uses Alice's public key to decrypt the digital signature. Bob then calculates the hash of the message and compares it with the decrypted digital signature of the message, which is the hash of the message. If these hashes match, Bob knows exactly what message was sent and who sent it.

4. Lamport hash chain

Let's analyze how hashing can be used to build the one-time password system.

The user chooses a password (P) and the number of one-time passwords that he is going to use (N). Let's assume, that N is equal to 3 (for simplicity of the description).

Then the one-time passwords (starting from the first one (P1) to the last one (P3)) are calculated by the user in the following way:

P1=H(H(H(P))) – P is hashed N times (3); the first one-time password (INDEX: 1)

P2=H(H(P)) – P is hashed N-1 times (2); the second one-time password (INDEX: 2)

P3=H(P) – P is hashed once (N-2); the third one-time password (INDEX: 3)

The successive one-time passwords are generated by hashing the password P that is entered by the user. The number of hashing steps is dependent on the INDEX of the one-time password. The value of INDEX is sent to the client by the authentication server (described later in the article). INDEX starts with 1 (for the first one-time password) and is incremented by one for the next one-time passwords (INDEX is 2 for the second one-time password, INDEX is 3 for the third one-time password).

The authentication server is initialized with P0, which is the hash of the first one-time password (H(P1)). That's why P0 is equal to H(H(H(H(P)))). P0 is stored together with the name of the user (USERNAME) and INDEX. At the very beginning INDEX is equal to 1, because the user is supposed to enter the first one-time password (P1).

If the user wants to authenticate, he sends his USERNAME to the authentication server and gets the value of INDEX from the server (which is 1). The user calculates the first one-time password (P1), which is H(H(H(P))) and sends it to the authentication server. The authentication server hashes P1 and compares the result (H(P1)) with P0. When they match, the user is authenticated. Then P0 is replaced with P1 (which is the hash of the second one-time password) and INDEX is incremented by 1. INDEX is equal to 2 at this moment, which means, that the user is supposed to enter the second one-time password (P2) next time.

The user wants to authenticate again. He sends his USERNAME to the authentication server and gets the value of INDEX from the server (which is 2). The user calculates the second one-time password (P2), which is H(H(P)) and sends it to the authentication server. The authentication server hashes P2 and compares the result (H(P2)) with P1.When they match, the user is authenticated. Then P1 is replaced with P2 (which is the hash of the third one-time password) and INDEX is incremented by 1. INDEX is equal to 3 at this moment, which means, that the user is supposed to enter the third one-time password (P3) next time.

The aforementioned steps are executed N times (until all one-time passwords are used). Then the new password P is chosen and the procedure starts from the beginning.

As you see, it is easy to calculate the previous one-time password, which is the hash of the current password. However, this is not a problem, because the previous one-time password is not valid any longer (reply attacks prevented). In addition to this it's impossible to calculate the next one-time password (hash function is irreversible). A single password and hashing were used to generate one-time passwords and there are no secrets stored on both sides of the communication (authentication server and user).

5. Conclusions

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Several applications of hashing were presented in this article. Hashing is used to achieve data integrity. HMAC is an authenticated hash and is used to achieve data integrity and authentication. Digital signature provides non-repudiation and is based on encrypting the hash of the message with the private key. Lamport hash chain is used to build the one-time password system (no secrets stored in the system; reply attacks prevented).