Note: Descriptions are shown in the official language in which they were submitted.
CA 02399092 2002-07-26
WO 01/57807 _1_ PCT/US00/14191
METHOD OF AUTHENTICATING A TAG
Field of the Invention
The invention relates to a method of authenticating a device, tag, label, or
similar item, and in one embodiment to a method of cryptographically verifying
a tag
of a matched component system so that hardware that is part of the matched
component
system will only interrogate tags that are authenticated as part of the
matched
component system.
Background of the Invention
Encryption has been used for many years to make information secure against
the efforts of those who should not have access to that information.
Information is first
encoded by a first authorized user, and then decoded by a second authorized
user to
obtain access to the information. An example of simple encryption would be to
equate
a unique number with each letter of the alphabet, and then to represent the
information
of interest using those numbers, instead of letters. A person who knows the
encryption
algorithm (the substitution of a unique number for each letter) could then
decode the
information to obtain access to it. This type of simple encryption is easily
broken
however, and thus is not very secure.
Other more sophisticated forms of encryption have been used, particularly in
modern times, to secure information that is to be electronically transferred
from one
authorized user to another. For example, it is often desirable to transmit
private
information such as a message, credit card number, or the like over the
Internet, and
thus to encrypt that information in a suitably secure manner. A suitable type
of
encryption for these purposes is the "public/private key" encryption technique
that is
described in common texts and patents on encryption.
The patent literature includes a number of references related to the uses of
encryption for tracking manufactured articles, or for performing article
authentication.
See, for example, European Patent Application 0 710 934 A2, entitled "Methods
and
Systems for Performing Article Authentication"; European Patent Application 0
889
448 A2, entitled "Method of Preventing Counterfeiting of Articles of
Manufacture";
and U.S. Patent No. 5,768,384, entitled "System for Identifying,
Authenticating and
CA 02399092 2002-07-26
WO 01/57807 _2_ PCT/US00/14191
Tracking Manufactured Articles." The methods described in these and other
references
are not, however, suitable for use with tags as a means of authentication, as
described
below with reference to the present invention.
Summar~of the Invention
Tags or labels containing information about an article can be provided as part
of
a matched component system along with the hardware used to read, scan, or
interrogate
those tags or labels. Examples of such systems include bar code labels (or
printing
equipment) and scanners, end radio frequency identification (RFID) tags and
RFID
interrogators. One reason to encourage the use of matched component systems is
to
enable the system to avoid interrogating tags belonging to another system.
Thus, error
messages may be reduced, and it may be possible to use two or more systems to
identify various materials in the same location. Another reason is related to
the product
or system warranties. That is, manufacturers often warrant their products for
a given
period or to perform a given function only if they are used with other
components with
which they have been repeatedly tested by the manufacturer, but offer no
warranty or a
reduced warranty if they are not. In the case of a matched component system of
the
type described herein, a system provider may warrant the operation of the
system if a
tag interrogator is used in conjunction with authentic tags, but not
otherwise.
Specifically, a system provider may warrant the operation of an RFID system
when that
provider sells the RFID tags, and also sells the equipment used to write
information to,
and/or read information from, those tags.
The authentication method described herein enables a system or user to
authenticate, for example, radio frequency identification (RFID) tags by
providing an
RFID tag having a stored security block that is cryptographically related to
the tag
address, obtaining the tag address from the tag, applying a cryptographic
transformation to at least the tag address and a private data set to obtain a
security
block, and then comparing that security block to the stored security block. If
the two
security blocks match, then the tag can be presumed to be authentic.
Alternatively, the
stored security block can be cryptographically transformed using at least a
private data
set to obtain a tag address, and that tag address can then be compared with
the stored
tag address. If the two tag addresses match, then the tag can be presumed to
be
CA 02399092 2002-07-26
WO 01/57807 _3_ PCT/US00/14191
authentic. Also described is an RFID tag for use with the present invention.
The
invention finds particularly useful application in the interrogation by
portable or
stationary RFID interrogators of RFID tags placed in library materials, such
as books.
Brief Description of the Drawings
The present invention is described in greater detail with reference to the
appended Figures, in which:
Figure 1 is a process diagram illustrating one embodiment of the inventive
method for providing a tag with a security block that is a cryptographic
transformation
of the tag address;
Figure 2 is a process diagram illustrating one embodiment of the inventive
method for authenticating a tag by field encryption and comparison;
Figure 3 is a process diagram illustrating one embodiment of the inventive
method for authenticating a tag by field decryption and comparison; and
Figure 4 is a schematic diagram of an RFID tag in accordance with the present
invention.
Detailed Description of the Invention
I. Overview
In simple terms, a preferred method of authenticating an RFID tag according to
the present invention involves the following steps. First, a tag address that
identifies
the tag is obtained from the memory of the tag. Second, the tag address and a
private
data set, and optionally a public data set, are cryptographically transformed
to provide a
security block that is stored in the memory of the tag. Third, when it is
desired to
authenticate the tag, the tag address is again obtained and, along with the
data sets) is
cryptographically transformed to provide a security block that is compared
with the
stored security block. Or, alternatively, the security block is
cryptographically
transformed, using the inverse of the original transformation, including
appropriate data
set(s), to obtain a tag address that is compared to the stored tag address.
Fourth, if the
two security blocks (or tag addresses, depending on which process was used)
are the
same, then the tag is authentic. If not, the tag is not authentic.
CA 02399092 2002-07-26
WO 01/57807 _4_ PCT/~JS00/14191
These steps, and other features, variations, and embodiments of the present
invention are described in greater detail below. Although the invention is
described in
terms of an RFID system, other systems in which information can be read from
and
written to a tag (preferably electronically) are also within the scope of the
present
invention.
II. The TaQ
An RFID tag suitable for use in conjunction with the present invention is
described in PCT Publicatfon 99/65006 entitled "Identification Tag With
Enhanced
Security," the rights to which are assigned to the assignee of the present
invention. As
shown in Figure 4, RFID tag 10 generally includes an antenna 12 connected to a
memory device 14 such as an integrated circuit (IC). The tag may include a
power
source, such as a battery or capacitor, or may be powered solely by the RFID
interrogator such that it receives both energy and information in the form of
radio
waves from the RFID interrogator. The tag may be provided with adhesive
(typically
pressure sensitive adhesive) so that it may be adhered to, for example, a
library book.
It will be appreciated by those skilled in the art that Figure 4 represents
only one of the
many embodiments of geometry and antenna design suitable for use in an RF117
tag.
A commercial example of a suitable RFID tag is one available from the Texas
Instruments Company of Dallas, Texas, under the designation "TIRIS Tag-it."
The
Tag-it brand RFID tag includes a first memory storage area that stores
unalterable data
(referred to as "permanent tag memory"), such as unique unalterable data
identifying
that specific tag (referred to herein as the "tag address"), and a second
memory storage
area that stores variable information provided by a user (referred to herein
as "variable
tag memory"). Current Tag-it brand RFID tags include 256 bits of variable tag
memory, although more memory is likely to become available on that and other
RFID
tags in the future. The Tag-it brand RFID tag operates at a 13.56 MHz
communication
frequency, although tags and interrogators that operate at other frequencies
may be
used instead. Tag-it brand RFID tag systems may also be used with Windows-
compatible software available from Texas Instruments to simplify the use of
Tag-it
brand RFID tags and equipment.
CA 02399092 2002-07-26
WO 01/57807 _5_ PCT/US00/14191
A. Permanent Tag Memory
It is preferred that the tag address is stored in the permanent tag memory. It
is
also preferred that this tag address be unique to insure that it is possible
to identify and
address a specific tag during use. This tag address might, for example, be 32
bits long,
allowing over 4 billion unique addresses. Typically this tag address is
programmed
into the tag during manufacture and "factory locked" so that it cannot be
changed later.
A tag address may include information stored in both the permanent tag memory
and
the variable tag memory, described below.
B. Variable Tag Memory
Variable tag memory, subject to any applicable restrictions on the amount of
memory available, may be used to store information about the manufacturer of
the tag
or the tag itself (such as when and where the tag was made), and/or about the
article to
which the tag is attached or to be attached. For example, where the RFID tag
will be
attached to a library book or other material, the title, author, call number,
checkout
status, and usage statistics associated with that book may be stored in the
variable tag
memory. Other information that may be stored in the variable tag memory
includes the
name of the library that owns the book or material, the specific library
branch from
which it was borrowed, the appropriate location (such as the specific shelf
location) for
the book or material, type of item (book, CD, video tape), and the like.
A portion of the variable tag memory may be locked, so that it cannot be
inadvertently modified. For example, the data on a tag associated with an item
belonging to a library can thereby be protected from accidental modification
by an
RFID-based airline baggage handling system or other RFm writer. The locking
procedure differs among RFm tag suppliers. In the case of the Texas
Instruments Tag-
it brand RFID tags, the smallest block of variable memory that can be locked
in this
manner is 32 bits, which may be used to store certain cryptographically
transformed
information in the manner described herein.
III. Readers (Interrogation Sources) and Writers (Programmers)
RFID tags used in one embodiment of the invention are both readable and
programmable. That is, the RFID tag can be read or interrogated by an
interrogation
CA 02399092 2002-07-26
WO 01/57807 _6_ PCT/US00/14191
source to obtain some or all of the information stored in the variable tag
memory of the
tag for use or manipulation by a user, and can also be programmed (written)
with
information provided by a system or user. Suitable RF117 interrogation sources
and
RF117 writers are commercially available from Texas Instruments of Dallas,
Texas
under the designation "Commander 320."
In one embodiment of the present invention, certain information is
cryptographically transformed and written into a portion of the available
variable tag
memory by an RFID writer, and in use the tag is interrogated by an RFID reader
that
determines whether the tag is authentic, as described in greater detail below.
RFID
readers preferably can interrogate multiple RFID tags virtually simultaneously
(the
Commander 320 brand interrogation source currently is able to interrogate 30
RFID
tags per second), though this feature is not required.
IV. Encryption
Before the tag can be authenticated, certain information is obtained from the
tag
and other information is stored on it. Specifically, the tag address is
obtained from the
tag, cryptographically transformed as described below, and the resulting
security block
is then stored on the tag. One exemplary process for providing a tag having a
stored
security block in accordance with the present invention is shown in Figure 1.
Step 100 is to read or interrogate the tag to obtain the tag address 102. The
tag
address is then concatenated with at least one data set, and preferably two
data sets. If
one data set is used, then that data set should be a private data set 106 that
is not
generally available to the public, but is stored in and used by the
interrogation source.
If two data sets are used, as exemplified in the remainder of this
description, then one
data set may be private and the other a public data set 104, as represented in
Figure 1.
The tag address and the data sets) could be interleaved or otherwise scrambled
(instead
of being concatenated) if desired, though this is not believed to add
significantly to the
security or reliability of the system.
The public and private data sets may consist of any string of characters
and/or
numbers, and can be human readable strings that are represented as binary data
using
CA 02399092 2002-07-26
WO 01/57807 _7_ PCT/US00/14191
standard methods such as ASCII, UTF-8 or Unicode. The public data set may be
widely distributed or not, as desired. In other words, the public and private
data sets
are simply two data sets, which may have different levels of secrecy imposed
on them
by the user. The data set(s), and particularly the private data set, is
preferably a string of
random characters and/or numbers, so that it is difficult or impossible to
reverse
engineer the data set from the cryptographically transformed information. To
create the
data set(s), a random or substantially random process may be used, such as a
random
number generator.
The public or private data set may be subsumed within software used to create
and authenticate the tags. The software, in general, will consist of machine
language
instructions, which are not readily intelligible to people and cannot be
deciphered
except by highly specialized individuals expending a great deal of time. Thus,
the data
sets) will preferably be sufficiently difficult to locate within that software
that it may
be considered for all practical purposes to be private even when the software
itself is
widely distributed. The form of the public or private data sets may also be
chosen to
facilitate legal protection under copyright, trade secret or other law, so
that any
unauthorized user of the data sets) would also be infringing on a legally
protected
right.
Although the tag address, the public data set, and the private data set may be
of
any desired length and content, by way of example the tag address may have,
for
example, 32 bits of information, the public data set may have at least 32
bytes of
information, and the private data set may have at least 32 bytes of
information. An
exemplary tag address could be the hexadecimal value 0x012345678, and
exemplary
public data set may be the ASCII string "3M Radio Frequency Identification
Systems,"
and an exemplary private data set may be
Ox0001E2882AC7B5 C613FAF447170E90702957A5053 CS C013D723 5168E268DE99
0.
The tag address 102 and private data set 106, and optionally the public data
set
104, are then fed into a cryptographic transformation algorithm 108, such as a
cryptographic hash algorithm, which transforms the data and outputs a message
digest
CA 02399092 2002-07-26
WO 01/57807 _8_ PCT/US00/14191
110 of, for example, 160 bits in length. Cryptographic transformations
encompass both
conventional reversible encryption such as the Data Encryption Standard (DES,
which
is also referred to as the Data Encryption Algorithm (DEA) by ANSI, and as the
DEA-1
by the ISO), and other related techniques such as the use of a one-way
cryptographic
hash such as the Secure Hash Algorithm 1, or SHA1. Examples of both types of
algorithms along with detailed source code in the C programming language are
including in the book Annlied Crypt~raphy. Protocols. Algorithms~and Source
Code
in C, by Bruce Schneier (John Wiley and Sons, Inc. 1996 (2d edition))
beginning at
page 442, and in the Handbook of Applied Cryptography, A. Menezes et al. (CRC
Press 1997) beginning at page 348. Although other cryptographic algorithms
such as
DES-CBC-MAC and DES-DMAC may be used as the cryptographic transformation
method of the present invention, cryptographic hash algorithms such as SHAI,
MDS,
and RIPEMD-160 are preferred because they provide a relatively high level of
security
against attempts to reverse-engineer the private data set when the message
digest and
the public data set are known, and also because they are readily available,
easy to
implement, and free of significant governmental restrictions on use. The
source code
associated with the SHAT described in the Annlied Crypto~ranhv reference cited
above
is currently available on computer disc from Bruce Schneier, Counterpane
Systems,
7115 W. North Ave., Suite 16, Oak Park, IL 60302-1002.
If, due to variable tag memory limitations, it is desirable not to store the
entire
message digest on the tag, then a specified portion of the message digest may
be
designated and stored in (written to) the variable tag memory of the RFID tag.
This
portion of the message digest is security block 112. Additionally, if it is
desired to lock
the security block in the variable tag memory against inadvertent alteration,
as
described above, then a lockable unit or block of the variable tag memory,
perhaps 32
bits, may determine the appropriate size of the security block of information
from
among the message digest which should be designated and stored in the variable
tag
memory. It may also or instead be desirable to store the message digest or the
security
block in the permanent tag memory, which would normally be done by or for the
manufacturer of the tag. For convenience, the output of the cryptographic
transformation (such as SHAT) will be referred to as the "message digest," and
the
entirety or portion of the message digest that is stored on the RFID tag will
be referred
CA 02399092 2002-07-26
WO 01/57807 _9_ PCT/US00/14191
to as the "security block." Thus the security block 112 may be created by
designating
at least part of the message digest, and then written to the RFID tag in the
manner
described above as shown at 114.
V. Authentication
Once a security block that represents the message digest, or a portion of the
message digest, from a cryptographic transformation has been stored on a tag,
the tag
may be used for authentication in the field. Authentication may be performed
in
several different manners, 'two of which are described below. The first
involves
following the same process used to encrypt the tag, and then comparing the
result (the
security block) with the stored security block to determine whether they are
the same.
If the two security blocks are the same, then the tag is authentic. If they
are different,
then the tag is not authentic. This is referred to as "field encryption and
comparison."
The second authentication process described below involves essentially the
reverse. That is, the authentication process begins by obtaining the stored
security
block from the memory of the tag, performing an encryption transformation in
reverse
using the private data set and, if needed, the public data set, to obtain a
tag address.
The tag address is then compared with the stored tag address. If the two tag
addresses
are the same, then the tag is authentic. If they are different, then the tag
is not
authentic. This is referred to as "field decryption and comparison." In order
to use this
second authentication process, the security block should comprise the entire
message
digest.
These authentication processes are described in further detail with reference
to
Figures 2 and 3.
A. Field Encryption and Comparison
Figure 2 illustrates the field encryption and comparison process steps used to
determine whether a certain tag is authentic. The user in the field follows
the same
method as shown in Figure 1, and then compares the resulting value with the
stored
security block to determine whether the tag is authentic.
CA 02399092 2002-07-26
WO 01/57807 _lp_ PCT/US00/14191
In the embodiment shown in Figure 2, steps 200 through 212 are the same as
their counterparts in Figure 1. That is, the tag address is obtained 200; the
tag address
202, the private data set 206, and optionally the public data set 204 are
provided to the
cryptographic transformation algorithm 208 that provides a message digest 210,
from
which a security block is created 212. To authenticate the tag by comparison,
the RFID
reader obtains the stored security block from the tag, as shown at 214, and
compares
the results (shown as 216) of the security block 212 with the stored security
block
obtained from the tag at 214. If the two security blocks are the same, then
the tag is
authentic. If the two messages do not match, then the user could conclude that
the item
is not authentic, and take any appropriate action. Such action could, for
example,
include terminating processing of the item to which the tag was affixed.
B. Field Decryption and Comparison
Figure 3 illustrates the field decryption and comparison process steps used to
determine whether a certain tag is authentic. As shown in Figure 3, the
security block
(which in this embodiment should be identical to the message digest) is
obtained from
the tag 300; the security block 302, the private data set 306, and optionally
the public
data set 304 are provided to the cryptographic transformation algorithm 308
that
provides the tag address 310. The RFID reader then obtains the stored tag
address from
the tag 312, and compares the results (shown as 314) of the tag address 310
with the
stored tag address at 312. If the two tag addresses are the same, then the tag
is
authentic. If the two tag addresses are not the same, the tag is not
authentic. The
cryptographic transformation can be a reversible block cipher, stream cipher,
or other
suitable process.
The cryptographic transformation 308 could be the inverse of the cryptographic
transformation used to create the security block stored on the RFI17 tag. In
one
embodiment, the cryptographic transformation could be a block cipher such as
DES
running in encrypt mode (to encrypt the security block) and decrypt mode (to
field
decrypt the security block), where the key to the block cipher would be a
function of
the public and private data sets. For example, the data sets) could be passed
through a
cryptographic hash function to produce a 160-bit message digest and a
predetermined
subset of these bits would be selected to create the 56-bit key for the DES
block cipher.
CA 02399092 2002-07-26
WO 01/57807 _11_ PCT/US00/14191
For block ciphers like RCS that accept long keys, the key could be a
concatenation or
other predetermined arrangement of the bits that make up the data set(s).
VI. Variations of the Inventive Process
S It will be appreciated that certain steps shown in Figures 1, 2, and 3 can
be done
in an order different than that shown in the respective illustrations. For
example, in
Figure 2 the step 214 of obtaining the stored security block from the tag
could take
place at an earlier stage in the process, perhaps even as the first step in
the process.
Similarly, in Figure 3 the step 312 of obtaining the stored tag address from
the tag
could take place at an earlier stage in the process. Also, although the tag
address, the
public data set, and the private data set are shown as independent inputs into
the
cryptographic transformation algorithm, they can as described above be
concatenated,
interleaved, or otherwise grouped prior to being input to the cryptographic
transformation algorithm.
1S
In other embodiments the role of the tag address and security block can be
reversed. This reversal can be useful when the tag address and security block
are stored
such that one is more difficult to change than the other. If the tag
manufacturer writes
the tag address and the application vendor writes the security block, then
reversing the
roles of the tag address and security block may be useful in some
circumstances.
The present invention is described in even greater detail in regard to the
following Example.
2S EXAMPLE
This Example is a representation of an arbitrary tag address, public data set,
and
private data set that could be used in conjunction with the method of the
present
invention. A tag address, expressed in hexadecimal, could be 0x12345678. This
address would be concatenated with an ASCII-string public data set "Copyright
(c)
2000, 3M IPC. All Rights Reserved", which in hexadecimal notation is "0x43
Ox6f
0x70 0x79 0x72 0x69 0x67 0x68 0x74 0x20 0x28 0x63 0x29 0x20 0x32 0x30 0x30
0x30 Ox2c 0x20 0x33 Ox4d 0x20 0x49 OxSO 0x43 Ox2e 0x20 0x41 Ox6c Ox6c 0x20
OxS2 0x69 0x67 0x68 0x74 0x73 0x20 OxS2 Ox6S 0x73 Ox6S 0x72 0x76 Ox6S 0x64".
CA 02399092 2002-07-26
WO 01/57807 _12_ PCT/US00/14191
This concatenated data would further be concatenated with a hexadecimal
private data
set "OxeO 0x34 Oxc7 Oxib Ox~ Oxf7 0x37 0x26 Oxf6 0x19 0x53 0x15 Oxl 1 0x64
OxeS
0x30 0x45 Ox4b Oxe3 Oxbf Ox6a Oxca Oxdc Ox6e Oxbe Oxb4 0x84 Oxe3 Oxbl Ox2d
0x77
0x38", which could be generated by computer using a pseudo-random number
generator. The full concatenated string would be processed using the SHAI
cryptographic hash algorithm, and the resulting message digest, expressed in
hexadecimal, would be Ox3385275891ceb2e69cdc4a56031276413d6d702d. From that
one could select the low-order nibble (4 bits) of each of the first eight (8)
bytes of the
message digest (shown as 'the underlined characters in the preceding message
digest)
which would then be concatenated to provide a security block, expressed in
hexadecimal, of Ox35781e26 that could be stored on an RF)D tag by an RF)D
writer.
The tag could then be authenticated by using the field encryption and
comparison
process described above to determine whether the tag was authentic.
The authentication method described herein finds particularly useful
application
in the authentication of RFID tags used with library materials such as books.
A
portable (handheld, for example) RFB7 interrogator may be used to interrogate
the
RFm tags and, if the tags are authentic, to obtain other information from the
RF1D tag
that is useful to library staff members. Stationary RFm interrogators such as
patron
self service devices, staff work stations, and stations at which library
materials having
only optical bar codes are converted to have RFm tags, may also use the
authentication
method of the present invention.
Although most of the foregoing disclosure has been in the specific context of
the authentication of RF)Z7 tags by an RFm reader through the use of certain
encryption (and in some cases decryption) techniques, variations of the
methods
described are also within the scope of the invention. For example, tags,
readers, and
writers that operate at frequencies other than radio frequencies may be used
in place of
those described. With suitable modifications, the present invention may be
adapted for
use with bar codes (including two-dimensional bar codes), wherein a bar code
address
would be substituted for an RFID tag address, and the like.
