Analyzing a Family of Key Protection Schemes against Modification Attacks

Protecting cryptographic keys in hardware devices is challenging. In this work, we reinvestigate a family of key protection schemes proposed by Fung, Golin and Gray (2001), which use permutations to protect keys stored in Electrically Erasable Programmable Read-Only Memory (EEPROM). Our analysis discovers vulnerabilities in the use of mathematical permutations. Specifically, we successfully identify two practical attacks-batch card attack and relative probing attack-which allow an adversary to discover the secret key stored in the EEPROM. Contrary to the claims of Fung et al., these attacks are realizable with a relatively small number of probes. Moreover, we examine the rationale of their security assumptions, which are mainly based on the modification attack described by Anderson and Kuhn (1997), and conclude that recent advances in hardware security (w.r.t. both attacks and countermeasures) suggest a stronger adversary model on designing such secure devices.