hashbrown's support for borsh is unsound

[kayabaNerve]

borsh is a codec advertised for and frequently used in security-critical projects. One of the advertised features is "consistency", where an encoded object only has a single representation. The implementation here breaks that property by encoding via iteration over the HashMap and not in a consistent (sorted) order. This is proven by https://github.com/kayabaNerve/hashbrown-borsh-poc. Additionally, the decode function does not perform any checks on the order of the keys.

This also breaks the borsh specification for HashMap/HashSet types. This claim can be dismissed if it's argued hashbrown is a HashMap/HashSet yet is not a borsh HashMap/HashSet, yet I'll continue on the assumption that yes, they should be the same. Not only is the ordering broken, yet hashbrown serializes the hasher (not defined in the borsh spec, producing non-compliant encodings for any hashers of non-0-encoded-length) and uses a usize for the length. usize is not defined in the codec yet is serialized as a u64 by the Rust borsh crate. The codec specifies HashMap lengths should be u32s.

The inclusion of borsh was also flawed from a design standpoint as I noted here: #525 (comment). The Rust borsh crate already supported HashMap/HashSet. This makes borsh have a cyclic dependency (as even though they won't import hashbrown 0.15, their deps will now that those have updated to 0.15. I had to pin older deps for my PoC to build). It also is less featured as the borsh crate also supported HashSet yet only HashMap was supported here.

---

I submitted a responsible disclosure on the correctness issues on October 5th/6th. Amanieu informed me a few hours ago that they and Pietro (one of the two coordinators of the Rust security team) believe it's okay to discuss publicly, hence my creation of an issue documenting all of this. Ever since I raised hashbrown already had this functionality (without raising the correctness issues), the plan appears to be to remove this functionality (#570), mostly resolving this.

Considering this bug could come up in real-world patterns (canonical encodings can be relied on to prevent 'double-spends' in cryptocurrency and prevent consensus splits), I personally recommended yanking 0.15. That opinion has been disagreed with and I ack it's not my decision. I solely want my stance noted.

For examples, please see:

• https://www.asymmetric.re/blog/ghost-in-the-block-ethereum-consensus-vulnerability

A recent issue on Ethereum regarding non-canonical encodings.

• https://polkadot.com/blog/a-polkadot-postmortem-24-05-2021

A 2021 issue in the Polkadot ecosystem (which did cause their network to halt) due to differing results from Rust's binary_search_by function dependent on compiler version. While this is unrelated to HashMaps/codecs, it highlights how any inconsistent behavior can have notable impact.

[clarfonthey]

It's getting removed in next version anyway, so, it doesn't really matter. Instead borsh will offer its own implementation, most likely.

[cuviper]

I don't think we should yank without a semver-compatible replacement. If we really want to force the issue, there could be a 0.15.1 that (breakingly) removes borsh, so yanking 0.15.0 wouldn't affect anyone who didn't care about borsh in the first place. (e.g. indexmap v2.6.0 depending on hashbrown = "^0.15.0")

[clarfonthey]

That seems reasonable to me, yanking 0.15 and releasing 0.15.1 without it.

[kayabaNerve]

Corrected the issue title to better reflect Rust's terminology.

Instead borsh will offer its own implementation, most likely.

borsh already did. All that is needed is for borsh to expand its version range. If a 0.16 release is made, this would require two separate features, hashbrown-0.14 and hashbrown-0.16 (in order to exclude hashbrown 0.15 from the version range). If a 0.15.1 release is made, a single feature could be used on the premise no one pinned directly to 0.15.0.

[cuviper]

All that is needed is for borsh to expand its version range.

Note that this is also fraught, because it can only resolve to one specific version. A complicated dependency tree could have both hashbrown 0.14.x and 0.15.x in play, but borsh can only provide implementations for one of them, unless it explicitly lists separate dependencies. Even if you don't need both, it's also sometimes tricky to get cargo to resolve it to the one you wanted.

[Amanieu]

You can use the same trick rkyv did by making the feature names specific to a particular version: https://github.com/rkyv/rkyv/blob/739f53928d7c9c870b1d2072a9b73c80466f2a87/rkyv/Cargo.toml#L34

I'm also happy to just do a 0.15.1 release with the breaking change, if all the borsh users are OK with that.

[Amanieu]

To clarify my position: I'm not going to yank 0.15 unless we release a semver-compatible 0.15.1.

This leaves only 2 possibilities:

• Release 0.15.1 with a breaking change and yank 0.15.
• Release 0.16 with borsh removed and not yank 0.15.

[kayabaNerve]

if all the borsh users are OK with that

I personally am. I doubt it's been adopted, the 'fix' for anyone broken is simply moving the borsh feature from hashbrown to the hashbrown feature on borsh, and I doubt this feature has been adopted in the ~10 days it's been out. While a few notable crates have updated to 0.15, none of them rely on the borsh functionality.

[kayabaNerve]

Following up on 0.15.1 and/or 0.16 since #570 was merged. Is there an explicit step forward (such as polling for any usage of this feature since release) I can help with?

[Amanieu]

I did a github code search and nobody seems to be using the borsh feature of hashbrown. I will release 0.15.1 today.