PATENT ABSTRACT
In a general aspect, a method for authenticating a plurality of slave devices connected to a master device can include: generating and sending by the master device a respective challenge to each slave device; in each slave device, generating a response to the respective challenge and transmitting it to the master device; verifying by the master device the response of one of the slave devices; returning by the master device the remaining responses to respective slave devices distinct from those that generated the responses; and verifying by each slave device the response returned thereto by the master device and transmitting the result of the verification to the master device.

PATENT DESCRIPTION
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of PCT Application No. PCT/FR2016/050597, filed Mar. 17, 2016, and also claims priority to French Patent Application No. FR15 52306, filed on Mar. 20, 2015, the disclosures of which are incorporated herein by reference in their entireties. 
     
    
     FIELD 
       [0002]    This disclosure relates to techniques for authenticating interconnected electronic devices. 
       BACKGROUND 
       [0003]    Certain apparatuses are designed to be equipped with removable devices such as peripherals or consumables. In certain situations, for reasons of safety or quality of service, the apparatus manufacturer may want the removable devices to be supplied by an authorized source and refuse to use a removable device of unknown origin. Such a situation is, for example, that of a printer and its ink cartridges. 
       SUMMARY 
       [0004]    A method is generally provided for authenticating a plurality of slave devices connected to a master device, where the method can include generating and sending, by the master device, a respective challenge to each slave device; in each slave device, generating a response to the respective challenge and transmitting it to the master device; verifying by the master device the response of one of the slave devices; returning by the master device the remaining responses to respective slave devices distinct from those that generated the responses; and verifying, by each slave device, the response returned thereto by the master device and transmitting the result of the verification to the master device. 
         [0005]    The method can include returning, by the master device, the response of the slave device of rank i to the slave device of rank i+1, where i varies from 1 to N−1, and N is the number of slave devices; verifying, by the master device, the response of the slave device of rank N; if the response verified by the master device is valid, authenticating the slave device of rank N; and if the answer verified by a device of rank j is valid, authenticating the device of rank j−1, where j decreases from N to 2. 
         [0006]    The master device may be a printer and the slave devices may be ink cartridges. 
         [0007]    To carry out the method, a consumable device authenticatable by a master apparatus through a challenge-response mechanism may include a microcircuit configured to perform cryptographic operations and be programmed (configured, etc.) to perform a verification of a response generated to a challenge by another device. 
         [0008]    The consumable device may store a key for authenticating the device itself, and a key for verifying the response generated by the other device. 
         [0009]    The consumable device may be an ink cartridge that can be authenticated by a printer. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0010]    Other advantages and features will become more clearly apparent from the following description of particular embodiments, which are provided for exemplary purposes only and represented in the appended drawings, in which: 
           [0011]      FIG. 1 , is an electronic circuit diagram of an apparatus connected to a plurality of peripheral devices, in accordance with an implementation; 
           [0012]      FIG. 2  is a timing diagram illustrating an authentication sequence for a plurality of peripheral devices, in accordance with an implementation; and 
           [0013]      FIG. 3  is a timing diagram illustrating an implementation of a chained authentication of several peripheral devices, in accordance with an implementation. 
       
    
    
     DETAILED DESCRIPTION 
       [0014]    Apparatuses and methods are described herein, where an apparatus (e.g., a printer) may authenticate one or more removable devices (e.g., ink cartridges) that are installed in (coupled with, etc.) the apparatus. In implementations, such apparatuses and removable devices may each include a cryptographic circuit that use one or more certificates of authenticity. The apparatus can then authenticate (e.g., direct authentication of) each of the removable devices upon power-up, and take preventive measures with devices whose authentication fails. 
         [0015]      FIG. 1  is an electronic block diagram of an apparatus  10  connected to a plurality of peripheral devices D 1  to D 3 . The apparatus  10  may be a printer and the devices D 1 -D 3  may be ink cartridges of different colors that are usable simultaneously. The apparatus  10  may include a processor CPU connected to memories and interfaces via a bus B. A read-only memory ROM may contain a key K′ for authentication operations. This key K′ may be the public key for (corresponding with) a master private key K of a manufacturer of the devices D 1  to D 3 , for example. An interface IF may be designed to communicate with the devices D 1  to D 3 . Each peripheral device to be authenticated may contain a respective private key K 1  to K 3 , the corresponding respective public key K 1 ′ to K 3 ′, and a proof of authenticity of the public key, or certificate of authenticity, in the form of a respective signature S 1  to S 3  of the public key by the master key K. 
         [0016]    Since such authentication operations can be relatively complex, they may be particularly time consuming if the number of devices to be authenticated is large and the computing resources of the apparatus are limited. The approaches described herein can be used to reduce an amount of time and/or computing resources used (e.g., by a master device) for authenticating such peripheral devices as compared to prior approaches. 
         [0017]      FIG. 2  is a timing diagram illustrating an authentication procedure that can be implemented in an apparatus, such as the apparatus of  FIG. 1 , upon power-up. Operations performed by a host processor (HOST) of the apparatus and by the peripheral devices D 1 -D 3  to be authenticated are indicated on respective vertical axes, in the form of rectangles having lengths that are illustrative of the durations of the operations. The rectangles are also drawn with different line types to differentiate the operations associated with the various peripheral devices. Communications between the elements are represented by horizontal arrows. 
         [0018]    From a time t 0 , a program (e.g., implemented using software, firmware and/or hardware) executed by the host starts an authentication procedure of the peripheral devices D 1  to D 3 . The host generates a respective challenge c 1  to c 3  for each of the devices D 1  to D 3 . The challenges may be different and consist of random numbers of standardized size. The challenges c 1  to c 3  are transmitted sequentially to the devices D 1  to D 3 , and then the host waits for the availability of the responses from the devices D 1  to D 3 . 
         [0019]    Each of the devices D 1  to D 3  calculates a respective response r 1  to r 3  to the challenge received according to a mechanism that may be standardized. Each of these responses includes, for example, a signature calculated on the challenge received, a response challenge, and an identifier, using respective secret keys K 1  to K 3  contained in the devices D 1  to D 3 . The calculated responses may be stored by the devices D 1  to D 3 , awaiting their reading by the host. 
         [0020]    From a time t 1 , the host reads the response r 1  of the device D 1  and verifies its validity. This verification may include, for example, authenticating the signature conveyed in the response using the public key K 1 ′ of the device, authenticating the public key K 1 ′ using the device&#39;s certificate S 1 , and authenticating the certificate S 1  using the public key K′ known to the host. 
         [0021]    In practice, the host may periodically poll the device D 1  from the time t 0  to check for the availability of the response r 1 . If the response is not ready in a current poll, the poll is reiterated. If the response is ready, it is read and the host proceeds with verification of the device D 1 . 
         [0022]    From a time t 2 , the host has completed the verification of the response r 1 . If the response r 1  is valid, the host may register (indicate) that the device D 1  is authentic (e.g., D 1  OK). The host then reads the response r 2  produced by the next device D 2 , and proceeds to check (verify) this response. 
         [0023]    From a time t 3 , the host has completed the verification of the response r 2 . If the response r 2  is valid, the host may register (indicate) that the device D 2  is authentic (e.g., D 2  OK). The host then reads the response r 3  produced by the last device D 3 , and proceeds to check this response. 
         [0024]    Finally, at a time t 4 , the host has completed the verification of the response r 3 . If the response r 3  is valid, the host may register (indicate) that the last device D 3  is authentic (D 3  OK). 
         [0025]    If the verification fails for any of the devices D 1  to D 3 , various measures may be taken depending on the context and nature of the failing device, ranging from the degraded operation of the apparatus without the failing device, to total refusal to operate. 
         [0026]    The signature calculations used to generate and verify responses can include relatively complex cryptographic calculations on large numbers up to several hundred bits. The host system may be embedded and of low cost, with limited computing resources, which can be the case for certain printers (or other apparatuses). In this case, the involved verification operations, proportional to the number of devices to be authenticated (for example eight cartridges in certain printers), can reach a duration of several seconds, which may be prohibitive for a power-up phase of the apparatus. 
         [0027]    As shown in  FIG. 2 , each device to be authenticated can be configured to generate responses to the challenges received on the basis of a local secret key and, therefore, can implement cryptographic functions to generate those responses. Such cryptographic functions can be provided, for example, by an inexpensive dedicated microcircuit, having a microcontroller associated with a hardware accelerator, or coprocessor dedicated to cryptographic functions. Even though such a microcontroller may have less computing power than the host processor, the coprocessor performance can be such that it can compute signatures at least as fast as the host processor. 
         [0028]    In order to further accelerate the authentication phase of several devices, computing resources of dedicated microcircuits of peripheral devices can be used to perform (carry out, implement, etc.) one or more authentication operations for the host processor (e.g., for the device  10  in  FIG. 1 ). For instance, rather than a host processor performing verification (authentication) for each peripheral device, approaches described herein can include the distribution (delegation, etc.) of verification (authentication) operations on (across) one or more peripheral devices that may be (at least initially) of an unknown source (type, manufacturer, etc.). Such approaches can further include establishing a chain of trust that ensures that any verification results taken into account (e.g., by a host processor) are produced by devices (e.g., peripheral devices) which have themselves been authenticated. 
         [0029]      FIG. 3  is a timing diagram illustrating an exemplary implementation of such a chained and distributed authentication process (method, phase, etc.). For purposes of illustration and clarity,  FIG. 3  is illustrated and described using the same context and notations as used in, and with respect to  FIG. 2 . 
         [0030]    In  FIG. 3 , from a time t 0 , as in  FIG. 2 , a program executed by the host starts an authentication procedure of the peripheral devices D 1  to D 3 . The host generates respective challenges c 1  to c 3  for each of the devices D 1  to D 3 . The challenges c 1  to c 3  are transmitted sequentially to the devices D 1  to D 3 , and then the host waits for the availability of the responses. 
         [0031]    As in  FIG. 2 , each of the devices D 1  to D 3  calculates a response r 1  to r 3  to the respective challenge received. These responses may be stored by the devices, awaiting their reading by the host. 
         [0032]    From a time t 1 , the host reads the response r 1  of the device D 1 . Instead of initiating a verification calculation of the response, the response r 1  is put on hold, awaiting the availability of another of the devices, for example D 2 . 
         [0033]    At a time t 2 , the host reads the response r 2  produced by the device D 2 . This reading implies that the device D 2  is available. The host immediately transfers the response r 1  to the device D 2  for the latter to carry out verification. The response r 2  is put on hold, awaiting the availability of another of the devices, here D 3 . 
         [0034]    The verification of the device D 1  from the response r 1  that is performed by the device D 2  can be done in the same way as it would be in the host. The result of the verification is stored temporarily in the device D 2  to be read by the host in due course. 
         [0035]    Thus, the peripheral device can be configured to contain the public key K′ (e.g., of the host device) in addition to its keys K 2  and K 2 ′, and to perform verification operations. The verification operations may be implemented by a modification of the microcircuit&#39;s program (e.g., a response generation program). The response transferred by the host may be included in a message identifying the nature of the operations to be performed by the peripheral device. 
         [0036]    At a time t 3 , the host reads the response r 3  produced by the device D 3 . This reading implies that the device D 3  is available. The host immediately transfers the response r 2  to the device D 3  for the latter to carry out verification of the device D 2 . 
         [0037]    To start a chain of trust, the host verifies the response r 3  of the (last) device D 3 . As shown, the verification of the response r 3  by the host is carried out substantially in parallel, or during overlapping time periods, with the verification of the responses r 1  and r 2  by, respectively, the devices D 2  and D 3 . 
         [0038]    A total duration of the authentication phase can, be reduced as compared to serial verification by the host. For instance the total duration of the authentication phase can be equal (substantially equal) to a longest duration of a verification of, in this example, the peripheral devices D 1  (by D 2 ), D 2  (by D 3 ) and D 3  (by the host), plus time of transfers of responses and results between the host and the devices D 1  to D 3 . 
         [0039]    At a time t 4 , the host has finished verifying the response r 3  and, in such implementations, determines that the device D 3  is authentic (e.g., D 3  OK). 
         [0040]    At a time t 5 , the host reads the verification result D 2  OK produced by the device D 3 . Since the device D 3  has been authenticated, the host can trust the verification result that it produces. This result, in such implementations, authenticates the device D 2 . 
         [0041]    Finally, the host reads the verification result D 1  OK produced by the device D 2 . Since the device D 2  has been authenticated, the host can trust the verification result it produces, and this result, in such implementations, authenticates the device D 1 . 
         [0042]    Thus, each of the devices D 3  to D 1  is authenticated, in turn, by the host or by a device which has itself been authenticated according to a chain of trust starting from the host. 
         [0043]    A rogue device could be designed to always provide the host with a valid verification result. But such attempts would be thwarted by the fact that the rogue device would be detected as non-authentic (would not be verified) upon the verification of its response to a challenge, which would be verified by another authenticated device, or by the host. Thus, the result produced by the rogue device would not be taken into account. Moreover, the result produced by the rogue device would relate to another device, and not to the rogue device itself. 
         [0044]    One pass of the method makes it possible to identify a first (if any) non-authentic devices of the chain. If a non-authentic device is identified, that pass may then be stopped, since authentication of the next devices in the chain may be compromised. In the example of  FIG. 3 , if the device D 3  is not authentic, this is detected by the host. The host may then distrust the device D 3  as to the result it provides for the device D 2 , and so on. 
         [0045]    If it is desired to detect all non-authentic devices, several passes of the method may be carried out, starting the chain of trust with a different device each time. Moreover, in order to thwart certain types of attacks, the first pass may further be designed to start the chain on a different device each time, for example, on a device chosen randomly. 
         [0046]    The approaches described herein can be used with any number of interconnected devices. In general, one master device may be designated to authenticate N slave devices. In such implementations, the master device can return a response of a slave device of rank i to a slave device of rank i+1, where i varies from 1 to N−1, and the master device can verify a response of a slave device of rank N. If the answer (response) verified by the master device is valid, the slave device of rank N is determined as being authentic. Then, for j decreasing from N to 2, if the answer verified by the device of rank j is valid, the device of rank j−1 is determined as being authentic. 
         [0047]    The approaches described herein may be used in many types of apparatus (master devices) using consumable devices (slaves). A printer and its ink cartridges were cited. Other examples can include a hot beverage machine and its refills, a tracing table and its pens, a parameter management system and its sensors, etc.