Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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) ?

share|improve this question
1  
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
1  
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
1  
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
2  
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
3  
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
show 6 more comments

1 Answer 1

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.

share|improve this answer
1  
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. –  Thomas Sep 12 '13 at 23:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.