1 Introduction
2 Related works
3 Preliminaries
3.1 Okamoto-Uchiyama (OU) algorithm
3.2 Elliptic curve ElGamal (EC-EG) algorithm
3.3 Homomorphic MAC scheme
3.4 Hash-based Message Authentication Code (HMAC)
4 Comments on “Confidentiality and integrity for data aggregation in WSN using homomorphic encryption”
-
Setup Phase. The base station generates parameters {n,g,h,p,q} and then publishes parameters {n,g,h} as its public key. These system parameters are preloaded on each sensor node. {p,q}are kept only by the base station and used as its private key.
-
Encrypt-Sign Phase.
-
Aggregation Phase.
-
Verify Phase.
5 Comments on “Symmetric-key based homomorphic primitives for end-to-end secure data aggregation in wireless sensor networks”
5.1 The weakness found
6 System model
6.1 Network model
6.2 Adversary model
-
A1: Eavesdropping attack. Eavesdropping attack concerns the passive adversary aiming to get information.
-
B1: Malleability. Malleability allows an adversary to modify data without knowing the content.
-
B2: Replay attack. An adversary intercepts the transmitted data, and then replays it in the future to deceive the BS.
-
B3: Injection attack. An adversary can generate valid ciphertexts under the public key of the base station and then inject them into the network to deceive the base station and waste the transmission energy.
-
B4: Unauthorized aggregation. The idea of such an attack is to aggregate two or more proper ciphertexts into a forged, but authentically looking one in order to cheat the base station.
-
C1: Compromise attack. An adversary can compromise a CH or a sensor node to try to obtain the sensing data.
7 The proposed scheme
Notation | Description |
---|---|
CID
j
| Cluster identifier of sensor nodes belonging to cluster j
|
η
| Number of sensor nodes per cluster |
m
ij
| Sensing data of member node CM
ij
|
H
ij
| The homomorphic MAC generated by CM
ij
|
n
c
| Number of clusters in the whole network |
CH
j
| The cluster head node of the jth cluster in the network |
CM
ij
| The ith member node in the jth cluster |
m
agg
| The sum of all valid sensing data |
-
The base station distributes a cluster identifier CID j to each node in cluster j; namely, the cluster identifiers of nodes in the same cluster are identical.
-
The base station chooses an identifier ID i ∈ [1, … , n]for each node in WSN and preloads them into nodes. For simplicity, we assume that ID i = i.
-
The base station shares a unique symmetric-key pair k j = {k j1, k j2}with all nodes in the same cluster j, where symmetric-key pair k j = {k j1, k j2}is used to generate H-MAC to protect end-to-end data integrity.
-
The cluster head CH j shares a symmetric-key k i − j with its each member nodes in cluster j and each cluster head CH j also shares a symmetric-key k j − BS with the base station, where k i − j and k j − BS are used to produce MAC to achieve in-network false data filtering.
-
The base station generates its public key (n, g, h) and private key (p, q) according to OU algorithm, then keeps the private key and publishes its public key.
-
Ciphertext. A member node CM ij picks a random number r∈ R ℤ n and computes its ciphertext \( {c}_{ij}={g}^{m_{ij}}{h}^{r_{ij}} \mod n \) under the public key of the base station through OU algorithm.
-
Homomorphic MAC. In our scheme, the homomorphic MAC H ij is generated over the ciphertext instead of plaintext, which solves the problem that once a member node in one cluster is compromised, all the member nodes’ data will be disclosed because the keys used to generate homomorphic MAC for each node in one cluster are identical.
-
MAC. We use MAC to achieve in-network false data filtering, which thus avoids consuming unnecessary transmission energy to transmit false data packets. Timestamp t is employed to guarantee data freshness. Algorithm 1 presents this process.
-
Check timestamps. The CH j checks the validity of the timestamp t ij . If the timestamp t ij is valid, the CH j will verify MAC. If not, reject it.
-
Verify MAC. The CH j computes HMAC(k i − j , c ij | | H ij | | t ij ) and compares it with MAC ij received. If they are equal, then the CH j aggregates the corresponding ciphertext and homomorphic MAC, or the packet will be rejected.
-
Aggregate. In this step, the cluster head CH j (j = 1, … , n c ) acts as a data aggregator. The CH j aggregates η − 1 ciphertexts received from its member nodes and its own ciphertext into a single ciphertext c j . Also, it combines η − 1 homomorphic MAC H ij and its own H ij into one homomorphic MAC H j . Then, the CH j sends the output of Algorithm 2 to the base station or the nearest CH. When a CH receives a packet from another CH, it only forwards it to the base station, and does not aggregate or verify it.
-
Check timestamps. The base station checks the validity of the timestamp t j . If the timestamp t j is valid, the base station will verify MAC. If not, reject it.
-
Verify MAC. The base station calculates HMAC(k j − BS , c j | | H j | | t j ) and compares it with MAC j received. If they are equal, it can be sure that the ciphertext received and the corresponding homomorphic MAC are not modified by adversaries.
-
End-to-end integrity verification. The base station verifies the integrity of each c j through the homomorphic MAC scheme. If the verification holds, then the aggregated ciphertext c j will be decrypted and has chance to participate in the final aggregation, otherwise it will be rejected. In our scheme, the packet of each cluster is verified individually; that is to say, after each cluster’s packet is verified successfully, the base station then decrypts them and aggregates all valid plaintext m j rather than directly verifying the final aggregated results. In this way, if the verification is failed to pass for one cluster, only the packet of this cluster is discarded. Unlike other schemes [4, 7], once the verification fails, all packets, including valid packets, will be abandoned, which means all data need to be retransmitted.
-
Decrypt. In this step, the base station decrypts the aggregated ciphertext c j and obtains the aggregated plaintext m j for each cluster. For those ciphertexts failed to pass end-to-end integrity verification, it is not necessary to decrypt them, which results in saving energy consumption, because, for a modified packet, verification then decryption only involves verification overhead while decryption then verification consumes energy in both verification and decryption.
-
Get the final aggregated result m agg . Only by passing the end-to-end integrity verification, can the aggregated plaintext m j participate in the final aggregation; namely, m agg is the result of the sum for all m j whose ciphertext passes the end-to-end integrity verification. Its advantage being that, if some received messages are not successfully verified, other valid packets can be utilized. Algorithm 3 describes the detail verification process.
8 Security analysis
-
Eavesdrop attack: In our scheme, the sensing data are encrypted under the public key of the base station during the transmission process. After receiving packets from its member nodes, a CH does not decrypt messages but only aggregates them. Only the base station can decrypt messages to obtain the sensing data. Even though an adversary eavesdrops on a transmitted packet, he has no way to decrypt the ciphertext without the private key of the base station. End-to-end confidentiality of our scheme can be reduced to the security of the underlying homomorphic encryption scheme, OU. Detailed security proof can be found in [19].
-
Malleability: Malleability is a common threat for all homomorphic encryption schemes. An adversary can alter a ciphertext by injecting false data, but it will not be detected due to the homomorphic property. For example, (m + k) mod n may be modified to (m + x) + k mod n, where x is the false data injected by an adversary. In our scheme, we use a homomorphic MAC scheme to verify the integrity of the data. If the encrypted data is tampered, the integrity verification will fail and thus the BS will refuse the received packet.
-
Replay attack: An adversary can impersonate any node through replaying old packets recorded from past communications; therefore, we add current timestamps to messages being signed to resist replay attacks. Thus, the receivers can ensure data freshness by checking the validity of the timestamps.
-
Injection attack: With public key cryptography, any adversary can generate a reasonable ciphertext and inject it into the network to deceive the base station. In our scheme, each sender (a sensor node or a CH) computes a MAC using the symmetric key shared with the receiver (a CH or the base station), so the receiver will reject these injected packets in the “Verify MAC” step if an adversary injects its false data.
-
Unauthorized aggregation: Unauthorized aggregation is a very specific weakness of homomorphic encryption schemes [18]. The idea of such an attack is to aggregate two or more proper ciphertexts into a forged but format-valid ciphertext to deceive the BS. If the CHs only aggregate data, anyone can impersonate this to produce a false aggregated result by dropping some packets and, thus, misleading the BS. To protect a homomorphic encryption scheme from unauthorized aggregation, in our scheme, each CH not only performs aggregation operation, but also generates MAC and homomorphic MAC on the aggregated result. Therefore, the BS can check the authenticity of the CHs and the integrity of the aggregated results.
-
Compromise attack: We classify compromise attack into two cases: (1) Compromise a CH. Since the CHs store important data, it makes them likely to be targeted by adversaries. However, even if a CH is compromised, an adversary cannot obtain the sensing data, because the CHs do not store the private key of the base station, and decrypting a ciphertext is impractical. (2) Compromise a sensor node. If a sensor node is compromised, it only reveals its own sensing data and an adversary has no way to get key and data for other nodes. In [9], once an adversary gains the key used to generate the homomorphic MAC by compromising a node, all nodes’ data will be disclosed, since they calculate the homomorphic MAC over the plaintext and the keys used for the homomorphic MAC are identical for all sensor nodes. However, we compute a homomorphic MAC over the ciphertext and the keys used to produce a homomorphic MAC for different clusters are different. In this way, even if a node is compromised, the result cannot have a significant impact upon the overall system security.
9 Performance analysis
9.1 Security requirements
9.2 Cost evaluation
9.2.1 Computation overhead
Encrypt (CM
ij
) | Aggregate(CH
j
) | |
---|---|---|
RCDA-HOMO | 4 SM | -- |
CDAMA (k = 2) | 4 SM | -- |
CDAMA (k = 3) | 6 SM | -- |
CDAMA (k = 4) | 8 SM | -- |
Sen-SDA | 4 SM | 2 N + 2 SM |
Our scheme | 1 E | -- |
9.2.2 Communication overhead
Communication (bits) | |
---|---|
RCDA-HOMO | 482 |
CDAMA (k = 2) | 769 |
CDAMA (k = 3) | 1025 |
CDAMA (k = 4) | 1281 |
Sen-SDA | 912 |
Our scheme | 1120 |
9.2.3 Energy consumption
-
ECs for computation. We can estimate ECs of each phase utilizing the formula W = U × I × t, where U is the voltage, I is the current draw, and t is the execution time for one phase. According to [19], we find that a modular exponentiation operation takes 7k/4 modular multiplications in the extended binary method and the encryption process of OU requires about 230 modular multiplications. Additionally, the time required to compute binary field multiplication at the 80-bit security level on Tmote Sky platform is 8706 cycles according to [29]. Since a pairing computation takes 10.4 × 106 cycles and the time consumed is 1.27 s, we can estimate the cost of a multiplication in the binary field as
-
ECs for communication. The ECs for receiving and transmitting an l-bits message are W r = U ∗ I r ∗ l/d r , and W t = U ∗ I t ∗ l/d r , respectively, where I r and I t are the current draw in receiving and transmitting mode, respectively, and d r (d r = 250kbps) is a data rate. Therefore, ECs for the reception and transmission of one message on Tmote Sky are W r = 3 ∗ 21.8 ∗ 1120/250 , 000 = 0.29 mJ and W t = 3 ∗ 19.5 ∗ 1120/250 , 000 = 0.26 mJ, respectively. In our scheme, a member node transmits the data to its cluster head once only, so the total EC of one member node for communication is W t = 0.26 mJ. The ECs for a member node are provided in Table 4. For CHs, apart from a Sen-SDA scheme, the CHs in other schemes only execute several simple operations and consume much smaller energy, which can be ignored, so we will not make a detailed description of ECs for CHs.
EC for comp. (mJ) | EC for comm.(mJ) | Total EC (mJ) | |
---|---|---|---|
RCDA-HOMO | 88.56 | 0.11 | 88.67 |
CDAMA(k = 2) | 88.56 | 0.18 | 88.74 |
CDAMA(k = 3) | 132.84 | 0.24 | 133.08 |
CDAMA(k = 4) | 177.12 | 0.30 | 177.42 |
Sen-SDA | 88.56 | 0.21 | 88.77 |
Our Scheme | 7.88 | 0.26 | 8.14 |
9.3 Delay
Processing delay | Aggregation delay | Decryption delay | |
---|---|---|---|
RCDA-HOMO | 4SM + 1PA + 1H
| (2N − 2)PA
| 1ECDLP + k(N + 1)P
|
CDAMA | 2kSM + kPA
| (k − 1)PA
|
kSM + kECDLP
|
Sen-SDA | 4SM + 1PA + 1H
| (2N + 2)SM + (2N − 2)PA + 1H
| (2k + 1)SM + 1ECDLP
|
Our Scheme | 1E + 3H
| (N + 1)H
| (2kN + k)H
|
T
SM
|
T
P
|
T
H
| |
---|---|---|---|
Execution Time (ms) | 0.442 | 4.211 | 0.0001 |
RCDA-HOTO | CDAMA | Sen-SDA | Our scheme | |
---|---|---|---|---|
Decryption Delay (ms) | 1096.42 | 3408.84 | 188.122 | 0.042 |