Git – One way hash (not for crypto/security), use SHA256 (not MD5, SHA-1)

githashmd5sconssha256

On a new system, we require a one-way-hash to compute a digital signature from binary input (e.g., a kilobyte of text, or larger text-and-binary files). The need is similar to how Scons (build system) hashes command-lines and source files, and how Git (version control system) hashes files to compute a signature for storage/synchronization.

Recall that Scons uses MD5, and Git uses SHA-1.

While MD5 and SHA-1 have been "broken", neither Scons nor Git are using their hashes specifically for security (e.g., it's not to store passwords), so general practice still considers those algorithms acceptable for that usage. (Of course, this is partially a rationalization due to legacy adoption.)

QUESTION: Would you use SHA256 (not MD5 nor SHA-1) for a (non-crypto/security) one-way hash in a new system?

The concerns are:

MD5 and SHA-1 have a long history of adoption
SHA256 is relatively new (not as much history), but
seems to be currently recommended for new work (but
"stronger" algorithm strength is not
specifically required for my
application)
SHA256 is more time-expensive to
compute
SHA256 produces a longer key (these
will be used as dir/file names, and
stored within index files), but I
suppose I could truncate the
produced key (hash is less strong,
but should be sufficient), or just assume storage is cheap and file systems can handle it.

I'd be particularly interested in an answer consistent with the Scons or Git communities saying, "We'll keep ours forever!" or "We want to move to a new hash as soon as practical!" (I'm not sure what their plans are?)

Best Answer

Yes, I would use SHA-256. SHA-256 had a lot more than security purposes in mind; in fact one of the reasons that SHA1 needed to be replaced was for the very reason you need a hash function. A hash algorithm produces a finite site output; while having an undetermined amount of input. Eventually there will be a collision. The larger the output; the less likely of a collision (when using a proper hash algorithm).

Git went with SHA1 because they use it as file names; and they wanted it to be small and compact. SHA256 produces a much larger digest; consuming more disk space and more data to transmit over the wire. This question specifically addresses what would happen if git were to encounter collisions.

To look at your points:

SHA256 has been in the wild long enough that if there were problems; we should have seen them by now.
It isn't "stronger" per-se, it's less likely to produce a collision (if that is your criteria for stronger; then yes it is stronger).
SHA-256 is slower; yes. Much slower? Depends on what your needs are. For 95% of people; it's performance is acceptable assuming you're using a proper implementation.
In general, truncating the hash of SHA2 is an okay thing to do.

How do you create a new project/repository?

A git repository is simply a directory containing a special .git directory.

This is different from "centralised" version-control systems (like subversion), where a "repository" is hosted on a remote server, which you checkout into a "working copy" directory. With git, your working copy is the repository.

Simply run git init in the directory which contains the files you wish to track.

For example,

cd ~/code/project001/
git init

This creates a .git (hidden) folder in the current directory.

To make a new project, run git init with an additional argument (the name of the directory to be created):

git init project002

(This is equivalent to: mkdir project002 && cd project002 && git init)

To check if the current current path is within a git repository, simply run git status - if it's not a repository, it will report "fatal: Not a git repository"

You could also list the .git directory, and check it contains files/directories similar to the following:

$ ls .git
HEAD         config       hooks/       objects/
branches/    description  info/        refs/

If for whatever reason you wish to "de-git" a repository (you wish to stop using git to track that project). Simply remove the .git directory at the base level of the repository.

cd ~/code/project001/
rm -rf .git/

Caution: This will destroy all revision history, all your tags, everything git has done. It will not touch the "current" files (the files you can currently see), but previous changes, deleted files and so on will be unrecoverable!

Git workflow and rebase vs merge questions

TL;DR

A git rebase workflow does not protect you from people who are bad at conflict resolution or people who are used to a SVN workflow, like suggested in Avoiding Git Disasters: A Gory Story. It only makes conflict resolution more tedious for them and makes it harder to recover from bad conflict resolution. Instead, use diff3 so that it's not so difficult in the first place.

Rebase workflow is not better for conflict resolution!

I am very pro-rebase for cleaning up history. However if I ever hit a conflict, I immediately abort the rebase and do a merge instead! It really kills me that people are recommending a rebase workflow as a better alternative to a merge workflow for conflict resolution (which is exactly what this question was about).

If it goes "all to hell" during a merge, it will go "all to hell" during a rebase, and potentially a lot more hell too! Here's why:

Reason #1: Resolve conflicts once, instead of once for each commit

When you rebase instead of merge, you will have to perform conflict resolution up to as many times as you have commits to rebase, for the same conflict!

Real scenario

I branch off of master to refactor a complicated method in a branch. My refactoring work is comprised of 15 commits total as I work to refactor it and get code reviews. Part of my refactoring involves fixing the mixed tabs and spaces that were present in master before. This is necessary, but unfortunately it will conflict with any change made afterward to this method in master. Sure enough, while I'm working on this method, someone makes a simple, legitimate change to the same method in the master branch that should be merged in with my changes.

When it's time to merge my branch back with master, I have two options:

git merge: I get a conflict. I see the change they made to master and merge it in with (the final product of) my branch. Done.

git rebase: I get a conflict with my first commit. I resolve the conflict and continue the rebase. I get a conflict with my second commit. I resolve the conflict and continue the rebase. I get a conflict with my third commit. I resolve the conflict and continue the rebase. I get a conflict with my fourth commit. I resolve the conflict and continue the rebase. I get a conflict with my fifth commit. I resolve the conflict and continue the rebase. I get a conflict with my sixth commit. I resolve the conflict and continue the rebase. I get a conflict with my seventh commit. I resolve the conflict and continue the rebase. I get a conflict with my eighth commit. I resolve the conflict and continue the rebase. I get a conflict with my ninth commit. I resolve the conflict and continue the rebase. I get a conflict with my tenth commit. I resolve the conflict and continue the rebase. I get a conflict with my eleventh commit. I resolve the conflict and continue the rebase. I get a conflict with my twelfth commit. I resolve the conflict and continue the rebase. I get a conflict with my thirteenth commit. I resolve the conflict and continue the rebase. I get a conflict with my fourteenth commit. I resolve the conflict and continue the rebase. I get a conflict with my fifteenth commit. I resolve the conflict and continue the rebase.

You have got to be kidding me if this is your preferred workflow. All it takes is a whitespace fix that conflicts with one change made on master, and every commit will conflict and must be resolved. And this is a simple scenario with only a whitespace conflict. Heaven forbid you have a real conflict involving major code changes across files and have to resolve that multiple times.

With all the extra conflict resolution you need to do, it just increases the possibility that you will make a mistake. But mistakes are fine in git since you can undo, right? Except of course...

Reason #2: With rebase, there is no undo!

I think we can all agree that conflict resolution can be difficult, and also that some people are very bad at it. It can be very prone to mistakes, which why it's so great that git makes it easy to undo!

When you merge a branch, git creates a merge commit that can be discarded or amended if the conflict resolution goes poorly. Even if you have already pushed the bad merge commit to the public/authoritative repo, you can use git revert to undo the changes introduced by the merge and redo the merge correctly in a new merge commit.

When you rebase a branch, in the likely event that conflict resolution is done wrong, you're screwed. Every commit now contains the bad merge, and you can't just redo the rebase*. At best, you have to go back and amend each of the affected commits. Not fun.

After a rebase, it's impossible to determine what was originally part of the commits and what was introduced as a result of bad conflict resolution.

_{*It can be possible to undo a rebase if you can dig the old refs out of git's internal logs, or if you create a third branch that points to the last commit before rebasing.}

Take the hell out of conflict resolution: use diff3

Take this conflict for example:

<<<<<<< HEAD
TextMessage.send(:include_timestamp => true)
=======
EmailMessage.send(:include_timestamp => false)
>>>>>>> feature-branch

Looking at the conflict, it's impossible to tell what each branch changed or what its intent was. This is the biggest reason in my opinion why conflict resolution is confusing and hard.

diff3 to the rescue!

git config --global merge.conflictstyle diff3

When you use the diff3, each new conflict will have a 3rd section, the merged common ancestor.

<<<<<<< HEAD
TextMessage.send(:include_timestamp => true)
||||||| merged common ancestor
EmailMessage.send(:include_timestamp => true)
=======
EmailMessage.send(:include_timestamp => false)
>>>>>>> feature-branch

First examine the merged common ancestor. Then compare each side to determine each branch's intent. You can see that HEAD changed EmailMessage to TextMessage. Its intent is to change the class used to TextMessage, passing the same parameters. You can also see that feature-branch's intent is to pass false instead of true for the :include_timestamp option. To merge these changes, combine the intent of both:

TextMessage.send(:include_timestamp => false)

In general:

Compare the common ancestor with each branch, and determine which branch has the simplest change
Apply that simple change to the other branch's version of the code, so that it contains both the simpler and the more complex change
Remove all the sections of conflict code other than the one that you just merged the changes together into

Alternate: Resolve by manually applying the branch's changes

Finally, some conflicts are terrible to understand even with diff3. This happens especially when diff finds lines in common that are not semantically common (eg. both branches happened to have a blank line at the same place!). For example, one branch changes the indentation of the body of a class or reorders similar methods. In these cases, a better resolution strategy can be to examine the change from either side of the merge and manually apply the diff to the other file.

Let's look at how we might resolve a conflict in a scenario where merging origin/feature1 where lib/message.rb conflicts.

Decide whether our currently checked out branch (HEAD, or --ours) or the branch we're merging (origin/feature1, or --theirs) is a simpler change to apply. Using diff with triple dot (git diff a...b) shows the changes that happened on b since its last divergence from a, or in other words, compare the common ancestor of a and b with b.
```
git diff HEAD...origin/feature1 -- lib/message.rb # show the change in feature1
git diff origin/feature1...HEAD -- lib/message.rb # show the change in our branch
```

Check out the more complicated version of the file. This will remove all conflict markers and use the side you choose.

git checkout --ours -- lib/message.rb   # if our branch's change is more complicated
git checkout --theirs -- lib/message.rb # if origin/feature1's change is more complicated

With the complicated change checked out, pull up the diff of the simpler change (see step 1). Apply each change from this diff to the conflicting file.