Using unpredictable information to minimize leakage from...

Details Using unpredictable information to minimize leakage from... Using unpredictable information to minimize leakage from...

1999-06-03

2001-12-04

Hayes, Gail (Department: 2132)

Electrical computers and digital processing systems: support

Data processing protection using cryptography

By stored data protection

C713S322000, C713S323000, C713S501000, C380S028000, C380S046000, C380S047000

Reexamination Certificate

active

06327661

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to securing cryptographic systems against external attacks and, more specifically, to the minimization and masking of useful information available by external monitoring of cryptographic operations.
BACKGROUND OF THE INVENTION
As described in U.S. Pat. 4,908,038 to Matsumura et al., cryptographic devices can be attacked using information gathered by observing the timing of comparison operations performed by such devices during their operation. For example, if a MAC (Message Authentication Code) algorithm is strong and the key is secure, forging a MAC should require O(2{circumflex over ( )}n) attempts (where n is the MAC length in bits), but a device using a vulnerable MAC validation process is vulnerable to an O(n) timing attack.
If timing is the only source of leaked information, securing the device is often relatively straightforward. Previously known countermeasures to attacks involving information leaking from cryptosystems employ large and often expensive physical shielding and/or careful filtering of inputs and outputs (e.g., U.S. government Tempest specifications). Unfortunately, these techniques are difficult to apply in constrained engineering environments. For example, physical constraints (such as size and weight), cost, and the need to conserve power can often prevent the use of such techniques. It is also known to use certain computational techniques (e.g., see Matsumura, above, or P. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,”
Advances in Cryptology—CRYPTO '
96, Springer-Verlag, 1996, pages 104-113) to equalize timing. However, sources of information leakage other than timing (e.g., a device's power consumption) provide other avenues of attack. Indeed, Matsumara's timing equalization system itself can be vulnerable to non-timing attacks, for example by analyzing power consumption to detect the start of processing delays. It would therefore be advantageous to protect the devices' internal operations themselves instead of (or in addition to) simply externally masking the devices' timing (or other) fluctuations.
The present invention includes countermeasures that can be incorporated into software and/or hardware, to provide improved protection at relatively low cost. Thus, the invention could be used in place of (or in addition to) traditional countermeasures. For example, the present invention can be implemented in smartcards and other highly constrained environments where physical shielding and other protection measures cannot be readily applied.
SUMMARY OF THE INVENTION
The use of unpredictable information to minimize leakage from smartcards and other cryptosystems is disclosed.
According to one approach, the present invention provides techniques for modifying the computational processes in implementations of cryptographic algorithms to incorporate new random information, beyond the input parameters that are traditionally used, while still producing desired results. Definitions and standards for cryptographic algorithms require that implementations of such algorithms produce specific outputs from given inputs. For example, implementations of the Data Encryption Standard (DES) defined in National Bureau of Standards Federal Information Processing Standard Publication 46 (Jan. 1977) should encrypt the message 0011223344556677 with the key 0123456789ABCDEF (with standard odd DES key parity bits) to produce the ciphertext CADB6782EE2B4823. However, implementers of this and other algorithms can choose the particular processing steps used to transform the inputs into the outputs. Thus, by modifying the computational processes to incorporate new random information, secret information that might be sought by an attacker (such as the key or other secrets) can be concealed within or among random (or otherwise unpredictable) information incorporated into the cryptographic operations. Information leaked during the system's operation will then be correlated to the unpredictable state information (or noise), making leaked information less useful to attackers. Said another way, leaked information can be made effectively uncorrelated (or less correlated) to the device's secrets. Some particular embodiments of this general approach will be described below. One embodiment of the invention also provides for the added unpredictable information to be updated frequently to prevent attackers from using monitoring attacks to determine the state information itself.
An attacker's measurements of an operating device are often imperfect, and contain both information that is useful (“signal”) and information that hinders or is irrelevant to interpretation of the signal (“noise”). (In addition, there may be irrelevant components of the measurements, such as predictable information, that neither helps nor hinders attacks.) To increase the difficulty of attack, one embodiment of the present invention increases the amount of noise in attackers' measurements and/or increases the signal complexity.
Still other embodiments of the general technique include software- and hardware- implementable clock skipping (to prevent the temporal correlation of specific operations with clock transitions provided by or observable by attackers), symmetric permutation blinding, and the introduction of entropy into the order of cryptographic operations. Such techniques are usable to prevent attackers from correlating observations with specific events within the cryptosystem's operation.
All of the foregoing will be explained in greater detail with respect to the figures and detailed description of the invention, below.


REFERENCES:
patent: 4200770 (1980-04-01), Hellman et al.
patent: 4405829 (1983-09-01), Rivest et al.
patent: 4759063 (1988-07-01), Chaum
patent: 4905176 (1990-02-01), Schultz
patent: 4908038 (1990-03-01), Matsumura et al.
patent: 5401950 (1995-03-01), Yoshida
patent: 5404402 (1995-04-01), Sprunk
patent: 5539827 (1996-07-01), Liu
patent: 5664017 (1997-09-01), Gressel et al.
patent: 6041122 (2000-03-01), Graunke et al.
Kocher, P. “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS and Other Systems.” in: Koblitz, N.,Advances in Cryptology-CRYPTO '96(Berlin, Springer, 1996), pp. 104-113.
Bellare, M. et al., “Incremental Cryptography: The Case of Hashing and Signing” in: Desmedt, Y.,Advances in Cryptology—CRYPTO '94.
“Security Requirements for Cryptographic Modules,” Federal Information Processing Standards Publication (FIPS PUB) 140-1, U.S. Department of Commerce, National Institute of Standards and Technology, Jan. 1994.
RSA Data Security, RSAREF Cryptographic Toolkit Source Code, File R-RANDOM.C, available fronftp://ftp.rsa.com.
Krawczyk, H. et al., “HMAC: Keyed-Hashing for Message Authentication,” Network Working Group Request for Comments RFC 2104, Feb. 1997.
Ryan, J. “Blinds for Thermodynamic Cipher Attacks,” unpublished material on the world wide web at http://www.cybertrace.com/thrmatak.html Mar. 1996.
Menezes, A.J., et al.,Handbook of Applied Cryptography(CRC Press, 1996), pp. including 285-298, 312-319, 452-462, 475, 515-524.
“Data Encryption Standard,” Federal Information Processing Standards Publication (FIPS PUB) 46-2, U.S. Department of Commerce, National Institute of Standards and Technology, Dec. 30, 1993.
Biham, E. et al., “Differential Fault Analysis of Secret Key Cryptosystems” in: Kaliski, B.,Advances in Cryptology—CRYPTO 97, (Berlin, Springer, 1997) 17thAnnual International Cryptology Conference, Aug. 17-21, 1997, pp. 513-525.

Affiliated with

Also associated with

Rating

Using unpredictable information to minimize leakage from... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Using unpredictable information to minimize leakage from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using unpredictable information to minimize leakage from... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2601529