New Algorithm Builds Encryption Keys from Wireless Network Metadata

One of the best problems in computer science is randomness. Random numbers underlie so much of what we do with computers, from the simplest games to the most advanced cryptography, yet computers are by definition/design non-random. Computers are deterministic—for most applications we do indeed prefer that they return the same answer for the same question, every time.

So, finding the best randomness often means looking beyond computers and instead at the natural world, which seems to achieve something much, much closer to randomness and with little effort in the forms of thermal fluctuations and atmospheric noise, for example. This sort of nature-harvested randomness isn't perfect, but it also isn't created by a human-designed deterministic algorithm.

Researchers from Iowa State University have developed an interesting new approach to the problem of randomness that doesn't have to leave the bounds of a computational system (e.g. doesn't have to resort to nature) yet still manages to come up with random numbers that can't be reverse engineered. Their algorithm, which is described in a forthcoming edition of IEEE Transactions on Information Forensics and Security, finds its randomness lurking in residual metadata from network routing protocols. Network dynamics is noisy as hell.

A packet traveling from some start node in a network—say an ad hoc network of mobile devices—follows a deterministic path to its destination, which is calculated based on a variety of factors. In the specific sort of network routing protocol examined by the Iowa State researchers, called dynamic source routing (DSR), this routing information is contained within each individual packet. Which is unusual and specific to wireless mesh networks. (Routing data is more typically contained in "next-hop" tables loaded onto individual routers.)

If our packets are getting from place to place in a deterministic fashion (the mechanics of how exactly the route is calculated aren't too important), how do we get to the hardcore randomness we're after? It's easy enough to see: A wireless mesh network consists of nodes that are constantly changing their positions relative to one another. So, every time a new route needs to be calculated through this bobbing sea of nodes, it calculates that route based on a new underlying network architecture—there is no pre-existing network infrastructure. The routing information guiding a packet is a snapshot of that network as it changes through time.

As such, we can't really take the network in question at some future time and use it to recreate the network and a particular route through it at a previous time. Which is more or less what random is.

Of course, routing information is available to that network at the time it's valid, so the randomness generated by this method isn't entirely secret. The researchers argue that this actually works in their favor as it results in a built-in way mechanism for "shared randomness," e.g. random keys that are known only to a few users. As one might expect, shared randomness—where message recipient Bob and message sender Alice each have a copy of some pad of random numbers—can be very useful for cryptography.

Finally, the researchers tested their algorithm out in simulated network conditions. The results are impressive: "In just 10 minutes, thousands of secret random bits can be generated network-wide, between different pairs in a network of 50 users," they report.

Naturally, the next step in evaluating the algorithm is trying to hack it. Stay tuned.