Re: SHA-1 collision in repository?
Thank you, Melissa, for tracking this down!
Your effort is very much appreciated.
Cheers,
Stefan
On Wed, Mar 07, 2018 at 11:18:43PM +, Philip Martin wrote:
> [Moving this to the dev@s.a.o list.]
>
> Well done! It looks like you have identified a serious bug here. The
> function svn_fs_fs__get_contents_from_file() that was recently added to
> 1.9 for the SHA1 collision detection so the code is new and it is also
> different from that on trunk.
>
> Your proposed fix looks like it might be correct, although rb->rep is
> just rep so it could be a bit simpler. One other consequence of this
> bug is that the checksum calculated in rep_read_contents is not
> finalized.
>
> Myria writes:
>
> > During rep_write_contents_close, there is a call to get_shared_rep.
> > get_shared_rep calls svn_fs_fs__get_contents_from_file, which has the
> > code pasted below.
> >
> >
> > /* Build the representation list (delta chain). */
> > if (rh->type == svn_fs_fs__rep_plain)
> > {
> > rb->rs_list = apr_array_make(pool, 0, sizeof(rep_state_t *));
> > rb->src_state = rs;
> > }
> > else if (rh->type == svn_fs_fs__rep_self_delta)
> > {
> > rb->rs_list = apr_array_make(pool, 1, sizeof(rep_state_t *));
> > APR_ARRAY_PUSH(rb->rs_list, rep_state_t *) = rs;
> > rb->src_state = NULL;
> > }
> > else
> > {
> > representation_t next_rep = { 0 };
> >
> > /* skip "SVNx" diff marker */
> > rs->current = 4;
> >
> > /* REP's base rep is inside a proper revision.
> >* It can be reconstructed in the usual way. */
> > next_rep.revision = rh->base_revision;
> > next_rep.item_index = rh->base_item_index;
> > next_rep.size = rh->base_length;
> > svn_fs_fs__id_txn_reset(&next_rep.txn_id);
> >
> > SVN_ERR(build_rep_list(&rb->rs_list, &rb->base_window,
> > &rb->src_state, &rb->len, rb->fs, &next_rep,
> > rb->filehandle_pool));
> >
> >
> > The bug is occurring because build_rep_list is being called with
> > first_rep->expanded_size set to zero. Well, the reason it's zero is
> > because first_rep is the second to last parameter to build_rep_list,
> > and the above code initialized expanded_size to zero:
> >
> > representation_t next_rep = { 0 };
> >
> > Does the code just need this? I don't know this call >.<
> >
> > next_rep.expanded_size = rb->rep.expanded_size;
> >
> > Melissa
> >
> > On Wed, Mar 7, 2018 at 9:02 AM, Nathan Hartman
> > wrote:
> >> On Mar 5, 2018, at 10:54 PM, Myria wrote:
> >>>
> >>> Final email for the night >.<
> >>>
> >>> What's clobbering the expanded_size is this in build_rep_list:
> >>>
> >>> /* The value as stored in the data struct.
> >>> 0 is either for unknown length or actually zero length. */
> >>> *expanded_size = first_rep->expanded_size;
> >>>
> >>> first_rep->expanded_size here is zero for the last call to this
> >>> function before the error. In every other case before the error, the
> >>> two values are equal.
> >>>
> >>> Then this code executes:
> >>>
> >>> if (*expanded_size == 0)
> >>>if (rep_header->type == svn_fs_fs__rep_plain || first_rep->size != 4)
> >>> *expanded_size = first_rep->size;
> >>>
> >>> first_rep->size is 16384, and this is why rb->len becomes 16384,
> >>> leading to the error.
> >>>
> >>> I don't know what all this code is doing, but that's the proximate
> >>> cause of the failure.
> >>>
> >>> Melissa
> >>
> >> Has it been possible to determine what is setting expanded_size to 0
> >> before that last call? I wonder if there is specific logic that
> >> decides (perhaps incorrectly?) to do that?
> >>
> >> Alternatively is it being clobbered by some out-of-bounds access,
> >> use-after-free, or another such issue?
> >>
> >> Is it possible in your debugger setup to determine the address of
> >> that variable and set a breakpoint that triggers when that memory is
> >> written? (It may be called a watchpoint?)
> >>
> >> Which leads me to another thought: if you can set such a breakpoint
> >> / watchpoint and it does not trigger, then this expanded_size might
> >> not be the same instance in that final call. Perhaps a shallow copy
> >> of an enclosing structure is made which leaves out the known size
> >> and sets it to 0 for some reason, and that final call is given that
> >> (incomplete) copy.
> >>
> >> Caveat: I am not familiar with the codebase but these are my
> >> thoughts based on adventures in other code bases.
> >>
> >
>
> --
> Philip
Re: SHA-1 collision in repository?
Philip Martin writes: > https://issues.apache.org/jira/browse/SVN-4722 I've proposed a fix in STATUS. -- Philip
Re: SHA-1 collision in repository?
Nathan Hartman writes: > Is it possible and does it make sense to always continue reading until > EOF, when the read is either 0 or < 16k? In other words to eliminate > the comparison against the expanded size? I believe setting the expanded size correctly is the only fix we need. > Alternatively, if reading up to the expanded size and then stopping, > does it make sense to attempt another read, which must come back as 0, > to verify that the expanded size and actual size are equal? If not > equal, an error message on this issue would be far more helpful than > the one currently output. Not sure. The caller often does just that but that essentially just involves: if (rb->off == rb->len) *len = 0; and trivially returns 0. I suppose we could make a call to data extraction functions but I don't know how that would behave. I am reluctant to do it on a release branch. There is one additional check we should add, on trunk at least. This code was originally written as a read_fn for an svn_stream_t and thus had to allow short reads. It is now a read_full_fn and the only short read is at EOF, so we should verify the expanded size on a short read. > Have you had a chance to test against the 1.10 rc? The trunk/1.10 code has been reworked and, as far as I can tell, the bug is not present. -- Philip
Re: SHA-1 collision in repository?
On Wed, Mar 7, 2018 at 10:37 PM, Philip Martin wrote: > > The cause of the bug, as identified by Melissa, is that the wrong > expanded size if computed -- it gets set to the size of the delta in the > protorev file. The svn_stream_t that is producing the fulltext works in > 16K chunks, so the total amout of fulltext goes up in steps: 16K, 32K, > 48K, etc. If one of those steps happens to match the erroneous expanded > size the stream treats that as the end of the fulltext. The stream then > finalizes the MD5 checksum for the partial fulltext and the MD5 checksum > failure occurs. > > For most commits the protorev delta is not a multiple of 16K and so the > erroneous expanded size does not match any of the fulltext steps. > Eventually the stream reaches EOF and gets a short read less than 16K. > The function svn_stream_contents_same2 recognises the short read as EOF > and ends the comparison between the two streams, however the stream > itself has not finalized the checksum because of the length mismatch. > This means we did not verify the MD5 checksum for the protorev fulltext > but we did verify that the protorev fulltext matches the fulltext in the > repository. > Is it possible and does it make sense to always continue reading until EOF, when the read is either 0 or < 16k? In other words to eliminate the comparison against the expanded size? Alternatively, if reading up to the expanded size and then stopping, does it make sense to attempt another read, which must come back as 0, to verify that the expanded size and actual size are equal? If not equal, an error message on this issue would be far more helpful than the one currently output. On Thu, Mar 8, 2018 at 6:41 AM, Philip Martin wrote: > > https://issues.apache.org/jira/browse/SVN-4722 > > My reproduction doesn't trigger the bug in 1.8 but that seems to be > because 1.8 has some other problem and the rep-cache deduplication > doesn't trigger. The third commit restoring the content in the first > commit simply stores a new delta. > Have you had a chance to test against the 1.10 rc?
Re: SHA-1 collision in repository?
Julian Foad writes: > Please would you file this issue in the issue tracker so I can give > outsiders a reference to it? https://issues.apache.org/jira/browse/SVN-4722 My reproduction doesn't trigger the bug in 1.8 but that seems to be because 1.8 has some other problem and the rep-cache deduplication doesn't trigger. The third commit restoring the content in the first commit simply stores a new delta. -- Philip
Re: SHA-1 collision in repository?
Please would you file this issue in the issue tracker so I can give outsiders a reference to it? - Julian Philip Martin wrote: Philip Martin writes: svn cat http://svn.apache.org/repos/asf/subversion/trunk/INSTALL@1826165 > f1 (for i in `seq 0 8712`;do echo -n $i;done && echo -n 1) > f1 svnadmin create repo svnmucc -mm -U file://`pwd`/repo put f1 f svnmucc -mm -U file://`pwd`/repo put f2 2 svnmucc -mm -U file://`pwd`/repo put f1 f Oops again! All three commits should be to destination 'f'. svn cat http://svn.apache.org/repos/asf/subversion/trunk/INSTALL@1826165 > f1 (for i in `seq 0 8712`;do echo -n $i;done && echo -n 1) > f2 svnadmin create repo svnmucc -mm -U file://`pwd`/repo put f1 f svnmucc -mm -U file://`pwd`/repo put f2 f svnmucc -mm -U file://`pwd`/repo put f1 f The cause of the bug, as identified by Melissa, is that the wrong expanded size if computed -- it gets set to the size of the delta in the protorev file. The svn_stream_t that is producing the fulltext works in 16K chunks, so the total amout of fulltext goes up in steps: 16K, 32K, 48K, etc. If one of those steps happens to match the erroneous expanded size the stream treats that as the end of the fulltext. The stream then finalizes the MD5 checksum for the partial fulltext and the MD5 checksum failure occurs. For most commits the protorev delta is not a multiple of 16K and so the erroneous expanded size does not match any of the fulltext steps. Eventually the stream reaches EOF and gets a short read less than 16K. The function svn_stream_contents_same2 recognises the short read as EOF and ends the comparison between the two streams, however the stream itself has not finalized the checksum because of the length mismatch. This means we did not verify the MD5 checksum for the protorev fulltext but we did verify that the protorev fulltext matches the fulltext in the repository.
Re: SHA-1 collision in repository?
Please would you file this issue in the issue tracker so I can give outsiders a reference to it? - Julian Philip Martin wrote: Philip Martin writes: svn cat http://svn.apache.org/repos/asf/subversion/trunk/INSTALL@1826165 > f1 (for i in `seq 0 8712`;do echo -n $i;done && echo -n 1) > f1 svnadmin create repo svnmucc -mm -U file://`pwd`/repo put f1 f svnmucc -mm -U file://`pwd`/repo put f2 2 svnmucc -mm -U file://`pwd`/repo put f1 f Oops again! All three commits should be to destination 'f'. svn cat http://svn.apache.org/repos/asf/subversion/trunk/INSTALL@1826165 > f1 (for i in `seq 0 8712`;do echo -n $i;done && echo -n 1) > f2 svnadmin create repo svnmucc -mm -U file://`pwd`/repo put f1 f svnmucc -mm -U file://`pwd`/repo put f2 f svnmucc -mm -U file://`pwd`/repo put f1 f The cause of the bug, as identified by Melissa, is that the wrong expanded size if computed -- it gets set to the size of the delta in the protorev file. The svn_stream_t that is producing the fulltext works in 16K chunks, so the total amout of fulltext goes up in steps: 16K, 32K, 48K, etc. If one of those steps happens to match the erroneous expanded size the stream treats that as the end of the fulltext. The stream then finalizes the MD5 checksum for the partial fulltext and the MD5 checksum failure occurs. For most commits the protorev delta is not a multiple of 16K and so the erroneous expanded size does not match any of the fulltext steps. Eventually the stream reaches EOF and gets a short read less than 16K. The function svn_stream_contents_same2 recognises the short read as EOF and ends the comparison between the two streams, however the stream itself has not finalized the checksum because of the length mismatch. This means we did not verify the MD5 checksum for the protorev fulltext but we did verify that the protorev fulltext matches the fulltext in the repository.
Re: SHA-1 collision in repository?
Philip Martin writes: > svn cat http://svn.apache.org/repos/asf/subversion/trunk/INSTALL@1826165 > f1 > (for i in `seq 0 8712`;do echo -n $i;done && echo -n 1) > f1 > svnadmin create repo > svnmucc -mm -U file://`pwd`/repo put f1 f > svnmucc -mm -U file://`pwd`/repo put f2 2 > svnmucc -mm -U file://`pwd`/repo put f1 f Oops again! All three commits should be to destination 'f'. svn cat http://svn.apache.org/repos/asf/subversion/trunk/INSTALL@1826165 > f1 (for i in `seq 0 8712`;do echo -n $i;done && echo -n 1) > f2 svnadmin create repo svnmucc -mm -U file://`pwd`/repo put f1 f svnmucc -mm -U file://`pwd`/repo put f2 f svnmucc -mm -U file://`pwd`/repo put f1 f The cause of the bug, as identified by Melissa, is that the wrong expanded size if computed -- it gets set to the size of the delta in the protorev file. The svn_stream_t that is producing the fulltext works in 16K chunks, so the total amout of fulltext goes up in steps: 16K, 32K, 48K, etc. If one of those steps happens to match the erroneous expanded size the stream treats that as the end of the fulltext. The stream then finalizes the MD5 checksum for the partial fulltext and the MD5 checksum failure occurs. For most commits the protorev delta is not a multiple of 16K and so the erroneous expanded size does not match any of the fulltext steps. Eventually the stream reaches EOF and gets a short read less than 16K. The function svn_stream_contents_same2 recognises the short read as EOF and ends the comparison between the two streams, however the stream itself has not finalized the checksum because of the length mismatch. This means we did not verify the MD5 checksum for the protorev fulltext but we did verify that the protorev fulltext matches the fulltext in the repository. -- Philip
Re: SHA-1 collision in repository?
Philip Martin writes: > (for i in `seq 0 8712`;do echo -n $i;done && echo -n 1) > f1 Oops, that should be > f2 -- Philip
Re: SHA-1 collision in repository?
Nathan Hartman writes: > That makes me wonder why this has not triggered more frequently for > users? Is there some obscure set of circumstances that triggers this > code path in this particular way? If so, can a test be added to the > test suite to prevent this sort of thing from slipping in again? When the client sends a file it sends either a delta or a fulltext. The backend reconstructs the fulltext and then computes a new delta as a candidate to be stored in the repository. This delta gets written to the protorev file and if the length of the delta is a multiple of 16384 then the bug occurs. After a bit of playing around I've got a test case: svn cat http://svn.apache.org/repos/asf/subversion/trunk/INSTALL@1826165 > f1 (for i in `seq 0 8712`;do echo -n $i;done && echo -n 1) > f1 svnadmin create repo svnmucc -mm -U file://`pwd`/repo put f1 f svnmucc -mm -U file://`pwd`/repo put f2 2 svnmucc -mm -U file://`pwd`/repo put f1 f The third commit fails: svnmucc: E16: SHA1 of reps '1 0 17791 55700 df5d0e251e4b811f0ed63694e7a2cd00 fb07bf4d765ccf4e18afe74d559f3b16f916a1e1 2-2/_1' and '-1 0 17793 55700 df5d0e251e4b811f0ed63694e7a2cd00 fb07bf4d765ccf4e18afe74d559f3b16f916a1e1 2-2/_1' matches (fb07bf4d765ccf4e18afe74d559f3b16f916a1e1) but contents differ svnmucc: E160004: Filesystem is corrupt svnmucc: E200014: Checksum mismatch while reading representation: expected: df5d0e251e4b811f0ed63694e7a2cd00 actual: c833ae35c9e02f2b4069d3b1a31d4de0 If you look at the protorev in the failed transaction it starts: $ od -c repo/db/txn-protorevs/2-2.rev | head -1 000 D E L T A 2 0 1 6 3 8 4 \n -- Philip
Re: SHA-1 collision in repository?
On Mar 7, 2018, at 6:18 PM, Philip Martin wrote:
>
> [Moving this to the dev@s.a.o list.]
>
> Well done! It looks like you have identified a serious bug here. The
> function svn_fs_fs__get_contents_from_file() that was recently added to
> 1.9 for the SHA1 collision detection so the code is new and it is also
> different from that on trunk.
>
> Your proposed fix looks like it might be correct, although rb->rep is
> just rep so it could be a bit simpler. One other consequence of this
> bug is that the checksum calculated in rep_read_contents is not
> finalized.
>
> Myria writes:
>
>> During rep_write_contents_close, there is a call to get_shared_rep.
>> get_shared_rep calls svn_fs_fs__get_contents_from_file, which has the
>> code pasted below.
>>
>>
>> /* Build the representation list (delta chain). */
>> if (rh->type == svn_fs_fs__rep_plain)
>>{
>> rb->rs_list = apr_array_make(pool, 0, sizeof(rep_state_t *));
>> rb->src_state = rs;
>>}
>> else if (rh->type == svn_fs_fs__rep_self_delta)
>>{
>> rb->rs_list = apr_array_make(pool, 1, sizeof(rep_state_t *));
>> APR_ARRAY_PUSH(rb->rs_list, rep_state_t *) = rs;
>> rb->src_state = NULL;
>>}
>> else
>>{
>> representation_t next_rep = { 0 };
>>
>> /* skip "SVNx" diff marker */
>> rs->current = 4;
>>
>> /* REP's base rep is inside a proper revision.
>> * It can be reconstructed in the usual way. */
>> next_rep.revision = rh->base_revision;
>> next_rep.item_index = rh->base_item_index;
>> next_rep.size = rh->base_length;
>> svn_fs_fs__id_txn_reset(&next_rep.txn_id);
>>
>> SVN_ERR(build_rep_list(&rb->rs_list, &rb->base_window,
>> &rb->src_state, &rb->len, rb->fs, &next_rep,
>> rb->filehandle_pool));
>>
>>
>> The bug is occurring because build_rep_list is being called with
>> first_rep->expanded_size set to zero. Well, the reason it's zero is
>> because first_rep is the second to last parameter to build_rep_list,
>> and the above code initialized expanded_size to zero:
>>
>> representation_t next_rep = { 0 };
>>
>> Does the code just need this? I don't know this call >.<
>>
>> next_rep.expanded_size = rb->rep.expanded_size;
>>
>> Melissa
>>
>>> On Wed, Mar 7, 2018 at 9:02 AM, Nathan Hartman
>>> wrote:
On Mar 5, 2018, at 10:54 PM, Myria wrote:
Final email for the night >.<
What's clobbering the expanded_size is this in build_rep_list:
/* The value as stored in the data struct.
0 is either for unknown length or actually zero length. */
*expanded_size = first_rep->expanded_size;
first_rep->expanded_size here is zero for the last call to this
function before the error. In every other case before the error, the
two values are equal.
Then this code executes:
if (*expanded_size == 0)
if (rep_header->type == svn_fs_fs__rep_plain || first_rep->size != 4)
*expanded_size = first_rep->size;
first_rep->size is 16384, and this is why rb->len becomes 16384,
leading to the error.
I don't know what all this code is doing, but that's the proximate
cause of the failure.
Melissa
>>>
>>> Has it been possible to determine what is setting expanded_size to 0
>>> before that last call? I wonder if there is specific logic that
>>> decides (perhaps incorrectly?) to do that?
>>>
>>> Alternatively is it being clobbered by some out-of-bounds access,
>>> use-after-free, or another such issue?
>>>
>>> Is it possible in your debugger setup to determine the address of
>>> that variable and set a breakpoint that triggers when that memory is
>>> written? (It may be called a watchpoint?)
>>>
>>> Which leads me to another thought: if you can set such a breakpoint
>>> / watchpoint and it does not trigger, then this expanded_size might
>>> not be the same instance in that final call. Perhaps a shallow copy
>>> of an enclosing structure is made which leaves out the known size
>>> and sets it to 0 for some reason, and that final call is given that
>>> (incomplete) copy.
>>>
>>> Caveat: I am not familiar with the codebase but these are my
>>> thoughts based on adventures in other code bases.
>>>
>>
>
> --
> Philip
Congrats for finding that!
It looks like this falls under the "shallow copy ... which leaves out the known
size" possibility I surmised about earlier, in which case it is zero because
the enclosing structure was previously memset()ed to 0 and this field was not
assigned.
That makes me wonder why this has not triggered more frequently for users? Is
there some obscure set of circumstances that triggers this code path in this
particular way? If so, can a test be added to the test suite to prevent this
sort of thing from slipping in again?
In what way is the code different on trunk?
Re: SHA-1 collision in repository?
[Moving this to the dev@s.a.o list.]
Well done! It looks like you have identified a serious bug here. The
function svn_fs_fs__get_contents_from_file() that was recently added to
1.9 for the SHA1 collision detection so the code is new and it is also
different from that on trunk.
Your proposed fix looks like it might be correct, although rb->rep is
just rep so it could be a bit simpler. One other consequence of this
bug is that the checksum calculated in rep_read_contents is not
finalized.
Myria writes:
> During rep_write_contents_close, there is a call to get_shared_rep.
> get_shared_rep calls svn_fs_fs__get_contents_from_file, which has the
> code pasted below.
>
>
> /* Build the representation list (delta chain). */
> if (rh->type == svn_fs_fs__rep_plain)
> {
> rb->rs_list = apr_array_make(pool, 0, sizeof(rep_state_t *));
> rb->src_state = rs;
> }
> else if (rh->type == svn_fs_fs__rep_self_delta)
> {
> rb->rs_list = apr_array_make(pool, 1, sizeof(rep_state_t *));
> APR_ARRAY_PUSH(rb->rs_list, rep_state_t *) = rs;
> rb->src_state = NULL;
> }
> else
> {
> representation_t next_rep = { 0 };
>
> /* skip "SVNx" diff marker */
> rs->current = 4;
>
> /* REP's base rep is inside a proper revision.
>* It can be reconstructed in the usual way. */
> next_rep.revision = rh->base_revision;
> next_rep.item_index = rh->base_item_index;
> next_rep.size = rh->base_length;
> svn_fs_fs__id_txn_reset(&next_rep.txn_id);
>
> SVN_ERR(build_rep_list(&rb->rs_list, &rb->base_window,
> &rb->src_state, &rb->len, rb->fs, &next_rep,
> rb->filehandle_pool));
>
>
> The bug is occurring because build_rep_list is being called with
> first_rep->expanded_size set to zero. Well, the reason it's zero is
> because first_rep is the second to last parameter to build_rep_list,
> and the above code initialized expanded_size to zero:
>
> representation_t next_rep = { 0 };
>
> Does the code just need this? I don't know this call >.<
>
> next_rep.expanded_size = rb->rep.expanded_size;
>
> Melissa
>
> On Wed, Mar 7, 2018 at 9:02 AM, Nathan Hartman
> wrote:
>> On Mar 5, 2018, at 10:54 PM, Myria wrote:
>>>
>>> Final email for the night >.<
>>>
>>> What's clobbering the expanded_size is this in build_rep_list:
>>>
>>> /* The value as stored in the data struct.
>>> 0 is either for unknown length or actually zero length. */
>>> *expanded_size = first_rep->expanded_size;
>>>
>>> first_rep->expanded_size here is zero for the last call to this
>>> function before the error. In every other case before the error, the
>>> two values are equal.
>>>
>>> Then this code executes:
>>>
>>> if (*expanded_size == 0)
>>>if (rep_header->type == svn_fs_fs__rep_plain || first_rep->size != 4)
>>> *expanded_size = first_rep->size;
>>>
>>> first_rep->size is 16384, and this is why rb->len becomes 16384,
>>> leading to the error.
>>>
>>> I don't know what all this code is doing, but that's the proximate
>>> cause of the failure.
>>>
>>> Melissa
>>
>> Has it been possible to determine what is setting expanded_size to 0
>> before that last call? I wonder if there is specific logic that
>> decides (perhaps incorrectly?) to do that?
>>
>> Alternatively is it being clobbered by some out-of-bounds access,
>> use-after-free, or another such issue?
>>
>> Is it possible in your debugger setup to determine the address of
>> that variable and set a breakpoint that triggers when that memory is
>> written? (It may be called a watchpoint?)
>>
>> Which leads me to another thought: if you can set such a breakpoint
>> / watchpoint and it does not trigger, then this expanded_size might
>> not be the same instance in that final call. Perhaps a shallow copy
>> of an enclosing structure is made which leaves out the known size
>> and sets it to 0 for some reason, and that final call is given that
>> (incomplete) copy.
>>
>> Caveat: I am not familiar with the codebase but these are my
>> thoughts based on adventures in other code bases.
>>
>
--
Philip
