Cryptographic computation using masking to prevent differential power analysis and other attacks

• US 7,668,310 B2
• Filed: 08/15/2001
• Issued: 02/23/2010
• Est. Priority Date: 06/03/1998
• Status: Expired due to Fees

• Current Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Inventors: Jun, Benjamin C., Kocher, Paul C., Jaffe, Joshua M.
• Primary Examiner(s): Dinh; Minh
• Application Number:
  US09/930,836
• Publication Number:
  US 20010053220A1
• Time in Patent Office: 3,114 Days
• Field of Search: 380/1, 380/28, 380/37, 380/42, 380/44, 380/46, 713/340
• 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 cryptographic operation with resistance to external monitoring attacks, where said cryptographic operation includes performing a substitution operation using a predefined substitution table, said method comprising:

(a) obtaining a representation of a predefined substitution table specifying a corresponding table value for each of a plurality of possible table index values;

(b) using random information, transforming said representation of said predefined substitution table into a new randomized representation of said substitution table;

(c) receiving a datum to be cryptographically processed;

(d) computing a blinded representation of a table index value from at least said datum;

(e) using said new randomized representation of said table, performing a substitution on said blinded table index value to derive a blinded representation of the table value corresponding to an unblinded version of said table index value in step (d); and

(f) using said blinded table value to compute a cryptographic result for use in securing a cryptographic protocol.

2. The method of claim 1, where said step (d) includes the substeps of:

(i) obtaining an input masking parameter; and

(ii) deriving said blinded table index value from at least said input masking parameter and said received datum.

3. The method of claim 2, where said blinded representation of said table value constitutes said unblinded version of said table value in step (e), exolusive-ORed with an output masking parameter whose value depends on said random information.

4. The method of claim 1, where said transforming in step (b) includes permuting a plurality of entries in said predefined substitution table.

5. The method of claim 1, where said transforming in step (b) includes computing at least one value in said randomized representation of said substitution table by exclusive-ORing at least one masking value with at least one value of said predetermined substitution table.

6. The method of claim 1, where said transforming in step (b) includes representing said predefined substitution table as a plurality of tables.

7. A method for performing a cryptographic operation involving a substitution operation using a predefined substitution table, comprising:

(a) obtaining random information;

(b) using said random information, producing a randomized representation of said table;

(c) receiving a datum to be cryptographically processed;

(d) applying said randomized representation of said table to a table input derived from at least said datum to produce a substitution result randomized by said random information;

(e) using said randomized substitution result, deriving a cryptographic result, where said cryptographic result is independent of said random information; and

(f) using said cryptographic result as part of securing a cryptographic protocol.

8. A device for performing a cryptographic operation, where said cryptographic operation involves a key and an input message and includes a substitution operation with a predefined substitution table, comprising:

(a) a source of random data;

(b) table randomization logic configured to use an output from said source of random data;

(c) a memory for storing a randomized representation of a predefined substitution table;

(d) table input parameter computation logic, configured to produce a table input parameter from at least a portion of an input message and said output from said source of random data;

(e) first cryptographic computation logic configured to perform substitution operations on said table input parameter using said randomized representation of said predefined substitution table in said memory;

(f) second cryptographic logic, configured to use said first cryptographic computation logic to compute a cryptographic result, where said cryptographic result depends solely on said key and said input message and is independent of said output from said source of random data.

9. The device of claim 8 where said source of random data is a pseudorandom number generator.

10. The device of claim 8 where said source of random data includes a source of truly random values.