Does it make sense to have a compression function that uses 64-bit of the message to create an output of 64-bit?

I have a very simple compression function, which looks like this in C++:

unsigned long long compress(unsigned long long current_block, unsigned long long last){
for(int i = 0; i<16; i++){
last += current_block;
last = last ^ (last << 13);
last = last ^ (last >> 11);
}
return last;
}


It's my own first try of a compression function :)
Now, this function is the core of a cryptographic hash function. All values are 64-bit. The function splits the message into 64-bit blocks, which get passed to the compression function (current_block) together with the sum (addition modulo $2^{64}$) of the last compressions (last). The initial value (the value that is used for last when the compression function is called the first time) is 0.
About the hash function itself: It is a Merkle–Damgård construction and the messages are padded with the length of the original message (64-bit value).

So, now I want to prove that this compression function is not preimage resistant (first and second) and not collision resistant. In order to do that I want to ignore the padding and just try to find the weaknesses of the compression function itself and then think about improves I could make.
In these days it is of course computationally feasible to brute force a 64-bit hash (particularly with a birthday attack), so I understand the term "collision resistant" as "an attacker needs to try all $2^{64}$ possibilities" (in case of a preimage attack).

What I've done so far
It's obvious, that compress(0, 0) == 0, so I could add as many 0-blocks as I want to the beginning of the message. This problem could be solved by using a different initial value.
It seems to be quite difficult to reverse the compression function, because it does 16 additions and 16 mixings, which creates quite a complex relationship and every bit of the input (current_block) can affect every bit of the output.
A general problem I thought of: Couldn't it happen, that we run into a loop? That would happen, if the result after the mixing in one round would be equals the starting value last. In this case, we would have quite a simple relationship as we need only to break one (or a few) mixing rounds. If this problem exists, I think it could be solved by adding a round constant (changing every round) in each round.

Questions I have
Does it make sense to have a compression function that uses 64-bit of the message to create an output of 64-bit? I see no problem with it, but I'm not sure about it as many common hash function use a much bigger message part to compress (MD5 does 512-bit => 128-bit).
Can we expect collisions with the same last-value, like compress(x, 0) == compress(x', 0) ?

• This sounds like a homework assignment. A general hint: Consider how current_block and last are combined - it's simple addition. The next two steps are mixing the state using a reversible operation (assuming << and >> are not cyclical, which they are not in the provided language). Sep 6, 2013 at 17:36
• As a trivial break, consider the 0 case. What obvious input hashes to 0? If you wanted to generate collisions for 0, how could you force the internal state to reach a value of 0? Sep 6, 2013 at 17:49
• So we know that compress(0, 0) = 0. Obviously, this can be iterated for an arbitrary number of blocks. Which of the hash properties can we use this fact to break? Sep 10, 2013 at 21:12
• Let's craft a less trivial collision. We can attack this general scheme, ignoring most of the details of compress. First, this is a Merkle–Damgård construction, so a collision for the compression function breaks the scheme. Note that compress is a permutation (16 rounds of a permutation): If you know the current_block that yielded a new value for last, you can run entire thing backward and get the original last that was updated by current_block. So let's model the for loop as a block cipher E(key, msg), using current_block as the key and last being encrypted/permuted.[...] Sep 11, 2013 at 7:56
• This question appears to be off-topic because it does not comply with our policy about homework. It does not show prior research or any research effort. It is just a "Please solve my homework for me", with a plain problem copied out of a textbook/homework problem.
– D.W.
Sep 12, 2013 at 21:13

2 Answers

This hash function has a 64-bit output. Therefore, it is not collision-resistant. It is easy to find a collision in any hash function with a 64-bit output. Since this appears to be a homework, I'm going to leave it to you to figure out why this is the case.

In general, please don't just post a homework question and expect us to solve it for you. We're not here to solve your homework for you. Instead, the expectation on this site is that you will show us in detail what you've tried and how far you've gotten, and explain where you got stuck. Then we might be able to help get you unstuck. But just posting the problem description from your homework, nothing more, and expecting us to hand you the solution on a platter is not what this site is for. This isn't a "solve-your-homework-for-you" site.

• Agreed on the second paragraph, but regarding the first paragraph, I think the point was to use some form of cryptanalysis to defeat this particular hash function, and not just invoke a generic attack. But yeah, no effort shown at all. Sep 12, 2013 at 23:17
• @Thomas: I nailed that cryptanalytic attack!
– fgrieu
Aug 23, 2015 at 17:07

When the lower 63 bits of current_block are 0 (that is, for current_block either $0$ or $2^{63}$), the step
last += current_block is the same as last ^= current_block, and all operations in compress are linear. Otherwise said each bit of the output of compress is a function that reduces to the XOR of some of the input bits. We express this as a boolean matrix of 64 rows (one per output) and 65 columns (the 64 inputs last, and the high bit of current_block).

We now consider the output of compress after hashing 65 blocks each with the lower 63 bits forced to 0, with 65 iterations of compress starting from some initial state. This function is linear, so collisions of two vectors of 65 blocks for any particular initial state (which are bound to exist by the pigeonhole principle) apply to all initial states, and all aligned locations in a message hashed using an iteration of compress.

We express said linear function for initial state zero, as a boolean matrix of 64 rows (one per output) and 65 column (the high order bits of the 65 input blocks). Computing all preimages, if any, reduces to solving a small linear system. We then find collisions by finding second preimages.

The attack extends to words of any width, with cost polynomial (of degree three) in the number of bits.