[postcard-schema] Key hash calculation could suffer collision if path and schema alias

[jamesmunns]

Described in jamesmunns/postcard-spec-ng#1 (comment),

Since some of the schema primes fall in the ascii range (and really, many other values could fall in the utf-8 range), it could be possible to get a collision between two Keys, for example since b'e' is the prime used for bytearray, the following two would alias:

("car", (bytearray, bytearray))
("care", (bytearray))

We should consider this to the next breaking change in postcard-schema and postcard-rpc.

Right now in postcard-rpc, this will lead to a compilation failure, as it would detect the two keys collide.

CC @DavidBuchanan314 who discovered this, and @max-heller for thoughts.

[jamesmunns]

One proposed fix for this is adding a value to be hashed between the two, ideally something that is NEITHER valid utf-8 NOR a valid schema item. We could potentially hash a fragment that is invalid utf-8, and also not a valid schema prime identifier.

[DavidBuchanan314]

Another mitigation could be to length-prefix the path

[jamesmunns]

Oh that's a good call. I also meant to make a note that we accept an empty path string, which probably isn't great for some reason I can't think of right now.

[max-heller]

Length-prefixing seems like a good solution.

we accept an empty path string, which probably isn't great for some reason I can't think of right now.

I'll note that I use empty paths

[jamesmunns]

One thing to note about length prefixing: we might need to pick a max length (e.g. u16, u32, u64), or commit to using varint encoding (varint(usize)) for the length. Basically, this is a note to not just blindly use usize as the length and hash the to_le_bytes form.

[thaodt]

One thing to note about length prefixing: we might need to pick a max length (e.g. u16, u32, u64), or commit to using varint encoding (varint(usize)) for the length. Basically, this is a note to not just blindly use usize as the length and hash the to_le_bytes form.

I'd like to go with using varint encoding for length prefixing. Fixed length can waste space for small values (e.g., u32 uses 4 bytes to store "testing" despite its 7-byte length).

[jamesmunns]

@thaodt this is for the key hashing, so we wouldn't store this anywhere. It would just be fed into the hasher. TYPICALLY this would only be done at a compile time anyway. The issue is: we need all systems to agree on the input to the hashing process, so for the length of "testing", that could either be [0x07] (varint), [0x07, 0x00, 0x00, 0x00] (u32), or [0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00] (u64).

In all cases, the output hash will be the same size, and that is what is stored. It's just about how many bytes we feed into the hasher.