Method and apparatus to quickly authenticate program using a security element

The authenticity of a program executed by a processor is determined by a security element that computes a hash code over re-ordered segments of a known-to-be-authentic copy of a program executed by the processor. The authenticity of the same segments are re-ordered by and provided by the processor to the security element, which computes a second hash code for the re-ordered segments received from the processor. If the hash values for the segments are identical, the program segments are identical. If the hash values for any segment are different, the two programs are different. When a processor's program is determined to be different from a known good copy, the processor can be stopped or an alarm signal generated.

BACKGROUND

Many systems and features in a motor vehicle are controlled by processors, i.e., microprocessors, microcontrollers and digital signal processors, each of which executes program instructions stored in non-transitory memory devices that are coupled to the processors by a bus. (As used herein, the term “bus” refers to a set of electrically-parallel conductors that form a main transmission path between a processor and devices peripheral to the processor, including non-transitory memory devices.) Such memory devices can be located away from a processor while other non-transitory memory devices storing program instructions are resident on the same silicon die as the processor that executes the instructions.

When program instructions are changed, the processor executing the program will change the function or system that it controls accordingly. It is thus possible to change the operating characteristics of a vehicle simply by changing the program instructions executed by a processor that controls a vehicle function or system. It thus becomes important for vehicle manufacturers to maintain the integrity or authenticity of a program that controls a vehicle function. Stated another way, it is important for a vehicle manufacturer to prevent the execution or use of unauthorized modifications of the software that controls the processors within a vehicle.

Some processors that provide critical functions within a vehicle need to perform a program authenticity check in order to ensure that the processor's program has not been modified improperly, i.e., is not unauthorized (by the manufacturer). In order to quickly check a program's authenticity, some processors use a dedicated security element, which can be either external to the processor, i.e., on a different silicon die, or “internal” to the processor, i.e., on the same silicon die, an example of which would be an integrated circuit having multiple processors on the same silicon die. Regardless of where the security element might be located, it is configured (programmed) by the vehicle's manufacturer to confirm or verify the authenticity of the program executed by an associated processor.

Using a security element to verify the authenticity of a processor's program presents at least two challenges. First, the communication between a processor and a security element should not allow someone to read program instructions that might be exchanged between a processor and its associated security element during a verification process. Second, the processors used in a vehicle must start quickly. Since an authenticity check is often performed when a processor starts running, a program authenticity check must be performed quickly. In view of those two challenges, an apparatus and method to quickly authenticate the software or program executed by a vehicle processor, and either inhibit the processor executing an unauthorized program or notify a vehicle operator, would be an improvement over the prior art.

DETAILED DESCRIPTION

FIG. 1depicts an apparatus100to quickly authenticate a computer program for a vehicle-located processor, i.e., a processor, put into a vehicle by a vehicle's manufacturer at the time of its assembly. The apparatus100comprises, of course, a vehicle-located processor102. The processor102is electrically connected to a non-transitory memory device104through a conventional bus106. The memory device and the bus106can be on the same silicon die as the processor102. In other embodiments, the memory device is physically separated from the processor102, i.e., on a different silicon die, and accessed by the processor102using a conventional bus106extending between the processor102and the memory device104.

InFIG. 1, vehicle systems108,110and112are coupled to the bus106and thus communicate with the processor102using the bus106. The operation of those peripheral devices108,110and112is determined or controlled by program instructions114stored in the non-transitory memory element104, regardless of where the memory element104is located and connected to the processor102. Changing any of the instructions can therefore change the operation of the processor102and devices peripheral to it108,110and112.

The apparatus100includes a “security element”150“coupled” to the processor102and pre-programmed to verify the authenticity of the instructions114in the memory device104when the apparatus100is manufactured. In one embodiment, the security element150is considered to be “external” to the processor102because the security element150is a separate processor programmed at the time of the vehicle's manufacture. In other embodiments, the security element150is on the same physical die as the processor102but logically separated from the processor102.

For security purposes, preferred embodiments of the security element150are not reprogrammable. For flexibility purposes, alternate embodiments of the security element150are reprogrammable.

The security element150can be operatively coupled to the processor102at least three (3) different ways. In a first embodiment, the security element150is connected to a bus106that extends between the processor102and peripheral devices108,110,112controlled by the processor102. In a second embodiment, wherein the processor102and security element150are on the same silicon die and that die has on-board non-transitory memory, a processor for the security element150shares an “internal” bus, i.e., a bus on the same silicon die. In a third embodiment, an input/output (I/O) port152is coupled to a corresponding I/O port154on the processor102. An I/O port-to-I/O port communications link156allows information to be exchanged between the processor and the security element150without accessing the bus106.

A control line158extends from the security element to the processor102and carries a signal from the security element150to the processor102. When the signal from the security element150is received by the processor102, the signal causes the processor102to either halt its operation or to raise an alarm notifying the vehicle operator that the program instructions114and the memory device104are not authentic, i.e. have been changed without the manufacturer's authorization. Examples of an alarm include illuminating a warning light or warning sound or disabling a corresponding feature or operation of the vehicle.

Those of ordinary skill in the art should recognize that faster authentication of the program and the memory device104can be achieved by reducing the number of operations that must be performed by the security element150to determine the program's authenticity.

As used herein, the term, “hash function” refers to any mathematical function that can be used to map data of an arbitrary size to data of a fixed size. Numeric values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The Security Hash Algorithm 2 or “SHA-2” algorithm is one example of a hash function that will produce a corresponding hash code.

FIG. 2,FIG. 3andFIG. 4depict steps of a method200for authenticating a computer program for a vehicle-located processor using a security element coupled to a processor,FIG. 3andFIG. 4simply showing steps of the method200that do not fit onFIG. 2. An “authentic” program is one provided to the processor by the vehicle's manufacturer. Stated another way, post-manufacturer modifications to a program that are made by unauthorized third parties are not considered to be authentic.

At a first step202a security element, such as the security element150depicted inFIG. 1, is provided or obtains an “authentic” copy of the program that is supposed to be executed by the processor102. At a second step204, the security element selects a segment or subset of instructions from the authentic copy that was provided to the security element. An “instruction segment” is the content of a predetermined, fixed number of consecutive memory locations e.g., 256, preferably starting from the “beginning” of the program or an address within a memory device.

By way of example, the contents of memory locations0-255can be the first segment of instructions, regardless of whether those locations contain executable instructions or data. The contents of locations255-512can also be a “first” instruction segment. Memory locations0-7,8-16,0-128can also be instruction segments.

In a preferred embodiment, at step206, an instruction segment of the authentic copy of the program is “re-ordered” by the processor in the security element using a pseudo-random re-ordering sequence, which is provided to the security element processor as a “transfer order table.” Stated another way, at step206, the order of the instructions that make up a segment from the authentic copy are essentially “pseudo-scrambled” according to a known and pre-determined scrambling or re-ordering sequence.

Re-ordering instructions in a program segment helps prevent pirating the program, i.e., it helps prevent copying of a program's object (machine) code and a subsequent de-compilation to yield a copy of the program that can be modified, or used to find program vulnerabilities.

At step208, a hash code for the authentic, re-ordered segment (provided at step206) is calculated by the security element processor, and provides what is referred to herein as a “first” hash code for the re-ordered, authentic segment. Any change to the instructions in a program or a program segment will produce a hash that is different from the hash code produced by an authentic copy of the same program or the same program segment. Any different re-ordering of a program's instructions or the instructions in a program segment will also produce a different hash code. The first hash code thus provides a unique representation of an “authentic” segment of a program.

At step210the “first” hash code of an authentic program segment and which was obtained by hashing the re-ordered segment of an authentic copy, is stored in the security element150for use in determining the authenticity of a program copy used by the processor to which the security element150is coupled.

InFIG. 2, a test is conducted at step212to determine whether all segments of the authentic copy of the program have been re-ordered and hashed by the security element. At step214, the method thus returns to step206for a second or next segment of the authentic copy, which is re-ordered at step206, hashed at step208and the hash of the next segment stored into the security element at step210. When all of the segments of the authentic program copy have been hashed, the program proceeds to step218.

Referring now toFIG. 3, at step218, performed by the processor102that executes a program that needs authenticity verification, a first segment of the processor's instructions are re-ordered by the processor in the same way that the first segment of known authentic instructions was re-ordered by the security element at step206. At step220, the re-ordered segment of instructions from the processor102is transferred to the securing element150over a bus connecting the processor to the security element.

(In an alternate embodiment of step218, segments of the processor's instructions are not re-ordered by the processor but are instead sent to the security element where the program segments are re-ordered by the security element in the same way that the known-to-be authentic instructions are re-ordered by the security element at step206.)

Once the re-ordered segment is obtained by the security element, the security element hashes the re-ordered segments it received from the processor102. A “second” hash code is thus computed by a processor in the security element at step222and at step224, the second hash code is compared to the “first” hash code computed by the security element for the same segment of the known, authentic copy of the program.

Referring now toFIG. 4, if the first and second hash codes for the known authentic copy and the processor copy are determined at step226to be equal, the method200assumes that the two corresponding segments of instructions (re-ordered and hashed using the same steps) are identical.

At step228, the segment obtained from the processor is considered to be authentic. The method thus proceeds to get the next segment from the processor at step230. That “next” segment is re-ordered and hashed. The program/method returns to step202where the re-ordering of the next segment is performed followed by its hashing.

Referring again to step226, if the two hash codes are not equal, the segment obtained from the processor102is not authentic. At step234, an inhibit signal is sent to the processor by the security element150.

When the processor102sees the inhibit signal, it can take various different actions responsive thereto. In one embodiment, the inhibit signal provided at step234causes the processor102to halt execution of the counterfeit program. In a second embodiment, the processor102generates and outputs a signal on the bus106which causes an indicator light107on the vehicle's dashboard to illuminate, thereby notifying the driver or vehicle owner that a problem with vehicle firmware authenticity has been detected.

Referring back toFIG. 2, in an alternate embodiment of the method200, step206is followed by an exclusive-ORing step240. The exclusive ORing step240adds an operation or step whereat every re-ordered instruction of a segment is exclusive-ORed (Boolean) by a binary value made up of the same number of binary digits as the re-ordered instructions. In a preferred alternate embodiment, the exclusive-OR values applied at step240are themselves pseudo-randomized such that every re-ordered instruction in a segment is exclusive-OR'ed by a non-sequential value.

FIG. 5depicts both a transfer order table302and an exclusive OR table304. In a preferred embodiment, the transfer order table302, and which is shown inFIG. 3, has a length of 256 entries. Alternate embodiments use transfer order tables of lengths other than 256 entries.

The transfer order table302specifies the order in which 256 consecutive instructions or memory locations of a segment of program are to be re-arranged or “re-ordered” prior to hashing. The exclusive-OR table304comprises values, here 256 values, each of which is exclusive-ORed against an instruction and a segment specified by a corresponding entry of the exclusive OR table.

By way of example, using the transfer order table302shown inFIG. 3, 256 consecutive instructions or (the contents of consecutive memory locations) of a segment of program are re-ordered with the 122ndinstruction, followed by the 53rdinstruction, followed by the 199thinstruction. The last three instructions of the 256 instruction segment are the 123rd, 35thand 207thinstruction. At step240, the 122ndinstruction from the segment is exclusive-ORed by the value “217.” The 53rdinstruction of 256 instructions comprising a segment is exclusive-ORed by the value “15.” The 199thinstruction of 256 instructions of a segment is exclusive-ORed by the value 225.

Those of ordinary skill in the art should recognize that the security element150shown inFIG. 1necessarily includes a processor, not shown inFIG. 1, but well known to those of ordinary skill in the art.

In a preferred embodiment, the processor102requests the security element to authenticate its operating instructions in the memory device104by sending an authentication request. In an alternate embodiment, the security element can request an authentication and take action if the processor doesn't respond thereto. A security element-initiated authentication will typically take place after some predetermined event has occurred or after a predetermined amount of time has elapsed. In such an alternate embodiment, if a processor's program or firmware has been corrupted and the processor doesn't issue an authentication request the secure element will nevertheless detect the problem and take appropriate action.

The foregoing description is for purposes of illustration only. The true scope of the invention is set forth in the following claims.