Secure Key Storage Using State Machines

In hardware implementations of cryptographic systems, secret keys are commonly stored in an on-chip memory. This makes them prone to physical attacks, since the location of a memory on a chip in usually easy to spot. We propose to encode secret keys using a state machine which can be concealed in the rest of the logic on a chip. We present an heuristic algorithm which constructs a minimal state machine for a given set of secret keys. We show that, by using m-ary encoding, we are able to construct state machines which are smaller than the ones constructed using binary encoding. The presented algorithm is feasible for storing up to 1 Mbits of random data.