Consumable authentication protocol and system

Details Consumable authentication protocol and system Consumable authentication protocol and system

2000-03-02

2002-04-16

Decady, Albert (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Security kernel or utility

Reexamination Certificate

active

06374354

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 OF THE INVENTION
The process of authentication has particular application in any system (chip or software) that manipulates secure data. This includes Internet commerce, peer to peer communication, Smart Cards, Authentication chips, electronic keys, and cryptographic equipment. Whilst the description of the preferred embodiments of the present invention assumes a System/consumable relationship, it is a trivial matter to extend the protocol for other uses. An example is Internet commerce, where each consumer is effectively the consumable, and the Shop is the System. Another usage is Smart Cards, where each smart card can have a unique key, known to the System.
Existing solutions to the problem of authenticating consumables have typically relied on physical patents on packaging. However this does not stop inferior refill operations or clone manufacture in countries with weak industrial property protection. Consequently a much higher level of protection is required.
SUMMARY OF THE INVENTION
This invention is a consumable authentication protocol (described as protocol 3) for validating the authenticity of an untrusted authentication chip, the protocol includes the steps of:
Generating a random number and applying a keyed one-way function to the random number using a first secret key to produce a first outcome, in a trusted authentication chip;
Passing the random number and the first outcome to the untrusted authentication chip;
Applying the keyed one-way function to the random number using the first secret key to produce a second outcome, in the untrusted authentication chip, and then comparing the first and second outcomes;
In the event that the first and second outcomes match, applying the keyed one-way function to the random number together with a data message read from the untrusted chip using a second secret key to produce a third outcome, in the untrusted chip;
Passing the third outcome together with the data message to the trusted chip;
Applying the keyed one-way function to the random number together with a data message read from the untrusted chip using the second secret key to produce a fourth outcome, in the trusted chip;
Comparing the third and fourth outcomes in the trusted chip, and in the event of a match, considering the untrusted chip and the data message to be valid;
Otherwise considering the untrusted 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.
To authenticate a write of new data to the untrusted chip the new data is written to the chip and then the above protocol is undertaken. If the chip is found to be authentic and the new data is the same as the data message read from the untrusted chip, then the write is validated.
The two secret keys are held by both the trusted and untrusted chips and must be kept secret.
The random number does not have to be secret. It is generated by a random function and must be seeded with a different initial value each time. The random number changes with each successful authentication.
The data message may be a memory vector of the authentication chip. A 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.
Each Authentication Chip contains a one-way function based upon the two secret keys.
The trusted chip may contain a test function to apply the keyed one-way function to the random number together with the data message passed from the untrusted chip using the second secret key to produce a fourth outcome which it compares with the third outcome. In the event of a match, the test function may return a value indicating validity, such as 1, and advance the random number if the untrusted chip is valid. Otherwise it may return a value indicating invalidity, such as 0. The time taken to return the value indicating invalidity is the same for all bad inputs.
The untrusted chip may contain a read function to read a first and second value and apply the one-way function to the first value to produce an outcome. If the outcome is the same as the second value it may return a data message and another output, from applying the one-way function to the first value and the data message. Otherwise it returns a value such as 0, indicating failure of the function. The time taken to return the output indicating failure is the same for all bad inputs.
The untrusted chip may also contain a write function to write new data over those parts of the data message that can legitimately be written over.
The one-way function need not be called directly. Instead it may be called indirectly by the random, test and read functions. As a result an attacker must perform a brute force search using multiple calls to the random, read, and test functions to obtain a desired random number, outcome of applying the one-way function to the random number pair.
Having the one-way function called indirectly prevents chosen text attacks on the authentication chip. Also a brute force attack on the first key is required in order to perform a limited chosen text attack on the second key. Any attempt at a chosen text attack on the second key would be limited since the text cannot be completely chosen.
Two different keys are used in order to ensure there is no correlation between applying the one-way function to the random number and the combination of the random number and the data message. The first key is therefore used to help protect the second key against differential attacks.
As an added precaution, the Random and Test functions in the untrusted chip could be disabled so that a brute force attack must be mounted against the more expensive trusted chip.
Similarly, there should be a minimum delay between calls to Random, Read and Test so that an attacker cannot call these functions at high speed. Thus each chip can only give a specific number output pairs away in a certain time period
There are some basic advantages with Protocol 3:
The secret keys are not revealed during the authentication process
Given a random number, a clone chip cannot generate the outcome of applying the one-way function to the combination of the random number and a data message without the key or access to a real authentication chip.
The other parts of a system are easy to design, especially in low cost systems such as ink-jet printers, as no encryption or decryption is required by other parts of the system.
A wide range of key based one-way functions exists, including symmetric cryptography, random number sequences, and message authentication codes.
Keyed one-way functions require fewer gates and are easier to verify than asymmetric algorithms).
Secure key size for a keyed one-way function does not have to be as large as for an asymmetric (public key) algorithm. A minimum of 128 bits can provide appropriate security if the one-way function is a symmetric cryptographic function.
Consequently, with this protocol, the only way to authenticate an untrusted chip is to read the contents of the chip's memory. The security of this protocol depends on the underlying one-way function and the domain of the random number over the set of all systems. Although the one-way function can be any keyed one-way function, there

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-2833763