Cryptography – Cryptanalysis
Reexamination Certificate
1999-04-29
2001-10-02
Hayes, Gail (Department: 1131)
Cryptography
Cryptanalysis
C708S491000
Reexamination Certificate
active
06298135
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to microelectronic assemblies, and more particularly, to smartcards and the like and methods for preventing security breach of the same when a power analysis attack is used.
BACKGROUND OF THE INVENTION
Present implementations of cryptographic algorithms implemented in tamper-resistant hardware, such as a smartcard, and certain smartcard microcontrollers, are vulnerable to specific kinds of attacks. For example, when an encryption algorithm is run in software or hardware in a microcontroller, close observation and monitoring of the microcontroller's power consumption has been shown to be correlated to the data being operated on. It has further been shown that such correlated information can then be used to enable recovery of, for example, cryptographic key information stored or processed by the microcontroller.
The information revealed by the power consumption can today be monitored in various ways, ranging from simple techniques, such as simple power analysis (SPA), to more complex techniques, such as differential power analysis (DPA). These attacks are described in greater detail in a technical information bulletin, titled “Introduction to Differential Power Analysis and Related Attacks”, by Paul Kocher, et al., of Cryptography Research, San Francisco, Calif., copyright 1998, reprinted at web site: www.cryptography.com.
In a typical smartcard system, the private-key for a public-key cryptosystem will be stored in a smartcard. A smartcard contains a microprocessor that is designed to be a tamper-resistant device. A smartcard's microprocessor is intended to be capable of storing the private key in such a manner as to prevent a malicious attacker from tampering with the smartcard and learning the value of this private key. However, power consumption information of a smartcard can be monitored by a malicious attacker to learn the bits of this private-key, thus breaching the security of the smartcard.
A smartcard is often used to digitally “sign” a random message as a proof of identity. This scheme is often referred to as an authentication algorithm and is used to ensure knowledge of a private key. In a popular authentication algorithm known as RSA, a smartcard contains a secret exponent E that is used as the private key. In order to determine if a smartcard is authentic, the smartcard is asked to raise A to the power of E and reduce the result by a modulus N. This mathematical operation is referred to as modular exponentiation. The notation for modular exponentiation is given in the following equation, where B is the result of the modular exponentiation and is referred to as the digital signature of A:
B=A
E
mod N
If the smartcard is authentic, then the resulting signature, B, can be verified by using the smartcard's public key, D, by performing another modular exponentiation operation given as:
A=B
D
mod N
In the RSA authentication scheme, the values of E and D are chosen such that the above equations are always true.
Another popular authentication algorithm known as an elliptic-curve cryptosystem can also be used for authentication purposes. An authentication scheme using elliptic curves is analogous to the RSA authentication, but instead of exponentiation, which is repeated multiplications, the elliptic-curve algorithm uses scalar point multiplication, which is repeated point additions. The elliptic-curve scheme also requires the use of a secret scalar, k, which is used to digitally sign messages.
In a smartcard system that uses modular exponentiation for authentication the value of E is stored in the memory of the smartcard's microprocessor and the modular exponentiation of A by E is performed in the smartcard's microprocessor. The secrecy of E is vital to the security of an authentication scheme. If E were revealed to a malicious attacker, then the security of the system would fail. The revelation of E would make it impossible to distinguish between the actual smartcard and an attacker possessing the secret E that is posing as the real smartcard. A similar argument can be made for protecting the secrecy of the scalar k in the elliptic-curve cryptosystem. Once the security of a tamper-resistant device, such as smartcards, has been breached and the secret exponent or scalar is known to an attacker, cloning smartcards, or theft of services/values from smartcards, becomes a real threat.
Unfortunately it can be shown that bits of E or k can be recovered by a malicious attacker using a Differential Power Analysis (DPA) attack. An attacker performing this attack on a smartcard can monitor the power consumption of the smartcard while the secret key, is being used to digitally sign a message. In the RSA cryptosystem, the secret E is used during the modular exponentiation operation and in an elliptic-curve cryptosystem, the secret k is used during the multiplication operation. In the RSA cryptosystem, the result of the modular exponentiation is obtained using a well-known algorithm called the square-and-multiply algorithm. In the elliptic-curve cryptosystem, the multiplication result is obtained using an analogous algorithm called the double-and-multiply algorithm. When the secret E is used by a smartcard during the square-and-multiply algorithm or the secret k is used by the double-and-multiply algorithm, the instantaneous power consumption can be monitored by an attacker. The attacker can use this power consumption information to learn the value of the secret.
A solution is therefore desired for mitigating or altogether eliminating the vulnerability of cryptographic elements that may possibly result by analysis of power variations, such as a cryptographic element revealing power consumption information that is correlated to the secret exponent.
REFERENCES:
patent: 5742530 (1998-04-01), Gressel et al.
patent: 5745398 (1998-04-01), Monier
patent: 5991415 (1999-11-01), Shamir
patent: 5995629 (1999-11-01), Reiner
patent: WO99/35782 (1999-07-01), None
Wayner. “Code Breaker Cracks Smart Card's Digital Safe”. The New York Times. Jun. 22, 1998. pp. 1-5.*
Kocher et al. “Differential Power Analysis”. Advances in Cryptology: Proceedings of CRYPTO '99. Springer-Verlag. Aug. 1999. pp. 388-397.*
Kocher et al. “Introduction to Differential Power Analysis and Related Attacks”. Cryptology Research, Inc. 1998. pp. 1-7.*
Anderson et al. “Tamper Resistance-a Cautionary Note”. The Second USENIX Workshop on Electronic Commerce Proceedings.Nov. 1996. pp. 1-11.*
Biham et al. “Differential Fault Analysis of Secret Key Cryptosystems”. Advances in Cryptology: Proceedings of CRYPTO '97. Springer-Verlag. Aug. 1997. pp. 513-525.*
Anderson et al. “Low Cost Attacks on Tamper Resistant Devices”. Security Protocol Workshop. Apr. 1997.*
Kocher et al. “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems”. Advances in Cryptology: Proceedings of CRYPTO '96. Springer-Verlag. Aug. 1996. pp. 104-113.*
Messerges et al. “Investigation of Power Analysis Attacks on Smartcards”. pp. 1-14.
Dabbish Ezzat A.
Messerges Thomas S.
Cyrus Khosravi K.
DiLorenzo Anthony
Hayes Gail
Hughes Terri S.
Motorola Inc.
LandOfFree
Method of preventing power analysis attacks on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of preventing power analysis attacks on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of preventing power analysis attacks on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579083