TECHNICAL FIELD

The present disclosure relates to a method, device and system for device authentication and particularly, but not exclusively, to a method, device and system for authenticating a device having predetermined memory content. Aspects of the invention relate to a method, to a device, to a system and to a vehicle.

BACKGROUND

Vehicles are becoming ever more complex in terms of numbers of electronic units distributed about the vehicle. These electronic units are distributed about a communication bus or network of the vehicle. A CAN bus is often currently used as the communication bus, although increasingly other network protocols are being adopted, such as Ethernet. With various units distributed about the vehicle security and safety risks may arise.

For example, a party may compromise an electronic unit of the vehicle to increase performance of that unit or an associated unit such as an engine of the vehicle, often known as remapping or "chipping" the vehicle. The compromise may lead to unsafe performance or performance which is detrimental to the vehicle i.e. to emissions or durability of the vehicle. In some instances, an electronic unit of the vehicle may be accessed in order to overcome security of the vehicle i.e. to gain unauthorised access to the vehicle. In these cases often the compromise of the electronic unit is to write to at least a portion of data stored in the memory of the electronic unit such as to overwrite or modify existing data, or to install malicious program code.

It is therefore desired to provide ways in which vehicle units may authenticate one- another. It is an object of embodiments of the invention to at least mitigate one or more of the problems of the prior art.

SUMMARY OF THE INVENTION

Aspects and embodiments of the invention provide a device authentication method, a device, a system and a vehicle as claimed in the appended claims. According to an aspect of the present invention there is provided a device authentication method, comprising: generating, at a first device, a seed value; determining a challenge based on the seed value; communicating the challenge and the seed value to a second device; signing at least a portion of a memory using the challenge as a key to generate a signature; determining a response based upon a combination of the signature with a modification value determined based on the seed; communicating the response from the second device to the first device; and determining, at the first device, whether the response is valid based upon the seed value. Advantageously the device generating the challenge is able to obtain confidence in the memory content of the device providing the response. Furthermore, the device generating the challenge is able to be a lightweight device, such as one without extensive memory.

The challenge may be determined by applying a first hash function to the seed value. In this way, advantageously, the seed value is not determinable from the challenge.

The method may comprise determining a verification value by applying a second hash function to the seed value, wherein the determining whether the response is valid is based upon the verification value. Advantageously the response value does not disclose the seed value.

The determining whether the response is valid may comprise comparing the response value and the verification value. Advantageously confidence is provided by the response value and the verification value matching. The first and second hash functions may be different which may, advantageously, provide increased security and confidence. The challenge may be determined based upon the seed value and a padding value. The padding value may help to obscure the seed value. The padding value may have a greater size than the seed value, which may further assist in obscuring the seed value. The verification value may be determined by applying the second hash function to the seed value and an additional value. The additional value may be the padding value. Advantageously a greater amount of data assists in providing a secure verification value. The modification value may be determined based upon the seed and a look-up table using the seed as an index to the look-up table. In this way computation of the modification value is advantageously avoided. The combination of the signature with the value determined based on the seed may be determined by a predetermined function. The predetermined function may be an XOR function. The function advantageously obscures the signature.

The first device may be a peripheral device. Advantageously the peripheral device is able to verify the other device.

Optionally one or both of the first and second hash functions are one-way hash functions. Advantageously the use of a one-way hash function prevents a result being used to compute an input.

The padding value may be selected to generate one of a valid or an invalid challenge. The method may comprise disregarding an invalid response if the padding value is selected to generate an invalid challenge. Advantageously the use of an invalid challenge may hinder an eavesdrop-based security compromise.

The seed value may be generated according to a timer, such that a range of seed values are generated over a predetermined period of time. Advantageously variation in the seed values hinders eavesdropping.

According to a further aspect of the present invention there is provided a device, comprising: seed generation means for generating a seed value; challenge generation means for generating a challenge based on the seed value; communication means for communicating the challenge and the seed value to a second device, and for receiving a response value from the second device; and comparison means for determining whether the response is valid based upon the seed value. A device as described above, wherein:

said seed generation means is a seed generation unit or module;

said challenge generation means is a challenge generation unit or module; communication means comprises a communication device or communication unit; and

said comparison means is a comparison unit or module. The aforesaid modules may be implemented in hardware or software, as will be appreciated. The challenge generation means may be arranged to determine the challenge by applying a first hash function to the seed value. The device may comprise verification means for determining a verification value by applying a second hash function to the seed value, wherein the comparison means is arranged for determining whether the response is valid by comparing the verification value and the response value. Said verification means may be a verification unit or module. The module may be implemented in hardware or software.

The device may comprise padding means for generating a padding value, wherein the challenge is determined based upon the seed value and a padding value. Said padding means may be a padding unit or module. The module may be implemented in hardware or software.

The seed value generated by the seed generation means may comprise a first predetermined number of bits and the padding value comprises a second predetermined number of bits larger than the first number of bits; optionally the seed value is appended to the padding value as lowest significant bits.

According to another aspect of the present invention there is provided a device, comprising: communication means for receiving a challenge value and a seed value; signature means for signing at least a portion of a memory using the challenge value as a key to generate a signature; and response generation means for determining a response based upon a combination of the signature with a modification value determined based on the seed value; wherein the communication means is arranged to communicate the response to the first device.

The device may comprise a look-up table, wherein the modification value is determined using the seed as an index to the look-up table.

The response generation means may be arranged to determine the response according to a predetermined function based upon the signature and the modification value.

The predetermined function may be an exclusive-OR function. According to a still further aspect of the present invention there is provided a system, comprising a first device according to an aspect of the invention and a second device according to an aspect of the invention communicably coupled to the first device. According to a yet further aspect of the present invention there is provided a vehicle comprising a system according to an aspect of the invention.

According to a still further aspect of the present invention there is provided computer software which, when executed by a computer, is arranged to perform a method according to an aspect of the invention. The computer software may be stored on a computer readable medium. The computer readable medium may be a non- transitory computer readable media.

Within the scope of this application it is expressly intended that the various aspects, embodiments, examples and alternatives set out in the preceding paragraphs, in the claims and/or in the following description and drawings, and in particular the individual features thereof, may be taken independently or in any combination. That is, all embodiments and/or features of any embodiment can be combined in any way and/or combination, unless such features are incompatible. The applicant reserves the right to change any originally filed claim or file any new claim accordingly, including the right to amend any originally filed claim to depend from and/or incorporate any feature of any other claim although not originally claimed in that manner. BRIEF DESCRIPTION OF THE DRAWINGS

One or more embodiments of the invention will now be described by way of example only, with reference to the accompanying drawings, in which:

Figure 1 shows a method according to an embodiment of the invention;

Figure 2 shows a functional block diagram of a first device according to an embodiment of the invention;

Figure 3 shows a functional block diagram of a second device according to an embodiment of the invention; Figure 4 shows an illustration of a seed value according to an embodiment of the invention; and

Figure 5 is a vehicle according to an embodiment of the invention.

DETAILED DESCRIPTION

Embodiments of the present invention allow devices to authenticate. In particular, embodiments of the invention allow a first device to authenticate that a second device comprises a memory storing data at least a portion of which corresponds to known content. The first and second devices are communicably coupled. The communicable coupling may be wired or wireless. In some embodiments the first and second devices are associated with a vehicle and communicate via a communication bus or network of the vehicle. The communication bus may be a CANbus or, in other embodiments, a communication network which may be based upon Internet Protocol (IP) such as Ethernet, although it will be realised that other protocols are envisaged.

In some embodiments the first device is a device having less data storage capacity than the second device. The second device may comprise a memory having data stored therein which is of a relatively larger size than any memory of the first device.

Figure 1 illustrates a device authentication method 100 according to an embodiment of the invention. The method 100 comprises steps performed by the first and second devices. In some embodiments, steps indicated with a reference numeral beginning with 1 are performed by the first device, whereas steps beginning with 2 are performed by the second device. It will also be realised that no ordering of the steps shown in Figure 1 is implied and that steps may be performed in a different order to that illustrated. Figure 2 illustrates a functional block diagram of an embodiment of the first 300 device. Figure 3 illustrates a functional block diagram of an embodiment of a second device 400. It will be noted that the functional blocks illustrated in Figures 2 and 3 do not necessarily relate to hardware features. For example the first device 300 may comprise processing means formed by one or more processing devices and memory means formed by one or more memory devices. The functional blocks may be formed by one or more software components where the corresponding computer executable instructions are stored in the memory means and executed by the processing means. Similarly the second device 400 may comprise a processing means formed by one or more processing devices and memory means formed by one or more memory devices. The first device 300 illustrated in Figure 2 comprises seed generation means 310 for generating a seed value, challenge generation means 330 for generating a challenge based on the seed value, verification means 340 for determining a verification value, comparison means 350 for comparing the verification value with a received response value and a communication means 360 for communicating with the second device 400. The seed generation means 310 may be a seed generation unit 310 or module. The challenge generation means 330 may be a challenge generation unit 330 or module. The communication means 360 may comprise a communication device 360 or communication unit 360, which may be arranged to communicate according to a predetermined protocol. The comparison means 350 may be a comparison unit or module. The verification means 340 may be a verification unit 340 or module. The aforesaid modules may be implemented in hardware or software, as will be appreciated.

The second device 400 illustrated in Figure 3 comprises signature means 410, look- up means 420, response generation means 430 and communication means 440 for communicating with the first device 300. The second device 400 comprises data storage means 450 for storing data therein which may comprise one or both of program code and data for performing one or more operations. The first device 300 wishes to authenticate that the data storage means 450 of the second device 300 has not been altered. For example, the first device 300 wishes to determine that the second device 400 has not been tampered with to, for example, insert authorised program code into the data storage means 450 or to alter data values stored in the data storage means 450. The data storage means 450 may store data for performing one or more operations such as controlling an engine, gearbox, braking system or other system of the vehicle. The first device 300 wishes to ensure that the second device 400 comprises an original i.e. authorised copy of the data stored in the data storage means 450. The data storage means 450 may correspond to a memory device 450 of the second device 400. The first and second devices 300, 400 when at least occasionally communicably coupled form a system. The system may be located in a vehicle. Operation of the first and second devices 300, 400 will now be explained with reference to the method 100 illustrated in Figure 1 . The method 100 illustrated in Figure 1 is performed by a combination of the first and second 300, 400 devices, as will be explained.

The seed generation means 310 is arranged for generating in step 1 10, at the first device 300, a seed value. The seed value is a random, or at least pseudorandom, value generated by the seed generation means 310. As will be appreciated, the seed generation means 310 may comprise a seed generation algorithm which generates seed values based upon an initial input seed which may be set at a time of first initialising the first device 300 such that generated seed values are pseudorandom. The seed value output by the seed generation means 310 may be represented as a plurality of bits. In some embodiments the seed value is an 8-bit value, although it will be realised that other sizes of seed value may be envisaged. Thus, in an embodiment having an 8-bit seed value, there are 256 possible seed values.

In some embodiments the seed generation means 310 comprises a timer which is arranged to control the generation of seed values. The seed values are generated by the seed generation means 310 according to the timer in order to distribute the generated seed values over a sufficient period of time. The sufficient period of time may be, for example, 12 hours, 24 hours or 48 hours, although it will be realised that other time periods may be selected. The period of time is selected to avoid a large number of seed values being output by the seed generation means 310 in a short space of time, which an attacker may observe in order to compromise the system. Within each smaller period of time, such as 1 hour, only a subset of the possible seed values may be output i.e. 21 seed values from 256 possible seed values during each 1 hour period of a 12 hour repeat period.

In some embodiments the first device 300 comprises padding means 320 for padding the seed value output by the seed generation means 310. The padding means 320 may be a padding unit 320 or module. The padding may be performed in some embodiments of step 1 10. The padding means 320 is arranged to append a plurality of additional bits to the seed value. The additional bits may be predetermined bits, random bits or may be bits selected according to a selection signal to be valid or invalid bits, as will be explained. The bits appended to the seed value are provided to distribute the seed values throughout a larger number space. Figure 4 illustrates a seed value 195 with a first plurality of bits 180 output by the seed generation means 310 and a second plurality of bits 190 appended to the first plurality of bits by the padding means 320. The second plurality of bits 190 may comprise more bits that the first plurality of bits 180. As shown in Figure 4 the first plurality of bits 180 may be least significant bits (LSB) whilst the second plurality of bits 190 may be most significant bits (MSB) of the combined value. However in other embodiments the first plurality of bits 180 may be the MSB, or may be an intermediate portion of the combined value. In some embodiments the second plurality of bits 190 are 24 bits, although it will be realised that other numbers of bits may be envisaged. Thus in one embodiment an output of the padding means 320 is a 32-bit seed value.

In an embodiment having an 8-bit value 180 output by the seed generation means 310 and a 24-bit value output by the padding means 320, if the 24-bit padding 190 is a fixed value then the combined seed value 195 has 256 possible values within a 4,294,967,296 number space. However the 256 seed values are adjacent values within the number space. Therefore, the padding value 190 may be randomly generated or selected according to the seed value 180 in order to distribute valid combined seed values 195 throughout the 4,294,967,296 number space i.e. so that the valid seed values are not substantially adjacent or consecutive numbers. Thus not every combined seed value 195 represents a valid seed value. A signal may be provided within the first device 300 indicative of the validity of the seed value 195 as will be explained. The challenge generation means 330 is arranged to determine a challenge based on the seed value 195 in step 120. The challenge generation means 330 receives the seed value output by the padding means 320. The challenge generation means 330 comprises a hash function. In particular the challenge generation means 330 comprises a one-way cryptographic hash function. The hash function receives input data in the form of the received seed value 195. The hash function determines an output value, or digest, which is not derivable from the seed value 195. The output value is the challenge which is provided to the second device 400. The challenge may have the same number of bits as the seed value 195, such as 32 bits. The challenge and the seed value 195 are communicated to the second device 400. The communication may comprise the first device 300 sending one or more messages to the second device 400 comprising the challenge and the seed value. The communication with the second device is via the communication means 360 which may be a wired or wireless communication interface. The communication means may be a network interface, for example, an Ethernet network. At the second device 400, in step 210 at least a portion of the memory 450 is signed using the challenge as a key to generate a signature. In some embodiments the signature may be determined by signing the entire content of the memory device 450. However in other embodiments only a portion of the content of the memory 450 may be signed to, advantageously, reduce a computation required to perform the signing. The portion of the memory 450 to be signed may be predetermined addresses, such as between first and second addresses, or may be predetermined words stored in the memory 450 such as distributed throughout the memory. More than one portion of the memory 450 may be signed. In some embodiments the portion of the memory signed may be, for example, every nth bit of the memory 450. The value of n may be selected based upon a number of possible challenges provided to the second device 400 i.e. n may be increased proportional to the number of challenges, as discussed below.

The challenge received by the second device 400 is provided to the signature means 410. The signature means 410 is communicably coupled to the memory 450 to access, or to be provided with, data to be signed. The output of the signature means 410 is determined as i = f (k,m) where s is an output signature, f is a function of k which is the challenge and m which is data to be signed from the memory 450. In step 220 a modification value is determined at the second device 200. The modification value is determined based on the seed value 195 received at the second device 400. The modification value is determined using a look-up table 420 stored at the second device 200. The look-up table 420 comprises a plurality of stored modification values. The seed value 195 is used as an index to the look-up table 420 to select the appropriate modification value from amongst a plurality of modification values stored at the second device 200. The seed value 195 received at the second device 200 may be smaller in size i.e. a number of bits, than the modification value. The modification value may be 32 bits, although it will be realised that other sized modification values may be used. In step 230 a response is determined based upon the signature determined in step 210 with the modification value determined in step 220. The response is determined by the response generation means 430 of the second device 400. The modification value is used to modify the signature. Advantageously the modification reduces a likelihood of the response being determined by a third party i.e. more than knowledge of the signature function is required to determine the response. In one embodiment the response is determined by the response generation means 430 as a combination of the signature with the modification value. In some embodiments the combination is a predetermined function, which may be an exclusive-OR (XOR) function in one embodiment, although it will be realised that other functions may be used. That is, in one embodiment, the signature value is subjected to an exclusive-OR with the modification value by the response generation means 430 to determine the response. The response is communicated subsequent to step 230 from the second device 400 to the first device 300. The communication may comprise the second device 400 sending one or more messages to the first device 300 comprising the response value. The communication with the first device 300 is via the communication means 440 which may be a wired or wireless communication interface. The communication means 440 may be a network interface, for example, an Ethernet network.

Step 130 comprises determining the verification value by applying a second hash function to the seed value. The second hash function may be applied to the seed value 180 alone, such as the 8-bit value output by the seed generation means 310 of the first device 300, or may be applied to the seed value 195 with the first plurality of bits 180 output by the seed generation means 310 and the second plurality of bits 190 appended to the first plurality of bits by the padding means 320. The second hash function may be different to the first hash function i.e. the same input values to the first and second hash functions may produce different output values.

The verification means 340 comprises a hash function. In particular the verification means 330 comprises a one-way cryptographic hash function. The hash function receives input data in the form of the received seed value 180, 195. The hash function determines an output value, or digest, which is not derivable from the seed value. The output value is the verification value which is provided to the comparison means 350. The verification value may have the same number of bits as the seed value 195, such as 32 bits. The verification value is output from the verification means 340 to the comparison means 350.

In step 140 it is determined, at the first device 300, whether the response is valid. The determination of the validity of the response is based upon the seed value 195. The verification means 340 of the first device 300 is arranged to determine a verification value. The comparison means 350 is arranged to compare the verification value with the received response value, as will be explained. In step 140 the comparison means 350 is arranged to compare the verification value with the response value received from the second device 400. The comparison means 350 determines whether the response is valid is based upon the verification value. If the verification value provided from the verification means 340 matches the received response value then the second device 400 is determined to be authenticated. That is, the memory 450 of the second device 400 is determined not to have been tampered with or altered. If, however, the verification value does not match the received response value then it is determined that the second device 400 may have been tampered with, such as to store different data in the memory 450 which may be malicious code. Therefore the first device 300 may determine not to communicate further with the second device 400. An output may be provided from the comparison means 350 indicative of the pass or fail of the comparison.

As noted above, a signal may be provided within the first device 300 indicative of the validity of the generated seed value 195. The signal may indicate when a valid seed value has been generated such that the comparison means 350 is able to distinguish valid seed values from invalid seed values. It will be realised that the signal may alternatively or additionally indicate when an invalid seed value has been generated.

In some embodiments, a portion of the padding 190 may be used to select or identify a portion of the response value received from the second device 400 to be compared with the verification value. For example, predetermined bits of the padding 190 may be used to select one more bits of the received response value. In one embodiment, three bits of the padding 190, such as the lowest three padding bits, may be used to identify one of the bits of the response for comparison. Where the received response value is 8 bits wide, the three padding bits may identify one of bit 0 to bit 7 for comparison. Similarly, where the response is 16 bits wide, the 3 padding bits may select 2 bits of the response value for comparison. Advantageously this increases a number of possible challenge values available. Furthermore, dependent upon the increase in number of challenge values, n may be increased to identify a portion of memory 450 for signing. Advantageously, since the first device 300 uses hash functions to determine the challenge and verification values a memory requirement for the first device 300 is relatively low. That is, the first device 300 is not required to store a data structure associating seed values with challenge values and verification values, respectively. Therefore the first device may be a peripheral network device with relatively little memory capacity.

In order for the second device 400 to be successfully compromised, i.e. the content of the memory device 450 of the second device 400 to be changed, and to continue to return response values corresponding to received challenge values then a large memory requirement is imposed on the second device 400. For example, where the challenge and response values are 32 bits, then 64 bits (8 bytes) must be stored per challenge corresponding to the signature and modification values. Therefore a memory requirement at the second device 400 of 32bn bytes is imposed to successfully circumvent the authentication.

It will be appreciated that embodiments of the present invention can be realised in the form of hardware, software or a combination of hardware and software. Any such software may be stored in the form of volatile or non-volatile storage such as, for example, a storage device like a ROM, whether erasable or rewritable or not, or in the form of memory such as, for example, RAM, memory chips, device or integrated circuits or on an optically or magnetically readable medium such as, for example, a CD, DVD, magnetic disk or magnetic tape. It will be appreciated that the storage devices and storage media are embodiments of machine-readable storage that are suitable for storing a program or programs that, when executed, implement embodiments of the present invention. Accordingly, embodiments provide a program comprising code for implementing a system or method as claimed in any preceding claim and a machine readable storage storing such a program. Still further, embodiments of the present invention may be conveyed electronically via any medium such as a communication signal carried over a wired or wireless connection and embodiments suitably encompass the same. All of the features disclosed in this specification (including any accompanying claims, abstract and drawings), and/or all of the steps of any method or process so disclosed, may be combined in any combination, except combinations where at least some of such features and/or steps are mutually exclusive.

Each feature disclosed in this specification (including any accompanying claims, abstract and drawings), may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise. Thus, unless expressly stated otherwise, each feature disclosed is one example only of a generic series of equivalent or similar features.

The invention is not restricted to the details of any foregoing embodiments. The invention extends to any novel one, or any novel combination, of the features disclosed in this specification (including any accompanying claims, abstract and drawings), or to any novel one, or any novel combination, of the steps of any method or process so disclosed. The claims should not be construed to cover merely the foregoing embodiments, but also any embodiments which fall within the scope of the claims.