Secret Common Randomness From Routing Metadata in Ad Hoc Networks

Automatic key establishment between two devices in a network is generally performed either by public-key-based algorithms or by encrypting the newly-generated key with a special key-wrapping key.

However, in addition to the well-established, well-investigated keying information exchange, one additional aspect of key establishment is often understated: to ensure the security of the application it serves, the newly generated secret key has to be truly random.

While minimum standards for software based randomness quality are generally being enforced, many applications rely on often costly hardware-based true random generators. Sources of randomness employed by true random number generators vary from wireless receivers and simple resistors to ring oscillators and SRAM memory.

Secret Common Randomness

Establishing secret common randomness between two or multiple devices in a network resides at the root of communication security. In its most frequent form of key establishment, the problem is traditionally decomposed into a randomness generation stage (randomness purity is subject to employing often costly true random number generators) and an information-exchange agreement stage, which relies either on public-key infrastructure or on symmetric encryption (key wrapping).

A secret-common-randomness establishment algorithm for ad hoc networks generally works by harvesting randomness directly from the network routing metadata, thus achieving both pure randomness generation and (implicitly) secret-key agreement.

Using Mobile Ad-hoc Networks

A readily available source of randomness is usually neglected: the network dynamics. Indeed, by their very nature, networks are dynamic and largely unpredictable. Their randomness is usually evident in easily-accessible networking metadata such as traffic loads, packet delays or dropped-packet rates.

However, as the main focus of our work is on mobile ad-hoc networks (MANETs), the source of randomness we shall discuss in this paper is one that is specific to infrastructure-less networks: the routing information itself.

Another interesting feature of the routing information, in addition to its randomness, is that it can easily be made available to the devices that took part in the routing process, but it is usually unavailable to those devices that were not part of the route.

This idea opens the door to a whole new class of applications: with the proper routing protocol, the routing information could be used for establishing secret common randomness between any two devices in a mobile ad-hoc network. This common randomness could then be further processed into true common randomness, and used as secret keys.

MANET

Mobile ad-hoc networks (MANETs) consist of mobile nodes communicating wirelessly with each other, without any pre-existing infrastructure. We consider a bidirectional MANET employing dynamic source routing (DSR), in which the nodes (corresponding to the mobile devices of the network’s users) are moving in a random fashion in a predefined area. The bidirectional network assumption is usually a practical one, especially when all the nodes in the network belong to the same class of devices (e.g. smart phones).

Conclusion

An algorithm for secret common randomness from Routing Metadata in Ad Hoc networks relies on the route discovery phase of an ad hoc network employing the dynamic source routing protocol, is lightweight, and requires relatively little communication overhead.

The algorithm is evaluated for various network parameters in an OPNET ad hoc network simulator. It has been studied that, in just 10 min, thousands of secret random bits can be generated network-wide, between different pairs in a network of 50 users.

Future Work

The randomness inherent in an ad-hoc network can be harvested and used for establishing shared secret keys. For practical network parameters, it has been studied that after only ten minutes of use, thousands of shared secret bits can be established between various pairs of nodes.

While the study is based on the entire-network level, a better option might be to let each one of the pairs of nodes decide whether using the spoiling knowledge technique is advantageous or not.

The number of achievable shared secret bits can be further increased by devising a more efficient partition algorithm for the generation of full-route subsets with a security property, instead of the naıve algorithm.

The randomness in the Traffic load and Network’s connectivity are still untapped and are a subject to work on it further.