Virtual Smart Cards: How to Sign with a Password and a Server

Abstract. An important shortcoming of client-side cryptography on consumer devices is the poor protection of secret keys. Encrypting the keys under a human-memorizable password hardly offers any protection when the device is stolen. Trusted hardware tokens such as smart cards can provide strong protection of keys but are cumbersome to use. We consider the case where secret keys are used for digital signatures and propose a password-authenticated server-aided signature Pass2Sign pro-tocol, where signatures are collaboratively generated by a device and a server, while the user authenticates to the server with a (low-entropy) password. Neither the server nor the device store enough information to create a signature by itself or to perform an offline attack on the pass-word. The signed message remains hidden from the server. We argue that our protocol offers comparable security to trusted hardware, but with-out its inconveniences. We prove it secure in the universal composability (UC) framework in a very strong adaptive corruption model where, un-like standard UC, the adversary does not obtain past inputs and outputs upon corrupting a party. This is crucial to hide previously entered pass-words and messages from the adversary when the device gets corrupted. The protocol itself is surprisingly simple: it is round-optimal, efficient, and relies exclusively on standard primitives such as hash functions and RSA. The security proof involves a novel random-oracle programming technique that may be of independent interest.