In the wake of the ChoicePoint
debacle, people are starting to think about how to stop
It's not an easy problem, though, because almost all the information
that you use to establish your identity is publicly known, especially
in the age of Google.
In particular, the social security number (SSN), while ostensibly
secret, is trivial to get your hands on because everyone from
the DMV to your credit card company to your doctor's office wants
to know it.
The basic problem with SSNs as a proof if identity is that they're
used for two purposes:
- Authenticator—because it's ostensibly secret, lots
of organizations use your knowledge of your SSN as evidence that
you're you. This only works if not many other people know your SSN.
- Record lookup keys—the SSN is the only unique identifier that
pretty much every American has, so it makes a pretty much ideal
storage and lookup key. But this leads to everyone knowing it,
a problem which is made even worse when databases that contain
SSNs get stolen.
This is obviously a bad mix of properties and it's at least partially
responsible for the identity theft problem. The good news is that
there's a standard fix in cryptographic protocols: public key
Public Key Approach
Every user (in this case, American citizen) gets
an asymmetric key pair. You use the public key as the lookup key
and the private key is the authenticator. The user performs a
digital signature to prove that it knows the private key.
Of course, this has some obvious problems for this particular
application. The most serious of these is that it requires
users to have a computer in order to prove their possession
of the private key—digitally signing is a pretty
complicated operation, far too complicated to do by hand.
An additional problem is that the database lookup keys get
large (at least 160 or so bits), which requires very extensive
modification to existing systems.
There's a sloppier solution, though: instead of using digital
signatures you use hash functions. Here's the simple approach:
the authenticator is some random value X. The lookup
key is L=Hash(X). In order to let people look up your
records, you just give them Hash(X). This is all
you need for your doctor's office, the DMV, etc.
For things like credit card applications, you need to
authenticate. In order to do this, you provide X.
The credit card agency (or whatever) computes Hash(X)
and verifies it against L. If it matches, you're you.
This strategy has two good features:
- You don't need to give your authenticator to everyone, just
people who are trying to verify your identity.
- People who verify your identity don't need to store your
authenticator—they can discard it as soon as they've verified
it, so they're not as at risk from database theft.
However, it's still not very good. You may not be giving L
out to everyone, but you're still giving it out to plenty of
people, so there's still a fairly high risk of compromise.
And since there's only one authenticator, you can't really
recover from that without changing L in every database
on the planet. A second problem is that L is a lot longer than your
average SSN, so it will still require retooling all the back-end
I've been doing some thinking, though, and I think there's a
hack that might get us most of the way there. Every year
the SSA sends you a set of pre-signed authentication tokens,
each good for a single month. These tokens are simply digitally signed
versions of your SSN, e.g., Sign(SSN, Month). When you
want to authenticate yourself, you provide the current token.
In order to verify it, the verifier checks the digital signature
and verifies that the token isn't expired. If both check out,
then you've been authenticated.1
This strategy has one really nice feature: because the
tokens are signatures over the SSN, no changes are required
to the back-end database, which can continue to use
SSNs as before. The only changes are required to the verification
procedure. Systems which use the SSN only as a locator
don't have to change at all, which is obviously attractive.
There are also some drawbacks. First, the authentication tokens
are fairly large. Even the smallest signature schemes are a lot
longer than an SSN. E.g., BLS is
160 bits (26 or so base 64-encoded characters) at the 80 bit security
level. This makes them fairly difficult to read over the phone and
even harder to memorize. Second, since they're only good for
a month or so, you're not going to want to memorize them. On
the other hand, you won't need them anywhere as often as you need
your SSN, so it's not quite as impractical to keep them in a card
in your wallet or whatever. Third, since each token is reusable
during its validity period, there's still some risk if its
stolen. It's possible to do single-use tokens but that requires
some national database of which tokens have been used (or more
likely the hashes of which tokens have been used).
Like I said, this is somewhat half-baked. It's a hack
designed to improve security while not requiring
too many changes to existing infrastructure. Sometimes hacks
like these hit the sweet spot and sometimes they're
the worst of both worlds. I can't decide which this one is.
1. Note that you don't need to provide the
month with the token. The verifier can just check the token
against the current valid month.