Preventing wormhole attacks on wireless ad hoc networks: A graph theoretic approach

We study the problem of characterizing the wormhole attack, an attack that can be mounted on a wide range of network protocols without compromising any cryptographic quantity or network node. Making use of geometric random induced by the communication range constraint of the nodes, present the necessary and sufficient conditions for detecting defending against wormholes. Using our theory, we also present a defense mechanism based on local broadcast keys. We our work is the first one to present analytical calculation of probabilities of detection. We also present simulation results illustrate our theory.