In recent work, Anderson and Kuhn [4] described an attack against tamper-resistant devices wherein a secret key stored in EEPROM is compromised using a simple and low-cost attack. The attack consists of setting bits in the EEPROM using low-cost probes and observing the effect on the output of the device. These attacks are extremely general, as they apply to virtually any cryptosystem. The objective of the present work is to explore cryptographic techniques with the goal of raising the cost (in terms of time and money) of carrying out the EEPROM modification attack by Class I attackers, at least to a point where it is as prohibitive as the cost of purchasing more expensive equipment....[ Read more ]

In recent work, Anderson and Kuhn [4] described an attack against tamper-resistant devices wherein a secret key stored in EEPROM is compromised using a simple and low-cost attack. The attack consists of setting bits in the EEPROM using low-cost probes and observing the effect on the output of the device. These attacks are extremely general, as they apply to virtually any cryptosystem. The objective of the present work is to explore cryptographic techniques with the goal of raising the cost (in terms of time and money) of carrying out the EEPROM modification attack by Class I attackers, at least to a point where it is as prohibitive as the cost of purchasing more expensive equipment.

First, several possible protection schemes as well as their weaknesses are discussed. We then propose the m-permutation protection scheme in which the key will be encoded in a special way and burned into the EEPROM of the device; its complimentary decoding process will rely on knowledge of the hidden wirings in the device, finding which is a difficult task for Class I attackers.

To attack the scheme, the attacker needs to be able to solve for K in the equation K= ⊕^m_i=1 P_i in which P_i's are unknown. It is observed that the m-permutation protection scheme does not distribute the key K uniformly. We analyse this behavior and show that although the keys are not uniformly distributed, their distribution is close to uniform if weak values are discarded. We illustrate that Chernoff bounds can help us discard the weak choices during the encoding process. Upper bounds for the probability that the attacker can infer the key from the known information is provided. Analysis also shows that m = 3 or m = 5 are already good enough practically to provide strong security if the encoding is done properly and that m [greater than] 5 may not give significant improvement to the security of the scheme.