Using unpredictable information to minimize leakage from smartcards and other cryptosystems

• US 6,327,661 B1
• Filed: 06/03/1999
• Issued: 12/04/2001
• 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): Hayes, Gail
• Assistant Examiner(s): DARROW, JUSTIN T
• Application Number:
  US09/326,222
• Time in Patent Office: 915 Days
• Field of Search: 713/172, 713/174, 713/193, 713/194, 713/300, 713/320, 713/322, 713/323, 713/324, 713/340, 713/500, 713/501, 713/502, 713/600, 713/601, 380/1, 380/28, 380/29, 380/42, 380/43, 380/46, 380/47, 380/48, 380/262, 380/263, 380/268
• US Class Current: 713/193
• 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: G06K 19/073 Special arrangements for circuits, e.g. for protecting identification code in memory protection against unauthorised use of computer memory G06F12/14
• CPC Class Codes: G06K 19/07363 by preventing analysis of the circuit, e.g. dynamic or static power analysis or current analysis
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G07F 7/082 Features insuring the integrity of the data on or in the card
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04K 3/825 by jamming
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• 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/004 for fault attacks
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI

Abstract

Methods and apparatuses are disclosed for securing cryptosystems against external monitoring attacks by reducing the amount (and signal to noise ratio) of useful information leaked during processing. This is generally accomplished by incorporating unpredictable information into the cryptographic processing. Various embodiments of the invention use techniques such as reduction of signal to noise ratios, random noise generation, clock skipping, and introducing entropy into the order of processing operations or the execution path. The techniques may be implemented in hardware or software, may use a combination of digital and analog techniques, and may be deployed in a variety of cryptographic devices.

Claims

1. A cryptographic processing device for securely performing a cryptographic processing operation including a sequence of instructions in a manner resistant to discovery of a secret by external monitoring, comprising:

(a) an input interface for receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) a source of unpredictable information;

(c) a processor;

(i) connected to said input interface for receiving and cryptographically processing said quantity,

(ii) configured to use said unpredictable information to conceal a correlation between externally monitorable signals and said secret during said processing of said quantity by modifying said sequence; and

(d) an output interface for outputting said cryptographically processed quantity to a recipient thereof.

2. The device of claim 1 wherein said input interface and said output interface are the same element.

3. The device of claim 1 wherein said processor is configured to use said unpredictable information in a manner such that said cryptographically processed quantity is independent of said unpredictable information.

4. The device of claim 1 wherein said cryptographic processing operation includes transforming a message with the Data Encryption Standard (DES).

22. A device according to claims 1, 4, 7, 9, 11, 14, 15, or 20 wherein said device comprises a smartcard.

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

(a) an input interface for receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) a source of unpredictable information;

(c) a processor;

(i) connected to said input interface for receiving and cryptographically processing said quantity,

(ii) configured to use said unpredictable information to conceal a correlation between externally monitorable signals and said secret during said processing of said quantity by randomizing the order of said permutation; and

(d) an output interface for outputting said cryptographically processed quantity to a recipient thereof.

6. A cryptographic processing device implemented on a single microchip for securely performing a cryptographic processing operation in a manner resistant to discovery of a secret by external monitoring, comprising:

(a) an input interface for receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) a source of unpredictable information;

(c) a processor;

(i) connected to said input interface for receiving and cryptographically processing said quantity,

(ii) configured to use said unpredictable information to conceal a correlation between said microchip'"'"'s power consumption and said processing of said quantity by expending additional electricity in said microchip during said processing; and

(d) an output interface for outputting said cryptographically processed quantity to a recipient thereof.

7. The device of claim 6 including program logic to activate said expending during said processing.

8. The device of claim 7 including

(a) program logic implementing said source of unpredictable information; and

(b) program logic to transmit said unpredictable information to an additional power expending circuit contained in said microchip.

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

(a) an input interface for receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) a source of unpredictable information;

(c) a processor;

(i) connected to said input interface for receiving and cryptographically processing said quantity,

(ii) configured to use said unpredictable information to conceal a correlation between externally monitorable signals and said secret during said processing of said quantity;

(d) an output interface for outputting said cryptographically processed quantity to a recipient thereof;

(e) a hardware-implemented noise production subunit connected to said source of unpredictable information and configured to expend unpredictable amounts of electricity based on the output of said source of unpredictable information; and

(f) an activation controller, which may be activated by software contained in said device, to activate and deactivate said expending of unpredictable amounts of electricity.

10. The device of claim 9 wherein said source of unpredictable information is a hardware-implemented random number generator, and wherein said noise production subunit includes a digital-to-analog converter.

11. A cryptographic processing device for securely performing a cryptographic processing operation in a manner resistant to discovery of a secret by external measurement of said device'"'"'s power consumption, comprising:

(a) an input interface for receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) an input interface for receiving a variable amount of power, said power consumption varying measurably during said performance of said operation;

(c) a processor connected to said input interface for receiving and cryptographically processing said quantity; and

(d) a noise production system for introducing noise into said measurement of said power consumption.

12. The device of claim 11 wherein said noise production system comprises:

(a) a source of randomness for generating initial noise having a random characteristic;

(b) a noise processing module for improving the random characteristic of said initial noise; and

(c) a noise production module configured to vary said power consumption based on an output of said noise processing module.

13. The device of claim 12 wherein said noise production system is connected to said processor and is selectively operable under the control of said processor.

14. A cryptographic processing device for securely performing a cryptographic processing operation in a manner resistant to discovery of a secret by external monitoring of said device'"'"'s power consumption, comprising:

(a) an input/output interface for receiving data to be cryptographically processed, said data being representative of at least a portion of a message;

(b) an oscillator generating a first clock signal;

(c) an input interface for receiving a variable amount of power, said power consumption varying measurably during said performance of said operation;

(d) a source of unpredictable information;

(e) a clock decorrelator coupled to said source of unpredictable information for generating a second clock signal from said first clock signal using said unpredictable information, such that said second clock signal cannot be reliably predicted from said first clock signal; and

(f) a processor;

(i) clocked by said second clock signal,

(ii) configured to cryptographically processing said data, and

(iii) configured to output said cryptographically processed data using said input/output interface.

15. A cryptographic processing device for securely performing a cryptographic processing operation in a manner resistant to discovery of a secret by external monitoring of said device'"'"'s power consumption, comprising:

(a) an input/output interface for receiving data to be cryptographically processed, said data being representative of at least a portion of a message;

(b) an input interface for receiving an external clock signal;

(c) an input interface for receiving a variable amount of power, said power consumption varying measurably during said performance of said operation;

(d) a source of unpredictable information;

(e) a clock decorrelator coupled to said source of unpredictable information for generating an internal clock signal from said external clock signal using said unpredictable information, such that said internal clock signal cannot be reliably predicted from said external clock signal; and

(f) a processor;

(i) clocked by said internal clock signal,

(ii) configured to cryptographically processing said data, and

(iii) configured to output said cryptographically processed data using said input/output interface.

16. The device of claim 15 wherein said clock decorrelator comprises a clock skipping module which selects a subset of the cycles of said external clock signal to use as said internal clock signal based on said unpredictable information.

17. The device of claim 15 wherein said source of unpredictable information comprises a hardware random number generator.

18. The device of claim 15 further comprising a monitor for detecting a clock fault in said external clock signal and preventing said processor from processing said quantity if said clock fault is detected.

19. The device of claim 15 wherein said clock decorrelator is selectively operable under the control of said processor.

20. The device of claim 15 wherein said clock decorrelator is selectively operable such that said clock decorrelator is disabled when data is being transferred across said input/output interface and enabled during said cryptographic processing operation.

21. The device of claim 15 further comprising a noise production system connected to said processor for introducing noise into said measurement of the power consumption by consuming a random amount of power during said cryptographic prosing operation.

23. A method of securely performing a cryptographic processing operation in a manner resistant to discovery of a secret within a cryptographic processing device by external monitoring, comprising:

(a) receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) generating unpredictable information;

(c) cryptographically processing said quantity, including using said unpredictable information while processing said quantity to conceal a correlation between externally monitorable signals and said secret by selecting between;

(c)(1) performing a computation and incorporating the result of said computation in said cryptographic processing, and

(c)(2) performing a computation whose output is not incorporated in said cryptographic processing; and

(d) outputting said cryptographically processed quantity to a recipient thereof.

24. The method of claim 23 where said selecting is performed in software.

25. The method of claim 23 where said selecting is performed in hardware on an integrated circuit including a microprocessor.

26. A method of securely performing a cryptographic processing operation in a manner resistant to discovery of a secret within a cryptographic processing device by external monitoring, comprising:

(a) receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) generating unpredictable information;

(c) cryptographically processing said quantity, including using said unpredictable information while processing said quantity to conceal a correlation between externally monitorable signals and said secret by selecting a code process from a plurality of code processes, where said selected code process is involved in said cryptographic processing, but where the value of said outputted quantity is independent of which of said code processes was selected; and

(d) outputting said cryptographically processed quantity to a recipient thereof.

27. A method of securely performing a cryptographic processing operation including a sequence of instructions in a manner resistant to discovery of a secret within a cryptographic processing device by external monitoring, comprising:

(a) receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) generating unpredictable information;

(c) using said unpredictable information while processing said quantity to conceal a correlation between externally monitorable signals and said secret by using said unpredictable information to modify said sequence; and

(d) outputting said cryptographically processed quantity to a recipient thereof.

28. A method of securely performing a cryptographic processing operation implementing a permutation in a manner resistant to discovery of a secret within a cryptographic processing device by external monitoring, comprising:

(a) receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(b) generating unpredictable information;

(c) using said unpredictable information while processing said quantity to conceal a correlation between externally monitorable signals and said secret by randomizing the order of said permutation; and

(d) outputting said cryptographically processed quantity to a recipient thereof.

29. A method of securely performing a cryptographic processing operation in a manner resistant to discovery of a secret within a cryptographic processing device by external monitoring of said device'"'"'s power consumption, comprising:

(a) receiving a variable amount of power, said power consumption varying measurably during said performance of said operation;

(b) receiving a quantity to be cryptographically processed, said quantity being representative of at least a portion of a message;

(c) introducing noise into said measurement of said power consumption while processing said quantity; and

(d) outputting said cryptographically processed quantity to a recipient thereof.

30. The method of claim 29 wherein said step of introducing noise comprises:

(a) generating initial noise having a random characteristic;

(b) improving the random characteristic of said initial noise; and

(c) varying said power consumption based on said improved initial noise.

31. A method of securely performing a cryptographic processing operation in a manner resistant to discovery of a secret within a cryptographic processing device by external monitoring of said device'"'"'s power consumption, comprising:

(a) receiving a variable amount of power, said power consumption varying measurably during said performance of said operation;

(b) generating a first clock signal;

(c) receiving data to be cryptographically processed, said data being representative of at least a portion of a message;

(d) generating unpredictable information;

(e) generating a second clock signal from said first clock signal using said unpredictable information, such that said second clock signal cannot be reliably predicted from said first clock signal;

(f) processing said data using said second clock signal; and

(g) outputting said cryptographically processed quantity to a recipient thereof.

32. A method of securely performing a cryptographic processing operation in a manner resistant to discovery of a secret within a cryptographic processing device by external monitoring of said device'"'"'s power consumption, comprising:

(a) receiving a variable amount of power, said power consumption varying measurably during said performance of said operation;

(b) receiving an external clock signal;

(c) receiving data to be cryptographically processed, said data being representative of at least a portion of a message;

(d) generating unpredictable information;

(e) generating an internal clock signal from said external clock signal using said unpredictable information, such that said external clock signal cannot be reliably predicted from said internal clock signal;

(f) processing said data using said internal clock signal; and

(g) outputting said cryptographically processed quantity to a recipient thereof.

33. The method of claim 32 wherein said step of generating said internal clock signal comprises a step of selecting a subset of the cycles of said external clock signal to use as said internal clock signal based on said unpredictable information.

34. The method of claim 32 wherein said step of generating unpredictable information comprises a step of generating a random number.

35. The method of claim 32 further comprising a step of monitoring for a clock fault in said external clock signal and a step of preventing said processor from outputting said cryptographically processed quantity if said clock fault is detected.

36. The method of claim 32 further comprising a step of introducing noise into said measurement of the power consumption.