[Cryptography] Signature Hashing Choices ... So Many Choices ...

[Jon Callas]

> On Oct 19, 2017, at 6:38 AM, Andrew Donoho <awd at ddg.com> wrote:
> 
> ... This, of course, results in a different hash value. 
> 
> 	hash(preamble || BLOB) != hash(preamble || hash(BLOB))
> 
> To my cryptographically unsophisticated eye, they look to be equivalently secure. Are they? My trusty copy of "Cryptography Engineering" appears to be silent on this issue. Any opinions?

Yes, it's good enough.

Go look at the definition of an HMAC and note the similarities. HMAC is solving a different problem, but it's building on the same idea, which is that the properties of a hash function are such that you can substitute the hash for the data (or BLOB). That's really the whole point of signatures anyway – that it's impractical to sign the actual data and so you use the hash of data as a proxy for the data itself.

This idea is also used in tree hashing, hash chains like Merkle trees, and others. Tree hashing parallelizes hashing to speed it up by running a bunch of hashes of segments of the data in parallel, and then hashing all those hashes.

In the syslog-sign protocol that John Kelsey and I did, we play similar games by signing a message that is a bunch of hashes of messages. So instead of figuring out how you're going to sign a bunch of log messages, we hash each log entry, and then sign a set of hashes.

Now there is a limitation in this, and that is that if someone can get a collision or second-preimage attack on your BLOB, then your hash gets a collision in it that would otherwise be harder to do. The major way it's an easier problem for an attacker is that their alternate BLOB doesn't have to be the same size as the real blob.

There are ways that you could protect against that. Note my clever use of the term "guard against" as opposed to "prevent." 

For example, suppose you take your BLOB and cut it up into chunks and hash each one, along with a counter. So you hash 0 || chunk_0, 1 || chunk_1, ..., n || chunk_n (and note that the last chunk is probably short), all the while accumulating all of those intermediate hashes together into the hash context that will be the thing that you will *then* hash with your preamble.

This makes the job of an attacker harder because they're forced to create an attack on a fixed-size chunk as opposed on the whole BLOB.

I'll also add that if your basic hash function works correctly, this is unnecessary. However, it protects against classes of weaknesses like the ones that Merkle-Damgard hashes have. This is arguably gilding the lily, but it's also arguably a reasonable protection.

But anyway, answering your question, yeah, what you're doing works fine assuming the underlying hash function is not broken, and the exposure in your first-order construction has only a tiny opening for hash flaws to hurt you. If you care about this, you can do some type of chunking.

	Jon