unforgeable optical tokens?

[Sidney Markowitz]

Perry E. Metzger <perry at piermont.com> wrote:
> But if you can't simulate the system, that implies that the challenger
> has to have stored the challenge-response pairs because he can't just
> generate them, right? That means that only finitely many are likely to
> be stored. Or was this thought of too?

The section on replay attacks in Pappu's PhD thesis only addresses what an
adversary could do given some free access to the device, presumably for a
finite time after which the device is returned to the owner. Pappu
demonstrates that it is not feasible to extract and store sufficient
information to either have all possible challenge/response pairs available
or to be able to compute them with a simulation.

That does not address the issue that the challenger also does not have
access to the full range of challenge/respones, and so has to keep a
feasibly small number of them as secrets. This is more secure than a shared
secret, because the token owner does not need to know which challenges the
challenger has stored, so an adversary can only obtain them from the
challenger. If the same challenge/response pair is given to two challengers,
then either one could forge authentication of the identity of the token's
owner. On the other hand there are so many possible challenge/response pairs
that there is no need to give the same ones to two people. In fact Pappu
describes a protocol in which challenge/response pairs are never reused. It
means that challengers can believe the authentication to the degree that
they believe that they have kept their copy of the challenge/response pairs
secure and that the token is in the physical possession of the right person
at the time the challenge/response is exchanged.

Pappu characterizes the device as a "physical one-way hash function". Given
a random challenge that is not known in advance, producing the proper
response proves that one has posession of a particular physical token. It
does not break security to lend the token to someone so that they can store
a bunch of challenge/response pairs for future use in having you
authenticate yourself to them.

Figuring out how to use this for digital signatures or asymmetric encryption
looks like a challenge: Unlike algorithmic one-way hash functions, the only
way to compute the function is to have physical posession of the device: Bob
does not get to confirm Alice's result unless the protocol involves Alice
lending or giving Bob her token. Pappu's example of a bit commitment
protocol (page 128 of his thesis) involves Alice picking a random token from
a pile and handing it to Bob.

The thesis has a section on digital signatures, but all that does is
describe how algorithmic one way hash functions are used to sign messages,
not how the physical one-way hash function could be used for that. Since the
only way to compute the hash is to have physical access to the device,
verification of a signature would require one to be able to submit a
challenge to the device and read back the response. This brings up all sorts
of questions such as how the challenger verifies that the device is the
correct signing token and is functioning properly, as well as how to prevent
the challenger from using their temporary access to the device to generate a
signature for any message they wish. Whether or not this device can be used
for digital signatures, how to do it is never addressed in the thesis.

 -- sidney



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com