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.
I just keep feeding things into the lower two words via an XOR, which follows that Davies-Meyer and the Merkle style architectures.
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:
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.
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?