On Design of Memory Data Authentication For Embedded Processor Systems

The boom of embedded systems and their wide applications, especially in thearea of e-business and -service, have raised increasing concerns about their security. One of the vulnerable components in most embedded systems is memory.Protecting memory data is essential to the embedded system.Many designs for memory data protection are based on the cryptographic primitives that have been systematically analysed and extensively evaluated, and oftenprovide a guaranteed level of security. However, such cryptographic primitivesusually come with significant processing and resource costs and may not be suit-able to embedded systems, where resources are extremely restricted.This thesis studies an existing design for protecting the integrity of memory datain an embedded processor system, where tag is used for data authentication. Thedesign is highly cost efficient, consumes small on-chip resources and low off-chipmemory, and offers flexibility for good trade-off between the design security andits implementation cost.However, the design assumes that the data to be protected are random and fitthe uniform distribution, and the security of the design is mainly focused onthe attacks with random data and tag values. Attacks with chosen values havemerely been addressed. Nevertheless, the chosen-value attacks can exploitthe design weakness, is much stronger than the random attack, and determinesthe true security level of a design.We have identified three pitfalls in this design: 1) there are some correlationsbetween data and the tag, 2) for a given data, its tag value is not distributed over thewhole tag value space; the effective tag space size for a given data is reducedand is less than the half of the tag value space, and 3) the effective tag space sizevaries for different data. Those weaknesses lead to the low security of the design.To patch the loopholes, we improve the design by implementing a series of randomflip functions and non-linear Galois field multiplication on the data blocks. Weshow, through the theoretical analysis and experimental demonstration, that with the design modifications the tag generated bears no correlation to its dataand the tag is uniformly random over the full tag value space. The improveddesign has the same capability to counter attacks with chosen values as to counterattacks with the random data. Therefore, the design is much secure yet stillretaining the cost effective feature of the original design