Consumable authentication protocol and system6816968Abstract This invention concerns a consumable authentication protocol for validating the existence of an untrusted authentication chip, as well as ensuring that the authentication chip lasts only as long as the consumable. In a further aspect it concerns a consumable authentication system for the protocol. A trusted authentication chip has a test function; and the untrusted authentication chip has a read function to test data from the trusted chip, including a random number and its signature, encrypted using a first key, by comparing the decrypted signature with a signature calculated from the decrypted random number. In the event that the two signatures match, it returns a data message and an encrypted version of the data message in combination with the random number, encrypted using the second key. The test function operates to encrypt the random number together with the data message using a second secret key, compare the two versions of the random number encrypted together with the data message using the second key. In the event that the two versions match, the untrusted authentication chip and the data message are considered to be valid; otherwise, they are considered to be invalid. Claims What is claimed is: Description TECHNICAL FIELD
TABLE 1
Summary of Symbolic Nomenclature
Symbol Description
F[X] Function F, taking a single parameter X
F[X, Y] Function F, taking two parameters, X and Y
X .vertline. Y X concatenated with Y
X {character pullout} Y Bitwise X AND Y
X {character pullout} Y Bitwise X OR Y (inclusive-OR)
X .sym. Y Bitwise X XOR Y (exclusive-OR)
{character pullout}X Bitwise NOT X (complement)
X .rarw. Y X is assigned the value Y
X .rarw. {Y, Z} The domain of assignment inputs to X is Y and Z
X = Y X is equal to Y
X .noteq. Y X is not equal to Y
{character pullout}X Decrement X by 1 (floor 0)
{character pullout}X Increment X by 1 (modulo register length)
Erase X Erase Flash memory register X
SetBits[X, Y] Set the bits of the Flash memory register X based
on Y
Z .rarw. ShiftRight[X, Y] Shift register X right one bit position, taking
input
bit from Y and placing the output bit in Z
3.2 Basic Terms A message, denoted by M, is plaintext. The process of transforming M into ciphertext C, where the substance of M is hidden, is called encryption. The process of transforming C back into M is called decryption. Referring to the encryption function as E, and the decryption function as D, we have the following identities: E[M]=C D[C]=M Therefore the following identity is true: D[E[M]]=M 3.3 Symmetric Cryptography A symmetric encryption algorithm is one where: the encryption function E relies on key K.sub.1, the decryption function D relies on key K.sub.2, K.sub.2 can be derived from K.sub.1, and K.sub.1 can be derived from K.sub.2. In most symmetric algorithms, K.sub.1 equals K.sub.2. However, even if K.sub.1 does not equal K.sub.2, given that one key can be derived from the other, a single key K can suffice for the mathematical definition. Thus: E.sub.K [M]=C D.sub.K [C]=M The security of these algorithms rests very much in the key K. Knowledge of K allows anyone to encrypt or decrypt. Consequently K must remain a secret for the duration of the value of M. For example, M may be a wartime message "My current position is grid position 123-456". Once the war is over the value of M is greatly reduced, and if K is made public, the knowledge of the combat unit's position may be of no relevance whatsoever. Of course if it is politically sensitive for the combat unit's position to be known even after the war, K may have to remain secret for a very long time. An enormous variety of symmetric algorithms exist, from the textbooks of ancient history through to sophisticated modern algorithms. Many of these are insecure, in that modern cryptanalysis techniques (see Section 3.8) can successfully attack the algorithm to the extent that K can be derived. The security of the particular symmetric algorithm is a function of two things: the strength of the algorithm and the length of the key [78]. The strength of an algorithm is difficult to quantify, relying on its resistance to cryptographic attacks (see Section 3.8). In addition, the longer that an algorithm has remained in the public eye, and yet remained unbroken in the midst of intense scrutiny, the more secure the algorithm is likely to be. By contrast, a secret algorithm that has not been scrutinized by cryptographic experts is unlikely to be secure. Even if the algorithm is "perfectly" strong (the only way to break it is to try every key--see Section 3.8.1.5), eventually the right key will be found. However, the more keys there are, the more keys have to be tried. If there are N keys, it will take a maximum of N tries. If the key is N bits long, it will take a maximum of 2.sup.N tries, with a 50% chance of finding the key after only half the attempts (2.sup.N-1). The longer N becomes, the longer it will take to find the key, and hence the more secure it is. What makes a good key length depends on the value of the secret and the time for which the secret must remain secret as well as available computing resources. In 1996, an ad hoc group of world-renowned cryptographers and computer scientists released a report [9] describing minimal key lengths for symmetric ciphers to provide adequate commercial security. They suggest an absolute minimum key length of 90 bits in order to protect data for 20 years, and stress that increasingly, as cryptosystems succumb to smarter attacks than brute-force key search, even more bits may be required to account for future surprises in cryptanalysis techniques. We will ignore most historical symmetric algorithms on the grounds that they are insecure, especially given modem computing technology. Instead, we will discuss the following algorithms: DES Blowfish RC5 IDEA 3.3.1 DES DES (Data Encryption Standard) [26] is a US and international standard, where the same key is used to encrypt and decrypt. The key length is 56 bits. It has been implemented in hardware and software, although the original design was for hardware only. The original algorithm used in DES was patented in 1976 (U.S. Pat. No. 3,962,539) and has since expired. During the design of DES, the NSA (National Security Agency) provided secret S-boxes to perform the key-dependent nonlinear transformations of the data block. After differential cryptanalysis was discovered outside the NSA, it was revealed that the DES S-boxes were specifically designed to be resistant to differential cryptanalysis. As described in [92], using 1993 technology, a 56-bit DES key can be recovered by a custom-designed $1 million machine performing a brute force attack in only 35 minutes. For $10 million, the key can be recovered in only 3.5 minutes. DES is clearly not secure now, and will become less so in the future. A variant of DES, called triple-DES is more secure, but requires 3 keys: K.sub.1, K.sub.2, and K.sub.3. The keys are used in the following manner: E.sub.K3 [D.sub.K2 [E.sub.K1 [M]]]=C D.sub.K3 [E.sub.K2 [D.sub.K1 [C]]]=M The main advantage of triple-DES is that existing DES implementations can be used to give more security than single key DES. Specifically, triple-DES gives protection of equivalent key length of 112 bits [78]. Triple-DES does not give the equivalent protection of a 168-bit key (3.times.56) as one might naively expect. Equipment that performs triple-DES decoding and/or encoding cannot be exported from the United States. 3.3.2 Blowfish Blowfish is a symmetric block cipher first presented by Schneier in 1994 [76]. It takes a variable length key, from 32 bits to 448 bits, is unpatented, and is both license and royalty free. In addition, it is much faster than DES. The Blowfish algorithm consists of two parts: a key-expansion part and a data-encryption part. Key expansion converts a key of at most 448 bits into several subkey arrays totaling 4168 bytes. Data encryption occurs via a 16-round Feistel network. All operations are XORs and additions on 32-bit words, with four index array lookups per round. It should be noted that decryption is the same as encryption except that the subkey arrays are used in the reverse order. Complexity of implementation is therefore reduced compared to other algorithms that do not have such symmetry. [77] describes the published attacks which have been mounted on Blowfish, although the algorithm remains secure as of February 1998 [79]. The major finding with these attacks has been the discovery of certain weak keys. These weak keys can be tested for during key generation. For more information, refer to [77] and [79]. 3.3.3 RC5 Designed by Ron Rivest in 1995, RC5 [74] has a variable block size, key size, and number of rounds. Typically, however, it uses a 64-bit block size and a 128-bit key. The RC5 algorithm consists of two parts: a key-expansion part and a data-encryption part. Key expansion converts a key into 2r+2 subkeys (where r=the number of rounds), each subkey being w bits. For a 64-bit blocksize with 16 rounds (w=32, r=16), the subkey arrays total 136 bytes. Data encryption uses addition mod 2w, XOR and bitwise rotation. An initial examination by Kaliski and Yin [43] suggested that standard linear and differential cryptanalysis appeared impractical for the 64-bit blocksize version of the algorithm. Their differential attacks on 9 and 12 round RC5 require 2.sup.45 and 2.sup.62 chosen plaintexts respectively, while the linear attacks on 4, 5, and 6 round RC5 requires 2.sup.37, 2.sup.47 and 2.sup.57 known plaintexts). These two attacks are independent of key size. More recently however, Knudsen and Meier [47] described a new type of differential attack on RC5 that improved the earlier results by a factor of 128, showing that RC5 has certain weak keys. RC5 is protected by multiple patents owned by RSA Laboratories. A license must be obtained to use it. 3.3.4 IDEA Developed in 1990 by Lai and Massey [53], the first incarnation of the IDEA cipher was called PES. After differential cryptanalysis was discovered by Biham and Shamir in 1991, the algorithm was strengthened, with the result being published in 1992 as IDEA [52]. IDEA uses 128-bit keys to operate on 64-bit plaintext blocks. The same algorithm is used for encryption and decryption. It is generally regarded as the most secure block algorithm available today [78][56]. The biggest drawback of IDEA is the fact that it is patented (U.S. Pat. No. 5,214,703, issued in 1993), and a license must be obtained from Ascom Tech AG (Bern) to use it. 3.4 Asymmetric Cryptography An asymmetric encryption algorithm is one where: the encryption function E relies on key K.sub.1, the decryption function D relies on key K.sub.2, K2 cannot be derived from K.sub.1 in a reasonable amount of time, and K1 cannot be derived from K.sub.2 in a reasonable amount of time. Thus: E.sub.K1 [M]=C D.sub.K2 [C]=M These algorithms are also called public-key because one key K.sub.1 can be made public. Thus anyone can encrypt a message (using K.sub.1) but only the person with the corresponding decryption key (K.sub.2) can decrypt and thus read the message. In most cases, the following identity also holds: E.sub.K2 [M]=C D.sub.K1 [C]=M This identity is very important because it implies that anyone with the public key K.sub.1 can see M and know that it came from the owner of K.sub.2. No-one else could have generated C because to do so would imply knowledge of K.sub.2. This gives rise to a different application, unrelated to encryption--digital signatures. The property of not being able to derive K.sub.1 from K.sub.2 and vice versa in a reasonable time is of course clouded by the concept of reasonable time. What has been demonstrated time after time, is that a calculation that was thought to require a long time has been made possible by the introduction of faster computers, new algorithms etc. The security of asymmetric algorithms is based on the difficulty of one of two problems: factoring large numbers (more specifically large numbers that are the product of two large primes), and the difficulty of calculating discrete logarithms in a finite field. Factoring large numbers is conjectured to be a hard problem given today's understanding of mathematics. The problem however, is that factoring is getting easier much faster than anticipated. Ron Rivest in 1977 said that factoring a 125-digit number would take 40 quadrillion years [30]. In 1994 a 129-digit number was factored [3]. According to Schneier, you need a 1024-bit number to get the level of security today that you got from a 512-bit number in the 1980s [78]. If the key is to last for some years then 1024 bits may not even be enough. Rivest revised his key length estimates in 1990: he suggests 1628 bits for high security lasting until 2005, and 1884 bits for high security lasting until 2015 [69]. Schneier suggests 2048 bits are required in order to protect against corporations and governments until 2015 [80]. Public key cryptography was invented in 1976 by Diffie and Hellman [15][16], and independently by Merkle [57]. Although Diffie, Hellman and Merkle patented the concepts (U.S. Pat. Nos. 4,200,770 and 4,218,582), these patents expired in 1997. A number of public key cryptographic algorithms exist. Most are impractical to implement, and many generate a very large C for a given M or require enormous keys. Still others, while secure, are far too slow to be practical for several years. Because of this, many public key systems are hybrid--a public key mechanism is used to transmit a symmetric session key, and then the session key is used for the actual messages. All of the algorithms have a problem in terms of key selection. A random number is simply not secure enough. The two large primes p and q must be chosen carefully--there are certain weak combinations that can be factored more easily (some of the weak keys can be tested for). But nonetheless, key selection is not a simple matter of randomly selecting 1024 bits for example. Consequently the key selection process must also be secure. Of the practical algorithms in use under public scrutiny, the following are discussed: RSA DSA ElGamal 3.4.1 RSA The RSA cryptosystem [75], named after Rivest, Shamir, and Adleman, is the most widely used public key cryptosystem, and is a de facto standard in much of the world [78]. The security of RSA depends on the conjectured difficulty of factoring large numbers that are the product of two primes (p and q). There are a number of restrictions on the generation of p and q. They should both be large, with a similar number of bits, yet not be close to one another (otherwise p=q=pq). In addition, many authors have suggested that p and q should be strong primes [56]. The Heilman-Bach patent (U.S. Pat. No. 4,633,036) covers a method for generating strong RSA primes p and q such that n=pq and factoring n is believed to be computationally infeasible. The RSA algorithm patent was issued in 1983 (U.S. Pat. No. 4,405,829). The patent expires on Sep. 20, 2000. 3.4.2 DSA DSA (Digital Signature Algorithm) is an algorithm designed as part of the Digital Signature Standard (DSS) [29]. As defined, it cannot be used for generalized encryption. In addition, compared to RSA, DSA is 10 to 40 times slower for signature verification [40]. DSA explicitly uses the SHA-1 hashing algorithm (see Section 3.6.3.3). DSA key generation relies on finding two primes p and q such that q divides p-1. According to Schneier [78], a 1024-bit p value is required for long term DSA security. However the DSA standard [29] does not permit values of p larger than 1024 bits (p must also be a multiple of 64 bits). The US Government owns the DSA algorithm and has at least one relevant patent (U.S. Pat. No. 5,231,688 granted in 1993). However, according to NIST [61]: "The DSA patent and any foreign counterparts that may issue are available for use without any written permission from or any payment of royalties to the U.S. government." In a much stronger declaration, NIST states in the same document [61] that DSA does not infringe third party's rights: "NIST reviewed all of the asserted patents and concluded that none of them would be infringed by DISCS. Extra protection will be written into the PK1 pilot project that will prevent an organization or individual from suing anyone except the government for patent infringement during the course of the project." It must however, be noted that the Schnorr authentication algorithm [81] (U.S. Pat. No. 4,995,082) patent holder claims that DSA infringes his patent. The Schnorr patent is not due to expire until 2008. 3.4.3 ElGamal The ElGamal scheme [22][23] is used for both encryption and digital signatures. The security is based on the conjectured difficulty of calculating discrete logarithms in a finite field. Key selection involves the selection of a prime p, and two random numbers g and x such that both g and x are less than p. Then calculate y=gx mod p. The public key is y, g, and p. The private key is x. ElGamal is unpatented. Although it uses the patented Diffie-Helman public key algorithm [15][16], those patents expired in 1997. ElGamal public key encryption and digital signatures can now be safely used without infringing third party patents. 3.5 Cryptographic Challenge-Response Protocols and Zero Knowledge Proofs The general principle of a challenge-response protocol is to provide identity authentication. The simplest form of challenge-response takes the form of a secret password. A asks B for the secret password, and if B responds with the correct password, A declares B authentic. There are three main problems with this kind of simplistic protocol. Firstly, once B has responded with the password, any observer C will know what the password is. Secondly, A must know the password in order to verify it. Thirdly, if C impersonates A, then B will give the password to C (thinking C was A), thus compromising the password. Using a copyright text (such as a haiku) as the password is not sufficient, because we are assuming that anyone is able to copy the password (for example in a country where intellectual property is not respected). The idea of cryptographic challenge-response protocols is that one entity (the claimant) proves its identity to another (the verifier) by demonstrating knowledge of a secret known to be associated with that entity, without revealing the secret itself to the verifier during the protocol [56]. In the generalized case of cryptographic challenge-response protocols, with some schemes the verifier knows the secret, while in others the secret is not even known by the verifier. A good overview of these protocols can be found in [25], [78], and [56]. Since this document specifically concerns Authentication, the actual cryptographic challenge-response protocols used for authentication are detailed in the appropriate sections. However the concept of Zero Knowledge Proofs bears mentioning here. The Zero Knowledge Proof protocol, first described by Feige, Fiat and Shamir in [24] is extensively used in Smart Cards for the purpose of authentication [34][36][67]. The protocol's effectiveness is based on the assumption that it is computationally infeasible to compute square roots modulo a large composite integer with unknown factorization. This is provably equivalent to the assumption that factoring large integers is difficult. It should be noted that there is no need for the claimant to have significant computing power. Smart cards implement this kind of authentication using only a few modulo multiplications [34][36]. Finally, it should be noted that the Zero Knowledge Proof protocol is patented [82] (U.S. Pat. No. 4,748,668, issued May 31, 1988). 3.6 One-Way Functions A one-way function F operates on an input X, and returns F[X] such that X cannot be determined from F[X]. When there is no restriction on the format of X, and F[X] contains fewer bits than X, then collisions must exist. A collision is defined as two different X input values producing the same F[X] value--i.e. X.sub.1 and X.sub.2 exist such that X.sub.1.noteq.X.sub.2 yet F[X.sub.1 ]=F[X.sub.2 ]. When X contains more bits than F[X], the input must be compressed in some way to create the output. In many cases, X is broken into blocks of a particular size, and compressed over a number of rounds, with the output of one round being the input to the next. The output of the hash function is the last output once X has been consumed. A pseudo-collision of the compression function CF is defined as two different initial values V.sub.1 and V.sub.2 and two inputs X.sub.1 and X.sub.2 (possibly identical) are given such that CF(V.sub.1, X.sub.1)=CF(V.sub.2, X.sub.2). Note that the existence of a pseudo-collision does not mean that it is easy to compute an X.sub.2 for a given X.sub.1. We are only interested in one-way functions that are fast to compute. In addition, we are only interested in deterministic one-way functions that are repeatable in different implementations. Consider an example F where F[X] is the time between calls to F. For a given F[X] X cannot be determined because X is not even used by F. However the output from F will be different for different implementations. This kind of F is therefore not of interest. In the scope of this document, we are interested in the following forms of one-way functions: Encryption using an unknown key Random number sequences Hash Functions Message Authentication Codes 3.6.1 Encryption Using an Unknown Key When a message is encrypted using an unknown key K, the encryption function E is effectively one-way. Without the key K, it is computationally infeasible to obtain M from EK[M]. An encryption function is only one-way for as long as the key remains hidden. An encryption algorithm does not create collisions, since E creates EK[M] such that it is possible to reconstruct M using function D. Consequently F[X] contains at least as many bits as X (no information is lost) if the one-way function F is E. Symmetric encryption algorithms (see Section 3.3) have the advantage over asymmetric algorithms (see Section 3.4) for producing one-way functions based on encryption for the following reasons: The key for a given strength encryption algorithm is shorter for a symmetric algorithm than an asymmetric algorithm Symmetric algorithms are faster to compute and require less software or silicon Note however, that the selection of a good key depends on the encryption algorithm chosen. Certain keys are not strong for particular encryption algorithms, so any key needs to be tested for strength. The more tests that need to be performed for key selection, the less likely the key will remain hidden. 3.6.2 Random Number Sequences Consider a random number sequence R.sub.0, R.sub.1, . . . , R.sub.i, R.sub.i+1. We define the one-way function F such that F[X] returns the X.sup.th random number in the random sequence. However we must ensure that F[X] is repeatable for a given X on different implementations. The random number sequence therefore cannot be truly random. Instead, it must be pseudo-random, with the generator making use of a specific seed. There are a large number of issues concerned with defining good random number generators. Knuth, in [48] describes what makes a generator "good" (including statistical tests), and the general problems associated with constructing them. Moreau gives a high level survey of the current state of the field in [60]. The majority of random number generators produce the i.sup.th random number from the i-1.sup.th state--the only way to determine the i.sup.th number is to iterate from the 0.sup.th number to the i.sup.th. If i is large, it may not be practical to wait for i iterations. However there is a type of random number generator that does allow random access. In [10], Blum, Blum and Shub define the ideal generator as follows: ". . . we would like a pseudo-random sequence generator to quickly produce, from short seeds, long sequences (of bits) that appear in every way to be generated by successive flips of a fair coin". They defined the x.sup.2 mod n generator [10], more commonly referred to as the BBS generator. They showed that given certain assumptions upon which modem cryptography relies, a BBS generator passes extremely stringent statistical tests. The BBS generator relies on selecting n which is a Blum integer (n=pq where p and q are large prime numbers, p.noteq.q, p mod 4=3, and q mod 4=3). The initial state of the generator is given by x.sub.0 where x.sub.0 =x.sup.2 mod n, and x is a random integer relatively prime to n. The i.sup.th pseudo-random bit is the least significant bit of x.sub.i where: x.sub.i =x.sup.2.sub.i-1 mod n As an extra property, knowledge of p and q allows a direct calculation of the i.sup.th number in the sequence as follows: x.sub.i =x.sub.0.sup.y mod n where y=2.sup.i mod((p-1)(q-1)) Without knowledge of p and q, the generator must iterate (the security of calculation relies on the conjectured difficulty of factoring large numbers). When first defined, the primary problem with the BBS generator was the amount of work required for a single output bit. The algorithm was considered too slow for most applications. However the advent of Montgomery reduction arithmetic [58] has given rise to more practical implementations, such as [59]. In addition, Vazirani and Vazirani have shown in [90] that depending on the size of n, more bits can safely be taken from x.sub.i without compromising the security of the generator. Assuming we only take 1 bit per x.sub.i, N bits (and hence N iterations of the bit generator function) are needed in order to generate an N-bit random number. To the outside observer, given a particular set of bits, there is no way to determine the next bit other than a 50/50 probability. If the x, p and q are hidden, they act as a key, and it is computationally infeasible to take an output bit stream and compute x, p, and q. It is also computationally infeasible to determine the value of i used to generate a given set of pseudo-random bits. This last feature makes the generator one-way. Different values of i can produce identical bit sequences of a given length (e.g. 32 bits of random bits). Even if x, p and q are known, for a given F[i], i can only be derived as a set of possibilities, not as a certain value (of course if the domain of i is known, then the set of possibilities is reduced further). However, there are problems in selecting a good p and q, and a good seed x. In particular, Ritter in [68] describes a problem in selecting x. The nature of the problem is that a BBS generator does not create a single cycle of known length. Instead, it creates cycles of various lengths, including degenerate (zero-length) cycles. Thus a BBS generator cannot be initialized with a random state--it might be on a short cycle. Specific algorithms exist in section 9 of [10] to determine the length of the period for a given seed given certain strenuous conditions for n. 3.6.3 Hash Functions Special one-way functions, known as Hash functions, map arbitrary length messages to fixed-length hash values. Hash functions are referred to as H[M]. Since the input is of arbitrary length, a hash function has a compression component in order to produce a fixed length output. Hash functions also have an obfuscation component in order to make it difficult to find collisions and to determine information about M from H[M]. Because collisions do exist, most applications require that the hash algorithm is preimage resistant, in that for a given X.sub.1 it is difficult to find X.sub.2 such that H[X.sub.1 ]=H[X.sub.2 ]. In addition, most applications also require the hash algorithm to be collision resistant (i.e. it should be hard to find two messages X.sub.1 and X.sub.2 such that H[X.sub.1 ]=H[X.sub.2 ]). However, as described in [20], it is an open problem whether a collision-resistant hash function, in the ideal sense, can exist at all. The primary application for hash functions is in the reduction of an input message into a digital "fingerprint" before the application of a digital signature algorithm. One problem of collisions with digital signatures can be seen in the following example. A has a long message M1 that says "I owe B $10". A signs H[M.sub.1 ] using his private key. B, being greedy, then searches for a collision message M.sub.2 where H[M.sub.2 ]=H[M.sub.1 ] but where M.sub.2 is favorable to B, for example "I owe B $1 million". Clearly it is in A's interest to ensure that it is difficult to find such an M.sub.2. Examples of collision resistant one-way hash functions are SHA-1 [28], MD5 [73] and RIPEMD-160 [66], all derived from MD4 [70][72]. 3.6.3.1 MD4 Ron Rivest introduced MD4 [70][72] in 1990. It is only mentioned here because all other one-way hash functions are derived in some way from MD4. MD4 is now considered completely broken [18][19] in that collisions can be calculated instead of searched for. In the example above, B could trivially generate a substitute message M.sub.2 with the same hash value as the original message M.sub.1. 3.6.3.2 MD5 Ron Rivest introduced MD5 [73] in 1991 as a more secure MD4. Like MD4, MD5 produces a 128-bit hash value. MD5 is not patented [80]. Dobbertin describes the status of MD5 after recent attacks [20]. He describes how pseudo-collisions have been found in MD5, indicating a weakness in the compression function, and more recently, collisions have been found. This means that MD5 should not be used for compression in digital signature schemes where the existence of collisions may have dire consequences. However MD5 can still be used as a one-way function. In addition, the HMAC-MD5 construct (see Section 3.6.4.1) is not affected by these recent attacks. 3.6.3.3 SHA-1 SHA-1 [28] is very similar to MD5, but has a 160-bit hash value (MD5 only has 128 bits of hash value). SHA-1 was designed and introduced by the NIST and NSA for use in the Digital Signature Standard (DSS). The original published description was called SHA [27], but very soon afterwards, was revised to become SHA-1 [28], supposedly to correct a security flaw in SHA (although the NSA has not released the mathematical reasoning behind the change). There are no known cryptographic attacks against SHA-1 [78]. It is also more resistant to brute force attacks than MD4 or MD5 simply because of the longer hash result. The US Government owns the SHA-1 and DSA algorithms (a digital signature authentication algorithm defined as part of DSS [29]) and has at least one relevant patent (U.S. Pat. No. 5,231,688 granted in 1993). However, according to NIST [61]: "The DSA patent and any foreign counterparts that may issue are available for use without any written permission from or any payment of royalties to the U.S. government." In a much stronger declaration, NIST states in the same document [61] that DSA and SHA-1 do not infringe third party's rights: "NIST reviewed all of the asserted patents and concluded that none of them would be infringed by DSS. Extra protection will be written into the PK1 pilot project that will prevent an organization or individual from suing anyone except the government for patent infringement during the course of the project." It must however, be noted that the Schnorr authentication algorithm [81] (U.S. Pat. No. 4,995,082) patent holder claims that DSA infringes his patent. The Schnorr patent is not due to expire until 2008. Fortunately this does not affect SHA-1. 3.6.3.4 RIPEMD-160 RIPEMD-160 [66] is a hash function derived from its predecessor RIPEMD [11] (developed for the European Community's RIPE project in 1992). As its name suggests, RIPEMD-160 produces a 160-bit hash result. Tuned for software implementations on 32-bit architectures, RIPEMD-160 is intended to provide a high level of security for 10 years or more. Although there have been no successful attacks on RIPEMD-160, it is comparatively new and has not been extensively cryptanalyzed. The original RIPEMD algorithm [11] was specifically designed to resist known cryptographic attacks on MD4. The recent attacks on MD5 (detailed in [20]) showed similar weaknesses in the RIPEMD 128-bit hash function. Although the attacks showed only theoretical weaknesses, Dobbertin, Preneel and Bosselaers further strengthened RIPEMD into a new algorithm RIPEMD-160. RIPEMD-160 is in the public domain, and requires no licensing or royalty payments. 3.6.4 Message Authentication Codes The problem of message authentication can be summed up as follows: How can A be sure that a message supposedly from B is in fact from B? Message authentication is different from entity authentication (described in the section on cryptographic challenge-response protocols). With entity authentication, one entity (the claimant) proves its identity to another (the verifier). With message authentication, we are concerned with making sure that a given message is from who we think it is from i.e. it has not been tampered with en route from the source to its destination. While this section has a brief overview of message authentication, a more detailed survey can be found in [86]. A one-way hash function is not sufficient protection for a message. Hash functions such as MD5 rely on generating a hash value that is representative of the original input, and the original input cannot be derived from the hash value. A simple attack by E, who is in-between A and B, is to intercept the message from B, and substitute his own. Even if A also sends a hash of the original message, E can simply substitute the hash of his new message. Using a one-way hash function alone, A has no way of knowing that B's message has been changed. One solution to the problem of message authentication is the Message Authentication Code, or MAC. When B sends message M, it also sends MAC[M] so that the receiver will know that M is actually from B. For this to be possible, only B must be able to produce a MAC of M, and in addition, A should be able to verify M against MAC[M]. Notice that this is different from encryption of M--MACs are useful when M does not have to be secret. The simplest method of constructing a MAC from a hash function is to encrypt the hash value with a symmetric algorithm: 1. Hash the input message H[M] 2. Encrypt the hash EK[H[M]] This is more secure than first encrypting the message and then hashing the encrypted message. Any symmetric or asymmetric cryptographic function can be used, with the appropriate advantages and disadvantage of each type described in Section 3.3 and Section 3.4. However, there are advantages to using a key-dependent one-way hash function instead of techniques that use encryption (such as that shown above): Speed, because one-way hash functions in general work much faster than encryption; Message size, because EK[M] is at least the same size as M, while H[M] is a fixed size (usually considerably smaller than M); Hardware/software requirements--keyed one-way hash functions are typically far less complex than their encryption-based counterparts; and One-way hash function implementations are not considered to be encryption or decryption devices and therefore are not subject to US export controls. It should be noted that hash functions were never originally designed to contain a key or to support message authentication. As a result, some ad hoc methods of using hash functions to perform message authentication, including various functions that concatenate messages with secret prefixes, suffixes, or both have been proposed [56][78]. Most of these ad hoc methods have been successfully attacked by sophisticated means [42][64][65]. Additional MACs have been suggested based on XOR schemes [8] and Toeplitz matrices [49] (including the special case of LFSR-based (Linear Feed Shift Register) constructions). 3.6.4.1 HMAC The HMAC construction [6][7] in particular is gaining acceptance as a solution for Internet message authentication security protocols. The HMAC construction acts as a wrapper, using the underlying hash function in a black-box way. Replacement of the hash function is straightforward if desired due to security or performance reasons. However, the major advantage of the HMAC construct is that it can be proven secure provided the underlying hash function has some reasonable cryptographic strengths--that is, HMAC's strengths are directly connected to the strength of the hash function [6]. Since the HMAC construct is a wrapper, any iterative hash function can be used in an HMAC. Examples include HMAC-MD5, HMAC-SHA1, HMAC-RIPEMD160 etc. Given the following definitions: H=the hash function (e.g. MD5 or SHA-1) n=number of bits output from H (e.g. 160 for SHA-1, 128 bits for MD5) M=the data to which the MAC function is to be applied K=the secret key shared by the two parties ipad=0x36 repeated 64 times opad=0x5C repeated 64 times The HMAC algorithm is as follows: 1. Extend K to 64 bytes by appending 0x00 bytes to the end of K 2. XOR the 64 byte string created in (1) with ipad 3. append data stream M to the 64 byte string created in (2) 4. Apply H to the stream generated in (3) 5. XOR the 64 byte string created in (1) with opad 6. Append the H result from (4) to the 64 byte string resulting from (5) 7. Apply H to the output of (6) and output the result Thus: HMAC[M]=H[(K .sym. opad).vertline.H[(K .sym. ipad).vertline.M]] The recommended key length is at least n bits, although it should not be longer than 64 bytes (the length of the hashing block). A key longer than n bits does not add to the security of the function. HMAC optionally allows truncation of the final output e.g. truncation to 128 bits from 160 bits. The HMAC designers' Request for Comments [51] was issued in 1997, one year after the algorithm was first introduced. The designers claimed that the strongest known attack against HMAC is based on the frequency of collisions for the hash function H (see Section 5.5.10), and is totally impractical for minimally reasonable hash functions: As an example, if we consider a hash function like MD5 where the output length is 128 bits, the attacker needs to acquire the correct message authentication tags computed (with the same secret key K) on about 264 known plaintexts. This would require the processing of at least 264 blocks under H, an impossible task in any realistic scenario (or a block length of 64 bytes this would take 250,000 years in a continuous 1 Gbps link, and without changing the secret key K all this time). This attack could become realistic only if serious flaws in the collision behavior of the function H are discovered (e.g. Collisions found after 230 messages). Such a discovery would determine the immediate replacement of function H (the effects of such a failure would be far more severe for the traditional uses of H in the context of digital signatures, public key certificates etc). Of course, if a 160-bit hash function is used, then 2.sup.64 should be replaced with 2.sup.80. This should be contrasted with a regular collision attack on cryptographic hash functions where no secret key is involved and 2.sup.64 off-line parallelizable operations suffice to find collisions. More recently, HMAC protocols with replay prevention components [62] have been defined in order to prevent the capture and replay of any M, HMAC[M] combination within a given time period. Finally, it should be noted that HMAC is in the public domain [50], and incurs no licensing fees. There are no known patents infringed by HMAC. 3.7 Random Numbers and Time Varying Messages The use of a random number generator as a one-way function has already been examined. However, random number generator theory is very much intertwined with cryptography, security, and authentication. There are a large number of issues concerned with defining good random number generators. Knuth, in [48] describes what makes a generator good (including statistical tests), and the general problems associated with constructing them. Moreau gives a high level survey of the current state of the field in [60]. One of the uses for random numbers is to ensure that messages vary over time. Consider a system where A encrypts commands and sends them to B. If the encryption algorithm produces the same output for a given input, an attacker could simply record the messages and play them back to fool B. There is no need for the attacker to crack the encryption mechanism other than to know which message to play to B (while pretending to be A). Consequently messages often include a random number and a time stamp to ensure that the message (and hence its encrypted counterpart) varies each time. Random number generators are also often used to generate keys. Although Klapper has recently shown [45] that a family of secure feedback registers for the purposes of building key-streams does exist, he does not give any practical construction. It is therefore best to say at the moment that all generators are insecure for this purpose. For example, the Berlekamp-Massey algorithm [54], is a classic attack on an LFSR random number generator. If the LFSR is of length n, then only 2n bits of the sequence suffice to determine the LFSR, compromising the key generator. If, however, the only role of the random number generator is to make sure that messages vary over time, the security of the generator and seed is not as important as it is for session key generation. If however, the random number seed generator is compromised, and an attacker is able to calculate future "random" numbers, it can leave some protocols open to attack. Any new protocol should be examined with respect to this situation. The actual type of random number generator required will depend upon the implementation and the purposes for which the generator is used. Generators include Blum, Blum, and Shub [10], stream ciphers such as RC4 by Ron Rivest [71], hash functions such as SHA-1 [28] and RIPEMD-160 [66], and traditional generators such LFSRs (Linear Feedback Shift Registers) [48] and their more recent counterpart FCSRs (Feedback with Carry Shift Registers) [44]. 3.8 Attacks This section describes the various types of attacks that can be undertaken to break an authentication cryptosystem. The attacks are grouped into physical and logical attacks. Logical attacks work on the protocols or algorithms rather than their physical implementation, and attempt to do one of three things: Bypass the authentication process altogether Obtain the secret key by force or deduction, so that any question can be answered Find enough about the nature of the authenticating questions and answers in order to, without the key, give the right answer to each question. The attack styles and the forms they take are detailed below. Regardless of the algorithms and protocol used by a security chip, the circuitry of the authentication part of the chip can come under physical attack. Physical attacks come in four main ways, although the form of the attack can vary: Bypassing the security chip altogether Physical examination of the chip while in operation (destructive and non-destructive) Physical decomposition of chip Physical alteration of chip The attack styles and the forms they take are detailed below. This section does not suggest solutions to these attacks. It merely describes each attack type. The examination is restricted to the context of an authentication chip (as opposed to some other kind of system, such as Internet authentication) attached to some System. 3.8.1 Logical Attacks These attacks are those which do not depend on the physical implementation of the cryptosystem. They work against the protocols and the security of the algorithms and random number generators. 3.8.1.1 Ciphertext Only Attack This is where an attacker has one or more encrypted messages, all encrypted using the same algorithm. The aim of the attacker is to obtain the plaintext messages from the encrypted messages. Ideally, the key can be recovered so that all messages in the future can also be recovered. 3.8.1.2 Known Plaintext Attack This is where an attacker has both the plaintext and the encrypted form of the plaintext. In the case of an authentication chip, a known-plaintext attack is one where the attacker can see the data flow between the system and the authentication chip. The inputs and outputs are observed (not chosen by the attacker), and can be analyzed for weaknesses (such as birthday attacks or by a search for differentially interesting input/output pairs). A known plaintext attack can be carried out by connecting a logic analyzer to the connection between the system and the authentication chip. 3.8.1.3 Chosen Plaintext Attacks A chosen plaintext attack describes one where a cryptanalyst has the ability to send any chosen message to the cryptosystem, and observe the response. If the cryptanalyst knows the algorithm, there may be a relationship between inputs and outputs that can be exploited by feeding a specific output to the input of another function. The chosen plaintext attack is much stronger than the known plaintext attack since the attacker can choose the messages rather than simply observe the data flow. On a system using an embedded authentication chip, it is generally very difficult to prevent chosen plaintext attacks since the cryptanalyst can logically pretend he/she is the system, and thus send any chosen bit-pattern streams to the authentication chip. 3.8.1.4 Adaptive Chosen Plaintext Attacks This type of attack is similar to the chosen plaintext attacks except that the attacker has the added ability to modify subsequent chosen plaintexts based upon the results of previous experiments. This is certainly the case with any system/authentication chip scenario described for consumables such as photocopiers and toner cartridges, especially since both systems and consumables are made available to the public. 3.8.1.5 Brute Force Attack A guaranteed way to break any key-based cryptosystem algorithm is simply to try every key. Eventually the right one will be found. This is known as a brute force attack. However, the more key possibilities there are, the more keys must be tried, and hence the longer it takes (on average) to find the right one. If there are N keys, it will take a maximum of N tries. If the key is N bits long, it will take a maximum of 2.sup.N tries, with a 50% chance of finding the key after only half the attempts (2.sup.N-1). The longer N becomes, the longer it will take to find the key, and hence the more secure the key is. Of course, an attack may guess the key on the first try, but this is more unlikely the longer the key is. Consider a key length of 56 bits. In the worst case, all 2.sup.56 tests (7.2.times.10.sup.16 tests) must be made to find the key. In 1977, Diffie and Hellman described a specialized machine for cracking DES, consisting of one million processors, each capable of running one million tests per second [17]. Such a machine would take 20 hours to break any DES code. Consider a key length of 128 bits. In the worst case, all 2.sup.128 tests (3.4.times.10.sup.38 tests) must be made to find the key. This would take ten billion years on an array of a trillion processors each running 1 billion tests per second. With a long enough key length, a brute force attack takes too long to be worth the attacker's efforts. 3.8.1.6 Guessing Attack This type of attack is where an attacker attempts to simply "guess" the key. As an attack it is identical to the brute force attack (see Section 3.8.1.5) where the odds of success depend on the length of the key. 3.8.1.7 Quantum Computer Attack To break an n-bit key, a quantum computer [83] (NMR, Optical, or Caged Atom) containing n qubits embedded in an appropriate algorithm must be built. The quantum computer effectively exists in 2.sup.n simultaneous coherent states. The trick is to extract the right coherent state without causing any decoherence. To date this has been achieved with a 2 qubit system (which exists in 4 coherent states). It is thought possible to extend this to 6 qubits (with 64 simultaneous coherent states) within a few years. Unfortunately, every additional qubit halves the relative strength of the signal representing the key. This rapidly becomes a serious impediment to key retrieval, especially with the long keys used in cryptographically secure systems. As a result, attacks on a cryptographically secure key (e.g. 160 bits) using a Quantum Computer are likely not to be feasible and it is extremely unlikely that quantum computers will have achieved more than 50 or so qubits within the commercial lifetime of the authentication chips. Even using a 50 qubit quantum computer, 2.sup.110 tests are required to crack a 160 bit key. 3.8.1.8 Purposeful Error Attack With certain algorithms, attackers can gather valuable information from the results of a bad input. This can range from the error message text to the time taken for the error to be generated. A simple example is that of a userid/password scheme. If the error message usually says "Bad userid", then when an attacker gets a message saying "Bad password" instead, then they know that the userid is correct. If the message always says "Bad userid/password" then much less information is given to the attacker. A more complex example is that of the recent published method of cracking encryption codes from secure web sites [41]. The attack involves sending particular messages to a server and observing the error message responses. The responses give enough information to learn the keys--even the lack of a response gives some information. An example of algorithmic time can be seen with an algorithm that returns an error as soon as an erroneous bit is detected in the input message. Depending on hardware implementation, it may be a simple method for the attacker to time the response and alter each bit one by one depending on the time taken for the error response, and thus obtain the key. Certainly in a chip implementation the time taken can be observed with far greater accuracy than over the Internet. 3.8.1.9 Birthday Attack This attack is named after the famous "birthday paradox" (which is not actually a paradox at all). The odds of one person sharing a birthday with another, is 1 in 365 (not counting leap years). Therefore there must be 183 people in a room for the odds to be more than 50% that one of them shares your birthday. However, there only needs to be 23 people in a room for there to be more than a 50% chance that any two share a birthday, as to shown in the following relation: Prob=1-nPr/n.sup.r =1-365P23/365.sup.23.apprxeq.0.507 Birthday attacks are common attacks against hashing algorithms, especially those algorithms that combine hashing with digital signatures. If a message has been generated and already signed, an attacker must search for a collision message that hashes to the same value (analogous to finding one person who shares your birthday). However, if the attacker can generate the message, the birthday attack comes into play. The attacker searches for two messages that share the same hash value (analogous to any two people sharing a birthday), only one message is acceptable to the person signing it, and the other is beneficial for the attacker. Once the person has signed the original message the attacker simply claims now that the person signed the alternative message--mathematically there is no way to tell which message was the original, since they both hash to the same value. Assuming a brute force attack is the only way to determine a match, the weakening of an n-bit key by the birthday attack is 2.sup.n/2. A key length of 128 bits that is susceptible to the birthday attack has an effective length of only 64 bits. 3.8.1.10 Chaining Attack These are attacks made against the chaining nature of hash functions. They focus on the compression function of a hash function. The idea is based on the fact that a hash function generally takes arbitrary length input and produces a constant length output by processing the input n bits at a time. The output from one block is used as the chaining variable set into the next block. Rather than finding a collision against an entire input, the idea is that given an input chaining variable set, to find a substitute block that will result in the same output chaining variables as the proper message. The number of choices for a particular block is based on the length of the block. If the chaining variable is c bits, the hashing function behaves like a random mapping, and the block length is b bits, the number of such b-bit blocks is approximately 2.sup.b /2.sup.c. The challenge for finding a substitution block is that such blocks are a sparse subset of all possible blocks. For SHA-1, the number of 512 bit blocks is approximately 2.sup.512 /2.sup.160, or 2.sup.352. The chance of finding a block by brute force search is about 1 in 2.sup.160. 3.8.1.11 Substitution with a Complete Lookup Table If the number of potential messages sent to the chip is small, then there is no need for a clone manufacturer to crack the key. Instead, the clone manufacturer could incorporate a ROM in their chip that had a record of all of the responses from a genuine chip to the codes sent by the system. The larger the key, and the larger the response, the more space is required for such a lookup table. 3.8.1.12 Substitution with a Sparse Lookup Table If the messages sent to the chip are somehow predictable, rather than effectively random, then the clone manufacturer need not provide a complete lookup table. For example: If the message is simply a serial number, the clone manufacturer need simply provide a lookup table that contains values for past and predicted future serial numbers. There are unlikely to be more than 10.sup.9 of these. If the test code is simply the date, then the clone manufacturer can produce a lookup table using the date as the address. If the test code is a pseudo-random number using either the serial number or the date as a seed, then the clone manufacturer just needs to crack the pseudo-random number generator in the system. This is probably not difficult, as they have access to the object code of the system. The clone manufacturer would then produce a content addressable memory (or other sparse array lookup) using these codes to access stored authentication codes. 3.8.1.13 Differential Cryptanalysis Differential cryptanalysis describes an attack where pairs of input streams are generated with known differences, and the differences in the encoded streams are analyzed. Existing differential attacks are heavily dependent on the structure of S boxes, as used in DES and other similar algorithms. Although other algorithms such as HMAC-SHA 1 have no S boxes, an attacker can undertake a differential-like attack by undertaking statistical analysis of: Minimal-difference inputs, and their corresponding outputs Minimal-difference outputs, and their corresponding inputs Most algorithms were strengthened against differential cryptanalysis once the process was described. This is covered in the specific sections devoted to each cryptographic algorithm. However some recent algorithms developed in secret have been broken because the developers had not considered certain styles of differential attacks [9] and did not subject their algorithms to public scrutiny. 3.8.1.14 Message Substitution Attacks In certain protocols, a man-in-the-middle can substitute part or all of a message. This is where a real authentication chip is plugged into a reusable clone chip within the consumable. The clone chip intercepts all messages between the system and the authentication chip, and can perform a number of substitution attacks. Consider a message containing a header followed by content. An attacker may not be able to generate a valid header, but may be able to substitute their own content, especially if the valid response is something along the lines of "Yes, I received your message". Even if the return message is "Yes, I received the following message . . . ", the attacker may be able to substitute the original message before sending the acknowledgment back to the original sender. Message Authentication Codes were developed to combat message substitution attacks. 3.8.1.15 Reverse Engineering the Key Generator If a pseudo-random number generator is used to generate keys, there is the potential for a clone manufacture to obtain the generator program or to deduce the random seed used. This was the way in which the security layer of the Netscape browser program was initially broken [33]. 3.8.1.16 Bypassing the Authentication Process It may be that there are problems in the authentication protocols that can allow a bypass of the authentication process altogether. With these kinds of attacks the key is completely irrelevant, and the attacker has no need to recover it or deduce it. Consider an example of a system that authenticates at power-up, but does not authenticate at any other time. A reusable consumable with a clone authentication chip may make use of a real authentication chip. The clone authentication chip uses the real chip for the authentication call, and then simulates the real authentication chip's state data after that. Another example of bypassing authentication is if the system authenticates only after the consumable has been used. A clone authentication chip can accomplish a simple authentication bypass by simulating a loss of connection after the use of the consumable but before the authentication protocol has completed (or even started). One infamous attack known as the "Kentucky Fried Chip" hack [2] involved replacing a microcontroller chip for a satellite TV system. When a subscriber stopped paying the subscription fee, the system would send out a "disable" message. However the to new micro-controller would simply detect this message and not pass it on to the consumer's satellite TV system. 3.8.1.17 Garrote/bribe Attack If people know the key, there is the possibility that they could tell someone else. The telling may be due to coercion (bribe, garrote etc.), revenge (e.g. a disgruntled employee), or simply for principle. These attacks are usually cheaper and easier than other efforts at deducing the key. As an example, a number of people claiming to be involved with the development of the Divx standard have recently (May/June 1998) been making noises on a variety of DVD newsgroups to the effect they would like to help develop Divx specific cracking devices--out of principle. 3.8.2 Physical Attacks The following attacks assume implementation of an authentication mechanism in a silicon chip that the attacker has physical access to. The first attack, Reading ROM, describes an attack when keys are stored in ROM, while the remaining attacks assume that a secret key is stored in Flash memory. 3.8.2.1 Reading ROM If a key is stored in ROM it can be read directly. A ROM can thus be safely used to hold a public key (for use in asymmetric cryptography), but not to hold a private key. In symmetric cryptography, a ROM is completely insecure. Using a copyright text (such as a haiku) as the key is not sufficient, because we are assuming that the cloning of the chip is occurring in a country where intellectual property is not respected. 3.8.2.2 Reverse Engineering of Chip Reverse engineering of the chip is where an attacker opens the chip and analyzes the circuitry. Once the circuitry has been analyzed the inner workings of the chip's algorithm can be recovered. Lucent Technologies have developed an active method [4] known as TOBIC (Two photon OBIC, where OBIC stands for Optical Beam Induced Current), to image circuits. Developed primarily for static RAM analysis, the process involves removing any back materials, polishing the back surface to a mirror finish, and then focusing light on the surface. The excitation wavelength is specifically chosen not to induce a current in the IC. A Kerckhoffs in the nineteenth century made a fundamental assumption about cryptanalysis: if the algorithm's inner workings are the sole secret of the scheme, the scheme is as good as broken [39]. He stipulated that the secrecy must reside entirely in the key. As a result, the best way to protect against reverse engineering of the chip is to make the inner workings irrelevant. 3.8.2.3 Usurping the Authentication Process It must be assumed that any clone manufacturer has access to both the system and consumable designs. If the same channel is used for communication between the system and a trusted system authentication chip, and a non-trusted consumable authentication chip, it may be possible for the non-trusted chip to interrogate a trusted authentication chip in order to obtain the "correct answer". If this is so, a clone manufacturer would not have to determine the key. They would only have to trick the system into using the responses from the system authentication chip. The alternative method of usurping the authentication process follows the same method as the logical attack described in Section 3.8.1.16, involving simulated loss of contact with the system whenever authentication processes take place, simulating power-down etc. 3.8.2.4 Modification of System This kind of attack is where the system itself is modified to accept clone consumables. The attack may be a change of system ROM, a rewiring of the consumable, or, taken to the extreme case, a completely clone system. Note that this kind of attack requires each individual system to be modified, and would most likely require the owner's consent. There would usually have to be a clear advantage for the consumer to undertake such a modification, since it would typically void warranty and would most likely be costly. An example of such a modification with a clear advantage to the consumer is a software patch to change fixed-region DVD players into region-free DVD players (although it should be noted that this is not to use clone consumables, but rather originals from the same companies simply targeted for sale in other countries). 3.8.2.5 Direct Viewing of Chip Operation by Conventional Probing If chip operation could be directly viewed using an STM (Scanning Tunnelling Microscope) or an electron beam, the keys could be recorded as they are read from the internal non-volatile memory and loaded into work registers. These forms of conventional probing require direct access to the top or front sides of the IC while it is powered. 3.8.2.6 Direct Viewing of the Non-volatile Memory If the chip were sliced so that the floating gates of the Flash memory were exposed, without discharging them, then the key could probably be viewed directly using an STM or SKM (Scanning Kelvin Microscope). However, slicing the chip to this level without discharging the gates is probably impossible. Using wet etching, plasma etching, ion milling (focused ion beam etching), or chemical mechanical polishing will almost certainly discharge the small charges present on the floating gates. 3.8.2.7 Viewing the Light Bursts Caused by State Changes Whenever a gate changes state, a small amount of infrared energy is emitted. Since silicon is transparent to infrared, these changes can be observed by looking at the circuitry from the underside of a chip. While the emission process is weak, it is bright enough to be detected by highly sensitive equipment developed for use in astronomy. The technique [89], developed by IBM, is called PICA (Picosecond Imaging Circuit Analyzer). If the state of a register is known at time t, then watching that register change over time will reveal the exact value at time t+n, and if the data is part of the key, then that part is compromised. 3.8.2.8 Viewing the Keys Using an SEPM A non-invasive testing device, known as a Scanning Electric Potential Microscope (SEPM), allows the direct viewing of charges within a chip [37]. The SEPM has a tungsten probe that is placed a few micrometers above the chip, with the probe and circuit forming a capacitor. Any AC signal flowing beneath the probe causes displacement current to flow through this capacitor. Since the value of the current change depends on the amplitude and phase of the AC signal, the signal can be imaged. If the signal is part of the key, then that part is compromised. 3.8.2.9 Monitoring EMI Whenever electronic circuitry operates, faint electromagnetic signals are given off. Relatively inexpensive equipment can monitor these signals and could give enough information to allow an attacker to deduce the keys. 3.8.2.10 Viewing I.sub.dd Fluctuations Even if keys cannot be viewed, there is a fluctuation in current whenever registers change state. If there is a high enough signal to noise ratio, an attacker can monitor the difference in I.sub.dd that may occur when programming over either a high or a low bit. The change in I.sub.dd can reveal information about the key. Attacks such as these have already been used to break smart cards [46]. 3.8.2.11 Differential Fault Analysis This attack assumes introduction of a bit error by ionization, microwave radiation, or environmental stress. In most cases such an error is more likely to adversely affect the chip (e.g. cause the program code to crash) rather than cause beneficial changes which would reveal the key. Targeted faults such as ROM overwrite, gate destruction etc. are far more likely to produce useful results. 3.8.2.12 Clock Glitch Attacks Chips are typically designed to properly operate within a certain clock speed range. Some attackers attempt to introduce faults in logic by running the chip at extremely high clock speeds or introduce a clock glitch at a particular time for a particular duration [1]. The idea is to create race conditions where the circuitry does not function properly. An example could be an AND gate that (because of race conditions) gates through Input1 all the time instead of the AND of Input.sub.1 and Input.sub.2. If an attacker knows the internal structure of the chip, they can attempt to introduce race conditions at the correct moment in the algorithm execution, thereby revealing information about the key (or in the worst case, the key itself). 3.8.2.13 Power Supply Attacks Instead of creating a glitch in the clock signal, attackers can also produce glitches in the power supply where the power is increased or decreased to be outside the working operating voltage range. The net effect is the same as a clock glitch--introduction of error in the execution of a particular instruction. The idea is to stop the CPU from XORing the key, or from shifting the data one bit-position etc. Specific instructions are targeted so that information about the key is revealed. 3.8.2.14 Overwriting ROM Single bits in a ROM can be overwritten using a laser cutter microscope [1], to either 1 or 0 depending on the sense of the logic. If the ROM contains instructions, it may be a simple matter for an attacker to change a conditional jump to a non-conditional jump, or perhaps change the destination of a register transfer. If the target instruction is chosen carefully, it may result in the key being revealed. 3.8.2.15 Modifying EEPROM/Flash These attacks fall into two categories: those similar to the ROM attacks except that the laser cutter microscope technique can be used to both set and reset individual bits. This gives much greater scope in terms of modification of algorithms. Electron beam programming of floating gates. As described in [87] and [32], a focused electron beam can change a gate by depositing electrons onto it. Damage to the rest of the circuit can be avoided, as described in [31]. This attack is potentially able to work against multi-level flash memory. 3.8.2.16 Gate Destruction Anderson and Kuhn described the rump session of the 1997 workshop on Fast Software Encryption [1], where Biham and Shamir presented an attack on DES. The attack was to use a laser cutter to destroy an individual gate in the hardware implementation of a known block cipher (DES). The net effect of the attack was to force a particular bit of a register to be "stuck". Biham and Shamir described the effect of forcing a particular register to be affected in this way--the least significant bit of the output from the round function is set to 0. Comparing the 6 least significant bits of the left half and the right half can recover several bits of the key. Damaging a number of chips in this way can reveal enough information about the key to make complete key recovery easy. An encryption chip modified in this way will have the property that encryption and decryption will no longer be inverses. 3.8.2.17 Overwrite Attacks Instead of trying to read the Flash memory, an attacker may simply set a single bit by use of a laser cutter microscope. Although the attacker doesn't know the previous value, they know the new value. If the chip still works, the bit's original state must be the same as the new state. If the chip doesn't work any longer, the bit's original state must be the logical NOT of the current state. An attacker can perform this attack on each bit of the key and obtain the n-bit key using at most n chips (if the new bit matched the old bit, a new chip is not required for determining the next bit). 3.8.2.18 Test Circuitry Attack Most chips contain test circuitry specifically designed to check for manufacturing defects. This includes BIST (Built In Self Test) and scan paths. Quite often the scan paths and test circuitry includes access and readout mechanisms for all the embedded latches. In some cases the test circuitry could potentially be used to give information about the contents of particular registers. Test circuitry is often disabled once the chip has passed all manufacturing tests, in some cases by blowing a specific connection within the chip. A determined attacker, however, can reconnect the test circuitry and hence enable it. 3.8.2.19 Memory Remanence Values remain in RAM long after the power has been removed [35], although they do not remain long enough to be considered non-volatile. An attacker can remove power once sensitive information has been moved into RAM (for example working registers), and then attempt to read the value from RAM. This attack is most useful against security systems that have regular RAM chips. A classic example is cited by [1], where a security system was designed with an automatic power-shut-off that is triggered when the computer case is opened. The attacker was able to simply open the case, remove the RAM chips, and retrieve the key because the values persisted. 3.8.2.20 Chip Theft Attack If there are a number of stages in the lifetime of an authentication chip, each of these stages must be examined in terms of ramifications for security should chips be stolen. For example, if information is programmed into the chip in stages, theft of a chip between stages may allow an attacker to have access to key information or reduced efforts for attack. Similarly, if a chip is stolen directly after manufacture but before programming, does it give an attacker any logical or physical advantage? 3.8.2.21 Trojan Horse Attack At some stage the authentication chips must be programmed with a secret key. Suppose an attacker builds a clone authentication chip and adds it to the pile of chips to be programmed. The attacker has especially built the clone chip so that it looks and behaves just like a real authentication chip, but will give the key out to the attacker when a special attacker-known command is issued to the chip. Of course the attacker must have access to the chip after the programming has taken place, as well as physical access to add the Trojan horse authentication chip to the genuine chips. SUMMARY OF THE INVENTION This invention is a consumable authentication protocol for validating the authenticity of an untrusted authentication chip. The protocol includes the steps of: Generating a secret random number and calculating a signature for the random number using a signature function, in a trusted authentication chip; Encrypting the random number and the signature using a symmetric encryption function using a first secret key, in the trusted authentication chip; Passing the encrypted random number and signature from the trusted authentication chip to an untrusted authentication chip; Decrypting the encrypted random number and signature with a symmetric decryption function using the first secret key, in the untrusted authentication chip; Calculating a signature for the decrypted random number using the signature function in the untrusted authentication chip; Comparing the signature calculated in the untrusted authentication chip with the signature decrypted; In the event that the two signatures match, encrypting the decrypted random number together with a data message read from the untrusted chip by the symmetric encryption function using a second secret key and returning it together with the data message to the trusted authentication chip; Encrypting the random number together with the data message by the symmetric encryption function using the second secret key, in the trusted authentication chip; Comparing the two versions of the random number encrypted together with the data message using the second key, in the trusted authentication chip; In the event that the two versions match, considering the untrusted authentication chip and the data message to be valid. Otherwise, considering the untrusted authentication chip and the data message to be invalid. When the untrusted chip is associated with a consumable item, validation of the chip can be used to validate the consumable item. Data messages read from the untrusted chip may be related to the lifespan of the consumable and may therefore ensure the chip lasts only as long as the consumable. The two secret keys are held in both the trusted and untrusted chips and must be kept secret. The random number may be generated by a random function only in the trusted chip, it should be secret and seeded with a different initial value each time. A new random number may be generated after each successful validation. The data message may be a memory vector of the authentication chip. Part of this space should be different for each chip. It does not have to be a random number, and parts of it may be constant (read only) for each consumable, or decrement only so that it can be completely downcounted only once for each consumable. The encryption function may be held in both chips, whereas the decryption function may be held only in the untrusted chip. The signature function may be held in both chips to generate digital signatures. The digital signature must be long enough to counter the chances of someone generating a random signature. 128 bits is a satisfactory size if S is symmetric encryption, while 160 bits is a satisfactory size if S is HMAC-SHA1. A test function may be held only in the trusted chip. It may return a value, such as 1, and advance the random number if the untrusted chip is valid; otherwise it may return a value, such as 0, indicating invalidity. The time taken to return a value indicating invalidity must be the same for all bad inputs. The time taken to return the value indicating validity must be the same for all good inputs. A read function in the untrusted chip may decrypt the random number and signature and then calculate its own signature for the decrypted random number. It may return the data message and a reencrypted random number in combination with the data message if the locally generated signature is the same as the decrypted signature. Otherwise it may return a value indicating failure, such as 0. The time taken to return the value indicating failure must be the same for all bad inputs. The time taken to make a return for a good input must be the same for all good inputs. In addition to validating that an authentication chip is present, the protocol is also able to validate writes and reads of the authentication chip's memory space. The authentication chip's data storage integrity is assumed to be secure--certain parts of memory may be Read Only, others Read/Write, while others are Decrement Only The protocol passes the chosen random number without the intermediate system knowing its value. This is done by encrypting both the random number and its digital signature. The protocol has the following advantages: The secret keys are not revealed during the authentication process. The time varying random number is encrypted, so that it is not revealed during the authentication process. An attacker cannot build a table of values of the input and output of the encryption process. An attacker cannot call Read without a valid random numbers and signature pair encrypted with the first key. The second key is therefore resistant to a chosen text attack. The random number only advances with a valid call to Test, so the first key is also not susceptible to a chosen text attack. The system is easy to design, especially in low cost systems such as ink-jet printers, as no encryption or decryption is required by the system itself. There are a number of well-documented and cryptanalyzed symmetric algorithms to chose from for implementation, including patent-free and license-free solutions. A wide range of signature functions exists, from message authentication codes to random number sequences to key-based symmetric cryptography. Signature functions and symmetric encryption algorithms require fewer gates and are easier to verify than asymmetric algorithms. Secure key size for symmetric encryption does not have to be as large as for an asymmetric (public key) algorithm. A minimum of 128 bits can provide appropriate security for symmetric encryption. In another aspect the invention is a consumable authentication system for validating the existence of an untrusted authentication chip, and for ensuring that the authentication chip lasts only as long as the consumable. The system includes a trusted authentication chip and an untrusted authentication chip. The trusted authentication chip includes a random number generator, a symmetric encryption function and two secret keys for the function, a signature function and a test function. The untrusted authentication chip includes symmetric encryption and decryption functions and two secret keys for these functions, a signature function and a read function. The read function operates to test data from the trusted chip, including a random number and its signature, encrypted using the first key, by comparing the decrypted signature with a signature calculated from the decrypted random number. In the event that the two signatures match, the read function operates to return a data message and an encrypted version of the data message in combination with the random number, encrypted using the second key. The test function operates to encrypt the random number together with the data message by the symmetric encryption function using the second secret key, compares the two versions of the random number encrypted together with the data message, using the second key, and in the event that the two versions match, considers the untrusted authentication chip and the data message to be valid; otherwise, it considers the untrusted authentication chip and the data message to be invalid. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a data flow diagram for single chip authentication. FIG. 2 is a data flow diagram for double chip authentication. FIG. 3 is a data flow diagram for Protocol P1. FIG. 4 is a data flow diagram for Protocol P2. FIG. 5 is a data flow diagram for Protocol P3. FIG. 6 is a data flow diagram for read authentication using Protocol C1. FIG. 7 is a data flow diagram for read authentication using Protocol C2. FIG. 8 is a data flow diagram for read authentication using Protocol C3. FIG. 9 is a block diagram of a 160-bit maximal-period LFSR random number generator. FIG. 10 is a block diagram of a clock filter. FIG. 11 is a circuit diagram of a tamper detection line. FIG. 12 is a layout diagram of an oversize nMOS transistor used as test transistors in the tamper detection line of FIG. 11. FIG. 13 is a circuit diagram of part of the tamper detection line of FIG. 11 including XOR gates between the two paths. FIG. 14 is a circuit diagram of the normal FET implementation of a CMOS inverter. FIG. 15 is voltage/current diagram for the transistors of the CMOS inverter of FIG. 14. FIG. 16 is a circuit diagram of the FET implementation of a non-flashing CMOS inverter. FIG. 17 is impedance diagram for the transistors of the CMOS inverter of FIG. 16. BEST MODES OF THE INVENTION 4 Requirements Existing solutions to the problem of authenticating consumables have typically relied on patents covering physical packaging. However this does not stop home refill operations or clone manufacture in countries with weak industrial property protection. Consequently a much higher level of protection is required. The authentication mechanism is therefore built into an authentication chip that is embedded in the consumable and allows a system to authenticate that consumable securely and easily. Limiting ourselves to the system authenticating consumables (we don't consider the consumable authenticating the system), two levels of protection can be considered: Presence Only Authentication: This is where only the presence of an authentication chip is tested. The authentication chip can be removed and used in other consumables as long as be used indefinitely. Consumable Lifetime Authentication: This is where not only is the presence of the authentication chip tested for, but also the authentication chip must only last the lifetime of the consumable. For the chip to be re-used it must be completely erased and reprogrammed. The two levels of protection address different requirements. We are primarily concerned with Consumable Lifetime authentication in order to prevent cloned versions of high volume consumables. In this case, each chip should hold secure state information about the consumable being authenticated. It should be noted that a Consumable Lifetime authentication chip could be used in any situation requiring a Presence Only authentication chip. Requirements for authentication, data storage integrity and manufacture are considered separately. The following sections summarize requirements of each. 4.1 Authentication The authentication requirements for both Presence Only and Consumable Lifetime authentication are restricted to the case of a system authenticating a consumable. We do not consider bi-directional authentication where the consumable also authenticates the system. For example, it is not necessary for a valid toner cartridge to ensure it is being used in a valid photocopier. For Presence Only authentication, we must be assured that an authentication chip is physically present. For Consumable Lifetime authentication we also need to be assured that state data actually came from the authentication chip, and that it has not been altered en route. These issues cannot be separated--data that has been altered has a new source, and if the source cannot be determined, the question of alteration cannot be settled. It is not enough to provide an authentication method that is secret, relying on a home-brew security method that has not been scrutinized by security experts. The primary requirement therefore is to provide authentication by means that have withstood the scrutiny of experts. The authentication scheme used by the authentication chip should be resistant to defeat by logical means. Logical types of attack are extensive, and attempt to do one of three things: Bypass the authentication process altogether Obtain the secret key by force or deduction, so that any question can be answered Find enough about the nature of the authenticating questions and answers in order to, without the key, give the right answer to each question. The logical attack styles and the forms they take are detailed in Section 3.8.1. The algorithm should have a flat keyspace, allowing any random bit string of the required length to be a possible key. There should be no weak keys. The examination of a solution to the requirement of authentication is examined in Section 5. 4.2 Data Storage Integrity Although authentication protocols take care of ensuring data integrity in communicated messages, data storage integrity is also required. Two kinds of data must be stored within the authentication chip: Authentication data, such as secret keys Consumable state data, such as serial numbers, and media remaining etc. The access requirements of these two data types differ greatly. The authentication chip therefore requires a storage/access control mechanism that allows for the integrity requirements of each type. The examination of a solution to the requirement of data storage integrity is examined in Section 7, although the requirements of the two kinds of data are examined briefly here. 4.2.1 Authentication Data Authentication data must remain confidential. It needs to be stored in the chip during a manufacturing/programming stage of the chip's life, but from then on must not be permitted to leave the chip. It must be resistant to being read from non-volatile memory. The authentication scheme is responsible for ensuring the key cannot be obtained by deduction, and the manufacturing process is responsible for ensuring that the key cannot be obtained by physical means. The size of the authentication data memory area must be large enough to hold the necessary keys and secret information as mandated by the authentication protocols. 4.2.2 Consumable State Data Consumable state data can be divided into the following types. Depending on the application, there will be different numbers of each of these types of data items. Read Only ReadWrite Decrement Only Read Only data needs to be stored in the chip during a manufacturing/programming stage of the chip's life, but from then on should not be allowed to change. Examples of Read Only data items are consumable batch numbers and serial numbers. ReadWrite data is changeable state information, for example, the last time the particular consumable was used. ReadWrite data items can be read and written an unlimited number of times during the lifetime of the consumable. They can be used to store any state information about the consumable. The only requirement for this data is that it needs to be kept in non-volatile memory. Since an attacker can obtain access to a system (which can write to ReadWrite data), any attacker can potentially change data fields of this type. This data type should not be used for secret information, and must be considered insecure. Decrement Only data is used to count down the availability of consumable resources. A photocopier's toner cartridge, for example, may store the amount of toner remaining as a Decrement Only data item. An ink cartridge for a color printer may store the amount of each ink color as a Decrement Only data item, requiring three (one for each of Cyan, Magenta, and Yellow), or even as many as five or six Decrement Only data items. The requirement for this kind of data item is that once programmed with an initial value at the manufacturing/programming stage, it can only reduce in value. Once it reaches the minimum value, it cannot decrement any further. The Decrement Only data item is only required by Consumable Lifetime authentication. Note that the size of the consumable state data storage required is only for that information required to be authenticated. Information which would be of no use to an attacker, such as ink color-curve characteristics or ink viscosity do not have to be stored in the secure state data memory area of the authentication chip. 4.3 Manufacture The authentication chip must have a low manufacturing cost in order to be included as the authentication mechanism for low cost consumables. The authentication chip should use a standard manufacturing process, such as Flash. This is necessary to: Allow a great range of manufacturing location options Use well-defined and well-behaved technology Reduce cost Regardless of the authentication scheme used, the circuitry of the authentication part of the chip must be resistant to physical attack. Physical attack comes in four main ways, although the form of the attack can vary: Bypassing the authentication chip altogether Physical examination of chip while in operation (destructive and non-destructive) Physical decomposition of chip Physical alteration of chip The physical attack styles and the forms they take are detailed in Section 3.8.2. Ideally, the chip should be exportable from the USA, so it should not be possible to use an authentication chip as a secure encryption device. This is low priority requirement since there are many companies in other countries able to manufacture the authentication chips. In any case, the export restrictions from the USA may change. The examination of a solution to the requirement of manufacture is examined in Section 10. 5 Authentication Existing solutions to the problem of authenticating consumables have typically relied on physical patents on packaging. However this does not stop home refill operations or clone manufacture in countries with weak industrial property protection. Consequently a much higher level of protection is required. It is not enough to provide an authentication method that is secret, relying on a home-brew security method that has not been scrutinized by security experts. Security systems such as Netscape's original proprietary system and the GSM Fraud Prevention Network used by cellular phones are examples where design secrecy caused the vulnerability of the security [33][91]. Both security systems were broken by conventional means that would have been detected if the companies had followed an open design process. The solution is to provide authentication by means that have withstood the scrutiny of experts. In this part, we examine a number of protocols that can be used for consumables authentication, together with a high level look at the advantages and disadvantages of each particular scheme. We only use security methods that are publicly described, using known behaviors in this new way. Readers should be familiar with the concepts and terms described in Section 3. We avoid the Zero Knowledge Proof protocol. For all protocols, the security of the scheme relies on a secret key, not a secret algorithm. The best way to protect against reverse engineering of any authentication chip is to make the algorithmic inner workings irrelevant (the algorithm of the inner workings must still be must be valid, but not the actual secret). All the protocols rely on a time-variant challenge (i.e. the challenge is different each time), where the response depends on the challenge and the secret. The challenge involves a random number so that any observer will not be able to gather useful information about a subsequent identification. Three protocols are presented for each of Presence Only and Consumable Lifetime authentication. Although the protocols differ in the number of authentication chips required for the authentication process, in all cases the system authenticates the consumable. Certain protocols will work with either one or two chips, while other protocols only work with two chips. Whether one chip or two authentication chips are used the system is still responsible for making the authentication decision. 5.0.1 Single Chip Authentication When only one authentication chip is used for the authentication protocol, a single chip 10 (referred to as ChipA) is responsible for proving to a system 11 (referred to as System) that it is authentic. At the start of the protocol, System 11 is unsure of ChipA's authenticity. System 11 undertakes a challenge-response protocol with ChipA 10, and thus determines ChipA's authenticity. In all protocols the authenticity of the consumable 12 is directly based on the authenticity of the chip associated with it, i.e. if ChipA 10 is considered authentic, then the consumable 12, in which chip 10 is placed, is considered authentic. The data flow can be seen in FIG. 1, and involves a challenge 13 issued from the system, and a response 14 returned by the chip 10. In single chip authentication protocols, System 11 can be software, hardware or a combination of both. It is important to note that System 11 is considered insecure--it can be easily reverse engineered by an attacker, either by examining the ROM or by examining circuitry. System is not specially engineered to be secure in itself. 5.0.2 Double Chip Authentication In other protocols, two authentication chips are required. A single chip 20 (referred to as ChipA) is responsible for proving to a system 21 (referred to as System) that it is authentic. ChipA 20 is associated with the consumable 22. As part of the authentication process, System 21 makes use of a trusted authentication chip 23 (referred to as ChipT). In double chip authentication protocols, System 21 can be software, hardware or a combination of both. However ChipT 23 must be a physical authentication chip. In some protocols ChipT 23 and ChipA 20 have the same internal structure, while in others ChipT 23 and ChipA 20 have different internal structures. The data flow can be seen in FIG. 2, and can be seen to involve a challenge 24 from system 21 to chipA 20 and a request 25 from system 21 to chipT 23, and a response 26 from chipA 20 to system 21 and information 27 from chipT 23 to system 21. 5.1 Presence Only Authentication (Insecure State Data) For this level of consumable authentication we are only concerned about validating the presence of the authentication chip. Although the authentication chip can contain state information, the transmission of that state information would not be considered secure. Three protocols are presented. Protocols P1 and P3 require two authentication chips, while Protocol P2 can be implemented using either one or two authentication chips. 5.1.1 Protocol P1 Protocol P1 is a double chip protocol (two authentication chips are required). Each authentication chip contains the following values: K Key for F.sub.K [X]. Must be secret. R Current random number. Does not have to be secret, but must be seeded with a different initial value for each chip instance. Changes with each invocation of the Random function. Each authentication chip contains the following logical functions: Random[ ] Returns R, and advances R to next in sequence. S[X] Returns S.sub.K [X], the result of applying a digital signature function S to X based upon the secret key K. The digital signature must be long enough to counter the chances of someone generating a random signature. The length depends on the signature scheme chosen (see below). The protocol is as follows: 1. System 21 requests 30 Random[ ] from ChipT 23; 2. ChipT 23 returns 31 R to System 21; 3. System 21 requests 32 S[R] from ChipT 23 and also requests 33 it from ChipA 20; 4. ChipT 23 returns 34 S.sub.KT [R] to System 21; 5. ChipA 20 returns 35 S.sub.KA [R] to System 21; 6. System compares S.sub.KT [R] with S.sub.KA [R]. If they are equal, then ChipA is considered valid. If not, then ChipA is considered invalid. The data flow can be seen in FIG. 3: Note that System 21 does not have to comprehend S.sub.K [R] messages. It must merely check that the responses from ChipA and ChipT are the same. The System 21 therefore does not require the key. The security of Protocol P1 lies in two places: The security of S[X]. Only authentication chips contain the secret key, so anything that can produce a digital signature S[X] from an X that matches the S[X] generated by a trusted authentication chip (ChipT) must be authentic. The domain of R generated by all authentication chips must be large and non-deterministic. If the domain of R generated by all authentication chips is small, then there is no need for a clone manufacturer to crack the key. Instead, the clone manufacturer could incorporate a ROM in their chip that had a record of all of the responses from a genuine chip to the codes sent by the system. The Random function does not strictly have to be in the authentication chip, since System can potentially generate the same random number sequence. However it simplifies the design of System and ensures the security of the random number generator will be the same for all implementations that use the authentication chip, reducing possible error in system implementation. Protocol P1 has several advantages: K is not revealed during the authentication process Given X, a clone chip cannot generate S.sub.K [X] without K or access to a real authentication Chip. System is easy to design, especially in low cost systems such as ink-jet printers, as no encryption or decryption is required by System itself A wide range of keyed signature functions exists, including symmetric cryptography, random number sequences, and message authentication codes. Keyed signature functions (such as one-way functions) require fewer gates and are easier to verify than asymmetric algorithms). Secure key size for a keyed signature functions does not have to be as large as for an asymmetric (public key) algorithm. A key length of 128 bits provides adequate security if S is a symmetric cryptographic function, while a key length of 160 bits provides adequate security if S is HMAC-SHA1. However there are problems with this protocol: It is susceptible to chosen text attack. An attacker can plug the chip into their own system, generate chosen Rs, and observe the output. In order to find the key, an attacker can also search for an R that will generate a specific S[R] since multiple authentication chips can be tested in parallel. Depending on the one-way function chosen, key generation can be complicated. The method of selecting a good key depends on the algorithm being used. Certain keys are weak for a given algorithm. The choice of the keyed one-way functions itself is non-trivial. Some require licensing due to patent protection. A man-in-the middle could take action on the plaintext message R before passing it on to ChipA--it would be preferable if the man-in-the-middle did not see R until after ChipA had seen it. It would be even more preferable if a man-in-the-middle didn't see R at all. If S is symmetric encryption, because of the 128-bit key size needed for adequate security, the chips could not be exported from the USA since they could be used as strong encryption devices. If Protocol P1 is implemented with S as an asymmetric encryption algorithm, there is no advantage over the symmetric case--the keys needs to be longer and the encryption algorithm is more expensive in silicon. Protocol P1 must be implemented with two authentication chips in order to keep the key secure. This means that each System requires an authentication chip and each consumable requires an authentication chip. 5.1.2 Protocol P2 In some cases, System may contain a large amount of processing power. Alternatively, for instances of systems that are manufactured in large quantities, integration of ChipT into System may be desirable. Use of an asymmetrical encryption algorithm allows the ChipT portion of System to be insecure. Protocol P2 therefore, uses asymmetric cryptography. For this protocol, each chip contains the following values: K.sub.T ChipT only. Public key for encrypting. Does not have to be secret. K.sub.A ChipA only. Private key for decrypting. Must be secret. R ChipT only. Current random number. Does not have to be secret, but must be seeded with a different initial value for each chip instance. Changes with each invocation of the Random function. The following functions are defined: E[X] ChipT only. Returns E.sub.KT [X] where E is asymmetric encrypt function E. D[X] ChipA only. Returns D.sub.KA [X] where D is asymmetric decrypt function D. Random[ ] ChipT only. Returns R.vertline.E.sub.K [R]. Advances R to next in random number sequence. The public key K.sub.T is in ChipT 23, while the secret key K.sub.A is in ChipA 20. Having K.sub.T in ChipT 23 has the advantage that ChipT can be implemented in software or hardware (with the proviso that the seed for R is different for each chip or system). Protocol P2 therefore can be implemented as a Single Chip Protocol or as a Double Chip Protocol. The protocol for authentication is as follows: 1. System 21 calls 40 ChipT's Random function; 2. ChipT 23 returns 41 R.vertline.E.sub.KT [R] to System 21; 3. System 21 calls 42 ChipA's D function, passing in E.sub.KT [R]; 4. ChipA 20 returns 43 R, obtained by D.sub.KA [E.sub.KT [R]]; 5. System 21 compares R from ChipA 20 to the original R generated by ChipT 23. If they are equal, then ChipA 20 is considered valid. If not, ChipA 20 is invalid. The data flow can be seen in FIG. 4: Protocol P2 has the following advantages: K.sub.A (the secret key) is not revealed during the authentication process Given E.sub.KT [X], a clone chip cannot generate X without K.sub.A or access to a real ChipA. Since K.sub.T.noteq.K.sub.A, ChipT can be implemented completely in software or in insecure hardware, or as part of System. Only ChipA (in the consumable) is required to be a secure authentication chip. If ChipT is a physical chip, System is easy to design. There are a number of well-documented and cryptanalyzed asymmetric algorithms to chose from for implementation, including patent-free and license-free solutions. However, Protocol P2 has a number of its own problems: For satisfactory security, each key needs to be 2048 bits (compared to minimum 128 bits for symmetric cryptography in Protocol P1). The associated intermediate memory used by the encryption and decryption algorithms is correspondingly larger. Key generation is non-trivial. Random numbers are not good keys. If ChipT is implemented as a core, there may be difficulties in linking it into a given System ASIC. If ChipT is implemented as software, not only is the implementation of System open to programming error and non-rigorous testing, but the integrity of the compiler and mathematics primitives must be rigorously checked for each implementation of System. This is more complicated and costly than simply using a well-tested chip. Although many asymmetric algorithms are specifically strengthened to be resistant to differential cryptanalysis (which is based on chosen text attacks), the private key K.sub.A is susceptible to a chosen text attack It would be preferable to keep R hidden, but since K.sub.T and in fact all of ChipT is public, R must be public as well. If ChipA and ChipT are instances of the same authentication chip, each chip must contain both asymmetric encrypt and decrypt functionality. Consequently each chip is larger, more complex, and more expensive than the chip required for Protocol P1. If the authentication chip is broken into two chips to save cost and reduce complexity of design/test, two chips still need to be manufactured, reducing the economies of scale. This is offset by the relative numbers of systems to consumables, but must still be taken into account. Protocol P2 authentication chips could not be exported from the USA, since they would be considered strong encryption devices. 5.1.3 Protocol P3 Protocol P3 attempts to solve one of the problems inherent in Protocols P1 and P2 in that pairs of X, F.sub.K [X] can be gathered by the attacker (where F is S or E). Protocol P1 is worse in that it is open to a chosen text attack. It is therefore desirable to pass the chosen random number R from ChipT to ChipA without the intermediate System knowing the value of R. Protocol P2 cannot do this since ChipT is public and hence R is not secret. In addition, since R is random, it is not enough to simply pass an encrypted version of R to ChipA, since a random sequence of bits could be substituted for a different random sequence of bits by the attacker. The solution is to encrypt both R and R's digital signature so that ChipA can test if R was in fact generated by ChipT. Since we don't want to reveal R, P3 must be a Double Chip Protocol (ChipT cannot be incorporated into a software System or be included as an ASIC core). Symmetric encryption can therefore be safely used. Protocol P3 therefore uses 2 sets of keys. The first key is used in ChipT to encrypt R and the signature of R. The encrypted R is sent to ChipA where R is extracted and verified by ChipA. If the R is valid, ChipA encrypts R using the second key, and outputs the result. The System sends the output from ChipA back to ChipT where it is compared against the known R encrypted with the second key. For this protocol, each chip contains the following values: K.sub.1 Key for encrypting in ChipT and decrypting in ChipA. Must be secret. K.sub.2 Key for encrypting in ChipA and ChipT. Must be secret. R Current random number. Must be secret and must be seeded with a different initial value for each chip instance. Changes with each successful call to the Test function. The following functions are defined: E[X] Internal function only. Returns E.sub.K [X] where E is symmetric encrypt function E. D[X] Internal function ChipA only. Returns D.sub.K [X] where D is symmetric decrypt function D. S[X] Internal function only. Returns S[X], the digital signature for X. The digital signature must be long enough to counter the chances of someone generating a random signature. 160 bits is the preferred size, giving someone 1 chance in 2.sup.160 of generating a valid signature by random. Random[ ] ChipT only. Returns E.sub.K1 [R.vertline.S[R]]. Test[X] ChipT only. Returns 1 and advances R if E.sub.K2 [R]=X. Otherwise returns 0. The time taken to return 0 must be identical for all bad inputs. The time taken to return 1 must be identical for all good inputs. Prove[X] ChipA only. Calculates Y.vertline.Z from D.sub.K1 [X]. Returns E.sub.K2 [Y] if S[Y]=Z. Otherwise returns 0. The time taken to return 0 must be identical for all bad inputs. The time taken to return E.sub.K2 [Y] must be the same for all good inputs. The protocol for authentication is as follows: 1. System 21 calls 50 ChipT's Random function; 2. ChipT 23 returns 51 E.sub.K1 [R.vertline.S[R]] to System 21; 3. System 21 calls ChipA's Prove function, passing in E.sub.K1 [R.vertline.S[R]]; 4. ChipA 20 decrypts E.sub.K1 [R.vertline.S[R]], and calculates its own S[R] based upon the decrypted R. If the two match, ChipA returns 53 E.sub.K2 [R]. Otherwise ChipA returns 0; 5. System 21 calls 54 ChipT's Test function, passing in the returned E.sub.K2 [R]. ChipT 23 generates its own E.sub.K2 [R] and compares it against the input value. If they are equal, then ChipA is considered valid and a 1 is returned 55 to System 21. If not, ChipA 20 is considered invalid and 0 is returned to System 21. The data flow can be seen in FIG. 5: Protocol P3 has the following advantages: K.sub.1 and K.sub.2 (the secret keys) are not revealed during the authentication process The time varying challenge R is encrypted, so that it is not revealed during the authentication process. An attacker cannot build a table of X, E.sub.K [X] values for K.sub.1 or K.sub.2. An attacker cannot call Prove without a valid R.vertline.S[R] pair encrypted with K.sub.1. K.sub.2 is therefore resistant to a chosen text attack. R only advances with a valid call to Test, so K.sub.1 also not susceptible to a chosen text attack. System is easy to design, especially in low cost systems such as ink-jet printers, as no encryption or decryption is required by System itself. There are a number of well-documented and cryptanalyzed symmetric algorithms to chose from for implementation of E, including patent-free and license-free solutions. A wide range of signature functions exists, from message authentication codes to random number sequences to key-based symmetric cryptography. Signature functions and symmetric encryption algorithms require fewer gates and are easier to verify than asymmetric algorithms. Secure key size for symmetric encryption does not have to be as large as for an asymmetric (public key) algorithm. A minimum of 128 bits can provide appropriate security for symmetric encryption. However, Protocol P3 has a number of its own problems: Although there are a large number of available functions for E and S, the choice of E and S is non-trivial. Some require licensing due to patent protection. Depending on the chosen encryption algorithm, key generation can be complicated. The method of selecting a good key depends on the algorithm being used. Certain keys are weak for a given algorithm. If ChipA and ChipT are instances of the same authentication chip, each chip must contain both symmetric encrypt and decrypt functionality. Consequently each chip is larger, more complex, and more expensive than the chip required for Protocol P1 which only has encrypt functionality. If the authentication chip is broken into 2 chips to save cost and reduce complexity of design/test, two chips still need to be manufactured, reducing the economies of scale. Unfortunately, ChipA must contain both encrypt and decrypt, making the consumable authentication chip the larger of the two chips. Both chips must also contain signature functions, making them more complex than the chip required for Protocol P1. Protocol P3 authentication chips could not be exported from the USA, since they would be considered strong encryption devices. 5.1.4 Additional Notes 5.1.4.1 General Comments Protocol P3 is the most secure of the three Presence Only authentication protocols, since nothing is revealed about the challenge from the response. However, Protocol P3 requires implementation of encryption, decryption and signature functions, making it more expensive in silicon than Protocol P1. In addition, export regulations imposed by the United States make this protocol problematic. With Protocol P2, even if the process of choosing a key was straightforward, Protocol P2 is impractical at the present time due to the high cost of silicon implementation (both key size and functional implementation). Protocol P1 is therefore the current protocol of choice for Presence Only authentication. Eventually, as silicon costs come down with Moore's Law, and USA export regulations are relaxed, Protocol P3 will be preferable to Protocol P1. When silicon costs are negligible or tight integration is required, Protocol P2 may be preferable to Protocol P1, but the security protocol of choice would still remain Protocol P3. 5.1.4.2 Clone Consumable Using Real Authentication Chip Protocols P1, P2 and P3 only check that ChipA is a real authentication chip. They do not check to see if the consumable 22 itself is valid. The fundamental assumption for authentication is that if ChipA is valid, the consumable is valid. It is therefore possible for a clone manufacturer to insert a real authentication chip into a clone consumable. There are two cases to consider: In cases where state data is not written to the authentication chip, the chip is completely reusable. Clone manufacturers could therefore recycle a valid consumable into a clone consumable. This may be made more difficult by melding the authentication chip into the consumable's physical packaging, but it would not stop refill operators. In cases where state data is written to the authentication chip, the chip may be new, partially used up, or completely used up. However this does not stop a clone manufacturer from using the piggyback attack, where the clone manufacturer builds a chip that has a real authentication chip as a piggyback. The attacker's chip (ChipE) is therefore a man-in-the-middle. At power up, ChipE reads all the memory state values from the real authentication chip into its own memory. ChipE then examines requests from System, and takes different actions depending on the request. Authentication requests can be passed directly to the real authentication chip, while read/write requests can be simulated by a memory that resembles real authentication chip behavior. In this way the authentication chip will always appear fresh at power-up. ChipE can do this because the data access is not authenticated. Note that in both these cases, in order to fool System into thinking its data accesses were successful, ChipE still requires a real authentication chip, and in the second case, a clone chip is required in addition to a real authentication chip. Consequently any of these protocols can be useful in situations where it is not cost effective for a clone manufacturer to embed a real authentication chip into the consumable. If the consumable cannot be recycled or refilled easily, it may be protection enough to use a Presence Only authentication protocol. For a clone operation to be successful each clone consumable must include a valid authentication chip. The chips would have to be stolen en masse, or taken from old consumables. The quantity of these reclaimed chips (as well as the effort in reclaiming them) should not be enough to base a business on, so the added protection of secure data transfer (see Protocols C1-C3) may not be useful. 5.1.4.3 Longevity of Key A general problem of these two protocols is that once the authentication key is chosen, it cannot easily be changed. The effect depends on the application of the key. In some instances, if the key is compromised, the results are disastrous. In other cases, it is only a minor inconvenience. For example, in a car/car-key System/Consumable scenario, the customer has only one set of car/car-keys. Each car has a different authentication key. Consequently the loss of a car-key only compromises the individual car. If the owner considers this a problem, they must g | ||||||