1






The Hong Kong University of Science and Technology
Department of Computer Science

PhD Thesis Defence

"Protection of Keys Against Modification Attacks"

By

Mr. Wai-Wa Fung

Abstract

In recent work, Anderson and Kuhn 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 based on the m n-bit words burned in the EEPROM.  It is observed that the m-permutation protection scheme does not distribute the key K uniformly. The thesis will 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 > 5 may not give significant improvement to the security of the scheme.


		Date:			Monday, 28 August 2000

		Time:			10:30a.m.-12:30p.m.
	
		Venue:			Room 2302						
					Lifts 17-18

		Chairman:		Prof. Kalok Chan (FINA)

		Committee Members:	Dr. Mordecai Golin (Supervisor)
					Dr. Cunsheng Ding
					Prof. Derick Wood
					Prof. S.Y. Cheng (MATH)
	Prof. Virgil D. Gligor  (	Electrical & Computer Engineering, 
	University of Maryland)


**** ALL are Welcome ****
??