On Tue, Apr 18, 2000 at 10:52:42PM -0500, Declan McCullagh wrote: > I have no idea if this U.are.U system is any good, but it strikes me that > the below objection to such a device in principle is off-base. > > The data provided by the fingerprint reader would become the passphrase, > assuming they were rich and reliable enough and satisfied the usual other > criteria. You claim it would "be compared against a known template," but > such a system would not necessarily have to be designed in that way. When I was working with biometrics vendors to do smartcard access via biometrics, they all said that it had to work that way. Perhaps they were too limted in their thinking. > A finger can change, so perhaps the key can be encrypted with multiple > "near matches" and those copies also stored. Ok, that sounds like a reasonable idea. Let's examine it. The fingerprint system I have worked the most with would return a template of between 10 and 20 minutae, usually closer to 20 if it got a good scan. The data in the template were simply points on a graph that described the location of the minutae. Some other algorithim decided what the minutae points were, and aligned the fingerprint so that the minutae points would be aligned. There's no way to tell what's a valid minutae and what is a cut or piece of dirt that looks like a valid minutae (actually there are probably lots of ways to tell, but they're not totally accurate- there are always going to be some non-real "minutae"). The match algorithim has an input parameter for the application to choose how many minutae must match for a scan to be considered a match against the template(s). A banking application would set the threshold low (selecting for more false positives and fewer false negatives, thereby locking fewer legit customers out of their accounts) while a physical access application might select a high threshold, accepting more false negatives to prevent false positives. I'd take the U.are.U system to be closer to the banking application end, where false positives are ok and false negatives are not. So let's say that it sets a threshold of 50%, because Digital Persona really doesn't want the $70 cost of a service call when someone's locked out of their files. For an example of how this would work with your scheme, let's assume that you have a scan with 20 points to form the "key". So you need to make a set of keys that each uses 10 points out of the 20 in your "template". You generate those keys, and encrypt the master key in each one, and store those on disk. To decrypt the data, you scan the finger, then use the first 10 points in the scan as a key to attempt to decrypt all the different encrypted master keys. When you succeed in decrypting a master key, then you can use that to decrypt the data. If you run through all the combinations without successfully decrypting a master key, you throw out one minutae from the set of 10 and use one of the remaining ones from the 20 in the scan, and do another search through the master keys. The minutae finding algorithim gives you unique points, and you can sort them in order, to make the number of keys smaller. That still gives 10^10 possible combinations. The minutae points are 4 byte values, so you'd have to hash the 40 bytes down to the key size and then start decrypting the encrypted master keys. You're doing a brute-force type key search which on average has to do (10^10)/2 encryptions... IF one of your first 10 points isn't a "minutae" generated by a piece of dirt, in which case you'd have to do one or more full searches on the entire set of keys. I think that this would be too slow for the application, no matter the algorithim (for 1DES CBC on 8 byte blocks I get about 1000kbytes/sec using openssl on a 500mhz AMDk6 linux box, which would mean about 8000 seconds to decrypt (10^10)/2 16-byte keys... and that's using one DES key, so it's not taking key setup into account). You could use fewer of the minutae in the scan for the key, say 5 out of 20, but the key search is still going to take an unacceptably long time. You could re-tune the biometric algorithim that finds the minutae to be more selective, i.e. returns fewer minutae. However if you go too far in that direction the false negative and false positive rates go up (because a single cut or blob of dirt that looks like a minutae is now a greater percentage of the total number of "minutae"). The systems I've dealt with were working hard on reducing the false positive/false negative rates. It's possible that tuning it to recognize fewer minutae would help for a U.are.U type application, at the cost of making it less useful for more traditional biometric uses. The system I worked with most did not allow tuning that algorithim, nor did the others who's developers I talked to (but that doesn't meant that it's not possible). Another possibile improvement would be to include a quality metric with each minutae. The system I worked most with could return a quality metric for the entire scan but not per minutae. With a per-minutae quality metric, you could then select the best minutae for the keys and for the keysearch. That could reduce the number encryptions needed for the search. The many-keys system also means that there has to be recognizeable plaintext in each encrypted master key to make the brute-forcing faster. Ideally you'd only want to decrypt one block. That known plaintext then makes a regular brute-force attack easier, although this probably isn't much of a security problem since there are usually ways to find known plaintext anyhow. > Perhaps it could also warn you > that your aging, saggy, scarred finger is getting close to the limit and > ask you to rescan (perhaps requiring more security). But to do that you'd have to keep a template to compare against, which your scheme was avoiding... > In other words, I can envision a system that would work without suffering > the objections you outlined. It's a good idea, but I think that it would be too slow, at least with biometric systems that resemble the ones that I looked at and worked with last year. > Perhaps those with real-world experience in > this area can join in. My real-world experience is with using fingerprint biometrics to unlock smartcards, which is a slightly different problem but gave me exposure to how some biometrics work. The vendors kept the minutae-selection and matching algorithims secret however. I'd be glad to hear how I'm wrong from someone from Digital Persona or anyone who's built a system similar to U.are.U. My thoughts are only conjecture based on what experience I have, and I don't have first-hand knowledge of how U.are.U works. -- Eric Murray www.lne.com/~ericm ericm at the site lne.com PGP keyid:E03F65E5
