Git and SHA-1 security (again)

Dear List Members, Git Developers,

I would like to discuss an old topic from 2006. I understand it was
already discussed. The only reason i'm sending this e-mail is to talk
about a possible solution which didn't show up on this list before.

I think we all understand that SHA-1 is broken. It still works perfect
as a storage key, but it's not cryptographically secure anymore. Git
is not moving away from SHA-1 because it would break too many
projects, and cryptographic security is not needed but git if you have
your own repository.

However I would like to show some big problems caused by SHA-1:
 - Git signed tags and signed commits are cryptographically insecure,
they're useless at the moment.
 - Git Torrent (https://github.com/cjb/GitTorrent) is also
cryptographically broken, however it would be an awesome experiment.
 - Linus said: "You only need to know the SHA-1 of the top of your
tree, and if you know that, you can trust your tree." That's not true
anymore. You have to trust your computer, you servers, your git
provider in a way that no-one can maliciously modify your data.

I understand that git is perfect for a work flow, where you have your
very own repository and you double-check any commits or diffs you
accepting to it. But that's not everybody's work flow. For example: if
I want to blindly trust my college, I could just include all commits
he signed without review. Currently I can't do that. There are
workarounds of course: signing the e-mail he sends me, or signing the
entire git repository's tarball, etc... But that's not the right way
to do things.

As a final thought on this, I would like to say: Git is a great tool,
but it can be so much better with a safe hash.


I would like to propose a solution for changing git's hash algorithm:
It would be a breaking change, bit I think it can be done pretty
painless. (If you read the discussion back in 2006 the problems of
moving are clear.)

In git, every data has to have one and only one key - so a hybrid hash
is a no-go. That means changing hash algo involves re-hashing every
data in a git repository, but it's not that bad. On a git clone, we
actually re-hash everything to check integrity. Changing all the keys
shouldn't be worth than that.

But - and that's the main idea i'm writing here - changing the storage
keys does not mean you should drop your old hashes out. If you change
the git data structure in a way, that it can keep multiple hashes for
the same "link" in each objects (trees, commits, etc) you can keep the
old ones right next to the new one. If you want to look up the
referenced object, you must use the newest hash - which is the key.
But if you want to verify some old hash, it's still possible! Just
look up the objects by the new key, remove all the newer generation
keys, and verify the old hash on that.

A storage structure like this would allow a very great flexibility:
 - You can change your hash algorithm in the future. If SHA-256
becomes broken, it's not a problem. Just re-hash the storage, and
append the new hashes the git objects.
 - You can still verify your old hashes after a hash change - removing
the new hashes from the objects before hashing should give you back
the old objects, thus giving you the same hash as before.
 - That makes possible for signed tags, and commits to keep their
validity after hash change! With a clever-enough new format, you can
even keep the validity of current hashes and signs. (To be able to do
that, you should be able to calculate back the current format from the
new format.)

Moving git forward to a format like this would solve the weak-key
problem in git forever. You would be able to configure your key algo
on a per repository basis, you - and git - can do the daily work on
the newest hashes, while still carrying the old hashes and signatures,
in case you ever want to verify them. That would allow repositories to
gracefully change hashes in case they need to, and to only
compatibility limitation is that you must use a new enough git to
understand the new storage format.

What are your thoughts on this approach? Will git ever reach a release
with exchangeable hash algorithm? Or should someone look for
alternatives if there's a need for cryptographic security?

Thank you for your time reading this.

References:
SHA-256 discussion in 2006:
http://www.gelato.unsw.edu.au/archives/git/0608/26446.html
Discussion about git signatures in 2014
https://www.mail-archive.com/git%40vger.kernel.org/msg61087.html
Linus's talk on git
https://www.youtube.com/watch?v=4XpnKHJAok8&t=56m20s

Kind regards,
Zsolt Herczeg

On Sat, Jul 16, 2016 at 03:48:49PM +0200, Herczeg Zsolt wrote:

But - and that's the main idea i'm writing here - changing the storage
keys does not mean you should drop your old hashes out. If you change
the git data structure in a way, that it can keep multiple hashes for
the same "link" in each objects (trees, commits, etc) you can keep the
old ones right next to the new one. If you want to look up the
referenced object, you must use the newest hash - which is the key.
But if you want to verify some old hash, it's still possible! Just
look up the objects by the new key, remove all the newer generation
keys, and verify the old hash on that.

A storage structure like this would allow a very great flexibility:
 - You can change your hash algorithm in the future. If SHA-256
becomes broken, it's not a problem. Just re-hash the storage, and
append the new hashes the git objects.
 - You can still verify your old hashes after a hash change - removing
the new hashes from the objects before hashing should give you back
the old objects, thus giving you the same hash as before.
 - That makes possible for signed tags, and commits to keep their
validity after hash change! With a clever-enough new format, you can
even keep the validity of current hashes and signs. (To be able to do
that, you should be able to calculate back the current format from the
new format.)

Moving git forward to a format like this would solve the weak-key
problem in git forever. You would be able to configure your key algo
on a per repository basis, you - and git - can do the daily work on
the newest hashes, while still carrying the old hashes and signatures,
in case you ever want to verify them. That would allow repositories to
gracefully change hashes in case they need to, and to only
compatibility limitation is that you must use a new enough git to
understand the new storage format.

What are your thoughts on this approach? Will git ever reach a release
with exchangeable hash algorithm? Or should someone look for
alternatives if there's a need for cryptographic security?

I'm working on adding new hash algorithm support in Git.  However, it
requires a significant refactor of the code base.  My current plan is
not to implement side-by-side data, for a couple reasons.

One is that it requires significantly more work to implement and
complicates the code.  It's also incompatible with all the refactoring
I've done already.

The second is that it requires that Git have the ability to store
multiple hashes at once, which is very expensive in terms of memory.
Moving from a 160-bit hash to a 256-bit hash (my current plan is
SHA3-256) requires 1.6× the memory.  Storing both requires 2.6× the
memory.  If you add a third hash, it requires even more.  Memory is
often a constraint with using Git.

The current plan is to use git-fast-import and git-fast-export to handle
that conversion process, and then maybe provide wrappers to make it more
transparent.

Currently the process of the refactor is ongoing, but it is a free time
activity for me.

If you'd like to follow the progress roughly, you can do so by checking
the output of the following commands:

  git grep 'unsigned char.*20' | wc -l
  git grep 'struct object_id' | wc -l

You are also welcome to contribute, of course.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

Dear Brian,

Thank you for your response. It very good to hear that changing the
hash is on the git project's list. I haven't found any official
communication on that topic since 2006.
I'll look into the contributions guide and the source codes, to check
if I can contribute to this transition. If you have any documentation
or other related info, please point me towards it.

Thanks,
Zsolt Herczeg


2016-07-16 22:13 GMT+02:00 brian m. carlson [off-list ref]:

On Sat, Jul 16, 2016 at 03:48:49PM +0200, Herczeg Zsolt wrote:

quoted

But - and that's the main idea i'm writing here - changing the storage
keys does not mean you should drop your old hashes out. If you change
the git data structure in a way, that it can keep multiple hashes for
the same "link" in each objects (trees, commits, etc) you can keep the
old ones right next to the new one. If you want to look up the
referenced object, you must use the newest hash - which is the key.
But if you want to verify some old hash, it's still possible! Just
look up the objects by the new key, remove all the newer generation
keys, and verify the old hash on that.

A storage structure like this would allow a very great flexibility:
 - You can change your hash algorithm in the future. If SHA-256
becomes broken, it's not a problem. Just re-hash the storage, and
append the new hashes the git objects.
 - You can still verify your old hashes after a hash change - removing
the new hashes from the objects before hashing should give you back
the old objects, thus giving you the same hash as before.
 - That makes possible for signed tags, and commits to keep their
validity after hash change! With a clever-enough new format, you can
even keep the validity of current hashes and signs. (To be able to do
that, you should be able to calculate back the current format from the
new format.)

Moving git forward to a format like this would solve the weak-key
problem in git forever. You would be able to configure your key algo
on a per repository basis, you - and git - can do the daily work on
the newest hashes, while still carrying the old hashes and signatures,
in case you ever want to verify them. That would allow repositories to
gracefully change hashes in case they need to, and to only
compatibility limitation is that you must use a new enough git to
understand the new storage format.

What are your thoughts on this approach? Will git ever reach a release
with exchangeable hash algorithm? Or should someone look for
alternatives if there's a need for cryptographic security?

I'm working on adding new hash algorithm support in Git.  However, it
requires a significant refactor of the code base.  My current plan is
not to implement side-by-side data, for a couple reasons.

One is that it requires significantly more work to implement and
complicates the code.  It's also incompatible with all the refactoring
I've done already.

The second is that it requires that Git have the ability to store
multiple hashes at once, which is very expensive in terms of memory.
Moving from a 160-bit hash to a 256-bit hash (my current plan is
SHA3-256) requires 1.6× the memory.  Storing both requires 2.6× the
memory.  If you add a third hash, it requires even more.  Memory is
often a constraint with using Git.

The current plan is to use git-fast-import and git-fast-export to handle
that conversion process, and then maybe provide wrappers to make it more
transparent.

Currently the process of the refactor is ongoing, but it is a free time
activity for me.

If you'd like to follow the progress roughly, you can do so by checking
the output of the following commands:

  git grep 'unsigned char.*20' | wc -l
  git grep 'struct object_id' | wc -l

You are also welcome to contribute, of course.
--
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

On Sat, Jul 16, 2016 at 11:46:06PM +0200, Herczeg Zsolt wrote:

Dear Brian,

Thank you for your response. It very good to hear that changing the
hash is on the git project's list. I haven't found any official
communication on that topic since 2006.

There's been some recent discussion on the list about it.  It is less on
the Git project's list and more on my personal list.  It's my hope that
Junio and other contributors will decide to accept my patches when they
are ready.  Also, the plan is to keep SHA-1 available, probably as the
default, for backwards compatibility.

I'll look into the contributions guide and the source codes, to check
if I can contribute to this transition. If you have any documentation
or other related info, please point me towards it.

The major work at this point is turning instances of unsigned char [20]
into struct object_id, as well as converting hardcoded 20 and 40 (and
derivative values) to GIT_SHA1_RAWSZ and GIT_SHA1_HEXSZ.  This work
allows us to make as little code as possible know about the size of the
hash, as well as generally being easier to maintain.

You can look at the bc/cocci branch which was recently merged into next.
(It doesn't exist independently outside of next, so you'll have to
search through the history).  That work is what in my branches is called
object-id-part4.  I'm currently working on getting to the point of
converting get_tree_entry to use struct object_id, which is what will
become my object-id-part5.

I recommend if you're planning on doing some of this work that you try
to avoid areas which are under work by other developers, especially the
refs code, which is undergoing massive changes.  Other people will
appreciate it.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

Hi Brian,

On Sat, 16 Jul 2016, brian m. carlson wrote:

My current plan is not to implement side-by-side data, for a couple
reasons.

I am as guilty as the next person to have use the "deafbee(This is my
commit, 2007-08-21)" format to refer to older commits. So I do have
concerns about rewriting history when switching to a new hash.

I understand the technical challenges, of course.

Out of curiosity: have you considered something like padding the SHA-1s
with, say 0xa1, to the size of the new hash and using that padding to
distinguish between old vs new hash?

I guess that it would also possible to introduce an opt-in "legacy mapper"
which would generate a mapping locally of all objects' SHA-1 to whatever
new hash you choose. Generating it locally would side-step the security
issues of the SHA-1 algorithm. We would need to teach Git to pick that
mapping up if available and use it, of course.

However, that latter solution would do nothing to address the problem of
existing GPG-signed commits.

Ciao,
Dscho

On Sun, Jul 17, 2016 at 10:01:38AM +0200, Johannes Schindelin wrote:

Out of curiosity: have you considered something like padding the SHA-1s
with, say 0xa1, to the size of the new hash and using that padding to
distinguish between old vs new hash?

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.  I was going to zero-pad, however.  I was also, at
least at first, going to force a separate .git dir for those, to avoid
having to try to store two separate types of objects in the same repo.

The other limitation with this is that it isn't immediately obvious what
hash is in use just because it has a certain length.  For example, I
plan on implementing SHA3-256, but it's also possible I might add
BLAKE2b-256 for people for whom SHA3-256 is too slow.  There's no way to
distinguish between those two algorithms.  Thus allowing multiple hashes
in the same repo won't work without a format byte.

What I might do, however, is add multihash-style format information to
the on-disk format for non-SHA-1 repos.  Then SHA-1 compatibility could
come in a future iteration.  That would be compatible with the existing
refactor.

I guess that it would also possible to introduce an opt-in "legacy mapper"
which would generate a mapping locally of all objects' SHA-1 to whatever
new hash you choose. Generating it locally would side-step the security
issues of the SHA-1 algorithm. We would need to teach Git to pick that
mapping up if available and use it, of course.

I think that might be easier.  Considering the number of tests that
hard-code object names, I might need that for the testsuite.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

On Sun, Jul 17, 2016 at 4:21 PM, brian m. carlson
[off-list ref] wrote:

On Sun, Jul 17, 2016 at 10:01:38AM +0200, Johannes Schindelin wrote:

quoted

Out of curiosity: have you considered something like padding the SHA-1s
with, say 0xa1, to the size of the new hash and using that padding to
distinguish between old vs new hash?

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.  I was going to zero-pad, however.  I was also, at
least at first, going to force a separate .git dir for those, to avoid
having to try to store two separate types of objects in the same repo.

If it's just the external hash representation, can we go with a prefix
<algo><colon> to identify the hash algorithm? For example
sha256:1234... is SHA-256 while 1235... by default is SHA-1 (but we
could switch the default to SHA-256 via config file later SHA-1 is
dead and nobody wants to type sha256: every time). It catches
incorrect hash algorithm references.
-- 
Duy

On Sun, Jul 17, 2016 at 05:19:02PM +0200, Duy Nguyen wrote:

On Sun, Jul 17, 2016 at 4:21 PM, brian m. carlson
[off-list ref] wrote:

quoted

On Sun, Jul 17, 2016 at 10:01:38AM +0200, Johannes Schindelin wrote:

quoted

Out of curiosity: have you considered something like padding the SHA-1s
with, say 0xa1, to the size of the new hash and using that padding to
distinguish between old vs new hash?

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.  I was going to zero-pad, however.  I was also, at
least at first, going to force a separate .git dir for those, to avoid
having to try to store two separate types of objects in the same repo.

If it's just the external hash representation, can we go with a prefix
<algo><colon> to identify the hash algorithm? For example
sha256:1234... is SHA-256 while 1235... by default is SHA-1 (but we
could switch the default to SHA-256 via config file later SHA-1 is
dead and nobody wants to type sha256: every time). It catches
incorrect hash algorithm references.

I'd make it such that the default is that of the repo.  If the current
repo is generating SHA-256, say, then 473a0f4 refers to the empty blob.
If you want to refer to an SHA-1 object, then you write sha-1:e69de29.

On disk, multihash[0] seems like the right way to go.  We'd serialize
references to the SHA-1 and SHA-256 empty blobs as
1114e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 and
1220473a0f4c3be8a93681a267e3b1e9a7dcda1185436fe141f7749120a303721813
respectively.  This makes parsing significantly easier.  On disk, we
could write them into the object database as 1114e6/9de2… and
122047/3a0f….

We could implement the default hash algorithm as extensions.hash and the
on-disk format (which would be a requirement for extensions.hash) as
extensions.explicitHash.

As I said, I'm not planning on multiple hash support at first, but it
doesn't appear impossible if we go this route.  We might still have to
rewrite objects, but we can verify signatures over the legacy SHA-1
objects by forcing them into the old-style object format.

[0] https://github.com/jbenet/multihash
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

On Sun, Jul 17, 2016 at 03:42:34PM +0000, brian m. carlson wrote:

As I said, I'm not planning on multiple hash support at first, but it
doesn't appear impossible if we go this route.  We might still have to
rewrite objects, but we can verify signatures over the legacy SHA-1
objects by forcing them into the old-style object format.

How hard would it be to make the on-disk format be multihash, even if
there is no support for anything other than a single hash, at least
for now?  That way we won't have to rewrite the objects twice.

Personally, so long as the newer versions of the tree are secured, I
wouldn't mind if the older commits stayed using SHA1 only.  The newer
commits are the ones that are most important and security-critical
anyway.  It seems like the main reason to rewrite all of the objects
is to simplify the initial rollout of a newer hash algorithm, no?

		     	   		   - Ted

On Sun, Jul 17, 2016 at 12:23:49PM -0400, Theodore Ts'o wrote:

On Sun, Jul 17, 2016 at 03:42:34PM +0000, brian m. carlson wrote:

quoted

As I said, I'm not planning on multiple hash support at first, but it
doesn't appear impossible if we go this route.  We might still have to
rewrite objects, but we can verify signatures over the legacy SHA-1
objects by forcing them into the old-style object format.

How hard would it be to make the on-disk format be multihash, even if
there is no support for anything other than a single hash, at least
for now?  That way we won't have to rewrite the objects twice.

Other than the amount of work to change reading from the on-disk format,
nothing prevents us from doing that, although I would recommend storing
the object database with the tag prefix if we do so (i.e., instead of
.git/objects/17, writing .git/objects/111417).  That future-proofs us
for when we change the hash.

I will say that the pack format will likely require some changes,
because it assumes things are 4-byte aligned.  It also assumes you can
use the object ID in the mmaped pack directly (4-byte aligned), which
you can no longer do.  We have some cases where we cast that memory
directly to struct object_id, which will no longer be valid, and even if
we add the two prefix bytes to struct object_id, that doesn't guarantee
that struct won't be aligned differently.

We could require that the pack format have two NUL bytes before the
hash, which would force it to be aligned.  We'd still have to make the
Git protocol negotiate the new extension and fail gracefully if the
version is too old.  We could do this by requiring a pack version 5,
which would simply cause older Gits to report errors.

It's a lot of work, and it's definitely a flag day.  That's why I had
planned to only do it with a new hash format: it would impact only
people who were moving to the new hash.  It also means that we get to
work out any problems with the design at that point and not be committed
to a design that might be inadequate.  This is a place where I don't
want to mess up.

Personally, so long as the newer versions of the tree are secured, I
wouldn't mind if the older commits stayed using SHA1 only.  The newer
commits are the ones that are most important and security-critical
anyway.  It seems like the main reason to rewrite all of the objects
is to simplify the initial rollout of a newer hash algorithm, no?

The reason is that we can't have an unambiguous parse of the current
objects if two hash algorithms are in use.  tree objects don't use a hex
encoding of hashes; they use a binary encoding.  It's therefore possible
to create an ambiguous tree representation.

So when we look at a new hash, we need to provide an unambiguous way to
know what hash is in use.  The two choices are to either require all
object use the new hash, or to extend the objects to include the hash.
Until a couple days ago, I had planned to do the former.  I had not even
considered using a multihash approach due to the complexity.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

Hi Brian,

On Sun, 17 Jul 2016, brian m. carlson wrote:

On Sun, Jul 17, 2016 at 10:01:38AM +0200, Johannes Schindelin wrote:

quoted

Out of curiosity: have you considered something like padding the SHA-1s
with, say 0xa1, to the size of the new hash and using that padding to
distinguish between old vs new hash?

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.  I was going to zero-pad, however.

I thought about zero-padding, but there are plenty of
is_null_sha1()/is_null_oid() calls around. Of course, I assumed
left-padding. But you may have thought of right-padding instead? That
would make short name handling much easier, too.

FWIW it never crossed my mind to allow different same-sized hash
algorithms. So I never thought we'd need a way to distinguish, say,
BLAKE2b-256 from SHA-256.

Is there a good reason to add the maintenance burden of several 256-bit
hash algorithms, apart from speed (which in my mind should decide which
one to use, always, rather than letting the user choose)? It would also
complicate transport even further, let alone subtree merges from
differently-hashed repositories.

Ciao,
Dscho

On Sat, Jul 16, 2016 at 3:48 PM, Herczeg Zsolt [off-list ref] wrote:

I would like to discuss an old topic from 2006. I understand it was
already discussed. The only reason i'm sending this e-mail is to talk
about a possible solution which didn't show up on this list before.

You mention the 2006 discussion, but I wonder if you've read the more
recent discussion from April on the subject.

I think we all understand that SHA-1 is broken. It still works perfect
as a storage key, but it's not cryptographically secure anymore. Git
is not moving away from SHA-1 because it would break too many
projects, and cryptographic security is not needed but git if you have
your own repository.

However I would like to show some big problems caused by SHA-1:
 - Git signed tags and signed commits are cryptographically insecure,
they're useless at the moment.
 - Git Torrent (https://github.com/cjb/GitTorrent) is also
cryptographically broken, however it would be an awesome experiment.
 - Linus said: "You only need to know the SHA-1 of the top of your
tree, and if you know that, you can trust your tree." That's not true
anymore. You have to trust your computer, you servers, your git
provider in a way that no-one can maliciously modify your data.

In particular, as far as I know and as Theodore Ts'o's post describes
better than I could[1], you seem to be confusing preimage attacks with
collision attacks, and then concluding that because SHA1 is vulnerable
to collision attacks that use-cases that would need a preimage attack
to be compromised (which as far is I can tell, includes all your
examples) are also "broken".

1. http://thread.gmane.org/gmane.comp.version-control.git/291305/focus=291511

On Sun, Jul 17, 2016 at 4:21 PM, brian m. carlson
[off-list ref] wrote:

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.

Or even the other way around, main repo is one with sha1 while
submodule is on sha256. I wonder if we should address this separately
(and even in parallel with sha256 support), making submodules work
with an any external VCS system (that supports some basic operations
we define).
-- 
Duy

In particular, as far as I know and as Theodore Ts'o's post describes
better than I could[1], you seem to be confusing preimage attacks with
collision attacks, and then concluding that because SHA1 is vulnerable
to collision attacks that use-cases that would need a preimage attack
to be compromised (which as far is I can tell, includes all your
examples) are also "broken".

I understand the differences between the collision and preimage
attacks. A collision attack is not that bad for git in a typical
use-case. But I think that it's important to note that there are many
use-cases which do need a hash safe from collision attack. Some
examples:

You maintain a repository with gittorrent with signed commits Others
can use these signatures to verify it's original. Let's say you
include some safe file (potentially binary) from a third-party
contributor. That would be fine if the hash algo is safe. Currently
there is the possibility that you received a (safe) file which was
made to collide with another malicious one. Once you committed (and
signed) that file, the attacker joins the gittorrent network and
starts to distribute the malicious file. Suddenly most of your clients
pulling are infected however your signature is correct.

Or, you would like to make a continuous delivery system, where you use
signed tags. The delivery happens only when signature is right, and
the signer is responsible for it. Your colleague makes a collision,
pushes the good-file. You make all the tests, everything is fine, sign
and push and wait for the delivery to happen. Your colleague changes
the file on the server. The delivery makes a huge mass, and you're
fired.

Or, let's say you use a service like github, which is nice enough to
make a repository for you, with .gitignore, licenses and everything.
Likely, you'll never change dose files. Let's say that service made
one of those initial files to collide something bad. That means, they
can "infect" anyone, who is pulling your repo.

Do you need more hypothetical stories? There are a lot. Of course they
need a lot of work, and they're unlikely to happen. But it's possible.
If you need trust, and gpg signatures that means you need ultimate
trust. What's the point in making GPG signatures anyway if you cannot
ultimately trust them? You could just as well say: well that's
repository is only reachable by trustworthy persons, everything here
is just fine and really made by the person named in the "author
field".

On Mon, Jul 18, 2016 at 7:48 PM, Herczeg Zsolt [off-list ref] wrote:

quoted

In particular, as far as I know and as Theodore Ts'o's post describes
better than I could[1], you seem to be confusing preimage attacks with
collision attacks, and then concluding that because SHA1 is vulnerable
to collision attacks that use-cases that would need a preimage attack
to be compromised (which as far is I can tell, includes all your
examples) are also "broken".

I understand the differences between the collision and preimage
attacks.

Fair enough. The rest of your E-Mail certainly shows that you do, and
I didn't know enough anything about GitTorrent and this case where
it's vulnerable to collission attacks.

But I didn't get that impression from your initial E-Mail which
outright said said:

    Git signed tags and signed commits are cryptographically
    insecure, they're useless at the moment.

It's important that those of us who *do* understand the difference
between collision and preimage attacks carefully phrase things, least
they turn into FUD.

Your initial E-Mail does *not* make it sound like you're just talking
about the cases where someone's provided you with a crafted blob that
you've been tricked into signing, but rather makes it sound like
signed tags & commits are just categorically broken, even for preimage
attacks, which is not the case.

The reality of the current situation is that it's largely mitigated in
practice because:

a) it's hard to hand someone a crafted blob to begin with for reasons
that have nothing to do with SHA-1 (they'll go "wtf is this garbage?")

b) even in that case it's *very* hard to come up with two colliding
blobs that are *useful* for some nefarious purpose, e.g. a program A
that looks normal being replaced by an evil program B with the same
SHA-1.

On Mon, 18 Jul 2016, Herczeg Zsolt wrote:

quoted

In particular, as far as I know and as Theodore Ts'o's post describes
better than I could[1], you seem to be confusing preimage attacks with
collision attacks, and then concluding that because SHA1 is vulnerable
to collision attacks that use-cases that would need a preimage attack
to be compromised (which as far is I can tell, includes all your
examples) are also "broken".

I understand the differences between the collision and preimage
attacks. A collision attack is not that bad for git in a typical
use-case. But I think that it's important to note that there are many
use-cases which do need a hash safe from collision attack. Some
examples:

You maintain a repository with gittorrent with signed commits Others
can use these signatures to verify it's original. Let's say you
include some safe file (potentially binary) from a third-party
contributor. That would be fine if the hash algo is safe. Currently
there is the possibility that you received a (safe) file which was
made to collide with another malicious one. Once you committed (and
signed) that file, the attacker joins the gittorrent network and
starts to distribute the malicious file. Suddenly most of your clients
pulling are infected however your signature is correct.

Or, you would like to make a continuous delivery system, where you use
signed tags. The delivery happens only when signature is right, and
the signer is responsible for it. Your colleague makes a collision,
pushes the good-file. You make all the tests, everything is fine, sign
and push and wait for the delivery to happen. Your colleague changes
the file on the server. The delivery makes a huge mass, and you're
fired.

Or, let's say you use a service like github, which is nice enough to
make a repository for you, with .gitignore, licenses and everything.
Likely, you'll never change dose files. Let's say that service made
one of those initial files to collide something bad. That means, they
can "infect" anyone, who is pulling your repo.

Do you need more hypothetical stories? There are a lot. Of course they
need a lot of work, and they're unlikely to happen. But it's possible.
If you need trust, and gpg signatures that means you need ultimate
trust. What's the point in making GPG signatures anyway if you cannot
ultimately trust them? You could just as well say: well that's
repository is only reachable by trustworthy persons, everything here
is just fine and really made by the person named in the "author
field".

All of your examples are actually preimage attacks. If the bad guy can tamper 
with the both the 'safe' and 'malicious' versions of the file, they don't 
actually need the malicious version, they can attack you through the one you 
think is 'safe'

The 'collision' attack isn't that there is some increased chance of a random 
file colliding with your safe file, it's that if you are manipulating the 
contents of both files, you can create two that collide. This won't hurt a Git 
repository unless one of these manipulated files is able to be introduced as a 
legitimate part of the repo you are dealing with.

David Lang

On Mon, Jul 18, 2016 at 09:00:06AM +0200, Johannes Schindelin wrote:

Hi Brian,

On Sun, 17 Jul 2016, brian m. carlson wrote:

quoted

On Sun, Jul 17, 2016 at 10:01:38AM +0200, Johannes Schindelin wrote:

quoted

Out of curiosity: have you considered something like padding the SHA-1s
with, say 0xa1, to the size of the new hash and using that padding to
distinguish between old vs new hash?

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.  I was going to zero-pad, however.

I thought about zero-padding, but there are plenty of
is_null_sha1()/is_null_oid() calls around. Of course, I assumed
left-padding. But you may have thought of right-padding instead? That
would make short name handling much easier, too.

I was going to right-pad.

FWIW it never crossed my mind to allow different same-sized hash
algorithms. So I never thought we'd need a way to distinguish, say,
BLAKE2b-256 from SHA-256.

Is there a good reason to add the maintenance burden of several 256-bit
hash algorithms, apart from speed (which in my mind should decide which
one to use, always, rather than letting the user choose)? It would also
complicate transport even further, let alone subtree merges from
differently-hashed repositories.

There are really three candidates:

* SHA-256 (the SHA-2 algorithm): While this looks good right now,
  cryptanalysis is advancing.  This is not a good choice for a long-term
  solution.
* SHA3-256 (the SHA-3 algorithm): This is the conservative choice.  It's
  also faster than SHA-256 on 64-bit systems.  It has a very
  conservative security margin and is a good long-term choice.
* BLAKE2b-256: This is the blisteringly fast choice.  It outperforms
  SHA-1 and even MD5 on 64-bit systems.  This algorithm was designed so
  that nobody would have a reason to use an insecure algorithm.  It will
  probably be secure for some time, but maybe not as long as SHA3-256.

I'm only considering 256-bit hashes, because anything longer won't fit
on an 80-column terminal in hex form.

The reason I had considered implementing both SHA3-256 and BLAKE2b-256
is that I want there to be no reason not to upgrade.  People who need a
FIPS-approved algorithm or want a long-term, conservative choice should
use SHA3-256.  People who want even better performance than current Git
would use BLAKE2b-256.

Performance comparison (my implementations):
SHA-1:     437 MiB/s
SHA-256:   196 MiB/s
SHA3-256:  273 MiB/s
BLAKE2b:   649 MiB/s

I hadn't thought about subtree merges, though.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

Hi Duy,

On Mon, 18 Jul 2016, Duy Nguyen wrote:

On Sun, Jul 17, 2016 at 4:21 PM, brian m. carlson
[off-list ref] wrote:

quoted

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.

Or even the other way around, main repo is one with sha1 while
submodule is on sha256. I wonder if we should address this separately
(and even in parallel with sha256 support), making submodules work
with an any external VCS system (that supports some basic operations
we define).

It is safe to assume that any project using a submodule with a more secure
hash would require Git tooling capable of said hash. It would hence make
no sense to use SHA-1 for the super project.

So I do not believe that we have to support the use case of a SHA-1-based
project using SHA-256-based submodules.

Ciao,
Dscho

On Tue, 19 Jul 2016, Johannes Schindelin wrote:

Hi Duy,

On Mon, 18 Jul 2016, Duy Nguyen wrote:

quoted

On Sun, Jul 17, 2016 at 4:21 PM, brian m. carlson
[off-list ref] wrote:

quoted

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.

Or even the other way around, main repo is one with sha1 while
submodule is on sha256. I wonder if we should address this separately
(and even in parallel with sha256 support), making submodules work
with an any external VCS system (that supports some basic operations
we define).

It is safe to assume that any project using a submodule with a more secure
hash would require Git tooling capable of said hash. It would hence make
no sense to use SHA-1 for the super project.

So I do not believe that we have to support the use case of a SHA-1-based
project using SHA-256-based submodules.

they have different upstreams, what if the upstream of the submodule has 
upgraded and is using signed commits of the sha-256 but the upstream of the 
parent hasn't and is using signed commits of sha1?

David Lang

On Mon, Jul 18, 2016 at 6:51 PM, Duy Nguyen [off-list ref] wrote:

On Sun, Jul 17, 2016 at 4:21 PM, brian m. carlson
[off-list ref] wrote:

quoted

I'm going to end up having to do something similar because of the issue
of submodules.  Submodules may still be SHA-1, while the main repo may
be a newer hash.

Or even the other way around, main repo is one with sha1 while
submodule is on sha256. I wonder if we should address this separately
(and even in parallel with sha256 support), making submodules work
with an any external VCS system (that supports some basic operations
we define).

Post-shower thoughts. In a tree object, a submodule entry consists of
perm (S_IFGITLINK), hash (which is the external hash) and path. We
could fill the "hash" part with all zero (invalid, signature of new
submodule hash format), then append "/<hashtype>:<external hash>" to
the "path" part. This way we don't have to update tree object or index
format. And I suspect the "path" part is available everywhere we need
to handle submodules already, so extracting the external hash should
be possible...
-- 
Duy

Hi Brian,

On Mon, 18 Jul 2016, brian m. carlson wrote:

On Mon, Jul 18, 2016 at 09:00:06AM +0200, Johannes Schindelin wrote:

quoted

FWIW it never crossed my mind to allow different same-sized hash
algorithms. So I never thought we'd need a way to distinguish, say,
BLAKE2b-256 from SHA-256.

Is there a good reason to add the maintenance burden of several 256-bit
hash algorithms, apart from speed (which in my mind should decide which
one to use, always, rather than letting the user choose)? It would also
complicate transport even further, let alone subtree merges from
differently-hashed repositories.

There are really three candidates:

* SHA-256 (the SHA-2 algorithm): While this looks good right now,
  cryptanalysis is advancing.  This is not a good choice for a long-term
  solution.
* SHA3-256 (the SHA-3 algorithm): This is the conservative choice.  It's
  also faster than SHA-256 on 64-bit systems.  It has a very
  conservative security margin and is a good long-term choice.
* BLAKE2b-256: This is the blisteringly fast choice.  It outperforms
  SHA-1 and even MD5 on 64-bit systems.  This algorithm was designed so
  that nobody would have a reason to use an insecure algorithm.  It will
  probably be secure for some time, but maybe not as long as SHA3-256.

I'm only considering 256-bit hashes, because anything longer won't fit
on an 80-column terminal in hex form.

The reason I had considered implementing both SHA3-256 and BLAKE2b-256
is that I want there to be no reason not to upgrade.  People who need a
FIPS-approved algorithm or want a long-term, conservative choice should
use SHA3-256.  People who want even better performance than current Git
would use BLAKE2b-256.

Performance comparison (my implementations):
SHA-1:     437 MiB/s
SHA-256:   196 MiB/s
SHA3-256:  273 MiB/s
BLAKE2b:   649 MiB/s

Those are impressive numbers on BLAKE2b. However, Keccak was chosen as
SHA-3 because it can be implemented in hardware more efficiently than
BLAKE (and hence, probably, also BLAKE2). Given that there are already SSE
instructions implementing SHA-1/SHA-256 on some CPUs [*1*], I would not be
surprised if SHA3 would also see some hardware support.

So speed seems less of a concern to me. We are talking about a multi-year
roadmap, after all.

And given the complications for public repository hosters, I would like to
settle for a single 256-bit hash. That'll be challenging enough.

Ciao,
Dscho

Footnote *1*: https://en.wikipedia.org/wiki/Intel_SHA_extensions