A National ID

[Joseph Ashwood]

Although I am against any national ID, at least as far "terrorist
identification" goes (note that the Social Security Number that every
American has IS a national ID card), I feel that a discussion on how to do
it properly is a worthwhile endeavor.

----- Original Message ----- 
From: "Peter Clay" <pete at flatline.org.uk>
Subject: Re: A National ID


> [T]he real danger is not the cards but the database for which they
> are a unique key. See just about every issue of RISKS for ways in which
> big national databases can go wrong.

The solution then is obvious, don't have a big central database. Instead use
a distributed database. I first suggested this concept some time ago on
sci.crypt. It's very simple, use cryptography so we don't have to be
concerned about duplication (although fraudulent acquisition of valid id
would be an issue). Issue each person a Flash RAM card, on the card is
biometric information, name, birthdate, etc, a Law Enforcement Only Field,
and a signature across all the information, most importantly DO NOT print
anything resembling what we currently see as an ID card (no picture, no
drivers license number, etc) just print a name on the card for ease of card
identification. At this point (assuming the cryptography is good) people can
make as many copies as they'd like, it's not going to make any difference.

The Law Enforcement Only Field (which I'll call LEAF for historical reasons)
serves a unique purpose, it is either a random number, or an encrypted old
identity. There are several possible reasons for the old identity;
undercover police, witness protection, support for pseudo-nyms, etc. This
field allows the police and only the police to identify undercover officers,
and provides tracability back through the process to identify granting a new
identity to someone.

The most important part though is the search time required for verifying an
ID. In the case of a giant central database it is O(log(n)) time, with the
cryptographic ID it is O(1). This reduces the cost of the national overhead,
while a database is still necessay for reissuing, and a new signing setup is
required, the access requirements are reduced by several orders of
magnitude. Further reduction comes from the ability of each police precinct
to have their own local "known" database, as well as every bar/nightclub
having their own banned list without the possibility of cross-corruption,
because there is no direct link. This further increases the security because
access to the main database can even be restricted to key personnel. This
personnel access reduction will again lower the speed requirements for the
central database, probably down to the point where a single Oracle server
with a few Terabytes of disk space could easily handle the load (I come up
with a horrible case size of about 300 Terabytes, and a minimum size of 70
gigabytes for storing only the signature and LEAF because everything else
can be reconstructed). (Sizes assume 1MB maximum data set, and DSA/ECDSA
with SHA-512)

This would also have a knock-on effect of creating a small ID customization
industry, because the ID can take any form-factor within certain reasonable
bounds there is no reason that it cannot be as customizable as a cell-phone.

As for security, this would put the citizen in general control of their
information, and with the minimum database size used would give the citizen
complete control over their own data. The additional overhead for the
current law enforcement databases would be minimal, each entry would only be
expanded by the size of the signature to mark the ID card.

The invasiveness for your average citizen would be minimized because there
is no chance of leakage between the big central database (which could be
very small) and the corner market, because the central database does not
have to be online.

Now as to the level of cryptographic security that would be necessary for
this. It is important to realize that the potential market for fraudulent ID
of this caliber would be massive, so a multi-decade multi-trillion dollar
effort to break the key is not unreasonable. This poses a risk of a
magnitude that cryptanalysts really haven't dealt with. Even at the level of
protecting the drivel from Shrub II, the possibility of a multi-decade,
multi-trillion dollar is simply inconceivable, and it is important to
remember that this signature has to remain secure not for a few years, or
even a couple of decades, it has to remain secure for longer than the
longest concievable lifespan for a human, which means 150 years (I've
rounded up from the record), which is a timeframe that we cannot even
conceive of at this time. A 100 trillion dollar, 150 year effort to break
the security is simply beyond our ability to predict cryptographically, with
Celerons at about $35 per GHz right now, that timeframe works out to
approximately 2^95 (again being generous to the attacker), that already
means that SHA-1 cannot be used simply because the workload is available to
defeat it. With just the march of Moore's law we would need >2^235 security,
SHA-512 simply isn't big enough. To have any safety margin at all would
require something like SHA-1024. Going further combatting the probability of
Quantum Computers would require something like SHA-2048, but now we're
getting into absolutely absurdly sized numbers. The only way to combat this
would be to accept a small number of fraudulent users and replace cards
every couple decades which would limit the requirements to an immediate
2^128 and a movement to 2^256 within a couple decades. The down side of this
is that we quickly end up exactly where we are now, even if the entire
population is cleaned of fake IDs, once the reissue starts happening we'll
see fake IDs creep up again.

Certain people may contend that if we force ID renewal on everyone at the
same time, that this simply won't happen. That is true, iff you succeed in
forcing EVERYONE to switch on the switch date. Let's face it, I look old
enough that no one doubts if I'm old enough to drive, no one doubts if I'm
old enough to buy wine, no one would doubt that I'm old enough to buy
cigarettes, so I will only be carded if pulled over by the police, which can
be avoided by simply not driving, I could live with my current ID for the
next 50 years and not have any real problem (the oldest expired license I've
heard of in active use was 47 years expired, so this is not unreasonable to
attempt) the security MUST be good for at least 50 years, and preferably 100
(at 100 years of age the field of options is narrow enough that they can be
a special case), that once again leaves us in the "we simply don't know how
to do it" stage.

The security requirements for a proper installation are so high that we
simply cannot do it, we can do better than we have now, and make it
extremely costly for the fake manufacturers, but the security problem is
simply too hard.
                    Joe

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