sha512: make it work, undo percpu message schedule

commit f9e2bca6c22d75a289a349f869701214d63b5060
aka "crypto: sha512 - Move message schedule W[80] to static percpu area"
created global message schedule area.

If sha512_update will ever be entered twice, hilarity ensures.

Probably the easiest way to notice incorrect hashes being calculated is
to run 2 ping floods over AH with hmac(sha512):

	#!/usr/sbin/setkey -f
	flush;
	spdflush;
	add IP1 IP2 ah 25 -A hmac-sha512 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000025;
	add IP2 IP1 ah 52 -A hmac-sha512 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000052;
	spdadd IP1 IP2 any -P out ipsec ah/transport//require;
	spdadd IP2 IP1 any -P in  ipsec ah/transport//require;

XfrmInStateProtoError will start ticking with -EBADMSG being returned
from ah_input(). This never happens with, say, hmac(sha1).

I personally don't understand this changelog entry:

	"The message schedule W (u64[80]) is too big for the stack."

Hash context is dynamically allocated.

W[80] stack usage can be trimmed like in SHA-1, this is for separate patch.

P. S.: If only one ping flood runs, XfrmInStateProtoError will also tick
	but very slowly. I personally can't explain this.

With patch applied (on BOTH sides), XfrmInStateProtoError does not tick
with multiple bidirectional ping flood streams like it doesn't tick
with SHA-1.

Signed-off-by: Alexey Dobriyan <redacted>
---

 crypto/sha512_generic.c |    6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

--- a/crypto/sha512_generic.c
+++ b/crypto/sha512_generic.c

@@ -21,8 +21,6 @@
 #include <linux/percpu.h>
 #include <asm/byteorder.h>
 
-static DEFINE_PER_CPU(u64[80], msg_schedule);
-
 static inline u64 Ch(u64 x, u64 y, u64 z)
 {
         return z ^ (x & (y ^ z));

@@ -89,7 +87,7 @@ sha512_transform(u64 *state, const u8 *input)
 	u64 a, b, c, d, e, f, g, h, t1, t2;
 
 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 W[80];
 
 	/* load the input */
         for (i = 0; i < 16; i++)

@@ -128,8 +126,6 @@ sha512_transform(u64 *state, const u8 *input)
 
 	/* erase our data */
 	a = b = c = d = e = f = g = h = t1 = t2 = 0;
-	memset(W, 0, sizeof(__get_cpu_var(msg_schedule)));
-	put_cpu_var(msg_schedule);
 }
 
 static int

On Wed, Jan 11, 2012 at 03:00:40AM +0300, Alexey Dobriyan wrote:

-	memset(W, 0, sizeof(__get_cpu_var(msg_schedule)));

And, yes, this is intentional -- modern gcc pisses on stone age data clearing.

On Wed, Jan 11, 2012 at 03:00:40AM +0300, Alexey Dobriyan wrote:

commit f9e2bca6c22d75a289a349f869701214d63b5060
aka "crypto: sha512 - Move message schedule W[80] to static percpu area"
created global message schedule area.

If sha512_update will ever be entered twice, hilarity ensures.

Hmm, do you know why this happens? On the face of it this shouldn't
be possible as preemption is disabled.

Thanks,
-- 
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

On 01/11/2012 01:00 AM, Alexey Dobriyan wrote:

commit f9e2bca6c22d75a289a349f869701214d63b5060
aka "crypto: sha512 - Move message schedule W[80] to static percpu area"
created global message schedule area.

[snip]

I personally don't understand this changelog entry:

	"The message schedule W (u64[80]) is too big for the stack."

Hash context is dynamically allocated.

My original patch did the same thing as yours and put the message
schedule on the stack in sha512_transform. Herbert argued [1], that it
was too big and suggested to store it in a static per-cpu area.

[1] - http://www.mail-archive.com/linux-crypto@vger.kernel.org/msg02527.html

On Wed, Jan 11, 2012 at 11:36:11AM +1100, Herbert Xu wrote:

On Wed, Jan 11, 2012 at 03:00:40AM +0300, Alexey Dobriyan wrote:

quoted

commit f9e2bca6c22d75a289a349f869701214d63b5060
aka "crypto: sha512 - Move message schedule W[80] to static percpu area"
created global message schedule area.

If sha512_update will ever be entered twice, hilarity ensures.

Hmm, do you know why this happens? On the face of it this shouldn't
be possible as preemption is disabled.

Herbert, I couldn't come up with a single scenario. :-(
But the bug is easy to reproduce.

On Fri, Jan 13, 2012 at 02:55:14AM +0300, Alexey Dobriyan wrote:

Herbert, I couldn't come up with a single scenario. :-(
But the bug is easy to reproduce.

OK, I'll try to reproduce it here.

Thanks!
-- 
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

On Wed, Jan 11, 2012 at 11:36:11AM +1100, Herbert Xu wrote:

On Wed, Jan 11, 2012 at 03:00:40AM +0300, Alexey Dobriyan wrote:

quoted

commit f9e2bca6c22d75a289a349f869701214d63b5060
aka "crypto: sha512 - Move message schedule W[80] to static percpu area"
created global message schedule area.

If sha512_update will ever be entered twice, hilarity ensures.

Hmm, do you know why this happens? On the face of it this shouldn't
be possible as preemption is disabled.

I did not try to reproduce, but this looks like a race of the 'local out'
and the receive packet path. On 'lokal out' bottom halves are enabled,
so could be interrupted by the NET_RX_SOFTIRQ while doing a sha512_update.
The NET_RX_SOFTIRQ could invoke sha512_update too, that would corrupt the
hash value. My guess could be checked easily by disabling the bottom halves
before the percpu value is fetched.

On Fri, Jan 13, 2012 at 07:22:56AM +0100, Steffen Klassert wrote:

I did not try to reproduce, but this looks like a race of the 'local out'
and the receive packet path. On 'lokal out' bottom halves are enabled,
so could be interrupted by the NET_RX_SOFTIRQ while doing a sha512_update.
The NET_RX_SOFTIRQ could invoke sha512_update too, that would corrupt the
hash value. My guess could be checked easily by disabling the bottom halves
before the percpu value is fetched.

Good point.  I'll send out a patch for Alexey to test.

Thanks,
-- 
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Le vendredi 13 janvier 2012 à 07:22 +0100, Steffen Klassert a écrit :

On Wed, Jan 11, 2012 at 11:36:11AM +1100, Herbert Xu wrote:

quoted

On Wed, Jan 11, 2012 at 03:00:40AM +0300, Alexey Dobriyan wrote:

quoted

commit f9e2bca6c22d75a289a349f869701214d63b5060
aka "crypto: sha512 - Move message schedule W[80] to static percpu area"
created global message schedule area.

If sha512_update will ever be entered twice, hilarity ensures.

Hmm, do you know why this happens? On the face of it this shouldn't
be possible as preemption is disabled.

I did not try to reproduce, but this looks like a race of the 'local out'
and the receive packet path. On 'lokal out' bottom halves are enabled,
so could be interrupted by the NET_RX_SOFTIRQ while doing a sha512_update.
The NET_RX_SOFTIRQ could invoke sha512_update too, that would corrupt the
hash value. My guess could be checked easily by disabling the bottom halves
before the percpu value is fetched.

Good catch. It can be generalized to any interrupts (soft and hard)

Another solution is using two blocks, one used from interrupt context.

static DEFINE_PER_CPU(u64[80], msg_schedule);
static DEFINE_PER_CPU(u64[80], msg_schedule_irq);

(Like we do for SNMP mibs on !x86 arches)

On Fri, Jan 13, 2012 at 07:48:38AM +0100, Eric Dumazet wrote:

Another solution is using two blocks, one used from interrupt context.

static DEFINE_PER_CPU(u64[80], msg_schedule);
static DEFINE_PER_CPU(u64[80], msg_schedule_irq);

(Like we do for SNMP mibs on !x86 arches)

Yes that sounds good.  Thanks Eric!
-- 
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

On Fri, Jan 13, 2012 at 02:55:14AM +0300, Alexey Dobriyan wrote:

Herbert, I couldn't come up with a single scenario. :-(
But the bug is easy to reproduce.

OK, does this patch work for you?

commit 31f4e55c09c1170f8b813c14b1299b70f50db414
Author: Herbert Xu [off-list ref]
Date:   Fri Jan 13 18:06:50 2012 +1100

    crypto: sha512 - Fix msg_schedule race
    
    The percpu msg_schedule setup was unsafe as a user in a process
    context can be interrupted by a softirq user which would then
    scribble over the exact same work area.  This was discovered by
    Steffen Klassert.
    
    This patch based on ideas from Eric Dumazet fixes this by using
    two independent work areas.
    
    Reported-by: Alexey Dobriyan [off-list ref]
    Signed-off-by: Herbert Xu [off-list ref]

diff --git a/crypto/sha512_generic.c b/crypto/sha512_generic.c
index 9ed9f60..a49c457 100644
--- a/crypto/sha512_generic.c
+++ b/crypto/sha512_generic.c

@@ -11,6 +11,7 @@
  *
  */
 #include <crypto/internal/hash.h>
+#include <linux/interrupt.h>
 #include <linux/kernel.h>
 #include <linux/module.h>
 #include <linux/mm.h>

@@ -21,7 +22,9 @@
 #include <linux/percpu.h>
 #include <asm/byteorder.h>
 
-static DEFINE_PER_CPU(u64[80], msg_schedule);
+#define SHA512_SCHEDULE_SIZE 80
+
+static DEFINE_PER_CPU(u64[SHA512_SCHEDULE_SIZE * 2], msg_schedule);
 
 static inline u64 Ch(u64 x, u64 y, u64 z)
 {

@@ -89,7 +92,8 @@ sha512_transform(u64 *state, const u8 *input)
 	u64 a, b, c, d, e, f, g, h, t1, t2;
 
 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 *W = get_cpu_var(msg_schedule) +
+		 SHA512_SCHEDULE_SIZE * !!in_interrupt();
 
 	/* load the input */
         for (i = 0; i < 16; i++)

@@ -128,7 +132,7 @@ sha512_transform(u64 *state, const u8 *input)
 
 	/* erase our data */
 	a = b = c = d = e = f = g = h = t1 = t2 = 0;
-	memset(W, 0, sizeof(__get_cpu_var(msg_schedule)));
+	memset(W, 0, SHA512_SCHEDULE_SIZE * sizeof(*W));
 	put_cpu_var(msg_schedule);
 }
 

Thanks,
-- 
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Good catch. It can be generalized to any interrupts (soft and hard)

Another solution is using two blocks, one used from interrupt context.

static DEFINE_PER_CPU(u64[80], msg_schedule);
static DEFINE_PER_CPU(u64[80], msg_schedule_irq);

(Like we do for SNMP mibs on !x86 arches)

Don't you need one block per interrupt level ?

It also means that the functions need to know where they
are being called from - which may not be true.

A thought is that if you are going to reserve this memory
for each cpu, it might as well be reserved as part of the
interrupt stack (assuming interrupts switch stacks).

Process level code would still need to use a reserved buffer.

	David

Le vendredi 13 janvier 2012 à 18:08 +1100, Herbert Xu a écrit :

On Fri, Jan 13, 2012 at 02:55:14AM +0300, Alexey Dobriyan wrote:

quoted

Herbert, I couldn't come up with a single scenario. :-(
But the bug is easy to reproduce.

OK, does this patch work for you?

commit 31f4e55c09c1170f8b813c14b1299b70f50db414
Author: Herbert Xu [off-list ref]
Date:   Fri Jan 13 18:06:50 2012 +1100

    crypto: sha512 - Fix msg_schedule race
    
    The percpu msg_schedule setup was unsafe as a user in a process
    context can be interrupted by a softirq user which would then
    scribble over the exact same work area.  This was discovered by
    Steffen Klassert.
    
    This patch based on ideas from Eric Dumazet fixes this by using
    two independent work areas.
    
    Reported-by: Alexey Dobriyan [off-list ref]
    Signed-off-by: Herbert Xu [off-list ref]

I wonder ...

With 4096 cpus, do we really want to reserve 5242880 bytes of memory for
this function ?

What about following patch instead ?

(Trying a dynamic memory allocation, and fallback on a single
pre-allocated bloc of memory, shared by all cpus, protected by a
spinlock)

diff --git a/crypto/sha512_generic.c b/crypto/sha512_generic.c
index 9ed9f60..5c80a76 100644
--- a/crypto/sha512_generic.c
+++ b/crypto/sha512_generic.c

@@ -21,7 +21,6 @@
 #include <linux/percpu.h>
 #include <asm/byteorder.h>
 
-static DEFINE_PER_CPU(u64[80], msg_schedule);
 
 static inline u64 Ch(u64 x, u64 y, u64 z)
 {

@@ -87,10 +86,16 @@ static void
 sha512_transform(u64 *state, const u8 *input)
 {
 	u64 a, b, c, d, e, f, g, h, t1, t2;
-
+	static u64 msg_schedule[80];
+	static DEFINE_SPINLOCK(msg_schedule_lock);
 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 *W = kzalloc(sizeof(msg_schedule), GFP_ATOMIC | __GFP_NOWARN);
 
+	
+	if (!W) {
+		spin_lock_bh(&msg_schedule_lock);
+		W = msg_schedule;
+	}
 	/* load the input */
         for (i = 0; i < 16; i++)
                 LOAD_OP(i, W, input);

@@ -128,8 +133,11 @@ sha512_transform(u64 *state, const u8 *input)
 
 	/* erase our data */
 	a = b = c = d = e = f = g = h = t1 = t2 = 0;
-	memset(W, 0, sizeof(__get_cpu_var(msg_schedule)));
-	put_cpu_var(msg_schedule);
+	memset(W, 0, sizeof(msg_schedule));
+	if (W == msg_schedule)
+		spin_unlock_bh(&msg_schedule_lock);
+	else
+		kfree(W);
 }
 
 static int

Le vendredi 13 janvier 2012 à 11:35 +0100, Eric Dumazet a écrit :

And a plain kmalloc() is enough, since we fully initialize the array a
bit later.

	for (i = 0; i < 16; i++)
		LOAD_OP(i, W, input);
	for (i = 16; i < 80; i++) {
		BLEND_OP(i, W);
	}

Le vendredi 13 janvier 2012 à 11:41 +0100, Eric Dumazet a écrit :

And a plain kmalloc() is enough, since we fully initialize the array a
bit later.

	for (i = 0; i < 16; i++)
		LOAD_OP(i, W, input);
	for (i = 16; i < 80; i++) {
		BLEND_OP(i, W);
	}

Here is an official patch ;)

[PATCH v3] crypto: sha512 - Fix msg_schedule race

The percpu msg_schedule setup was unsafe as a user in a process
context can be interrupted by a softirq user which would then
scribble over the exact same work area.

Bug reported by Alexey Dobriyan, and diagnosed by Steffen Klassert.

Bug added in commit f9e2bca6c22 (crypto: sha512 - Move message schedule
W[80] to static percpu area)
    
Try a dynamic memory allocation, and fallback using a single static
area, guarded by a spinlock.

This removes use of percpu memory.

Reported-by: Alexey Dobriyan <redacted>
Signed-off-by: Eric Dumazet <redacted>
CC: Herbert Xu <herbert@gondor.apana.org.au>
CC: Adrian-Ken Rueegsegger <redacted>
CC: Steffen Klassert <steffen.klassert@secunet.com>
---
 crypto/sha512_generic.c |   18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

diff --git a/crypto/sha512_generic.c b/crypto/sha512_generic.c
index 9ed9f60..b52ef9b 100644
--- a/crypto/sha512_generic.c
+++ b/crypto/sha512_generic.c

@@ -18,10 +18,8 @@
 #include <linux/crypto.h>
 #include <linux/types.h>
 #include <crypto/sha.h>
-#include <linux/percpu.h>
 #include <asm/byteorder.h>
 
-static DEFINE_PER_CPU(u64[80], msg_schedule);
 
 static inline u64 Ch(u64 x, u64 y, u64 z)
 {

@@ -87,10 +85,15 @@ static void
 sha512_transform(u64 *state, const u8 *input)
 {
 	u64 a, b, c, d, e, f, g, h, t1, t2;
-
+	static u64 msg_schedule[80];
+	static DEFINE_SPINLOCK(msg_schedule_lock);
 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 *W = kmalloc(sizeof(msg_schedule), GFP_ATOMIC | __GFP_NOWARN);
 
+	if (!W) {
+		spin_lock_bh(&msg_schedule_lock);
+		W = msg_schedule;
+	}
 	/* load the input */
         for (i = 0; i < 16; i++)
                 LOAD_OP(i, W, input);

@@ -128,8 +131,11 @@ sha512_transform(u64 *state, const u8 *input)
 
 	/* erase our data */
 	a = b = c = d = e = f = g = h = t1 = t2 = 0;
-	memset(W, 0, sizeof(__get_cpu_var(msg_schedule)));
-	put_cpu_var(msg_schedule);
+	memset(W, 0, sizeof(msg_schedule));
+	if (W == msg_schedule)
+		spin_unlock_bh(&msg_schedule_lock);
+	else
+		kfree(W);
 }
 
 static int

On Fri, Jan 13, 2012 at 11:35:42AM +0100, Eric Dumazet wrote:

Le vendredi 13 janvier 2012 à 18:08 +1100, Herbert Xu a écrit :

quoted

On Fri, Jan 13, 2012 at 02:55:14AM +0300, Alexey Dobriyan wrote:

quoted

Herbert, I couldn't come up with a single scenario. :-(
But the bug is easy to reproduce.

OK, does this patch work for you?

commit 31f4e55c09c1170f8b813c14b1299b70f50db414
Author: Herbert Xu [off-list ref]
Date:   Fri Jan 13 18:06:50 2012 +1100

    crypto: sha512 - Fix msg_schedule race
    
    The percpu msg_schedule setup was unsafe as a user in a process
    context can be interrupted by a softirq user which would then
    scribble over the exact same work area.  This was discovered by
    Steffen Klassert.
    
    This patch based on ideas from Eric Dumazet fixes this by using
    two independent work areas.
    
    Reported-by: Alexey Dobriyan [off-list ref]
    Signed-off-by: Herbert Xu [off-list ref]

I wonder ...

With 4096 cpus, do we really want to reserve 5242880 bytes of memory for
this function ?

What about following patch instead ?

(Trying a dynamic memory allocation, and fallback on a single
pre-allocated bloc of memory, shared by all cpus, protected by a
spinlock)

If we want to do dynamic memory allocation, we could place it to the
shash_desc context where we already store the intermediate digest value.
This is preallocated anyway, so we don't need to do another allocation.

On 1/13/12, Eric Dumazet [off-list ref] wrote:

+	static u64 msg_schedule[80];
+	static DEFINE_SPINLOCK(msg_schedule_lock);

No guys, no.

SHA-512 only needs u64[16] running window for message scheduling.

I'm sending whitespace mangled patch which is only tested
with selfcryptotest passed, so you won't apply something complex.

Stackspace usage drops down to like this:

    -139:   48 81 ec c8 02 00 00    sub    $0x2c8,%rsp
    +136:       48 81 ec 18 01 00 00    sub    $0x118,%rsp

--- a/crypto/sha512_generic.c
+++ b/crypto/sha512_generic.c

@@ -21,8 +21,6 @@
 #include <linux/percpu.h>
 #include <asm/byteorder.h>

-static DEFINE_PER_CPU(u64[80], msg_schedule);
-
 static inline u64 Ch(u64 x, u64 y, u64 z)
 {
         return z ^ (x & (y ^ z));

@@ -80,7 +78,7 @@ static inline void LOAD_OP(int I, u64 *W, const u8 *input)

 static inline void BLEND_OP(int I, u64 *W)
 {
-	W[I] = s1(W[I-2]) + W[I-7] + s0(W[I-15]) + W[I-16];
+	W[I%16] = s1(W[(I-2)%16]) + W[(I-7)%16] + s0(W[(I-15)%16]) + W[I%16];
 }

 static void

@@ -89,38 +87,48 @@ sha512_transform(u64 *state, const u8 *input)
 	u64 a, b, c, d, e, f, g, h, t1, t2;

 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 W[16];

 	/* load the input */
         for (i = 0; i < 16; i++)
                 LOAD_OP(i, W, input);

-        for (i = 16; i < 80; i++) {
-                BLEND_OP(i, W);
-        }
-
 	/* load the state into our registers */
 	a=state[0];   b=state[1];   c=state[2];   d=state[3];
 	e=state[4];   f=state[5];   g=state[6];   h=state[7];

-	/* now iterate */
-	for (i=0; i<80; i+=8) {
-		t1 = h + e1(e) + Ch(e,f,g) + sha512_K[i  ] + W[i  ];
-		t2 = e0(a) + Maj(a,b,c);    d+=t1;    h=t1+t2;
-		t1 = g + e1(d) + Ch(d,e,f) + sha512_K[i+1] + W[i+1];
-		t2 = e0(h) + Maj(h,a,b);    c+=t1;    g=t1+t2;
-		t1 = f + e1(c) + Ch(c,d,e) + sha512_K[i+2] + W[i+2];
-		t2 = e0(g) + Maj(g,h,a);    b+=t1;    f=t1+t2;
-		t1 = e + e1(b) + Ch(b,c,d) + sha512_K[i+3] + W[i+3];
-		t2 = e0(f) + Maj(f,g,h);    a+=t1;    e=t1+t2;
-		t1 = d + e1(a) + Ch(a,b,c) + sha512_K[i+4] + W[i+4];
-		t2 = e0(e) + Maj(e,f,g);    h+=t1;    d=t1+t2;
-		t1 = c + e1(h) + Ch(h,a,b) + sha512_K[i+5] + W[i+5];
-		t2 = e0(d) + Maj(d,e,f);    g+=t1;    c=t1+t2;
-		t1 = b + e1(g) + Ch(g,h,a) + sha512_K[i+6] + W[i+6];
-		t2 = e0(c) + Maj(c,d,e);    f+=t1;    b=t1+t2;
-		t1 = a + e1(f) + Ch(f,g,h) + sha512_K[i+7] + W[i+7];
-		t2 = e0(b) + Maj(b,c,d);    e+=t1;    a=t1+t2;
+#define SHA512_0_15(i, a, b, c, d, e, f, g, h)			\
+	t1 = h + e1(e) + Ch(e, f, g) + sha512_K[i] + W[i];	\
+	t2 = e0(a) + Maj(a,b,c);				\
+	d += t1;						\
+	h = t1 + t2
+
+#define SHA512_16_79(i, a, b, c, d, e, f, g, h)			\
+	BLEND_OP(i, W);						\
+	t1 = h + e1(e) + Ch(e, f, g) + sha512_K[i] + W[(i)%16];	\
+	t2 = e0(a) + Maj(a,b,c);				\
+	d += t1;						\
+	h = t1 + t2
+
+	for (i = 0; i < 16; i += 8) {
+		SHA512_0_15(i, a, b, c, d, e, f, g, h);
+		SHA512_0_15(i + 1, h, a, b, c, d, e, f, g);
+		SHA512_0_15(i + 2, g, h, a, b, c, d, e, f);
+		SHA512_0_15(i + 3, f, g, h, a, b, c, d, e);
+		SHA512_0_15(i + 4, e, f, g, h, a, b, c, d);
+		SHA512_0_15(i + 5, d, e, f, g, h, a, b, c);
+		SHA512_0_15(i + 6, c, d, e, f, g, h, a, b);
+		SHA512_0_15(i + 7, b, c, d, e, f, g, h, a);
+	}
+	for (i = 16; i < 80; i += 8) {
+		SHA512_16_79(i, a, b, c, d, e, f, g, h);
+		SHA512_16_79(i + 1, h, a, b, c, d, e, f, g);
+		SHA512_16_79(i + 2, g, h, a, b, c, d, e, f);
+		SHA512_16_79(i + 3, f, g, h, a, b, c, d, e);
+		SHA512_16_79(i + 4, e, f, g, h, a, b, c, d);
+		SHA512_16_79(i + 5, d, e, f, g, h, a, b, c);
+		SHA512_16_79(i + 6, c, d, e, f, g, h, a, b);
+		SHA512_16_79(i + 7, b, c, d, e, f, g, h, a);
 	}

 	state[0] += a; state[1] += b; state[2] += c; state[3] += d;

@@ -128,8 +136,6 @@ sha512_transform(u64 *state, const u8 *input)

 	/* erase our data */
 	a = b = c = d = e = f = g = h = t1 = t2 = 0;
-	memset(W, 0, sizeof(__get_cpu_var(msg_schedule)));
-	put_cpu_var(msg_schedule);
 }

 static int

Trying a dynamic memory allocation, and fallback on a single
pre-allocated bloc of memory, shared by all cpus, protected by a
spinlock

...

-
+	static u64 msg_schedule[80];
+	static DEFINE_SPINLOCK(msg_schedule_lock);
 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 *W = kzalloc(sizeof(msg_schedule), GFP_ATOMIC |

__GFP_NOWARN);

 
+	
+	if (!W) {
+		spin_lock_bh(&msg_schedule_lock);
+		W = msg_schedule;
+	}

If this code can be called from an ISR is the kmalloc()
call safe?

If the above is safe, wouldn't it be better to:
1) try to use the static buffer
2) try to kalloc() a buffer
3) spinwait for the static buffer to be free

	David

Le vendredi 13 janvier 2012 à 13:33 +0200, Alexey Dobriyan a écrit :

Even if its true, its not stable material.

stable teams want obvious patches.

Le vendredi 13 janvier 2012 à 11:45 +0000, David Laight a écrit :

quoted

Trying a dynamic memory allocation, and fallback on a single
pre-allocated bloc of memory, shared by all cpus, protected by a
spinlock

...

quoted

-
+	static u64 msg_schedule[80];
+	static DEFINE_SPINLOCK(msg_schedule_lock);
 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 *W = kzalloc(sizeof(msg_schedule), GFP_ATOMIC |

__GFP_NOWARN);

quoted

 
+	
+	if (!W) {
+		spin_lock_bh(&msg_schedule_lock);
+		W = msg_schedule;
+	}

If this code can be called from an ISR is the kmalloc()
call safe?

Yes, obviously, kmalloc() is IRQ safe.

If the above is safe, wouldn't it be better to:
1) try to use the static buffer
2) try to kalloc() a buffer
3) spinwait for the static buffer to be free

No idea of what you mean, and why you think its better.

kmalloc() propably can give us a block already hot in cpu cache.

On Fri, Jan 13, 2012 at 01:34:13PM +0100, Eric Dumazet wrote:

Le vendredi 13 janvier 2012 à 13:33 +0200, Alexey Dobriyan a écrit :

quoted

On 1/13/12, Eric Dumazet [off-list ref] wrote:

quoted

+	static u64 msg_schedule[80];
+	static DEFINE_SPINLOCK(msg_schedule_lock);

No guys, no.

SHA-512 only needs u64[16] running window for message scheduling.

I'm sending whitespace mangled patch which is only tested
with selfcryptotest passed, so you won't apply something complex.

Stackspace usage drops down to like this:

    -139:   48 81 ec c8 02 00 00    sub    $0x2c8,%rsp
    +136:       48 81 ec 18 01 00 00    sub    $0x118,%rsp

--- a/crypto/sha512_generic.c
+++ b/crypto/sha512_generic.c

@@ -21,8 +21,6 @@
 #include <linux/percpu.h>
 #include <asm/byteorder.h>

-static DEFINE_PER_CPU(u64[80], msg_schedule);
-
 static inline u64 Ch(u64 x, u64 y, u64 z)
 {
         return z ^ (x & (y ^ z));

@@ -80,7 +78,7 @@ static inline void LOAD_OP(int I, u64 *W, const u8 *input)

 static inline void BLEND_OP(int I, u64 *W)
 {
-	W[I] = s1(W[I-2]) + W[I-7] + s0(W[I-15]) + W[I-16];
+	W[I%16] = s1(W[(I-2)%16]) + W[(I-7)%16] + s0(W[(I-15)%16]) + W[I%16];
 }

 static void

@@ -89,38 +87,48 @@ sha512_transform(u64 *state, const u8 *input)
 	u64 a, b, c, d, e, f, g, h, t1, t2;

 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 W[16];

 	/* load the input */
         for (i = 0; i < 16; i++)
                 LOAD_OP(i, W, input);

-        for (i = 16; i < 80; i++) {
-                BLEND_OP(i, W);
-        }
-
 	/* load the state into our registers */
 	a=state[0];   b=state[1];   c=state[2];   d=state[3];
 	e=state[4];   f=state[5];   g=state[6];   h=state[7];

-	/* now iterate */
-	for (i=0; i<80; i+=8) {
-		t1 = h + e1(e) + Ch(e,f,g) + sha512_K[i  ] + W[i  ];
-		t2 = e0(a) + Maj(a,b,c);    d+=t1;    h=t1+t2;
-		t1 = g + e1(d) + Ch(d,e,f) + sha512_K[i+1] + W[i+1];
-		t2 = e0(h) + Maj(h,a,b);    c+=t1;    g=t1+t2;
-		t1 = f + e1(c) + Ch(c,d,e) + sha512_K[i+2] + W[i+2];
-		t2 = e0(g) + Maj(g,h,a);    b+=t1;    f=t1+t2;
-		t1 = e + e1(b) + Ch(b,c,d) + sha512_K[i+3] + W[i+3];
-		t2 = e0(f) + Maj(f,g,h);    a+=t1;    e=t1+t2;
-		t1 = d + e1(a) + Ch(a,b,c) + sha512_K[i+4] + W[i+4];
-		t2 = e0(e) + Maj(e,f,g);    h+=t1;    d=t1+t2;
-		t1 = c + e1(h) + Ch(h,a,b) + sha512_K[i+5] + W[i+5];
-		t2 = e0(d) + Maj(d,e,f);    g+=t1;    c=t1+t2;
-		t1 = b + e1(g) + Ch(g,h,a) + sha512_K[i+6] + W[i+6];
-		t2 = e0(c) + Maj(c,d,e);    f+=t1;    b=t1+t2;
-		t1 = a + e1(f) + Ch(f,g,h) + sha512_K[i+7] + W[i+7];
-		t2 = e0(b) + Maj(b,c,d);    e+=t1;    a=t1+t2;
+#define SHA512_0_15(i, a, b, c, d, e, f, g, h)			\
+	t1 = h + e1(e) + Ch(e, f, g) + sha512_K[i] + W[i];	\
+	t2 = e0(a) + Maj(a,b,c);				\
+	d += t1;						\
+	h = t1 + t2
+
+#define SHA512_16_79(i, a, b, c, d, e, f, g, h)			\
+	BLEND_OP(i, W);						\
+	t1 = h + e1(e) + Ch(e, f, g) + sha512_K[i] + W[(i)%16];	\
+	t2 = e0(a) + Maj(a,b,c);				\
+	d += t1;						\
+	h = t1 + t2
+
+	for (i = 0; i < 16; i += 8) {
+		SHA512_0_15(i, a, b, c, d, e, f, g, h);
+		SHA512_0_15(i + 1, h, a, b, c, d, e, f, g);
+		SHA512_0_15(i + 2, g, h, a, b, c, d, e, f);
+		SHA512_0_15(i + 3, f, g, h, a, b, c, d, e);
+		SHA512_0_15(i + 4, e, f, g, h, a, b, c, d);
+		SHA512_0_15(i + 5, d, e, f, g, h, a, b, c);
+		SHA512_0_15(i + 6, c, d, e, f, g, h, a, b);
+		SHA512_0_15(i + 7, b, c, d, e, f, g, h, a);
+	}
+	for (i = 16; i < 80; i += 8) {
+		SHA512_16_79(i, a, b, c, d, e, f, g, h);
+		SHA512_16_79(i + 1, h, a, b, c, d, e, f, g);
+		SHA512_16_79(i + 2, g, h, a, b, c, d, e, f);
+		SHA512_16_79(i + 3, f, g, h, a, b, c, d, e);
+		SHA512_16_79(i + 4, e, f, g, h, a, b, c, d);
+		SHA512_16_79(i + 5, d, e, f, g, h, a, b, c);
+		SHA512_16_79(i + 6, c, d, e, f, g, h, a, b);
+		SHA512_16_79(i + 7, b, c, d, e, f, g, h, a);
 	}

 	state[0] += a; state[1] += b; state[2] += c; state[3] += d;

@@ -128,8 +136,6 @@ sha512_transform(u64 *state, const u8 *input)

 	/* erase our data */
 	a = b = c = d = e = f = g = h = t1 = t2 = 0;
-	memset(W, 0, sizeof(__get_cpu_var(msg_schedule)));
-	put_cpu_var(msg_schedule);
 }

 static int

Even if its true, its not stable material.

stable teams want obvious patches.

I understand that.

But it _is_ obvious if you see what macro does and original code and
read FIPS 180-2 6.3.2 "SHA-512 Hash Computation" from where
it is obvious that W[i] depends on W[i - 16] and doesn't depend on
earlier values.

This stack reduction patch completely fixes original bug and
doesn't show any AH errors. Given the nature of crypto code
where one bit mistake ruins everything, it should be enough.

commit f9e2bca6c22d75a289a349f869701214d63b5060
aka "crypto: sha512 - Move message schedule W[80] to static percpu area"
created global message schedule area.

If sha512_update will ever be entered twice, hash will be silently
calculated incorrectly.

Probably the easiest way to notice incorrect hashes being calculated is
to run 2 ping floods over AH with hmac(sha512):

	#!/usr/sbin/setkey -f
	flush;
	spdflush;
	add IP1 IP2 ah 25 -A hmac-sha512 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000025;
	add IP2 IP1 ah 52 -A hmac-sha512 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000052;
	spdadd IP1 IP2 any -P out ipsec ah/transport//require;
	spdadd IP2 IP1 any -P in  ipsec ah/transport//require;

XfrmInStateProtoError will start ticking with -EBADMSG being returned
from ah_input(). This never happens with, say, hmac(sha1).

With patch applied (on BOTH sides), XfrmInStateProtoError does not tick
with multiple bidirectional ping flood streams like it doesn't tick
with SHA-1.

After this patch sha512_transform() will start using ~750 bytes of stack on x86_64.
This is OK for simple loads, for something more heavy, stack reduction will be done
separatedly.

Signed-off-by: Alexey Dobriyan <redacted>
Cc: stable@vger.kernel.org
---

 crypto/sha512_generic.c |    6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

--- a/crypto/sha512_generic.c
+++ b/crypto/sha512_generic.c

@@ -21,8 +21,6 @@
 #include <linux/percpu.h>
 #include <asm/byteorder.h>
 
-static DEFINE_PER_CPU(u64[80], msg_schedule);
-
 static inline u64 Ch(u64 x, u64 y, u64 z)
 {
         return z ^ (x & (y ^ z));

@@ -89,7 +87,7 @@ sha512_transform(u64 *state, const u8 *input)
 	u64 a, b, c, d, e, f, g, h, t1, t2;
 
 	int i;
-	u64 *W = get_cpu_var(msg_schedule);
+	u64 W[80];
 
 	/* load the input */
         for (i = 0; i < 16; i++)