Wireless network security phần 2

8 EURASIP Journal on Wireless Communications and Networking
600 N
Nixon Farm Dr.
20
550
Huntley Rd.
19
18
500
17
16
450
15
14 Perth St. Perth St.
400
13
350 12
McBean St.
11
Fowler St.
300 10 9 8 7 6 5 4 3 2 1
250
200 Martin St.
200 250 300 350 400 450 500 550 600
Figure 2: Example of attacker mobility path.
600
550
20 Figure 4: Urban scenario—Richmond, Ontario.
500
16
450
set Aβ and perimeter-pairs Aγ HPB algorithms with four,
400 eight, 16 and 32 receivers. In each HPB execution, four
of the receivers are fixed road-side units (RSUs) stationed
350 12
at intersections. The remaining receivers are randomly
positioned on-board units (OBUs), distributed uniformly on
300 8 4
the grid streets. Every HPB execution also sees a transmitter
250 placed at a random road position within the inner square of
the simulation grid. We assume that in a sufficiently dense
200 urban setting, RSUs are positioned at most intersections. As a
200 250 300 350 400 450 500 550 600
result, any transmitter location is geographically surrounded
Figure 3: Example of mobile attacker localization. by four RSUs within radio range. For each defined number of
receivers and two separate confidence levels C ∈ {0.95, 0.90},
the HPB algorithms, Aα , Aβ and Aγ , are executed 1000
propagation characteristics, in both indoor and outdoor times. For every execution, RSS values are generated for
channels, including in mobility scenarios. In our previous each receiver from the log-normal shadowing model. We
work, we have evaluated HPB results with both log-normal adopt existing experimental path loss parameter values from
shadowing simulated RSS values and RSS reports harvested large-scale measurements gathered at 2.4 GHz by Liechty
from an outdoor field experiment at 2.4 GHz [9]. We found et al. [26, 27]. From η = 2.76 and a signal shadowing
that the simulated and experimental location estimation standard deviation σ = 5.62, we augment the simulated RSS
results are nearly identical, indicating that at this frequency, values with an independently generated amount of random
the log-normal shadowing model is an appropriate tool for shadowing to every receiver in a given HPB execution. Since
generating realistic RSS values. the EIRP used by a malicious transmitter is unknown, a
We compare the success rates of the Aα , Aβ and Aγ probable range is computed according to Heuristic 1.
algorithms at estimating a malicious transmitter’s location For every HPB execution, whether the Aα , Aβ or Aγ
within a candidate area, as well as the relative sizes of the algorithm is used, we gather three metrics: the success rate
grid and vehicular candidate areas. We model a mobile in localizing the transmitter within a computed candidate
transmitter’s path through a vehicular scenario and assess the area GA; the size of the unconstrained candidate area GA
success in tracking it by measuring the distance between the as a percentage of the one square kilometer grid; the size of
actual and estimated positions, in addition to the difference the candidate area restricted to the vehicular layout VA as a
between the approximated direction of travel and the real percentage of the grid. The success rate and candidate area
one. size results we obtain are deemed 90% accurate within a 2%
and 0.8% confidence interval, respectively. The average HPB
5.1. Hyperbolic Position Bounding of Vehicular Devices. Our execution times for each algorithm on an HP Pavilion laptop
simulation uses a one square kilometer urban grid, as with an AMD Turion 64 × 2 dual-core processor are shown
depicted in Figure 4. We evaluate the all-pairs Aα , 4-pair in Table 1. As expected from our complexity analysis, the Aα
EURASIP Journal on Wireless Communications and Networking 9
100 corresponds to 21% of the simulation grid, with four
90 receivers, for both Aβ and Aα , while Aγ narrows the area
to only 7%. In fact, the Aγ approach exhibits a GA size
80
that is independent of the number of receivers. Yet for Aβ
70 and Aα , the GA size is noticeably lower with additional
60 receivers. This finding reflects the use of perimeter receivers
Success rate
with Aγ . These specialized receivers serve to restrict the GA
50
to a particular portion of the simulation grid, even with
40 few receivers. However, this variation does not fully exploit
30 the presence of additional receiving devices, as these only
support the GA determined by the perimeter receivers. The
20
size of the vehicular candidate area VA follows the same
10 trend, with a near constant size of 0.64% to 1% of the grid for
0 Aγ , corresponding to a localization granularity within an area
4 8 16 32 less than 100 m × 100 m, assuming the transmitter is aboard
Number of receivers a vehicle traveling on a road. The Aβ and Aα algorithms
compute vehicular candidate area sizes that decrease as more
Aγ receivers are taken into account, with Aα yielding the best
Aβ localization granularity. But even with four receivers, Aβ and
Aα Aα localize a transmitter within a vehicular layout area of
1.6% of the grid, or 125 m × 125 m.
Figure 5: Success rate for C = 0.95.
Generally, both the GA and VA sizes decrease as the
number of receivers increases, since additional hyperbolic
areas pose a higher number of constraints on a candidate
Table 1: Average HPB execution time (seconds). area, thus decreasing its extent. We see in Figures 6 and 7 that
Aβ consistently yields larger candidate areas than Aα for the
# Rcvrs Aγ Aβ Aα same reason, as Aα generates a significantly greater number
Mean Std dev. Mean Std dev. Mean Std dev. of hyperbolic areas. For example, while Aα computes an
4 0.005 0.000 0.023 0.001 0.023 0.001 average GAα of 10% and 3% of the simulation grid with eight
8 0.023 0.001 0.045 0.001 0.104 0.003 and 16 receivers, Aβ yields areas of 15% and 9%, respectively.
16 0.075 0.001 0.090 0.002 0.486 0.142 By contrast, Aγ yields a GA size of 5-6% but its reliability is
32 0.215 0.059 0.195 0.053 2.230 0.766 greater, as demonstrated by the higher success rates achieved.
The nearly constant 5% GA size computed with Aγ has an
average success rate of 81% for 16 receivers, while the 9% GA
generated by Aβ is 79% reliable and the 3% GA obtained with
variation is markedly slower, and the computational costs Aα features a dismal 68% success rate. Indeed, Figures 5 and 6
increase as additional receivers participate in the location taken together indicate that smaller candidate areas provide
estimation effort. For example in the case of eight receivers, increased granularity at the cost of lower success rates, and
a single execution of Aγ takes 23 milliseconds, while Aα thus decreased reliability. This phenomenon is consistent
requires over 100 milliseconds. with the intuitive expectation that a smaller area is less likely
The comparative success rates of the Aα , Aβ and Aγ to contain the transmitter.
approaches are illustrated in Figure 5, for confidence level
C = 0.95. While Aγ exhibits the best localization success 5.2. Tracking a Vehicular Device. We generate 1000 attacker
rate, every algorithm sees its performance degrade as more mobility paths P, as stipulated in Definition 5, of 20 consecu-
receivers are included. With four receivers for example, all tive points evenly spaced at every 25 meters. Each path begins
three variations successfully localize a transmitter 94-95% of at a random start location along the central square of the
the time. However with 32 receivers, Aγ succeeds in 79% simulation grid depicted in Figure 4. We keep the simulated
of the cases, while Aβ and Aα do so in 71% and 50% of transmitter location within the area covered by four fixed
executions. Given that each receiver pair takes into account RSUs, presuming that an infinite grid features at least four
an amount of signal shadowing based on the confidence level RSUs within radio range of a transmitter. The direction of
C, it also probabilistically ignores a portion (1 − C) of the travel for the start location is determined randomly. Each
shadowing. As more receivers and thus more receiver pairs subsequent point in the mobile path is contiguous to the
are added, the error due to excluded shadowing accumulates. previous point, along the direction of travel. Upon reaching
The results obtained for confidence level C = 0.90 follow the an intersection in the simulation grid, a direction of travel is
same trend, although the success rates are slightly lower. chosen randomly among the ones available from the current
Figures 6 and 7 show the grid and vehicular candi- position, excluding the reverse direction.
date area sizes associated with our simulation scenario, as The Aα , Aβ and Aγ algorithms are executed at every
computed with algorithms Aα , Aβ and Aγ , for confidence fourth point pi of each mobility path P, corresponding to a
level C = 0.95. The size of the grid candidate area GA transmitted attack signal at every 100 meters. The algorithms
10 EURASIP Journal on Wireless Communications and Networking
25 140
120
20
Location error (meters)
Candidate area size (%)
100
15 80
60
10
40
5
20
0 0
0 5 10 15 20 25 30 35 4 8 16 32
Number of receivers Number of receivers
GAγ Aγ
GAβ Aβ
GAα Aα
Figure 6: Grid candidate area size for C = 0.95.
Figure 8: Location error for C = 0.95.
1.8
transmitter location and the angle θi computed for the
1.6
approximated locations.
1.4 The location error for the Aα , Aβ and Aγ algorithms,
given confidence level C = 0.95, is illustrated in Figure 8.
Candidate area size (%)
1.2
As expected, the smaller VA sizes achieved with a greater
1 number of receivers for Aα and Aβ correspond to a more
precise transmitter localization. The location error associated
0.8
with the Aα algorithm is smaller, compared to Aβ , for the
0.6 same reason. Correspondingly, the nearly constant VA size
obtained with Aγ yields a similar result for the location error.
0.4 For instance with confidence level C = 0.95, eight and 16
0.2 receivers produce a location error of 114 and 79 meters,
respectively, with Aα but of 121 and 102 meters with Aβ . The
0 location error with Aγ is once more nearly constant, at 96
0 5 10 15 20 25 30 35
Number of receivers
and 91 meters. The use of all receiver pairs to compute a VA
with Aα allows for localization that is up to 40–50% more
VAγ precise than grouping the receivers in sets of four or relying
VAβ on perimeter receivers when 16 or 32 receiving devices are
VAα present. Despite its granular localization performance, the
Figure 7: Vehicular candidate area size for C = 0.95. Aα approach works best with large numbers of receivers,
which may not consistently be realistic in a practical setting.
Another important disadvantage of the Aα approach lies in
its large complexity of O(n2 ) for n receivers, when compared
are executed for confidence levels C ∈ {0.95, 0.90}, with to Aβ and Aγ with a complexity of O(n), as discussed in
each of four, eight, 16 and 32 receivers. In every case, the Section 4.2.
receivers consist of four static RSUs, and the remaining are Figure 9 plots the root mean square location error in
OBUs randomly placed at any point on the simulated roads. terms of VA size for the three algorithms. While Aα and
For each execution of Aα , Aβ and Aγ , a vehicular Aβ yield smaller VAs for a large number of receivers, the
candidate area VA is computed, and its centroid V χ is taken VAs computed with Aγ offer more precise localization with
as the probable location of the transmitter, as described in respect to their size. For example, a 0.7% VA size obtained
Algorithm 4. Two metrics are aggregated over the executions: with Aγ features a 96 meter location error, while a similar
the root mean square location error, as the distance in meters size VA computed with Aβ and Aα generates a 102 and 114
between the actual transmitter location pi and its estimated meter location error, respectively.
position pi = V χi ; and the root mean square angle error The error in estimating the direction of travel exhibits
between the angle of travel θi for each consecutive actual little variation in terms of number of receivers and choice
EURASIP Journal on Wireless Communications and Networking 11
140 6. Discussion
130
The location error results of Figure 8 shed an interesting
120 light on the HPB success rates discussed in Section 5.1. For
example in the presence of 32 receivers, for confidence level
Location error (meters)
110
C = 0.95, only 50% of Aα executions yield a candidate area
100
containing a malicious transmitter, as shown in Figure 5.
90 Yet the same scenario localizes a transmitter with a root
80
mean square location error of 45 meters of its true location,
whether it lies within the corresponding candidate area
70 or not. This indicates that while a candidate area may be
60 computed in the wrong position, it is in fact rarely far from
the correct transmitter location. This may be a result of
50
our strict definition of a successful execution, where only
40 a candidate area in the intersection of all hyperbolic areas
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6
is considered. We have observed in our simulations that a
Vehicular candidate area size (%)
candidate area may be erroneous solely because of a single
VAγ misplaced hyperbolic area, which results in either a wrong
VAβ location or an empty candidate area. In our simulations
VAα tracking a mobile attacker, we notice that while Aγ and Aβ
Figure 9: Location error for vehicular candidate area size. generate an empty VA for 10% and 14% of executions, Aα
does so in 31% of the cases. This phenomenon is likely
due to the greater number of hyperbolic areas generated
with the Aα approach and the subsequent greater likelihood
80
of erroneously situated hyperbolic areas. While the success
70 rates depicted in Figure 5 omit the executions yielding
empty candidate areas as inconclusive, future work includes
60 devising a heuristic to recompute a set of hyperbolic areas in
Angle error (degrees)
the case where their common intersection is empty.
50
In comparing the location accuracy of HPB with related
40 technologies, we find that, for example, differential GPS
devices can achieve less than 10 meter accuracy. However,
30 this technology is better suited to self-localization efforts
relying on a device’s assistance and cannot be depended upon
20
for the position estimation of a noncooperative adversary.
10 The FCC has set forth regulations for the network-based
localization of wireless handsets in emergency 911 call
0 situations. Service providers are expected to locate a calling
4 8 16 32 device within 100 meters 67% of the time and within 300
Number of receivers meters in 95% of cases [28]. In the minimalist case involving
four receivers, the HPB perimeter-pairs variation Aγ localizes
Aγ a transmitting device with a root mean square location error
Aβ
of 107 meters. This translates into a location accuracy of
Aα
210 meters in 95% of cases and of 104 meters in 67%
Figure 10: Direction of travel angle error for C = 0.95. of executions. While the former case is fully within FCC
guidelines, the latter is very close. With a larger number
of receivers, for example, eight receiving devices, Aγ yields
an accuracy of 188 meters 95% of the time and of 93
of HPB algorithm, as shown in Figure 10. With eight and 16 meters in 67% of cases. Although HPB is designed for the
receivers, for confidence level C = 0.95, Aβ approximates location estimation of a malicious insider, its use may be
the angle of travel between two consecutive points within extended to additional applications such as 911 call origin
77◦ and 71◦ , respectively, whereas Aα estimates it within 76◦ localization, given that its performance closely matches the
and 63◦ . Aγ exhibits a slightly higher direction error at 76◦ FCC requirements for emergency services.
and 77◦ . It should be noted that for all three algorithms,
for all numbers of receivers, the range of angle errors 7. Conclusion
only spans 14◦ . So while the granularity of localization
is contingent upon the HPB methodology used and the We extend a hyperbolic position bounding (HPB) mecha-
number of receivers, the three variations perform similarly nism to localize the originator of an attack signal within
in estimating the general direction of travel. a vehicular network. Because of our novel assumption that
12 EURASIP Journal on Wireless Communications and Networking
the message EIRP is unknown, the HPB location estimation Engineering Research Council of Canada (NSERC) and the
approach is suitable to security scenarios involving malicious Automobile of the 21st Century (AUTO21) Network of
or uncooperative devices, including insider attacks. Any Centers of Excellence (NCE).
countermeasure to this type of exploit must feature minimal-
ist assumptions regarding the type of radio equipment used
by an attacker and expect no cooperation with localization References
efforts on the part of a perpetrator.
[1] IEEE Intelligent Transportation Systems Committee, “IEEE
We devise two additional HPB-based approaches to com- Trial-Use Standard for Wireless Access in Vehicular
pute hyperbolic areas between pairs of trusted receivers by Environments—Security Services for Applications and
grouping them in sets and establishing perimeter receivers. Management Messages,” IEEE Std 1609.2-2006, July 2006.
We demonstrate that due to the dynamic computation of [2] R. Anderson, M. Bond, J. Clulow, and S. Skorobogatov, “Cryp-
a probable EIRP range utilized by an attacker, our HPB tographic processors—a survey,” Proceedings of the IEEE, vol.
algorithms are impervious to varying power attacks. We 94, no. 2, pp. 357–369, 2006.
extend the HPB algorithms to track the location of a mobile [3] R. Anderson and M. Kuhn, “Tamper resistance: a cautionary
attacker transmitting along a traveled path. note,” in Proceedings of the 2nd USENIX Workshop on Elec-
The performance of all three HPB variations is evaluated tronic Commerce, pp. 1–11, Oakland, Calif, USA, November
in a vehicular scenario. We find that the grouped receivers 1996.
method yields a localization success rate up to 11% higher [4] National Institute of Standards and Technology, “Security
for a 6% increase in candidate area size over the all- Requirements for Cryptographic Modules,” Federal Informa-
pairs approach. We also observe that the perimeter-pairs tion Processing Standards 140-2, NIST, May 2001.
algorithm provides a more constant candidate area size, [5] IBM, “IBM 4764 PCI-X Cryptographic Coprocessor,”
independently of the number of receivers, for a success rate http://www.ibm.com.
up to 13% higher for a 2% increase in candidate area size [6] D. E. Williams, “A Concept for Universal Identification,” White
over the all-pairs variation. We conclude that the original paper, SANS Institute, December 2001.
HPB mechanism using all pairs of receivers produces a [7] SeVeCom, “Security architecture and mechanisms for
smaller localization error than the other two approaches, V2V/V2I, deliverable 2.1,” Tech. Rep. D2.1, Secure Vehicle
when a large number of receiving devices are available. Communication, Paris, France, August 2007, edited by
Antonio Kung.
We observe that for a confidence level of 95%, the former
approach localizes a mobile transmitter with a granularity [8] C. Laurendeau and M. Barbeau, “Insider attack attribution
using signal strength-based hyperbolic location estimation,”
as low as 45 meters, up to 40–50% more precisely than the
Security and Communication Networks, vol. 1, no. 4, pp. 337–
grouped receivers and perimeter-pairs methods. However, 349, 2008.
the computational complexity of the all-pairs variation is
[9] C. Laurendeau and M. Barbeau, “Hyperbolic location esti-
significantly greater, and its performance with fewer receivers mation of malicious nodes in mobile WiFi/802.11 networks,”
is less granular than the perimeter-pairs method. Of the in Proceedings of the 2nd IEEE LCN Workshop on User
two approaches with complexity O(n), the perimeter-pairs MObility and VEhicular Networks (ON-MOVE ’08), pp. 600–
method yields a success rate up to 8% higher for consistently 607, Montreal, Canada, October 2008.
smaller candidate area sizes, location, and direction errors. [10] A. Boukerche, H. A. B. F. Oliveira, E. F. Nakamura, and A. A.
In a vehicular scenario, we achieve a root mean square F. Loureiro, “Vehicular ad hoc networks: a new challenge for
location error of 107 meters with four receivers and of localization-based systems,” Computer Communications, vol.
96 meters with eight receiving devices. This granularity is 31, no. 12, pp. 2838–2849, 2008.
sufficient to satisfy the FCC-mandated location accuracy [11] R. Parker and S. Valaee, “Vehicular node localization
regulations for emergency 911 services. Our HPB mechanism using received-signal-strength indicator,” IEEE Transactions on
may therefore be adaptable to a wide range of applications Vehicular Technology, vol. 56, no. 6, part 1, pp. 3371–3380,
involving network-based device localization assuming nei- 2007.
ther target node cooperation nor knowledge of the EIRP. [12] J.-P. Hubaux, S. Čapkun, and J. Luo, “The security and privacy
We have demonstrated the suitability of the hyperbolic of smart vehicles,” IEEE Security & Privacy, vol. 2, no. 3, pp.
position bounding mechanism for estimating the candidate 49–55, 2004.
location of a vehicular network malicious insider and for [13] S. Čapkun and J.-P. Hubaux, “Secure positioning in wireless
tracking such a device as it moves throughout the network. networks,” IEEE Journal on Selected Areas in Communications,
vol. 24, no. 2, pp. 221–232, 2006.
Future research is required to assess the applicability of the
HPB localization and tracking mechanisms in additional [14] S. Brands and D. Chaum, “Distance-bounding protocols,” in
Proceedings of the Workshop on the Theory and Application of
types of wireless and mobile technologies, including wireless
Cryptographic Techniques on Advances in Cryptology (EURO-
access networks such as WiMAX/802.16. CRYPT ’94), vol. 765 of Lecture Notes in Computer Science, pp.
344–359, Springer, Perugia, Italy, May 1994.
[15] B. Xiao, B. Yu, and C. Gao, “Detection and localization of
Acknowledgments sybil nodes in VANETs,” in Proceedings of the Workshop on
Dependability Issues in Wireless Ad Hoc Networks and Sensor
The authors gratefully acknowledge the financial support Networks (DIWANS ’06), pp. 1–8, Los Angeles, Calif, USA,
received for this research from the Natural Sciences and September 2006.
EURASIP Journal on Wireless Communications and Networking 13
[16] T. Leinmüller, E. Schoch, and F. Kargl, “Position verification
approaches for vehicular ad hoc networks,” IEEE Wireless
Communications, vol. 13, no. 5, pp. 16–21, 2006.
[17] J. R. Douceur, “The Sybil attack,” in Peer-to-Peer Systems,
vol. 2429 of Lecture Notes in Computer Science, pp. 251–260,
Springer, Berlin, Germany, 2002.
[18] L. Tang, X. Hong, and P. G. Bradford, “Privacy-preserving
secure relative localization in vehicular networks,” Security and
Communication Networks, vol. 1, no. 3, pp. 195–204, 2008.
[19] G. Yan, S. Olariu, and M. C. Weigle, “Providing VANET
security through active position detection,” Computer Com-
munications, vol. 31, no. 12, pp. 2883–2897, 2008.
[20] N. Mirmotahhary, A. Kohansal, H. Zamiri-Jafarian, and
M. Mirsalehi, “Discrete mobile user tracking algorithm via
velocity estimation for microcellular urban environment,” in
Proceedings of the 67th IEEE Vehicular Technology Conference
(VTC ’08), pp. 2631–2635, Singapore, May 2008.
[21] Z. R. Zaidi and B. L. Mark, “Real-time mobility tracking
algorithms for cellular networks based on Kalman filtering,”
IEEE Transactions on Mobile Computing, vol. 4, no. 2, pp. 195–
208, 2005.
[22] T. S. Rappaport, Wireless Communications: Principles and
Practice, Prentice-Hall, Upper Saddle River, NJ, USA, 2nd
edition, 2002.
[23] C. Laurendeau and M. Barbeau, “Probabilistic evidence
aggregation for malicious node position bounding in wireless
networks,” Journal of Networks, vol. 4, no. 1, pp. 9–18, 2009.
[24] Y. Chen, K. Kleisouris, X. Li, W. Trappe, and R. P. Martin,
“The robustness of localization algorithms to signal strength
attacks: a comparative study,” in Proceedings of the 2nd IEEE
International Conference on Distributed Computing in Sensor
Systems (DCOSS ’06), vol. 4026 of Lecture Notes in Computer
Science, pp. 546–563, Springer, San Francisco, Calif, USA, June
2006.
[25] American National Standards Institute, “Programming Lan-
guage FORTRAN,” ANSI Standard X3.9-1978, 1978.
[26] L. C. Liechty, Path loss measurements and model analysis of
a 2.4 GHz wireless network in an outdoor environment, M.S.
thesis, Georgia Institute of Technology, Atlanta, Ga, USA,
August 2007.
[27] L. C. Liechty, E. Reifsnider, and G. Durgin, “Developing
the best 2.4 GHz propagation model from active network
measurements,” in Proceedings of the 66th IEEE Vehicular
Technology Conference (VTC ’07), pp. 894–896, Baltimore, Md,
USA, September-October 2007.
[28] Federal Communications Commission, 911 Service, FCC
Code of Federal Regulations, Title 47, Part 20, Section 20.18,
October 2007.
Hindawi Publishing Corporation
EURASIP Journal on Wireless Communications and Networking
Volume 2009, Article ID 427492, 12 pages
doi:10.1155/2009/427492
Research Article
In Situ Key Establishment in Large-Scale Sensor Networks
Yingchang Xiang,1 Fang Liu,2 Xiuzhen Cheng,3 Dechang Chen,4 and David H. C. Du5
1 Department of Basic Courses, Rizhao Polytechnic College, Rizhao, Shandong 276826, China
2 Department of Computer Science, University of Texas - Pan American, Edinburg, Texas 78539, USA
3 Department of Computer Science, The George Washington University, Washington, DC, 20052, USA
4 Department of Preventive Medicine and Biometrics, Uniformed Services University of the Health Sciences,
Bethesda, MD 20817, USA
5 Department of Computer Science and Engineering, University of Minnesota, Minneapolis, Minnesota, USA
Correspondence should be addressed to Xiuzhen Cheng, [email protected]
Received 1 January 2009; Accepted 11 April 2009
Recommended by Yang Xiao
Due to its efficiency, symmetric key cryptography is very attractive in sensor networks. A number of key predistribution schemes
have been proposed, but the scalability is often constrained by the unavailability of topology information before deployment and
the limited storage budget within sensors. To overcome this problem, three in-situ key establishment schemes, SBK, LKE, and
iPAK, have been proposed. These schemes require no preloaded keying information but let sensors compute pairwise keys after
deployment. In this paper, we propose an in-situ key establishment framework of which iPAK, SBK, and LKE represent different
instantiations. We further compare the performance of these schemes in terms of scalability, connectivity, storage, and resilience.
Our simulation results indicate that all the three schemes scale well to large sensor networks. We also notice that SBK outperforms
LKE and LKE outperforms iPAK with respect to topology adaptability. Finally, observing that iPAK, SBK, and LKE all rely on the
key space models that involve computationally intensive modular operations, we propose an improvement that rely on random
keys that can be easily computed from a secure pseudorandom function. This new approach requires no computation overhead at
regular worker sensors, therefore has a high potential to conserve the network resource.
Copyright © 2009 Yingchang Xiang et al. This is an open access article distributed under the Creative Commons Attribution
License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly
cited.
1. Introduction 42 mJ (840 mJ) for RSA encryption (digital signature) and
0.104 mJ for AES when the key size for both cases is 1024 bits.
Secure communication is a critical requirement for many Therefore establishing a shared key for pairwise communica-
sensor network applications. Nevertheless, the constrained tion becomes a central problem for sensor network security
capabilities of smart sensors (battery supply, CPU, memory, research. Ever since the pioneer work on key predistribution
etc.) and the harsh deployment environment of a sensor by Eschenauer and Gligor [2] in the year 2002, a variety of
network (infrastructureless, wireless, ad hoc, etc.) make this key establishment schemes have been reported, as illustrated
problem very challenging. A secure sensor network requires in Figure 1.
a “sound” key establishment scheme that should be easily Key predistribution is motivated by the observation that
realized by individual sensors, should be localized to scale no topology information is available before deployment. The
well to large sensor networks, should require small amount of two extreme cases are the single master key scheme, which
space for keying information storage, and should be resilient preloads a master key to all sensors, and the all pairwise
against node capture attacks. keys scheme, which preloads a unique key for each pair
Symmetric key cryptography is attractive and applicable of sensors. The first one is weak in resilience while the
in sensor networks because it is computationally efficient. As second one has a high storage overhead. Other than these
reported by Carman et. al [1], a middle-ranged processor two extreme cases there exist a number of probabilistic-
such as the Motorola MC68328 “DragonBall” consumes based key predistribution schemes [2–11], which attract
2 EURASIP Journal on Wireless Communications and Networking
Key establishment
Predistribution
(deterministic approach) In-Situ
Single master key All pairwise keys Under study
Predistribution
(probabilistic approach)
Random keys Random pairwise keys Random key spaces Group-based
Figure 1: Existing Key Establishment Schemes - A Taxonomy.
most of the research interests in securing sensor networks. that involve intensive computation overhead, we propose an
The probabilistic-based schemes require each sensor to improvement that rely on random keys that could be easily
preload keying information such that two neighboring generated by a secure pseudorandom function.
sensors compute a shared key after exchanging part of the This paper is organized as follows. Major key predistri-
stored information after deployment. Generally speaking, bution schemes are summarized in Section 2. Preliminaries,
the larger the amount of keying information stored within models, and assumptions are sketched in Section 3. The in-
each sensor, the better the connectivity of the key-sharing situ key establishment framework is introduced in Section 4,
graph, the higher the computation and communication and the three instantiations are outlined in Section 5.
overheads. A major drawback of the schemes in this category Performance evaluation and comparison study are reported
is the storage space wastage since a large amount of keying in Section 6. Finally, we summarize our work and discuss the
information may never be utilized during the lifetime of a future research in Section 7.
sensor. Consequently, the scalability of key predistribution
is poor, since the amount of required security information 2. Related Work: Key Predistribution
to be preloaded increases with the network size. Further-
more, many of the probabilistic-based approaches bear poor In this section, major related works on key predistribution
resilience as the compromise of any sensors could release the are summarized and compared. We refer the readers to [10,
pairwise key used to protect the communications between 15] for a more comprehensive literature survey.
two uncompromised sensors. In summary, probabilistic- The basic random keys scheme is proposed by Eschenauer
based key predistribution could not achieve good perfor- and Gligor in [2], in which a large key pool K is computed
mance in terms of scalability, storage overhead, key-sharing offline and each sensor picks m keys randomly from K
probability, and resilience simultaneously. without replacement before deployment. Two sensors can
Recently, three in-situ key establishment schemes, iPAK establish a shared key as long as they have at least one key
[12], SBK [13] and LKE [14], have been proposed for in common. To enhance the security of the basic scheme in
the purpose of overcoming all the problems faced by key against small-scale attacks, Chan et al. [3] propose the q-
predistribution. Schemes in this category require no keying composite keys scheme in which q > 1 number of common
information to be predistributed, while sensors compute keys are required for two nodes to establish a shared key.
shared keys with their neighbors after deployment. The basic This scheme performs worse in resilience when the number
idea is to utilize a small number of service sensors as sacrifices of compromised sensors is large.
for disseminating keying information to worker sensors in In these two schemes [2, 3], increasing the number of
the vicinity. Worker sensors are in charge of normal network compromised sensors increases the percentage of compro-
operations such as sensing and reporting. Two worker mised links shared by uncompromised sensors. To overcome
sensors can derive a common key once they obtain keying this problem, in the same work Chan et al. [3] propose to
information from the same service sensor. In this paper, we boost up a unique key for each link through multi-path
first propose the in-situ key establishment framework, of enhancement. For the same purpose, Zhu et al. [16] propose
which iPAK, SBK, and LKE represent different instantiations. to utilize multiple logic paths. To improve the efficiency of
Then we report our comparison study on the performance key discovery in [2, 3], which is realized by exchanging the
of these three schemes in terms of scalability, connectivity, identifiers of the stored keys, or by a challenge-response
storage overhead and resilience. Our results indicate that all procedure, Zhu et al. [16] propose an approach based on
the three in-situ schemes scale well to large sensor networks the pseudo-random key generator seeded by the node id.
as they require only local information. Furthermore, we also Each sensor computes the key identifiers and preloads the
notice that SBK outperforms LKE and LKE outperforms corresponding keys based on its unique id. Two sensors can
iPAK with respect to topology adaptability. Finally, observing determine whether they have a common key based on their
that iPAK, SBK, and LKE all rely on the key space models ids only. Note that this procedure does not improve the
EURASIP Journal on Wireless Communications and Networking 3
security of the key discovery procedure since an attacker storage overhead. Two similar works [8, 11] have been
can still Figure out the key identifiers as long as the proposed at ACM Wise 2005 independently. In [8], sensors
algorithm is available. Further, a smart attacker can easily are equally partitioned based on ids into disjoint deployment
beat the pseudo-random key generator to compromise the groups and disjoint cross groups. Each sensor resides in
network faster [17]. Actually for smart attackers, challenge- exactly one deployment group and one cross group. Sensors
response is an effective way for key discovery but it is too within the same group can establish shared keys based on
computationally intensive. Di Pietro et al. [17] propose a any of the key establishment schemes mentioned above
pseudo-random key predeployment scheme that supports a [2–4, 18, 19]. In [11], the deployment groups and cross
key discovery procedure that is as efficient as the pseudo- groups are defined differently and each sensor may reside in
random key generator [16] and as secure as challenge- more than two groups. Note that these two schemes inherit
response. many nice features of [6], but release the strong topology
To improve the resilience of the random keys scheme in assumption adopted by [6]. A major drawback of these
against node capture attacks, random pairwise keys schemes schemes is the high communication overhead when path
have been proposed [3, 4], in which a key is shared by two keys are sought to establish shared keys between neighboring
sensors only. These schemes have good resilience against sensors.
node capture attacks since the compromise of a sensor Even with these efforts, the shared key establishment
only affects the links incident to that sensor. The difference problem still has not been completely solved yet. As claimed
between [3] and [4] is that sensors in [3] are paired based on by [20, 21], the performance is still constrained by the
ids while in [4] are on virtual grid locations. Similar to the conflict between the desired probability to construct shared
random keys schemes, random pairwise keys schemes do not keys for communicating parties and the resilience against
scale well to large sensor networks. Neither do they have good node capture attacks, under a given capacity for keying
key-sharing probability due to the conflict between the high information storage in each sensor. Researchers have been
keying storage redundancy requirement and the memory actively working toward this to minimize the randomness
constraint. [22, 23] in the key predistribution schemes. Due to space
To improve the scalability of the random keys schemes, limitations, we could not cover all of them thoroughly.
two random key spaces schemes [5, 7] have been proposed Interested readers are referred to a recent survey [15] and the
independently at ACM CCS 2003. These two works are references therein.
similar in nature, except that they apply different key space Architectures consisting of base stations for key man-
models, which will be summarized in Subsection 3.1. Each agement have been considered in [24] and [25], which
sensor preloads several keying shares, with each belonging to rely on base stations to establish and update different
one key space. Two sensors can establish a shared key if they types of keys. In [1], Carman et al. apply various key
have keying information from the same key space. References management schemes on different hardware platforms and
[7] also proposes to assign one key space to each row or each evaluate their performance in terms of energy consumption,
column of a virtual grid. A sensor residing at a grid point for and so forth. Authentication in sensor networks has been
receives keying information from exactly two key spaces. This considered in [24–26], and so forth.
realization involves more number of key spaces. Note that The three in-situ key establishment schemes [12–14]
these random key spaces schemes also improve resilience are radically different from all those mentioned above.
and key-sharing probability because more key spaces are They rely on service sensors to facilitate pairwise key
available, and because two sensors compute a unique key establishment between worker sensors after deployment. The
within one key space for their shared links. service sensors could be predetermined [12], or self-elected
Compared to the works mentioned above, group-based based on some probability [13] or location information
schemes [6, 8, 9, 11] have the best performance in scalability, [14]. Each service sensor carries or computes a key space
key-sharing probability, storage, and resilience due to the and distributes a unique piece of keying information to
relatively less randomness involved in these key predistri- each associated worker sensor in its neighborhood via a
bution schemes. Du et al. scheme [6] is the first to apply computationally asymmetric secure channel. Two worker
the group concept, in which sensors are grouped before sensors are able to compute a pairwise key if they obtain
deployment and each group is dropped at one deployment keying information from the same key space. As verified
point. Correspondingly, a large key pool K is divided by our simulation study in Section 6, in-situ schemes
into subkey spaces, with each associated with one group can simultaneously achieve good performance in terms of
of sensors. Subkey spaces overlap if the corresponding scalability, storage overhead, key-sharing probability, and
deployment points are adjacent. Such a scheme ensures resilience.
that close-by sensors have a higher chance to establish a
pairwise key directly. But the strong assumption on the 3. Preliminaries, Models, and Assumptions
deployment knowledge (static deployment point) renders it
impractical for many applications. Also relying on deploy- 3.1. Key Space Models. The two key space models for est-
ment knowledge, the scheme proposed by Yu and Guan ablishing pairwise keys, one is polynomial-based [19] and
in [9] significantly reduces the number of potential groups the other is matrix-based [18], have been tailored for sensor
from which neighbors of each node may come, yet still networks at [7] and [5], respectively. These two models are
achieves almost perfect key-sharing probability with low similar in nature.
4 EURASIP Journal on Wireless Communications and Networking
The polynomial-based key space utilizes a bivariate λ- 3.2.1. Key Generation. Choose two large distinct primes p

degree polynomial f (x, y) = f (y, x) = λi, j =0 ai j x j y j over and q such that p ≡ q ≡ 3 mod 4. (p, q) is the private key
a finite field Fq , where q is a large prime number (q must while n = p · q is the public key.
be large enough to accommodate a cryptographic key) .
By pluging in the id of a sensor, we obtain the keying 3.2.2. Encryption. For the encryption, only the public key n
information (called a polynomial share) allocated to that is needed. Let Pl be the plain text that is represented as an
sensor. For example, sensor i receives f (i, y) as its keying integer in Zn . Then the cipher text c = Pl2 mod n.
information. Therefore two sensors knowing each other’s id
can compute a shared key from their keying information as 3.2.3. Decryption. Since p ≡ q ≡ 3 mod 4, we have
f (x, y) = f (y, x). For the generation of a polynomial-based
key space f (x, y), we refer the readers to [19]. m p = c p+1/4 mod p,
The matrix-based key space utilizes a (λ + 1) × (λ + 1) (1)
public matrix (Note that G can contain more than (λ + 1) mq = cq+1/4 mod q.
columns.) G and a (λ + 1) × (λ + 1) private matrix D over a By applying the extended Euclidean algorithm, y p and yq can
finite field GF(q), where q is a prime that is large enough be computed such that y p · p + yq · q = 1.
to accommodate a cryptographic key. We require D to be From the Chinese remainder theorem, four square roots
symmetric. Let A = (D · G)T . Since D is symmetric, A · G +r, −r, +s, −s can be obtained:
is symmetric too. If we let K = A · G, we have ki j = k ji ,  
where ki j is the element at the ith row and the jth column r = y p · p · mq + yq · q · m p mod n
of K, i, j = 1, 2, . . . , λ + 1. Therefore if a sensor knows a row
of A, say row i, and a column of G, say column j, then the −r = n − r
  (2)
sensor can compute ki j . Based on this observation, we can s = y p · p · mq − yq · q · m p mod n
allocate to sensor i a keying share containing the ith row of
A and the ith column of G, such that two sensors i and j can −s = n − s.
compute their shared key ki j by exchanging the columns of
Note that Rabin’s encryption [27] requires only one
G in their keying information. We call (D, G) a matrix-based
squaring, which is several hundreds of times faster than
key space, whose generation has been well-documented by
RSA. However, its decryption time is comparable to RSA.
[18] and further by [5].
The security of Rabin’s scheme is based on the factorization
Both key spaces are λ-collusion-resistent [18, 19]. In
of large numbers; thus, it is comparable to that of RSA
other words, as long as no more than λ sensors receiving
too. Since Rabin’s decryption produces three false results in
keying information from the same key space release their
addition to the correct plain text, a prespecified redundancy,
stored keying shares to an attacker, the key space remains
a bit string R, is appended to the plain text before encryption
perfectly secure. Note that it is interesting to observe that the
for ambiguity resolution.
storage space required by a keying share from either key space
at a sensor can be very close ((λ+1)·log q for the polynomial-
based key space [19] and (λ + 2)·log q for the matrix-based 3.3. Network Model and Security Assumptions. We consider
key space [18]) for the same λ, as long as the public matrix G a large-scale sensor network with nodes dropped over the
is carefully designed. For example, [5] proposes to employ a deployment region through vehicles such as aircrafts. There-
Vandermonde matrix over GF(q) for G, such that a keying fore no topology information is available before deployment.
share contains one row of A and the seed element of the Sensors are classified as either worker nodes or service nodes.
corresponding column in G. However, the column of G in Worker sensors are in charge of sensing and reporting
a keying share must be restored when needed, resulting in data, and thus are expected to operate for a long time.
(λ − 1) modular multiplications. Service sensors take care of key space generation and
Note that iPAK, SBK and LKE work with both key space keying information dissemination to assist in bootstrapping
models. In these schemes, service sensors need to generate pairwise keys among worker sensors. They may die early
or to be preloaded with a key space and then distribute to due to depleted energy resulted from high workload in the
each worker sensor a keying share. Two worker sensors can bootstrapping procedure. In this sense, they are sacrifices.
establish a shared key as long as they have keying information Nevertheless, we assume service sensors are able to survive
from the same key space. Note that for a polynomial-based the bootstrapping procedure.
key space, two sensors need to exchange their ids while for a In our consideration, sensors are not tamper resistant.
matrix-based key space, they need to exchange the columns The compromise or capture of a sensor releases all its security
(or the seeds of the corresponding columns) of G in their information to the attacker. Nevertheless, a sensor deployed
keying shares. in a hostile environment must be designed to survive at
least a short interval longer than the key bootstrapping
3.2. Rabin’s Public Cryptosystem. Rabin’s scheme [27] is a procedure when captured by an adversary; otherwise, the
public cryptosystem, which is adopted by the in-situ key whole network can be easily taken over by the opponent [28].
establishment schemes to set up a computationally asymmet- We further assume that a cryptographically secure key
ric secure channel through which keying information can be k0 is preloaded to all sensors such that all communications
delivered from a service sensor to a worker sensor. in the key establishment procedure can be protected by a
EURASIP Journal on Wireless Communications and Networking 5
popular symmetric cryptosystem such as AES or Triple- Worker node Service node
DES. Therefore k0 is adopted mainly to protect against
false sensor injection attacks, and any node deployed by ×q
n= p
an adversary can be excluded from key establishment. Note
that k0 is strong enough such that it is almost impossible Select Ks En (K
s R)
for an adversary to recover it before the key establishment =(
Ks 
procedure is complete, and the release of k0 after the R) 2
m od n
key establishment procedure does not negatively affect the Decrypt:
security of the in-situ key establishment schemes since )
ation D p,q (En (Ks R)) = Ks R
all sensitive information involved in the key establishment g i nform
ey in
procedure is protected via a different technique. All sensors E Ks (k
should remove their stored keying information (k0 and/or
the key space/pool) at the end of the key bootstrapping
procedure. Figure 2: Service sensor association. A worker node associates itself
to a service sensor to obtain the keying information through a
secure channel established based on Rabin’s public cryptosystem.
4. The In-Situ Key Establishment Framework
Compared to the predistribution schemes, in-situ key estab-
lishment schemes distribute keying information for shared
key computation after deployment. unique key space id, (ii) the public key n, where n =
p × q and (p, q) is the corresponding private key preloaded
All the in-situ key establishment contains three phases:
before deployment, and (iii) the coverage area of the service
service node determination and key space construction, service
sensor, which is determined in LKE by a grid size L,
node association and keying information acquisition, and
and specified in iPAK and SBK by a forwarding bound
shared key derivation. iPAK, SBK, and LKE mainly differ
H, the maximum distance in hop count over which the
from each other in the first phase, which will be detailed
existence of a key space can be announced. The mes-
afterwards. Now we sketch the framework for in-situ key
sage will be forwarded to all sensors within S’s coverage
establishment in sensor networks.
area.
4.1. Service Node Determination and Key Space Construc-
tion. In the first phase, service nodes are either prese- 4.2.2. Secure Channel Establishment. Any worker node
lected (in iPAK[12]), or self-elected with some probabil- requesting the keying information from a service node needs
ity (in SBK[13]) or based on sensors’ physical location to establish a secure channel to the associated service node.
(in LKE[14]). A λ-collusion resistent key space (either Recall that we leverage Rabin’s public key cryptosystem [27]
polynomial-based [19] or matrix-based [18]) is allocated to for this purpose. After obtaining the public key n, a worker
[12] or generated by [13, 14] each service sensor. sensor picks up a random key Ks and computes En (Ks R) =
Before deployment, each sensor randomly picks up two (Ks R)2 mod n, where R is a predefined bit pattern for ambi-
primes p and q from a pool of large primes without guity resolution in Rabin’s decryption. En (Ks R), along with
replacement. The prime pool is precomputed by high- the location information, is transmitted to the corresponding
performance facilities, which is out of the scope of this paper. service sensor. After Rabin’s decryption, the service sensor
Primes p and q will be used to form the private key such that obtains D p,q (En (Ks R)) = Ks R, where Ks will be utilized to
Rabin’s public cryptosystem [27] can be applied to establish protect the keying share transmission from the service sensor
a secure channel for disseminating keying information in the to the work sensor.
second phase. Note that in this protocol, each worker sensor executes
one Rabin’s encryption for each service sensor from which an
4.2. Service Node Association and Keying Information Acqui- existence announcement is received, whereas the computa-
sition. Once a service sensor finishes the key space con- tionally intensive decryption of Rabin’s system is performed
struction, it broadcasts a beacon message notifying others only at service sensors. This can conserve the energy of
of its existence after a random delay. A worker node worker sensors to extend the operation time of the network.
receiving the beacon will acquire keying information from In this aspect, service nodes work as sacrifices to extend the
the service sensor through a secure channel established network lifetime.
based on Rabin’s cryptosystem between the two nodes. As
illustrated in Figure 2, the service node association and 4.2.3. Keying Information Acquisition. After a shared key Ks
keying information acquisition is composed of the following is established between a worker node and a service node, the
three steps. service sensor allocates to the node a keying share from its
key space. The keying information, encrypted with Ks based
4.2.1. Key Space Advertisement. A service node S announces on any popular symmetric encryption algorithm (AES, DES,
its existence through beacon broadcasting when its key etc.), is transmitted to the requesting worker node securely.
space is ready. The beacon message should include: (i) a Any two worker nodes receiving keying information from the
6 EURASIP Journal on Wireless Communications and Networking
same service node can derive a shared key for secure data
exchange in the future.
After disseminating the keying information to all worker
sensors in the coverage area, the service sensor should erase all L v
stored key space information for security enhancement. δ
(X, Y ) L
u
4.3. Shared Key Derivation. Two neighboring nodes sharing Competition area
at least one key space (having obtained keying information
from at least one common service sensor) can establish a
shared key accordingly. The actual computation procedure Coverage area
is dependent on the underlying key space model. We refer
the readers for the details to Subsection 3.1. Note that Figure 3: LKE: A virtual grid, with each grid size of L, is computed
this procedure involves the exchange of either node ids, based on location information. Sensor u is selected from the
if polynomial-based key space model is utilized [19], or competition area and will take care of key establishment for nodes
columns (seeds) of the public matrix, if matrix-based key residing in the coverage area.
space model is utilized [18]. To further improve security,
nonces can be introduced to protect against replay attacks.
In SBK, the service node election is conducted for
several rounds. At the beginning of each round, a non-
5. Service Sensor Election for the In-Situ service sensor that does not have any service node within
Key Establishment Schemes T0 − 1 hops decides to become a service node with the
probability Ps . If a sensor succeeds in the self-election,
All the in-situ key establishment schemes rely on service
it sets up a key space, announces its status to T0 -hop
sensors for keying information dissemination after deploy-
neighbors after a random delay, and then enters the next
ment. As stated before, the major difference among the three
phase for keying information dissemination. Otherwise, it
schemes lies in how service sensors are selected, which is
listens to key space advertisements. Upon receiving any new
sketched in this section.
key space announcements from a service node that is at
most T0 − 1 hops away, the sensor becomes a worker node,
5.1. iPAK. Service node election in iPAK is trivial. They erases its primes, and enters the next phase for service
are predetermined by the network owner. iPAK considers sensor association and keying information acquisition. Note
a heterogeneous sensor network consisting of two different that the reception of a service node announcement also
types of sensors, namely, worker nodes and service nodes. suppresses sensors who have self-elected as service nodes but
Since the number of service sensors is expected to be much have not broadcasted their decisions to broadcast their status.
smaller than that of the worker sensors, service sensors are If no service node within T0 −1 hops is detected in the current
assumed to have much higher capability (computational round, the sensor participates in the next round.
power, energy, and so forth) in order to complete the key
bootstrapping procedure before they run out of energy. To speed up the key bootstrapping procedure, an
Each service node is preloaded with all the necessary enhanced scheme, iSBK, is also proposed in [13], which
information, including one key space and two large primes. achieves high connectivity in less time by generating more
Worker sensors and service sensors are deployed together, service sensors. In iSBK, the service sensor election probabil-
with the proportion predetermined by ρ, where ρ = λ · ity Ps is initialized as Ps = 1/NT0 −1 , and is doubled in each
Ns /Nw , and Ns (Nw ) is the number of service nodes (worker new round until it reaches 1.
nodes). The serving area of a service node is predetermined
by the forwarding bound T0 , the utmost hop distance 5.3. LKE. Similar to SBK, LKE [14] is a self-configuring
from the service node that the keying information can be key establishment scheme. However, the role differentiation
disseminated. is based on location information instead of a probability
Ps . Right after deployment, each sensor positions itself and
5.2. SBK. Compared to iPAK, SBK does not differentiate computes a virtual grid with the grid size of L. As illustrated
the roles of worker sensors and service sensors before in Figure 3, each grid contains a competition area, the disk
deployment. Instead, sensors determine their roles after region within a radius of δ from the grid center. At most one
deployment by probing the local topology of the network. service sensor will be selected from the competition area.
In SBK, service sensors are elected based on a probability An eligible sensor first waits a random delay. If it
Ps , which is initialized as Ps = 1/λ. Once elected, a service receives no competition message from others, it announces
sensor constructs a λ-collusion-resistent key space and serves its decision to be a service sensor. Otherwise, the sensor
worker sensors within its coverage area that is determined self-configures as a worker sensor. Note that all the eligible
by the forwarding bound T0 . T0 is defined according to the sensors√are within δ-distance from the grid center with
expected network density, which should satisfy NT0 ≤ λ δ = R/ 5, where R is the nominal transmission range. The
where NT0 is the average number of neighbors within T0 hops setting of δ ensures that all eligible sensors within a grid can
in the network. communicate with each other directly.