BUG CEP-19: Different directory trees may end up with the same hash value

[hunger]

Checklist

• I added a descriptive title
• I searched open reports and couldn't find a duplicate

What happened?

I have set up two different directory trees:

|-- testdata1
|   `-- testFhello-world
`-- testdata2
    |-- test
    `-- world

Using the python script from CEP-19 to hash these two trees, they both have the same hash value:

CEP19 hash of testdata1: e91a9f9adcb3561a7a78a04d6f33b391beb92491f9ed99663b455867b031d30a
CEP19 hash of testdata2: e91a9f9adcb3561a7a78a04d6f33b391beb92491f9ed99663b455867b031d30a

The file name testFhello-world in testdata1 is added to the hash stream and is indistinguishable from a file name test with contents hello followed by a file world with whatever contents testFhello-world has. This is not the only way to confuse the algorithm: You can also use the contents of files to "pretend" there are more files.

One way to stop these filesystem trees from having the same hash value is to add the length of the input. You can do that either by hashing the length as an integer of a defined bit length or "stringified" followed by a separator like :. The separator is needed after a stringified value as without it the user provided contents may change that length by starting with digits. That might allow for another way to confuse the algorithm.

cep-19-fail.tar.gz has the script from CEP19 and the two directories so you can try for yourself.

Additional Context

No response

[jaimergp]

I guess you mean:

|-- testdata1
|   `-- testFhello-world
`-- testdata2
    |-- test
    `-- hello-world

One way to stop these filesystem trees from having the same hash value is to add the length of the input.

What about simply adding the length of the filename to the separator?

Anyway, thank you for the report! I am not aware of any wide usage of this algorithm so we can simply amend CEP 19 with a PR. Would you mind opening one with the proposed corrections and I'll review? Thanks!

[pb01ka]

Hi @jaimergp. Since I am already working on similar topic in rattler-build - prefix-dev/rattler-build#2483. So I will take up this issue as well.

Thank you.

[pb01ka]

I'd like to propose a fix to CEP-19.

The problem

The current CEP 19 algorithm builds the hash stream for each directory entry by concatenating raw bytes in this order:

<path_bytes> <type_marker> <content_bytes> <separator "-">

Because there is no field-length information, two structurally different directory trees can produce an identical byte stream whenever a filename happens to embed the same bytes used as type markers (F, D, L) or the entry separator (-).

Concrete example (as described in the OP):

• Tree 1: a single file named testFhello-world with content www
• Tree 2: a file named test (content hello) and a file named world (content www)

Both trees yield the byte stream testFhello-worldFwww-, and therefore the same digest - a true hash collision on structurally different directory trees.

Proposed fix: length-prefix every variable-length field

Prefix each variable-length field with its decimal byte length followed by : before feeding it to the hasher. This makes every field boundary unambiguous and eliminates the collision:

Field	Before	After
Path	<path_bytes>	<len>:<path_bytes>
Symlink target	<target_bytes>	<len>:<target_bytes>

The updated Python reference implementation would look like:

import hashlib
from pathlib import Path
from functools import partial

def contents_hash(directory: str, algorithm: str) -> str:
    hasher = hashlib.new(algorithm)
    for path in sorted(Path(directory).rglob("*")):
        rel = path.relative_to(directory).as_posix().replace("\\", "/")
        rel_bytes = rel.encode("utf-8")
        hasher.update(f"{len(rel_bytes)}:".encode("utf-8"))
        hasher.update(rel_bytes)
        if path.is_symlink():
            target = str(path.readlink()).replace("\\", "/")
            target_bytes = target.encode("utf-8")
            hasher.update(b"L")
            hasher.update(f"{len(target_bytes)}:".encode("utf-8"))
            hasher.update(target_bytes)
        elif path.is_dir():
            hasher.update(b"D")
        elif path.is_file():
            hasher.update(b"F")
            try:
                lines = []
                with open(path) as fh:
                    for line in fh:
                        lines.append(line.replace("\r\n", "\n"))
                for line in lines:
                    hasher.update(line.encode("utf-8"))
            except UnicodeDecodeError:
                with open(path, "rb") as fh:
                    for chunk in iter(partial(fh.read, 8192), b""):
                        hasher.update(chunk)
        else:
            raise RuntimeError(f"Unknown file type: {path}")
        hasher.update(b"-")
    return hasher.hexdigest()

With the same two trees from above:

• Tree 1: stream becomes 16:testFhello-worldFwww- - the 16: prefix makes clear the path is 16 bytes, so the F at byte 17 is unambiguously the type marker.
• Tree 2: stream becomes 4:testFhello5:worldFwww- - entirely different, no collision.

I have a working implementation of this fix in conda/conda-build#5992. I'd be happy to also draft a CEP amendment (or a new superseding CEP) to update the specification in CEP 19 accordingly.

Happy to hear thoughts from the steering council on the preferred path forward.

[jaimergp]

@conda/steering-council any thoughts on this issue? I think the fix is solid but the question remains: how do we approach this? Amend the CEP or create a new one? Do we need to vote on an amendment? Which one is clearer?

Thanks!

[jaimergp]

This was discussed in yesterday's community meeting. Consensus was to go for a new CEP that supersedes 19 so the algorithms producing different hash values are clearly identifiable and there's no confusion about which CEP 19 "edition" is being referred to.