Message Authentication Functions

Any message authentication or digital signature mechanism has two levels of functionality.At the lower level, there must be some sort of function that produces an authenticator: a value to be used to authenticate a message. This lower-level function is then used as a primitive in a higher-level authentication protocol that enables a receiver to verify the authenticity of a message.

This section is concerned with the types of functions that may be used to produce an authenticator. These may be grouped into three classes.

■ Hash function: A function that maps a message of any length into a fixed-length hash value, which serves as the authenticator

■ Message encryption: The ciphertext of the entire message serves as its authenticator

■Message authentication code (MAC): A function of the message and a secret key that produces a fixed-length value that serves as the authenticator

Message Encryption

Message encryption by itself can provide a measure of authentication. The analysis differs for symmetric and public-key encryption schemes.

SYMMETRIC ENCRYPTION 

Consider the straightforward use of symmetric encryption (Figure 12.1a). A message $M$ transmitted from source $A$ to destination $B$ is encrypted using a secret key $K$ shared by $A$ and $B$. If no other party knows the key, then confidentiality is provided: No other party can recover the plaintext of the message.

In addition, $B$ is assured that the message was generated by $A$. Why? The message must have come from $A$, because $A$ is the only other party that possesses $K$ and therefore the only other party with the information necessary to construct ciphertext that can be decrypted with $K$. Furthermore, if $M$ is recovered, $B$ knows that none of the bits of $M$ have been altered, because an opponent that does not know $K$ would not know how to alter bits in the ciphertext to produce the desired changes in the plaintext.

So we may say that symmetric encryption provides authentication as well as confidentiality. However, this flat statement needs to be qualified. Consider exactly what is happening at $B.$ Given a decryption function $D$ and a secret key $K$, the destination will accept any input $X$ and produce output $Y = D(K, X)$. If $X$ is the ciphertext of a legitimate message $M$ produced by the corresponding encryption function, then $Y$ is some plaintext message $M$. Otherwise, $Y$ will likely be a meaningless sequence of bits. There may need to be some automated means of determining at $B$ whether $Y$ is legitimate plaintext and therefore must have come from $A$.

Suppose the message $M$ can be any arbitrary bit pattern. In that case, there is no way to determine automatically, at the destination, whether an incoming message is the ciphertext of a legitimate message.This conclusion is incontrovertible: If $M$ can be any bit pattern, then regardless of  the value of $X$, the value $Y = D(K, X)$ is some bit pattern and therefore must be accepted as authentic plaintext.

It may be difficult to determine automatically if incoming ciphertext decrypts to intelligible plaintext. If the plaintext is, say, a binary object file or digitized X-rays, determination of properly formed and therefore authentic plaintext may be difficult. Thus, an opponent could achieve a certain level of disruption simply by issuing messages with random content purporting to come from a legitimate user.

One solution to this problem is to force the plaintext to have some structure that is easily recognized but that cannot be replicated without recourse to the encryption function. We could, for example, append an error-detecting code, also known as a frame check sequence (FCS) or checksum, to each message before encryption, as illustrated in Figure 12.2a. $A$ prepares a plaintext message $M$ and then provides this as input to a function $F$ that produces an FCS. The FCS is appended to $M$ and the entire block is then encrypted. At the destination, $B$ decrypts the incoming block and treats the results as a message with an appended FCS. $B$ applies the same function $F$ to attempt to reproduce the FCS. If the calculated FCS is equal to the incoming FCS, then the message is considered authentic. It is unlikely that any random sequence of bits would exhibit the desired relationship.

Note that the order in which the FCS and encryption functions are performed is critical. The sequence illustrated in Figure 12.2a is referred as internal error control, which the authors contrast with external error control (Figure 12.2b). With internal error control, authentication is provided because an opponent would have difficulty generating ciphertext that, when decrypted, would have valid error control bits. If instead the FCS is the outer code, an opponent can construct messages with valid error-control codes. Although the opponent cannot know what the decrypted plaintext will be, he or she can still hope to create confusion and disrupt operations.

PUBLIC-KEY ENCRYPTION 

The straightforward use of public-key encryption (Figure 12.1b) provides confidentiality but not authentication. The source ($A$) uses the public key $PU_b$ of the destination ($B$) to encrypt $M$. Because only $B$ has the corresponding private key $PR_b$, only $B$ can decrypt the message. This scheme provides no authentication, because any opponent could also use $B$’s public key to encrypt a message and claim to be $A$.

To provide authentication, $A$ uses its private key to encrypt the message, and $B$ uses $A$’s public key to decrypt (Figure 12.1c). This provides authentication using the same type of reasoning as in the symmetric encryption case: The message must have come from $A$ because $A$ is the only party that possesses $PR_a$ and therefore the only party with the information necessary to construct ciphertext that can be decrypted with $PU_a$. Again, the same reasoning as before applies: There must be some internal structure to the plaintext so that the receiver can distinguish between well-formed plaintext and random bits.

Assuming there is such structure, then the scheme of Figure 12.1c does provide authentication. It also provides what is known as digital signature.Only $A$ could have constructed the ciphertext because only $A$ possesses $PR_a$. Not even $B$, the recipient, could have constructed the ciphertext. Therefore, if $B$ is in possession of the ciphertext, $B$ has the means to prove that the message must have come from $A$. In effect, $A$ has “signed” the message by using its private key to encrypt. Note that this scheme does not provide confidentiality. Anyone in possession of $A$’s public key can decrypt the ciphertext.

To provide both confidentiality and authentication, $A$ can encrypt $M$ first using its private key, which provides the digital signature, and then using $B$’s public key, which provides confidentiality (Figure 12.1d). The disadvantage of this approach is that the public-key algorithm, which is complex, must be exercised four times rather than two in each communication.

Note: we will discuss Hash Functions and MAC later.