« The Prilosec shortage | Main | Initial notes on FreeBSD on the Panasonic W-2 »

February 23, 2005

A half-baked proposal for reducing identity fraud

In the wake of the ChoicePoint debacle, people are starting to think about how to stop identity theft. 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:

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 cryptography.

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.

Hash functions
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:

  1. You don't need to give your authenticator to everyone, just people who are trying to verify your identity.
  2. 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 systems.

Signed Authenticators
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.

Posted by ekr at February 23, 2005 8:35 PM | Filed under:

Comments

One way to ease the pain of the hash length would be to use the approach taken by S-Key, and encode it into a small number of easily-remembered words.

Posted by: Chris Walsh at February 24, 2005 12:04 AM

What I find a lot of companies are doing is using personal information (mother's first name, birthplace, predetermined question, etc.) for authentication. This is similar - if only in function - to what Chris mentioned.

Posted by: Andrew at February 24, 2005 1:46 AM

Andrew,

The problem with personal information is that there are only a few such items and so you have the same database theft problem as before. (You could store a hash but then you are really brittle in the case of data entry errors). Also, it's getting a lot easier to determine things like mother's name and birthplace with Google.

Posted by: EKR at February 24, 2005 6:52 AM

I'd suggest that we step back and ask, for what kinds of transactions do we really need to prove our identity? And for which transactions will be be harmed if someone else impersonates us?

I think the main ones are financial: opening bank accounts, getting credit cards. Especially risky are situations where you get credit, because then you get badly burned if someone borrows money in your name and doesn't pay it back.

So I would work in the direction of making it harder to open credit accounts. Don't do it over the phone; don't do it by mail. I realize the credit card companies aren't going to like this, but the system we have now is untenable.

Wouldn't it be great to be able to opt out voluntarily of being able to open credit accounts easily? To get out of the whole identity-theft system? You'd publish a record somewhere that banks would see, that says don't open a credit account in my name on the basis of knowing information about me. I will not be responsible for any debts incurred in that way.

Then, when you did want credit, you'd have to do something more difficult. Maybe (horrors) you'd actually have to physically show up at the bank and identify yourself. Yes, and possibly even use biometrics to make it reliable. It's your own livelihood that you are protecting by such measures.

Posted by: Cypherpunk at February 24, 2005 9:51 AM

One point about the failings of SSNs as an identifier—they aren't unique.  At a former employer I found collisions in a database of only a few tens of thousands of active users (inactive was worse), some because of identity fraud but many because the SSA has inadvertently issued duplicates many times.  Anyone assuming SSNs are unique is in for a rude awakening…

Posted by: Jonathan Conway at February 24, 2005 3:29 PM

Here's an extreme solution: do away with the facade of SSNs as secret identifiers by having the SSA publish all SSNs online. This would force entities that consider SSNs secret to rethink their methods.

The SSA could give everyone a year before they publish, for example, to change the way they do business.

Posted by: Pete at February 25, 2005 7:12 AM