Poseidon hash collision

Cryptography
1

Hi,

during testing I noticed that there are hash collision in Poseidon due
to the padding.
Specifically I noticed that the Poseidon hashes of [Field(23)] and
[Field(23), Field(0)] are the same.
[‍], [Field(0)] and [Field(0), Field(0)] also have the same hash value.
[Field(0), Field(0), Field(0)] however has a different hash value.

As poseidon itself is collision resistent
(https://www.poseidon-hash.info/) and also the o1js documentation on
Poseidon does not mention that there are collisions (the SHA256
documentation also recommends to use Poseidon without menitioning that
there are collisions), I expect that a collision in the hash function
is a severe security vulnerability.

In case you think this is the expected behaviour, I think it should at
least be documented a lot better and more prominent.

The issues seems to be due to the padding in update in poseidon.ts.
A solution could be to pad with the length of the message or always
append a Field(1) and only then pad with Field(0) at the end, similar
to how padding in SHA works
(https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf).
However the resulting hash function would obviously be different.

example code:

const h23 = Poseidon.hash([Field(23)])
const h23_0 = Poseidon.hash([Field(23), Field(0)])
console.log(`h23:   ${h23}`)
console.log(`h23_0: ${h23_0}`)
const he = Poseidon.hash([])
const h0 = Poseidon.hash([Field(0)])
const h0_0 = Poseidon.hash([Field(0), Field(0)])
const h0_0_0 = Poseidon.hash([Field(0), Field(0), Field(0)])
console.log(`he     : ${he}`)
console.log(`h0     : ${h0}`)
console.log(`he0_0  : ${h0_0}`)
console.log(`he0_0_0: ${h0_0_0}`)

I tried to contact security@o1labs.org about this, however the mail-address does not exist. I tried to contact contact@o1labs.org about that, however didn’t get an answer.

1 Like
2

The usages of poseidon in o1js circuits are always fixed length. As such, there are no collisions.
In the general use.

This is good to call out in the documentation though, I’ve opened an issue here.

2 Likes
3

You can use poseidon with variable length using the recursion, so there certainly are collisions.
This may not be the usual way to use poseidon, but it can definitely be used that way.

1 Like
4

I built a smart contract with Mina

available here PinSave/packages/mina/src/NFTsMapContract.ts at 503300a6d6395c1478ed4f9fe6c02a2c224e382c · PinSaveDAO/PinSave · GitHub

In my case, I have used Field(0) to denote that the state is empty.

I think you are essentially adding nothing to an array.

Thats very similar to 23 + 0 = 23 and 23=23

Here is a very basic use of Fields:

console.log(Field(1).add(Field(1)).toJSON()); returns us 2

5

In the Auditing Report by Veridise this has now also been noted as V-O1J-VUL-036: Non-injective padding for hash functions.
I fully support their recommendation