[adrian_b]

Twenty years ago this paper was considered surprising and, together with a handful of other attacks and with the concrete attacks against MD5 and SHA-1 succeeded by some Chinese researchers prompted the organization of the SHA-3 competition.

John Kelsey and Bruce Schneier: "Second Preimages on n-bit Hash Functions for Much Less than 2^n Work"

https://eprint.iacr.org/2004/304

The abstract at this link provides the essential results.

"We provide a second preimage attack on all n-bit iterated hash functions with Damgaard-Merkle strengthening and n-bit intermediate states, allowing a second preimage to be found for a 2^k-message-block message with about k * 2^(n/2+1) + 2^(n-k+1) work. Using SHA-1 as an example, our attack can find a second preimage for a 2^60 byte message in 2^106 work, rather than the previously expected 2^160 work."

Besides this result, there is also the previous result obtained by Joux for multi-collisions, which also become easier for longer input data (Antoine Joux: "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions").

[oconnor663]

Thanks! I've added a note about this here: https://github.com/oconnor663/bao/issues/41#issuecomment-119.... Does that sound like an accurate summary to you?

[adrian_b]

It is OK, but the problems demonstrated by these attacks and others similar to them are specific to the linear chaining of a great number of blocks, where the same hashing function is applied to all blocks.

Incorporating somehow a block counter in the block hashing function or using a sponge structure is equivalent to using a different hashing function for each block, which stops the attacks.

Tree hashing where the final branches i.e. the chunks are short, so there are only a small number of blocks hashed in cascade with the same function, behaves differently from linear block chaining, because the hashing function must include additional inputs anyway, so the blocks in a chunk are hashed differently from the blocks that merge tree branches or the root block.

Whether any of the attacks that exist for simple Merkle-Damgaard cascading like SHA-2 are applicable to a tree hash depends on how the blocks are encoded and on the structure of the tree. In any case, the probabilities of success will be different in the case of a tree hash.

I have never analyzed whether the BLAKE2 or BLAKE3 tree hashes could be secure enough without block counters. In any case, the block counters, which are absolutely necessary for linear block chaining, also increase the strength of tree hashing against any attacks and their added overhead is minimal, so there would be no reason to remove them.

A hash computed with a sponge structure, like SHA-3 or KangarooTwelve, is equivalent with a CBC-MAC where the key is updated at each block, instead of being constant. Because each block is hashed with a different key, there is no need for an additional counter input to differentiate the hashing functions. A sponge structure is much simpler than the structure used by BLAKE, but it needs a wider invertible mixing transformation, e.g. for a similar strength BLAKE2b uses an 1024-bit mixing transformation, while SHA-3 uses an 1600-bit mixing transformation. (BLAKE3 trades off strength for speed, so it is not comparable with SHA-3, but only with KangarooTwelve.)