Authenticating Hairy Crabs

Selected solutions to the Hairy Crab authentiation problem reported in the Wall Street Journal.

Randy Unger

The concept of digital signatures also applies to the crab problem. A manager at the crab-stamping factory generates a public and private key using PKI. Since the crabs come in a variety of weights, the weight can be used as an identifying characteristic (this seems like a better identifier than the serial number because the SN is not easily related to a particular crab). The factory workers enter the weight into a program or website that encrypts the weight using the factory's private key. The workers themselves do not perform the encryption because they would have to know the private key, and this would require more trust than is necessary. The workers then stamp the encrypted weight on the crab. When a crab is being considered for purchase, the buyer whips out his calculator or PKI decrypting program and decrypts the number on the crab's back using the public key (freely available at Yang Cheng Lake Crabs .com). If this matches the weight of the crab as measured using the handy scale provided by the seller, the crab is legit.

The strength of this method is that the identifier used is (somewhat) particular to this crab, providing better assurance of authenticity than just a serial number to be verified using a hotline. If a serial number were used, the seller could simply buy authentic crabs and copy their encrypted serial numbers onto his fake crabs.

A weakness of this method is that the weight is probably not significant past 2 or 3 digits using scales that the vendors would have. This increases the number of keys that could possibly authenticate a single crab. By increasing the precision of vendor's and the factory's scales, fewer encrypted strings would decrypt to a weight that was close enough to the measured weight for the buyer's comfort. Of course, your average fake crab salesman is not going to be able to create an encrypted string that would decrypt to anything remotely resembling the weight of the crab, so this weakness is minor.

Richard Barnes

This situation calls for a solution such that:

• Crabs can be verified with high confidence to be from a Yang Cheng producer.
• No one but the producer can create valid credentials.
• The process of verification is simple and fast for buyers.

Solutions so far reveal that relying on having technology superior to that of the counterfeiters is useless. Beyond that, the solution I would propose would depend on the time it takes for a crab to go from fishery to table:

If this time were short enough, say 48 hours or so, then the crabs could just bear a dated digital signature in addition to their serial number. In this scheme each crab would carry three pieces of information: its serial number, the date and time (in some standard time) at which it was marked, and a piece of ciphertext resulting from encrypting the first two with a public-key cryptosystem using a private key known only to the production company. This way, rather than making buyers call their suppliers to find out if their crabs were valid, suppliers could freely distribute a simple application into which a signature could be entered and decrypted, then matched against the other data. To be thoroughly modern, all of these data could live on an RFID tag and be automatically handed back and forth. The one weakness of the system is its vulnerability to replay attacks; given enough time, counterfeiters could potentially copy serial numbers, dates, and signatures off of genuine crabs and put them on their own crabs, a task which would be even easier with the RFID solution.

Thus, in order to obviate replay attacks, it seems that some solution that keeps some piece of information hidden is crucial here. One possible solution would be to implement a simple challenge-response protocol. Each crab (or unit of crabs shipped) could be tagged with a smart RFID tag that would some store secret private key internally and implement some public-key algorithm, so that when a shipment of crabs arrived, they could be quickly and automatically verified to be authentic (a similar method is used by GSM SIM cards). For example, a crab could be verified by sending a plaintext query (for example the serial number of the crab), which the RFID tag would encrypt with its secret key and send back, so that the origin of the crab would be guaranteed by verifying that decryption with the corresponding public key yields the correct result. It is important that the source of plaintexts here be sufficiently diverse that spoofing is not practical. If, for instance, one buyer always used the same query, then it would be easy for a counterfeiter to produce the desired response. Since each crab's serial number is unique, these should serve as an appropriate source. In order to prevent counterfeiters from predicting outputs, a limit could be put on the number of queries that an RFID tag would process in its lifetime (e.g. the number of steps in the supply chain) or the number of queries it will process in some length of time (e.g. only one per hour). The only weakness that remains is the possibility of actual theft of the ID tags off of the crabs; one would think that if someone already had that much access, they would just take the crabs!

University of Virginia Department of Computer Science CS 851/551: Cryptography Applications Bistro

evans@virginia.edu