A Compromise-Resilient Pair-wise Rekeying Protocol in Large-Scale Wireless Sensor Networks

Song GuoInTech 2010 · DOI · OpenAlex

Wireless Sensor Networks (WSNs) are frequently deployed in unattended or hostile environments, making them physically vulnerable to node capture. This paper, originally published in Smart Wireless Sensor Networks (2010), proposes a robust perturbation-based rekeying protocol designed to maintain network security even after multiple nodes have been compromised.

The Challenge: Node Capture Attacks

WSN nodes typically lack expensive tamper-proof hardware. In a Node Capture Attack (NCA), an adversary physically seizes nodes to extract cryptographic keys from their memory. Traditional security schemes often rely on symmetric bivariate polynomials for key distribution. However, these schemes have a mathematical "breaking point": if an attacker captures more nodes than the degree of the polynomial ($t$), they can reconstruct the entire master secret using linear algebra. This compromises all past and future communications across the entire network.

Methodology: Perturbation-Based Rekeying

To address this vulnerability, the authors introduce a Perturbation Polynomial Function into the classic hierarchical key management structure. The network is organized into clusters, each led by a Cluster Head (CH) that manages several Sensor Nodes (SNs).

Mathematical Foundation

The following table defines the primary notations used throughout the protocol's mathematical framework:

Table 1: Notations used in the proposed rekeying protocol.

Instead of storing a pure share of the master polynomial $f(x, y)$, each node $u$ is preloaded with a perturbed version: $$\bar{g}_u(y) = g_u(y) + \phi_u(y)$$ where $\phi_u(y)$ is a perturbation polynomial that only affects the least significant bits of the key. This "Limited Infection Property" ensures that while legitimate nodes can navigate the noise, attackers face an exponentially larger search space.

The Rekeying Process

When a key update is required, the CH generates a new univariate polynomial and broadcasts a modified "master" polynomial to its cluster. Because of the pre-existing perturbation, a sensor node cannot directly calculate the new key. Instead, it must derive three candidate keys to account for potential mathematical carries from the perturbation bits.

Figure 1: The step-by-step rekeying protocol between a Cluster Head (CH) and a Sensor Node (SN).

As shown in Figure 1, the process follows these steps:

  1. CH Generation: The CH generates a new polynomial $p_{CH_a}(y)$ and updates its local pair-wise key.
  2. Broadcast: The CH constructs and broadcasts a new master polynomial $w_{CH_a}(y)$.
  3. SN Calculation: The SN calculates three candidate keys ($K^*, K^+, K^-$) based on its perturbed share.
  4. Verification: The SN attempts to decode a test message piggybacked in a unicast transmission. The candidate that successfully decodes the message is selected as the new pair-wise key.

Key Insights and Results

  • Breaking the Threshold: Unlike traditional schemes that collapse completely once $t+1$ nodes are captured, this protocol transitions to a probabilistic security model. The probability of an attacker successfully reconstructing the secret is reduced to $m^{-(t+1)}$, where $m$ is the number of perturbation polynomials.
  • Resilience to NCA: Numerical simulations show that while benchmark protocols (like Chadha’s scheme) fail entirely after 160 nodes are captured (for $t=80$), the proposed scheme reveals zero keys to the attacker under identical conditions.
  • Computational Efficiency: The protocol is optimized for low-power sensor nodes. Storage requirements are minimal, and the computation for a rekeying cycle involves only one polynomial evaluation and three hash operations.

Conclusion

By introducing controlled "noise" into the key distribution process, the authors have developed a protocol that is significantly more resilient to physical node capture than standard polynomial-based methods. While it requires an offline authority for initial deployment and assumes basic intrusion detection capabilities at the Cluster Head level, it provides a vital layer of forward and backward secrecy for large-scale, vulnerable sensor networks.

Summary updated

BibTeX
@inproceedings{guo2010compromise,
  author = {Song Guo},
  title = {{A Compromise-Resilient Pair-wise Rekeying Protocol in Large-Scale Wireless Sensor Networks}},
  booktitle = {InTech},
  year = {2010},
  doi = {10.5772/13671},
}
Figure