Opened 4 years ago

Closed 4 years ago

#17776 closed defect (fixed)

Buffer over-reads in directory and rendcache tests

Reported by: cypherpunks Owned by: cypherpunks
Priority: Medium Milestone: Tor: 0.2.8.x-final
Component: Core Tor/Tor Version: Tor: 0.2.7.3-rc
Severity: Normal Keywords: TorCoreTeam201512
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

Some of the directory and rendcache tests contain buffer over-reads caused by using strings that are too short.

Child Tickets

Attachments (6)

Change History (17)

Changed 4 years ago by cypherpunks

Changed 4 years ago by cypherpunks

comment:1 Changed 4 years ago by cypherpunks

Status: newneeds_review

The attached patches fixes the issues mentioned in the ticket description. I hope the commit messages speak for themselves. Rewriting them into the ticket seemed redundant.

Patch 0003 is not related to this ticket other than that i found it while working on this ticket. I can open a separate ticket for it if that is preferred.

comment:2 in reply to:  1 Changed 4 years ago by teor

Status: needs_reviewneeds_revision

Replying to cypherpunks:

The attached patches fixes the issues mentioned in the ticket description. I hope the commit messages speak for themselves. Rewriting them into the ticket seemed redundant.

Code Review: Patches 1 & 2

I agree that these buffer overruns need to be fixed.

But what I'd like to do is change the functions that overrun the buffers so they don't overrun buffers if a short string is passed to them. That way, we fix the problem at the source.

I want to check that the fingerprint strings are:

  • not NULL, and
  • don't contain a NULL character in the first DIGEST_LEN bytes?

before the functions read the strings?

You can use code like:

tor_assert(fingerprint); 
tor_assert(memchr(fingerprint, 0, DIGEST_LEN) == NULL);

That would also require updating all the test data so it's really DIGEST_LEN characters long (and increasing the buffer lengths by 1 to accommodate the terminating nul byte).

Patch 0003 is not related to this ticket other than that i found it while working on this ticket. I can open a separate ticket for it if that is preferred.

Separate commits is great (and sufficient).

Code Review: Patch 3

Patch 0003 removes an unnecessary cast, let's merge Patch 3 only.

comment:3 Changed 4 years ago by teor

Keywords: TorCoreTeam201512 added
Milestone: Tor: 0.2.8.x-final
Version: Tor: unspecifiedTor: 0.2.7.3-rc

Patches 1 & 2 are on unit tests introduced in 0.2.7.3-rc.
(The functions being tested are a lot older than that.)

comment:4 in reply to:  3 ; Changed 4 years ago by cypherpunks

Replying to teor:

Replying to cypherpunks:

The attached patches fixes the issues mentioned in the ticket description. I hope the commit messages speak for themselves. Rewriting them into the ticket seemed redundant.

Code Review: Patches 1 & 2

I agree that these buffer overruns need to be fixed.

But what I'd like to do is change the functions that overrun the buffers so they don't overrun buffers if a short string is passed to them. That way, we fix the problem at the source.

I want to check that the fingerprint strings are:

  • not NULL, and
  • don't contain a NULL character in the first DIGEST_LEN bytes?

before the functions read the strings?

You can use code like:

tor_assert(fingerprint); 
tor_assert(memchr(fingerprint, 0, DIGEST_LEN) == NULL);

That would also require updating all the test data so it's really DIGEST_LEN characters long (and increasing the buffer lengths by 1 to accommodate the terminating nul byte).

The bugs were found using AddressSanitizer and i think the memchr solution will trigger similar warnings because the behavior is undefined if access occurs beyond the end of the array searched.

The assertion implies that the digests are required to be null-terminated strings. This moves away from the requirement that they need to be DIGEST_LEN long and is something which could be ignored in a similar fashion.

The solution IMO would be to require string length parameters (like the modern C string functions).

Replying to teor:

Patches 1 & 2 are on unit tests introduced in 0.2.7.3-rc.
(The functions being tested are a lot older than that.)

The commit messages of patches 1 and 2 include the commits which introduced the issues. According to git describe --contains both commits are not within in a tag. Is this correct?

comment:5 in reply to:  4 ; Changed 4 years ago by teor

Replying to cypherpunks:

Replying to teor:

Replying to cypherpunks:

The attached patches fixes the issues mentioned in the ticket description. I hope the commit messages speak for themselves. Rewriting them into the ticket seemed redundant.

Code Review: Patches 1 & 2

I agree that these buffer overruns need to be fixed.

But what I'd like to do is change the functions that overrun the buffers so they don't overrun buffers if a short string is passed to them. That way, we fix the problem at the source.

I want to check that the fingerprint strings are:

  • not NULL, and
  • don't contain a NULL character in the first DIGEST_LEN bytes?

before the functions read the strings?

You can use code like:

tor_assert(fingerprint); 
tor_assert(memchr(fingerprint, 0, DIGEST_LEN) == NULL);

That would also require updating all the test data so it's really DIGEST_LEN characters long (and increasing the buffer lengths by 1 to accommodate the terminating nul byte).

The bugs were found using AddressSanitizer and i think the memchr solution will trigger similar warnings because the behavior is undefined if access occurs beyond the end of the array searched.

memchr(fingerprint, 0, DIGEST_LEN) will never access any byte in fingerprint beyond a nul byte or DIGEST_LEN bytes. (Whichever comes first.)

The assertion implies that the digests are required to be null-terminated strings. This moves away from the requirement that they need to be DIGEST_LEN long and is something which could be ignored in a similar fashion.

The assertion is intended to catch code which passes strings shorter than DIGEST_LEN to the function. (We will need to comment it to make this clear.)

Buffers passed to the function should never contain a nul byte in the first DIGEST_LEN bytes. If they do, it's because someone passed a short string to the function. (As you've noticed, this is easy to do.)

Since there's no way to find the length of the memory pointed to by a pointer in C, our best option is to look for evidence that someone passed in a short buffer.

The solution IMO would be to require string length parameters (like the modern C string functions).

The buffer is a set-length non-nul terminated block of memory.
Any string length parameter would always be DIGEST_LEN, so it's redundant. (And it would imply that the buffers need to be nul-terminated, which they don't.)

Replying to teor:

Patches 1 & 2 are on unit tests introduced in 0.2.7.3-rc.
(The functions being tested are a lot older than that.)

The commit messages of patches 1 and 2 include the commits which introduced the issues. According to git describe --contains both commits are not within in a tag. Is this correct?

I don't know how this feature of git works.
I think we tag the commit that finalises a release. We don't tag all commits in a release.

When I look for the release that contains a commit, I look for the first release commit after that commit in git log.

comment:6 in reply to:  5 ; Changed 4 years ago by cypherpunks

Replying to teor:

Replying to cypherpunks:

Replying to teor:

Replying to cypherpunks:

The attached patches fixes the issues mentioned in the ticket description. I hope the commit messages speak for themselves. Rewriting them into the ticket seemed redundant.

Code Review: Patches 1 & 2

I agree that these buffer overruns need to be fixed.

But what I'd like to do is change the functions that overrun the buffers so they don't overrun buffers if a short string is passed to them. That way, we fix the problem at the source.

I want to check that the fingerprint strings are:

  • not NULL, and
  • don't contain a NULL character in the first DIGEST_LEN bytes?

before the functions read the strings?

You can use code like:

tor_assert(fingerprint); 
tor_assert(memchr(fingerprint, 0, DIGEST_LEN) == NULL);

That would also require updating all the test data so it's really DIGEST_LEN characters long (and increasing the buffer lengths by 1 to accommodate the terminating nul byte).

The bugs were found using AddressSanitizer and i think the memchr solution will trigger similar warnings because the behavior is undefined if access occurs beyond the end of the array searched.

memchr(fingerprint, 0, DIGEST_LEN) will never access any byte in fingerprint beyond a nul byte or DIGEST_LEN bytes. (Whichever comes first.)

Unless the fingerprint isn't null-terminated and adjacent memory happens to contain random data with a null-byte exactly at DIGEST_LEN+1. This would both be undefined behavior because it over-reads and it would see the fingerprint as being of valid length which it isn't.

The assertion implies that the digests are required to be null-terminated strings. This moves away from the requirement that they need to be DIGEST_LEN long and is something which could be ignored in a similar fashion.

The assertion is intended to catch code which passes strings shorter than DIGEST_LEN to the function. (We will need to comment it to make this clear.)

I agree the comments on the related functions need to be clearer regarding the expected buffer length.

Buffers passed to the function should never contain a nul byte in the first DIGEST_LEN bytes. If they do, it's because someone passed a short string to the function. (As you've noticed, this is easy to do.)

Since there's no way to find the length of the memory pointed to by a pointer in C, our best option is to look for evidence that someone passed in a short buffer.

I agree with this, but i would like to do it in a way that doesn't leave the door open for other issues.

The solution IMO would be to require string length parameters (like the modern C string functions).

The buffer is a set-length non-nul terminated block of memory.
Any string length parameter would always be DIGEST_LEN, so it's redundant. (And it would imply that the buffers need to be nul-terminated, which they don't.)

I agree that it is redundant so maybe it is not a good solution, but it does not imply the buffers are null-terminated. On the contrary, it implies the buffer are not null-terminated hence why we need the length as a separate parameter.

Replying to teor:

Patches 1 & 2 are on unit tests introduced in 0.2.7.3-rc.
(The functions being tested are a lot older than that.)

The commit messages of patches 1 and 2 include the commits which introduced the issues. According to git describe --contains both commits are not within in a tag. Is this correct?

I don't know how this feature of git works.
I think we tag the commit that finalises a release. We don't tag all commits in a release.

When I look for the release that contains a commit, I look for the first release commit after that commit in git log.

After as in below it? Because that would mean the commit is not included in that release as git log usually goes back in time starting from the top. To quote the git manual on git describe --contains

--contains
           Instead of finding the tag that predates the commit, find the tag
           that comes after the commit, and thus contains it.

Finally, maybe i am overthinking the solution but i feel the proposed memchr assertion does not prevent all corner cases from occurring (as the first part of this reply explains). It introduces issues of its own. In search of other solutions i have looked at other parts of the Tor code base such as the crypto_digest* functions. These functions assume the digest buffer is large enough because they have no way of verifying it and all they do is assert the digest pointer isn't NULL. I know these are write operations on a buffer instead of read operations on a buffer, but the core question is the same; what if the buffer is too short? These functions do not care.

With this knowledge i like to update the proposed changes to be

  • assert the pointer to the buffer isn't NULL (same as proposed by teor)
  • do not assert that the buffer is too short (there is no proper way to do this)
  • update the comments on the related functions that the buffer should be DIGEST_LEN long (as there is no proper way to enforce it otherwise)

comment:7 in reply to:  6 ; Changed 4 years ago by teor

Replying to cypherpunks:

Replying to teor:

Replying to cypherpunks:

Replying to teor:

I want to check that the fingerprint strings are:

  • not NULL, and
  • don't contain a NULL character in the first DIGEST_LEN bytes?

before the functions read the strings?

You can use code like:

tor_assert(fingerprint); 
tor_assert(memchr(fingerprint, 0, DIGEST_LEN) == NULL);

That would also require updating all the test data so it's really DIGEST_LEN characters long (and increasing the buffer lengths by 1 to accommodate the terminating nul byte).

The bugs were found using AddressSanitizer and i think the memchr solution will trigger similar warnings because the behavior is undefined if access occurs beyond the end of the array searched.

memchr(fingerprint, 0, DIGEST_LEN) will never access any byte in fingerprint beyond a nul byte or DIGEST_LEN bytes. (Whichever comes first.)

Unless the fingerprint isn't null-terminated and adjacent memory happens to contain random data with a null-byte exactly at DIGEST_LEN+1. This would both be undefined behavior because it over-reads and it would see the fingerprint as being of valid length which it isn't.

This isn't how memchr works. It only ever reads "n" bytes, where "n" is its third argument. If we pass DIGEST_LEN for n, it will never read byte DIGEST_LEN + 1 under any circumstances. (But see my comments below for why this doesn't matter.)

Replying to teor:

Patches 1 & 2 are on unit tests introduced in 0.2.7.3-rc.
(The functions being tested are a lot older than that.)

The commit messages of patches 1 and 2 include the commits which introduced the issues. According to git describe --contains both commits are not within in a tag. Is this correct?

I don't know how this feature of git works.
I think we tag the commit that finalises a release. We don't tag all commits in a release.

When I look for the release that contains a commit, I look for the first release commit after that commit in git log.

After as in below it? Because that would mean the commit is not included in that release as git log usually goes back in time starting from the top. To quote the git manual on git describe --contains

--contains
           Instead of finding the tag that predates the commit, find the tag
           that comes after the commit, and thus contains it.

When I said "after", I meant "after in time", which is earlier in git log.

Finally, maybe i am overthinking the solution but i feel the proposed memchr assertion does not prevent all corner cases from occurring (as the first part of this reply explains). It introduces issues of its own. In search of other solutions i have looked at other parts of the Tor code base such as the crypto_digest* functions. These functions assume the digest buffer is large enough because they have no way of verifying it and all they do is assert the digest pointer isn't NULL. I know these are write operations on a buffer instead of read operations on a buffer, but the core question is the same; what if the buffer is too short? These functions do not care.

With this knowledge i like to update the proposed changes to be

  • assert the pointer to the buffer isn't NULL (same as proposed by teor)
  • do not assert that the buffer is too short (there is no proper way to do this)
  • update the comments on the related functions that the buffer should be DIGEST_LEN long (as there is no proper way to enforce it otherwise)

That sounds like a good idea. Let's do that.

comment:8 in reply to:  7 ; Changed 4 years ago by cypherpunks

Owner: set to cypherpunks
Status: needs_revisionassigned

Replying to teor:

Replying to cypherpunks:

Replying to teor:

Replying to cypherpunks:

Replying to teor:

I want to check that the fingerprint strings are:

  • not NULL, and
  • don't contain a NULL character in the first DIGEST_LEN bytes?

before the functions read the strings?

You can use code like:

tor_assert(fingerprint); 
tor_assert(memchr(fingerprint, 0, DIGEST_LEN) == NULL);

That would also require updating all the test data so it's really DIGEST_LEN characters long (and increasing the buffer lengths by 1 to accommodate the terminating nul byte).

The bugs were found using AddressSanitizer and i think the memchr solution will trigger similar warnings because the behavior is undefined if access occurs beyond the end of the array searched.

memchr(fingerprint, 0, DIGEST_LEN) will never access any byte in fingerprint beyond a nul byte or DIGEST_LEN bytes. (Whichever comes first.)

Unless the fingerprint isn't null-terminated and adjacent memory happens to contain random data with a null-byte exactly at DIGEST_LEN+1. This would both be undefined behavior because it over-reads and it would see the fingerprint as being of valid length which it isn't.

This isn't how memchr works. It only ever reads "n" bytes, where "n" is its third argument. If we pass DIGEST_LEN for n, it will never read byte DIGEST_LEN + 1 under any circumstances. (But see my comments below for why this doesn't matter.)

I believe my argument is still valid even when "n" is DIGEST_LEN (i did make a off-by-one error in my initial argument). Imagine if fingerprint has a length of 1 but that single character isn't a null-byte, memchr will then over-read until it finds a null-byte or has read DIGEST_LEN - 1 bytes of adjacent memory. I'm not trying to beat a dead horse or be defensive, just trying to explain the issue with memchr.

Replying to teor:

Patches 1 & 2 are on unit tests introduced in 0.2.7.3-rc.
(The functions being tested are a lot older than that.)

The commit messages of patches 1 and 2 include the commits which introduced the issues. According to git describe --contains both commits are not within in a tag. Is this correct?

I don't know how this feature of git works.
I think we tag the commit that finalises a release. We don't tag all commits in a release.

When I look for the release that contains a commit, I look for the first release commit after that commit in git log.

After as in below it? Because that would mean the commit is not included in that release as git log usually goes back in time starting from the top. To quote the git manual on git describe --contains

--contains
           Instead of finding the tag that predates the commit, find the tag
           that comes after the commit, and thus contains it.

When I said "after", I meant "after in time", which is earlier in git log.

Only with git log --reverse if you use the CLI implementation.

Finally, maybe i am overthinking the solution but i feel the proposed memchr assertion does not prevent all corner cases from occurring (as the first part of this reply explains). It introduces issues of its own. In search of other solutions i have looked at other parts of the Tor code base such as the crypto_digest* functions. These functions assume the digest buffer is large enough because they have no way of verifying it and all they do is assert the digest pointer isn't NULL. I know these are write operations on a buffer instead of read operations on a buffer, but the core question is the same; what if the buffer is too short? These functions do not care.

With this knowledge i like to update the proposed changes to be

  • assert the pointer to the buffer isn't NULL (same as proposed by teor)
  • do not assert that the buffer is too short (there is no proper way to do this)
  • update the comments on the related functions that the buffer should be DIGEST_LEN long (as there is no proper way to enforce it otherwise)

That sounds like a good idea. Let's do that.

Ok, i'll assign the ticket to this account then and implement these changes.

comment:9 in reply to:  8 Changed 4 years ago by teor

Replying to cypherpunks:

Replying to teor:

Replying to cypherpunks:

Replying to teor:

Replying to cypherpunks:

Replying to teor:

I want to check that the fingerprint strings are:

  • not NULL, and
  • don't contain a NULL character in the first DIGEST_LEN bytes?

before the functions read the strings?

You can use code like:

tor_assert(fingerprint); 
tor_assert(memchr(fingerprint, 0, DIGEST_LEN) == NULL);

That would also require updating all the test data so it's really DIGEST_LEN characters long (and increasing the buffer lengths by 1 to accommodate the terminating nul byte).

The bugs were found using AddressSanitizer and i think the memchr solution will trigger similar warnings because the behavior is undefined if access occurs beyond the end of the array searched.

memchr(fingerprint, 0, DIGEST_LEN) will never access any byte in fingerprint beyond a nul byte or DIGEST_LEN bytes. (Whichever comes first.)

Unless the fingerprint isn't null-terminated and adjacent memory happens to contain random data with a null-byte exactly at DIGEST_LEN+1. This would both be undefined behavior because it over-reads and it would see the fingerprint as being of valid length which it isn't.

This isn't how memchr works. It only ever reads "n" bytes, where "n" is its third argument. If we pass DIGEST_LEN for n, it will never read byte DIGEST_LEN + 1 under any circumstances. (But see my comments below for why this doesn't matter.)

I believe my argument is still valid even when "n" is DIGEST_LEN (i did make a off-by-one error in my initial argument). Imagine if fingerprint has a length of 1 but that single character isn't a null-byte, memchr will then over-read until it finds a null-byte or has read DIGEST_LEN - 1 bytes of adjacent memory. I'm not trying to beat a dead horse or be defensive, just trying to explain the issue with memchr.

I think we agree about how memchr works, and that it isn't a perfect solution.

comment:10 Changed 4 years ago by cypherpunks

Status: assignedneeds_review

Patch 5 updates the comments to mention the expected digest length. (Going to open a separate ticket about the intro_entry parameter staying untouched, because it isn't)

Turns out the rendcache functions that were tested in the code that patch 1 and 2 patches passes their parameters to the digest map functions. The digest map functions already assert for the map, the key, and the value not to be NULL so no extra asserts are needed here.

The dir_server_new function (which is used by trusted_dir_server_new) did miss one assert so patch 6 adds that.

comment:11 Changed 4 years ago by nickm

Resolution: fixed
Status: needs_reviewclosed

Merged the above; thanks!

Note: See TracTickets for help on using tickets.