Date: October 2, 2002
Story: Plastic tag makes foolproof ID
Subject: Physical cryptography
In February and March this year, I was lucky enough to visit MIT on sabbatical. On asking whether there was any radical new work in the security field, I was directed to Ravi Pappu's thesis. The following paper is based on that work.
The forgery of high-value objects, from banknotes through perfumes to consumer electronics, costs industry (and government) billions of dollars. When it extends to products such as drugs and aircraft parts, it can also cost lives. Traditional countermeasures, such as seals and security printing, have their limitations; they need to be integrated with audit, testing and inspection systems in order to be really effective. Automating this is hard, and we could do with new technological ideas.
There have been a number of attempts to combine cryptographic authentication mechanisms with the physical randomness of materials so as to make objects that are extremely difficult to forge. One of the early ideas came from Sandia National Laboratories in the mid-1980s. Banknote paper would be impregnated with chopped-up optical fibres, creating a speckle pattern under appropriate illumination; a digitally signed version of this would be printed in a barcode on the side of the note. The combination of a cryptographic seal with physical randomness might give the forger a really serious headache. At the time, however, this idea could not be made to work properly; the fibres then available were too fragile and the speckle pattern degraded rapidly when the note was circulated.
Pappu's work takes a different tack. He embeds hundreds of tiny glass spheres in a clear plastic token, which is then illuminated by a laser to give a speckle pattern that is reduced using a Gabor transform to a 300-byte number. This number can then be used in various security protocols, such as to authenticate its owner to a system. It turns out that tampering with the token - such as drilling a very small hole into it - destroys the pattern.
His team has therefore come up with a new candidate for an optical authentication device, which may provide a useful addition to the security packaging industry's toolkit. But that is not all. As the number read from the token is critically dependent on the precise centre and angle of illumination, it is possible for a single token to be used to authenticate its owner to multiple systems.
This brings us to the second idea in the paper. How can a novel authentication mechanism be brought into the theoretical framework developed by cryptographers over the last quarter century? The answer is to treat it was a one-way function. Such a function, say h, has the property that given an input value x it is easy to compute y = h(x), but given a value z that you have not seen before, it is very hard to find a w such that z = h(w).
The authors of the paper argue from physics that the token can be modeled as a read-only memory containing about 2^40 bits of random data and with a rather slow readback mechanism. Such a device can be used, within limits, as a one-way function.
An ideal one-way function can be visualised as a machine that accepts an input string of any length and outputs a random string of fixed length, say n bits long. Unless we invoke this machine so often that a collision - a pair of different inputs that yield the same output - occurs by chance, then it will be a one-way function in the following sense. Given any input value we can easily compute the corresponding output using the machine, but given an n-bit string that we have not previously been given as an output, we cannot find a corresponding input that would yield that string as an output.
One-way functions have many uses in security, having been used in a primitive form by nineteenth century banks in telegraphic payment systems and in a more modern form since the 1960s for one-way encryption of computer passwords. They are now used by many devices, from remote car door locks to the chips that prevent mobile phones working well with batteries made by the phone manufacturer's ompetitors.
The device invented by Pappu and his colleagues might be used as follows. If its owner bought the right to use a car park twenty times, she might present the token to the car park server which would read it from twenty different random angles $A_i$, storing these values together with the corresponding speckle patterns $P_i$. Later, each time she wanted to pass the barrier, she'd present the token, whose reader would verify that an input angle $A_i$ did indeed give an output of $P_i$. The token can be used for multiple purposes; if it were also used to buy fuel, the garage would interrogate it using different random angles $A'_i$, getting outputs $P'_i$. Unless the token were used an unreasonably large number of times, the set $A_i$, $P_i$ would give no information about the set $A'_i$, $P'_i$ (or vice versa). So if the car-park owner wished to buy fuel on his customers' account, he would have to spend an unreasonably long time reading their tokens from a large number of angles (and would still face the difficult task of manufacturing a forged token that would somehow present the stolen data to the garage's reader in a convincing way). But that part of the security argument we can hopefully abstract away. Thanks to the experience of using one-way functions based on cryptography, we have a reasonable theory of how such mechanisms can be used safely.
So this paper is not just about a better physical seal. It describes a new primitive that can be plugged into our existing security protocol technology to support a wide range of authentication and related services. What's more, its tamper-resistance is based on the physical attributes of a material rather than on cryptologic mathematics. For those who dislike putting all their eggs in one basket, and lie awake at night worrying that quantum computation will make number-theoretic cryptology obsolete, this may be of interest.
Ross Anderson is a reader in security engineering at Cambridge University in England.
Date: July 9, 2002
Just wanted to say thanks for a great site. I especially like having independant researchers give their opinions on a particluar article/area of research. It gives the main researchers more credibility.
Grand Junction, Colorado
Date: May 24, 2001
Story: Prototype shows electronic paper potential
Subject: Electronic paper
This is an interesting product that may indeed have many uses.
I do think that we should hold off on getting rid of our file folders, binders and cabinets because no one will want to sign anything if the piece of paper that it is written on has a 'cut and paste' option. We will be swimming in wood pulp for centuries to come. There will always be a need for a hard copy with a human signature to serve as a backup for security and legal reasons (Just as there will always be data entry clerks, I'm afraid - one of the worst jobs of the information age).
Fredericton, New Brunswick
Submit a letter to the editor.
Read discussions about TRN news stories from forums around the Net.
© Copyright Technology Research News, LLC 2000-2005. All rights reserved.