Paper 2014/700

Bounded Pre-Image Awareness and the Security of Hash-Tree Keyless Signatures

Ahto Buldas, Risto Laanoja, Peeter Laud, and Ahto Truu


We present a new tighter security proof for unbounded hash tree keyless signature (time-stamping) schemes that use Merkle-Damg\aa rd (MD) hash functions with Preimage Aware (PrA) compression functions. It is known that the PrA assumption alone is insufficient for proving the security of unbounded hash tree schemes against back-dating attacks. We show that many known PrA constructions satisfy a stronger \emph{Bounded Pre-Image Awareness (BPrA)} condition that assumes the existence of an extractor $\EXT$ that is bounded in the sense that for any efficiently computable query string $\alpha$, the number of outputs $y$ for which $\EXT(y,\alpha)$ succeeds does not exceed the number of queries in $\alpha$. We show that blockcipher based MD-hash functions with rate-1 compression functions (such as Davies-Meyer and Miyaguchi-Preneel) of both type I and type II are BPrA. We also show that the compression function of Shrimpton-Stam that uses non-compressing components is BPrA. The security proof for unbounded hash-tree schemes is very tight under the BPrA assumption. In order to have $2^s$-security against back-dating, the hash function must have $n=2s + 4$ output bits, assuming that the security of the hash function is close to the birthday barrier, i.e. that there are no structural weaknesses in the hash function itself. Note that the previous proofs that assume PrA gave the estimation $n=2s + 2 \log_2 C + 2$, where $C$ is the maximum allowed size of the hash tree. For example, if $s=100$ ($2^{100}$-security) and $C=2^{50}$, the previous proofs require $n=302$ output bits, while the new proof requires $n=204$ output bits.

Note: A missing author (Peeter Laud) added.

Available format(s)
Publication info
Published elsewhere. MINOR revision.ProvSec 2014
hash functionsPre-image awarenesstime-stamping
Contact author(s)
ahto buldas @ guardtime com
risto laanoja @ guardtime com
ahto truu @ guardtime com
2014-09-05: received
Short URL
Creative Commons Attribution


      author = {Ahto Buldas and Risto Laanoja and Peeter Laud and Ahto Truu},
      title = {Bounded Pre-Image Awareness and the Security of Hash-Tree Keyless Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2014/700},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.