Subject: bug#26545: closed (Re: bug#26545: shred: buffer overlap, some data not wiped)

From: [email-masked] (GNU bug Tracking System)
Date: Tue, 18 Apr 2017 02:51:02 +0000

Your bug report

#26545: shred: buffer overlap, some data not wiped

which was filed against the coreutils package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
26545: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=26545
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#26545: shred: buffer overlap, some data not wiped
From: Pádraig Brady <[email-masked]>
To: Bogdan <[email-masked]>, [email-masked]
Date: Mon, 17 Apr 2017 19:50:14 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

On 17/04/17 11:53, Bogdan wrote:
>  Hi.
> 
>  I believe I've found a bug in shred.c, function fillpattern(): there
> is code that says:
> 
>   for (i = 3; i < size / 2; i *= 2)
>     memcpy (r + i, r, i);
>   if (i < size)
>     memcpy (r + i, r, size - i);
> 
> The problem occurs for specific values of the "size" variable.
> Example: size = 7:
> 1) size / 2 = 3,
> 2) the "for" loop sets "i" to 3 and never runs (the condition is "3 <
> 3"), even though it could (there are 4 bytes left to be wiped now)
> 3) the "if" condition is true (3 < 7)
> 4) the memcpy call evaluates to
> 	memcpy (r + 3, r, 7 - 3)
>    in other words:
> 	memcpy (r + 3, r, 4)
> 
> Now, this poses a few problems:
> 
> 1) copying 4 bytes between areas separated by 3 bytes means that the
> areas overlap, which is forbidden for memcpy (results are not guaranteed),
> 
> 2) copying 4 bytes with only 3 of them wiped means potentially copying
> 1 byte of the original data (from byte 4 to byte 7) and leaving it there.
> 
>  I don't know if it's possible to get "size = 7" with the current code
> shape, but there may be other "problematic" values. May look like a
> small bug now, may become bigger later.

Very well spotted!
It's easy enough to trigger:

  touch blah
  shred -n4 -s7 blah

valgrind or ASAN will trigger failures due to this issue.

>  Anyway, I'm attaching a simple patch to fix this. The key change is
> to write "i * 2 < size" instead of "i < size / 2". Although
> mathematically equivalent, with C's integer arithmetic the latter one
> will truncate the results.
>  You may change left shifts to multiplications, if you wish, but if
> overflow happens, it will happen in both versions.
> 
>  Things to keep in mind for later:
> - size_t may be 32 bits wide, so watch out for buffers of 4GB or more
> (may happen one day? :) ),
> - if one day "size" could be any value (including 1 or 2), buffer
> overflow will happen.

These overflow issues can be avoided by just changing the < to <=.
I've not noted the issue in NEWS since it really is edge case stuff
not practically relevant to users, especially considering there
is always a random pass written after the patterns.

I've updated your patch in the attached and will push later.

thanks,
Pádraig
From f4570a9ed6a4a3d9698093d5c9388c59d454d1dd Mon Sep 17 00:00:00 2001
From: Bogdan Drozdowski <[email-masked]>
Date: Mon, 17 Apr 2017 19:04:01 -0700
Subject: [PATCH] shred: fix invalid pattern generation for certain sizes

* src/shred.c (fillpattern): Fix the "off by one" issue when
testing whether we have enough space to copy the already
written portion of the buffer to the remainder of the buffer.
Specifically for buffer sizes that are (3*(2^x))+1, i.e. 7,13,...
we both use an uninitialized byte and invoke undefined
behavior in memcpy() operation on overlapping memory regions.
* tests/misc/shred-passes.sh: Add an invocation that will
trigger either valgrind UMR, or ASAN like:
  ERROR: AddressSanitizer: memcpy-param-overlap: memory ranges
  #1 0x403065 in fillpattern src/shred.c:293
A direct test is awkward due to the random writes surrounding
the problematic pattern writes.
Fixes http://bugs.gnu.org/26545
---
 src/shred.c                | 2 +-
 tests/misc/shred-passes.sh | 8 ++++++++
 2 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/src/shred.c b/src/shred.c
index a317c44..7926e7a 100644
--- a/src/shred.c
+++ b/src/shred.c
@@ -287,7 +287,7 @@ fillpattern (int type, unsigned char *r, size_t size)
   r[0] = (bits >> 4) & 255;
   r[1] = (bits >> 8) & 255;
   r[2] = bits & 255;
-  for (i = 3; i < size / 2; i *= 2)
+  for (i = 3; i <= size / 2; i *= 2)
     memcpy (r + i, r, i);
   if (i < size)
     memcpy (r + i, r, size - i);
diff --git a/tests/misc/shred-passes.sh b/tests/misc/shred-passes.sh
index e8fcb4f..1990115 100755
--- a/tests/misc/shred-passes.sh
+++ b/tests/misc/shred-passes.sh
@@ -79,5 +79,13 @@ shred: f: removed" > exp || framework_failure_
 shred -v -u -n20 -s4096 --random-source=Us f 2>out || fail=1
 compare exp out || fail=1
 
+# Trigger an issue in shred before v8.27 where single
+# bytes in the pattern space were not initialized correctly
+# for particular sizes, like 7,13,...
+# This failed under both valgrind and ASAN.
+for size in 1 2 6 7 8; do
+  touch shred.pattern.umr.size
+  shred -n4 -s$size shred.pattern.umr.size || fail=1
+done
 
 Exit $fail
-- 
2.9.3

Subject: shred: buffer overlap, some data not wiped
From: Bogdan <[email-masked]>
To: [email-masked]
Date: Mon, 17 Apr 2017 20:53:47 +0200
List-Id: <debbugs-submit.debbugs.gnu.org>

 Hi.

 I believe I've found a bug in shred.c, function fillpattern(): there
is code that says:

  for (i = 3; i < size / 2; i *= 2)
    memcpy (r + i, r, i);
  if (i < size)
    memcpy (r + i, r, size - i);

The problem occurs for specific values of the "size" variable.
Example: size = 7:
1) size / 2 = 3,
2) the "for" loop sets "i" to 3 and never runs (the condition is "3 <
3"), even though it could (there are 4 bytes left to be wiped now)
3) the "if" condition is true (3 < 7)
4) the memcpy call evaluates to
	memcpy (r + 3, r, 7 - 3)
   in other words:
	memcpy (r + 3, r, 4)

Now, this poses a few problems:

1) copying 4 bytes between areas separated by 3 bytes means that the
areas overlap, which is forbidden for memcpy (results are not guaranteed),

2) copying 4 bytes with only 3 of them wiped means potentially copying
1 byte of the original data (from byte 4 to byte 7) and leaving it there.

 I don't know if it's possible to get "size = 7" with the current code
shape, but there may be other "problematic" values. May look like a
small bug now, may become bigger later.

 Anyway, I'm attaching a simple patch to fix this. The key change is
to write "i * 2 < size" instead of "i < size / 2". Although
mathematically equivalent, with C's integer arithmetic the latter one
will truncate the results.
 You may change left shifts to multiplications, if you wish, but if
overflow happens, it will happen in both versions.

 Things to keep in mind for later:
- size_t may be 32 bits wide, so watch out for buffers of 4GB or more
(may happen one day? :) ),
- if one day "size" could be any value (including 1 or 2), buffer
overflow will happen.

-- 
Pozdrawiam/Regards - Bogdan                     (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux):            http://bogdro.evai.pl
Grupy dyskusyjne o asm:  pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.Xiph.org www.TorProject.org  Soft(EN): http://bogdro.evai.pl/soft
--- src/shred-orig.c	2017-04-17 17:49:51.877401171 +0200
+++ src/shred.c	2017-04-17 17:50:39.875382422 +0200
@@ -287,7 +287,7 @@
   r[0] = (bits >> 4) & 255;
   r[1] = (bits >> 8) & 255;
   r[2] = bits & 255;
-  for (i = 3; i < size / 2; i *= 2)
+  for (i = 3; (i << 1) < size; i <<= 1)
     memcpy (r + i, r, i);
   if (i < size)
     memcpy (r + i, r, size - i);