UC Secure Network Coding Against Pollution Attacks

Considering the pollution attacks in network coding, in the single-source multi-sinks directed acyclic network, we present a Universally Composable (UC) secure random network coding scheme based on All-Or-Nothing Transform (AONT) encryption and homomorphic Network Coding Signature (NCS₁). At the source node, by means of AONT encryption an eavesdropper is unable to get any meaningful information no matter how many channels are wiretapped. To prevent malicious modification of data packets, in this study, we adopt the signature scheme NCS₁ for authentication the integrity of the transmitted data and the node identity. Lastly, we have proved the novel scheme is secure in the UC security model. By the security proof and comprehensive analysis, it is showed that the proposed scheme not only has the ability of resistance eavesdropper and the Byzantine attacker but also achieves the maximum flow of information transmission.

INTRODUCTION

Network coding has been proven to maximize network throughput (Ahlswede et al., 2000) by mixing the received information before forwarding them to the next nodes, however, network coding is vulnerable to pollution attacks by malicious nodes in the network. Once a packet is corrupted, a single error further will cause pollution of downstream nodes like the plague spread on the network. Thus, even a faulty transmission on a single edge will eventually cause almost all messages being forwarded in the network to be incorrect and will thus prevent reconstruction of even a portion of the messages.

The algorithms of detecting misbehaved wireless nodes have been described by Raja et al. (2008) and Jun and Wei-Hua (2010). Some network error correcting algorithms (Cai and Yeung, 2002; Zhang, 2008; Wei et al., 2011) based on different techniques have been proposed. Zhou et al. (2010) have designed a network coded non-orthogonal Interleave-division Multiple-access (IDMA) cooperation system. The design of secure network coding is mainly against two types of pollution attacks, including wiretapping attacks (passive attacks) (Meng, 2011) and Byzantine attacks (active attacks) (Lamport et al., 1982; Wang et al., 2003; Yan and Wang, 2004; Meng, 2011). A Byzantine attacker is a malicious adversary hidden in a network, capable of intercepting, tampering or inserting packets in the original information flow. We have surveyed some techniques for combating data pollution when network coding is used. The literatures (Silva and Kschischang, 2008; Chanl and Grant, 2008; Zhou et al., 2009) studied different encoding methods for preventing eavesdropping attackers. Ho et al. (2004) have proposed a Byzantine attack detection model that based on the attacker did not know the random coding coefficients. The first efficient scheme to design and implement error-correction against Byzantine adversaries has been used in the distributed network coding setting (Jaggi et al., 2008). It should be noted that in these papers, the adversary model is based on the threshold number of communication links that could be controlled by the adversary. Yu et al. (2008) have designed a RSA homomorphic signature scheme for network coding against pollution attacks but it is pointed out in a recent paper (Gennaro et al., 2010), that this protocol is incorrect indeed. Agrawal and Boneh (2009) have proposed a homomorphic MAC mechanism but only at the receiving node could detect malicious packets; intermediate nodes could not detect them. RIPPLE mechanism (Li et al., 2010) has been designed to prevent pollution attacks. Recently, Wang (2010) shows that there are serious flaws in these schemes (Jaggi et al., 2008; Yu et al., 2008; Agrawal and Boneh, 2009; Gennaro et al., 2010; Li et al., 2010).

Our previous study (Feng et al., 2011) have presented a security random network coding model against Byzantine attack based on CBC (Hayat et al., 2004; Zaidan et al., 2010). In the model, the source adopts CBC packet encryption, intermediate nodes use ElGamal signature scheme. However, the security of the scheme is also dependent on limiting the numbers of eavesdropping links and this signature technology can not be combined at downstream nodes. To solve the problems, this study proposes a UC secure network coding model in view of the single-source multi-sinks directed acyclic network. We adopt AONT encryption instead of previous CBC encryption, no matter how many channels are wiretapped; the attacker can not get any meaningful information of the source messages. In order to ensure the participation of legitimate nodes, the source and intermediate nodes sign encoded message based on homomorphic signature scheme NCS₁ by Boneh et al. (2009), intermediate nodes and sinks can verify the integrity and legitimacy of the received information. NCS₁ signature scheme has the advantage that signatures can be associated with individual vectors rather than an entire subspace. Both the public key and per-vector signatures in this scheme have constant size, making the scheme ideally suited for network coding. This scheme also supports the transmission of streaming data, in the sense that the sender need not be aware of the entire file before computing the signature first packet. The novel approach to solve the problem of concurrent network coding against pollution attack within the framework of Universally Composable (UC) security is described by Meng (2011). The most outstanding nature of UC framework is its modular design concept: may alone design a protocol, so long as the protocol satisfies the UC security, it can be guaranteed secure while running concurrently with other protocols. By the security proof and comprehensive analysis, it is showed that the proposed scheme has greatly improved security and efficiency compared to the previous schemes.

PRELIMINARIES

Encoding kernel: The pair G = (V_G, E_G) is called a single-source acyclic network, where V_G and E_G are the node set and the edge set. The node SεV_G called the source node, T = {t₁, t₂, …t_m} called the sink set. For every node v, let In(v) denote the set of incoming channels to v and Out(v) the set of outgoing channels from v. Meanwhile, let S’ denote an imaginary source at the upstream of S.

Local description of a linear network code on an acyclic network: Let F be a finite field and ω a positive integer. An ω-dimensional F-valued linear network code on an acyclic communication network consists of a scalar k_d,e, called the local encoding kernel, for every adjacent pair (d, e). Meanwhile, the local encoding kernel at the node v means: the |In(v)|x|Out(v)| matrix K_v = [k_d,e]_{dε In(v),eε Out(v)}.

Global description of a linear network code on an acyclic network: Let F be a finite field and ω a positive integer. An ω-dimensional F-valued linear network code on an acyclic communication network consists of a scalar k_d,e for every adjacent pair (d, e) in the network as well as an ω-dimensional column vector f_e for every channel e such that:

•	, where, eε Out(v)

Let the source generate a message x in the form of an ω-dimensional row vector. A node v receives the symbols x.f_d, dεIn(v), from which it calculates the symbol x.f_e for sending onto each channel eεOut(v) via the linear Eq. 1:

(1)

UC framework: Universally composable security (UC security) is a kind of computational complexity model which was proposed by Canetti (2001) to represent and analyze cryptographic protocols under concurrent circumstances. The framework provides a rigorous method for defining the security of cryptographic tasks. A protocol is represented as a system of probabilistic Interactive Turing Machines (ITMs), where each ITM represents the program to be run within a different party. Adversarial entities are also modeled as ITMs. An additional adversarial entity called the environment Z is introduced. This environment generates the inputs to all parties, reads all outputs and in addition interacts with the adversary in an arbitrary way throughout the computation.

The real-life model: A probabilistic polynomial-time adversary. A participates in a run of the interactive protocol π with a set of parties P₁, …, P_l. All parties are connected through point-to-point communication channels. The channels are public; the adversary can read all data transmitted between parties. The adversary is also responsible for delivery of messages. Each party is initially honest and follows the predetermined program of π. The adversary may corrupt parties, either at the outset only (non-adaptive or static adversaries) or at any point during the execution (adaptive adversaries). Once a party is corrupted by A, the party hands over all internal data including its input, previous incoming and outgoing communication and the content of the random tape to the adversary. If a party becomes corrupted by the adversary, the party follows the adversary’s instructions from then on. Let REAL_π,A,Z denote the output of environment Z when interacting with adversary A and parties running protocol π.

The ideal process: A probabilistic polynomial-time adversary S (also called simulator) participates in an execution of (dummy) parties P₁’,…,P_l’ with some ideal and trustworthy functionality F. All parties are only connected to the functionality by secure channels and the simulator can not read the content of transmissions. Once an honest dummy party receives some input, it immediately forwards this input to the functionality, at some point which may reply with output for some parties (including the simulator S). Corruptions are dealt with as in the real-life setting. Let IDEAL_F,S,Z denote the output of environment Z after interacting in the ideal process with adversary S and ideal functionality F.

In both settings an interactive distinguisher, the probabilistic polynomial-time environment Z, is present. This environment can interact with honest parties by determining the inputs and reading the output of these parties. Additionally, Z can communicate with the adversary A or S, respectively.

We say that a protocol π UC realizes an ideal functionality F if for any real-life adversary A there exists an ideal-process adversary S such that no environment Z, on any input, can tell with non-negligible probability whether it is interacting with A and parties running π in the real-life process or with S and F in the ideal process. We have the following:

Definition 1: Let lεL. Let F be an ideal functionality and let π be an l-party protocol. We say that π securely realizes F if for any adversary A there exists an ideal-process adversary S such that for any environment Z, we define Eq. 2 as follows:

(2)

The hybrid model. In order to state the composition theorem and in particular in order to formalize the notion of a real-life protocol with access to an ideal functionality, the hybrid model of computation with access to an ideal functionality F is formulated. The parties of this model may send messages to and receive messages from an unbounded number of copies of F. Each copy of F is identified via a unique session identifier (sid); all messages addressed to this copy and all message sent by this copy carry the corresponding sid. (The sids are chosen by the protocol run by the parties).

SECURE NETWORK CODING SCHEME

In this study, we present a UC secure network coding scheme in view of single-source multi-sinks directed acyclic network. The source messages are divided into m+1 packets, every packet has the same message length. Assume that the network maximum transmission rate is m+1 and each link throughput is 1. We obtain new m+1 packets by AONT encryption. Furthermore, the source node transforms into m augmented vectors x₁, x₂…, x_m. Finally, the source makes initial sub-signatures for x₁, x₂…, x_m based on the signature mechanism NCS₁ and sends them to participate in encoding at the downstream nodes. The (m+1)th packet is sent directly to the sinks by a shared secret channel between the source and every sink rather than participate in encoding. The intermediate nodes combine and encode the received information and sign the encoded message based on signature mechanism NCS₁, after that, the intermediate nodes and sinks can verify the receiving information, thereby effectively prevent pollution caused by the attacker and ultimately the sinks can decode and decrypt correctly.

The all-or-nothing transform: Rivest (1997) presented a model of encryption for block ciphers which is called All-Or-Nothing Transform (AONT). AONT is defined for information-theoretic security (Stinson, 2001).

Definition 2: Let F_q be a finite field and Fⁿ_q be an n-dimensional space over F_q. Suppose that Φ:Fⁿ_q→Fⁿ_q, Φ is named as an (n, q)-AONT if Φ satisfies the following properties:

•	If any m of the m+1 output values is fixed, then the value of any input value wi (1≤I≤ m+1) is completely undetermined

NCS₁ signature scheme: The signature scheme operates over a bilinear group tuple ξ = (G₁, G₂, G_T, q, e, Φ) with the following properties:

Given a security parameter 1^k and a positive integer N, N-m = n, do:

•	Generate a bilinear group tuple ξ = (G1, G2, GT, q, e,φ), such that q>2k, where k is the security parameter of the system. Generate N-m random numbers g1,…,gnεG1\{1}, Choose a generator

•	Choose and set u=hα, hence

In the following section, We will discuss in detail how NCS₁ signature is applied to the network coding.

NETWORK CODING SCHEME

Source node: In the finite field F_q, we construct a linear ANOT according to the literature (Rivest, 1997), such that Φ(w) = wM^-1 ,where M is an invertible (m+1)-by-(m+1) matrix, function Φ is a linear ANOT. As in definition 2, a file to be transmitted is viewed as an ordered sequence of (m+1)-dimensional vectors w₁,w₂…,w_m,w_m+1εFⁿ_q. In another word, individual vectors refer to as packets, each w_i consists of n elements from F_q. If the source messages have not enough length, the source node pads the messages with corresponding 0 elements. Through the AONT encryption, we get the new ciphertext as .The transformation is defined by Eq. 3:

(3)

Let q = p^k, where p is prime and k is a positive integer. Let λεF_q be such that λ∉{m mod p, m-1 mod p}(this can be done since q>2). We can define γ = (m-λ)^-1, define M to be the following symmetric matrix by Eq. 4:

(4)

It is straightforward to verify that M is invertible; indeed, M^-1 is indicated by Eq. 5:

(5)

Next, we start to encode the first packets Fⁿ_qxF^m_q→F_q^n+m to the input information ₁εFⁿ_q and some randomly chosen rεF^m_q. According to the AONT properties, the attacker is unable to get any meaningful information about source even if eavesdropping all of the m coding channel. The source node pads the messages with the mxm identity matrix I by Eq. 6:

(6)

where, N = n+m and the m augmented vectors x₁, x₂,…, x_m are given by Eq. 7:

(7)

that is, each original vector is appended with the vector of length m containing a single ‘1’ in the ith position. The source makes initial sub-signature σ_i for x_i (1≤i≤m), respectively based on the signature mechanism NCS₁ as follows.

Source sub-signatures (SK, id, v) the source selects randomly a private key SK:= αεF_q, given an identifier idε{0,1}^k, the source computes signature σ_i on vector x_i = (x_i,1,…, x_{i, N})εF^N_q by Eq. 8:

(8)

Intermediate nodes: First verify the signatures on the received signed packets, then produce linear combinations of the verified packets and compute a signature for the encoded packet using the received signatures without the need to access the private keys.

At this point, the combining process has to check if all input packets that contain a signature for an x_i contain the same value of σ_i. If not, the combining process fails and an adversary is recognized. Setting y is the encoded payload and y is defined by Eq. 9:

(9)

β_i = (β_i,1,…, β_i,m) is the corresponding randomly chosen global encoding kernel. All intermediate nodes in the network to sign and verify received packets as follows:

•	Combine(PK, id, : Given a public key PK, an identifier id and {(βi, σi)}Ii = I with βiεFq, this algorithm outputs:

(10)

(11)

(12)

If Υ₁ (PK, σ) = Υ₂ (PK, id, y), this algorithm outputs 1; otherwise it outputs 0.

Sink node: The sinks receive the former level transmitted message and verify the signature as the above method. The verified message can be ultimately decoded and decrypted. If t_iεT, the sink t_i final received message is message Y that has a valid signature. Let A_m be system transfer matrix of input vector X and the output vector Y, where Y=A_m. X given by Eq. 13:

(13)

If the sink t_i receives correct information from at least m incoming channels and global encoding kernel of the m incoming channels are linearly independent, only in this way can t_i recovery source information. Koetter R (Koetter and Medard, 2003) has proved a coding scheme to be secure, as long as the system transfer matrix A_m=A(I-F)^-1B^T is full rank, the destination can decode correctly and output X = A_m^-1.Y. The vector X is column vector and we write X^T to denote the corresponding row vector, that is X^T = (x₁,..,x_m),obviously we can obtain , then we have where, has been transmitted through a secret channel. Finally, we will obtain source original information by AONT inverse transformation matrix M. The process can be described by Eq. 14:

(14)

PROOF SECURITY OF CODING SCHEME

Our protocols are based on the following cryptographic assumptions. Adversaries can adaptively corrupt as many parties as they wish. The protocol is secure against adaptive adversaries in the so-called non-erasing model, where the parties are not allowed to erase any information. Our protocols need UC security even in non-erasing model.

Construction of UC secure network coding protocol: In this section, we formulate a universally composable network coding scheme π_coding in (F_CPKE, F_sig )-hybrid model. Here, F_CPKE is the encryption ideal functionality and F_sig is the signature ideal functionality. In the following graphs, the definition of function Φ, matrix M, M^-1, y and Y as above. We start by presenting F_CPKE and F_sig. Next we present the real protocol π_coding. According to the UC secure framework (Canetti, 2004), we modify the definition of F_CPKE (Canetti and Herzog, 2006), as indicated in Fig. 1.

Fig. 1:	The certified public-key encryption functionality

Fig. 2:	The functionality of network coding signature

According to the UC secure framework, we modify the definition of F_sig (Canetti, 2001) as indicated in Fig. 2. In Fig. 2, ZS denotes sub-signature function and C combination function.

Note that all our functionalities receive initially a session id sid=(P, sid’) where P is the set of players who participate in realizing the functionality and sid’ is a number identifying this particular instance of the functionality. Next we present the real protocol π_coding in Fig. 3.

Construction of network coding against pollution attacks ideal functionality F_coding: In this section, we present our formulation of an ideal functionality for network coding against pollution attacks in the UC framework. An exact definition of the ideal functionality, denoted F_coding, appears in Fig. 4.

SECURITY PROOF OF π_CODING

Theorem 1: Protocol π_coding securely realizes F_coding in the (F_CPKE, F_sig )-hybrid model.

Proof: Let A be an adaptive adversary that interacts with the parties running π_coding in the (F_CPKE, F_sig )-hybrid model.

Fig. 3:	The protocol πcoding

We construct an ideal adversary S such that any environment Z can not distinguish with a non-negligible probability whether it is interacting with A and π_coding in the (F_CPKE, F_sig )-hybrid model (denoted REAL_{UC-coding,A,Z}) or it is interacting with S and F_coding in the ideal world (denoted IDEAL_Fcoding,S,Z).

Construction of the adversary S: The adversary S shown below runs a simulated copy of the adversary A, thus S is often called a simulator. Any input from Z is forwarded to A and any output of A is copied to the output of S.

Simulating the sender: When an uncorrupted party P is activated with input (Encrypt,sid,w_i), S obtains this value from F_coding and simulates for A the protocol π_coding.

Whenever, S obtains (Encrypt,sid,w_i) from F_CPKE, S sends the message (Encrypt,sid,w_i) to A with sid = (P, sid’), then forwards the response x_i (1≤i≤m+1)from A to F_sig.

Whenever, S receives a message (KenGen,sid) from F_sig, S sends to A the message (KenGen,sid) with sid = (P, sid’), then forwards the response (Verification key, sid, ZS, C, V) from A to F_sig.

Whenever, S receives a message (Sign, sid, x_i) from F_sig, S sends (Sign,sid,x_i) to A, then forwards the response (signature, sid, x_i, σ_i) from A to F_sig.

Fig. 4:	Secure network coding ideal functionality

Simulating the intermediate nodes: Whenever S receives a message (Encoding,Combine,x₁,σ₁,...,x_m,σ_m) from F_sig, S sends (Encoding,Combine,x₁,σ₁,...,x_m,σ_m) to A, then forwards the response(y,σ,C) from A to F_sig.

Simulating the recipients: When A delivers a message (y,σ,C) to an uncorrupted party t, S simulates for A the protocol π_coding.

Whenever, S receives a message (Verify,sid,y’,σ,V) from F_sig, S sends (Verify,sid,y’,σ,V) to A, where a sink receives a encoded message y’ at a previous level, then forwards the response (Verified,sid, y’, f) from A to F_sig.

If F_CPKE receives (Verify,sid, y’,σ,V,f=1) from F_sig, then records (x,V) and sends (y,σ,C) to t. Otherwise, do nothing.

If t receives (Decrypt, sid, _i) from F_CPKE, if there is a recorded pair (w_i, _i) then hands w_i to t. Otherwise, computes w_i = D(_i) and hands w_i (1≤i≤m+1) to t.

Simulating party corruption: Whenever, a corrupts a party, S corrupts the same party and provides A with the internal state of the corrupted party. Whenever a corrupted party P receives (Encrypt, sid, w_i), S obtains x_i from F_coding and simulates for A only the interaction with F_sig and F_CPKE. Whenever S obtains (Encrypt,sid,w_i) from F_CPKE, S sends the message (Encrypt, sid, w_i) to A with sid = (P, sid’), then forwards the response x_i (1≤i≤m+1)from A to F_sig. Whenever, S receives a message (KenGen,sid) from F_sig, S sends to A the message (KenGen,sid) with sid = (P,sid’), then forwards the response (Verificationkey, sid, ZS, C, V’) from A to F_sig. (V’ may be different from V). Whenever, S receives a message (Sign, sid, x_i) from F_sig, S sends (Sign, sid, x_i) to A, then forwards the response (signature, sid, x_i, σ_i) from A to F_sig. Assume that π_coding can not securely realize F_coding, then existing Z can distinguish with a non-negligible probability whether it is interacting with A and π_coding or it is interacting with S and F_coding. Assume that we can construct an adversary B who can forge signature. B can activate environment Z, when C is activated with input (Encoding,Combine,x₁,σ₁,...,x_m,σ_m) by Z and B computes the signature of x_i by sub-signatures combination algorithm and submits it to Z. When P is activated with input (Verify,sid,y,σ,V) by Z, B first checks whether (y,σ,C) is a forged signature or not. If it is a forged signature, then B outputs (y,σ,C) and stops operation. Next, we analysis the probability of success of B. We first denote D as the event where the receiver obtains (Verified,sid,y,f = 1),while party P is uncorrupted at the time when the message is delivered and has never sent (y,σ,C). However, according to the protocol and the logics of F_CPKE and F_sig, the event D would not happen. The reason being is that, firstly the receiver should obtain a valid verified key from F_sig (Otherwise (Verified,sid,y,f = 1) would not be sent by F_sig ); secondly, if an uncorrupted P never sent (y,σ,C), then the message y is never signed by F_sig. Thus, P would always obtain (Verified,sid,y_i,f = 0) from F_sig. Otherwise, this is incompatible with the existential unforgeability(EU-COMA) (Even et al., 1989; Canetti, 2001) property of F_sig. Therefore, the simulation above is perfect based on the fact that the event D will not occur. In another word, Z can not distinguish with a non-negligible probability whether it is interacting with A and π_coding or it is interacting with S and F_coding. Thus, we realize indistinguishability of REAL_{UC-coding,A,Z} and IDEAL_Fcoding,S,Z, in other words, π_coding securely realizes the functionality F_coding in the (F_CPKE, F_sig )-hybrid model. (If we use y’ instead of y, the operation is in the same way).

COMPARISON WITH RELATED WORK

The scheme for network coding against pollution attacks in this article is compared with other representative schemes in Table 1, including security model, the adversary’s capability model and complexity of computation. The literature (Li et al., 2010) gave a MAC-based approach supporting in-network verification and resisting an arbitrary number of collusions.

Table 1:	Comparison between the different schemes for secure network coding
In the table above, ‘Mults’ is the abbreviation of multiplications and ‘exps’ is the abbreviation of exponentiations

The adversary does not have access to the randomness used by the source in order to produce the various cryptographic keys. The computation complexity includes three algorithms: generation MAC, combination of signatures and verification. The computation complexity of literature (Feng et al., 2011) includes two parts: source encryption’s complex is O (logN) and intermediate nodes’s discrete logarithm complex log_gy^rr.

Our protocol is secure against adaptive adversaries in the so-called non-erasing model, Existing equipment or software can achieve AONT encryption, so we need not consider the encryption computational complexity. The computational complexity is mainly reflected in the following aspects. Signing a raw packet requires N exponentiations and N-1 multiplications. Combining is extremely simple, m packets require mN exponentiations and m (N-1) multiplications. Verification is computationally more expensive, if m packets are combined together, computing Υ₁ requires m mappings, m exponentiations and m-1 multiplications, while Υ₂ requires N modulo exponentiations, N-1 multiplications and one mapping.

CONCLUSION

We presented a new random network coding scheme within the framework of Universally Composable (UC). In this work, we realized indistinguishability of wiretapping messages by means of ANOT encryption. In order to prevent malicious nodes, we adopted the signature mechanism NCS₁ to authenticate nodes identity and the transmitted data. Finally, according to the composition theorem, our construction using F_CPKE and F_sig was a secure network coding scheme. Through comparison between the different representative schemes, show that the new scheme having better performance. However, the scheme NCS₁ is based on bilinear maps which may require more powerful computing capabilities for the intermediate nodes. Our next work is to design protocol using more effective signature scheme in network coding.

ACKNOWLEDGMENTS

First and foremost, I am most grateful to my senior, Professor Mr Guo, whose useful suggestions, incisive comments and constructive criticism have contributed greatly to the completion of this paper. I am also greatly indebted to all my friends who have helped me directly and indirectly in my studies. Any progress that I have made is the result of their profound concern and selfless devotion. Among them the following require mentioning: Mr. Liang, Miss Chen and Mr. Jiao.