Consumable authentication protocol and system

Details Consumable authentication protocol and system Consumable authentication protocol and system

2000-02-15

2004-11-09

Barrón, Gilberto (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S167000, C713S170000, C713S172000, C713S155000, C713S159000, C713S176000, C713S181000, C713S189000, C380S046000, C380S260000, C380S262000, C380S259000

Reexamination Certificate

active

06816968

ABSTRACT:

TECHNICAL FIELD
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. In this invention we are concerned not only with validating that an authentication chip is present, but writes and reads of the authentication chip's memory space must be authenticated as well.
BACKGROUND ART
1 Introduction
Manufacturers of systems that require consumables, such as a laser printer that requires toner cartridges, have struggled with the problem of authenticating consumables, to varying levels of success. Most have resorted to specialized packaging. However this does not stop home refill operations or clone manufacture. The prevention of copying is important for two reasons:
To protect revenues
To prevent poorly manufactured substitute consumables from damaging the base system. For example, poorly filtered ink may clog print nozzles in an ink jet printer.
2 Scope
Authentication is an extremely large and constantly growing field. This invention is concerned with authenticating consumables. In most cases, there is no reason to prohibit the use of consumables in a third party product.
The invention concerns an authentication chip that contains an authentication code and circuit specially designed to prevent copying. The chip is manufactured using the standard Flash memory manufacturing process, and is low cost enough to be included in consumables such as ink and toner cartridges.
Once programmed, the authentication chips are compliant with the NSA export guidelines since they do not constitute an encryption device. They can therefore be practically manufactured in the USA (and exported) or anywhere else in the world.
3 Concepts and Terms
This part discusses terms and concepts that are referred to throughout the remainder of the document.
3.1 Symbolic Nomenclature
The following symbolic nomenclature is used throughout this document:
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 | Y
X concatenated with Y
X
 Y
Bitwise X AND Y
X
 Y
Bitwise X OR Y (inclusive-OR)
X ⊕ Y
Bitwise X XOR Y (exclusive-OR)
X
Bitwise NOT X (complement)
X ← Y
X is assigned the value Y
X ← {Y, Z}
The domain of assignment inputs to X is Y and Z
X = Y
X is equal to Y
X ≠ Y
X is not equal to Y
X
Decrement X by 1 (floor 0)
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 ← 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
1
,
the decryption function D relies on key K
2
,
K
2
can be derived from K
1
, and
K
1
can be derived from K
2
.
In most symmetric algorithms, K
1
equals K
2
. However, even if K
1
does not equal K
2
, given that one key can be derived from the other, a single key K can suffice for the mathematical definition. Thus:
E
K
[M]=C
D
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
N
tries, with a 50% chance of finding the key after only half the attempts (2
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
1
, K
2
, and K
3
. The keys are used in the following manner:
E
K3
[D
K2
[E
K1
[M]]]=C
D
K3
[E
K2
[D
K1
[C]]]=M
The main advantage of triple-DES is that existing DES implementations can be used to give more sec

Affiliated with

Also associated with

Rating

Consumable authentication protocol and system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Consumable authentication protocol and system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Consumable authentication protocol and system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3312811