Cryptographic Architecture with Instruction Masking and other Techniques for Thwarting Differential Power Analysis

Abstract

An apparatus and method for preventing information leakage attacks that utilize timeline alignment. The apparatus and method inserts a random number of instructions into an encryption algorithm such that the leaked information can not be aligned in time to allow an attacker to break the encryption.

1 . A cryptographic architecture comprising:
 a processor;   a memory containing an encryption algorithm coupled to said processor; and   a control flag register and a shift control counter coupled to said processor for controlling the state operation of the processor, the shift control counter adapted to count a number of desired real shift instructions for carrying out the encryption algorithm;   the control flag register being set and/or reset by instructions stored in said memory and issued by the processor, the control flag register assuming a particular state when shift instructions are to be performed as pseudo shift instructions by the processor.   
     
     
         2 . The cryptographic architecture of  claim 1  wherein the control flag register and a shift control counter are interconnected by a pair of gates, a first gate of said pair of gates having an output coupled to a first input of a second gate of said pair of gates, the first gate having one input thereof coupled to an output of the control flag register and having another input thereof coupled to an output of the second gate, the second gate having another input coupled to the shift control counter, the output of the second gate also being coupled to the processor for halting state operation of the processor. 
     
     
         3 . The cryptographic architecture of  claim 2  wherein the desired shift instructions and the pseudo shift instructions occur in a plurality of groups, each group of shift instructions comprising a fixed number of shift instructions, with the number of pseudo shift instructions in each group varying by group. 
     
     
         4 . The cryptographic architecture of  claim 3  wherein at least one group comprises all pseudo shift instructions and at least one another group comprises all real shift instructions. 
     
     
         5 . The cryptographic architecture of  claim 1  wherein the desired shift instructions and the pseudo shift instructions occur in a plurality of groups, each group of
 instructions comprising a fixed number of shift instructions, with the number of pseudo shift instructions in each group varying by group. 
 
     
     
         6 . The cryptographic architecture of  claim 5  wherein at least one group comprises all pseudo shift instructions and at least one another group comprises all real shift instructions. 
     
     
         7 . The cryptographic architecture of  claim 1  wherein said processor is a 16-bit, 32-bit or 64-bit processor. 
     
     
         8 . The cryptographic architecture of  claim 1  wherein said encryption algorithm is a Data Encryption Standard (DES) algorithm. 
     
     
         9 . A system for thwarting differential power analysis, said system comprising:
 means for running an encryption algorithm; and   means for inserting a random or a predetermined number of pseudo instructions into said encryption algorithm, said pseudo instruction mimicking real instructions in terms of at least energy consumption without affecting the encryption algorithm being run.   
     
     
         10 . The system of  claim 9  wherein said means for running an encryption algorithm comprises:
 a processor; and 
 a memory storing the encryption algorithm coupled to said processor. 
 
     
     
         11 . The system of  claim 10  wherein said processor is a 16-bit, 32-bit or 64-bit processor. 
     
     
         12 . The system of  claim 10  wherein said encryption algorithm is a Data Encryption Standard (DES) algorithm. 
     
     
         13 . The system of  claim 9  wherein the pseudo instructions emulate bit-wise shift instructions power consumption wise. 
     
     
         14 . The system of  claim 9  wherein the pseudo instructions comprise a set of randomized instructions. 
     
     
         15 . The system of  claim 9  wherein said means for inserting comprises: a control flag register coupled to said processor; and a random number generator coupled to said control flag register. 
     
     
         16 . The system of  claim 15  wherein said random number generator is a one-bit random number generator. 
     
     
         17 . A system for decorrelating side channel information, said system comprising:
 means for running a Data Encryption Standard (DES) algorithm, said DES algorithm comprising a plurality of substitution/permutation box entry address evaluations; and   means for inserting a number of pseudo instructions in at least one of said plurality of substitution/permutation box entry address evaluations, the pseudo instructions mimicking, energy consumption-wise, corresponding real instructions, but without affecting the running of the DES algorithm.   
     
     
         18 . The system of  claim 17  wherein said means for running a DES algorithm comprises:
 a processor; and 
 a memory containing an encryption algorithm coupled to said processor and 
 a plurality of lookup tables coupled to said processor, said plurality of substitution/permutation boxes being implemented in said plurality of lookup tables. 
 
     
     
         19 . The system of  claim 18  wherein said processor is a 16-bit, 32-bit or 64-bit processor. 
     
     
         20 . The system of  claim 17  wherein said means for inserting includes a control flag register coupled to said processor for causing said processor to issue pseudo instructions, which do not update registers associated with the processor, rather than corresponding real instructions which would update at least register associated with the processor. 
     
     
         21 . The system of  claim 20  wherein said means for inserting further includes a shift control counter for inserting additional real instructions into the DES algorithm if a connection between the control flag register and the processor is successfully probed by an attacker, the additional real inserted instructions being effective to disable calculations performed by the DES algorithm. 
     
     
         22 . The system of  claim 20  wherein said means for inserting further includes a random number generator coupled to said control flag register. 
     
     
         23 . The system of  claim 22  wherein said random number generator is a one-bit random number generator. 
     
     
         24 . A system for decorrelating side channel information, said system comprising:
 means for running a Data Encryption Standard (DES) algorithm, said DES algorithm comprising a plurality of substitution/permutation box entry address evaluations; and   means for inserting a fixed and/or a random number of pseudo instructions in at least one of said plurality of substitution/permutation box entry address evaluations.   
     
     
         25 . The system of  claim 24  wherein said means for running a DES algorithm comprises:
 a processor; and 
 a memory module containing an encryption algorithm coupled to said processor and a plurality of lookup tables coupled to said processor, said plurality of substitution/permutation boxes being implemented in said plurality of lookup tables. 
 
     
     
         26 . The system of  claim 25  wherein said processor is a 16-bit, 32-bit or 64-bit processor. 
     
     
         27 . A method of altering a power trace of a cryptographic architecture comprising:
 running an encryption algorithm;   setting a control flag; and   performing a number of pseudo instructions when said control flag is set, said pseudo instructions mimicking corresponding real instructions energy consumption wise without affecting calculations performed according to said encryption algorithm.   
     
     
         28 . The method of  claim 27  wherein in the setting a control flag further comprises halting a state machine of a processor running said encryption algorithm. 
     
     
         29 . The method of  claim 28  wherein the halting of the state machine further comprises disabling a destination register in said state machine. 
     
     
         30 . The method of  claim 27  further comprising modifying said encryption algorithm to shuffle an access order of a plurality of lookup tables. 
     
     
         31 . The method of  claim 27  wherein said encryption algorithm is a Date Encryption Standard (DES) algorithm. 
     
     
         32 . The method of  claim 27  further comprising resetting said control flag, wherein said step of resetting further comprises sending a signal from a random number generator to a control flag register. 
     
     
         33 . A cryptographic CPU architecture comprising:
 an ALU;   a control flag;   a plurality of registers for normally receiving output of the ALU in response to an arithmetic instruction; and   an additional register for receiving output of the ALU, in lieu of one of the plurality of registers, in response to an arithmetic instruction when the control flag is set.   
     
     
         34 . The cryptographic CPU architecture of  claim 33  further comprising:
 a first program counter; and 
 a second program counter; 
 wherein the first and second program counters are responsive to the state of said control flag so that the first program counter is enabled where said control flag is not set and so that the second program counter is enabled where said control flag is set; and 
 wherein an enabled one of said first and second program counters fetches instructions from an instruction memory. 
 
     
     
         35 . The cryptographic CPU architecture of  claim 34  wherein the ALU outputs the results of an arithmetic instruction fetched by the first program counter to one of said plurality of registers and the ALU outputs the results of an arithmetic instruction fetched by the second program counter to said additional register. 
     
     
         36 . The cryptographic CPU architecture of  claim 35  wherein the additional register is a dummy register having no output for transferring data to the ALU. 
     
     
         37 . The cryptographic CPU architecture of  claim 36  wherein the registers and the additional register each have an associated gate for controlling the transfer of data to the registers and to the additional register, the associated gates being controlled by the state of said control flag. 
     
     
         38 . The cryptographic CPU architecture of  claim 33  wherein the additional register is a dummy register having no output for transferring data to the ALU. 
     
     
         39 . The cryptographic CPU architecture of  claim 33  wherein the registers and the additional register each have an associated gate for controlling the transfer of data to the registers and to the additional register, the associated gates being controlled by the state of said control flag. 
     
     
         40 . A method of concealing data processing occurring in a CPU from power analysis during the execution of a program, the method comprising:
 (i) at a point during the execution of the program, inserting a random number of program counter cycles instruction fetch cycles,   (ii) while the random number of instruction fetch cycles are occurring, fetching instructions from memory, executing those instructions in program sequence, but inhibiting updating of normal memory locations based on the execution of those instructions; and   (iii) at the conclusion of said random number of instructions, then recommencing normal program execution by refetching the same instructions which were initially fetched while the random number of instruction fetch cycles were occurring, but when the instructions are refetched, updating memory locations in a normal manner for the CPU.   
     
     
         41 . The method of  claim 40  wherein the insertion of said random number of program counter cycles instruction fetch cycles is controlled by s state of a random instruction mask control flag. 
     
     
         42 . The method of  claim 40  wherein, while the random number of instruction fetch cycles are occurring, updating a dummy memory location based on the execution of instructions. 
     
     
         43 . A method of concealing data processing occurring in a CPU from power analysis during the execution of a program, the method comprising:
 (i) at a point during the execution of the program, inserting a random number of program counter cycles instruction fetch cycles; and   (ii) while the random number of instruction fetch cycles are occurring, mimicking power consumption associated with (a) fetching instructions from memory, (b) executing those instructions in program sequence, and (c) writing results to memory registers.   
     
     
         44 . A data processor comprising:
 an arithmetic logic unit;   a control flag register;   a plurality of registers for normally receiving output of the arithmetic logic unit in response to an arithmetic instruction and in response to a first state of said control flag register; and   a dummy register for receiving output of the arithmetic logic unit, in lieu of one of the plurality of registers, in response to an instruction and in response to a second state of said control flag register.   
     
     
         45 . The data processor of  claim 44  further comprising:
 a first program counter; 
 a second program counter; 
 the first and second program counters being responsive to the state of said control flag register so that the first program counter is enabled when said control flag register is in said first state and so that the second program counter is enabled when said control flag register is in said second state; and 
 wherein an enabled one of said first and second program counters fetches instructions from an instruction memory. 
 
     
     
         46 . The data processor of  claim 45  wherein the arithmetic logic unit outputs the results of an arithmetic instruction fetched by the first program counter to one of said plurality of registers and the arithmetic logic unit outputs the results of an arithmetic instruction fetched by the second program counter to said dummy register. 
     
     
         47 . The data processor of  claim 46  wherein the dummy register has no output for transferring data to the arithmetic logic unit. 
     
     
         48 . The data processor of  claim 47  wherein the registers and the dummy register each have an associated logic gate for controlling the transfer of data to the registers and to the dummy register, the associated logic gates being controlled by the state of said control flag register. 
     
     
         49 . The data processor of  claim 44  wherein the dummy register has no output for transferring data to the arithmetic logic unit. 
     
     
         50 . The data processor of  claim 44  wherein the registers and the dummy register each have an associated logic gate for controlling the transfer of data to the registers and to the dummy register, the associated logic gates being controlled by the state of said control flag register. 
     
     
         51 . A cryptographic bus architecture comprising:
 a random number generator having a plurality of random number outputs at which a multi-bit random number is output;   a plurality of bi-directional bus drivers, each bi-directional bus driver having at least one input for receiving at least one of said random number outputs; and   a bus coupling at least one of said plurality of bi-directional bus drivers to at least another of said bi-directional bus drivers;   Wherein di-directional bus drivers that are coupled to a common line of said bus are controlled by a common selected one of said random number outputs.   
     
     
         52 . The cryptographic bus architecture as claimed in  claim 51  wherein said plurality of random number outputs is camouflaged. 
     
     
         53 . The cryptographic bus architecture as claimed in  claim 51  wherein at least one of said plurality of bi-directional bus drivers comprises a normally inverting tri-state buffer and at least another one of said plurality of bi-directional bus drivers comprises a normally non-inverting tri-state buffer. 
     
     
         54 . The cryptographic bus architecture as claimed in  claim 51  further comprising a set of dual rails coupled to said plurality of bi-directional bus drivers, the set of dual rails coupling said bus to a CPU or to memory. 
     
     
         55 . The cryptographic bus architecture as claimed in  claim 51  wherein the random number generator is responsive to a control signal for causing said random number generator to emit a new random number. 
     
     
         56 . The cryptographic bus architecture as claimed in  claim 55  wherein the control signal is generated by a processor. 
     
     
         57 . The cryptographic bus architecture as claimed in  claim 56  wherein the control signal is generated by said processor in response to a software instruction. 
     
     
         58 . A method of preventing a breach of security comprising the steps of:
 sending encrypted bits over a bus; and   randomly toggling the polarity of said encrypted bits on said bus.   
     
     
         59 . The method as claimed in  claim 58  wherein said bus has dual rails for each bit transmitted in a parallel manner on said bus, one rail of said dual rails being invented compared to the other rail of said dual rails. 
     
     
         60 . A method of preventing a breach of security comprising sending encrypted bits over a bus having dual rails for each bit transmitted in a parallel manner on said bus, one rail of said dual rails being invented compared to the other rail of said dual rails. 
     
     
         61 . A method for protecting secret keys comprising:
 providing a plurality of bi-directional bus drivers;   coupling a line of a data bus between at least a first bi-directional bus driver of said plurality of bi-directional bus drivers and a second bi-directional bus driver of said plurality of bi-directional bus drivers;   signaling said first bi-directional bus driver to provide a first set of bits to said bus, said bits having a first polarity;   signaling said second bi-directional bus driver to receive said first set of bits having said first polarity;   randomly signaling said first bi-directional bus driven to provide a second set of bits to said bus, said second set of bits'having an opposite polarity than said first set of bits; and   signaling said second bi-directional bus driver to receive said second set of bits having said opposite polarity.   
     
     
         62 . The method as claimed in  claim 61  further comprising the step of camouflaging said signaling of said first and second bi-directional bus drivers. 
     
     
         63 . The method as claimed in  claim 61  further including:
 coupling a second line of said data bus between at least a third bi-directional bus driver of said plurality of bi-directional bus drivers and a forth bi-directional bus driver of said plurality of bi-directional bus drivers; 
 signaling said third bi-directional bus driver to provide a third set of bits to said bus, said bits having a first polarity, 
 signaling said forth bi-directional bus driver to receive said third set of bits having said first polarity; 
 randomly signaling said third bi-directional bus driver to provide a forth set of bits to said bus, said forth set of bits having an opposite polarity than said second set of bits; and 
 signaling said forth bi-directional bus driver to receive said forth set of bits having said opposite polarity. 
 
     
     
         64 . A method for preventing information leakage attacks comprising the steps of:
 randomly inverting a polarity of at least one of a plurality of signals on a first end of a bus; and   signaling to a second end of said bus that said random inverting has occurred at said first end of said bus.   
     
     
         65 . A cryptographic bus architecture comprising:
 a random number generator for generating a multi-bit random number;   first and second pluralities of bi-directional bus drivers, each bi-directional bus driver having a control input responsive to a selected bit of said random number; and   a bus coupling said first plurality of bi-directional bus drivers to said second plurality of bi-directional bus drivers, each of said bi-directional bus drivers being associated with a single line of said bus and wherein the bi-directional bus drivers coupled to a common line of said bus are responsive to a common bit of random number.   
     
     
         66 . The cryptographic bus architecture as claimed in  claim 65  wherein said random number generator has a plurality of camouflaged random number output ports. 
     
     
         67 . The cryptographic bus architecture as claimed in  claim 65  wherein said bi-directional bus drivers comprise an inverting tri-state buffer or a non-inverting tri-state buffer as determined by a state of data at its control input. 
     
     
         68 . The cryptographic bus architecture as claimed in  claim 65  further comprising a first and second sets of dual rails coupled to said first and second pluralities of bi-directional bus drivers, the first and second sets of dual rails coupling said bus to a CPU and to memory.