Keywords

1 Introduction

With diverse devices getting connected to internet and communicate with each other (or with central server), it is necessary to have authentication protocols that ensure that the messages received from senders are trustworthy and genuine, and are not altered from intruders of network or jammers or attackers present in the communication channel [1, 2]. In an environment that is prone to attacks, it is very important to establish authenticity of devices in communication system. Shannon’s influential paper on Mathematical Theory of Communication has immensely influenced research in many directions [3]. The problems of achieving reliability and security in digital communication paradigm are addressed separately in literature. To achieve reliability error correcting codes are used rather than redundantly transmitting the same packets until an acknowledgment message is received from receiver. Additional parity bits are added to the message to be transmitted so that errors if any will be corrected by employing suitable decoding techniques. Adding such parity bits are little computationally expensive but provides better throughput over transmitting redundant packets repeatedly which incurs additional overhead. Encoding E can be given as an injective map as follows [4]:

$$\begin{aligned} E: \varSigma ^{k} \rightarrow \varSigma ^{n} \end{aligned}$$
(1)

where, message m of length k is encoded into a message of length n over an alphabet \(\varSigma \). The additional bits r added to message of length k are called parity bits or redundancy bits and \(n = k + r\). Similarly, decoding D can be given as a function as follows [4]:

$$\begin{aligned} D: \varSigma ^{n + \eta } \rightarrow \varSigma ^{k} \end{aligned}$$
(2)

where, \(\eta \) is the noise added by the communication channel.

To achieve security, efficient cryptographic techniques are used which are broadly classified into public key cryptosystem and private key cryptosystem. In public key cryptosystem, sender will possess a public key using which he/she encrypts the message and transmits. User upon receiving the encrypted message uses his/her private key to decrypt the message. In private key cryptosystem, both sender and receiver will agree upon a mutual set of keys that act as key to encrypt and decrypt. Sender using his/her private key, encrypts the message and transmits whereas receiver will use his/her private key to decrypt the message.

Encryption Enc can be given as a mapping from actual message defined over an alphabet to another message defined over different alphabet as follows:

$$\begin{aligned} Enc: \varSigma ^{n} \rightarrow \sigma ^{n} \end{aligned}$$
(3)

where, \(\varSigma \) and \(\sigma \) are the alphabets over which plain text and cipher text are defined respectively. Similarly, decryption Dec is given as a map as \(Dec: \sigma ^{n} \rightarrow ~\varSigma ^{n}\).

In this paper, we propose a multi purpose light weight authentication protocol based on coding theory, i.e., by exploiting the error correction capability of the code. Maurya et al. [5] have used such coding theory based authentication protocol to authenticate Radio-Frequency Identification (RFID) tags with the RFID readers with the help of a trusted server. In our proposed protocol the necessity of such server assistance is removed. This makes the proposed protocol suitable for use in diverse communication scenarios such as Device to Device (D2D), Machine-to-Machine (M2M), Vehicle-to-Vehicle (V2V), Cognitive Radio Networks (CRNs) and Cyber Physical Systems (CPS) that uses error correction codes for achieving reliability. In these communication setup, i.e., Device to Device (D2D), Machine-to-Machine (M2M), Vehicle-to-Vehicle (V2V), both sender and receiver will have almost same capabilities (can be termed broadly as Ubiquitous computing [6]). The protocol is constructed using the techniques of coding theory especially linear error correcting codes that are defined over Field \(\mathbb {F}_{q}^{n} \), pseudo random numbers and Cyclic Redundancy Check functions. General protocol is given in this paper and it can be used with any linear error correcting codes defined over \(\mathbb {F}_{q}^{n}\). Here, the emphasis is on achieving authentication in communication systems exploiting error correction capability of the code employed to achieve reliability. Proposed method is also useful in achieving security in terms of authentication in communication systems that has only physical layer in the communication stack and not the upper layers [1, 7] (in scenarios such as using TV spectrum as opportunistic cognitive radio [8, 9]).

Present paper is organized as follows: In Sect. 2 related works and attack models are discussed. Section 3 discusses the proposed authentication protocol. Analysis of the proposed protocol is made in Sect. 4. Section 5 deals with conclusions and future work.

2 Related Works and Attack Models

2.1 Related Works

To overcome these challenges coding theory and cryptography techniques can be efficiently combined. The idea of employing error correcting codes for authenticating messages were introduced by Gilbert et al. [10]. The mathematical formulation of such schemes and a survey on construction of unconditionally secure authentication schemes from error correcting codes was given by Simmons [11, 12]. There after many authentication schemes were proposed in the literature [13, 14] to achieve security. Kacewicz [15] has analyzed few error correcting codes that are suitable to achieve reliability as well as security in the context of wireless communication systems.

Tsimbalo et al. [16,17,18] have exploited the Cyclic Redundancy Check (CRC) function bits of Bluetooth Low Energy (BLE) and IEEE 802.15.4 standards meant for resource constrained IoT devices intended to detect errors (not for correcting, as error correction or high level encoding involves processing overhead for the resource constrained devices), and proposed Forward Error Correction (FEC) over CRC which was purposefully disabled in those two protocols for saving energy at sender side. Tsimbalo et al. [16] proposed forward error correcting codes over such CRC redundant bits and checked the performance of such codes in communication paradigms where receiver can process received codewords from constrained devices and employ decoding to correct errors instead of discarding received packets and requesting sender to resend discarded packets.

Ez-zazi et al. [19] have proposed coding based reliable communication scheme for constrained IoT devices. The scheme uses Low Density Parity Check codes and CRC to achieve reliability. Sender will encode data sensed using LDPC codes and CRC of encoded data is computed, such encoding and CRC computation is termed as joint FEC/CRC by authors. Such encoded data is transmitted to the next hop or base station, upon receiving the joint FEC/CRC encoded package, first CRC will be checked to find if there are any errors in the received packets, if not it will be transmitted further. If any errors are detected by CRC, then the received packet will be decoded using belief propagation technique of decoding LDPC codes and errors will be corrected. If such packet’s error correction is performed at intermediate hops, then the message will be further encoded using LDPC scheme and further CRC is computed before transmitting it further.

Alabady et al. [20] have proposed novel Low Complexity Parity Check (LCPC) codes for the resource constrained IoT devices. The proposed scheme encodes the data using LCPC codes at sender and uses three stage decoding algorithm to correct up to two bit errors if any and decode the message. This scheme corrects only one bit and two bit errors and beyond that discards the received packet and request the sender to retransmit the discarded packet.

2.2 Attack Models

The common attacks both cryptographic and coding theory methods used to achieve reliability and security subjected to are - eavesdropping, Denial-of-Service attacks, intrusion attacks, man-in-the-middle attacks, replay kind of attacks. By combining or selectively using techniques from coding theory as well as cryptography, attacks such as intruder, Man-in-the-Middle, replay and Denial-of-Service can be effectively mitigated.

Intrusion Attack. In intrusion attack, the adversaries will join the network or the group of existing communication entities posing as legitimate user and then use the network resources or information similar to legitimate users or sometimes even dominating legitimate users. Mitigating or overcoming or detecting such intrusion is necessary to make network resources available only for legitimate users.

Man-in-the-Middle Attack. Communication between sender and receiver is through a channel that is subjected to noise and attacks. Additive White Gaussian Noise (AWGN) is considered in the channel that changes bits and the channel is assumed to be insecure. Any intruder posing as legitimate user can send messages to receiver and thwart communication. Identifying the source of received message at receiver is an important task to mitigate such attack.

Replay Attack. The communication between sender and receiver can be copied (copying session keys) and used at later instances. Such attacks should be avoided in real time communication systems so that entities will not function adversely.

Denial-of-Service Attack. Denial-of-Service attack will make legitimate users deprive of services. One instance of it is to use powerful signal and entirely change the routing of packets in the network to other unintended nodes than to legitimate receiver present in the network. Also, making the receiver deprive of legitimate data over network is an instance of Denial-of-Service attack.

3 Authentication Protocol

The proposed protocol works in two phases, namely, initialization phase and execution phase. Initialization phase involves setting up of the environment necessary for execution of the protocol. Notations used in the protocol are given in Table 1.

Table 1. Notations
Full size table

3.1 Assumptions

The following assumptions are made in defining the protocol.

  1. 1.

    \([n, k, d]_{q}\) error correcting code is assumed, where n is the length of the codeword, k is the information to be encoded, d is the minimum Hamming distance and q is the alphabet over which code is defined [21]. The error correcting code \(\mathbb {C}\) is assumed to have \(2^{k}\) distinct codewords.

  2. 2.

    It is assumed that the random number generated at the sender \(R_{s}\) is such that \(wt(Rs) \le t\), where t is the error correction capacity of the code. It is to ensure that the errors that occur in this can only be corrected (Hamming bound).

  3. 3.

    The length of pseudo random numbers \(R_{s}\) and \(R_{r}\) are assumed to be n, which is same as the length of the codeword \(c \in \mathbb {C}\).

3.2 Initialization Phase

In the initialization phase, both sender and receiver will compute functions that are necessary for the working of the protocol. Both sender and receiver will share a secret key K, also called as shared secret key. Both sender and receiver will have respective pseudo random number generators that can generate pseudo random numbers indicated by \(R_{s}\) and \(R_{r}\) respectively. But the pseudo random generator at the sender can generate random number which satisfies the condition that \(wt(R_{s}) \le t\). Both sender and receiver will have their respective Cyclic Redundancy Check (CRC) functions that computes the CRC sums for the inputs provided. The encoder function of sender will encode message m of length k into codeword c of length n.

3.3 Execution Phase

Both sender and receiver will compute \(S_{s}\) and \(S_{r}\) respectively by XOR-ing random number generated with the shared secret key K. \(S_{s} = R_{s} \oplus K\) and \(S_{r} = R_{r} \oplus K\). Both sender and receiver will exchange \(S_{s}\) and \(S_{r}\). At receiver, random number of sender \(R_{s}\) will be computed by XOR-ing the received \(S_{s}\) values with the shared secret key K, i.e., \(R_{s} = S_{s} \oplus K\). Similarly, sender will compute \(R_{r} = S_{r} \oplus K\) to get \(R_{r}\). Thus, both sender and receiver will get \(R_{r}\) and \(R_{s}\) respectively without being explicitly sharing it.

Sender will concatenate the codeword \(c_{i}\) to be transmitted with the random number generated by both sender and receiver and compute CRC sum of the concatenated message, i.e., \(CRC(c_{i}||R_{s}||R_{r})\). Also, the sender will compute \(c_{i} \oplus R_{s}\). Sender will transmit both \(CRC(c_{i}||R_{s}||R_{r})\) and \(c_{i} \oplus R_{s}\) to the receiver. Let \(E_{1}\) = \(CRC(c_{i}||R_{s}||R_{r})\) and \(E_{2}\) = \(c_{i} \oplus R_{s}\). \(E_{2}\) will be similar to codeword.

Fig. 1.
figure 1

Proposed authentication protocol

Full size image

Receiver will receive messages \(E_{1}\) and \(E_{2}\) from the sender. It will decode the received message \(E_{2}\) employing Maximum Likelihood decoding as \(R_{s} \le t\) and produce codeword \(c_{i}'\). Further, the receiver will compute \(E_{3}\) such that \(E_{3}\) = \(CRC(c_{i}'||R_{s}||R_{r})\). If \(E_{1}\) computed at sender is equivalent to \(E_{3}\) computed at receiver, i.e., \(E_{1} = E_{3}\) then the communication is authentic and it is sent from genuine sender, if not, i.e., \(E_{1} \ne E_{3}\) then message is being received from other sources than the intended sender. \(E_{1}\) can be shared with the receiver as private key similar to that of Private Key Cryptosystem. Overview of the proposed Authentication protocol is given in Fig. 1.

4 Analysis of Proposed Authentication Protocol

4.1 Replay Attack

Adversary or intruder of the channel tries to send the same session details in a future instance to communicate with the receiver. But in the proposed protocol even if shared secret key K is known to the intruder, it is difficult to guess the random numbers \(R_{r}\) and \(R_{s}\) generated at receiver and sender respectively, as they will be generated for each session. CRC computed at both sender as well as at receiver further makes it difficult even if intruder knows either \(R_{s}\) or \(R_{r}\) as they will be freshly generated.

4.2 Impersonation Attack

If intruder stores \(E_{2}\) and tries to use it in future instance proposed protocol will reject it as values of \(R_{r}\) and \(R_{s}\) will be generated for sessions or as and when required. Further, CRC will be computed at both sender and receiver. That makes it difficult for intruders to impersonate the sessions. Even though \(E_{2}\) look like codeword it will be XOR-ed with \(R_{s}\) thus impersonating codeword is also difficult.

4.3 Man-in-the-Middle Attack

Intruder in the channel can alter the message \(E_{2}\) in the channel and transmit. But due to the nature of generating \(S_{s}\), \(S_{r}\), \(E_{2}\) and \(E_{1}\) it will be easy to detect unauthenticated transmissions received and reject them.

4.4 Computation Cost

Three \(\oplus \) – operations are performed at sender to compute \(S_{s}\), \(R_{r}\) and \(E_{1}\). Similarly, two \(\oplus \) – operations are performed at receiver to compute \(S_{r}\) and \(R_{s}\) respectively. One time CRC operation is performed at sender as well as receiver. Both sender and receiver will perform two || operation. If computation time to perform \(\oplus \) operation is indicated by \(T_{\oplus }\), CRC operation by \(T_{CRC}\) and || operation by \(T_{||}\), then computation time taken at the sender to implement the proposed protocol is 3\(T_{\oplus }\) + 2\(T_{||}\) + 1\(T_{CRC}\). This computation is in addition to the computation time required at the sender to compute codeword \(c \in \mathbb {C}\). Similarly at the receiver it takes a total of 2\(T_{\oplus }\) + 2\(T_{||}\) + 1\(T_{CRC}\) to implement the proposed protocol in addition to the cost involved at receiver to decode the received codeword \(c'\) using Maximum Likelihood Decoder.

5 Conclusion

A simple authentication protocol is proposed in this paper based on linear error correcting codes, pseudo random number generators and CRC function. The proposed protocol provides resistance against replay attack, impersonation attack and man-in-the-middle kind of attacks. The protocol can also be employed in any communication setups that uses linear error correcting codes (to achieve reliability) as discussed in paper to achieve security in terms of authentication. Further, it is interesting to incorporate this protocol in real time systems and analyze its performance.