Yes, there are attacks. Hash functions aren't designed for massive related message first preimage attacks. In an ideal scenario. Where the attacker can get a MAC for any string he wants that's what the hash has to stand up against. The one way function inside MD4 has to resist being reversed even when fed with lots of attacker controlled message blocks. This isn't something it was designed to do.
MD4 is similar to most of its successors (MD5 SHA1, SHA2) in that it's built from a Davies–Meyer compression function. There's an internal 128 bit state. To process a message block, the state is encrypted using a 128 bit block cipher keyed with the message block (512 bits --> 32bits x 16 words). To make the function one way, the input value is added to the output before processing the next block.
So, consider this a sort of fault injection attack. We get to flip bits of the round keys and see the resulting cipher-text (with the plaintext as an offset) we can vary the other message blocks to vary the plain-text that will be encrypted and then added to the result before we get it. The goal is to recover the plain-text.
The block cipher here has 48 rounds. There's about 200 nonlinear operations, with pretty good mixing between rounds. This sounds pretty horrible right?
Well the rounds are actually split into three groups of 16 rounds and the key schedule isn't too complex. Each of the 16 rounds in a group uses one of the 32 bit words in the current message block as a round key. Any bits we flip in a message cause a bit flip in three of the round keys.
Let's say we flipped two bits, one in one round key and another in a later round key. It's possible that the first bit flip would be cancelled by the second. Its also possible for this to repeat itself for the same bit flips in the second group of rounds. That would leave only the bit flips in the final group of rounds which are close enough to the final value we see that we might be able to distinguish that case.
Taking a look at section 3.4 of the MD4 spec, pairs (5,9) and (6,10) look promising. They aren't used too far apart in the first and second round groups while also being close enough to the end in the third round group not to have the differences spread too much before the end
(11,14) would be better but are more limited since 14 is part of the padding (the message length) which limits the bit flips we can do.
So we need the differences to cancel in the first and second round groups. We detect the lack of significant change in the hash output. This gives us information about the internal state where the cancellation happened.
Once this happens, we can make a slight change in the area of the first cancellation and then make further changes afterwards until there's a cancellation in the second round group. This gives more information. As our information improves we become limited by the probability of the second cancellation since getting that to happen is blind luck. Eventually though, we would have the full state in the area of the first collision. Just work backwards from that to get the input, the thing we were trying to get.
What does this get you?
Case 1: The secret key is the initial hash state.
The attacker can recover the initial state used as the MAC key. They can now MAC any message they want.
Case 2: the secret key is prepended to the message data and the message and key fit in a single block.
This complicates the attack but likely not that much. This would directly recover the secret key.
Case 3: The secret key is prepended to the message but padded to take up the whole first block.
Now the attacker can't recover the key but , like with case 1, can recover the secret internal state required to MAC arbitrary messages.
Case 4: The minimum message size is several blocks.
Now the attacker can't recover the key. They can only work backwards 1 block at a time. Every output value used in attacking the second to last block has to be gotten by repeating the whole attack process for the last block. If attacking one block takes N queries, attacking two takes N^2 and 3 N^3 queries. They'll likely be able to change the last block but nothing else.
Is there any way to mitigate this without using HMAC?
Yes! Add 55 bytes (64 byte block - (8 byte length + 1 byte min padding)) of constant value padding to your message before hashing. This is enough to keep all message data out of the last block. Now the attacker can't get access to the output value of the last block for which they supply message data. None of the interesting behaviour is visible to them except through an entire block of nasty behaviour.
That other statistical attack
There is one other failure mode worth mentioning. Thanks to the birthday paradox, submitting on average 2^64 plain-texts where a single block is tweaked will yield a collision. If they do the same for a second block they'll also get a collision. The important point is, this is a collision in the internal state so where A and A' are the first set of colliding blocks MAC(AB)=MAC(A'B)=MAC(AB')=MAC(A'B'). The internal state after processing block A is the same as after processing block A'. This is known as a multicollision and generalizes to multiple chained blocks. Using MD4-HMAC does not help with this since this is a fundamental statistical weakness of Merkle–Damgård construction.
What about other hash algorithms (MD5, SHA1, SHA256 ...)
They would be a lot harder to attack if not impossible. The same properties that make this kind of attack function also make it easier to find collisions. MD5 has four round groups with more shuffling of sub-keys. All other variants have a real key schedule with messy nonlinear operations used to expand the message block into multiple round keys. The probability of touching something deep inside and not completely changing the output is negligible.
