Efficient Implementation of Keyless Signatures with Hash Sequence Authentication.

Abstract. We present new ideas for decreasing the size of secure memory needed for hardware imple-mentations of hash-sequence based signatures proposed recently by Buldas, Laanoja and Truu (in the following referred to as BLT). In their scheme, a message m is signed by time-stamping a concatena-tion m‖zt of the message and the one-time pseudo-random password zt intended to sign messages at a particular time t. The signature is valid only if the time-stamp points to the same time t. Hence, the one time passwords cannot be abused after their use. To efficiently and securely implement such a scheme at the client side, dedicated hardware is needed and thereby, the solutions that save the (secure) memory and computational time are important. For such schemes, the memory consumption directly depends on the efficiency of the hash sequence reversal algorithms. The best known reversal algorithm for the BLT scheme uses O(log2 `) memory. This means that for a signing key that is valid for one year (i.e. ` ≈ 225 with one-second time resolution), the device needs to store about 252 = 625 hash values which for SHA-256 hashing algorithm means about 20 K bytes of secure memory. Another problem with hash sequence reversal algorithms is that they mostly assume that the signature device is always connected to the computer or has an independent power supply. This is a serious limitation for smart-card implementations of the scheme.