Cryptanalysis of the m-permutation protection schemes - WU, Hongjun (Institutional Knowledge at Singapore Management University, 2000)
Anderson and Kuhn have proposed the EEPROM modification attack to recover the secret key stored in the EEPROM. At ACISP ’98, Fung and Gray proposed an m-permutation protection scheme against the EEPROM modification attack. At ACISP ’99, Fung and Gray pointed out that in their original scheme, a secret key with too small or too large Hamming weight could be recovered easily. Then they proposed a revised m- permutation protection scheme and claimed that their revised scheme does not leak any information of the secret key. In this paper, we break completely both the original and the revised m-permutation protection schemes. The original scheme is broken with about 2log2 n devices from the same batch and about (3log2 n +2 ) ×m ×n probes (n is the length of the secret key and m is the amount of permutations). The revised m-permutation protection scheme is more vulnerable than the original one. It could be broken with only one device and about m ×n 3/3 probes.