Skip to contentSkip to conversation

: Miscompiling sha256.c by gcc 3.2.3 and arch pentium3,4

CRYPTO R CHAN 9 participants 15 messages Jan 30, 2004 – Feb 2, 2004

lore
Share & tools
lore

R CHAN

author
#0 lore raw

2.6.2-rc2 sha256.c is miscompiled with gcc 3.2.3. (User space is RedHat 3ES.)

Just an observation:

gcc 3.2.3 is miscompiling sha256.c when using
-O2 -march=pentium3
or pentium4.

gcc 3.3.x is ok, or the problem disappears
if I use arch=i686 or reduce the optimisation level to -O2.

Sympthoms are all the sha256 test vectors fail. If I extract the guts of the file to compile in user space the same problem occurs.

#1 lore raw
Quoted 9 lines · R CHAN

2.6.2-rc2 sha256.c is miscompiled with gcc 3.2.3. (User space is RedHat 3ES.)

Just an observation:

gcc 3.2.3 is miscompiling sha256.c when using
-O2 -march=pentium3
or pentium4.

Quoted 6 lines

gcc 3.3.x is ok, or the problem disappears
if I use arch=i686 or reduce the optimisation level to -O2.

Sympthoms are all the sha256 test vectors fail. If I extract the guts of the file to compile in user space the same problem occurs.

Have you noticed if this happens for any of the other crypto algorithms?

- James

Signature · 2 lines
James Morris
<[email protected]>
#2 lore raw

Has this been demonstrated on *any* system/arch using GCC 3.2.3 (or other 3.2 series) or is it limited in scope to the description below? Does it seem to do this with other implementations (other than sha256.c) or other kernels? Just trying to get an idea if this is a complier optimization bug or something much more limited in scope.

My personal lab is currently being unboxed and I won't be able to run my own tests for another week or so. (apologies in advance)

In any case, this is *extremely* serious from a number of angles.

Kind Regards,
-dsp

-----Original Message-----
From: [email protected] [mailto:[email protected]]On Behalf Of James Morris
Sent: Friday, January 30, 2004 9:40 AM
To: R CHAN
Cc: [email protected]; David S. Miller
Subject: Re: [CRYPTO]: Miscompiling sha256.c by gcc 3.2.3 and arch pentium3,4

Quoted 9 lines · R CHAN

2.6.2-rc2 sha256.c is miscompiled with gcc 3.2.3. (User space is RedHat 3ES.)

Just an observation:

gcc 3.2.3 is miscompiling sha256.c when using
-O2 -march=pentium3
or pentium4.

Quoted 6 lines

gcc 3.3.x is ok, or the problem disappears
if I use arch=i686 or reduce the optimisation level to -O2.

Sympthoms are all the sha256 test vectors fail. If I extract the guts of the file to compile in user space the same problem occurs.

Have you noticed if this happens for any of the other crypto algorithms?

- James
--
James Morris
<[email protected]>

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

author
#3 lore raw

I've narrowed the problem - it seems to be a specific optimisation bug with gcc-3.2.3-24 that comes with RedHat 3ES. The problem is not kernel related (sorry!) as the guts of the file exhibits the same problem when compiled in user space. (All the non-sha256 test vectors in tcrypt.ko pass BTW.)

The older gcc32 that comes with Fedora Cora 1 and the gcc33 there get it right.

For the actual files please check bug #114610 in https://bugzilla.redhat.com.
https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=114610
- the bug report includes sha256.c, tcrypt.c, and types.h necessary to demonstrate the problem in user space.

Quoted 67 lines · Dave Paris

Has this been demonstrated on *any* system/arch using GCC 3.2.3 (or other 3.2 series) or is it limited in scope to the description below? Does it seem to do this with other implementations (other than sha256.c) or other kernels? Just trying to get an idea if this is a complier optimization bug or something much more limited in scope.

My personal lab is currently being unboxed and I won't be able to run my own tests for another week or so. (apologies in advance)

In any case, this is *extremely* serious from a number of angles.

Kind Regards,
-dsp

-----Original Message-----
From: [email protected] [mailto:[email protected]]On Behalf Of James Morris
Sent: Friday, January 30, 2004 9:40 AM
To: R CHAN
Cc: [email protected]; David S. Miller
Subject: Re: [CRYPTO]: Miscompiling sha256.c by gcc 3.2.3 and arch pentium3,4

Quoted 9 lines · R CHAN

2.6.2-rc2 sha256.c is miscompiled with gcc 3.2.3. (User space is RedHat 3ES.)

Just an observation:

gcc 3.2.3 is miscompiling sha256.c when using
-O2 -march=pentium3
or pentium4.

Quoted 8 lines

gcc 3.3.x is ok, or the problem disappears
if I use arch=i686 or reduce the optimisation level to -O2.

Sympthoms are all the sha256 test vectors fail. If I extract the guts of the file to compile in user space the same problem occurs.

Have you noticed if this happens for any of the other crypto algorithms?

- James
--
James Morris
<[email protected]>

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#4 lore raw
In reply to Dave Paris
Quoted 10 lines · Dave Paris

Has this been demonstrated on *any* system/arch using GCC 3.2.3 (or other 3.2 series) or is it limited in scope to the description below? Does it seem to do this with other implementations (other than sha256.c) or other kernels? Just trying to get an idea if this is a complier optimization bug or something much more limited in scope.

My personal lab is currently being unboxed and I won't be able to run my own tests for another week or so. (apologies in advance)

In any case, this is *extremely* serious from a number of angles.

GCC handling of automatic const variables with initializers is very fragile. There have been numerous bugs in it in the past and last one has been fixed just yesterday (on GCC trunk only for the time being). It will be eventually backported once it gets some more testing on GCC mainline.

The problematic line in sha256.c is:
static void sha256_final(void* ctx, u8 *out)
{
...

	const u8 padding[64] = { 0x80, };

where if you are unlucky, scheduler will with various different GCC versions on various architectures reorder instructions so that store of 0x80 into the struct is before clearing of the 64 bytes.

On the other side, doing this in sha256.c seems quite inefficient, IMHO much better would be to have there static u8 padding[64] = { 0x80 }; because that will not mean clearing 64 bytes and writing another one on top of it every time the routine is executed.

Jakub

#5 lore raw
Quoted 6 lines · Jakub Jelinek

The problematic line in sha256.c is:
static void sha256_final(void* ctx, u8 *out)
{
...

	const u8 padding[64] = { 0x80, };
Quoted 8 lines

where if you are unlucky, scheduler will with various different GCC versions on various architectures reorder instructions so that store of 0x80 into the struct is before clearing of the 64 bytes.

On the other side, doing this in sha256.c seems quite inefficient, IMHO much better would be to have there static u8 padding[64] = { 0x80 }; because that will not mean clearing 64 bytes and writing another one on top of it every time the routine is executed.

Proposed patch below. I think sha512 would have been ok, but might as well make them the same.

R Chan, please test and let us know if it fixes the problem for you.

- James

Signature · 27 lines
James Morris
<[email protected]>

diff -urN -X dontdiff linux-2.6.2-rc2-mm2.o/crypto/sha256.c linux-2.6.2-rc2-mm2.w/crypto/sha256.c
--- linux-2.6.2-rc2-mm2.o/crypto/sha256.c	2003-09-27 20:50:15.000000000 -0400
+++ linux-2.6.2-rc2-mm2.w/crypto/sha256.c	2004-01-30 11:27:26.465531792 -0500
@@ -295,7 +295,7 @@
 	u8 bits[8];
 	unsigned int index, pad_len, t;
 	int i, j;
-	const u8 padding[64] = { 0x80, };
+	static u8 padding[64] = { 0x80, };
 
 	/* Save number of bits */
 	t = sctx->count[0];
diff -urN -X dontdiff linux-2.6.2-rc2-mm2.o/crypto/sha512.c linux-2.6.2-rc2-mm2.w/crypto/sha512.c
--- linux-2.6.2-rc2-mm2.o/crypto/sha512.c	2003-09-27 20:51:04.000000000 -0400
+++ linux-2.6.2-rc2-mm2.w/crypto/sha512.c	2004-01-30 11:32:16.182488120 -0500
@@ -249,7 +249,7 @@
 {
         struct sha512_ctx *sctx = ctx;
 	
-        const static u8 padding[128] = { 0x80, };
+        static u8 padding[128] = { 0x80, };
 
         u32 t;
 	u64 t2;
#6 lore raw

Review

Quoted 2 lines · James Morris
(quoted diff) +1 -1
-	const u8 padding[64] = { 0x80, };
+	static u8 padding[64] = { 0x80, };

The RedHat bug suggests 'static const' as the appropriate replacement.

https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=114610#c4

Unfortunately that probably means an extra 64 bytes of text, rather than the 10 or so bytes of instructions to do the memset and store. Ideally padding[] would be allocated in BSS rather than text or the stack (and initialized with { 0x80, } at runtime), but I guess you can't have everything.

-andy

#7 lore raw
Quoted 6 lines · Andy Isaacson

Review

Quoted 2 lines · James Morris
(quoted diff) +1 -1
-	const u8 padding[64] = { 0x80, };
+	static u8 padding[64] = { 0x80, };

The RedHat bug suggests 'static const' as the appropriate replacement.

Quoted 7 lines

https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=114610#c4

Unfortunately that probably means an extra 64 bytes of text, rather than the 10 or so bytes of instructions to do the memset and store. Ideally padding[] would be allocated in BSS rather than text or the stack (and initialized with { 0x80, } at runtime), but I guess you can't have everything.

Or you can use

	u8 padding[64] = { 0x80 };
if you really want to initialize it at runtime and want to work around the
compiler bug.  It shouldn't be any less efficient than
	const u8 padding[64] = { 0x80 };

since it is used just once, passed to non-inlined function.

Jakub

#8 lore raw
Quoted 18 lines · Jakub Jelinek
Quoted 7 lines · Andy Isaacson

Review

Quoted 2 lines · James Morris
(quoted diff) +1 -1
-	const u8 padding[64] = { 0x80, };
+	static u8 padding[64] = { 0x80, };

The RedHat bug suggests 'static const' as the appropriate replacement.

Quoted 7 lines

https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=114610#c4

Unfortunately that probably means an extra 64 bytes of text, rather than the 10 or so bytes of instructions to do the memset and store. Ideally padding[] would be allocated in BSS rather than text or the stack (and initialized with { 0x80, } at runtime), but I guess you can't have everything.

Quoted 6 lines

Or you can use

	u8 padding[64] = { 0x80 };
if you really want to initialize it at runtime and want to work around the
compiler bug.  It shouldn't be any less efficient than
	const u8 padding[64] = { 0x80 };

since it is used just once, passed to non-inlined function.

I like this, as it avoids bloating the 64 bytes into the kernel.

Signature · 3 lines
bill davidsen <[email protected]>
  CTO TMR Associates, Inc
  Doing interesting things with small computers since 1979
#9 lore raw
In reply to James Morris
Quoted 4 lines · On Fri, 30 Jan 2004 11:35:20 -0500 (EST) James Morris <[email protected]>…

Proposed patch below. I think sha512 would have been ok, but might as well make them the same.

R Chan, please test and let us know if it fixes the problem for you.

I'm putting this into my tree(s), thanks James.

#10 lore raw
Quoted 10 lines · David S. Miller
Quoted 3 lines · On Fri, 30 Jan 2004 11:35:20 -0500 (EST) James Morris <[email protected]>…

Proposed patch below. I think sha512 would have been ok, but might as well make them the same.

R Chan, please test and let us know if it fixes the problem for you.

I'm putting this into my tree(s), thanks James.

What didn't you like about Jakob's patch which avoids the 64 byte size penalty?

Signature · 3 lines
bill davidsen <[email protected]>
  CTO TMR Associates, Inc
  Doing interesting things with small computers since 1979
#11 lore raw
Quoted 2 lines · On Sun, 01 Feb 2004 16:18:48 -0500 Bill Davidsen <[email protected]> wrote:

What didn't you like about Jakob's patch which avoids the 64 byte size penalty?

Because it means memset'ing the thing every time the function is called. And this function is called for every transform.

#12 lore raw
In reply to Bill Davidsen
Quoted 3 lines · Bill Davidsen

What didn't you like about Jakob's patch which avoids the 64 byte size penalty?

What size penalty?

The data has to be allocated somewhere, and on the stack is simply not acceptable. So there can be no size penalty.

Yes, the text size of the binary is slightly bigger, because a "static const" ends up in the ro-section, but that's _purely_ an accounting thing. It has to be somewhere, be it .text, .data or .bss. Who would ever care where it is?

Having it in .ro means that there are no initialization issues, and a compressed kernel compresses the zero bytes better than having init-time code to initialize the array (or, worse, doing it over and over at run-time).

So where does this size penalty idea come from?

In short: "static const" is correct.

Linus

#13 lore raw
Quoted 11 lines · Linus Torvalds
Quoted 3 lines · Bill Davidsen

What didn't you like about Jakob's patch which avoids the 64 byte size penalty?

What size penalty?

The data has to be allocated somewhere, and on the stack is simply not acceptable. So there can be no size penalty.

The point was that it doesn't have to be allocated somewhere unless it's actually used, and many kernels will want the capability but in practice won't use it. David pointed out the overhead of repeated initialize, and that's an overpowering reason not to do runtime allocation.

Quoted 12 lines

Yes, the text size of the binary is slightly bigger, because a "static const" ends up in the ro-section, but that's _purely_ an accounting thing. It has to be somewhere, be it .text, .data or .bss. Who would ever care where it is?

Having it in .ro means that there are no initialization issues, and a compressed kernel compresses the zero bytes better than having init-time code to initialize the array (or, worse, doing it over and over at run-time).

So where does this size penalty idea come from?

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
#14 lore raw
In reply to Jakub Jelinek

Jakub said something like...

Quoted 10 lines

GCC handling of automatic const variables with initializers is very fragile. There have been numerous bugs in it in the past and last one has been fixed just yesterday (on GCC trunk only for the time being). It will be eventually backported once it gets some more testing on GCC mainline.

The problematic line in sha256.c is:
static void sha256_final(void* ctx, u8 *out)
{
...

	const u8 padding[64] = { 0x80, };

Verry interesting. Good work Jakub.

JLC

Signature · 4 lines
http://www.certainkey.com
Suite 4560 CTTC
1125 Colonel By Dr.
Ottawa ON, K1S 5B6