Prevention of side channel attacks against block cipher implementations and other cryptographic systems

• US 20060045264A1
• Filed: 10/18/2005
• Published: 03/02/2006
• Est. Priority Date: 06/03/1998
• Status: Active Grant

• Current Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Inventors: Kocher, Paul C., Jun, Benjamin C., Jaffe, Joshua M.
• Granted Patent: US 7,787,620 B2
• Time in Patent Office: Days
• US Class Current: 380/37
• CPC Class Codes: G06F 21/556 involving covert channels, i.e. data leakage between processes inhibiting the analysis of circuitry or operation with measures against power attack G06F21/755
• 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/046 of operations, operands or results of the operations
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/127 Trusted platform modules [TPM]
• 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/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 improving DES and other cryptographic protocols against external monitoring attacks by reducing the amount (and signal-to-noise ratio) of useful information leaked during processing. An improved DES implementation of the invention instead uses two 56-bit keys (K1 and K2) and two 64-bit plaintext messages (M1 and M2), each associated with a permutation (i.e., K1P, K2P and M1P, M2P) such that K1P{K1} XOR K2P{K2} equals the “standard” DES key K, and M1P{M1} XOR M2P{M2} equals the “standard” message. During operation of the device, the tables are preferably periodically updated, by introducing fresh entropy into the tables faster than information leaks out, so that attackers will not be able to obtain the table contents by analysis of measurements. The technique is implementable in cryptographic smartcards, tamper resistant chips, and secure processing systems of all kinds.

Claims

1. A method for performing a symmetric block cipher operation on a message block, using a tamper resistant device, comprising:

(a) receiving an input message;

(b) obtaining unpredictable information;

(c) producing at least one masked intermediate parameter and a corresponding blinding parameter from at least said input message and said unpredictable information, such that;

(i) the value of said masked intermediate parameter is unpredictable to an attacker;

(ii) the value of said blinding parameter is unpredictable to an attacker;

(iii) the value of an intermediate value in said block cipher operation is represented by a mathematical relationship between said masked intermediate parameter and said blinding parameter;

(d) performing a plurality of rounds of said block cipher operation, where each said round includes changing said value for at least one of said parameters; and

(e) producing an output message from at least said masked intermediate parameter and said blinding parameter after said round operations in step (d).

2. The method of claim 1 where said block cipher operation is compatible with the Advanced Encryption Standard.

3. The method of claim 1 where said block cipher operation is compatible with the Data Encryption Standard.

4. The method of claim 1 where said intermediate value is predictable to an attacker.

5. The method of claim 1 further comprising:

(x) obtaining additional unpredictable information; and

(y) using said additional unpredictable information, processing said masked intermediate parameter and said blinding parameter to obtain a new value for said masked intermediate parameter and a new value for said blinding parameter.

6. The method of claim 5, where:

(i) a first intermediate value corresponds to a mathematical relationship between the masked intermediate parameter and blinding factor; and

(ii) a second intermediate value corresponds to said mathematical relationship between said new value for said masked intermediate parameter and said new value for said blinding factor.

7. The method of claim 6, where said second intermediate value is equal to said first intermediate value.

8. A tamper resistant device containing means for performing a symmetric block cipher operation on a message block, comprising:

(a) means for receiving an input message;

(b) a source of unpredictable information;

(c) means for producing at least one masked intermediate parameter and a corresponding blinding parameter from at least an input message and unpredictable information, such that;

(i) the value of said masked intermediate parameter is unpredictable to an attacker;

(ii) the value of said blinding parameter is unpredictable to an attacker;

(iii) the value of an intermediate value in said block cipher operation is represented by a mathematical relationship between said masked intermediate parameter and said blinding parameter;

(d) means for performing a round of said block cipher operation, including changing said value for at least one of said parameters; and

(e) means for producing an output message, from at least said masked intermediate parameter and said blinding parameter, incorporating the result of said round in (d).