Secure communication protocol and method therefor

RELATED APPLICATION

0001The present application is related to a commonly assigned, co-pending application by Sibigtroth et al. entitled, “Method and Apparatus For Updating A Count Value”, having attorney docket number TS48143TS, and filed concurrently herewith.

FIELD OF THE INVENTION

0002The present invention relates generally to secure communications, and more particularly, to a secure communication protocol and method therefor.

RELATED ART

0003Wireless control systems are commonly used to provide remote control of a variety of applications. Certain applications require a level of security. Remote keyless entry (RKE) systems have been designed to allow relatively secure control of automobiles and garage door openers. RKE type systems may also be used in other access entry systems and for device authentication.

0004Some RKE systems use a rolling code as part of a transmitted security code. The rolling code is combined with a device-unique key code to form an encryption key. In some applications, multiple encryptions are performed on a single received message. A match with one of the encryptions is enough to validate the transmission. However, performing multiple encryptions consumes significantly more power than performing just one encryption per transmission. Also, for security purposes, each rolling code is used only once and then changed to prevent someone with monitoring equipment from capturing a transmitted code and later using it to gain unauthorized access. Each time a rolling code is changed a program operation of a non-volatile memory is required.

0005Therefore, there is a need for a secure communication system and protocol that consumes less power and uses fewer non-volatile programming operations.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example and not limited by the accompanying figures, in which like references indicate similar elements, and in which:

<figref idref="DRAWINGS">FIG. 1</figref> illustrates, in block diagram form, an RKE transmitter and receiver in accordance with one embodiment.

<figref idref="DRAWINGS">FIG. 2</figref> illustrates, in block diagram form, the RKE transmitter of <figref idref="DRAWINGS">FIG. 1</figref> in more detail.

<figref idref="DRAWINGS">FIG. 3</figref> illustrates a transmitter message in accordance with one embodiment.

<figref idref="DRAWINGS">FIG. 4</figref> illustrates a method for transmitting a message authentication code (MAC) for use in the transmitter message of <figref idref="DRAWINGS">FIG. 3</figref>.

<figref idref="DRAWINGS">FIG. 5</figref> illustrates a method for generating the transmitter message of <figref idref="DRAWINGS">FIG. 3</figref>.

<figref idref="DRAWINGS">FIG. 6</figref> illustrates a method for updating the count portion of the transmitter message of <figref idref="DRAWINGS">FIG. 3</figref>.

<figref idref="DRAWINGS">FIG. 7</figref> illustrates a method for authenticating the transmitter message of <figref idref="DRAWINGS">FIG. 3</figref> in an RKE receiver.

0014Skilled artisans appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help improve the understanding of the embodiments of the present invention.

DETAILED DESCRIPTION OF THE DRAWINGS

0015As used herein, the term “bus” is used to refer to a plurality of signals or conductors which may be used to transfer one or more various types of information, such as data, addresses, control, or status. The conductors as discussed herein may be illustrated or described in reference to being a single conductor, a plurality of conductors, unidirectional conductors, or bidirectional conductors. However, different embodiments may vary the implementation of the conductors. For example, separate unidirectional conductors may be used rather than bidirectional conductors and vice versa. Also, plurality of conductors may be replaced with a single conductor that transfers multiple signals serially or in a time multiplexed manner. Likewise, single conductors carrying multiple signals may be separated out into various different conductors carrying subsets of these signals. Therefore, many options exist for transferring signals.

0016Generally, there is provided, in one form, a secure communication apparatus and protocol that uses a count value as part of a transmitted message. A lower bit portion is stored in volatile memory and an upper bit portion is stored in non-volatile memory. The count value is incremented based on a time interval that is shorter than a time required to transmit the message. The upper bit portion of the count in non-volatile memory is only programmed with a new count value if the upper bit portion of the count value has been used in a previous transmission.

0017The transmitted message includes a transmitter number, a command, and a count, none of which are encrypted, and a message authentication code (MAC). Transmitting the count in the clear makes it easier for the receiver to construct the key needed to compute a new MAC to be checked against the received MAC. Some previous protocols needed to generate multiple keys using the expected next count and several additional counts in case some transmitted messages were not received.

0018Because time is used to increment count values, this could result in numerous updates of the non-volatile portion even when no transmissions are occurring. To avoid unnecessary updates of non-volatile memory, a flag is used to indicate whether the non-volatile portion of the count was ever used in a transmission. If it was not used, there is no need to update the non-volatile memory when the low portion of the count value overflows. The non-volatile portion of the count is also updated after a power interruption to avoid the possibility of reusing a previous count value. If the flag indicates the non-volatile count has not been used in a transmission, it is not necessary to update this count value after a power interruption.

0019The secure communication apparatus and method may be used in, for example, an RKE system for automobiles and garage door openers. Also, the secure communication apparatus may also be used in other access entry systems and for device authentication. In addition, the secure communication apparatus and method may be used in consumable items such as batteries and toner cartridges.

0020In one aspect, there is provided, a method for secure communication between a transmitter and a receiver. The transmitter comprises a non-volatile memory for storing a first portion of a count value, where the count value is updated after an elapse of a period of time. The transmitter comprises a volatile memory for storing a second portion of the count value. In response to receipt of a transmit request, the transmitter sets a use indicator corresponding to the first portion of the count value. Upon elapse of the period of time, the second portion of the count value is updated. The first portion of the count value is updated if the second portion of the count value overflows and the use indicator corresponding to the first portion of the count value is set. Based on at least the count value, a message authentication code is generated. A message transmitted to the receiver comprises at least the message authentication code.

0021In another aspect, there is provided, a method for secure communication between a transmitter and a receiver. A count value is extracted from a message transmitted by the transmitter. The count value has a first portion and a second portion. The second portion of the count value is updated by the transmitter after elapse of a period of time and a first portion of the count value is updated if the second portion of the count value overflows and a use indicator corresponding to the first portion of the count value is set. A learned key segment is retrieved from a receiver memory corresponding to the transmitter if the count value is different from previous count values extracted by the receiver. A message authentication code is generated based on at least the count value retrieved from the receiver memory. The transmitter uses a key comprising at least the count value and the learned key segment. The generated message authentication code is compared to a message authentication code received by the receiver. The message is accepted as a valid message if the generated message authentication code matches the received message authentication code.

0022<figref idref="DRAWINGS">FIG. 1</figref> illustrates, in block diagram form, an RKE transmitter <b>10</b> and receiver <b>20</b> in accordance with one embodiment. Transmitter <b>10</b> is coupled to an omni-directional antenna <b>20</b>, and transmits a message to receiver <b>24</b>. The message is generated in transmitter <b>10</b> in accordance with a protocol <b>22</b>. In one embodiment, the message includes an authentication portion, a count value, a command, and a transmitter number as will be described in more detail in the discussion of <figref idref="DRAWINGS">FIG. 3</figref>. The message is transmitted to and received by the receiver <b>24</b> via antenna <b>28</b> (assuming the receiver is within range). The receiver processes the message in accordance with the protocol <b>26</b>. The message, protocol <b>22</b>, and protocol <b>26</b> include security features that insure no other transmitters except transmitter <b>10</b>, or another authorized transmitter, can control a device having receiver <b>24</b>. In the case of an RKE system for an automobile, the security features insure that only the transmitters intended for use with the automobile can have access to the automobile.

0023<figref idref="DRAWINGS">FIG. 2</figref> illustrates, in block diagram form, the transmitter <b>10</b> of <figref idref="DRAWINGS">FIG. 1</figref> in more detail. Transmitter <b>10</b> includes a central processing unit (CPU) <b>12</b>, non-volatile memory (NVM) <b>14</b>, volatile memory <b>16</b>, and transmitter portion <b>18</b>, each bi-directionally coupled to a bus <b>19</b>. In one embodiment, the protocol <b>22</b> of <figref idref="DRAWINGS">FIG. 1</figref> is implemented in software that is executed on CPU <b>12</b>. In other embodiments, the protocol <b>22</b> may be implemented in software, hardware, or a combination of hardware and software. The protocol <b>22</b> may be stored in NVM <b>14</b> or may be embodied in combinational logic.

0024A portion <b>15</b> of NVM <b>14</b> is for storing a flag value that is for indicating whether or not a count value, stored in NVM <b>14</b>, has been transmitted or not. The NVM <b>14</b> may be implemented with, for example, flash memory, EEPROM (electrically erasable programmable read only memory), MRAM (magneto-resistive random access memory), or other suitable non-volatile memory type. Volatile memory <b>16</b> may be any type of volatile memory such as for example, static random access memory (SRAM), dynamic random access memory (DRAM), or the like.

0025In response to a transmission request signal, a transmitter message is generated in CPU <b>12</b> and communicated via bus <b>19</b> to transmitter portion <b>18</b>. The transmission request signal may be generated in response to pushing a button (not shown) in a device having transmitter <b>10</b>. In the illustrated embodiment, transmitter portion <b>18</b> transmits the transmitter message wirelessly via antenna <b>20</b>. In another embodiment, the transmit request signal may be substituted with a request for device authentication. For example, in a system such as a laptop computer, where the battery contains an authorization tag (analogous to the transmitter in an RKE system), the host laptop would challenge the battery to provide an authentication message or value. The battery (transmitter) would respond with a valid message. In this embodiment, the challenge request is analogous to an RKE button press. Also, the message composition in this embodiment is likely to be different than for an RKE application. In another embodiment, the transmit request signal may be generated by satisfaction of a condition.

0026<figref idref="DRAWINGS">FIG. 3</figref> illustrates a transmitter message <b>30</b> in accordance with one embodiment. In one embodiment, transmitter message <b>30</b> includes 128 bits. In other embodiments, transmitter message <b>30</b> may include a different number of bits. As illustrated in <figref idref="DRAWINGS">FIG. 3</figref>, transmitter message <b>30</b> includes a message authentication code bit field [<b>0</b>-<b>63</b>] labeled “MAC”, a count value bit field [<b>64</b>-<b>95</b>] labeled “COUNT”, a command bit field [<b>96</b>-<b>103</b>] labeled “CMD”, and a transmitter identification bit field [<b>104</b>-<b>127</b>] labeled “TX NUMBER”.

0027The MAC bit field is a 64 bit portion of an AES (Advanced Encryption Standard) encryption result which is used to verify that the sender is an authorized transmitter. It is not possible to de-encrypt the MAC to determine the original 128 bit data block. The count value COUNT is a variable code that is 32 bits long and which is transmitted in each transmitter message <b>30</b>. In the illustrated embodiment, the high 16 bits of the count value are stored in NVM <b>14</b> and the 16 low bits are stored in volatile memory <b>16</b>. The count value COUNT is different for each transmission. In the transmitter, the count value COUNT is a monotonic count which is conditionally updated based on time. In the receiver, the count value COUNT is stored in a non-volatile memory (not shown) related to the transmitter identification TX NUMBER for each valid message that is received. The receiver checks to make sure any new message has a larger count value COUNT than the previous valid message from that transmitter.

0028The command CMD is an 8 bit field in transmitter message <b>30</b> that contains a control command (or data) for use in the application. Example commands in an automotive RKE application include, but are not limited to, lock, unlock, unlock-all, windows down, and start.

0029The transmitter identification TX NUMBER is a unique 24 bit value that is programmed into each transmitter during manufacturing. The TX NUMBER bit field identifies a specific transmitter.

0030<figref idref="DRAWINGS">FIG. 4</figref> illustrates a method for generating a MAC for use in the transmitter message MAC bit field of <figref idref="DRAWINGS">FIG. 3</figref>. An encryption block <b>36</b> may be implemented in software, as illustrated for example in <figref idref="DRAWINGS">FIG. 1</figref> and <figref idref="DRAWINGS">FIG. 2</figref>, for implementing the AES encryption algorithm, or it could be dedicated hardware or some combination thereof. Note that in other embodiments, the particular encryption algorithm may be different. Encryption block <b>36</b> receives an encryption key <b>32</b> at input labeled “KEY”, and encryption data <b>34</b> at an input labeled “DATA”. The encryption key <b>32</b> includes an OEM (original equipment manufacturer) key segment, a count portion, and a learned key segment as illustrated in <figref idref="DRAWINGS">FIG. 4</figref>. The OEM key segment is a secret 32 bit value that is programmed into every transmitter and receiver in a group of compatible devices. This value is stored in a secured portion of NVM memory <b>14</b> and is not transmitted so it is known only to the OEM. The COUNT bit field includes the count value as transmitted in transmitter message <b>30</b>. The learned key segment bit field of encryption key <b>32</b> is a secret 64 bit value which is generated in the transmitter and memorized by the receiver during learning. This value is different each time the learning procedure is repeated. The “learning” procedure is used during manufacturing and any time a transmitter is introduced to a receiver to match certain values in the transmitter to corresponding values in the receiver.

0031The encryption data <b>34</b> includes the transmitter number TX NUMBER, command CMD, count value COUNT, and learned filler code “LEARNED FILLER CODE”. The bit fields TX NUMBER, CMD, and COUNT are the same as described in the discussion of <figref idref="DRAWINGS">FIG. 3</figref>. The bit field LEARNED FILLER CODE includes a secret 64 bit value which is generated in the transmitter and memorized by the receiver during learning. This value is different each time the learning procedure is repeated.

0032Using the encryption key <b>32</b> and the encryption data <b>34</b>, the encryption block <b>36</b> produces an encryption result <b>38</b>. In the illustrated embodiment, the encryption result is truncated such that the 64 least significant bits are used as the MAC portion of the transmitter message. In other embodiments, a different portion of the encryption result <b>38</b> can be used as the MAC portion.

0033<figref idref="DRAWINGS">FIG. 5</figref> illustrates a method <b>40</b> for transmitting the transmitter message <b>30</b> of <figref idref="DRAWINGS">FIG. 3</figref>. In method <b>40</b>, at step <b>42</b>, a request is generated in the transmitter to send a message <b>30</b>. The request may be generated by pushing a button (not shown). At step <b>44</b>, a USED flag bit is set in portion <b>15</b> of NVM <b>14</b> to indicate that the count value COUNT has been used. The count value COUNT will be updated as described in the discussion of <figref idref="DRAWINGS">FIG. 6</figref>, below. At step <b>46</b>, the count value COUNT is read from NVM <b>14</b>. At step <b>48</b>, a MAC is generated as described above regarding <figref idref="DRAWINGS">FIG. 4</figref>. The MAC is included in the MAC bit field of message <b>30</b> as illustrated in <figref idref="DRAWINGS">FIG. 3</figref>. At step <b>50</b>, message <b>30</b> is transmitted to a receiver.

0034<figref idref="DRAWINGS">FIG. 6</figref> illustrates a method <b>60</b> for updating the count portion of the transmitter message of <figref idref="DRAWINGS">FIG. 3</figref>. In method <b>60</b>, at step <b>62</b>, both the high bit portion and the low bit portion of the count value COUNT are cleared. As discussed above, the high portion is the 16 most significant bits and the low portion is the 16 least significant bits. The high portion is stored in NVM <b>14</b> and the low portion is stored in volatile memory <b>16</b>. At decision step <b>64</b>, it is determined if a time period Δt has expired. In the illustrated embodiment, Δt is about one second, in other embodiments, Δt is any period less than a time it takes to transmit a new message <b>30</b>. If Δt has not expired, then the NO path is taken back to the entry into step <b>64</b>. When Δt expires, the YES path is taken to step <b>66</b>. At step <b>66</b>, the lower 16 bit portion of count value COUNT is updated. In the illustrated embodiment, the low portion is updated by incrementing the count value COUNT by one. In other embodiments, the count value COUNT may be updated by incrementing or decrementing by any number. At decision step <b>68</b>, it is determined if a memory portion for storing the low portion has overflowed. If the low portion has not overflowed, the NO path is taken back to step <b>64</b>. If the low portion has overflowed, or exceeded its maximum value, the YES path is taken to decision step <b>70</b>. At decision step <b>70</b> it is determined if the flag in portion <b>15</b> (<figref idref="DRAWINGS">FIG. 2</figref>) has been set to indicate that the count value COUNT currently stored in memory has already been used at least once. If the count value has not been used, or transmitted, then it is not necessary to update the count value and the method continues at step <b>64</b>. However, if the “USED” flag has been set, indicating that the count value COUNT has been transmitted already, then the YES path is taken to step <b>72</b>. At step <b>72</b>, the high portion of count value COUNT is updated by incrementing. In other embodiments, the high portion of COUNT may be updated in some other way. At step <b>74</b>, the “USED” flag is cleared.

0035If power is removed from the transmitter <b>10</b>, for example, when exhausted batteries are replaced, then a power-on-reset (POR) operation is run by the CPU <b>12</b>. In method <b>60</b>, at step <b>76</b>, a POR event causes a POR operation to run. At step <b>78</b>, the low portion is cleared to maximize the length of time until the next NVM update. After step <b>78</b> the method continues at step <b>70</b>.

0036<figref idref="DRAWINGS">FIG. 7</figref> illustrates a method <b>80</b> for authenticating transmitter message <b>30</b> of <figref idref="DRAWINGS">FIG. 3</figref> in an RKE receiver. At step <b>82</b>, the message <b>30</b> is received by receiver <b>24</b> (<figref idref="DRAWINGS">FIG. 1</figref>). At step <b>84</b>, the count value COUNT is extracted from message <b>30</b>. At step <b>86</b>, the transmitter identifier TX NUMBER is extracted from message <b>30</b>. At decision step <b>88</b>, it is determined if the count value COUNT is different from all previously used count values. If the count value COUNT is the same as a previously used count value, then the message <b>30</b> is ignored as being invalid. If the count value COUNT is not the same as a previously used count value, then the YES path is taken to step <b>92</b>. At this point the receiver needs to generate a MAC as described above regarding <figref idref="DRAWINGS">FIG. 4</figref>. At step <b>92</b>, the learned key segment (<figref idref="DRAWINGS">FIG. 4</figref>) of the encryption key <b>32</b> is retrieved from a look-up table stored in NVM <b>14</b>. At step <b>94</b>, the encryption key <b>32</b> is formed as described in the discussion of <figref idref="DRAWINGS">FIG. 4</figref>. At step <b>96</b>, the encryption data <b>34</b> is formed. At step <b>98</b>, the encryption result <b>38</b> is computed. At step <b>100</b>, the MAC is extracted from the encryption result <b>38</b> computed at step <b>98</b>. At decision step <b>102</b>, it is determined if the extracted MAC is the same as the MAC received in the message <b>30</b>. If the extracted MAC is not equal to the received MAC, the NO path is taken to step <b>104</b> and the message is ignored as not being a valid message from an authorized transmitter. If the extracted MAC is equal to the received MAC, then the YES path is taken to step <b>106</b> and the message <b>30</b> is accepted and the count value COUNT is updated as described in the discussion of steps <b>72</b> and <b>74</b> of <figref idref="DRAWINGS">FIG. 6</figref>.

0037In the foregoing specification, the invention has been described with reference to specific embodiments. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the present invention as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of present invention.

0038Benefits, other advantages, and solutions to problems have been described above with regard to specific embodiments. However, the benefits, advantages, solutions to problems, and any element(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential feature or element of any or all the claims. The terms a or an, as used herein, are defined as one or more than one. The terms including and/or having, as used herein, are defined as comprising (i.e., open language). As used herein, the terms “comprises,” “comprising,” or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus.