Message authentication: Information theoretic bounds

The goal of message authentication is to ensure that an accepted message truly comes from its acclaimed transmitter. It has wide applications in e-commerce and other areas. For example, when a stock broker receives a trading instruction for an account, he or she needs to verify that it is the owner of the account, and not someone else, who sends the instruction. There are usually three parties involved in message authentication: a transmitter, a receiver, and an opponent. The opponent in authentication is active. It will initiate various attacks in order to mislead the receiver. For example, the opponent can initiate an impersonation attack, in which the opponent sends a fake packet to the receiver directly, hoping that the packet will be accepted by the receiver. The opponent can also initiate a substitution attack. In a substitution attack, the opponent will first intercept the packet transmitted from the source, and then modify the content in the packet. After the modification, the opponent will then forward the modified packet to the receiver. The receiver in a properly designed authentication system should be able to distinguish, with high probability, fake packets or modified packets from true packets coming from the transmitter. Similar to secure transmission, there are two different design approaches for message authentication systems: the computational approach and the information theoretic approach. Computational approach based authentication systems are built on two assumptions: (1) certain mathematics problems are difficult to solve; and (2) the opponent has limited computational power. Hence the security of a computational approach based authentication system essentially relies on the validity of these assumptions. On the other hand, information theoretic based authentication systems do not make these two assumptions. Various coding techniques are employed in information theoretic based systems to ensure the detection of attacks. We will focus on information theoretic based authentication systems in this chapter. To distinguish the source from the opponent, it is assumed that the source and the receiver share a key. Except for the value of the key and source message, the opponent is assumed to be aware of the system design, including the encoding/decoding schemes, etc. There is a relationship between the key size and the success probability¹ of each attack mentioned above. Intuitively, the larger the key size, the more difficult for an attack to be successful, and hence the system is more secure. Of course, one would like to make the success probability of the opponent as small as possible. But it is impossible to design an authentication scheme so that the success probability of the opponent is zero. To see this, consider the following simple attack strategy of the opponent for any authentication scheme: guess the value of the key. If the guess of the key is correct, there is no difference between the opponent and the source. Then, the impersonation attack will be successful, since now the opponent knows the key value and the coding scheme. If the total number of possible key values is |K|, then the probability of a correct guess is 1/|K|. Hence, one important question is, can we design a scheme so that the success probability of the opponent is limited by 1/|K|? This question was first studied by Simmons [1]. As we will discuss in the sequel, Simmonss model assumes that there is no transmission noise. Under this model, Simmons showed that the success probability of the opponent is at least as large as 1/√|K|. This result is pessimistic since the 1/√|K| is typically much larger than 1/|K|. More importantly, this is only a lower bound on the success probability of the opponent. The success probability of the opponents attack could be much larger than this bound. However, physical transmission systems are noisy.Acommonway of dealing with this fact is to use channel coding to convert the noisy channel into a noiseless one, and then to design an authentication code on top of channel coding. Liu and Boncelet [2, 3] also considered the situation in which channel coding is not perfect, and hence, there are some residual errors induced by the channel. The main conclusion of these works is that channel noise is detrimental to authentication, since it will cause the receiver to reject authentic messages from the transmitter. In this chapter, we take an alternative view of the noisy channel model and design channel and authentication coding jointly. This way, we are able to exploit the channel noise to hide the key information from the opponent. The codebook of our channel code is designed such that the conditional distribution of the keys after observing the noisy output at the opponent is very close to a uniform distribution,2 and hence the opponent is unable to use the noisy observations to increase the success probability of a substitution attack. By using this approach, we derive an upperbound on the cheating probability which is significantly smaller than the existing lower bounds for the noiseless channel model. Moreover, this upper-bound is shown to coincide with a simple lower bound on the cheating probability. In particular, we show that the success probability of the opponent is limited by 1/|K|, and thus all the key information can be used to protect against substitution and impersonation attacks simultaneously.We further consider the authentication of multiple messages using the same key K over the noisy channel. Similar to the single-message case, lower and upper bounds on the cheating probability are derived and shown to coincide. Again, all the key information can be used to protect against all the attacks simultaneously. Throughout this chapter, upper-case letters (e.g., X) will denote random variables, lower-case letters (e.g., x) will denote realizations of the corresponding random variables, and calligraphic letters (e.g, X) will denote finite alphabet sets over which corresponding variables range. Also, upper-case boldface letters (e.g., X) will denote random vectors whereas lower-case boldface letters (e.g., x) will denote realizations of the corresponding random vectors. The rest of the chapter is organized as follows. In Sect. 14.2, we review results for authentication over noiseless channel. In Sect. 14.3, we introduce our system model and notation. Section 14.4 is devoted to the single message authentication scenario. Next, we analyze the authentication of multiple message using the same key in Sect. 14.5. Finally, in Sect. 14.6, we offer some concluding remarks.