System and method for securely upgrading firmware

RELATED APPLICATIONS

P-0001[0001] This application relates to and claims priority from U.S. Application Serial No. 60/289,825 filed May 10, 2001 entitled FIRMWARE FIELD UPGRADE SECURITY METHOD, the disclosure of which is hereby incorporated in its entirety by reference.

TECHNICAL FIELD

P-0002[0002] The present invention relates to microcontrollers and, more particularly, to programming such microcontrollers.

BACKGROUND ART

P-0003[0003] Microcontrollers and microprocessors are used to control a variety of equipment and systems. In particular, large appliances such as heaters, air conditioners, thermostats, and refrigerators include programmable microcontrollers that manage and direct their operation. Such microcontrollers typically include, among other features, programmable memory that is programmed during assembly of the appliance to store information about the appliance as well as executable code that permits the microcontroller to perform its intended function.

P-0004[0004] By storing this appliance-controlling executable code in programmable memory, an appliance's performance and operation can be updated by merely reprogramming the microcontroller's programmable memory region. Such reprogramming can be performed in the field and eliminates the need for technicians to stock and install sensitive electronic devices for a large number of different appliances.

P-0005[0005] Along with such flexibility, however, comes some dangers. In particular, the easier it becomes to reprogram the microcontroller, the easier it becomes to install the wrong operating application in an appliance. Also the accessibility of the executable code for re-programming reprogrammable devices, can be targets for malicious or unscrupulous appliance owners or vandals. There is also the danger that proprietary information and appliance characteristics within the microcontroller's memory and executable code can be determined and misappropriated by business competitors.

P-0006[0006] While encryption of information is one option for addressing these concerns, this option typically requires more powerful, and costly, microprocessors than would otherwise be needed to simply control an appliance.

P-0007[0007] Accordingly, there exists an unmet need for a method and system by which firmware in a product (e.g., appliance) with a microcontroller can be upgraded while maintaining the privacy, security and integrity of the firmware throughout the upgrade process.

DISCLOSURE OF INVENTION

P-0008[0008] The present invention relates to a system and method for distributing firmware for a microcontroller's programmable (e.g., flash) memory that secures the privacy and security of the firmware during the upgrade process. In addition, the authenticity and integrity of the firmware is validated during the process and encryption and decryption algorithms are utilized that can be performed even by microcontrollers with {fraction (8/16)} bit cores having limited mathematic processing capabilities.

P-0009[0009] One aspect of the present invention relates to a method and computer software for constructing an encrypted file. According to this aspect of the invention, first and second encryption keys are obtained and used to contract a third encryption key by combining and rearranging the first and second keys. A fourth encryption key is then constructed by selecting a subset of the third encryption key. A source file is first encrypted using the fourth encryption key to generate an intermediate file and the intermediate file is then encrypted using the third encryption key,

P-0010[0010] Another aspect of the present invention relates to a method and computer software for constructing a firmware file for a target microcontroller. According to this aspect of the invention, an unencrypted firmware image file destined for a target microcontroller is obtained. Each byte of the image file is encrypted using a first key, wherein the first key's value partially depends on the device in which the target microcontroller is embedded. The byte-encrypted file is then block encrypted using a second key, wherein the first key is a selected portion of the second key.

P-0011[0011] A further aspect of the present invention relates to a method and computer software for updating firmware in a microcontroller. According to this aspect of the present invention, a microcontroller receives a request to update its current firmware and, in response, resets so as to initiate its boot-up sequence of instructions. First, the present integrity of the firmware is checked to determine whether or not to proceed with updating the firmware. If the firmware's integrity is verified, then the boot-up sequence waits for a time period to see if a command is received to begin the updating process. If no such command is received before the time period expires, then the microcontroller continues by executing the current firmware in normal operational mode. If, however, such a command is received, then the microcontroller continues by executing a firmware programming routine. When the firmware's integrity cannot be positively verified, the boot-up sequence continuously waits for the command to begin the updating process and does not enter normal operational mode.

P-0012[0012] Yet another aspect of the present invention relates to a method and software for upgrading firmware in a microcontroller-controlled device. According to this aspect of the invention, the microcontroller receives an encrypted portion of new firmware and verifies that the new firmware is appropriate for installation based on information in this first portion. The encrypted new firmware is then received along with a first CRC or other integrity value. In response, the new firmware is decrypted on the fly, used to calculate a second CRC (or integrity indicator), and then discarded. The received CRC and the calculated CRC are compared to determine the validity and integrity of the new firmware file before the current firmware is ever modified. Next, the encrypted new firmware is received again. This time, the stream of the encrypted firmware is decrypted using a first algorithm into blocks of intermediate data which, themselves, are decrypted using a second algorithm into an unencrypted firmware image that is written over the current firmware.

P-0013[0013] An additional aspect of the present invention relates to a firmware distribution file that is embodied on a carrier wave. According to this aspect of the innovation, the firmware distribution file includes: a firmware image that is encrypted using a first algorithm to create a first file; a header that contains information about the microcontroller, the firmware image or both; a combination of (a) the first file, (b) the header, and (c) a integrity indicator calculated from (a) and (b), the combination being encrypted using a second algorithm to create a second file; and an integrity indicator calculated from the second file.

BRIEF DESCRIPTION OF DRAWINGS

P-0014[0014] The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

P-0015[0015]FIG. 1 illustrates an exemplary environment for application of embodiments of the present invention.

P-0016[0016]FIG. 2 illustrates a flowchart for constructing an encrypted firmware file according to embodiments of the present invention and also illustrates the transitional file structures corresponding to the different flowchart steps.

P-0017[0017]FIG. 3 illustrates a flowchart of a bootblock routine for update firmware in accordance with an embodiment of the present invention.

P-0018[0018]FIG. 4 illustrates a flowchart for communicating with a microcontroller to upload an encrypted firmware file in accordance with an embodiment of the present invention.

P-0019[0019]FIG. 5 illustrates a flowchart which details decrypting a received firmware file in accordance with an embodiment of the present invention.

P-0020[0020]FIG. 6 illustrates a detailed flowchart of extracting and constructing decryption keys in accordance with an embodiment of the present invention.

P-0021[0021]FIG. 7 illustrates a detailed flowchart of block decrypting and byte decrypting a firmware file in accordance with an embodiment of the present invention.

BEST MODE FOR CARRYING OUT THE INVENTION AND INDUSTRIAL APPLICABILITY

P-0022[0022] To aid with the understanding of the present invention, exemplary embodiments are presented within the context of a specific environments. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures, devices, and processes are shown in block diagram form, herein, in order to avoid unnecessarily obscuring the present invention.

Exemplary Environment

P-0023[0023]FIG. 1 illustrates one typical environment <b>100</b> that can benefit from various embodiments of the present invention. Within the illustrated environment <b>100</b>, a computer <b>114</b> is used to design, test, debug and compile the main operating firmware for an appliance <b>102</b>. The appliance <b>102</b> can be, for example, a heater, a heat pump, air conditioner, or other large appliance under control of a microcontroller. The operating firmware for the appliance <b>102</b> is executed by the microcontroller to control the operation of the appliance <b>102</b>. For example, if appliance <b>102</b> is a heater, the microcontroller may have software routines to obtain information about a room's ambient temperature, information about a desired set point temperature, and information about the current operating state of the heater. Using such information, the operating firmware has other software routines that turn the heater on and off, initiate diagnostic cycles, or possibly communicate with other devices and appliances.

P-0024[0024] According to an embodiment of the present invention, the operating firmware is arranged into an encrypted flash data file <b>116</b> that can be used by the microcontroller once decrypted. Preferably, the computer <b>114</b> includes software routines that can arrange the operating firmware into a file that is formatted such that the file can be used by the microcontroller without further rearrangement, address linking, or other manipulation.

P-0025[0025] To get the encrypted file <b>116</b> to the appliance <b>102</b>, a number of different distribution methods can be used. For example, an appliance manufacturer can have a web site from which technicians or other service personnel can download updated and upgraded firmware (for free or for a fee). Alternatively, or conjunctively, the various firmwares could be sent in periodic updates on a number of physical computer media or through e-mail. Regardless of the distribution method, a technician will obtain the file <b>116</b>, store the file <b>116</b> on a portable computing device <b>112</b> (e.g., a PDA, laptop, etc.), and will arrive at the appliance <b>102</b> to perform a firmware upgrade or update.

P-0026[0026] The exemplary environment described herein includes a portable computing device <b>112</b> carried by a technician and, thus, is locally located with the appliance <b>102</b> during the upgrading of the appliance's operating firmware. The physical connection between the device <b>112</b> and the appliance <b>102</b> can include industry standard communication methods (e.g., RS-232, RS-422), infrared and other wireless communication schemes, or proprietary communications protocols that depend on the specific microcontroller <b>104</b> or appliance <b>102</b>. While it is within the scope of the present invention that the portable computing device <b>112</b> can be a non-portable device located remotely from the appliance <b>102</b>, such an environment is not described herein in detail, so as not to obscure the merits of the present invention, as such an alternative environment differs from the exemplary environment merely by utilizing remote communication capabilities such as network connectivity or modem capabilities rather than local communication methods.

P-0027[0027] The computing device <b>112</b> includes a bootload program for communicating with the appliance <b>102</b>. This bootload program <b>118</b> can be freely distributed to service personnel as it does not contain decrypted keys or any decryption algorithm. Instead, the bootload program executes simple communication steps that initiate and carryout a file transfer operation with the appliance <b>102</b>.

P-0028[0028] The appliance <b>102</b>, as described earlier, includes a microcontroller <b>104</b> that controls its functioning and operation. Such a microcontroller <b>104</b>, as is known in the art, usually has an 8 or 16-bit core that has limited mathematic capability. Even though more complex microcontrollers could be used, their added complexity adds to the cost of design, implementation and support while their additional performance capabilities go mostly unused.

P-0029[0029] In particular, the microcontroller <b>104</b> typically includes a number of memory regions for storing data and information about the appliance <b>102</b>. A skilled artisan would recognize that many functionally equivalent arrangements and circuitry can be used to store the appliance's operational data and application software. The memory arrangement illustrated in FIG. 1 is one exemplary arrangement that includes a programmable memory region <b>106</b> for the microcontroller application software, an EEPROM memory <b>108</b> for less volatile data, and a programmable bootblock memory <b>110</b> that stores bootloading information and other data, such as encryption keys, that can be protected using hardware fuse bits and other security measures.

P-0030[0030] In operation, one embodiment of the present invention uses the bootload program <b>118</b> of the portable computing device <b>112</b> to signal to the appliance's microcontroller <b>104</b> that a firmware upgrade is to be initiated. In response, the microcontroller <b>104</b> executes a software routine that communicates with the portable device <b>112</b> to start receiving information from the device <b>112</b> and overwriting the application memory <b>106</b> with information from the new firmware upgrade file <b>116</b>. Upon completing the download of the information from the firmware file <b>116</b>, the microcontroller <b>104</b> is reset so that it can operate under the control of the newly acquired firmware now stored in the programmable memory <b>106</b>.

Encryption Keys

P-0031[0031] Embodiments of the present invention utilize encryption to protect a firmware file <b>116</b> while it is being distributed. Without the file <b>116</b> being encrypted, information regarding the operation and capabilities of the appliance <b>102</b> can be readily determined from even a cursory examination of the instructions and data included in the file <b>116</b>. Accordingly, as described in more detail below, the file <b>116</b> is encrypted by the computer <b>114</b> before being distributed and remains encrypted until being written to the programmable memory <b>106</b>.

P-0032[0032] The encryption methods and protocols used by the different embodiments described herein utilize a number of keys to encrypt and decrypt information. In the exemplary environments, methods and embodiments described herein, these keys are described as having a particular length (e.g. 32 bits). Other key lengths are also contemplated within the scope of the present invention where shorter and longer keys can be used depending on whether more security or faster performance is desired. These keys, for example, can include:

P-0033[0033] Key A: A key selected at the time the file <b>116</b> is being created on the computer <b>114</b>. This key is embedded in the file <b>116</b> and distributed with the file <b>116</b>. By randomly, or continuously cycling, this key's selection, the encryption scheme can be further strengthened. A 32-bit KeyA has the structure A1H:A1L:A2H:A2L wherein each of the AxH and AxL refer to a byte and H refers to a higher order byte and L refers to the lower order byte.

P-0034[0034] Key B: A key, the same size as KeyA, that is embedded in the bootblock region <b>110</b> during initial programming of the microcontroller <b>104</b> and protected using conventional hardware security measures such as fuse bits. All appliances <b>102</b> of a particular product family have the same KeyB but this key differs among different product families. A 32-bit KeyB has the structure B1H:B1L:B2H:B2L.

P-0035[0035] KeyAB: A key derived from KeyA and KeyB by permuting the different bytes. The exemplary method described herein utilizes the particular 64-bit permutation of: A1H:B1L:B2H:A2L:B1H:A1L:A2H:B2L. Other arrangements of the bytes of KeyA and KeyB are contemplated, as well.

P-0036[0036] SubKeyAB: An 8-bit key derived by taking, for example, every fifth bit of each byte segment in KeyAB. As most characters are represented using an 8-bit code, an 8-bit code is useful for implementing a character encryption routine.

P-0037[0037] If additional security is warranted, 128-bit key encryption keys can be used. For example, KeyA would be a 64-bit key, KeyB would be a 64-bit key and KeyAB would be a 128-bit key. The same permutation scheme would still apply for KeyAB but each particular byte (e.g., B1L, A2H, etc.) would have a length of 16 bit rather than 8 bits.

Flash File Construction

P-0038[0038]FIG. 2 illustrates a flowchart for constructing an encrypted flash file <b>116</b> in accordance with an embodiment of the present invention for updating the firmware in an appliance <b>102</b>. Also included in FIG. 2, to the left of the flowchart steps, is an illustration of the individual modifications to the distribution file <b>116</b> as it is constructed. In creating the firmware for the appliance <b>102</b>, a programmer typically uses a higher-level computer language, for example C, to write (step <b>202</b>) the source code <b>252</b> for the control and operational routines that make up the firmware. Conventional development suites and programming environments operating on the computer <b>114</b> provide tools that will compile, debug and edit (step <b>204</b>) the source code <b>252</b> for a target microcontroller <b>104</b>. The resulting compiled file <b>254</b> will typically be in a recognized industry format, such as an .A90 hex file.

P-0039[0039] In step <b>206</b>, this standard format file <b>254</b> is rearranged to construct a memory image file <b>256</b> that can execute without modification on the microcontroller <b>104</b> and its memory arrangement <b>120</b>. For example, an .A90 hex file <b>254</b> can be stripped of its native header information and column checksums. Furthermore, the data addresses in the .A90 hex file <b>254</b> can be stripped and rearranged to conform to the memory section <b>120</b> of the target microcontroller <b>104</b> by stuffing empty bytes with $00 to fill the entire memory image. Alternatively, instead of using conventional development tools, proprietary tools can be developed which internally integrate the rearrangement steps <b>206</b> described above.

P-0040[0040] In order to later verify the integrity of the image file <b>256</b>, a checksum <b>258</b> can be calculated (step <b>208</b>) and stored for later use.

P-0041[0041] To protect the information that can be explicitly and implicitly discovered from the image file <b>256</b>, the image file <b>256</b> is initially encrypted (step <b>210</b>) using a character encryption method. In a preferred embodiment, this encryption method substitutes for each character (e.g., 8 bits) in the file <b>256</b> with the following algorithm:

CYPHER=((SOURCE′+SubKeyAB+LASTCYPHER) mod 256)XOR(LASTCYPHER)

P-0042[0042] In the above equation, CYPHER is the substituted character, SOURCE is the complement of the original character, and LASTCYPHER is the most recent, previously-substituted character. As can be appreciated, this algorithm implements cipher chaining which utilizes an initial value or vector which, in a preferred embodiment, is SubKeyAB or a derivative thereof.

P-0043[0043] The particular substitution equation identified above is exemplary only and a skilled artisan would recognize that other variations are contemplated. For example, SOURCE does not have to complemented and the modulo dividend of 256 can be changed to suit the character bit length.

P-0044[0044] In order to implement this encryption routine, the software development environment executing on the computer <b>114</b> has at its availability KeyA and KeyB to allow the construction of SubKeyAB from KeyAB. In particular, KeyA can be calculated by the computer <b>114</b> using random number generators or obtained from other conventional cryptographic tools used to generate keys. KeyB is obtained from a highly confidential local or remote database that stores the encryption keys corresponding to particular product families. This is the same key that is embedded in an appliance's bootblock <b>110</b> when that appliance <b>102</b> is manufactured or initially programmed.

P-0045[0045] A header <b>262</b> is then constructed (step <b>212</b>) using information <b>240</b> relating to the intended appliance <b>102</b> for the image file <b>256</b>. The information <b>240</b> can include microcontroller and equipment hardware version, software version, checksum <b>258</b>, software expiration date, product (or appliance) ID, and KeyA. Other information about the software or the target equipment can also be included in this header <b>262</b>. The inclusion of this information will permit the programming routine of the microcontroller <b>104</b> to verify that the image file <b>256</b> is the appropriate file for the particular appliance <b>102</b> and microcontroller <b>104</b> on which it is trying to be installed. Information about products, appliances and software versions can be stored in the computer <b>114</b> or automatically determined by evaluating a software developer's responses and choices to menus and prompts during the creation of the image file <b>256</b>. In a preferred embodiment, KeyA is the first information in the header <b>262</b>. With KeyA being located in this position, a later decryption routine can extract KeyA after only receiving the first portion of the header <b>262</b>.

P-0046[0046] In step <b>214</b>, a cyclic redundancy check (CRC) is calculated for the header <b>262</b> and the encrypted image file <b>264</b>. This CRC will permit verification of the integrity of the encrypted file and header during a later decrypting step.

P-0047[0047] If the source file (<b>262</b>, <b>264</b> and <b>266</b>) were distributed as is, the image file <b>256</b> would be protected by only one level of encryption and KeyA would be transmitted in the clear, thus limiting the protection of the image file <b>256</b>. Accordingly, a second encryption routine (step <b>216</b>) is used to further protect the firmware file that is ultimately distributed.

P-0048[0048] The length of the header <b>262</b> can be adjusted so that the source file (<b>262</b>, <b>264</b>, and <b>266</b>) that is encrypted in step <b>216</b> has a length in bytes that is evenly divisible by a predetermined integer. For example, if the source file (<b>262</b>, <b>264</b>, and <b>266</b>) has a length in bytes evenly divisible by 8 then a 64-bit (i.e., 8 bytes) block cipher can be used to encrypt the source file in step <b>216</b>.

P-0049[0049] In a preferred embodiment, each 64 bit segment of the source file (<b>262</b>, <b>264</b>, and <b>266</b>) is encrypted (step <b>216</b>) using byte permutation and the 64-bit key KeyAB. The permutation order is the same for each 64-bit segment and reorders the 8 bytes (B1:B2:B3:B4:B5:B6:B7:B8) to (B2:B8:B1:B7:B3:B6:B4:B5).

P-0050[0050] The block encryption routine of step <b>216</b> substitutes each 64-bit segment with the following algorithm:

CYPHER=(SOURCE)XOR(KeyAB)+LASTCYPHER

P-0051[0051] where SOURCE is an 8-byte block after it has been permuted.

P-0052[0052] A CRC <b>270</b> is calculated (step <b>218</b>) for the encrypted file <b>268</b> and appended thereto in order to construct the distribution file <b>116</b> that is distributed (step <b>220</b>) for installation by a technician.

Field Operation

P-0053[0053] Because of the two-level encryption scheme, the firmware upgrade distribution file <b>116</b> and KeyA can be distributed via any of a variety of physical and electronic means without fear of revealing protected or sensitive information. Once distributed to technicians or service companies, the firmware upgrade can be loaded or stored in portable diagnostic equipment, PDAs, laptop computers or remotely networked computers <b>112</b>. From whatever equipment <b>112</b> the firmware upgrade file <b>116</b> is loaded on, the file can then be uploaded to the microcontroller <b>104</b> to be stored in the programmable memory area <b>106</b>.

P-0054[0054] Because the file <b>116</b> that is stored on the portable device <b>112</b>, for example a PDA, is encrypted and the image file stored in memory <b>106</b> and executed by the microcontroller <b>104</b> is unencrypted, the present inventive firmware upgrade methods include routines for decrypting the data that is uploaded from the PDA <b>112</b> to the application memory area <b>106</b>.

P-0055[0055] If the decryption scheme is constructed such that it occurs at the PDA <b>112</b>, then any technician with an appropriately programmed PDA would be able to view the image file <b>256</b> as cleartext. If the decryption keys and methods were stored in a region of memory <b>120</b> that could be read from, then decryption of the distribution file <b>116</b> could be accomplished after extracting the necessary information from the memory <b>120</b>. Accordingly, embodiments of the present invention include a firmware upgrade method that performs, at the microcontroller <b>104</b>, decryption of a received encrypted data stream using stored executable code and data that are protected by hardware security fuse bits to prevent access to predetermined memory regions from external readers while still allowing access to those same memory regions from executing instructions.

P-0056[0056] As previously explained, the microcontroller <b>104</b> executes main application software which determines and controls the functioning and operation of the appliance <b>102</b>. This main application, or firmware, typically executes as a continuous loop that is interrupted, intentionally or unintentionally, by external occurrences such as a power reset or an external interrupt signal.

P-0057[0057] Upon reset, the microcontroller <b>104</b> begins execution by jumping to an address known as the reset vector which points to a section of instructions known as a bootblock. Once the sequence of instructions in the bootblock are completed, the control of the microprocessor <b>104</b> jumps to the starting location of the main application, or firmware, and begins execution.

P-0058[0058] In embodiments of the present invention, the bootblock <b>110</b> includes instructions to wait for a ‘Program’ code (or command) and also other instructions that implement a firmware updating or programming routine.

Upgrading Firmware

P-0059[0059]FIG. 3 illustrates a flowchart of upgrading or updating of microcontroller firmware in accordance with an embodiment of the present invention.

P-0060[0060] In step <b>302</b>, the microcontroller <b>104</b> is reset. This reset can be due to a power interruption, actuation of a reset switch, or a software interrupt, or condition, that results in a self-initiated reset. Upon resetting, the microcontroller <b>104</b> enters and begins execution of the bootblock <b>110</b>, in step <b>304</b>. The bootblock <b>110</b> checks, in step <b>306</b>, if a ‘FAILED’ flag is set indicating some error in the programming of the firmware. If this flag is not set, then flow continues with step <b>308</b>. If, however, this flag is set, then the microcontroller <b>104</b> is prevented from controlling the appliance <b>102</b> and, instead, continuously waits, in step <b>310</b>, for receipt of a ‘Program’ command.

P-0061[0061] In step <b>308</b>, the microcontroller also waits for receipt of a ‘Program’ command from an external source, such as device <b>112</b>. However, in step <b>308</b>, the wait only lasts for a predetermined length (e.g. 5 seconds). If no ‘Program’ command is received during this time period, then the microcontroller <b>104</b> continues its execution by jumping to the main application software in step <b>314</b> and normal operation of the appliance commences.

P-0062[0062] A microcontroller, as is known in the art, typically includes a number of input ports for receiving and recognizing data in a variety of formats and protocols. The microcontroller <b>104</b> polls (in steps <b>308</b> and <b>310</b>) one or more of these input ports for the ‘Program’ command sent by the device <b>112</b> being used by a technician.

P-0063[0063] Regardless of whether the polling occurs during step <b>308</b> or step <b>310</b>, the receipt of the ‘Program’ code results in the sending of an acknowledgment to the portable device <b>112</b> in step <b>311</b> and the execution of a programming routine in step <b>312</b> that receives new firmware from the device <b>112</b> and overwrites the existing firmware with this new firmware.

P-0064[0064] The firmware programming routine of step <b>312</b> returns a “success” indicator that is used in step <b>316</b> to determine whether the bootblock flow continues with step <b>320</b> or step <b>318</b>. If the programming routine was unsuccessful, then, in step <b>318</b>, the microcontroller retrieves the RESET vector and jumps there so that the firmware programming can be repeated. If the programming routine was successful, then the ‘FAILED’ flag is cleared in step <b>320</b> and program flow continues, in step <b>322</b>, by jumping to the beginning of the new firmware to begin execution.

Using the Portable Device

P-0065[0065] The details of the firmware programming routine of step <b>312</b> are illustrated by the flowchart of FIG. 5. This routine is executed during the bootloading process of the microcontroller <b>104</b> and involves communication with the device <b>112</b>. While the present invention focuses on the upgrading of firmware of a microcontroller, a software application is necessarily described below, with reference to FIG. 4, that operates on the device <b>112</b>. The functional behavior of this application executing on device <b>112</b> is designed to interoperate with the inventive firmware upgrading methods executed by the microcontroller <b>104</b>. Other software applications that could execute on the device <b>112</b> which may differ in design details but that provide equivalent, or similar, function are contemplated within the scope of the present invention.

P-0066[0066] In step <b>402</b>, a technician using the portable device <b>112</b> establishes a communication channel with the microcontroller <b>104</b> of the appliance <b>102</b>. In designing the communication software routines, some prior knowledge of the various microcontrollers, their command sequences, and their capabilities is needed.

P-0067[0067] Next, in step <b>404</b>, the software application presents to the technician a menu, or similar list, of available firmware upgrade files that are stored on the device <b>112</b>. In response to the technician's selection of a particular firmware file, that file is retrieved, in step <b>406</b>, in preparation for uploading to the microcontroller <b>104</b>.

P-0068[0068] The firmware upgrade file has associated with it a CRC that was distributed along with the firmware file. In retrieving the file in step <b>406</b>, the software also calculates a CRC of the file and compares, in step <b>408</b>, the calculated CRC with the original CRC for agreement. Other data verification methods, such as checksums, can be used instead of a CRC.

P-0069[0069] If the two CRCs are different, then the software notifies the technician using visible, audible, or other means, in step <b>410</b>, and ends the firmware upgrade process. If, however, the two CRCs are in agreement, then the firmware upgrade process can continue with step <b>412</b>, by sending a reset signal to the microcontroller <b>104</b>. After, the reset signal is sent, the software sends, in step <b>414</b>, the ‘Program’ command or code to the microcontroller at regular intervals until an acknowledgment is received from the microcontroller, in step <b>416</b>, indicating that the ‘Program’ command was received and recognized. Step <b>414</b> can include a timer that signals the technician that a predetermined time period has passed since the sending of the reset signal without receipt of an acknowledgment from the microcontroller <b>104</b>. Using this information, the technician can determine if a problem may exist with the established communications channel, the microcontroller <b>104</b>, or the portable device <b>112</b>.

P-0070[0070] Once an acknowledgment is received from the microcontroller <b>104</b>, the software continues, in step <b>418</b>, by transmitting the first part of the encrypted header of the firmware upgrade file. The size of the transmitted portion is the same as the key size used to block encrypt the firmware file. This portion of the header includes a permuted and encrypted version of KeyA which the microcontroller uses in conjunction with KeyB to decrypt the firmware file.

P-0071[0071] The microcontroller <b>104</b> receives the transmitted header portion and then begins receiving and decrypting the firmware upgrade file as described below with reference to FIG. 5. In performing the firmware upgrade, the microcontroller <b>104</b> periodically requests data to be sent from the device <b>112</b> and also transmits various status messages and other information. In response to the communication stream from the microcontroller <b>104</b>, the software, as in step <b>420</b>, receives and processes these messages and requests, streams the encrypted firmware upgrade file to the microcontroller <b>104</b>, and displays an indication of the status of the upgrade process for the benefit of the technician. Upon completion of the upgrade process, the microcontroller <b>104</b> transmits an indication of whether the process was successful or not. This indication of the process's success is displayed, in step <b>422</b>, to the technician.

Firmware Programming Details

P-0072[0072]FIG. 5 illustrates an embodiment of the firmware programming or updating routine introduced as step <b>312</b> in FIG. 3. This routine is executed by the microcontroller <b>104</b> to communicate with the portable device <b>112</b> so that the encrypted firmware upgrade file is received, decrypted and written to the firmware memory region <b>106</b>.

P-0073[0073] To reach step <b>502</b>, the portable device <b>112</b> has already sent a reset request to the microcontroller <b>104</b> and issued the ‘Program’ command which has been received and acknowledged.

P-0074[0074] In response to receiving the acknowledgment from the microcontroller <b>104</b>, the portable device <b>112</b> transmits the first portion of the block encrypted header to the microcontroller <b>104</b>. In step <b>502</b>, this portion of the header is received by the programming routine. In step <b>504</b>, KeyA is extracted from the received portion and KeyB is obtained from a known location in the bootblock memory region <b>110</b>. Using the two keys, the routine constructs KeyAB and SubKeyAB.

P-0075[0075] Once the decryption keys are constructed the microcontroller <b>104</b> signals, in step <b>506</b>, the portable device <b>112</b> to send the entire header which is received in step <b>508</b> and decrypted using KeyAB.

P-0076[0076] The information within the header can be used to ensure that the firmware upgrade is appropriate for the microcontroller <b>104</b>. For example, the decrypted software version can be compared to the software version stored in the EEPROM memory region <b>108</b> to see if a later (or an earlier) version is being installed. A similar comparison can be used to compare compatible Hardware Types and IDs from the header with the information in the EEPROM memory <b>108</b>. Other tests can involve the firmware expiration date, the appliance identification number and any other information stored in the header. The programming routine <b>312</b> can also include sending the extracted information back to the portable device <b>112</b> in order to query the technician whether the upgrade should proceed based on the extracted information. After receiving the technician's approval, for example as in step <b>514</b>, the microcontroller <b>104</b> continues with the upgrade process by requesting the receipt of the entire encrypted file.

P-0077[0077] The file is received, in step <b>516</b> and the data is decrypted, in step <b>518</b>, but is discarded as it is received while a CRC is calculated for the received file on the fly. Accordingly, at no time is an entire decrypted image of the file available on the device <b>112</b> or the appliance <b>102</b> for misappropriation.

P-0078[0078] In step <b>520</b>, the last portion of the encrypted file containing the original, encrypted CRC that was distributed with the file is extracted and retained. The extracted CRC is compared with the CRC calculated in step <b>518</b> to determine the validity and integrity of the firmware file.

P-0079[0079] If the two CRCs do not agree then a failure message is sent to the portable device <b>112</b> in step <b>524</b> and the upgrade process is aborted. If, however, the two CRCs do agree, then a success message is sent to the portable device <b>112</b> in step <b>526</b> and the upgrade process continues with the portable device <b>112</b> resending the entire encrypted file. In addition, the ‘FAILED’ flag is set (See step <b>306</b> of FIG. 3) to indicate that the firmware may be in an unusable condition in step <b>528</b>. Upon successful completion of the firmware programming, this flag is cleared. However, if the programming routine fails or is interrupted, then this flag remains set and the microcontroller reenters the programming mode upon being reset instead of trying to execute faulty firmware.

P-0080[0080] In step <b>530</b>, the programming routine receives the entire encrypted file and, in step <b>532</b>, decrypts by block and by character the firmware file. The decrypted characters from the firmware image file are written, in step <b>534</b>, to the firmware memory region <b>106</b> on the fly. However, as some flash memories require writing of data in page sizes, the decrypted characters may be collected in properly sized segments before being written to the memory <b>106</b>. Within the header, the checksum for the image file is included and is extracted for later use.

P-0081[0081] Once the new firmware image file has been written in the memory region <b>106</b>, a checksum is calculated in step <b>536</b>. This calculated checksum is compared with the checksum extracted from the header to determine if the firmware programming was successful. If the checksums disagree, then the ‘FAILED’ flag remains set and the portable device <b>112</b> is informed of the failure in step <b>538</b>. Under such conditions (as described in FIG. 3), the microcontroller <b>104</b> stays in the programming mode and waits for the portable device <b>112</b> to try again to update the firmware. If, however, the checksums agree, then the ‘FAILED’ flag is cleared and the device <b>112</b> is informed of the success. Under these latter circumstances, the microcontroller <b>104</b> begins operating under control of the new firmware.

Details of Extracting Keys

P-0082[0082] During construction of the encrypted file <b>116</b>, KeyA was permuted across twice its size and encrypted with KeyAB. Thus, the beginning portion of the header in encrypted file <b>116</b> that is twice the size of KeyA contains KeyA encoded within.

P-0083[0083] This portion of the header is received from the device <b>112</b> and decrypted to the point of being able to extract KeyA as described earlier in step <b>504</b>. A flowchart which details the extraction of KeyA from the received encrypted header portion is depicted in FIG. 6. This flowchart continues with the exemplary embodiment previously introduced in which KeyA and KeyB are 32-bit keys used to derive a 64-bit key KeyAB and an 8-bit key SubKeyAB.

P-0084[0084] In step <b>602</b>, the received header portion is de-permuted by reordering bytes (B1:B2:B3:B4:B5:B6:B7:B8) to (B3:B1:B5:B7:B8:B6:B4:B2), and KeyB which is stored in bootblock <b>110</b> is retrieved, in step <b>604</b>, in order to begin decryption of the firmware file.

P-0085[0085] In step <b>606</b>, KeyAB is constructed from KeyA and KeyB by reordering the bytes from the keys as described earlier. However, at this stage of decryption, KeyA is not yet known and, therefore, $00 is substituted in KeyAB for all the bytes from KeyA. This incomplete version of KeyAB is then used to block decrypt the de-permuted bytes by the following algorithm:

SOURCE=(CYPHER) XOR (KeyAB)+LASTCYPHER

P-0086[0086] In the above substitution, SOURCE is the cleartext version of the header portion received from the device <b>112</b>.

P-0087[0087] The first 32 bits of the resulting cleartext reveals KeyA which can be extracted for later use. It is because of the specific rearrangement of both the bytes that make up KeyAB and the rearrangement of the bytes that are block encrypted and decrypted as well as the nature of the XOR operation that allow the incomplete version of KeyAB to decode the encrypted bytes corresponding to KeyA and, thereby, permits its extraction. The specific, exemplary embodiment described herein is but one way of accomplishing the encryption and decryption of KeyA in this manner. Other permutations and rearrangements of bytes which result in KeyA being extractable by an incomplete KeyAB are also contemplated within the scope of the present invention.

P-0088[0088] The availability of KeyB and the discovery of KeyA permit the construction of a complete KeyAB and also SubKeyAB, in step <b>610</b>, for later use. These latter keys are constructed as described earlier.

Details of Decrypting Firmware

P-0089[0089] With the decryption keys available, the firmware programming routine is able to receive, for example, a 64-bit segment and block decode it and then byte decode each byte within the block (see step <b>534</b> of FIG. 5). FIG. 7 illustrates a flowchart which details the decryption, or decoding, of the firmware file <b>116</b>.

P-0090[0090] In step <b>702</b>, an encrypted block is received. The block size varies according to the size of KeyAB which in the exemplary embodiment is 64 bits in size. The received block is de-permuted, in step <b>704</b>, by reordering bytes (B1:B2:B3:B4:B5:B6:B7:B8) to (B3:B1:B5:B7:B8:B6:B4:B2). The de-permuted bytes are then block decrypted, in step <b>706</b>, according to the substitution algorithm:

SOURCE=(CYPHER)XOR(KeyAB)+LASTCYPHER

P-0091[0091] Each decrypted block includes a plurality of character encrypted bytes. Thus, in step <b>708</b>, each encrypted byte is decrypted according to the algorithm:

DECIPHERED=(((CIPHERED)XOR(SubKeyAB))′+SubKeyAB+LASTCYPHER)MOD 256

P-0092[0092] In the above equation, DECIPHERED is the cleartext version of each CIPHERED byte of the firmware image that was encoded and encrypted in the distribution file <b>116</b>. These deciphered bytes are written to the firmware memory region <b>106</b> to update the firmware for the controller <b>104</b>.

P-0093[0093] The particular decryption scheme described above provides significant security but is limited to simple integer manipulations that can be easily and quickly performed by less-powerful microcontrollers having only basic mathematic function.

P-0094[0094] A firmware programming method has been described which can be reinitiated following a programming failure (i.e., re-entrant), prevents future microcontroller execution of the firmware should programming be interrupted or corrupted, validates the authenticity and the integrity of the distributed firmware before the existing firmware is altered, prompts a technician when the firmware appears to be a downgrade, verifies that firmware for different product types cannot be programmed into the wrong product, verifies that the new firmware is compatible with the target hardware, microcontroller and product, mathematically friendly to microcontrollers, and secures the privacy of the firmware since all decryption occurs within.

P-0095[0095] While this invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not limited to the disclosed embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims. The invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive.