[messaging] Fwd: [Cfrg] Analysis of Hash-Based Signatures (draft-mcgrew-hash-sigs-02)

[David Leon Gil]

> ---------- Forwarded message ----------
> From: Jonathan Katz <jkatz at cs.umd.edu>
> Date: Fri, May 29, 2015 at 7:17 AM
> Subject: [Cfrg] Analysis of Hash-Based Signatures (draft-mcgrew-hash-sigs-02)
> To: cfrg at irtf.org
> We analyze a signature scheme described in a recent Internet Draft,
> and highlight a variant (based on prior work of Micali and Leighton)
> that offers improved concrete security.
>
> The paper is available here:
> http://www.cs.umd.edu/~jkatz/papers/HashBasedSigs.pdf

I thought this list might be interested, both because of the stated
result w.r.t. hash-based signatures, as well as its direct application
to hash-tree-based append-only logs.

I don't think I ever posted here about it, but I suggested the
precaution of using a MAC (for key-transparency tries) to some of the
folks on this list a while back.

Short summary:

Suppose that you form a hash tree in the naive way, as, e.g.,

N_(..., 0, _) = Hash(N_(..., 0, 0) | N_(..., 0, 1))

where Hash has 's*2' bits of output, an adversary has a multitarget
advantage of O(log(#N)). (If there are K independent hash trees, this
increases the multitarget advantage similarly.)

So, instead of hashing, do something like:

N_(..., i, _) = Mac(k, encode_node_position(..., i) || N_(..., i, 0) |
N_(..., i, 1))

where `k` is a random, per-tree key.

This results in reasonably tight s-bit security. (Any admissible
tree-hashing mode has some encode_node_position function that can be
used for plain Merkle trees.)

--

This doesn't really work for certificate transparency, because the
append-only log is the Merkle tree itself. (But it remains useful for
each log to choose a random key rigidly, e.g., as Hash(dnsname).)

This does, however, work for key transparency proposals in the style of CONIKS.

- David