International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: How to Disembed a Program?

Benoit Chevallier-Mames
David Naccache
Pascal Paillier
David Pointcheval
Search ePrint
Search Google
Abstract: This paper presents the theoretical blueprint of a new secure token called the Externalized Microprocessor (XmP). Unlike a smart-card, the XmP contains no ROM at all. While exporting all the device's executable code to potentially untrustworthy terminals poses formidable security problems, the advantages of ROM-less secure tokens are numerous: chip masking time disappears, bug patching becomes a mere terminal update and hence does not imply any roll-out of cards in the field. Most importantly, code size ceases to be a limiting factor. This is particularly significant given the steady increase in on-board software complexity. After describing the machine's instruction-set we will introduce two XmP variants. The first design is a public-key oriented architecture which relies on a new RSA screening scheme and features a relatively low communication overhead at the cost of computational complexity, whereas the second variant is secret-key oriented and relies on simple MACs and hash functions but requires more communication. For each of these two designs, we propose two protocols that execute and dynamically authenticate arbitrary programs. We also provide a strong security model for these protocols and prove their security under appropriate complexity assumptions.
  title={How to Disembed a Program?},
  booktitle={IACR Eprint archive},
  keywords={applications /},
  note={An extended abstract  appears in CHES'04 12579 received 10 Jun 2004},
  author={Benoit Chevallier-Mames and David Naccache and Pascal Paillier and David Pointcheval},