research-article

Towards provable secure neighbor discovery in wireless networks

Authors:

Marcin Poturalski,

Panos Papadimitratos,

Jean-Pierre HubauxAuthors Info & Claims

FMSE '08: Proceedings of the 6th ACM workshop on Formal methods in security engineering

Pages 31 - 42

https://doi.org/10.1145/1456396.1456400

Published: 27 October 2008 Publication History

Abstract

In wireless systems, neighbor discovery (ND) is a fundamental building block: determining which devices are within direct radio communication is an enabler for networking protocols and a wide range of applications. To thwart abuse of ND and the resultant compromise of the dependent functionality of wireless systems, numerous works proposed solutions to secure ND. Nonetheless, until very recently, there has been no formal analysis of secure ND protocols. We close this gap in [24], but we concentrate primarily on the derivation of an impossibility result for a class of protocols. In this paper, we focus on reasoning about specific protocols. First, we contribute a number of extensions and refinements on the framework of [24]. As we are particularly concerned with the practicality of provably secure ND protocols, we investigate availability and redefine accordingly the ND specification, and also consider composability of ND with other protocols. Then, we propose and analyze two secure ND protocols: We revisit one of the protocols analyzed in [24], and introduce and prove correct a more elaborate challenge-response protocol.

References

[1]

http://www.multispectral.com/.

[2]

G. Ács, L. Buttyán, and I. Vajda. Provably secure on-demand source routing in mobile ad hoc networks. IEEE Transactions on Mobile Computing 5(11):1533--1546, 2006.

Digital Library

[3]

S. Brands and D. Chaum. Distance-bounding protocols. In EUROCRYPT'93: Workshop on the theory and application of cryptographic techniques on Advances in cryptology May 1993.

Digital Library

[4]

L. Bussard. Trust establishment protocols for communicating devices PhD thesis, October 2004.

[5]

L. Buttyán, L. Dóra, and I. Vajda. Statistical wormhole detection in sensor networks. In Second European Workshop on Security and Privacy in Ad hoc and Sensor Networks (ESAS) July 2005.

Digital Library

[6]

I. Cervesato, C. Meadows, and D. Pavlovic. An encapsulated authentication logic for reasoning about key distribution protocols. Computer Security Foundations, 18th IEEE Workshop June 2005.

Digital Library

[7]

J. Clulow, G. P. Hancke, M. G. Kuhn, and T. Moore. So near and yet so far: Distance-bounding attacks in wireless networks. In Third European Workshop on Security and Privacy in Ad hoc and Sensor Networks (ESAS) September 2006.

Digital Library

[8]

J. Eriksson, S. V. Krishnamurthy, and M. Faloutsos. Truelink: A practical countermeasure to the wormhole attack in wireless networks. In ICNP'06. Proceedings of the 2006 14th IEEE International Conference on Network Protocols November 2006.

Digital Library

[9]

G. Hancke and M. Kuhn. An RFID distance bounding protocol. In Conference on Security and Privacy for Emerging Areas in Communication Networks -- Secure Comm 2005 September 2005.

Digital Library

[10]

G. P. Hancke. Practical attacks on proximity identification systems (short paper). pages 328--333, May 2006.

Digital Library

[11]

G. P. Hancke and M. G. Kuhn. Attacks on time-of-flight distance bounding channels. In WiSec'08: Proceedings of the first ACM conference on Wireless network security April 2008.

Digital Library

[12]

Y. Hanna, H. Rajan, and W. Zhang. Slede: a domain-specific verification framework for sensor network security protocol implementations. In WiSec'08: Proceedings of the first ACM conference on Wireless network security April 2008.

Digital Library

[13]

C. He, M. Sundararajan, A. Datta, A. Derek, and J. C. Mitchell. A modular correctness proof of IEEE 802.11i and TLS. In CCS'05: Proceedings of the 12th ACM conference on Computer and communications security October 2005.

Digital Library

[14]

L. Hu and D. Evans. Using directional antennas to prevent wormhole attacks.In Symposium on Network and Distributed Systems Security (NDSS) February 2004.

[15]

Y.-C. Hu, A. Perrig, and D. B. Johnson. Packet leashes: A defense against wormhole attacks in wireless networks. In IEEE Conference on Computer Communications INFOCOM April 2003.

[16]

R. Maheshwari, J. Gao, and S. R. Das. Detecting wormhole attacks in wireless networks using connectivity information. In IEEE Conference on Computer Communications INFOCOM May 2007.

Digital Library

[17]

C. Meadows, R. Poovendran, D. Pavlovic, L.-W. Chang, and P. Syverson. Distance bounding protocols: Authentication logic analysis and collusion attacks. In Secure Localization and Time Synchronization for Wireless Sensor and Ad Hoc Networks Springer-Verlag, Series: Advances in Information Security, Vol. 30.

[18]

J. Munilla, A. Ortiz, and A. Peinado. Distance bounding protocols with void-challenges for RFID. In Printed handout at the Workshop on RFID Security, RFIDSec 06, Ecrypt July 2006.

[19]

S. Nanz and C. Hankin. A framework for security analysis of mobile wireless networks. Theoretical Computer Science 367(1):203--227, 2006.

Digital Library

[20]

P. Papadimitratos, Z. Haas, and J.-P. Hubaux. How to Specify and How to Prove Correctness of Secure Routing Protocols for MANET. In IEEE-CS Third International Conference on Broad Band Communications, Networks, and Systems October 2006.

[21]

P. Papadimitratos, M. Poturalski, P. Schaller, P. Lafourcade, D. Basin, S. Čapkun, and J.-P. Hubaux. Secure neighborhood discovery: A fundamental element for mobile ad hoc networking. IEEE Communications Magazine Vol. 46, No. 2, February 2008.

Digital Library

[22]

Dusko Pavlovic and Catherine Meadows. Deriving secrecy properties in key establishment protocols. In Dieter Gollmann and Andrei Sabelfeld, editors, Proceedings of ESORICS 2006 volume 4189, September 2006.

Digital Library

[23]

R. Poovendran and L. Lazos. A graph theoretic framework for preventing the wormhole attack in wireless ad hoc networks. Wireless Networks 13(1):27--59, 2007.

Digital Library

[24]

M. Poturalski, P. Papadimitratos, and J-P. Hubaux. Secure Neighbor Discovery in Wireless Networks: Formal Investigation of Possibility. In ASIACCS'08: Proceedings of the 3rd ACM symposium on Information, computer and communications security March 2008.

Digital Library

[25]

M. Poturalski, P. Papadimitratos, and J-P. Hubaux. Towards provable secure neighbor discovery in wireless networks. Technical Report LCA-REPORT-2008--025, EPFL, October 2008.

Digital Library

[26]

Kasper B. Rasmussen and Srdjan Čapkun. Implications of radio fingerprinting on the security of sensor networks. In Proceedings of IEEE Secure Comm September 2007.

[27]

J. Reid, J. M. Gonzalez Nieto, T. Tang, and B. Senadji. Detecting relay attacks with timing-based protocols. In ASIACCS'07: Proceedings of the 2nd ACM symposium on Information, computer and communications security March 2007.

Digital Library

[28]

D. Singelée and B. Preneel. Distance bounding in noisy environments.In Fourth European Workshop on Security and Privacy in Ad hoc and Sensor Networks (ESAS) July 2007.

Digital Library

[29]

S. Čapkun and J. P. Hubaux. Secure Positioning in Wireless Networks.IEEE Journal on Selected Areas in Communications (JSAC)24(2): 221--232, 2006.

Digital Library

[30]

Srdjan Čapkun, Levente Buttyán, and Jean-Pierre Hubaux. SECTOR: secure tracking of node encounters in multi-hop wireless networks. In SASN'03: Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks October 2003.

Digital Library

[31]

W. Wang and B. Bhargava. Visualization of wormholes in sensor networks.In WiSe'04: Proceedings of the 2004 ACM workshop on Wireless security October 2004.

Digital Library

[32]

S. Yang and J. S. Baras. Modeling vulnerabilities of ad hoc routing protocols. In SASN'03: Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks October 2003.

Digital Library

Cited By

S DD PP A(2019)Secure Neighbour Discovery: Secure k-Nearest ROUTING AD-HOC Networking Using Diffie-Helman and HIGHEST Connectivity AlgorithmJournal of Communications10.12720/jcm.14.3.164-169(164-169)Online publication date: 2019
https://doi.org/10.12720/jcm.14.3.164-169
Ehdaie MAlexiou NAttari MAref MPapadimitratos P(2015)Key splittingSecurity and Communication Networks10.5555/2914534.29145438:3(431-445)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.5555/2914534.2914543
Zhang RSun JZhang YHuang X(2015)Jamming-Resilient Secure Neighbor Discovery in Mobile Ad Hoc NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2015.243968814:10(5588-5601)Online publication date: Oct-2015
https://doi.org/10.1109/TWC.2015.2439688
Show More Cited By

Towards provable secure neighbor discovery in wireless networks
1. Networks
  1. Network types

Recommendations

Secure neighbor discovery in wireless networks: formal investigation of possibility
ASIACCS '08: Proceedings of the 2008 ACM symposium on Information, computer and communications security

Wireless communication enables a broad spectrum of applications, ranging from commodity to tactical systems. Neighbor discovery (ND), that is, determining which devices are within direct radio communication, is a building block of network protocols and ...
Formal Analysis of Secure Neighbor Discovery in Wireless Networks

We develop a formal framework for the analysis of security protocols in wireless networks. The framework captures characteristics necessary to reason about neighbor discovery protocols, such as the neighbor relation, device location, and message ...
Improved Secure Neighbor Discovery Protocol (ISEND) for New Wireless Networks Generations
ICETE 2014: Proceedings of the 11th International Joint Conference on e-Business and Telecommunications - Volume 6

In charge of several critical functionalities, the Neighbor Discovery Protocol (NDP) is used by IPv6 nodes to find out nodes on the link, to learn their link-layer addresses to discover routers, and to preserve reachability information about the paths ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FMSE '08: Proceedings of the 6th ACM workshop on Formal methods in security engineering

October 2008

70 pages

ISBN:9781605582887

DOI:10.1145/1456396

Program Chair:
Vitaly Shmatikov
The University of Texas at Austin, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS08

Sponsor:

CCS08: 15th ACM Conference on Computer and Communications Security 2008

October 27, 2008

Virginia, Alexandria, USA

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
437
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

S DD PP A(2019)Secure Neighbour Discovery: Secure k-Nearest ROUTING AD-HOC Networking Using Diffie-Helman and HIGHEST Connectivity AlgorithmJournal of Communications10.12720/jcm.14.3.164-169(164-169)Online publication date: 2019
https://doi.org/10.12720/jcm.14.3.164-169
Ehdaie MAlexiou NAttari MAref MPapadimitratos P(2015)Key splittingSecurity and Communication Networks10.5555/2914534.29145438:3(431-445)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.5555/2914534.2914543
Zhang RSun JZhang YHuang X(2015)Jamming-Resilient Secure Neighbor Discovery in Mobile Ad Hoc NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2015.243968814:10(5588-5601)Online publication date: Oct-2015
https://doi.org/10.1109/TWC.2015.2439688
Shyry SRangan PJayaraman B(2014)Novel Enhanced Encryption Algorithm for Shared Key GenerationProceedings of the 2014 International Conference on Interdisciplinary Advances in Applied Computing10.1145/2660859.2660953(1-7)Online publication date: 10-Oct-2014
https://dl.acm.org/doi/10.1145/2660859.2660953
Bartolini NBongiovanni GLa Porta TSilvestri S(2014)On the Vulnerabilities of the Virtual Force Approach to Mobile Sensor DeploymentIEEE Transactions on Mobile Computing10.1109/TMC.2014.230820913:11(2592-2605)Online publication date: Nov-2014
https://doi.org/10.1109/TMC.2014.2308209
Arnaud MCortier VDelaune S(2014)Modeling and verifying ad hoc routing protocolsInformation and Computation10.1016/j.ic.2014.07.004238:C(30-67)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.ic.2014.07.004
Ehdaie MAlexiou NAttari MAref MPapadimitratos P(2014)Key splitting: making random key distribution schemes resistant against node captureSecurity and Communication Networks10.1002/sec.9918:3(431-445)Online publication date: 31-Mar-2014
https://doi.org/10.1002/sec.991
Fiore MCasetti CChiasserini CPapadimitratos P(2013)Discovery and Verification of Neighbor Positions in Mobile Ad Hoc NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2011.25812:2(289-303)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1109/TMC.2011.258
Poturalski MPapadimitratos PHubaux J(2013)Formal Analysis of Secure Neighbor Discovery in Wireless NetworksIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2013.1710:6(355-367)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1109/TDSC.2013.17
Sejun Song Haijie Wu Baek-Young Choi (2012)Statistical wormhole detection for mobile sensor networks2012 Fourth International Conference on Ubiquitous and Future Networks (ICUFN)10.1109/ICUFN.2012.6261721(322-327)Online publication date: Jul-2012
https://doi.org/10.1109/ICUFN.2012.6261721
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten