Electrical computers and digital processing systems: support – Data processing protection using cryptography – Tamper resistant
Reexamination Certificate
1999-06-03
2001-10-02
Hayes, Gail (Department: 2132)
Electrical computers and digital processing systems: support
Data processing protection using cryptography
Tamper resistant
C713S193000, C380S028000, C380S030000
Reexamination Certificate
active
06298442
ABSTRACT:
FIELD OF THE INVENTION
The method and apparatus of the invention relate generally to securing cryptographic systems against external attacks and, more specifically, to minimizing the information discoverable by external monitoring of a processor performing, cryptographic operations involving modular exponentiation.
BACKGROUND OF THE INVENTION
Most cryptosystems implementations include a combination of hardware and software. For example, cryptographic smartcards on the market today typically include a hardware microprocessor that executes programs stored in internal secure memory (which can be read-only or updateable). This or other memory is used to hold cryptographic keys, which are managed by these programs. Such keys are used in connection with various cryptographic operations including, without limitation, symmetric encryption using DES, triple DES, IDEA, SEAL, and RC4; public key (asymmetric) encryption and decryption using, RSA and ElGamal; digital signatures using, DSA, ElGamal, and RSA; and Diffic-Heilman key agreement protocols. The key-based operations are, in turn, used to securely process messages being handled by the cryptosystems.
For example, in asymmetric (i.e., public-key based) systems, private keys are used to perform digital signatures and decrypt received data. For example, in the RSA protocol, a private key includes a secret exponent, and a received message is cryptographically signed (or a received encrypted message is decrypted) by raising the message to the value of the secret exponent. These and many other details and aspects of private key operations are well known to those skilled in the art (see, e.g., such standard references as
Handbook of Applied Cryptography
by Menezes et al., CRC Press, 1997 and/or
Applied Cryptography
by Schneier, Wiley, 1996) and need not be described in detail here. Attackers who obtain the private key can use it to forge digital signatures, modify transmitted data, and intercept transmitted information. Therefore, the private key must be kept secret. Symmetric (e.g., DES) systems similarly contain cryptographic keys that must be kept secret. Therefore, well-designed cryptographic systems should prevent attackers who eavesdrop on communications from compromising key security. As a matter of convenience, the key to be protected—whether asymmetric or symmetric—will be referred to herein as a secret quantity.
In addition, many cryptographic systems require tamper-evident or tamper-resistant hardware, and other implementation-specific measures, to prevent attackers from accessing or finding the secret keys. Physical measures might include enclosing key management systems in physically durable enclosures, physical shielding (e.g., shielding according to U.S. Governnent Tempest specifications), physical isolation, wrapping devices with fine wires or membranes that detect tampering, and coating integrated circuits with special coatings that destroy the chip when removed. Such techniques are often expensive or physically cumbersome, and therefore inappropriate for many applications. They are also difficult to design/evaluate because, for example, there is no mathematical model for their security.
The foregoing techniques are also ineffective against certain types of attacks. For example, recent work by Cryptography Research, Inc. has shown that attackers can often non-invasively extract secret keys using external measurement and analysis of a device's power consumption, electromagnetic radiation, or processor cycle timing during performance of cryptographic operations. Known physical and electronic techniques used to deter external monitoring of cryptographic secrets include: a) equipping power supplies with large capacitors to mask fluctuations in power consumption; b) enclosing devices in well-shielded cases to prevent electromagnetic radiation; c) buffering inputs/outputs to prevent signals from leaking out on I/O lines; d) message blinding to prevent timing attacks; and e) using timing delays to equalize operation times. These known techniques can be helpful in deterring some types of external monitoring attacks, but are impractical and/or ineffective against other attacks. For example, timing equalization may deter timing attacks, but not power consumption attacks. Also, well shielded power supplies can deter power consumption attacks, but they cannot be used in small devices.
Furthermore, it is extremely difficult to make hardware key management systems that provide good security, particularly in low-cost, unshielded cryptographic devices for use in applications where attackers may gain physical control over the device. For example, cryptographic smartcards used in electronic cash and content distribution schemes must protect their keys in potentially hostile environments. Smartcards are examples of cryptographic tokens—devices that contain or manipulate cryptographic keys that need to be protected from attackers. Forms in which tokens may be manufactured include, without limitation, smartcards, specialized encryption and key management devices, secure telephones, secure picture phones, consumer electronics devices using cryptography, secure microprocessors, and other tamper-resistant cryptographic systems.
In such cryptographic tokens, many of the aforementioned techniques are ineffective or impractical. For example, physical measures that deter tampering by increasing the likelihood of detection (e.g., by authorized users or security personnel) are ineffective for cryptographic tokens when attackers gain physical control over the token (e.g., smartcards used in stored value schemes, satellite television descrambling schemes, etc.), because only the attacker would witness the evidence of tampering. Many physical measures (e.g., wire-wrapping) are impractical because their cost is prohibitive where cryptographic tokens must be produced at relatively low cost. Also, physical measures are often impractical for mobile (e.g., personal) cryptographic tokens due to reliance on external power sources, the physical impracticality of shielding, and other characteristics imposed by a token's physical (e.g., size or weight) constraints. Furthermore, it is often difficult to select/implement appropriate countermeasures at the design stage, before it is known what information will be available to an attacker—as is often the case before a device has been physically manufactured and characterized.
There is therefore a need for cryptographic security techniques that can be: a) characterized at the design level before a device is physically built; b) implemented where traditional physical techniques fail or need to be augmented (e.g., against power consumption and timing attacks); and/or c) implemented within the physical constraints of smartcards and other cryptographic tokens.
SUMMARY OF THE INVENTION
Many cryptographic operations involve asymmetric cryptographic protocols (e.g., RSA or Diffie-Hellman) that use of modular exponentiation including a private key having a secret exponent and a modulus. Thus, an attacker who determines the secret exponent generally breaks the scheme.
Modular exponentiation with a large exponent is conventionally performed as a series of squaring (multiplication by self) and multiplication (by other than self) operations. Which of these operations occurs at any particular time is controlled by a conditional jump (or branch) that depends on the value of the exponent (i.e., key) as it is traversed, commonly bit-by-bit. However, microcontrollers (or other forms of microprocessors) used in smartcards and other cryptographic devices can exhibit significant differences in power consumption, electromagnetic radiation, and/or timing between when a conditional jump in the execution path is taken and when it is not taken, thus making results of branching decisions often among the easiest information for attackers to identify. Such differences arise because the microcontroller execution sequence varies depending on the branch. For example, attackers can determine secret exponents (and therefore, private keys
Jaffe Joshua M.
Kocher Paul C.
Cryptography Research, Inc.
Darrow Justin T.
Hayes Gail
Lane Thomas R.
Skadden, Arps et al.
LandOfFree
Secure modular exponentiation with leak minimization for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Secure modular exponentiation with leak minimization for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secure modular exponentiation with leak minimization for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598655