WASHINGTON, Sept. 19, 2002 — When you send your credit card number over the Internet to pay for a new book or a pair of pants, the number is mathematically disguised — encrypted — so that the original string of digits can be decoded only by the merchant at the other end of your shopping spree. Such encryption is common, but it isn’t entirely secure or practical for all transactions. In Friday’s issue of the journal Science, researchers report a new method that may improve electronic security: a material that “does the math” for encryption.
Like the low-tech wax seals of old, these tokens could become the secure devices used with smart cards — cards with an embedded computer chip that store financial or personal data — as well as with sensors and digital signatures, said authors Ravikanth Pappu of ThingMagic LLC, Neil Gershenfeld of the Massachusetts Institute of Technology’s Center for Bits and Atoms, and MIT graduate students Benjamin Recht and Jason Taylor.
The math formulas used for most modern encryption techniques are called one-way functions. One-way functions are equations that are easy to compute in one direction, but hard to “undo” or compute in reverse. For instance, it’s relatively easy to multiply a series of large prime numbers together, but it’s almost impossible to break down that multiplication product into the original prime numbers.
“Mathematical one-way functions have too many possible inputs to feasibly find the one that matches a given output,” said Gershenfeld.
One-way functions can also have an “avalanche” property, where a change to one bit of the original output can change about half of the bits in the output. All of these properties make one-way functions excellent encryption tools, because they can compress an arbitrary-length input — like a credit card number or a computer password — into a fixed-length output that can’t easily be “solved” to find the original input.
But such encryption is likely to be increasingly vulnerable to the challenges of advancing technology, according to the Science authors. For instance, quantum computers can already tackle problems like factoring small numbers in real time, and massive networks of computers can be used to crack previously safe codes. From a practical standpoint, it’s also difficult and expensive to assemble the necessary computing technology required to perform one-way functions in objects such as smart cards.
A penny's worth of security
The challenge for the Science researchers was to find a way to exploit the enormous potential of one-way functions using a secure object. Their goal was to create a physical one-way function — an object with a structure that could “perform” such calculations.
In an analogy with the mathematical one-way function, Pappu and colleagues determined that the laser light “input” effectively computes a function of the token’s structure, resulting in a speckle pattern “output.” The speckle pattern can then be converted to a fixed-length string of digits, resembling the output of a classical one-way function.
Since those digits depend on the details of how the token is illuminated by the laser, each token contains an enormous number of possible input-output pairs. Knowledge of any one pair from this huge set won’t help to determine the other possible pairs. This means that the outputs do not need to be reused, and that the behavior of the token can’t be replayed or simulated by an eavesdropper.
“We have about a terabit — a one followed by twelve zeros — of information contained in a penny’s worth of material,” said Gershenfeld.
No tampering, copying, or faking
In practice, the combination of laser light inputs and resulting speckle pattern outputs for each token could be stored on a secure database. The token could then be read at a terminal that queries the database and authenticates the token’s identity.
The tokens appear to be tamper-proof and copy-proof, according to the researchers. Drilling a small hole in the tokens changes their internal structure enough to unleash the avalanche effect, so that the outputs from the same token before and after drilling differ by roughly half of their bits. Yet the process that transforms the speckle pattern into a string of digits can be modified to ignore accidental surface scratches.
Since the output of each token is determined by extremely small variations in its internal structure, it’s not feasible to duplicate in detail the 3-D structure of the token using foreseeable technology, the authors report. Attempts to fake the speckle pattern output using holograms or other optics run into similar problems.
It’s unlikely that the tokens will replace current cryptographic methods for most communications, but they can support those techniques by providing a new, low-cost and secure approach to authentication. However, physical one-way functions may prove to be most useful in providing security for information within physical objects such as smart cards or sensors.
“Smart card security is likely to be the most important application of this technology, but another significant one could be in authenticating a device, rather than just data. For example, a sensor used to monitor a nuclear arms treaty could be encapsulated in the token, so that along with providing its readings, it can prove its identity and demonstrate that it hasn’t been tampered with,” Gershenfeld explained.
“This research illustrates the fact that there is a lot to be gained by treating information and its physical embodiment as a coherent whole,” Pappu said. “Remembering that information is physical often allows us to do things in surprising ways that could not be done using digital systems alone. I expect that physical one-way functions will find application wherever is it important to verify that digital bits and their associated atoms are indeed in the same spatial location and haven’t been tampered with.”
Gershenfeld said that his team was a little worried that traditional cryptographers might resent the intrusion on their turf, but that the response has been “quite the opposite.” Many researchers have welcomed the addition of this physical mechanism as a new way to provide cryptographic security.
“Cryptosystems don’t protect information if they’re not used. The introduction of physical one-way functions greatly expands where, and how, information can be protected,” the Science authors concluded.
© 2013 American Association for the Advancement of Science