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" <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED]