Proof for collision resistance on a block-based hash

Question

I am designing an unkeyed hash based on the SIMON cipher. This is a follow up to “this” question. A quick summary: I have an ECC engine and the SIMON cipher in hardware, and it’s in an extremely power constrained environment. I want a hash generator for two reasons: 1) the ECC shared secret, and 2) if I want to verify a stream. I cannot use any of the other hash engines due to hardware constraints, which is mainly that they are huge and ruin my power budget, but because I already have a SIMON encryption block, I can modify that any way that I want.

I started by reading “chap9.pdf”, and a bunch of papers; however, I would like to blow holes in what I designed. I need to justify my use of this to myself because hardware is such and expensive proposition.

I took the SIMON 128/256 architecture that has a key expansion on 4, 64-bit words and then used that to create something that takes 128-bit in and puts 128-bits out. Just to make the problem tractable for this explanation, I will use SIMON 32/64 from here on as it has 4, 8-bit words.

The basic architecture is here:

I just keep feeding things into the lower two words via an XOR, which follows that Davies-Meyer and the Merkle style architectures.

In order to visualize this, I’ve generated the key expansion for a 64-bit input of all 0s for two runs through the hash engine:

In the image above, the result of feeding a stream of 0s into the hash for two hash rounds results in 0x5753c0fe. This means that 32-bits eventually results in 32-bits, and in the system I plan to implement 128-bit blocks eventually results in a 128-bit number.

Now, I can say everything that is wrong with this that I know of:

1. I cannot specify the length because this needs to be used as a stream, and I cannot guarantee how many blocks will go through it. For 2 blocks through it, I can find collisions. . This seems to be less of a problem as I make the stream inputs longer, but I could not find a formal proof for this.

2. I have a counter that exists to run the encryption hardware, and I could XOR against that on either the high or low word, but for 2 blocks, I can still find collisions.

Question: Is there a formal proof for length of stream input and collisions somewhere for a block-based, unkeyed cipher?

Answer 1

If I understand you correctly, you are using the Simon key expansion process, so that the input to your block is the 256 bit Simon key, and the output is the 256 bit last round key (and you're ignoring the Simon encryption process entirely).

If so, three nits:

• I believe that you can find preimages for your hash function in $O(2^{64})$ compression function evaluations. This happens because the key expansion process is invertible; that is, given a 256 bit output, you can find the corresponding 256 bit input. So, what an attacker would do is assume a 2 block message; he would:

  • Generate $2^{64}$ initial blocks, and compute the intermediate states from them.
  • Generate $2^{64}$ final states consisting of the target hash and $2^{64}$ different $K_i, K_{i+1}$ words, and compute the inverse key expansion
  • Look for a collision in the $K_{i+2}, K_{i+3}$ words; if you find one, this implies a preimage

  This is easy to fix; make the transform noninvertible.

• If you want your hash function to be collision resistant, you'll need to add some collision-free padding mechanism.

• This architecture is actually closer to a Sponge hash function than a Davies-Meyer type construction (just in case you're wondering)