Bellcore Media Advisory.

MORRISTOWN, N.J.--(BUSINESS WIRE)--Sept. 26, 1996--Bellcore, a leading provider of communications software, engineering and consulting services, is a recognized expert in all aspects of network security.

It is therefore our responsibility to alert our customers about the possibility of any threat to the security of their networks and communications products and services.

As a result, Bellcore has issued an alert to its clients notifying them about a potentially serious problem that could significantly impact the security of the "smart cards" that are used by many domestic and international phone companies and banking institutions. A smart card can be manipulated into making a computational error which can then render it vulnerable to the mathematical techniques used by cryptographers to extract secrets stored in the card, including the secret key used to authenticate the legitimacy of that card.

Bellcore also notified them that Bellcore is available to analyze the various devices and computers that are used by all electronic cash systems to determine the extent of a potential threat to any one particular system. Bellcore also offers unique solutions developed by its team of security experts that are unavailable anywhere else. These solutions generally involve complex mathematical cryptography methods, as well as other methods that involve the physical characteristics and defenses built into some existing cards.

Bellcore has experts on this subject available to answer inquiries from the media about this situation. If you wish to set up an interview, please contact Bellcore media relations manager Ken Branson on 201/829-2165 and Annie Lindstrom on 201/829-4062. -0- SECURITY ALERT

Now Smart Cards Can Leak Secrets;

A New Breed Of Crypto Attack on 'Tamperproof'

Tokens Cracks Even the Strongest RSA Code

SEPTEMBER 25, 1996--Security research findings do not usually cause dramatic changes in the marketplace. This one will. It's such a novel approach to breaking cryptographic security systems that it is considered a new threat model. The work is formally called 'Cryptanalysis in the Presence of Hardware Faults," and it exposes a serious flaw in the assumptions made by manufacturers of smart cards, secure ID cards, and other "tamperproof" hardware tokens that are used for secure networked transactions.

The attack targets public key cryptography schemes- such as the well-known RSA authentication and digital signature algorithms-when they are implemented in tamperproof devices. RSA public key cryptography has been licensed to a wide range of companies for inclusion in their products and services. Indeed, faith in the strength of this code underlies much of the market optimism for electronic commerce.

Of all the challenges facing electronic commerce- billing logistics, Internet congestion, lack of privacy, and so forth-the new attack on tamperproof devices may be the most debilitating. It diminishes confidence in smart cards that are used for stored value, such as some forms of electronic money; and in cards that personalize cellular phones, generate digital signatures, or authenticate users for remote login to corporate networks. The security risks in each of these examples are impersonation and fraudulent use of data.

"Designers of cryptography systems have a new constraint to worry about,' says Dan Boneh, a Bellcore research scientist and co-developer of the new threat model along with Richard Lipton, a professor of computer science at Princeton University and a Bellcore chief scientist, and Richard DeMillo, a Bellcore vice president and head of Bellcore's Information Sciences and Technologies Research laboratory. "'Our attack," Boneh explains, "is basically a creative use of a device's miscalculations, or, faults. Now, tamperproof devices must not only conceal the unit's inner circuitry but also be fault resistant."

In light of the new threat model, it is dangerous to assume that secret information stored in a tamperproof device cannot be discovered by an adversary. Moreover, according to DeMillo, "designers of tamperproof devices can no longer claim with impunity that their products are secure. An external testing organization, such as Bellcore, must determine to what extent the device is vulnerable to the new attack-by analyzing the design and manufacture of the device and playing the results against the new mathematical methodology."

HOW THE NEW ATTACK WORKS

Lipton is given credit for making the crucial observation on which the new threat model is based. He noted that once a device performs a faulty computation, it may well leak information that can be used for cryptanalysis. This is a new way of looking at the fact, widely acknowledged in the computer industry, that no computing system can be perfectly fault free.

The attack uses an algorithm that, first, compares the faulty values generated by a device against correct values and, second, infers the cryptographic code stored inside the device. Next, in the case of some RSA implementations, the algorithm efficiently factors the RSA modulus. It is not difficult to then derive the private key of the private/public key pair.

Perhaps the most powerful and surprising aspect of the new threat model is that it avoids directly factoring the RSA modulus. Therefore, it is equally effective against moduli of any length. In contrast, the Number Field Sieve factoring technique developed by former Bellcore research scientist Arjen Lenstra and others has, so far, broken RSA implementations using moduli that are 130 digits (i.e., 431 bits) long but has not succeeded against 512-bit implementations, which are used in products worldwide.

"Even if all of the products currently using RSA authentication or digital signatures were upgraded to use 1024-bit moduli, we could still break the code with the new threat model," says Boneh. But, he adds, the algorithm used in the new threat model is not effective against symmetric or, secret key cryptographic techniques, such as the Data Encryption Standard (DES) and Bellcore's Video Rate Algorithm (VRA). "The algorithm that we apply to the device's faulty computations works against the algebraic structure used in public key cryptography," Boneh explains. "Another algorithm will have to be devised to work against the nonalgebraic operations that are used in secret key techniques."

CREATING FAULTS

The new threat model hypothesizes that a tamperproof device can be easily subjected to physical stresses that cause it to generate faulty computations at rare and unpredictable rates. It is reasonable to assume that an adversary could easily gain full control over a smart card and card-reading device while the processor is performing security-related calculations. Certain levels of radiation or atypical voltage could then be applied, or for brief periods of time the device might be given a higher clock rate that it was designed to accommodate.

It would be more difficult to gain this type of control over a larger computing device housed inside a secure environment. So far, therefore, it seems that the new threat model is most acute against such tamperproof devices as smart cards because we can cause them to make faults. However, there is a substantial threat even in the case of servers that operate behind locked doors. Lipton notes that since all computers make errors from time to time, "even servers are not safe from our attack. Our methods work even against machines that we cannot actively tamper with. As long as they are not perfect, we can use our methods to break their security code."

The new model has been tested using hypothetical calculations, but the physical phase of the research has not been carried out. It is not, however, necessary to mount the attack in order to emphasize its seriousness. In the security community, it is universally accepted that the mere possibility of an attack's existence is a sign of great danger. Now that the model called "Cryptanalysis in the Presence of Hardware Faults" has been proven to work theoretically, security experts must assume that attackers exist who have the means of carrying it out.

One way to protect devices against the new attack is to ensure that the computing device verifies the computed value by, for example, repeating the computation and checking that the same answer is obtained both times. Unfortunately, in some systems, this form of protection usually slows down the computation by a factor of 2. For some applications, this drag on performance is not acceptable.

Lipton points out that "checking the computation in this way may not stop all our attacks." A better way to protect a tamperproof device is to use protocols that are fault-resistant. Lipton believes that it may be possible to create such protocols.

NEW THREAT MODEL BREAKS CRYPTO CODES

Fact Sheet Backgrounder for Press Release

WHAT END-USER APPLICATIONS SUBMIT TO YOUR CODE-BREAKING SCHEME?

Our research discovery proves that all tamperproof devices--such as smart cards and other hardware security tokens--that use public key cryptography for user authentication are now at risk. For example, smart cards that are used for stored value, such as some forms of electronic money; cards that personalize cellular phones; cards that generate digital signatures; and cards that authenticate users for remote login to corporate networks are all open to the attack that we describe. The underlying crimes in all these cases are impersonation and fraudulent use of data.

HOW DOES YOUR RESEARCH AFFECT THE SECURITY INDUSTRY?

Designers of cryptography systems now have a new constraint to worry about. Our attack is basically a creative use of a devices, miscalculations, or, faults. Therefore, tamperproof devices must now not only conceal the device's inner circuitry but also be fault resistant. Being tamperproof is no longer good enough to ensure security.

WHAT IS THE BUSINESS SIGNIFICANCE OF THIS RESEARCH?

Designers of "tamperproof" devices can no longer claim with impunity that their products are secure. An external organization, such as Bellcore, will have to determine to what extent the devices are vulnerable. Bellcore would analyze the design and manufacture of the device--in effect, test it--and play the results against the mathematical methodology of the new threat model.

WHAT IS YOUR NEW THREAT MODEL?

We observed that once a computing device performs a faulty computation, it might leak information that can be useful for inferring secret data. This is a novel approach to the widely acknowledged fact that no computing system is safe from faults.

In our theoretical model, which is called Cryptanalysis in the Presence of Hardware Faults, we use an algorithm to compare the faulty values with correct values and then to infer the cryptographic code stored in a tamperproof device.

It can be likened to a person making a Freudian slip; the listener compares the phrase with other observations and certain thinking processes to infer things about the speaker that he might otherwise have wished to keep secret.

WHAT CRYPTOGRAPHIC CODES DOES THIS APPROACH BREAK?

This model is a threat to authentication systems that use public key cryptography and that are implemented in tamperproof devices. So far, we have shown that the following types of public key cryptography can be broken with our model: RSA, Rabin's Signature Scheme, and the Fiat-Shamir Identification Scheme.

HOW DOES YOUR ATTACK ON RSA COMPARE WITH FACTORING ATTACKS?

Our attack is much more powerful than cryptanalysis that uses factoring. For example, the Number Field Sieve factoring technique developed by Arjen Lenstra and others has so far broken RSA implementations using 130-digit (i.e., 431-bit) moduli. But our attack applies to any length of modulus.

Even if all of the products currently using RSA authentication were upgraded to use 1024-bit moduli, we could still break the code.

DOES YOUR ATTACK ENDANGER SECRET KEY CRYPTOGRAPHY, SUCH AS DES?

No. The algorithm that we apply to the device's faulty computations is effective against the algebraic structure used in public key cryptography. Another algorithm will have to be devised to work against the nonalgebraic operations that are used in secret key cryptography. The Data Encryption Standard (DES) and Bellcore's Video Rate Algorithm (VRA) both use secret key cryptography, which is also called symmetric key cryptography.

WHY IS YOUR ATTACK MODEL RESTRICTED TO TAMPERPROOF DEVICES?

The attack succeeds because it takes advantage of a processor's faulty computations. In our model we hypothesize that tamperproof devices, such as smart cards or any hardware tokens, can be easily subjected to harmful physical stresses and thereby forced to make faults. The attacker can easily gain full control over a smart card and card-reading device while the processor is performing security-related calculations.

It would be more difficult to gain this type of control over a larger computing device housed inside a secure environment. So far, therefore, it seems that our model is best suited for attacking tamperproof devices.

WHAT KIND OF PHYSICAL STRESS WOULD BE APPLIED TO THE CARD?

It is reasonable to assume that certain levels of radiation or heat, or incorrect voltage, or atypical clock rates could be imposed on tamperproof devices, which are usually small and portable. These physical stresses can cause the device to malfunction while it is calculating.

HOW DO YOU USE THE FAULTY COMPUTATIONAL VALUES?

We derived an algorithm that makes use of the faulty values in order to recover the factors of the stored cryptographic information. In the case of RSA implementations, our algorithm efficiently factors the RSA modulus. It is not difficult to then derive the public key of the private/public key pair.

WHAT LONG-TERM SIGNIFICANCE DO YOU ENVISION FOR THIS WORK?

Our threat model will spark a new research trend. In addition to focusing on the mathematical properties of the code, researchers may now try to apply the idea of using hardware faults to other cryptographic schemes and perhaps prove that certain schemes are resistant to this type of attack.

HOW DOES THIS COMPARE WITH THE TIMING ATTACK ON RSA ANNOUNCED EARLIER THIS YEAR?

They are similar in that both measure things that are taking place within the processing device. The timing attack described by Paul Kocher compares the discrepancies in time required by certain operations and uses this information to extract the secret information. Our attack is based on using the occurrence of hardware faults to extract the secret data. It may be harder to protect against our attack than to thwart the timing attack.

HAVE YOU TESTED YOUR THEORETICAL MODEL?

We have tested the algorithm using hypothetical faulty calculations. But we have not carried out the physical phase of the research, which would involve using a radiation chamber or high voltage source.

It is not, however, necessary to mount the attack in order to emphasize its seriousness. In the security community, it is widely acknowledged that the mere possibility of an attack existing is a sign of great danger. Now that we have proved that the attack model called Cryptanalysis in the Presence of Hardware Faults works, we must assume that attackers exist who have the means of carrying it out. The fact that our work has not yet been experimented with in the laboratory does not make it a less serious security threat.

HOW CAN DESIGNERS PROTECT SMART CARDS FROM THIS ATTACK?

One way to protect against the attack is to ensure that the device verifies the computed value by, for example, repeating the computation and checking that the same answer is obtained both times. Unfortunately, this form of protection usually slows down the computation by a factor of 2. For some applications, this drag on performance is not acceptable.

WHO ARE THE RESEARCHERS WHO DEVELOPED THE NEW THREAT MODEL?

Richard Lipton, a professor of computer science at Princeton University and a part-time Bellcore research scientist; Rich DeMillo, a Bellcore vice president and head of Bellcore's Information Sciences and Technologies Research laboratory; and Dan Boneh, a Bellcore research scientist. Richard Lipton made the crucial observation that once a device performs a faulty computation, it may well leak information that can be used for cryptanalysis.

CONTACT: Bellcore

Ken Branson, 201/829-2165

or

Annie Lindstrom, 201/829-4062