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.

--HPS

On 2023-01-13 at 13:23:59, Hans Petter Selasky wrote:

This is intentional. Commit and tag signing requires an unbroken Merkle tree-like construction that prevents the history from being modified by signing a single commit or tag.

git fsck is designed to detect this, and by default it's run every time the repository is repacked (such as by git gc). But yes, this is a problem, and changing to an algorithm which isn't cryptographically secure won't change that. Prudent users back up data to prevent data loss.

This is a problem in every Merkle tree-like system. Most repositories have some sort of code review or access control that prevents people from generally pushing inappropriate content. For example, if somebody proposed to push any sort of pornography or other inappropriate content (e.g., a racist screed) to one of my repositories or one of my employer's, I'd refuse to approve or merge such a change, because that wouldn't be appropriate for the repository.

I don't feel this is enough of a problem that using a Merkle tree-like construction is a bad idea, given the benefits it offers.

As the person who wrote the SHA-256 support, I'm pleased to report that adding a new hash algorithm isn't very difficult anymore. The largest part of the work is updating all the tests. I've tried very hard to make this substantially easier for everyone.

However, Git is moving in the direction of stronger cryptographic algorithms, rather than insecure hashing algorithms. I don't think your proposal is a good idea, nor do I think it's likely to be adopted.

If it were adopted, the signing of commits and tags would be meaningless, and because it would be trivial to create collisions[0], there would clearly be some pairs of objects which could not be stored. This would make Git much less useful, and it might allow users to attempt to forge or replace content without being detected.

That being said, you are free to create your own fork of the code which does so, provided you comply with the terms of the license.

For the same reason as above, I don't think this is a good idea.

This would dramatically increase the size of most repositories. I've easily seen repositories where the uncompressed contents exceed 1 TB in size yet the repository is only double-digit gigabytes, if that. Most people will find the increase in disk usage unacceptable, and I'm certain that includes Git hosterse.

[0] CRC is linear and the following relations apply, which makes forgery trivial (see https://en.wikipedia.org/wiki/Cyclic_redundancy_check):

CRC(x XOR y) = CRC(x) XOR CRC(y) XOR c for some c CRC(x XOR y XOR z) = CRC(x) XOR CRC(y) XOR CRC(z)

"brian m. carlson" <sandals@crustytoothpaste.net> writes:

While I agree with the primary thrust of your argument, this one is a bit tricky to reason about. External rules change and can declare what has been accepted as appropriate inappropriate on a whim, long after you reviewed the material coming into your history and decided it was perfectly fine, under the then-prevailing definition of what is and isn't appropriate.

On Sun, 15 Jan 2023 at 01:05, brian m. carlson <sandals@crustytoothpaste.net> wrote:

[resend in plain text]

It isn't clear to me why this needs to be a problem at all. If the Merkele tree contains data later in its chain that says "replace Object X with Y", provided the replacement mechanism doesn't touch commit objects, only blobs, then you can replace files in the history with other files without altering the commit history.

Provided the toolchain validates that it has found a proper "replacement instruction" in the history, it should be possible to safely replace blobs without a full history rewrite.

The replacement mechanism could be structured so that you can only "nuke" a file, eg, replace it with a zero byte blob, making it somewhat less open to abuse, or it could allow arbitrary blobs to be mapped to each other. So long as the mapping data is in the commit history it should be as secure as the original mapping no? Git could be taught to warn the user "Checking out a rewritten blob X as Y, see 012deadbeef for the rewrite instruction." when it happened.

Again, provided this does not touch the *commit* tree, just raw blobs, I dont see why you can't have an object replacement facility. Am I missing something?

Yves

On 1/15/23 00:59, brian m. carlson wrote:

Yeah, right. And of course you have all the tools to decode those megabyte big firmware blobs from intel supporting wireless cards all over the place to see what is actually inside there, that they are not using some 3rd party code which licence will expire at some point, and then you need to remove those binaries.

--HPS

On 1/15/23 00:59, brian m. carlson wrote:

I disagree. There is no need for signing in a version control system. It just makes it harder to change things, like the right-to-repair. In my eyes there is a high chance of abuse, by vendors that do no want others to flash or edit their device firmwares.

--HPS

On January 16, 2023 2:24 AM, Hans Petter Selasky wrote:

The two matters are completely isolated and distinct. In the OpenSource community, anyone typically has the right to modify. Please refer to the GPLv3, ECLIPSE, and MIT licenses for example. Those are the governing documents that permit modification and define intellectual property rights. Please consult those licenses with regards to right-to-repair statements that have no legal bearing on git or any other GPL-governed software product. In my view, the issue raised is a red herring that keeps getting brought up, which does not contribute positively to this request's discussion, but would presumably would increase the hit rate on web searches, to which this reply unfortunately contributes.

The assertion of no need for signing can apply to a centralized version control system, like SVN, because users are authenticated centrally, and the contribution can be made definitive without a separate signature, providing no one with root authority on the server hacks the repository. In the architecture of a distributed version control system (specifically git for this discussion), there is no evidence of origin of changes because the commit identity is cooperative rather than being enforced by a central authority and hacking the repository by root is detectible. The assertion of signing as abuse of rights is also an opinion that, so far, has no supporting evidence given. Perhaps a paper in a refereed journal might give this position some credibility.

My point is that signing is critical in a DVCS and a major function point used by DevOps architects for adopting git in new organizations. In the regulated world, FinTech, FDA, Aviation, etc., signing contributes to the evidence of origin of changes required by PCI and SWIFT (ref: section 6 in each regulation). Without signed tags (which the establishes the change origins for releases for production use), deployment becomes less certain and less acceptable to the audit community with whom I interact on a regular basis.

--Randall

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

Hi,

The use of cryptographic hash tags, allows one party to stay in control of and monetize a project, actually by doing nothing more than rebranding an existing product.

 From what I've read the GPLv3 goes pretty far to also provide flashing 
rights for software, but what use is that, when flashing the unsigned 
software on your Samsung phone, for example, some fuse breaks in the 
hardware, and then you can no longer use certain apps on your phone?

It's very clear to me, that supporting signing straight off the VCS, will not help the opensource and right-to-repair community at all. It's just ripe for abuse, like I say.

Hacking is prevented by using a secure copy mechanism between the servers, which you can upgrade separately. You already see the problem, SHA-1 is not good enough to prevent hacking. Why not just separate the hacking preventing measures and the needs of a good VCS?

--HPS

Hans Petter Selasky <hps@selasky.org> writes:

It smells that you are conflating the signing of source material and the sealing of tivoized hardware that use cryptographic signature to tell what binaries are allowed to run on it.

The signing implemented by the software we the Git development community build is not about the latter. The source used to build binaries for your tivoized hardware can come from a VCS that is deliberately designed to allow object name collisions, and your build would just be locked out the same unless you have the signing key that pleases the hardware. Use of Git there would not make the story any different, I am afraid.

Hello,

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

That also makes it difficult to alter the repository intentionally without anyone noticing. With SHA1 being somewhat weak it may be possible to alter repository content although I am not aware of any practical attacks shown so far. For that reason using stronger hashes is planned in the future.

It's good to avoid spam getting into your repository. If you really need to alter it long into the past you still can. Everyone will notice that you did, and that's an intentional feature. In some situations it is understandably an annoyance but there's so much you can do. At least tags should remain stable.

So long as all links have integrity protection it's end-to-end.

Integrity checks for CPU chaches, buses, and IO protocols do exist.

It's not that errors cannot happen, they are very unlikely.

In the very rare case that such error happens so long as non-corrupted version of the object can be supplied by anyone who has a copy of the repository it is recoverable.

For old objects this should be your backup system.

For new objects the worst case is that the history is rolled back so the missing object is not needed.

Thanks

Michal

On 1/15/23 14:53, Michal Suchánek wrote:

 >

 >

Hi Michael,

You clearly don't see what this is about! Only if the same CRC mechanism is end-to-end, you don't have any good integrity mechanism at all!

Let me try to explain what this is about in very simple words. Because memcpy() does not copy the ECC CRC values along with the data, it is an unsafe memory copy mechanism, which may introduce bit-errors without noticing. It does not help to only have ECC RAM or for that sake protect the PCI links.

--HPS

On Mon, Jan 16, 2023 at 08:17:58AM +0100, Hans Petter Selasky wrote:

The ECC protects against 1bit errors - so long as only 1 bit is flipped along that path it is corrected.

If you have bigger errors ECC can sometimes detect them and your system crashes or whatever, and sometimes they go unnoticed.

It does not make sense to copy around that CRC. It is used to recover the corrupted bit, and when that data is copied to a new location a new CRC is calculated that can detect an error in that location. Copying that checksum around would only accumulate the errors.

Of course, that assumes that the corruption happens only in the cheaper external long-term storage, and data does not get corrupted as it goes through your CPU where it is stored only a few CPU cycles at a time. It is mostly the case but when you need extreme reliability system-level schemes that mitigate this possibility do exist.

Thanks

Michal

On 1/16/23 10:13, Michal Suchánek wrote:

Yes, that is correct, but what is "copying data"? Are you saying that copying data is always error free?

--HPS

On January 16, 2023 4:56 AM, Hans Petter Selasky wrote:

Not in all possible computing devices, no. But in certain high-reliability and mission critical systems, there are parity checks and communication mechanisms that verify the integrity of data transfers memory-to-memory, memory-to-register, and over inter-CPU bus, and memory-to-disk-storage checks. The result of a corruption on one of my systems would result in a CPU halt rather than blindly accepting the result, taking the faulty processor offline until the cause is investigated and then reloaded or repaired. This applies to any component, including disks, CLIMs, DMA, and anything else in the architecture.

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

Hi,

I doesn't matter if the system is high-reliability or not. The problem is exactly the same.

If you have a CPU register which you add to another CPU register, then you need to recompute the parity information on the destination CPU register. That basically means you always trust the output of the CPU adder. There is simply no relationship between input parity and output parity in the linear adder case.

Whenever "parity" information is lost, it opens up the possiblity of irrecoverable errors.

That's why I say, that GIT would be better of in that regard with an end-to-end, CRC parity mechanism.

--HPS

On Mon, Jan 16, 2023 at 10:55:34AM +0100, Hans Petter Selasky wrote:

Maybe you should not cut out the answer to your qestion?

Thanks

Michal