Balanced cryptographic computational method and apparatus for leak minimizational in smartcards and other cryptosystems

• US 6,510,518 B1
• Filed: 06/03/1999
• Issued: 01/21/2003
• Est. Priority Date: 06/03/1998
• Status: Expired due to Term

• Current Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Inventors: Kocher, Paul C., Jun, Benjamin C., Jaffe, Joshua M.
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/325,611
• Time in Patent Office: 1,328 Days
• Field of Search: 713/168, 713/171, 713/200, 713/201, 713/152
• US Class Current: 713/168
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/755 with measures against power attack
• CPC Class Codes: G06F 2207/7219 Countermeasures against side channel or fault attacks
• CPC Class Codes: H04L 2209/122 Hardware reduction or efficient architectures
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation

Abstract

Cryptographic devices that leak information about their secrets through externally monitorable characteristics (such as electromagnetic radiation and power consumption) may be vulnerable to attack, and previously-known methods that could address such leaking are inappropriate for smartcards and many other cryptographic applications. Methods and apparatuses are disclosed for performing computations in which the representation of data, the number of system state transitions at each computational step, and the Hamming weights of all operands are independent of computation inputs, intermediate values, or results. Exemplary embodiments implemented using conventional (leaky) hardware elements (such as electronic components, logic gates, etc.) as well as software executing on conventional (leaky) microprocessors are described. Smartcards and other tamper-resistant devices of the invention provide greatly improved resistance to cryptographic attacks involving external monitoring.

Claims

1. A method for using a secret key to cryptographically process a message, comprising:

(a) receiving a message to be cryptographically processed;

(b) in a hardware device, cryptographically processing said message by performing a plurality of cryptographic suboperations thereon, each said suboperation;

(i) taking an input, via at least one intermediate, to an output,

(ii) including a number of computational state transformations, said number being independent of said message and of said key, and

(iii) characterized such that the Hamming weights of said message, said intermediate, and said output are independent of said message and of said key; and

(c) outputting said cryptographically processed message;

whereby external monitoring of said hardware device does not reveal useful information about said secret key.

33. The method of claim 1, 2, 3, 4, 5, 7, 8, 9, 10, 16, 17, 18, 19, 20, 21, 22, 23, 31, or 32 implemented in an ISO 7816-compliant smart card.

2. A method for performing a balanced cryptographic operation on input data, comprising:

(a) representing said input data using a constant Hamming weight representation; and

(b) using a secret key, manipulating said input data to produce output data by performing a balanced cryptographic operation thereon;

thereby cryptographically processing said input data in a manner resistant to detection of said secret key by external monitoring of a hardware device performing said cryptographic operation.

3. The method of claim 2 wherein step (a) includes converting said input data from a non-constant Hamming weight representation, said method further comprising converting said output data to said non-constant Hamming weight representation.

4. The method of claim 2 wherein the number of state transitions performed during step (b) is balanced so as to be uncorrelated to the value of said secret key.

5. A method for performing a balanced cryptographic operation on input data, comprising:

(a) representing said input data using a first constant Hamming weight representation;

(b) manipulating said input data to produce intermediate data in said first constant Hamming weight representation;

(c) converting said intermediate data from said first constant Hamming weight representation to a second constant Hamming weight representation; and

(d) manipulating said intermediate data to produce output data according to said cryptographic operation;

thereby cryptographically processing said input data in a manner resistant to detection of said secret key by external monitoring of a hardware device performing said cryptographic operation.

6. A balanced cryptographic processing device comprising:

(a) a secret key;

(b) an input interface for receiving data;

(c) a conversion unit to convert said data into a constant Hamming weight representation; and

(d) a processor configured to perform a cryptographic operation on said data by using said secret key while preserving said constant Hamming weight representation.

7. A method for performing a balanced cryptographic operation using secret data, comprising:

(a) performing a plurality of suboperations using said secret data and an operand; and

(b) for each of said plurality of suboperations, simultaneously performing corresponding suboperations using

(i) said operand and the complement of said secret data,

(ii) said secret data and the complement of said operand, and

(iii) the complement of said secret data and the complement of said operand;

thereby cryptographically processing said operand and said secret data in a manner resistant to detection of said secret data by external monitoring of a hardware device performing said cryptographic operation.

8. A method for performing a balanced computational process comprising:

(a) receiving a first and a second input variable, each input variable having N bits;

(b) creating a value of a first intermediate variable having 2N bits, each of a first half of said 2N bits being equal to a corresponding bit of said first input variable, each of a second half of said 2N bits being equal to the complement of a corresponding bit of said first input variable;

(c) creating a value of a second intermediate variable having 2N bits, each of a first half of said 2N bits corresponding to a bit of said second input variable, each of a second half of said 2N bits being equal to a corresponding bit of said first half of said 2N bits;

(d) creating a value of a third intermediate having 2N bits, each bit being the result of a bitwise logical operation on a corresponding bit of said first intermediate variable and a corresponding bit of said second intermediate variable; and

(e) extracting a result of said computational process from said third intermediate variable;

thereby cryptographically processing said input variables in a manner resistant to detection by external monitoring of a hardware device performing said computational process.

9. The method of claim 8 wherein said first and second input variables are represented in a constant Hamming code representation, wherein said method further comprises transforming said third intermediate variable such that said result is represented in said constant Hamming code representation.

10. The method of claim 9 wherein said step of transforming includes a constant number of state transitions.

11. A balanced cryptographic processing device comprising:

(a) an input interface for receiving a first and a second input variable to be used as inputs to a computation, each input variable represented by at least a first bit and a second bit, where said representation has a constant Hamming weight;

(b) a first computational unit for performing a bitwise logical operation on said first bit of said first input variable and said first bit of said second input variable;

(c) a second computational unit for performing said bitwise logical operation on said first bit of said first input variable and said second bit of said second input variable;

(d) a third computational unit for performing said bitwise logical operation on said second bit of said first input variable and said first bit of said second input variable; and

(e) a fourth computational unit for performing said bitwise logical operation on said second bit of said first input variable and said second bit of said second input variable;

thereby cryptographically processing said input variables in a manner resistant to detection by external monitoring of a hardware device performing said operations.

12. The device of claim 11 further comprising a first load including an output interface for outputting an output of said computation, said output interface connected to an output of said first computational unit.

13. The device of claim 12 further comprising a second load connected to an output of said second computational unit, a third load connected to an output of said third computational unit, and a fourth load connected to an output of said fourth computational unit, each of said second, third, and fourth loads having an impedance matched to the impedance of said first load.

14. The device of claim 13 wherein said first, second, third, and fourth computational units have identical design parameters.

34. The device of claim 6, 11, or 13 where said device comprises an ISO 7816-compliant smart card.

15. An electronic circuit configured to perform a computation on input data represented in a balanced Hamming weight format, said computation comprising:

(a) receiving said input data through an input interface;

(b) producing from said input data an intermediate variable represented in said balanced Hamming weight format;

(c) deriving a result from said intermediate variable; and

(d) transmitting at least a portion of said result to a receiving circuit.

16. A method for reducing the amount of information available for detection through monitoring of the power consumption of a device during a digital cryptographic computation comprising:

(a) receiving input data represented by a plurality of sets of data bits in a representation format wherein;

(i) each data bit can have one of two values,

(ii) each set of data bits includes at least two data bits;

(iii) the value of each set of data bits can be encoded as at least two functionally-equivalent combinations of values of said data bits;

(b) processing said input data through a series of substeps, wherein

(i) said substeps combine said input data to compute intermediate data represented in said format, and

(ii) by balancing at least one characteristic of said computation, the amount of power consumed at each substep is made not detectably correlated to the value of said intermediate data; and

(c) producing an output result from said intermediate data.

17. The method of claim 16 wherein a plurality of said processing substeps include transforming said intermediate data from a first representation to a second representation, said first and second representation being functionally equivalent.

18. The method of claim 16 wherein the at least one characteristic balanced in step (b)(ii) includes the total Hamming weight of the representation of said intermediate data.

19. The method of claim 16 wherein the at least one characteristic balanced in step (b)(ii) includes the number of state transitions that occur during at least one of said substeps that are a function of the representation of said intermediate data.

20. The method of claim 16 wherein a plurality of said substeps of step(b) include computing a representation of said intermediate data from the XOR of two data bits of said input data.

21. The method of claim 16 wherein said computation is performed using a circuit of hard-wired transistors.

22. The method of claim 16 wherein said computation is implemented in microcode.

23. The method of claim 16 wherein said computation is implemented in software as part of a cryptographic process using a secret key.

24. The method of claim 23 wherein said cryptographic algorithm is a symmetric block cipher.

25. A method for converting a definition of a computational device capable of performing cryptographic operations using a secret key into a definition of a digital circuit, comprising:

(a) receiving a machine-readable definition of said computational device;

(b) using a processor to compile at least a portion of a process for said operation by (i) converting said process into a sequence including a plurality of logic operations, and (ii) converting said plurality of logic operations into a plurality of operations for which the power consumption is balanced;

(c) writing an output file representing said plurality of balanced logic operations; and

(d) transmitting said output file to a third party for fabrication into said digital circuit.

26. The method of claim 25 wherein each of a first plurality of bits represented in said machine-readable definition is represented in said output file by a second plurality of bits, wherein the Hamming weight of said second plurality of bits is independent of the individual values of said bits.

27. The method of claim 25 wherein said cryptographic operation comprises a block cipher, and said digital circuit is balanced to reduce a correlation between power consumption and a cryptographic processing intermediate variable.

28. The method of claim 25 wherein said digital circuit includes a multiplier.

29. A method for converting a definition of a computational process into a definition of software whose power consumption is balanced, comprising the steps of:

(a) receiving a machine-readable definition of said computational process;

(b) using a processor to compile at least a portion of said process by (i) converting said process into a sequence of operations including a plurality of logic operations, and (ii) converting said plurality of logic operations into a plurality of operations for which the power consumption is balanced; and

(c) writing an output file representing said plurality of balanced logic operations expressed as a sequence of executable instructions.

30. The method of claim 29 wherein said computational process comprises a block cipher.

31. A cryptographic processing device for securely performing a cryptographic processing operation in a manner resistant to the discovery of a secret by external monitoring, comprising:

(a) an input interface for receiving a quantity to be cryptographically processed and for converting said quantity into an expanded balanced representation; and

(b) a processing circuit operatively connected to said input interface and including;

(i) a plurality of main logic subunits configured to in compute the result of said cryptographic processing operation; and

(ii) a plurality of additional logic subunits of composition similar to said main logic units which operate simultaneously with said main logic units to balance the power consumption of the computation performed by said main logic units; and

(c) an output interface operatively connected to said processing circuit for outputting said result of said cryptographic processing operation.

32. The method of claim 31 wherein said cryptographic processing operation comprises a block cipher.