sha: prevent removal of memset as dead store in sha1_update()

Due to optimization A call to memset() may be removed as a dead store when the buffer is not used after its value is overwritten.

Signed-off-by Roel Kluin <[email protected]>

From: Roel Kluin <[email protected]>
Date: Thu, 25 Feb 2010 16:10:27 +0100

Quoted 4 lines

Due to optimization A call to memset() may be removed as a dead store when the buffer is not used after its value is overwritten.

Signed-off-by Roel Kluin <[email protected]>

Solution is wrong and overkill in my mind.

It's overkill because the whole reason it's using a stack buffer is to avoid the overhead of a kmalloc() call.

And it's wrong because the reason the memset() is there seems to be to clear out key information that might exist kernel stack so that it's more difficult for rogue code to get at things.

Quoted 13 lines

From: Roel Kluin <[email protected]>
Date: Thu, 25 Feb 2010 16:10:27 +0100

Quoted 4 lines

Due to optimization A call to memset() may be removed as a dead store when the buffer is not used after its value is overwritten.

Signed-off-by Roel Kluin <[email protected]>

Solution is wrong and overkill in my mind.

It's overkill because the whole reason it's using a stack buffer is to avoid the overhead of a kmalloc() call.

Quoted 3 lines

And it's wrong because the reason the memset() is there seems to be to clear out key information that might exist kernel stack so that it's more difficult for rogue code to get at things.

If the memset is optimized away then the clear out does not occur. Do you know a different way to fix this?

Quoted 3 lines

And it's wrong because the reason the memset() is there seems to be to clear out key information that might exist kernel stack so that it's more difficult for rogue code to get at things.

If the memset is optimized away then the clear out does not occur. Do you know a different way to fix this? I observed this with:

Quoted 6 lines · roel kluin

Quoted 3 lines

And it's wrong because the reason the memset() is there seems to be to clear out key information that might exist kernel stack so that it's more difficult for rogue code to get at things.

If the memset is optimized away then the clear out does not occur. Do you know a different way to fix this? I observed this with:

You could always cast to volatile before memsetting?

Quoted 10 lines · Andi Kleen

Quoted 6 lines · roel kluin

Quoted 3 lines

And it's wrong because the reason the memset() is there seems to be to clear out key information that might exist kernel stack so that it's more difficult for rogue code to get at things.

If the memset is optimized away then the clear out does not occur. Do you know a different way to fix this? I observed this with:

You could always cast to volatile before memsetting?

I tried that and it doesn't work. Furthermore passing a volatile void * to a function expecting a void * provokes a compiler warning.

I currently think that defining and using

void secure_bzero(void *p, size_t n)
{
memset(p, 0, n);
/* We need for this memset() to be performed even if *p
* is about to disappear (a local auto variable going out
* of scope or some dynamic memory being kfreed()).
* Thus we need to fake a "use" of *p here.
* barrier() achieves that effect, and much more.
* TODO: find a better alternative to barrier() here. */
barrier();

}

Instead of barrier(), this works with gcc-3.2.3 up to gcc-4.4.3 for the purpose of making the memset() not disappear:

	{
		struct s { char c[n]; };
		asm("" : : "m"(*(struct s *)p));
	}

Every byte in the [p,p+n[ range must be used. If you only use the first byte, via e.g. asm("" :: "m"(*(char*)p)), then the compiler _will_ skip scrubbing bytes beyond the first.

An explicit loop that uses each byte individually also works, but results in awful code with older compilers.

Due to optimization A call to memset() may be removed as a dead store when the buffer is not used after its value is overwritten.

Signed-off-by Roel Kluin <[email protected]>

---
see http://cwe.mitre.org/data/slices/2000.html#14

checkpatch.pl, compile and sparse tested. Comments?

crypto/sha1_generic.c +2 -2

index 0416091..86de0da 100644
@@ -49,8 +49,8 @@ static int sha1_update(struct shash_desc *desc, const u8 *data,
 	src = data;
 
 	if ((partial + len) > 63) {
-		u32 temp[SHA_WORKSPACE_WORDS];
-
+		u32 *temp = kzalloc(SHA_WORKSPACE_WORDS * sizeof(u32),
+				GFP_KERNEL);
 		if (partial) {
 			done = -partial;
 			memcpy(sctx->buffer + partial, data, done + 64);

I fear that the only portable (across compiler versions) and safe solution is to invoke an assembly-coded dummy function with prototype

       void use(void *p);

and rewrite the code above as

       {
               u32 temp[...];
               ...
               memset(temp, 0, sizeof temp);
               use(temp);
       }

This forces the compiler to consider the buffer live after the memset, so the memset cannot be eliminated.

Quoted 14 lines · Mikael Pettersson

I fear that the only portable (across compiler versions) and safe solution is to invoke an assembly-coded dummy function with prototype

       void use(void *p);

and rewrite the code above as

       {
               u32 temp[...];
               ...
               memset(temp, 0, sizeof temp);
               use(temp);
       }

Quoted 2 lines

This forces the compiler to consider the buffer live after the memset, so the memset cannot be eliminated.

So is there some "do not optimize" GCC magic that we could use for a memzero_secret() helper function?

Quoted 14 lines · Mikael Pettersson

I fear that the only portable (across compiler versions) and safe solution is to invoke an assembly-coded dummy function with prototype

       void use(void *p);

and rewrite the code above as

       {
               u32 temp[...];
               ...
               memset(temp, 0, sizeof temp);
               use(temp);
       }

Quoted 2 lines

This forces the compiler to consider the buffer live after the memset, so the memset cannot be eliminated.

So is there some "do not optimize" GCC magic that we could use for a memzero_secret() helper function?

                       Pekka

Quoted 21 lines · Pekka Enberg

Quoted 14 lines · Mikael Pettersson

I fear that the only portable (across compiler versions) and safe solution is to invoke an assembly-coded dummy function with prototype

       void use(void *p);

and rewrite the code above as

       {
               u32 temp[...];
               ...
               memset(temp, 0, sizeof temp);
               use(temp);
       }

Quoted 2 lines

This forces the compiler to consider the buffer live after the memset, so the memset cannot be eliminated.

So is there some "do not optimize" GCC magic that we could use for a memzero_secret() helper function?

Quoted 2 lines

                       Pekka

       *(volatile char *)p = *(volatile char *)p;

appears to work when called after the memset:

Roel Kluin writes:
 > Due to optimization A call to memset() may be removed as a dead store when > the buffer is not used after its value is overwritten.
 >
 > Signed-off-by: Roel Kluin <[email protected]>
 > ---
 > see http://cwe.mitre.org/data/slices/2000.html#14
 >
 > checkpatch.pl, compile and sparse tested. Comments?
 >
 > diff --git a/crypto/sha1_generic.c b/crypto/sha1_generic.c
 > index 0416091..86de0da 100644
 > --- a/crypto/sha1_generic.c
 > +++ b/crypto/sha1_generic.c
 > @@ -49,8 +49,8 @@ static int sha1_update(struct shash_desc *desc, const u8 *data, >      src = data;
 >
 >      if ((partial + len) > 63) {
 > -            u32 temp[SHA_WORKSPACE_WORDS];
 > -
 > +            u32 *temp = kzalloc(SHA_WORKSPACE_WORDS * sizeof(u32), > +                            GFP_KERNEL);
 >              if (partial) {
 >                      done = -partial;
 >                      memcpy(sctx->buffer + partial, data, done + 64); > @@ -64,6 +64,7 @@ static int sha1_update(struct shash_desc *desc, const u8 *data, >              } while (done + 63 < len);
 >
 >              memset(temp, 0, sizeof(temp));
 > +            kfree(temp);
 >              partial = 0;
 >      }
 >      memcpy(sctx->buffer + partial, src, len - done);

At best this might solve the issue right now, but it's not future-proof by any margin.

One problem is that just like the lifetimes of auto variables are known to the compiler, allowing dead store elimination (DSE) on them, there is development going on to make malloc() and free() known to the compiler. I don't think it's complete yet, but once free() is known, the sequence "memset(p, 0, n); free(p);" will obviously be DSE:d just like in the current case with the auto variable.

And as soon as gcc can optimize malloc() and free(), you can be sure that some eager kernel hacker will mark the kernel's allocators accordingly, and then we're back to square one.

I fear that the only portable (across compiler versions) and safe solution is to invoke an assembly-coded dummy function with prototype

       void use(void *p);

and rewrite the code above as

       {
               u32 temp[...];
               ...
               memset(temp, 0, sizeof temp);
               use(temp);
       }

This forces the compiler to consider the buffer live after the memset, so the memset cannot be eliminated.

The reason the use() function needs to be in assembly code is that with link-time optimizations soon commonplace (LTO in gcc-4.5), a compiler can possibly discover that even an out-of-line function

       void use(void *p) { }

doesn't in fact use *p, which then enables (in theory) the preceeding memset() to be DSE:d.

Would barrier() (which is a simple memory clobber) after the memset work?

Quoted 1 line · Brian Gerst

Would barrier() (which is a simple memory clobber) after the memset work?

I don't know. It's implemented as an asm with a "memory" clobber, but I wouldn't bet on that forcing previous writes to a dying object to actally be performed (it would have to have a data-dependency on the dying object, but I don't think there is one).

From the GCC manual, section 5.37:

Quoted 9 lines

Quoted 1 line · Brian Gerst

Would barrier() (which is a simple memory clobber) after the memset work?

I don't know. It's implemented as an asm with a "memory" clobber, but I wouldn't bet on that forcing previous writes to a dying object to actally be performed (it would have to have a data-dependency on the dying object, but I don't think there is one).

From the GCC manual, section 5.37:

If your assembler instructions access memory in an unpredictable fashion, add `memory' to the list of clobbered registers. This will cause GCC to not keep memory values cached in registers across the assembler instruction and not optimize stores or loads to that memory. You will also want to add the volatile keyword if the memory affected is not listed in the inputs or outputs of the asm, as the `memory' clobber does not count as a side-effect of the asm.

--
Brian Gerst

Also from that document:

If you know how large the accessed memory is, you can add it as input or output but if this is not known, you should add memory. As an example, if you access ten bytes of a string, you can use a memory input like:

     {"m"( ({ struct { char x[10]; } *p = (void *)ptr ; *p; }) )}.

does this mean we could use something like:

#define SECURE_BZERO(x) do {                                            \
        memset(x, 0, sizeof(x));                                        \
        asm("" : :"m"( ({ struct { char __y[ARRAY_SIZE(x)]; } *__z =    \
                                        (void *)x ; *__z; }) ));        \

} while(0)