# Swapping a single bit inside a 40 bytes inputs fed to keccak256. Is it safe to assume no change in the first 20 bytes can result in the same hash?

I have the following data (represented as hex from binary below) where the lower bytes is controlled by attacker in the second case :

0x00: 000000000000000000000000cf269986 ????????????????
0x10: da781407b0eeeac3ea79ac1c9d857d38 ?x???????y?????8
0x20: 00000000000000000000000000000000 ????????????????
0x30: 00000000000000000000000000000001 ????????????????
0x40: 00000000000000000000000000000000 ????????????????


which does 0x1350c327906a2da929ed2a625e133cdfc3aaa945d7540e93b1266293dd2c1d11.

0x00: 000000000000000000000000cf269986 ????????????????
0x10: da781407b0eeeac3ea79ac1c9d857d38 ?x???????y?????8
0x20: 00000000000000000000000000000000 ????????????????
0x30: 00000000000000000000000000000002 ????????????????
0x40: 00000000000000000000000000000000 ????????????????


which does 0xf11930e4cc6cdaaaa9da21243f512da3fba796ffa7c74870669af9cee3a06c0c. Because the use of 0x2 from 0x1 left shift a single bit by one (but both inputs keep the same length).

Even if the change is about a single byte, there’s no way to modify the first 20 bytes of the second case so the hash is equal to 0x1350c327906a2da929ed2a625e133cdfc3aaa945d7540e93b1266293dd2c1d11(the hash of first case) without requiring a computational power not available on the short term, right ?

There are no known attacks on SHA3 series that are faster than the generic attacks.

Your problem is the 2nd pre-image attack: given a message $$m_1$$ finding another message $$m_2$$ such that $$m_1 \neq m_2$$ and $$Hash(m_1)=Hash(m_2)$$.

SHA3-256 has $$2^{256}$$ 2nd preimage resistance.

Now, you only allow the attacker first 20-byte which is 160-bit of your data. The attacker must try to find the $$m'$$ if exist. He cannot brute-force the 160-bit space to execute the generic attack. That is not reachable, even 128-bit is not.

The bitcoin miners' latest SHA-256 hash rate peak was $$2^{66}$$ hashes per second and $$2^{83}$$ per day from 108464285TH/s on 29/09/2019.

Another question is: does this 2nd pre-image exist? With a negligible probability, no!

Even if the change is about a single byte,

We want the avalanche effect from the hash functions that is; a single bit flip should randomly flip the %50 percentage of output bits.

In general, if you want to find an attack into a good hash function you need some degree of freedom. What you are looking for is the reverse.

• Only the padding is changed. If there were a huge difference, Wikipedia will have a different page for KECCAK other than SHA3. – kelalaka Oct 15 '19 at 19:48
• What do you mean by single difference? On the output or in the 20-byte? – kelalaka Oct 15 '19 at 19:49
• single bit difference in the input. – user2284570 Oct 15 '19 at 19:49
• That should be almost impossible. You can try that and if you find you will be famous since you find a weakness in SHA3. We expect that SHA3 has the avalanche effect, so 1-bit change will randomly affect almost half of the output bits – kelalaka Oct 15 '19 at 19:50