Computer and Communication Networks (paperback)

10.5. Authentication

Authentication techniques are used to verify identity. Message authentication verifies the authenticity of both the message content and the message sender. Message content is authenticated through implementation of a hash function and encryption of the resulting message digest. The sender's authenticity can be implemented by use of a digital signature.

A common technique for authenticating a message is to implement a hash function , which is used to produce a " fingerprint " of a message. The hash value is added at the end of message before transmission. The receiver recomputes the hash value from the received message and compares it to the received hash value. If the two hash values are the same, the message was not altered during transmission. Once a hash function is applied on a message, m , the result is known as a message digest, or h(m) . The hash function has the following properties.

• Unlike the encryption algorithm, the authentication algorithm is not required to be reversible.

• Given a message digest h(m) , it is computationally infeasible to find m .

• It is computationally infeasible to find two different messages m ₁ and m ₂ such that h(m ₁ ) = h(m ₂ ).

Message authentication can be implemented by two methods . In the first method, as shown in Figure 10.5 (a), a hash function is applied on a message, and then a process of encryption is implemented. Thus, a message digest can also be encrypted in this method. At this stage, the encryption can be a public key or a secret key. The authenticity of a message in this method is assured only if the sender and the receiver share the encryption key. At the receiver site, the receiving user 2 has to decrypt the received message digest and compare it with the one made locally at its site for any judgments on the integrity of the message.

In the second method, as shown in Figure 10.5 (b), no encryption is involved in the process of message authentication. This method assumes that the two parties share a secret key. Hence, at the receiving site, the comparison is made between the received h(m) and the message digest made locally from the received message. This technique is more popular in the security infrastructure of the Internet Protocol. Among the message authentication protocols are the MD5 hash algorithm and the Secure Hash Algorithm (SHA). SHA is the focus of our discussion.

10.5.1. Secure Hash Algorithm (SHA)

The Secure Hash Algorithm (SHA) was proposed as part of the digital signature standard. SHA-1, the first version of this standard, takes messages with a maximum length of 2 ²⁴ and produces a 160-bit digest. With this algorithm, SHA-1 uses five registers, R ₁ through R ₅ , to maintain a "state" of 20 bytes.

The first step is to pad a message m with length l _m . The message length is forced to l _m = 448 mod 512. In other words, the length of the padded message becomes 64 bits less than the multiple of 512 bits. The number of padding bits can be as low as 1 bit and as high as 512 bits. The padding includes a 1 bit and as many 0 bits as required. Therefore, the least-significant 64 bits of the message length are appended to convert the padded message to a word with a multiple of 512 bits.

After padding, the second step is to expand each block of 512-bit (16 32 bits) words {m , m ₁ , ..., m ₁₅ } to words of 80 32 bits using:

Equation 10.12

and

Equation 10.13

where j means left rotation by j bits. This way, bits are shifted several times if the incoming block is mixed with the state. Next, bits from each block of w _i are mixed into the state in four steps, each maintaining 20 rounds. For any values of a , b , and c , and bit number i , we define a function F _i (a , b , c ) as follows :

Equation 10.14

Then, the 80 steps ( i = 0, 1, 2, ..., 79) of the four rounds are described as follows:

Equation 10.15

Equation 10.16

Equation 10.17

Equation 10.18

Equation 10.19

Equation 10.20

where C _i is a constant value specified by the standard for round i . The message digest is produced by concatenation of the values in R ₁ through R ₅ .