What, cryptographically speaking, is a “long message”?

Question

I have read about long message attacks on some cryptographic hash functions. However, I don't quite understand what is being referred to as a "long message".

Also, do long message attacks only apply for such "long" messages or can they also be used (any exceptions?) with "normal" messages? ("Normal" as opposed to "long", I mean)

Thank you.

EDIT: Actually, I thought I wanted a general explanation, but I guess it might be better that I specify the source of my misunderstanding. Reading Gauravaram and Kelsey's Cryptanalysis of a class of cryptographic hash functions in trying to understand second-preimage attacks, I came across the generic long message second preimage attack on GOST in Appendix Section E.1 (page 26) and it got me wondering on the meaning (and pertinence) of the so-called "long message" attack.

Hope this clarifies my question better.

Answer 1

Without the specific reference I can't be sure this is what you are talking about, but generally a "long message" attack is a way to defeat second preimage resistance with less complexity than expected. It uses a time-space tradeoff to find a second preimage with complexity $2^{n/2}$ for a $n$-bit hash function (normally you would expect $2^n$).

In the simplest form, what you do is generate a message that is $2^{n/2}$ blocks long, which will consequently have about $2^{n/2}$ "intermediate" hash values (output from the hash function upon processing each block). You store those hash values in memory, and then try repeatedly hashing random messages until you find a message $m$ such that $h(m)$ is equal to one of the intermediate hash values. This will take about $2^{n/2}$ tries, since you have $2^{n/2}$ targets to shoot for.

At this point you can split the long message on that target intermediate value and "splice" the message $m$ into that place, and it will still produce the same final output. What this effectively does, is find a collision somewhere in the interior of the message and replace that substring with the new colliding one. Since collisions are generally easier to find than second preimages (because of the birthday paradox), this leads to an effective second preimage attack. Particularly, it requires only about $2^{n/2}$ time and $2^{n/2}$ memory, instead of $2^{n}$ time.

However, this is purely an academic attack since most hash functions use the Merkle-Damgard construction to handle large messages, and it includes a block at the end which specifies the length of the message. In the above attack the two messages will not have the same length.

Answer 2

A long message is a message that, when padded, is longer than the block size of the hash function. That means that the hash function has to process the message in parts and keep track of state somehow, which may allow for attacks. Such attacks would not apply to messages shorter than the block size, and may additionally require a large number of blocks to give a real advantage.

For example, the Merkle–Damgård construction used by e.g. SHA-2 allows a second preimage attack with complexity $2^{n/2+1}+2^{n-k+1}$, which for large about number of blocks (denoted by $2^{k}$) is much more efficient than the brute force $2^{n}$ complexity. It doesn't apply to single block messages at all, and would require a large enough $k$ to be a real advantage over brute force.