Can it be done? Securing physical badges with cryptography

Question

I need to hand out physical access cards to a group of people. My main objective is to guarantee at every location where this cards will be checked that no information in the card has been modified. I print those cards so I have all the user information (name, lastname, ID number, etc).

My idea is to use some sort of algorithm to input all this data and generate a maximum of 15-20 digit barcode that I can print in the card.

The cards will be checked using scanners similar to those used for passport control, which means that the operator will have the ability to obtain all the information in the card by OCR. Without distributing my input algorithm (and risking someone else being able to replicate it), is there a way to have him check that no information has been modified on the card?

I'm open to all suggestions regarding my need as nothing is implemented yet. However, I cannot connect the verification points with a central server for checking, they are remote locations with no internet. The cards should hold data on themselves that allows to verify that no data has been modified. The cards don't have chips or magnetic stripe, so I'm locked to using OCR.

Any solutions?

Thanks in advance!

Answer 1

This is actually a fairly standard cryptographical problem, with standard solutions.

The easiest solution would be to use a Message Authentication Code; this is a function that takes a key and a message (in your case, the text on the badge), and produces a random-looking code. What you would do is initially pick a random key, and give that key to both the guy producing the badges, and also install it into the scanner. When you create the badge, you take the text and the key, send it through the MAC, and generate a value, which you also put on the badge. When the scanner reads the badge, it takes the text it reads (excelt for the MAC value), and the key, send that through the MAC, and generate the value, and see if that's the value on the badge.

Obviously, this very straight-forward, and we have MACs for which the best known way to generate a forgery is to select a random value, and hope that value happens to be the correct one (which can't be verified until you actually scan the badge); if you have a 10-15 digit value, this would almost certainly be detected.

This meets all your requirements, and just has one problem; the MAC key needs to be installed in the scanner. If it's possible that someone can steal a scanner, open it up, and recover the MAC key, this breaks the entire system.

If this is a viable attack, then the next step is to use a signature operation (such as ECDSA as mentioned in the comments); this works similarly to the MAC, except you generate two keys, a private one (which you use to create the badges), and a public one (which you use to verify the badges). The public key can verify a badge, but (here's the cryptographical magic) it can't be used to create new ones. The problem is the signature size; public key signatures are always rather larger then the corresponding MACs. The comment says that an ECDSA signature could fit into about 32 bytes; this assumes an EC curve that could be broken by a large institution (circa $O(2^{64})$ effort), and so might not serve your purpose. A 64 byte ECDSA signature, on the other hand, should be good against any adversaty; if you can fit 64 bytes into a QR code, that might be a viable alternative.