State space blow-up in the verification of secure smartcard interoperability

Smartcards are used in a wide range of applications including electronic (e-) driving licenses, e-identity cards, e-payments, e-health cards, and digital signatures. Nevertheless secure smartcard interoperability has remained a significant challenge. Currently the secure operation of smartcards is certified (e.g. through the Common Criteria) for a specific and closed environment that does not comprise the presence of other smartcards and their corresponding applications. To enable secure smartcard interoperability one must, however, explicitly consider settings in which different smartcards interact with their corresponding applications, i.e. not in isolation. Consequently the interoperability problem is only insufficiently addressed in security verification processes. In an ideal scenario one should be able to certify that introducing a new type of smartcard into an environment in which several smartcards safely interoperate will have no detrimental side-effects for the security and interoperability of the existing system as well as for the new smartcard and its associated applications. In this work, strong experimental evidence is presented demonstrating that such certification cannot be provided through common model checking approaches for security verification due to state space blow-up. Furthermore it is shown how the state space blow-up can be prevented by employing a verification protocol which, by taking the results of the Common Criteria certification into account, avoids checking any transitions that occur after an illegal transition has been detected. © 2012 IEEE.