Re: Unaligned accesses in sha1dc

From

MÅMartin Ågren <martin.agren@gmail.com>

Date

Jun 1, 2017, 15:57 UTC

Message-ID

<CAN0heSp9DpW4_0QL57_oAHGu+os8k6yd=Z5+0MJnaL6iXTa-qQ@mail.gmail.com>

In-Reply-To

<CAN0heSrZcW3b6Osa8XNs0ghg2RE0ZS6FdPq8oPpwLcJjXAtLHg@mail.gmail.com>

On 1 June 2017 at 13:53, Martin Ågren <martin.agren@gmail.com> wrote:

> On 1 June 2017 at 12:33, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>> On Thu, Jun 1, 2017 at 12:26 PM, Martin Ågren <martin.agren@gmail.com> wrote:
>>> On 1 June 2017 at 12:08, Andreas Schwab <schwab@suse.de> wrote:
>>>> Even if the architecture implements unaligned accesses in hardware, it
>>>> is still undefined behaviour, and the compiler will (eventually) take
>>>> advantage of it.
>>>
>>> I tried to optically follow the macros and ended up on line 87/89 in
>>> lib/sha1.c of the sha1dc-library, where there is undefined behavior if
>>> the address is unaligned, which it seems it could be. Maybe Git uses
>>> some particular combination of macro-definitions and I went down the
>>> wrong path... There might also be other spots; I haven't thrown UBSan
>>> at the code.
>>>
>>> Using memcpy on those lines should not be a performance problem on
>>> platforms where unaligned access is ok, of course assuming the
>>> compiler sees the opportunity.
>>
>> This is what the upstream version of sha1dc now in the next branch
>> does, i.e. just does a memcpy() on platforms which aren't on a
>> whitelist of CPUs that allow unaligned access.
>
> Ok, now I get it. Undefined behavior can occur on line 1772 in
> sha1dc/sha1.c on "next", but only if SHA1DC_ALLOW_UNALIGNED_ACCESS is
> defined. I don't think the macro does what its name suggests, though.
> To me, it behaves more like
> SHA1DC_RELY_ON_UNDEFINED_BEHAVIOR_TO_DO_THE_RIGHT_THING_BY_CHANCE...
>
> So it seems the call chain of commands and macros could be redesigned
> to work with "char*" instead of "uint32_t*"... Then the lines I
> mentioned earlier could be converted to memcpy and "should" be
> compiled to efficient loads where possible. Yes, I know, patches speak
> for themselves, and no, this mail is not a patch.

diff --git a/Makefile b/Makefile
index 7c621f7..e3fdad0 100644
--- a/Makefile
+++ b/Makefile
@@ -402,7 +402,7 @@ GIT-VERSION-FILE: FORCE

 # CFLAGS and LDFLAGS are for the users to override from the command line.

-CFLAGS = -g -O2 -Wall
+CFLAGS = -g -O2 -Wall -fsanitize=undefined -fsanitize-recover=undefined
 DEVELOPER_CFLAGS = -Werror \
     -Wdeclaration-after-statement \
     -Wno-format-zero-length \
@@ -412,7 +412,7 @@ DEVELOPER_CFLAGS = -Werror \
     -Wstrict-prototypes \
     -Wunused \
     -Wvla
-LDFLAGS =
+LDFLAGS = -fsanitize=undefined -fsanitize-recover=undefined
 ALL_CFLAGS = $(CPPFLAGS) $(CFLAGS)
 ALL_LDFLAGS = $(LDFLAGS)
 STRIP ?= strip
diff --git a/t/helper/test-sha1.c b/t/helper/test-sha1.c
index a1c13f5..d4e1463 100644
--- a/t/helper/test-sha1.c
+++ b/t/helper/test-sha1.c
@@ -24,6 +24,8 @@ int cmd_main(int ac, const char **av)
         if (bufsz < 1024)
             die("OOPS");
     }
+    buffer++;
+    bufsz--;

     git_SHA1_Init(&ctx);



Then I ran

$ ./test-sha1 < ../t0013/shattered-1.pdf

in t/helper. No doubt an experienced Git developer would not patch the
Makefile and would not run the test like that, but that's what I did.
UBSan reports an unaligned load (the UB happened already as the
pointer was cast). Of course, tweaking the alignment of "buffer" is
cheating, but similar alignments can supposedly occur in the wild, or
the bug reports wouldn't be coming in.

This "fixes" the problem:

diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index 3dff80a..d6f4c44 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -66,9 +66,9 @@
 #define sha1_mix(W, t)  (rotate_left(W[t - 3] ^ W[t - 8] ^ W[t - 14]
^ W[t - 16], 1))

 #ifdef SHA1DC_BIGENDIAN
-    #define sha1_load(m, t, temp)  { temp = m[t]; }
+    #define sha1_load(m, t, temp)  { memcpy(&temp, m+t*4, 4); }
 #else
-    #define sha1_load(m, t, temp)  { temp = m[t]; sha1_bswap32(temp); }
+    #define sha1_load(m, t, temp)  { memcpy(&temp, m+t*4, 4);
sha1_bswap32(temp); }
 #endif

 #define sha1_store(W, t, x)    *(volatile uint32_t *)&W[t] = x
@@ -309,7 +309,7 @@ static void sha1_compression_W(uint32_t ihv[5],
const uint32_t W[80])



-void sha1_compression_states(uint32_t ihv[5], const uint32_t m[16],
uint32_t W[80], uint32_t states[80][5])
+void sha1_compression_states(uint32_t ihv[5], const uint8_t m[64],
uint32_t W[80], uint32_t states[80][5])
 {
     uint32_t a = ihv[0], b = ihv[1], c = ihv[2], d = ihv[3], e = ihv[4];
     uint32_t temp;
@@ -1639,7 +1639,7 @@ static void sha1_recompression_step(uint32_t
step, uint32_t ihvin[5], uint32_t i



-static void sha1_process(SHA1_CTX* ctx, const uint32_t block[16])
+static void sha1_process(SHA1_CTX* ctx, const uint8_t block[64])
 {
     unsigned i, j;
     uint32_t ubc_dv_mask[DVMASKSIZE] = { 0xFFFFFFFF };
@@ -1759,7 +1759,7 @@ void SHA1DCUpdate(SHA1_CTX* ctx, const char*
buf, size_t len)
     {
         ctx->total += fill;
         memcpy(ctx->buffer + left, buf, fill);
-        sha1_process(ctx, (uint32_t*)(ctx->buffer));
+        sha1_process(ctx, (uint8_t*)(ctx->buffer));
         buf += fill;
         len -= fill;
         left = 0;
@@ -1769,10 +1769,10 @@ void SHA1DCUpdate(SHA1_CTX* ctx, const char*
buf, size_t len)
         ctx->total += 64;

 #if defined(SHA1DC_ALLOW_UNALIGNED_ACCESS)
-        sha1_process(ctx, (uint32_t*)(buf));
+        sha1_process(ctx, (uint8_t*)(buf));
 #else
         memcpy(ctx->buffer, buf, 64);
-        sha1_process(ctx, (uint32_t*)(ctx->buffer));
+        sha1_process(ctx, (uint8_t*)(ctx->buffer));
 #endif /* defined(SHA1DC_ALLOW_UNALIGNED_ACCESS) */
         buf += 64;
         len -= 64;
@@ -1809,7 +1809,7 @@ int SHA1DCFinal(unsigned char output[20], SHA1_CTX *ctx)
     ctx->buffer[61] = (unsigned char)(total >> 16);
     ctx->buffer[62] = (unsigned char)(total >> 8);
     ctx->buffer[63] = (unsigned char)(total);
-    sha1_process(ctx, (uint32_t*)(ctx->buffer));
+    sha1_process(ctx, (uint8_t*)(ctx->buffer));
     output[0] = (unsigned char)(ctx->ihv[0] >> 24);
     output[1] = (unsigned char)(ctx->ihv[0] >> 16);
     output[2] = (unsigned char)(ctx->ihv[0] >> 8);
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
index a0ff5d1..1d181a1 100644
--- a/sha1dc/sha1.h
+++ b/sha1dc/sha1.h
@@ -18,7 +18,7 @@ extern "C" {

 /* sha-1 compression function that takes an already expanded message,
and additionally store intermediate states */
 /* only stores states ii (the state between step ii-1 and step ii)
when DOSTORESTATEii is defined in ubc_check.h */
-void sha1_compression_states(uint32_t[5], const uint32_t[16],
uint32_t[80], uint32_t[80][5]);
+void sha1_compression_states(uint32_t[5], const uint8_t[64],
uint32_t[80], uint32_t[80][5]);

 /*
 // Function type for sha1_recompression_step_T (uint32_t ihvin[5],
uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5]).



With this diff, various tests which seem relevant for SHA-1 pass,
including t0013, and the UBSan-error is gone. The second diff is just
a monkey-patch. I have no reason to believe I will be able to come up
with a proper and complete patch for sha1dc. And I guess such a thing
would not really be Git's patch to carry, either. But at least Git
could consider whether to keep relying on undefined behavior or not.

There's a fair chance I've mangled the whitespace. I'm using gmail's
web interface... Sorry about that.