Starting to think about sha-256?

Starting to think about sha-256?

[Jeff Garzik]

Recent press[1] is talking about sha-1 collisions again.  Even though 
the reported attack was against a weakened variant of sha-1 (64, not 80, 
passes), it serves as a useful point to start talking about the future.

I argue that sha-256 is better suited to git's purposes, and to modern 
machines, than sha-1.

Upsides to sha-256:
* not just a bit increase, but a stronger algorithm.  there is more 
mixing, doing a more-than-incrementally better job at avoiding collisions.
* the bit increase itself provides more hash space, theoretically 
reducing collisions.
* properly aligned, a set of 32-byte hashes won't straddle CPU cachelines.

Downsides to sha-256:
* git protocol/storage format change implications.
* increase in storage size (20 to 32 bytes per hash).
* fewer hand-optimized algorithm variants have been implemented.
* likely more CPU cycles per hash, though I haven't measured.

Wikimedia page has lotsa info: 
http://en.wikipedia.org/wiki/Secure_Hash_Algorithm

Maybe sha-256 could be considered for the next major-rev of git?

	Jeff


[1] http://www.heise-security.co.uk/news/77244

Re: Starting to think about sha-256?

[Krzysztof Halasa]

Jeff Garzik <jeff@garzik.org> writes:

> Downsides to sha-256:
> * git protocol/storage format change implications.

The only which really matters, I think.

> Maybe sha-256 could be considered for the next major-rev of git?

Not sure, but _if_ we want it we should do it sooner rather than
later.
-- 
Krzysztof Halasa

Re: Starting to think about sha-256?

[Linus Torvalds]

On Sun, 27 Aug 2006, Krzysztof Halasa wrote:
> 
> > Maybe sha-256 could be considered for the next major-rev of git?
> 
> Not sure, but _if_ we want it we should do it sooner rather than
> later.

Modifying git-convert-objects.c to rewrite the regular sha1 into a sha256 
should be fairly straightforward. It's never been used since the early 
days (and has limits like a maximum of a million objects etc that can need 
fixing), but it shouldn't be "fundamentally hard" per se.

		Linus

Re: Starting to think about sha-256?

[Krzysztof Halasa]

Linus Torvalds <torvalds@osdl.org> writes:

> Modifying git-convert-objects.c to rewrite the regular sha1 into a sha256 
> should be fairly straightforward. It's never been used since the early 
> days (and has limits like a maximum of a million objects etc that can need 
> fixing), but it shouldn't be "fundamentally hard" per se.

Sure. I was rather thinking of rapidly increasing number of git
repositories, each with growing history.
-- 
Krzysztof Halasa

Re: Starting to think about sha-256?

[Johannes Schindelin]

Hi,

On Sun, 27 Aug 2006, Linus Torvalds wrote:

> On Sun, 27 Aug 2006, Krzysztof Halasa wrote:
> > 
> > > Maybe sha-256 could be considered for the next major-rev of git?
> > 
> > Not sure, but _if_ we want it we should do it sooner rather than
> > later.
> 
> Modifying git-convert-objects.c to rewrite the regular sha1 into a sha256 
> should be fairly straightforward. It's never been used since the early 
> days (and has limits like a maximum of a million objects etc that can need 
> fixing), but it shouldn't be "fundamentally hard" per se.

But what about signed tags? (This issue has come up before, but never has 
been adressed.)

I also thought about supporting hybrid hashes, i.e. that older objects 
still can be hashed with SHA-1. Alas, a simple thought experiment 
demonstrates how silly that idea is: most of the objects will not change 
between two revisions, and they'd have to be rehashed with SHA-256 (or 
whatever we decide upon) anyway, so hybrids would do no good.

A better idea would be to increment the repository version, and expect 
SHA-1 for version 1, SHA-256 for version >= 2.

However, I could imagine that we do not need this huge change (it would 
break _many_ setups). The breakthrough was announced last Tuesday, and it 
involved 75% payload, i.e. to fake a new -- say -- git.c, one would need 
to enlarge git.c by a factor 4, and you would see a lot of gibberish 
inside some comment. (Note that I did not listen to the talk myself, this 
is all deducted from the scarce information which is available via the 
'net.)

Even if the breakthrough really comes to full SHA-1, you still have to add 
_at least_ 20 bytes of gibberish. Which would be harder to spot, but it 
would be spotted.

This made me think about the use of hashes in git. Why do we need a hash 
here (in no particular order):

1) integrity checking,
2) fast lookup,
3) identifying objects (related to (2)),
4) trust.

Except for (4), I do not see why SHA-1 -- even if broken -- should not be 
adequate. It is not like somebody found out that all JPGs tend to have 
similar hashes so that collisions are more likely.

And thinking about trust: The hash is augmented by thinking persons. It is 
not like you blindly trust a person forever. You build up trust, and once 
you were failed, the trust is lost, and very hard to build up again. So, 
you just would try to get all objects again from somebody you still trust, 
and never pull from the loser^H^H^H^H^Huntrusted person again. Ever.

Besides, as has been pointed out several times, a dishonest person could 
try to sneak bad code into your repository _regardless_ of a secure hash.

So: Do we really need a secure hash, or do we need an adequate hash, and 
just happen to use one which was intended as a secure hash, but no longer 
is?

Ciao,
Dscho

Re: Starting to think about sha-256?

[Linus Torvalds]

On Mon, 28 Aug 2006, Johannes Schindelin wrote:
> > 
> > Modifying git-convert-objects.c to rewrite the regular sha1 into a sha256 
> > should be fairly straightforward. It's never been used since the early 
> > days (and has limits like a maximum of a million objects etc that can need 
> > fixing), but it shouldn't be "fundamentally hard" per se.
> 
> But what about signed tags? (This issue has come up before, but never has 
> been adressed.)

Signed tags fundamentally have to be re-signed. That's by design: if 
somebody could rewrite an archive and signed tags would still be accepted 
to have the right signature, that would be a _serious_ sign of a totally 
broken security model.

The git security model isn't broken.

> I also thought about supporting hybrid hashes, i.e. that older objects 
> still can be hashed with SHA-1. Alas, a simple thought experiment 
> demonstrates how silly that idea is: most of the objects will not change 
> between two revisions, and they'd have to be rehashed with SHA-256 (or 
> whatever we decide upon) anyway, so hybrids would do no good.

Indeed. Hybrids would not only do no good, but they would actually 
_actively_ hurt things, because they'd fundamentally break the notion that 
the hash being identical means that the object (blob, tree, subtree) is 
the same.

So allowing two names for the same object is very fundamentally wrong in 
git-speak. 

> A better idea would be to increment the repository version, and expect 
> SHA-1 for version 1, SHA-256 for version >= 2.

Yes. It would be reasonably painful for users, though (as Krzysztof 
correctly points out). Every client would have to convert when a 
repository they track is converted.

> Even if the breakthrough really comes to full SHA-1, you still have to add 
> _at least_ 20 bytes of gibberish. Which would be harder to spot, but it 
> would be spotted.

Yeah, I don't think this is at all critical, especially since git really 
on a security level doesn't _depend_ on the hashes being cryptographically 
secure. As I explained early on (ie over a year ago, back when the whole 
design of git was being discussed), the _security_ of git actually depends 
on not cryptographic hashes, but simply on everybody being able to secure 
their own _private_ repository.

So the only thing git really _requires_ is a hash that is _unique_ for the 
developer (and there we are talking not of an _attacker_, but a benign 
participant).

That said, the cryptographic security of SHA-1 is obviously a real bonus. 
So I'd be disappointed if SHA-1 can be broken more easily (and I obviously 
already argued against using MD5, exactly because generating duplicates of 
that is fairly easy). But it's not "fundamentally required" in git per se.

[ The one exception: the "signed tags" security does depend on the hashes 
  being cryptographically strong. So again, breaking SHA-1 would not mean 
  that git stops working, but it _would_ potentially mean that if you 
  don't trust your own _private_ repository, the signed tag may no longer 
  protect you entirely ]

> This made me think about the use of hashes in git. Why do we need a hash 
> here (in no particular order):
> 
> 1) integrity checking,
> 2) fast lookup,
> 3) identifying objects (related to (2)),
> 4) trust.
> 
> Except for (4), I do not see why SHA-1 -- even if broken -- should not be 
> adequate. It is not like somebody found out that all JPGs tend to have 
> similar hashes so that collisions are more likely.

Correct. I'm pretty sure we had exactly this discussion around May 2005, 
but I'm too lazy to search ;)

		Linus

Re: Starting to think about sha-256?

[David Lang]

--On Sunday, August 27, 2006 03:35:20 PM -0700 Linus Torvalds 
<torvalds@osdl.org> wrote:
>
> On Mon, 28 Aug 2006, Johannes Schindelin wrote:
>> Even if the breakthrough really comes to full SHA-1, you still have to
>> add  _at least_ 20 bytes of gibberish. Which would be harder to spot,
>> but it  would be spotted.
>
> Yeah, I don't think this is at all critical, especially since git really
> on a security level doesn't _depend_ on the hashes being
> cryptographically  secure. As I explained early on (ie over a year ago,
> back when the whole  design of git was being discussed), the _security_
> of git actually depends  on not cryptographic hashes, but simply on
> everybody being able to secure  their own _private_ repository.
>
> So the only thing git really _requires_ is a hash that is _unique_ for
> the  developer (and there we are talking not of an _attacker_, but a
> benign  participant).
>
> That said, the cryptographic security of SHA-1 is obviously a real bonus.
> So I'd be disappointed if SHA-1 can be broken more easily (and I
> obviously  already argued against using MD5, exactly because generating
> duplicates of  that is fairly easy). But it's not "fundamentally
> required" in git per se.


>> This made me think about the use of hashes in git. Why do we need a hash
>> here (in no particular order):
>>
>> 1) integrity checking,
>> 2) fast lookup,
>> 3) identifying objects (related to (2)),
>> 4) trust.
>>
>> Except for (4), I do not see why SHA-1 -- even if broken -- should not
>> be  adequate. It is not like somebody found out that all JPGs tend to
>> have  similar hashes so that collisions are more likely.
>
> Correct. I'm pretty sure we had exactly this discussion around May 2005,
> but I'm too lazy to search ;)

just to double check.

if you already have a file A in git with hash X is there any condition 
where a remote file with hash X (but different contents) would overwrite 
the local version?

what would happen if you ended up with two packs that both contained a file 
with hash X but with different contents and then did a repack on them? 
(either packs from different sources, or packs downloaded through some 
mechanism other then the git protocol are two ways this could happen that I 
can think of)

David Lang

Re: Starting to think about sha-256?

[Linus Torvalds]

On Mon, 28 Aug 2006, David Lang wrote:
> 
> just to double check.
> 
> if you already have a file A in git with hash X is there any condition where a
> remote file with hash X (but different contents) would overwrite the local
> version?

Nope. If it has the same SHA1, it means that when we receive the object 
from the other end, we will _not_ overwrite the object we already have.

So what happens is that if we ever see a collision, the "earlier" object 
in any particular repository will always end up overriding. But note that 
"earlier" is obviously per-repository, in the sense that the git object 
network generates a DAG that is not fully ordered, so while different 
repositories will agree about what is "earlier" in the case of direct 
ancestry, if the object came through separate and not directly related 
branches, two different repos may obviously have gotten the two objects in 
different order.

However, the "earlier will override" is very much what you want from a 
security standpoint: remember that the git model is that you should 
primarily trust only your _own_ repository. So if you do a "git pull", the 
new incoming objects are by definition less trustworthy than the objects 
you already have, and as such it would be wrong to allow a new object to 
replace an old one.

So you have two cases of collision:

 - the inadvertent kind, where you somehow are very very unlucky, and two 
   files end up having the same SHA1. At that point, what happens is that 
   when you commit that file (or do a "git-update-index" to move it into 
   the index, but not committed yet), the SHA1 of the new contents will be 
   computed, but since it matches an old object, a new object won't be 
   created, and the commit-or-index ends up pointing to the _old_ object.

   You won't notice immediately (since the index will match the old object 
   SHA1, and that means that something like "git diff" will use the 
   checked-out copy), but if you ever do a tree-level diff (or you 
   do a clone or pull, or force a checkout) you'll suddenly notice that 
   that file has changed to something _completely_ different than what you 
   expected. So you would generally notice this kind of collision fairly 
   quickly.

   In related news, the question is what to do about the inadvertent 
   collision.. First off, let me remind people that the inadvertent kind 
   of collision is really really _really_ damn unlikely, so we'll quite 
   likely never ever see it in the full history of the universe. But _if_ 
   it happens, it's not the end of the world: what you'd most likely have 
   to do is just change the file that collided slightly, and just force a 
   new commit with the changed contents (add a comment saying "/* This 
   line added to avoid collision */") and then teach git about the magic 
   SHA1 that has been shown to be dangerous.

   So over a couple of million years, maybe we'll have to add one or two 
   "poisoned" SHA1 values to git. It's very unlikely to be a maintenance 
   problem ;)

 - The attacker kind of collision because somebody broke (or brute-forced) 
   SHA1.

   This one is clearly a _lot_ more likely than the inadvertent kind, but 
   by definition it's always a "remote" repository. If the attacker had 
   access to the local repository, he'd have much easier ways to screw you 
   up.

   So in this case, the collision is entirely a non-issue: you'll get a 
   "bad" repository that is different from what the attacker intended, but 
   since you'll never actually use his colliding object, it's _literally_ 
   no different from the attacker just not having found a collision at 
   all, but just using the object you already had (ie it's 100% equivalent 
   to the "trivial" collision of the identical file generating the same 
   SHA1).

> what would happen if you ended up with two packs that both contained a file
> with hash X but with different contents and then did a repack on them? (either
> packs from different sources, or packs downloaded through some mechanism other
> then the git protocol are two ways this could happen that I can think of)

See above. The only _dangerous_ kind of collision is the inadvertent kind, 
but that's obviously also the very very unlikely kind.

			Linus

Re: Starting to think about sha-256?

[Linus Torvalds]

On Mon, 28 Aug 2006, Linus Torvalds wrote:
> 
>  - The attacker kind of collision because somebody broke (or brute-forced) 
>    SHA1.
> 
>    This one is clearly a _lot_ more likely than the inadvertent kind, but 
>    by definition it's always a "remote" repository. If the attacker had 
>    access to the local repository, he'd have much easier ways to screw you 
>    up.
> 
>    So in this case, the collision is entirely a non-issue: you'll get a 
>    "bad" repository that is different from what the attacker intended, but 
>    since you'll never actually use his colliding object, it's _literally_ 
>    no different from the attacker just not having found a collision at 
>    all, but just using the object you already had (ie it's 100% equivalent 
>    to the "trivial" collision of the identical file generating the same 
>    SHA1).

Btw, this is obviously only true for the native git protocol itself.

If the attacker can fool you into generating the new file _yourself_, he 
can cause your checked-out copy to not match the git object database any 
more.

In other words, one "interesting" attack vector is to feed you the 
colliding SHA1 not through a git-to-git transfer, but by generating a 
_patch_ that when applied will generate the collision, so that when you 
then commit that patch, you get something else than you expected.

And _this_ is where it's important that the hash that git uses be a 
non-trivial one - ie we don't want people to be able to generate two files 
that look superficially "ok".

So here's the rule: If you ever get a patch that looks like line-noise, 
especially from somebody you don't trust, DON'T APPLY IT!

Now, that is obviously something you should never do _regardless_ of any 
git issues, so I don't think this is really a problem either. If you apply 
patches from people you don't have a good reason to trust without 
sanity-checking them, you deserve whatever you get, and quite frankly, a 
SHA1 hash collision is the _least_ of your problems ;)

(This ends up boiling down to one common issue: it's generally _much_ 
easier to attack a project through _other_ means than through a hash 
collision. And I pretty much guarantee that that is the case even if we 
were to use a much weaker hash, like MD5. Hash collisions fundamentally 
just aren't good attack vectors, and it's a hell of a lot easier to try 
to insert bad code by other means)

			Linus

Re: Starting to think about sha-256?

[Jeff King]

On Mon, Aug 28, 2006 at 10:56:01AM -0700, Linus Torvalds wrote:

> However, the "earlier will override" is very much what you want from a 
> security standpoint: remember that the git model is that you should 
> primarily trust only your _own_ repository. So if you do a "git pull", the 

This concept breaks down somewhat if you are pulling from two
repositories (one good and one evil). If I pull from the evil repo
first, that will become my "earlier" object, and I will never get the
colliding object from the good repo.

Executing such an attack might not be that hard, either (once we get
over that little hump of creating collisions at will!). The owner of
'evil' has to know a SHA1 that will be in 'good' before it makes it to
'good'. However, I imagine we frequently see SHA1s migrate from more
central repos (like .../torvalds/linux-2.6.git) to less central ones
(subsystem / port maintainers, etc).

-Peff

Re: Starting to think about sha-256?

[Linus Torvalds]

On Mon, 28 Aug 2006, Jeff King wrote:
>
> On Mon, Aug 28, 2006 at 10:56:01AM -0700, Linus Torvalds wrote:
> 
> > However, the "earlier will override" is very much what you want from a 
> > security standpoint: remember that the git model is that you should 
> > primarily trust only your _own_ repository. So if you do a "git pull", the 
> 
> This concept breaks down somewhat if you are pulling from two
> repositories (one good and one evil). If I pull from the evil repo
> first, that will become my "earlier" object, and I will never get the
> colliding object from the good repo.

Sure. But if you are pulling from an untrusted source, you'd better at 
least check the result.

In fact, that's partly why "git pull" will do a diffstat after the pull. 
Exactly to force people to at least be minimally aware of what they 
pulled. And "gitk ORIG_HEAD.." is a great thing to always run when you 
pull from somebody you don't know and trust really well.

Of course, that all was done mostly not because I don't "trust" the people 
I work with, but more because I didn't always trust that they'd do the 
right thing with git (ie they'd screw up the repo not because they were 
evil, but because they made a mistake).

So even if you pull from an "evil" repo first, and you somehow get a "bad" 
object, the point is, the bad object _should_ be the one that overrides. 

Why? Because once you find out that the evil repo was bad (which you'll 
eventually find simply because it caused some bug - if the evil repo only 
helps you, it's obviously not evil at all), what you need to do is reset 
to _before_ the evil repo happened, do a "git repack -a -d" and finally a 
"git prune" to clean out all the bad cruft, and then pull the good repo 
without pulling the bad one first.

After that, you apologize to everybody for screwing up and pulling from 
somebody you didn't trust, and then ask them to re-clone (or give them the 
appropriate "git reset" + "git repack -a" + "git prune" + "git pull" 
sequence so that they can fix their existing repos).

The point being, a hash attack is really no worse than an attack that 
fools you into applying a really bad diff (regardless of SCM), and it's a 
hell of a lot harder to do. Both a hash attack and a diff attack mean that 
the person merging data should either trust his source or inspect the end 
result.

Anybody who just blindly accepts data from untrusted sources is screwed in 
so many other ways that the hash attack simply isn't even on the radar.

		Linus

Re: Starting to think about sha-256?

[Jeff King]

On Mon, Aug 28, 2006 at 11:46:39AM -0700, Linus Torvalds wrote:

> Sure. But if you are pulling from an untrusted source, you'd better at 
> least check the result.

I completely agree; however, even discussing "earlier takes precedence"
entails that you are somehow pulling from an untrusted source. I just
wanted to point out that "earlier" does not always mean "more trusted
than the thing you're pulling now" (since it might have just been pulled
earlier, not created or verified by you).

> Anybody who just blindly accepts data from untrusted sources is screwed in 
> so many other ways that the hash attack simply isn't even on the radar.

Agreed.

-Peff

Re: Starting to think about sha-256?

[Krzysztof Halasa]

Linus Torvalds <torvalds@osdl.org> writes:

>    In related news, the question is what to do about the inadvertent 
>    collision.. First off, let me remind people that the inadvertent kind 
>    of collision is really really _really_ damn unlikely, so we'll quite 
>    likely never ever see it in the full history of the universe.

Actually I think we may see it when somebody tries to put a real
example of conflicting SHA-1 pair into git repository.
-- 
Krzysztof Halasa

Re: Starting to think about sha-256?

[Linus Torvalds]

On Mon, 28 Aug 2006, Krzysztof Halasa wrote:
>
> Linus Torvalds <torvalds@osdl.org> writes:
> 
> >    In related news, the question is what to do about the inadvertent 
> >    collision.. First off, let me remind people that the inadvertent kind 
> >    of collision is really really _really_ damn unlikely, so we'll quite 
> >    likely never ever see it in the full history of the universe.
> 
> Actually I think we may see it when somebody tries to put a real
> example of conflicting SHA-1 pair into git repository.

Well, by definition, I wouldn't call that "inadvertent" ;)

Anyway, the way to do it (if you want to use git to document SHA1 hash 
mismatches) is to just check the files that have an identical SHA1 in. It 
will magically work!

Why? Because a git SHA1 is actually _not_ the SHA1 of the file itself, 
it's the SHA1 of the file _with_the_git_header_added_.

So if you find two files that have the same SHA1, they would also have to 
have the same length in order to actually generate the same object name. 
If they have different lenths, you can just check them into git, and 
they'll get two different git SHA1 names and you'll have a cool git 
archive that when you check the files out, they checked-out files will 
share the same SHA1 ;)

		Linus

Re: Starting to think about sha-256?

[Krzysztof Halasa]

Linus Torvalds <torvalds@osdl.org> writes:

> Anyway, the way to do it (if you want to use git to document SHA1 hash 
> mismatches) is to just check the files that have an identical SHA1 in. It 
> will magically work!
>
> Why? Because a git SHA1 is actually _not_ the SHA1 of the file itself, 
> it's the SHA1 of the file _with_the_git_header_added_.
>
> So if you find two files that have the same SHA1, they would also have to 
> have the same length in order to actually generate the same object name. 

Well, conflicting files will most probably have the same size,
like with MD5 cases :-)
-- 
Krzysztof Halasa

Re: Starting to think about sha-256?

[Linus Torvalds]

On Mon, 28 Aug 2006, Krzysztof Halasa wrote:
> 
> Well, conflicting files will most probably have the same size,
> like with MD5 cases :-)

That's only true for the much easier injection case where you generate 
_both_ files together.

>From an external git hash-attack standpoint, that's not a very useful 
case. It's much more useful if you can make a new file that has a hash 
that matches a given old file, and in that case, the filelengths are 
likely not the same.

			Linus

Re: Starting to think about sha-256?

[Johannes Schindelin]

Hi,

On Mon, 28 Aug 2006, Linus Torvalds wrote:

> 
> 
> On Mon, 28 Aug 2006, David Lang wrote:
> > 
> > just to double check.
> > 
> > if you already have a file A in git with hash X is there any condition where a
> > remote file with hash X (but different contents) would overwrite the local
> > version?
> 
> Nope. If it has the same SHA1, it means that when we receive the object 
> from the other end, we will _not_ overwrite the object we already have.

The only notable exception I can think of: "git fetch -k". If you then try 
to retrieve the bogus object, it will return the one of whichever pack was 
returned first be readdir(). (If I read the source correctly.)

Now, the cases are rare where you do both "git fetch -k" and "git repack 
-a -d" (the latter of which _could_ leave a hole in the directory which 
_could_ make the next fetched pack fill that hole, which in turn _could_ 
make readdir() return that pack before more "senior" packs) in the same 
repository, but in these cases, yes, you could end up with the copy of the 
remote side.

You'd need to explicitely use "git fetch -k", though.

Ciao,
Dscho

Re: Starting to think about sha-256?

[Linus Torvalds]

On Tue, 29 Aug 2006, Johannes Schindelin wrote:
>
> > Nope. If it has the same SHA1, it means that when we receive the object 
> > from the other end, we will _not_ overwrite the object we already have.
> 
> The only notable exception I can think of: "git fetch -k". If you then try 
> to retrieve the bogus object, it will return the one of whichever pack was 
> returned first be readdir(). (If I read the source correctly.)

Good point.

I didn't even think of "-k", since I mentally put that in the "initial 
clone usage only" category, but yeah, if people use it for incremental 
updates too, that could indeed cause ambiguity in which object to use when 
the other end does something bad.

		Linus

Re: Starting to think about sha-256?

[Florian Weimer]

* Jeff Garzik:

> * likely more CPU cycles per hash, though I haven't measured.

According to a quick test using "openssl speed", it's a factor of two
to four, depending on the input size (the difference is less
pronounced for small input sizes).

> Maybe sha-256 could be considered for the next major-rev of git?

And in 2008, you'd have to rewrite history again, to use the next
"stronger" hash function?  Do you think that's really necessary or
desirable?  Most users will have good control over what data enters
their repositories, so they can spot the evil twins thanks to their
high-entropy contents.  Obviously, a second preimage attack would
mattr, but even for MD5, we aren't close to that one AFAIK.

Re: Starting to think about sha-256?

[linux]

For those worrying, note that even a "complete" break of SHA-1 doesn't
imply the ability to sneak a trojan into a git repository via a patch
or something.

What cryptographers consider a break is finding a collision, two messages
x and y such that hash(x) == hash(y).  But note that the attacker gets
to pick both x and y!

A so-called second pre-image attack, where x is fixed beforehand is far
harder, even if you get to choose from the 320K or so objects in the
linux kernel repository.

Merely inducing you to somehow import the trojan object y into your
object database doesn't help unless you trust and are willing to build
and run source including the object x that it is a doppelgänger for.
So, armed with only a collision-finding attack, the attacker has to
create a collision pair including an innocent source file that can get
included (without any bizarre contents getting "fixed" by a maintainer)
before anyone can attempt to substitute the trojan y.

That requirement eliminates most collision attacks, which generate
good-sized binary blobs.  There's a demo where someone did it with a
postscript file, but that was basically

	if (parity("line noise"))
		print innocent message
	else
		print trojan message

Now, admittedly, this sort of fine reasoning does reduce the possible
application domain of git to human-readable source.  If I'm using git
as a back-end for (say) an archive of statically verified but opaque
java byte-code files, then there's potential for trouble.

But I just want to remind people that even if a "complete" break of SHA-1
were announced tomorrow, it wouldn't imply that using git is dangerous.
Frankly, it would *still* probably be less work to hide a trojan in the
source code well enough that it sneaks under the maintainer's radar.


> Why? Because a git SHA1 is actually _not_ the SHA1 of the file itself, 
> it's the SHA1 of the file _with_the_git_header_added_.
> 
> So if you find two files that have the same SHA1, they would also have to 
> have the same length in order to actually generate the same object name. 
> If they have different lenths, you can just check them into git, and 
> they'll get two different git SHA1 names and you'll have a cool git 
> archive that when you check the files out, they checked-out files will 
> share the same SHA1 ;)

This has always seemed silly to me.  Every cryptographic hash
algorithm since the (catastrophically broken) MD4 has used the standard
Merkle-Damgård strengthening construction to include the length.
There's no point in doing it a second time.

It's done as a suffix, not a prefix, but it's there.  And an odd-sized
prefix makes it hard to have a fast-path aligned hash for the bulk of
the data on machines with alignment restrictions.

Now, the case can be made that a prefix is slightly stronger 
(http://cs.nyu.edu/~puniya/papers/merkle.pdf), but I don't think
that's why it was done.

Note that since the length is included, you can avoid the odd-sized prefix
problem by putting any extra data you like on the hash as a trailer.
As long as it's suffix-free, (e.g. leading null byte), you haven't
hurt anything.



Anyway, SHA-256 is tricky on x86, because it has 8 words of state and
x86 has only 7 registers.

But here's some (public domain) code which works well on x86, and doesn't
suck too badly on other processors.  It's designed to be benchmarked
against Brian Gladman's implementation; if you have that, change the
obvious #define and link against sha2.o.

The other interesting benchmark is "nm -n *.o"; on x86, it's 290 bytes
of core transform vs. 4773 bytes for sha256_compile.


#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define DEBUG 0
#define HAVE_GLADMAN_CODE 0

struct sha256_state {
	uint32_t iv[8];	/* h, g, f, e, d, c, b, a */
	uint32_t w[64];	/* Fill in first 16 with ntohl(input) */
	uint32_t d2, c2, b2, a2;
	uint32_t bytes_hi, bytes_lo;
};

/* Rotate right macro.  GCC can usually get this right. */
#define ROTR(x,s) ((x)>>(s) | (x)<<(32-(s)))

/*
 * An implementation of SHA-256 for register-starved architectures like
 * x86 or perhaps the MSP430.  (Although the latter's lack of a multi-bit
 * shifter will doom its performance no matter what.)
 * This code is also quite small.
 *
 * If you have 12 32-bit registers to work with, loading the 8 state
 * variables into registers is probably faster.  If you have 28 registers
 * or so, you can put the input block into registers as well.
 *
 * The key idea is to notice that each round consumes one word from the
 * key schedule w[i], computes a new a, and shifts all the other state
 * variables down one position, discarding the old h.
 *
 * So if we store the state vector in reverse order h..a, immediately
 * before w[i], then a single base pointer can be incremented to advance
 * to the next round.
 */
void
sha256_transform(uint32_t p[76])
{
	static uint32_t const k[64] = {
		0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b,
		0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01,
		0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7,
		0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
		0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152,
		0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147,
		0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
		0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
		0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819,
		0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08,
		0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f,
		0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
		0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
	};
	/*
	 * Look, ma, only 6 local variables including p!
	 * Too bad they're so overloaded it's impossible to give them
	 * meaningful names.
	 */
	register uint32_t const *kp;
	register uint32_t a, s, t, u;

	/* Step 1: Expand the 16 words of w[], at p[8..23] into 64 words */
	for (u = 8; u < 8+64-16; u++) {
		/* w[i] = s1(w[i-2]) + w[i-7] + s0(w[i-15]) + w[i-16] */
		/* Form s0(x) = (x >>> 7) ^ (x >>> 18) ^ (x >> 3) */
		s = t = p[u+1];
		s = ROTR(s, 18-7);
		s ^= t;
		s = ROTR(s, 7);
		s ^= t >> 3;
		/* Form s1(x) = (x >>> 17) ^ (x >>> 19) ^ (x >> 10) */
		a = t = p[u+14];
		a = ROTR(a, 19-17);
		a ^= t;
		a = ROTR(a, 17);
		a ^= t >> 10;

		p[u+16] = s + a + p[u] + p[u+9];
	}

	/* Step 2: Copy the initial values of d, c, b, a out of the way */
	p[72] = p[4];
	p[73] = p[5];
	p[74] = p[6];
	p[75] = a = p[7];

	/*
	 * Step 3: The big loop.
	 * We maintain p[0..7] = h..a, and p[8] is w[i]
	 * Only the variable a is actually kept in a local register.
	 */
	kp = k;

	do {
		/* T1 = h + S1(e) + Ch(e,f,g) + k[i] + w[i] */
		/* Form Ch(e,f,g) = g ^ (e & (f ^ g)) */
		s = t = p[1];	/* g */
		s ^= p[2];	/* f ^ g */
		s &= u = p[3];	/* e & (f ^ g), copy of e left in u */
		s ^= t;
		/* Form S1(e) = (e >>> 6) ^ (e >>> 11) ^ (e >>> 25) */
		t = u;
		u = ROTR(u, 25-11);
		u ^= t;
		u = ROTR(u, 11-6);
		u ^= t;
		u = ROTR(u, 6);
		s += u;
		/* Now add other things to t1 */
		s += p[0] + p[8] + *kp;	/* h + w[i] + kp[i] */
		/* Round function: e = d + T1 */
		p[4] += s;
		/* a = t1 + (t2 = S0(a) + Maj(a,b,c) */
		/* Form S0(a) = (a >>> 2) ^ (a >>> 13) ^ (a >>> 22) */
		t = a;
		t = ROTR(t, 22-13);
		t ^= a;
		t = ROTR(t, 13-2);
		t ^= a;
		t = ROTR(t, 2);
		s += t;
		/* Form Maj(a,b,c) = (a & b) + (c & (a ^ b)) */
		u = p[6];	/* b */
		t = a;
		a ^= u;		/* a ^ b */
		u &= t;		/* a & b */
		a &= p[5];	/* c & (a + b) */
		s += u;
		a += s;	/* Sum final result into a */

		/* Now store new a on top of w[i] and shift... */
		p[8] = a;
		p++;
#if DEBUG 
		/* If debugging, print out the state variables each round */
		printf("%2u:", kp-k);
		for (t = 8; t--; )
			printf(" %08x", p[t]);
		putchar('\n');
#endif
	} while (++kp != k+64);

	/* Now, do the final summation. */
	kp = p;
	p -= 64;
	/*
	 * Now, the final h..a are in p[64..71], and the initial values
	 * are in p[0..7].  Except that p[4..7] got trashed in the loop
	 * above, so use the copies we made.
	 */
	p[0] += kp[0];
	p[1] += kp[1];
	p[2] += kp[2];
	p[3] += kp[3];
	p[4] = kp[4] + kp[8];
	p[5] = kp[5] + kp[9];
	p[6] = kp[6] + kp[10];
	p[7] = a     + kp[11];
}

/* Initial values H7..H0 for SHA-256, and SHA-224. Note reverse order! */
static uint32_t const _sha256_iv[8] = {
	0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
	0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667
};
static uint32_t const _sha224_iv[8] = {
	0xbefa4fa4, 0x64f98fa7, 0x68581511, 0xffc00b31,
	0xf70e5939, 0x3070dd17, 0x367cd507, 0xc1059ed8
};

#if HAVE_GLADMAN_CODE

#include "sha2.h"

#else

/* Compatibility wrappers */

typedef struct sha256_state sha256_ctx;

void
sha256_begin(struct sha256_state *s)
{
	memcpy(s->iv, _sha256_iv, sizeof _sha256_iv);
	s->bytes_lo = s->bytes_hi = 0;
}

#include <netinet/in.h>	/* For ntohl, htohl */

void
sha256_hash(unsigned char const *data, size_t len, struct sha256_state *s)
{
	unsigned space = 64 - (unsigned)s->bytes_lo % 64;
	unsigned i;

	s->bytes_lo += (uint32_t)len;
	s->bytes_hi += s->bytes_lo < (uint32_t)len;
	if ((size_t)-1 > (uint32_t)-1)
		s->bytes_hi += (uint32_t)(len >> 16 >> 16);

	while (len >= space) {
		memcpy((unsigned char *)s->w + 64 - space, data, space);
		len -= space;
		space = 64;
		for (i = 0; i < 16; i++)
			s->w[i] = ntohl(s->w[i]);
		sha256_transform(s->iv);
	}
	memcpy((unsigned char *)s->w + 64 - space, data, len);
}

void
sha256_end(unsigned char hash[32], struct sha256_state *s)
{
	unsigned i, pos = (unsigned)s->bytes_lo % 64;
	uint32_t *out;

	((unsigned char *)s->w)[pos++] = 0x80;
	if (pos > 56) {
		memset((unsigned char *)s->w + pos, 0, 64-pos);
		for (i = 0; i < 16; i++)
			s->w[i] = ntohl(s->w[i]);
		sha256_transform(s->iv);
		pos = 0;
	}
	memset((unsigned char *)s->w + pos, 0, 56-pos);
	for (i = 0; i < 14; i++)
		s->w[i] = ntohl(s->w[i]);
	s->w[15] = s->bytes_lo << 3;
	s->w[14] = s->bytes_hi << 3 | s->bytes_lo >> 29;
	sha256_transform(s->iv);

	out = (unsigned)hash % sizeof s->iv[0] ? s->w : (uint32_t *)hash;
	for (i = 0; i < 8; i++)
		out[i] = htonl(s->iv[7-i]);
	if (out == s->w)
		memcpy(hash, out, sizeof s->iv);
	memset(s, 0, sizeof s);	/* Good cryptographic hygiene */
}

void
sha256(unsigned char hash[32], const unsigned char *data, size_t len)
{
	struct sha256_state s;
	sha256_begin(&s);
	sha256_hash(data, len, &s);
	sha256_end(hash, &s);
}

#endif /* !HAVE_GLADMAN_CODE */

#include <string.h>
#include <sys/time.h>

#define TESTSIZE 100000000
#if TESTSIZE & 64 != 0
#error For now, TESTSIZE must be a multiple of 64.
#endif

int
main(void)
{
	uint32_t array1[76] = {
		/* Initial values, h..a */
		0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
		0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667,
		/* First 16 w[i] values */
		0x61626380, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0x00000018
	};
	uint32_t array2[76] = {
		/* Initial values, h..a */
		0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
		0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667,
		/* First 16 w[i] values */
		0x61626364, 0x62636465, 0x63646566, 0x64656667,
		0x65666768, 0x66676869, 0x6768696a, 0x68696a6b,
		0x696a6b6c, 0x6a6b6c6d, 0x6b6c6d6e, 0x6c6d6e6f,
		0x6d6e6f70, 0x6e6f7071, 0x80000000, 0x00000000
	};
	uint32_t array3[76] = {
		/* Initial values, h..a */
		0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f,
		0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667
	};
	unsigned i;
	struct timeval start, stop;
	sha256_ctx s256;
	unsigned char buf[64];

	/* The FIPS180-2 appendix B.1 example */
	printf("Appendix B.1 example:\n");
	sha256_transform(array1);
	printf("==>");
	for (i = 8; i--; )
		printf(" %08x", array1[i]);
	putchar('\n');

	printf("\nAppendix B.2 example:\n");
	sha256_transform(array2);
	printf("==>");
	for (i = 8; i--; )
		printf(" %08x", array2[i]);
	putchar('\n');
	putchar('\n');

	for(i = 8; i < 23; i++)
		array2[i] = 0;
	array2[23] = 0x000001c0;
	sha256_transform(array2);
	printf("==>");
	for (i = 8; i--; )
		printf(" %08x", array2[i]);
	putchar('\n');

	/* Now to hash 1,000,000 letters 'a' */
	printf("\nAppendix B.3 example:\n");

	gettimeofday(&start, 0);
	for (i = 0; i < TESTSIZE/64; i++) {
		memset((char *)(array3+8), 'a', 64);
		sha256_transform(array3);
	}
	array3[8] = 0x80000000;
	array3[23] = i*64*8;	/* Length in bits */
	for (i = 9; i < 23; i++)
		array3[i] = 0;
	sha256_transform(array3);
	gettimeofday(&stop, 0);
	stop.tv_sec -= start.tv_sec;
	stop.tv_usec -= start.tv_usec;
	if (stop.tv_usec < 0) {
		stop.tv_usec += 1000000;
		stop.tv_sec--;
	}
	printf("New code: %u.%06ld\n", (unsigned)stop.tv_sec, stop.tv_usec);
	printf("==>");
	for (i = 8; i--; )
		printf(" %08x", array3[i]);
	putchar('\n');


	sha256_begin(&s256);
	gettimeofday(&start, 0);
	for (i = 0; i < TESTSIZE/64; i++) {
		memset(buf, 'a', 64);
		sha256_hash(buf, 64, &s256);
	}
	sha256_end(buf, &s256);
	gettimeofday(&stop, 0);
	stop.tv_sec -= start.tv_sec;
	stop.tv_usec -= start.tv_usec;
	if (stop.tv_usec < 0) {
		stop.tv_usec += 1000000;
		stop.tv_sec--;
	}
	printf(
#if HAVE_GLADMAN_CODE
		"Gladman code: %u.%06ld\n",
#else
		"Wrapper code: %u.%06ld\n",
#endif
		(unsigned)stop.tv_sec, stop.tv_usec);

	printf("==>");
	for (i = 0; i < 32; i++) {
		if (i % 4 == 0)
			putchar(' ');
		printf("%02x", buf[i]);
	}
	putchar('\n');

	return 0;
}