Hacker News Reader

Comment by kpcyrd | Hacker News Reader

Please educate yourself what a merkle tree is. It's a well understood building block of various security systems, including certificate transparency (which explicitly uses sha256).

You refer to PGP signed Git objects, but you also argue:

> Git hashes are not supposed to be a security mechanism

Guess what the Git PGP signature is signing.

View on HN

This is exactly right. A signature is only worth as much as the hash that it’s signing. And all the usual signature algorithms are signing a hash.

I tried to spelunk this thread and couldn't find the topic I want to see explored.

I don't really have the crypto chops to declare a fact here, but I have a speculation or intuition. In this day of supply chain worries, I think a proper signing algorithm should not be signing this tower of hashes, or not just this tower.

It should incorporate a canonical stream of all the actual commit content. It is the integrity of this content from the author's working copy that they can and should attest, not some derived byproduct of the storage scheme. Edit: Of course, I mean a secure hash of this stream, not a signature including a copy of the entire content!

My intuition is that the content-addressable store is used to reconstitute the commit content, but the verification should be over the original content, not the internal addressing of the store.

Wouldn't this make it harder to do these exploits? You would have to find alternate content that simultaneously produces collisions in the internal addressing hashes and for the overall canonical stream hash.

If you also carry size info alongside each hash, would this also make it much more difficult to produce useful collisions?

The GPG signature is not signing the git hash, if that's what you mean.

The GPG signature signs some kind of hash calculated over the commit, minus the GPG header, which is thereby added.

The git hash is then calculated over the whole thing. The git hash is on the outside, and not part of the signing.

> The GPG signature is not signing the git hash, if that's what you mean.

It kind of is - it’s signing the hash of the tree object, which is the actual thing that you’d attack with a hash collision

The actual thing you'd attack with a hash collision is the blob object, not the tree object, right? The tree object has a rigid structure and git will throw a fit if you add non-functional data to modify its hash. Source code files have comments which make it much easier to manipulate the hash.

you're right, i worded that poorly. what i meant to imply was that a blob hash collision causes any tree referencing it to be malicious, which cascades down to many different commits/tags (potentially all of them, if the tree is untouched since repo creation).

Maybe you could make a valid tree object with the same hash and different content; the details about which graph node at which level is used as a target do not seem that important.

I understand that if we sign a commit with the help of some arbitrarily strong hash, it doesn't protect the parent commit(s). The integrity of the SHA-1 hash references to the parent commits is not in question, but the authenticity of those commits themselves.

No, not the abstract tree formed by a series of commits.

The actual git ‘tree’ object, which is the thing a commit actually points to, referenced by a hash in the commit. That is signed by the GPG signature.

Correct. The content of the git `tree` is partially controlled by the attacker because filenames in the repository are part of it. So if it's feasible to manufacture a generic hash collision it MAY (not MUST) be feasible to generate two colliding `tree` objects.

That doesn't make a difference: with sha1 a malicious change in content will still result in the same content hash, so the signature will still be valid, and the commit hash will still be the same.

Only if the GPG signing process stupidly relies on the SHA-1 hash. I.e. if it takes an unsigned commit and signs only its SHA-1 hash and then creates a new commit with GPG headers. If that's how it works, that is massively stupid and can be fixed without forcing SHA-256 as a git hash. Just have the signing calculate its own digest for its own purposes.

That digest can be the SHA-256; since the infrastructure is there for it, signing should use SHA-256 regardless of what hash is used by the repository for identifying and linking content.

  > if it takes an unsigned commit and signs only its SHA-1 hash and then creates a new commit with GPG headers

It does indeed. The bytes passed to GPG when constructing a signed commit look something like:

  tree eebfed94e75e7760540d1485c740902590a00332
  parent 04b871796dc0420f8e7561a895b52484b701d51a
  author Alice <alice@example.com> 1465981137 +0000
  committer Alice <alice@example.com> 1465981137 +0000

  Headline

  Message

where the contents being signed are entirely represented by the oids of the tree object and parent commit object. This string is very similar to the content that is fed to the hash function to produce a normal git commit object id.

Haha, well that is a screw up. The weak tree hash can be attacked, replacing the content that is itself not pulled into GPG.

The "bytes passed to GPG" of course get hashed by GPG, using something better than SHA-1.

All bytes that comprise the commit should be hashed by GPG, rather than depending on the content referencing hash in the object tracking system.

This is something that is possible; it is not a logically deductive necessity that we just scan the topmost object and trust the hashes it contains.

> it is not a logically deductive necessity that we just scan the topmost object and trust the hashes it contains.

It kind of is. Otherwise the whole idea of signing a commit with a backing git history (rather than just a snapshot of a working directory) collapses. The only guarantee you have that the git history is what is claimed by the cryptographic signature is some sort of Merkle tree structure. Either the original one, or you have to construct a whole new parallel one with a better hash, in which case, as I bring up in a cousin comment, why not just use a better hash in your original one?

In a git repo based on SHA-1 hashes, it would be good enough that the meaning of a commit signature is that the content of the commit is attested, not the parents.

Parent commits can have their own signatures, and it's true that there is an attack possible there where the same parent hash could point to two different commits, that have valid signatures of some kind (possibly from the same sneaky developer who is a bona fide project member).

Be that as it may, it's perfectly okay for the signature on a banana to validate only the banana, and not the gorilla that is holding it, or the vine the gorilla is swinging on, and the whole jungle.

It would be worth it to have better quality commit signing for SHA-1-based repos.

> it would be good enough that the meaning of a commit signature is that the content of the commit is attested, not the parents.

This is a significant degradation of the implicit guarantees given by a cryptographic signature, to the point that basically all personal use cases I have for signed commits would be invalidated.

Keep in mind that git does not have diffs as first-class objects. Every commit is just a snapshot of some state of the working directory. That means that without attesting to the integrity of the parents of a commit, the only thing a commit X signed by a person A says is "at some point on A's computer, the state of the repo looked like X".

Almost all the relevant questions I would want to ask are not answered by this. E.g. there is a malicious function F that is present in X. Did A write it? Don't know. Did someone else write it? Can't know for certain. Who introduced a certain feature? Don't know. Did A sign off on a new bugfix? Don't know.

All you know is that at some point the codebase looked like X on A's computer. A might not have made any relevant changes at all!

You can only back out a diff and therefore actually attribute a change to someone (either explicitly through `git blame` or informally by looking at git logs) if you have attestation of the parents.

The Merkle tree structure of git repos is interwoven through basically ever useful thing git does. Without cryptographic signatures implicitly carrying a promise of validity for that structure, this would make commit signing useless (depending on just how broken SHA-1 is) for the needs of any org I've ever worked at.

In a SHA-1-based git repo, if a signature were to digest all the bits spanned by a commit, that would be a monotonic improvement over what is done now, even if it falls short of some people's expectations.

Because now, commit X signed by person A does not even attest that the repo looked like X on A's computer, or not very well, due to weaknesses in the hash.

Have you ever worked with large repositories? You really don't want to read every single byte from disk just for signing a commit if you can avoid it.

Then use a SHA256-based repo, and use the cheaper signing scheme.

For some people, an improved signing scheme over the SHA-1-linked repository format would meet their requirements based on their assessment of their security threats.

> Then use a SHA256-based repo, and use the cheaper signing scheme.

The scheme you just called a "screw up"?

> If that's how it works, that is massively stupid and can be fixed without forcing SHA-256 as a git hash.

I don't think it's massively stupid. Unless you want to re-hash the entire Merkle tree structure to sign your commit, you basically have to trust the hashes in the Merkle tree (or have a separate parallel Merkle tree) at some point in what you sign, which means you do have to trust the SHA-1 hashes. Otherwise even with a cryptographic signature you can always spoof at least the git repo history (e.g. even if you try to directly hash the entire contents of the current commit).

Re-hashing the entire Merkle tree structure seems prohibitively expensive to generate (even with a lot of caching) and pretty complicated for e.g. verifying a signature. Or you can do that incrementally, but then you're just generating a whole new parallel Merkle tree structure.

Regardless, at the end of the day, you need to trust the integrity of the Merkle tree structure. And you can either do that by trusting the hashes of the current Merkle tree, or you have to completely recreate a new one with more trustworthy hashes, in which case why not just use better hashes in your original tree?

I need a commit signature to only attest the integrity and authenticity of that commit, nothing else; no parent or grandparent, etc.

Sure, "just" completely change how git commit signatures work to avoid having to replace a compromised hash function...

But that is a less disruptive change, because it's managed in headers; it's not part of the core of how objects are linked together.

You just have new header fields (or values for existing fields) which indicate that this is such and such a new style signature, and that's mostly it. Older git won't validate it or produce it. Newer git validates and produces old and new.

Importantly, older git installations will be able to read the commits, etc, just not validate the signatures.

This is not to avoid replacing the compromised hash function as such (taking away the choice from people making new git projects). We have that already.

But existing repos aren't based on that new function. Not everyone wants to switch their existing repos to to start using SHA-256; that means the repos don't work with older git.

The disruption is real.

Reply on news.ycombinator.com