On 1 June 2017 at 12:33, Ævar Arnfjörð Bjarmason [off-list ref] wrote:
On Thu, Jun 1, 2017 at 12:26 PM, Martin Ågren [off-list ref] wrote:
quoted
On 1 June 2017 at 12:08, Andreas Schwab [off-list ref] wrote:
quoted
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.
On 1 June 2017 at 13:53, Martin Ågren [off-list ref] wrote:
On 1 June 2017 at 12:33, Ævar Arnfjörð Bjarmason [off-list ref] wrote:
quoted
On Thu, Jun 1, 2017 at 12:26 PM, Martin Ågren [off-list ref] wrote:
quoted
On 1 June 2017 at 12:08, Andreas Schwab [off-list ref] wrote:
quoted
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.
I looked into this some more. It turns out it is possible to trigger
undefined behavior on "next". Here's what I did:
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 ?= stripdiff --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.