# Break a simple compression function of a cryptographic hash function

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). –  B-Con Sep 6 '13 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? –  B-Con Sep 6 '13 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? –  B-Con Sep 10 '13 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.[...] –  B-Con Sep 11 '13 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 '13 at 21:13