From: Junio C Hamano <hidden> Date: 2016-06-15 22:52:18
Jeff King [off-list ref] writes:
Agreed. Having hidden cruft makes birthday collision attacks easier (or
it will, if sha1 ever gets broken to that point). Unfortunately, there
is a _ton_ of code which assumes that commit messages are
NUL-terminated, as they always have been since e871b64 (2005-05-25).
I think that commit is irrelevant, as long as read_sha1_file() returns the
contents as <ptr,len> pair, which has been the case forever. It's just the
matter of propagating the length back up the callchain.
A naïve implementation to add "len" member to struct commit would increase
the size of the in-core commit object by sizeof(unsigned long), which we
may want to avoid. Traversals that care nothing but the topology of the
history would have to waste that memory and these things tend to add up
(8-byte ulong * 250k commits = 2MB).
Perhaps change the type of "buf" member in struct commit to a pointer to a
<ptr,len> pair, or something? Or perhaps a few megabytes wasted between
friends we do not care much about?
From: Jeff King <hidden> Date: 2016-06-15 22:52:18
On Wed, Oct 19, 2011 at 11:57:17PM -0700, Junio C Hamano wrote:
Jeff King [off-list ref] writes:
quoted
Agreed. Having hidden cruft makes birthday collision attacks easier (or
it will, if sha1 ever gets broken to that point). Unfortunately, there
is a _ton_ of code which assumes that commit messages are
NUL-terminated, as they always have been since e871b64 (2005-05-25).
I think that commit is irrelevant, as long as read_sha1_file() returns the
contents as <ptr,len> pair, which has been the case forever. It's just the
matter of propagating the length back up the callchain.
It's not that the commit is bad or the source of problems. My point is
that the assumption that commit messages are NUL-terminated has been
there for a really long time, so there are lots of spots in the code
that sloppily run string functions on them. Every one of those needs to
be found and fixed (e.g., I remember seeing this in
for-each-ref.c:find_subpos recently).
It's not impossible, of course, or even really that hard. It's just a
giant pain, and I wonder if the effort is worth it.
A naïve implementation to add "len" member to struct commit would increase
the size of the in-core commit object by sizeof(unsigned long), which we
may want to avoid. Traversals that care nothing but the topology of the
history would have to waste that memory and these things tend to add up
(8-byte ulong * 250k commits = 2MB).
Perhaps change the type of "buf" member in struct commit to a pointer to a
<ptr,len> pair, or something? Or perhaps a few megabytes wasted between
friends we do not care much about?
I think you'd have to convert the struct (even if not every piece of
code is converted to use it) and profile.
-Peff
On Thu, Oct 20, 2011 at 5:57 PM, Junio C Hamano [off-list ref] wrote:
Jeff King [off-list ref] writes:
quoted
Agreed. Having hidden cruft makes birthday collision attacks easier (or
it will, if sha1 ever gets broken to that point). Unfortunately, there
is a _ton_ of code which assumes that commit messages are
NUL-terminated, as they always have been since e871b64 (2005-05-25).
I think that commit is irrelevant, as long as read_sha1_file() returns the
contents as <ptr,len> pair, which has been the case forever. It's just the
matter of propagating the length back up the callchain.
A naïve implementation to add "len" member to struct commit would increase
the size of the in-core commit object by sizeof(unsigned long), which we
may want to avoid. Traversals that care nothing but the topology of the
history would have to waste that memory and these things tend to add up
(8-byte ulong * 250k commits = 2MB).
Or write commit_length(struct commit *c) that calculates SHA-1 from
c->buf and checks against c->object.sha1. If it does not match,
consider NUL part of the message and move to the next NUL. This
function would be expensive so we may not call frequently though.
Or store length in ((int*)c->buf)[-1].
--
Duy
On Thu, Oct 20, 2011 at 03:13:56AM -0400, Jeff King wrote:
It's not that the commit is bad or the source of problems. My point is
that the assumption that commit messages are NUL-terminated has been
there for a really long time, so there are lots of spots in the code
that sloppily run string functions on them. Every one of those needs to
be found and fixed (e.g., I remember seeing this in
for-each-ref.c:find_subpos recently).
Another possibility is to warn if the commit messages are not NULL
terminated. Note though that if we're really worried about a bad guy
trying to attack us with a hash collision, he/she could always use
"invisible" non-printing characters in the commit message, and/or just
mess with one or both of the timestamps. The more bits and more
degrees of flexibility the attacker has, the easier it would be, of
course. In the grand scheme of things it's not clear to me how big of
a deal this would be.
If people were really concerned it would probably be easier to use
backup crypto checksum using something stronger (say, SHA-2 or the
eventual SHA-3). Just store the backup checksums of the parent
commitments in some backwardly compatible place that old git
implementations wouldn't look (say, after the NULL in the commit
message if there isn't a better place :-), and new implementations
would know to generate the checksums, and old implementations would
ignore it.
That way, if anyone *does* figure out a way to generate real hash
collisions with SHA1 of objects that look almost completely identical
to the original objects, new implementations that would gradually make
their way out to the field could verify the SHA-2 (or SHA-3, when it
is announced, assuming that we the tag the checksums with a type
identifier) checksums and notice that they are not correct.
Maybe someone's already thought of this, but the cool thing about this
idea is it's a way that we can upgrade to a stronger hash algorithm
without needing a flag day due to some kind of incompatible format
change; we keep using SHA1 for the user-visible hash, since it's fine
modulo intentional attacks, and then use a hidden, backup checksum
which can be checked either all the time, or if that turns out to be a
computational burden, at some configurable random percent of the time.
Anyway, just a thought....
- Ted
From: Jeff King <hidden> Date: 2016-06-15 22:52:18
On Thu, Oct 20, 2011 at 09:14:55AM -0400, Ted Ts'o wrote:
Another possibility is to warn if the commit messages are not NULL
terminated.
A minor nit, but it's not whether they are terminated with NUL, but
rather whether they have embedded NUL. But yeah, this could maybe just
be something fsck looks for.
Note though that if we're really worried about a bad guy trying to
attack us with a hash collision, he/she could always use "invisible"
non-printing characters in the commit message, and/or just mess with
one or both of the timestamps. The more bits and more degrees of
flexibility the attacker has, the easier it would be, of course. In
the grand scheme of things it's not clear to me how big of a deal this
would be.
Good point. Append-only attacks are cheaper, because you can avoid doing
most of the hash computation on each iteration (like my patch does). But
that's not a big-O speedup, it just makes the constant smaller. So you
could assume that any feasible appending attack would probably become
feasible for recomputing the full hash eventually.
If people were really concerned it would probably be easier to use
backup crypto checksum using something stronger (say, SHA-2 or the
eventual SHA-3). Just store the backup checksums of the parent
commitments in some backwardly compatible place that old git
implementations wouldn't look (say, after the NULL in the commit
message if there isn't a better place :-), and new implementations
would know to generate the checksums, and old implementations would
ignore it.
Yeah, if birthday attacks against sha1 become possible, the sensible
thing is probably not to worry too much about the file format, but to
use a better hash.
Commits can hide extra hashes in a header pretty easily. But what about
trees and blobs? I don't think there's any "ignored" space in either
one.
-Peff
On Thu, 2011-10-20 at 11:56 -0400, Jeff King wrote:
On Thu, Oct 20, 2011 at 09:14:55AM -0400, Ted Ts'o wrote:
quoted
Another possibility is to warn if the commit messages are not NULL
terminated.
A minor nit, but it's not whether they are terminated with NUL, but
rather whether they have embedded NUL. But yeah, this could maybe just
be something fsck looks for.
God (or your deity of choice) forbid that anybody ever writes code that
saves raw UTF-16 as the commit message...
--
-Drew Northup
________________________________________________
"As opposed to vegetable or mineral error?"
-John Pescatore, SANS NewsBites Vol. 12 Num. 59