Gitorious should use CRC128 / 256 / 512 instead of SHA-1

Hi,

Currently GIT only supports cryptographic hashes for its commit tags.

That means:

1) It's very difficult to edit the history without also recomputing the 
hash tags for all commits after the needed change-point, which then 
means references to a repository is broken.

2) Only a single bit error in the main repository can break everything!

3) Illicit contents may be present in binary blobs, which in the future 
may be need to be removed without warrant and the only way to do that is 
by rebasing and force pushing, which will break "everything". It can be 
everything from child-porn to expired distribution licenses.

Many people think that bit errors cannot happen because the memory uses ECC and the file system uses cryptographic hashes to verify the integrity of the data. But what many people forget about is that when copying data from memory to disk, typically using a DMA channel data is copied w/o any kind of integrity protection, because the integrity protection is not end-to-end. The integrity protection is only per-link.

Therefore I propose the following changes to GIT.

1) Use a CRC128 / 256 or 512 non-cryptographic based hashing algorithm 
as default.

2) Add support for a CRC fixup field, which usually is zero, but when 
merges are needed, it can be non-zero, to allow the hash-tag-value to 
remain the same! This also allows for easy conversion of existing GIT 
repositories to the new scheme.

3) All git objects should be uncompressed.

CRC-XXX can easily be used to correct multiple bit errors without any performance overhead.

Please CC me. I'm not subscribed to this list.

--HPS

On Fri, Jan 13, 2023 at 01:59:44PM +0100, Hans Petter Selasky wrote:

[...]

https://github.com/git/git/blob/9bf691b78cf906751e65d65ba0c6ffdcd9a5a12c/Documentation/technical/hash-function-transition.txt

It's not clear why are you referring to Gitorious in your mail's subject and then talk about Git.

On 1/13/23 14:30, Konstantin Khomoutov wrote:

Hi,

I thought that Git was short for Gitorious? My bad.

The document you refer to really highlights my concerns, that a strong cryptographic hash algorithm is the highway to hell.

Do _not_ use a cryptographic hash for Git. Use plain good old CRC hashes.

Just imagine the consequences of finding child porn inside a 10-year old firmware binary blob in the Linux kernel. Will you just ignore it, or will you fix it?

That's why I say, that it must be possible to forge the hashes by default.

--HPS

On January 13, 2023 8:40 AM, Hans Petter Selasky wrote:

I do not understand the goal of this request. If it is possible to forge hashes, then nothing in a git repository can ever be trusted. Signed content will no longer be verifiable. The whole Merkel Tree representing the commit history becomes easily corruptible by hackers and no upstream remote repository can ever be trusted - or someone's own if someone targets a repo with malware that rewrites hashes. Imagine a scenario when malware replaces a blob in a repo and then forges the hash to pretend that the replacement never occurred. Using git as a supply chain audit trail becomes impossible. This is a potential vector for ransomware invading the git ecosystem. This seems like a really fatal path to take for the product.

The advantage of how git functions is that it is possible to mirror or clone repositories, protecting from hardware errors. Repositories exist in distributed form, so there may be hundreds or thousands of copies in case someone's copy is corrupted by a disk or memory write error - so that takes hash reconstruction out of the requirement set. If the git architecture was based on a central repository model only, then this might be a reasonable request, but that is not how git works. If, for instance, a main GitHub repo is somehow corrupted, it can be repaired by a push --force or a clone from a different instance.

Unless I am missing your point. --Randall

On 1/13/23 15:21, rsbecker@nexbridge.com wrote:

Hi,

If a hacker replaces a blob, everyone on the project will see it, because such changes typically generate a commit e-mail. And then an action will be made to revoke the access of that hacker. Now a clever hacker wouldn't do that. A clever hacker would just flip one bit somewhere in a random blob, looking like a hardware fault, and then force the project to rewind to backups every day, because the repository can no longer be verified.

There is no advantage from protecting from hardware errors, unless you can recover from them! Cryptographic hash algorithms are not suitable to recover bits. They only tell data is OK or NOK, and if there is no backup, you loose it! It is no solution for big repositories to rewind to backups just because of bit-flips. Such problems should be fixed w/o the need to roll-back, because that stops the entire production!

 > it can be repaired by a push --force

Hobby projects can do that, but not big projects like FreeBSD and the Linux kernel.

Yes, a little bit :-)

--HPS

On Fri, Jan 13, 2023 at 03:42:48PM +0100, Hans Petter Selasky wrote:

I don't think you have a very clear picture of how git works.

That's not how it works at all. If there is a corrupted object, the admins of the repository just put the correct object into place either from a backup or from another copy of the repository. There is no rewinding required.

This is true about all digital media.

No it doesn't.

Sure they can, but not due to missing objects (a corrupted object is just a missing object). If, for some reason, Linus ever needs to remove something from linux.git, he will do it and just give a heads-up why and for what reason.

I think you're misunderstanding some of the core principles of git.

-K

On 1/13/23 16:45, Konstantin Ryabitsev wrote:

Maybe, I'm usually commandering git via the terminal.

But if you say you can already edit stuff, why does the commit hash need to be cryptographic? I don't get that part. Yeah, I think of git commits like blockchain.

--HPS

On January 13, 2023 10:50 AM, Hans Petter Selasky wrote:

git is using SHA1/SHA256 (which happen to be coincidentally cryptographic) as message digests with a very low probability of collisions when the hashes are computed. There is never a situation, implied by cryptography, where there is a decode of a git hash.  In order to make git a blockchain, you would need to implement central signing authorities, which would require a fork if the signature mechanism changes. The signature mechanism (SSH, GPG) is distinct from hash computation in git's trees, but depends on hash integrity.

On 1/13/23 16:56, rsbecker@nexbridge.com wrote:

I see.

But at the same time any unique enough hash, identifies a specific piece of code or checkout, even though it is not under a specific signing authority. And that is the problem, that authorities may distribute allowed-only-hashes for their hardware ...

--HPS

On 1/13/23 16:45, Konstantin Ryabitsev wrote:

This gotta be a joke.

There are 46K forks of Linus Torvalds Linux kernel on GitHUB, and if Linus Torvalds one day decides to do a forced push, it will for sure be a disaster!

--HPS

On Fri, Jan 13, 2023 at 04:54:39PM +0100, Hans Petter Selasky wrote:

No it won't, and I speak from some position of authority on this subject (I'm responsible for git.kernel.org).

If Linus has to alter the history of linux.git, it will for sure be an extraordinary event -- it's never happened yet. However, it will be widely publicised, the reasons for it will be made clear, and everyone will just accept it and move on.

Git history edits occur all the time. Most tooling expects this to occasionally happen and deals with it correctly.

-K

On 1/13/23 17:02, Konstantin Ryabitsev wrote:

OK, if you say so. Though in my mind 46K rebases of millions of commits seem a lot overhead.

However, if history can be edited anyway, why do you need the cryptographic hash algorithm. Why not use a non-cryptographic one?

What's the point? Only so that one party can stay in control?

--HPS

On 1/13/23 17:06, Hans Petter Selasky wrote:

Let me phrase it like this:

You clearly believe in the zero-trust principle. I don't.

Why can't git support both beliefs, and it can be configurable somehow then?

--HPS

On Fri, Jan 13, 2023 at 05:18:40PM +0100, Hans Petter Selasky wrote:

I'm not sure what you mean here, but git is certainly not zero-trust. When you clone linux.git from git.kernel.org, you're very much trusting that:

- I (or members of my team) didn't mess with the repository
- Linus (or someone who hacked his laptop) didn't mess with the repository

Git is tamper-evident, not tamper-proof, so by definition it cannot be zero-trust.

Well, git is literally built on the concept of unique hashes. It's not possible to make this bit configurable, as it would be a totally different project with entirely different internals.

Not saying such framework doesn't have a reason to exist, but it's not something that can be built on top of git.

-K

On 1/13/23 17:36, Konstantin Ryabitsev wrote:

Hi,

By using a cryptographic hash algorithm, the goal is to avoid tampering you say, like tampering on the internet, ISP, cache node and so on. To me that's clearly a zero-trust thought. You don't trust the guy(s) that put down the infrastructure, neither those that provide that local cache for the GIT repository, only the master repository. SHA-1 gives a certain confidence, that if you checkout XXXXXXX, then you get a likely expected result with reduced possibility of tampering.

Anyone could intercept a CRC protected blob and re-compute the hash and send it on. But not a SHA-1 one.

I on the other hand trust the guys that put down the internet and are providing the cache nodes for GIT.

It's two different world views.

--HPS

On Fri, Jan 13, 2023 at 05:44:03PM +0100, Hans Petter Selasky wrote:

I admit, I never trust the "guys who put down the internet," so that's a very scary scenario to me (and I would say to pretty much everyone else on this list).

Indeed, werenotalike.gif :)

-K

On 1/13/23 17:49, Konstantin Ryabitsev wrote:

OK, I have no problem about that.

Thanks for the discussion.

--HPS

On Fri, Jan 13, 2023 at 05:06:57PM +0100, Hans Petter Selasky wrote:

Not to discourage you, but you seem to be making statements without a good understanding of how git works. If there is a history rewrite (even one that for some reason goes back millions of commits) all hash calculations will happen exactly once -- on the system of the person who's rewriting the history. After they push it, it's just a bunch of objects that everyone else merely downloads.

The answer is, unhelpfully, "because that's how git works." Every commit is a standalone object that references the previous commit, plus includes hashes of all trees, and those include hashes of all blobs. SHA-1 was picked because of its speed and the fact that it guarantees an extremely low potential for collisions (even better with SHA256). As a side-effect, it's easy to calculate the integrity of the entire tree, including its history, by verifying its hashes (this is what git fsck does).

Hashes aren't really "cryptographic" anyway (they just happen to be used all over the place in cryptography). It's really just a one-way function to reduce content of arbitrary size to a set of bytes of a determined size (and give a relatively high assurance of it being collision-free).

-K

On 1/13/23 17:27, Konstantin Ryabitsev wrote:

Same thing can be said for CRC-XXX. Just some magic CPU instructions and we're good. You don't even need a library.

--HPS

On 1/13/23 17:27, Konstantin Ryabitsev wrote:

If you used CRC, you would not need that, because CRC calculations are "concatenatable", while SHA-1's are not. CRC would just need the first and the last hash, and then you would apply the "difference".

--HPS

On Fri, Jan 13, 2023 at 05:35:57PM +0100, Hans Petter Selasky wrote:

It doesn't matter how it works behind the scenes as long as the produced hash is not unique (and CRC gives you no assurance of being unique). Git is built on the concept that every object has a unique hash. If this is no longer true, then it's literally no longer git, but is something else.

Since we're discussing this on the git list, it's not really a discussion worth having here.

-K

On 1/13/23 17:41, Konstantin Ryabitsev wrote:

That's why I say you need a fixup field, in case of collisions. CRC is used plenty all over the place and has good entropy.

--HPS

On 1/13/23 15:21, rsbecker@nexbridge.com wrote:

Hi,

As a long time open sourcer and hacker, I'm totally against signing software. Is the GIT project going to build the new infrastructure for John-Deers new tractor firmware adventure? It is totally against the values of open source craftmanship.

I don't think any of you crypto-enthusiasts understand how propritary companies use signed software to keep their power intact.

That's also an argument for using a non-crypto hash.

--HPS

On 13/01/2023 14:21, rsbecker@nexbridge.com wrote:

I'd agree about the core need for 'absolute' integrity checking.

However we have been here before, but without a way forward.

It was the "Subject: [TOPIC 3/17] Obliterate" at Git Contributor Summit, Los Angeles (April 5, 2020). https://lore.kernel.org/git/5B2FEA46-A12F-4DE7-A184-E8856EF66248@jramsay.com.au/

Discussion at https://docs.google.com/document/d/15a_MPnKaEPbC92a4jhprlHvkyirDh2CtTtgOxNbnIbA/edit#heading=h.wljwyo3r1m6l

The core need I think HPS is referring to is that need to 'obliterate' some blob (which contains the en-mass data), and perhaps some trees, commits and tags, which may also hold objectionable meta data, at least from reference repositories, and at the same time authenticate (if that's the right term) the list of such obliterated objects.

It will be a difficult task to carefully cut the fog of misdirection and scares in this arena.

It's one of those problem statements whose answer is "42".

The supply chain audit is (would be) a real problem if the presence of a specific hash is a punishable criminal offence. I suspect it already is in some jurisdictions.

The law works in mysterious ways it's wonderful ways to demonstrate ;-) Possession of certain artefacts can be a problem, so it is something that is worth careful consideration. We shouldn't let the 'distribution of criminal artefacts' be something 'guaranteed' by Git, despite careful users.

The forced replacement of 'redacted' material is already a problem in other domains. We should be able to manage a redaction list for a repository that needs it.

All that said, CRC isn't any sort of solution!

-- Philip

On Fri, Jan 13, 2023 at 02:39:37PM +0100, Hans Petter Selasky wrote:

How do you expect something like this would happen? A much more likely scenario would be someone contributing a binary blob that doesn't actually allow redistribution, and therefore would need to be purged from the repository.

When something like this happens, everyone is given a heads-up, the history is rewritten, and everyone moves on. It's a fairly routine procedure -- ask anyone who's ever committed an API key into their repo.

Git supports history edits and everyone lives with it just fine -- I think you are under the impression that git is some kind of globally distributed blockchain where any history edit requires a consensus fork. It's not at all the case.

-K

On Fri, Jan 13, 2023 at 02:39:37PM +0100, Hans Petter Selasky wrote:

[...]

[...]

No, unless you're late to the Git party ;-) Old-timers do remember Gitorious as a software project [1] which is closely related to Git but was a totally separate project.

  1. https://en.wikipedia.org/wiki/Gitorious