[PATCH RFC v1 0/3] remove remaining users of SHA-1

[PATCH RFC v1 0/3] remove remaining users of SHA-1

[Jason A. Donenfeld]

Hi,

There are currently two remaining users of SHA-1 left in the kernel: bpf
tag generation, and ipv6 address calculation. In an effort to reduce
code size and rid ourselves of insecure primitives, this RFC patchset
moves to using the more secure BLAKE2s function. I wanted to get your
feedback on how feasible this patchset is, and if there is some
remaining attachment to SHA-1, why exactly, and what could be done to
mitigate it. Rather than sending a mailing list post just asking, "what
do you think?" I figured it'd be easier to send this as an RFC patchset,
so you see specifically what I mean.

Thoughts? Comments?

Thanks,
Jason

Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: Ard Biesheuvel <ardb@kernel.org>
Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
Cc: linux-crypto@vger.kernel.org

Jason A. Donenfeld (3):
  bpf: move from sha1 to blake2s in tag calculation
  ipv6: move from sha1 to blake2s in address calculation
  crypto: sha1_generic - import lib/sha1.c locally

 crypto/sha1_generic.c | 114 +++++++++++++++++++++++++++++++++++
 include/crypto/sha1.h |  10 ---
 kernel/bpf/core.c     |  39 ++----------
 lib/Makefile          |   2 +-
 lib/sha1.c            | 137 ------------------------------------------
 net/ipv6/addrconf.c   |  31 +++-------
 6 files changed, 128 insertions(+), 205 deletions(-)
 delete mode 100644 lib/sha1.c

-- 
2.34.1

[PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Jason A. Donenfeld]

BLAKE2s is faster and more secure. SHA-1 has been broken for a long time
now. This also removes quite a bit of code, and lets us potentially
remove sha1 from lib, which would further reduce vmlinux size.

Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: Ard Biesheuvel <ardb@kernel.org>
Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
Cc: linux-crypto@vger.kernel.org
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 kernel/bpf/core.c | 39 ++++-----------------------------------
 1 file changed, 4 insertions(+), 35 deletions(-)

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 2405e39d800f..d01976749467 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -33,6 +33,7 @@
 #include <linux/extable.h>
 #include <linux/log2.h>
 #include <linux/bpf_verifier.h>
+#include <crypto/blake2s.h>
 
 #include <asm/barrier.h>
 #include <asm/unaligned.h>
@@ -265,24 +266,16 @@ void __bpf_prog_free(struct bpf_prog *fp)
 
 int bpf_prog_calc_tag(struct bpf_prog *fp)
 {
-	const u32 bits_offset = SHA1_BLOCK_SIZE - sizeof(__be64);
 	u32 raw_size = bpf_prog_tag_scratch_size(fp);
-	u32 digest[SHA1_DIGEST_WORDS];
-	u32 ws[SHA1_WORKSPACE_WORDS];
-	u32 i, bsize, psize, blocks;
 	struct bpf_insn *dst;
 	bool was_ld_map;
-	u8 *raw, *todo;
-	__be32 *result;
-	__be64 *bits;
+	u8 *raw;
+	int i;
 
 	raw = vmalloc(raw_size);
 	if (!raw)
 		return -ENOMEM;
 
-	sha1_init(digest);
-	memset(ws, 0, sizeof(ws));
-
 	/* We need to take out the map fd for the digest calculation
 	 * since they are unstable from user space side.
 	 */
@@ -307,31 +300,7 @@ int bpf_prog_calc_tag(struct bpf_prog *fp)
 		}
 	}
 
-	psize = bpf_prog_insn_size(fp);
-	memset(&raw[psize], 0, raw_size - psize);
-	raw[psize++] = 0x80;
-
-	bsize  = round_up(psize, SHA1_BLOCK_SIZE);
-	blocks = bsize / SHA1_BLOCK_SIZE;
-	todo   = raw;
-	if (bsize - psize >= sizeof(__be64)) {
-		bits = (__be64 *)(todo + bsize - sizeof(__be64));
-	} else {
-		bits = (__be64 *)(todo + bsize + bits_offset);
-		blocks++;
-	}
-	*bits = cpu_to_be64((psize - 1) << 3);
-
-	while (blocks--) {
-		sha1_transform(digest, todo, ws);
-		todo += SHA1_BLOCK_SIZE;
-	}
-
-	result = (__force __be32 *)digest;
-	for (i = 0; i < SHA1_DIGEST_WORDS; i++)
-		result[i] = cpu_to_be32(digest[i]);
-	memcpy(fp->tag, result, sizeof(fp->tag));
-
+	blake2s(fp->tag, raw, NULL, sizeof(fp->tag), bpf_prog_insn_size(fp), 0);
 	vfree(raw);
 	return 0;
 }
-- 
2.34.1

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Toke Høiland-Jørgensen]

[ adding the bpf list - please make sure to include that when sending
  BPF-related patches, not everyone in BPF land follows netdev ]  

"Jason A. Donenfeld" <Jason@zx2c4.com> writes:

> BLAKE2s is faster and more secure. SHA-1 has been broken for a long time
> now. This also removes quite a bit of code, and lets us potentially
> remove sha1 from lib, which would further reduce vmlinux size.

AFAIU, the BPF tag is just used as an opaque (i.e., arbitrary) unique
identifier for BPF programs, without any guarantees of stability. Which
means changing it should be fine; at most we'd confuse some operators
who have memorised the tags of their BPF programs :)

The only other concern I could see would be if it somehow locked us into
that particular algorithm for other future use cases for computing
hashes of BPF programs (say, signing if that ends up being the direction
we go in). But obviously SHA1 would not be a good fit for that anyway,
so the algorithm choice would have to be part of that discussion in any
case.

So all in all, I don't see any issues with making this change for BPF.

-Toke

> Cc: Geert Uytterhoeven <geert@linux-m68k.org>
> Cc: Herbert Xu <herbert@gondor.apana.org.au>
> Cc: Ard Biesheuvel <ardb@kernel.org>
> Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
> Cc: linux-crypto@vger.kernel.org
> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
> ---
>  kernel/bpf/core.c | 39 ++++-----------------------------------
>  1 file changed, 4 insertions(+), 35 deletions(-)
>
> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> index 2405e39d800f..d01976749467 100644
> --- a/kernel/bpf/core.c
> +++ b/kernel/bpf/core.c
> @@ -33,6 +33,7 @@
>  #include <linux/extable.h>
>  #include <linux/log2.h>
>  #include <linux/bpf_verifier.h>
> +#include <crypto/blake2s.h>
>  
>  #include <asm/barrier.h>
>  #include <asm/unaligned.h>
> @@ -265,24 +266,16 @@ void __bpf_prog_free(struct bpf_prog *fp)
>  
>  int bpf_prog_calc_tag(struct bpf_prog *fp)
>  {
> -	const u32 bits_offset = SHA1_BLOCK_SIZE - sizeof(__be64);
>  	u32 raw_size = bpf_prog_tag_scratch_size(fp);
> -	u32 digest[SHA1_DIGEST_WORDS];
> -	u32 ws[SHA1_WORKSPACE_WORDS];
> -	u32 i, bsize, psize, blocks;
>  	struct bpf_insn *dst;
>  	bool was_ld_map;
> -	u8 *raw, *todo;
> -	__be32 *result;
> -	__be64 *bits;
> +	u8 *raw;
> +	int i;
>  
>  	raw = vmalloc(raw_size);
>  	if (!raw)
>  		return -ENOMEM;
>  
> -	sha1_init(digest);
> -	memset(ws, 0, sizeof(ws));
> -
>  	/* We need to take out the map fd for the digest calculation
>  	 * since they are unstable from user space side.
>  	 */
> @@ -307,31 +300,7 @@ int bpf_prog_calc_tag(struct bpf_prog *fp)
>  		}
>  	}
>  
> -	psize = bpf_prog_insn_size(fp);
> -	memset(&raw[psize], 0, raw_size - psize);
> -	raw[psize++] = 0x80;
> -
> -	bsize  = round_up(psize, SHA1_BLOCK_SIZE);
> -	blocks = bsize / SHA1_BLOCK_SIZE;
> -	todo   = raw;
> -	if (bsize - psize >= sizeof(__be64)) {
> -		bits = (__be64 *)(todo + bsize - sizeof(__be64));
> -	} else {
> -		bits = (__be64 *)(todo + bsize + bits_offset);
> -		blocks++;
> -	}
> -	*bits = cpu_to_be64((psize - 1) << 3);
> -
> -	while (blocks--) {
> -		sha1_transform(digest, todo, ws);
> -		todo += SHA1_BLOCK_SIZE;
> -	}
> -
> -	result = (__force __be32 *)digest;
> -	for (i = 0; i < SHA1_DIGEST_WORDS; i++)
> -		result[i] = cpu_to_be32(digest[i]);
> -	memcpy(fp->tag, result, sizeof(fp->tag));
> -
> +	blake2s(fp->tag, raw, NULL, sizeof(fp->tag), bpf_prog_insn_size(fp), 0);
>  	vfree(raw);
>  	return 0;
>  }
> -- 
> 2.34.1

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Alexei Starovoitov]

On Wed, Jan 12, 2022 at 5:14 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> [ adding the bpf list - please make sure to include that when sending
>   BPF-related patches, not everyone in BPF land follows netdev ]
>
> "Jason A. Donenfeld" <Jason@zx2c4.com> writes:
>
> > BLAKE2s is faster and more secure. SHA-1 has been broken for a long time
> > now. This also removes quite a bit of code, and lets us potentially
> > remove sha1 from lib, which would further reduce vmlinux size.
>
> AFAIU, the BPF tag is just used as an opaque (i.e., arbitrary) unique
> identifier for BPF programs, without any guarantees of stability. Which
> means changing it should be fine; at most we'd confuse some operators
> who have memorised the tags of their BPF programs :)
>
> The only other concern I could see would be if it somehow locked us into
> that particular algorithm for other future use cases for computing
> hashes of BPF programs (say, signing if that ends up being the direction
> we go in). But obviously SHA1 would not be a good fit for that anyway,
> so the algorithm choice would have to be part of that discussion in any
> case.
>
> So all in all, I don't see any issues with making this change for BPF.

Nack.
It's part of api. We cannot change it.

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Jason A. Donenfeld]

Hi Alexei,

On 1/13/22, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> Nack.
> It's part of api. We cannot change it.

This is an RFC patchset, so there's no chance that it'll actually be
applied as-is, and hence there's no need for the strong hammer nack.
The point of "request for comments" is comments. Specifically here,
I'm searching for information on the ins and outs of *why* it might be
hard to change. How does userspace use this? Why must this 64-bit
number be unchanged? Why did you do things this way originally? Etc.
If you could provide a bit of background, we might be able to shake
out a solution somewhere in there.

Thanks,
Jason

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Alexei Starovoitov]

On Thu, Jan 13, 2022 at 4:27 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> Hi Alexei,
>
> On 1/13/22, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> > Nack.
> > It's part of api. We cannot change it.
>
> This is an RFC patchset, so there's no chance that it'll actually be
> applied as-is, and hence there's no need for the strong hammer nack.
> The point of "request for comments" is comments. Specifically here,
> I'm searching for information on the ins and outs of *why* it might be
> hard to change. How does userspace use this? Why must this 64-bit
> number be unchanged? Why did you do things this way originally? Etc.
> If you could provide a bit of background, we might be able to shake
> out a solution somewhere in there.

There is no problem with the code and nothing to be fixed.

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Geert Uytterhoeven]

Hi Alexei,

On Thu, Jan 13, 2022 at 11:45 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Thu, Jan 13, 2022 at 4:27 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> > On 1/13/22, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> > > Nack.
> > > It's part of api. We cannot change it.
> >
> > This is an RFC patchset, so there's no chance that it'll actually be
> > applied as-is, and hence there's no need for the strong hammer nack.
> > The point of "request for comments" is comments. Specifically here,
> > I'm searching for information on the ins and outs of *why* it might be
> > hard to change. How does userspace use this? Why must this 64-bit
> > number be unchanged? Why did you do things this way originally? Etc.
> > If you could provide a bit of background, we might be able to shake
> > out a solution somewhere in there.
>
> There is no problem with the code and nothing to be fixed.

"Your Jedi mind tricks don't work on me."

The "problem" is that this is one of the few last users of SHA-1 in
the kernel.

Can you please answer the questions above, so we can get a better
understanding?
Thanks!

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Jason A. Donenfeld]

Hi Alexei,

On Thu, Jan 13, 2022 at 11:45 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Thu, Jan 13, 2022 at 4:27 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> >
> > Hi Alexei,
> >
> > On 1/13/22, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> > > Nack.
> > > It's part of api. We cannot change it.
> >
> > This is an RFC patchset, so there's no chance that it'll actually be
> > applied as-is, and hence there's no need for the strong hammer nack.
> > The point of "request for comments" is comments. Specifically here,
> > I'm searching for information on the ins and outs of *why* it might be
> > hard to change. How does userspace use this? Why must this 64-bit
> > number be unchanged? Why did you do things this way originally? Etc.
> > If you could provide a bit of background, we might be able to shake
> > out a solution somewhere in there.
>
> There is no problem with the code and nothing to be fixed.

Yes yes, my mama says I'm the specialist snowflake of a boy too. That
makes two of us ice crystals, falling from the winter heavens,
blessing vim with our beautiful shapes and frosty code.

Anyway, back to reality, as Geert points out, we're hoping to be able
to remove lib/sha1.c from vmlinux (see 3/3 of this series) for
codesize, and this bpf usage here is one of two remaining usages of
it. So I was hoping that by sending this RFC, it might elicit a bit
more information about the ecosystem around the usage of the function,
so that we can start trying to think of creative solutions to sunset
it.

I started trying to figure out what's up there and wound up with some
more questions. My primary one is why you're okay with such a weak
"checksum" -- the thing is only 64-bits, and as you told Andy Polyakov
in 2016 when he tried to stop you from using SHA-1, "Andy, please read
the code. \ we could have used jhash there just as well. \ Collisions
are fine."

Looking at https://github.com/iovisor/bcc/blob/e17c4f7324d8fc5cc24ba8ee1db451666cd7ced3/src/cc/bpf_module.cc#L571
I see:

  err = bpf_prog_compute_tag(insns, prog_len, &tag1);
  if (err)
    return err;
  err = bpf_prog_get_tag(prog_fd, &tag2);
  if (err)
    return err;
  if (tag1 != tag2) {
    fprintf(stderr, "prog tag mismatch %llx %llx\n", tag1, tag2);

So it's clearly a check for something. A collision there might prove pesky:

  char buf[128];
  ::snprintf(buf, sizeof(buf), BCC_PROG_TAG_DIR "/bpf_prog_%llx", tag1);
  err = mkdir(buf, 0777);

Maybe you don't really see a security problem here, because these
programs are root loadable anyway? But I imagine things will
ultimately get more complicated later on down the road when bpf
becomes more modular and less privileged and more namespaced -- the
usual evolution of these sorts of features.

So I'm wondering - why not just do this in a more robust way entirely,
and always export a sufficiently sized blake2s hash? That way we'll
never have these sorts of shenanigans to care about. If that's not a
sensible thing to do, it's likely that I _still_ don't quite grok the
purpose of the program tag, in which case, I'd be all ears to an
explanation.

Jason

[ PS: As an aside, I noticed some things in the userspace tag
calculation code at
https://github.com/iovisor/bcc/blob/aa7200b9b2a7a2ce2e8a6f0dc1f456f3f93af1da/src/cc/libbpf.c#L536
- you probably shouldn't use AF_ALG for things that are software based
and can be done in userspace faster. And the unconditional
__builtin_bswap64 there means that the code will fail on big endian
systems. I know you mostly only care about x86 and all, but <endian.h>
might make this easy to fix. ]

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Ard Biesheuvel]

On Fri, 14 Jan 2022 at 15:12, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> Hi Alexei,
>
> On Thu, Jan 13, 2022 at 11:45 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> > On Thu, Jan 13, 2022 at 4:27 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> > >
> > > Hi Alexei,
> > >
> > > On 1/13/22, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> > > > Nack.
> > > > It's part of api. We cannot change it.
> > >
> > > This is an RFC patchset, so there's no chance that it'll actually be
> > > applied as-is, and hence there's no need for the strong hammer nack.
> > > The point of "request for comments" is comments. Specifically here,
> > > I'm searching for information on the ins and outs of *why* it might be
> > > hard to change. How does userspace use this? Why must this 64-bit
> > > number be unchanged? Why did you do things this way originally? Etc.
> > > If you could provide a bit of background, we might be able to shake
> > > out a solution somewhere in there.
> >
> > There is no problem with the code and nothing to be fixed.
>
> Yes yes, my mama says I'm the specialist snowflake of a boy too. That
> makes two of us ice crystals, falling from the winter heavens,
> blessing vim with our beautiful shapes and frosty code.
>

Can we please keep it professional, guys?

> Anyway, back to reality, as Geert points out, we're hoping to be able
> to remove lib/sha1.c from vmlinux (see 3/3 of this series) for
> codesize, and this bpf usage here is one of two remaining usages of
> it. So I was hoping that by sending this RFC, it might elicit a bit
> more information about the ecosystem around the usage of the function,
> so that we can start trying to think of creative solutions to sunset
> it.
>

Yeah, so the issue is that, at *some* point, SHA-1 is going to have to
go. So it would be helpful if Alexei could clarify *why* he doesn't
see this as a problem. The fact that it is broken means that it is no
longer intractable to forge collisions, which likley means that SHA-1
no longer fulfills the task that you wanted it to do in the first
place.

And just dismissing the issue every time it comes up won't make the
problem go away. There are people on this thread that have a much
better handle on how to use crypto safely and responsibly, and it is
in everybody's interest if we can come to an agreement about when and
how SHA-1 will be phased out.


> I started trying to figure out what's up there and wound up with some
> more questions. My primary one is why you're okay with such a weak
> "checksum" -- the thing is only 64-bits, and as you told Andy Polyakov
> in 2016 when he tried to stop you from using SHA-1, "Andy, please read
> the code. \ we could have used jhash there just as well. \ Collisions
> are fine."
>
> Looking at https://github.com/iovisor/bcc/blob/e17c4f7324d8fc5cc24ba8ee1db451666cd7ced3/src/cc/bpf_module.cc#L571
> I see:
>
>   err = bpf_prog_compute_tag(insns, prog_len, &tag1);
>   if (err)
>     return err;
>   err = bpf_prog_get_tag(prog_fd, &tag2);
>   if (err)
>     return err;
>   if (tag1 != tag2) {
>     fprintf(stderr, "prog tag mismatch %llx %llx\n", tag1, tag2);
>
> So it's clearly a check for something. A collision there might prove pesky:
>
>   char buf[128];
>   ::snprintf(buf, sizeof(buf), BCC_PROG_TAG_DIR "/bpf_prog_%llx", tag1);
>   err = mkdir(buf, 0777);
>
> Maybe you don't really see a security problem here, because these
> programs are root loadable anyway? But I imagine things will
> ultimately get more complicated later on down the road when bpf
> becomes more modular and less privileged and more namespaced -- the
> usual evolution of these sorts of features.
>
> So I'm wondering - why not just do this in a more robust way entirely,
> and always export a sufficiently sized blake2s hash? That way we'll
> never have these sorts of shenanigans to care about. If that's not a
> sensible thing to do, it's likely that I _still_ don't quite grok the
> purpose of the program tag, in which case, I'd be all ears to an
> explanation.
>
> Jason
>
> [ PS: As an aside, I noticed some things in the userspace tag
> calculation code at
> https://github.com/iovisor/bcc/blob/aa7200b9b2a7a2ce2e8a6f0dc1f456f3f93af1da/src/cc/libbpf.c#L536
> - you probably shouldn't use AF_ALG for things that are software based
> and can be done in userspace faster. And the unconditional
> __builtin_bswap64 there means that the code will fail on big endian
> systems. I know you mostly only care about x86 and all, but <endian.h>
> might make this easy to fix. ]

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Jason A. Donenfeld]

On Fri, Jan 14, 2022 at 4:08 PM Ard Biesheuvel <ardb@kernel.org> wrote:
> Yeah, so the issue is that, at *some* point, SHA-1 is going to have to
> go. So it would be helpful if Alexei could clarify *why* he doesn't
> see this as a problem. The fact that it is broken means that it is no
> longer intractable to forge collisions, which likley means that SHA-1
> no longer fulfills the task that you wanted it to do in the first
> place.

I think the reason that Alexei doesn't think that the SHA-1 choice
really matters is because the result is being truncated to 64-bits, so
collisions are easy anyway, regardless of which hash function is
chosen (birthday bound and all). But from Geert's perspective, that
SHA-1 is still taking up precious bytes in m68k builds. And from my
perspective, it's poor form and clutters vmlinux, and plus, now I'm
curious about why this isn't using a more appropriately sized tag in
the first place.

On Fri, Jan 14, 2022 at 3:12 PM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> "checksum" -- the thing is only 64-bits, and as you told Andy Polyakov

Whoops, meant Lutomirski here. x86 Andy, not crypto Andy :)

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Geert Uytterhoeven]

Hi Jason,

On Fri, Jan 14, 2022 at 4:20 PM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> I think the reason that Alexei doesn't think that the SHA-1 choice
> really matters is because the result is being truncated to 64-bits, so
> collisions are easy anyway, regardless of which hash function is
> chosen (birthday bound and all). But from Geert's perspective, that
> SHA-1 is still taking up precious bytes in m68k builds. And from my
> perspective, it's poor form and clutters vmlinux, and plus, now I'm
> curious about why this isn't using a more appropriately sized tag in
> the first place.

Not just on m68k. Same on other architectures.
Yes, people do make products with SoCs with 8 MiB of builtin SRAM,
running Linux. They might stay away from BPF, though ;-)

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

RE: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[David Laight]

From: Jason A. Donenfeld
> Sent: 14 January 2022 15:21
> 
> On Fri, Jan 14, 2022 at 4:08 PM Ard Biesheuvel <ardb@kernel.org> wrote:
> > Yeah, so the issue is that, at *some* point, SHA-1 is going to have to
> > go. So it would be helpful if Alexei could clarify *why* he doesn't
> > see this as a problem. The fact that it is broken means that it is no
> > longer intractable to forge collisions, which likley means that SHA-1
> > no longer fulfills the task that you wanted it to do in the first
> > place.
> 
> I think the reason that Alexei doesn't think that the SHA-1 choice
> really matters is because the result is being truncated to 64-bits, so
> collisions are easy anyway...

Which probably means that SHA-1 is complete overkill and something
much simpler could have been used instead.
Is the buffer even big enough to have ever warranted the massive
unrolling of the sha-1 function.
(I suspect that just destroys the I-cache on most cpu.)

The IPv6 address case seems even more insane - how many bytes
are actually being hashed.
The unrolled loop is only likely to be sane for large (megabyte)
buffers.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Alexei Starovoitov]

On Fri, Jan 14, 2022 at 7:08 AM Ard Biesheuvel <ardb@kernel.org> wrote:
>
> Yeah, so the issue is that, at *some* point, SHA-1 is going to have to
> go.

sha1 cannot be removed from the kernel.
See AF_ALG and iproute2 source for reference.

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Jason A. Donenfeld]

On Fri, Jan 14, 2022 at 5:19 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Jan 14, 2022 at 7:08 AM Ard Biesheuvel <ardb@kernel.org> wrote:
> >
> > Yeah, so the issue is that, at *some* point, SHA-1 is going to have to
> > go.
>
> sha1 cannot be removed from the kernel.
> See AF_ALG and iproute2 source for reference.

It can be removed from vmlinux, and be folded into the crypto API's
generic implementation where it belongs, which then can be built as a
module or not built at all, depending on configuration. Please see the
3/3 patch in this series to see what that looks like:
https://lore.kernel.org/lkml/20220114142015.87974-4-Jason@zx2c4.com/

Meanwhile, you have not replied to any of the substantive issues I
brought up. I'd appreciate you doing so.

Thank you,
Jason

Re: [PATCH RFC v1 1/3] bpf: move from sha1 to blake2s in tag calculation

[Jeffrey Walton]

On Wed, Jan 12, 2022 at 8:13 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> [ adding the bpf list - please make sure to include that when sending
>   BPF-related patches, not everyone in BPF land follows netdev ]
>
> "Jason A. Donenfeld" <Jason@zx2c4.com> writes:
>
> > BLAKE2s is faster and more secure. SHA-1 has been broken for a long time
> > now. This also removes quite a bit of code, and lets us potentially
> > remove sha1 from lib, which would further reduce vmlinux size.
>
> AFAIU, the BPF tag is just used as an opaque (i.e., arbitrary) unique
> identifier for BPF programs, without any guarantees of stability. Which
> means changing it should be fine; at most we'd confuse some operators
> who have memorised the tags of their BPF programs :)
>
> The only other concern I could see would be if it somehow locked us into
> that particular algorithm for other future use cases for computing
> hashes of BPF programs (say, signing if that ends up being the direction
> we go in). But obviously SHA1 would not be a good fit for that anyway,
> so the algorithm choice would have to be part of that discussion in any
> case.
>
> So all in all, I don't see any issues with making this change for BPF.

Somewhat related, if BPF is going to move from SHA to something, then
consider SipHash. Here are the numbers I regularly observe. They
remain relative the same on 64-bit platforms:

    * SHA-1: 4.31 cpb using SSE2
    * BLAKE2s: 4.84 cpb using SSE4.1
    * BLAKE2b: 3.49 cpb using SSE4.1
    * SipHash 2-4: 1.54 cpb using C/C++
    * SipHash 4-8: 2.55 cpb using C/C++

If BPF is Ok with 64-bit tags, then SipHash 2-4 is probably what you
want on the wish list.

Jeff

[PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Jason A. Donenfeld]

BLAKE2s is faster and more secure. SHA-1 has been broken for a long time
now. This also removes some code complexity, and lets us potentially
remove sha1 from lib, which would further reduce vmlinux size.

Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: Ard Biesheuvel <ardb@kernel.org>
Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
Cc: linux-crypto@vger.kernel.org
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 net/ipv6/addrconf.c | 31 +++++++++----------------------
 1 file changed, 9 insertions(+), 22 deletions(-)

diff --git a/net/ipv6/addrconf.c b/net/ipv6/addrconf.c
index 3445f8017430..f5cb534aa261 100644
--- a/net/ipv6/addrconf.c
+++ b/net/ipv6/addrconf.c
@@ -61,7 +61,7 @@
 #include <linux/delay.h>
 #include <linux/notifier.h>
 #include <linux/string.h>
-#include <linux/hash.h>
+#include <crypto/blake2s.h>
 
 #include <net/net_namespace.h>
 #include <net/sock.h>
@@ -3225,25 +3225,16 @@ static int ipv6_generate_stable_address(struct in6_addr *address,
 					const struct inet6_dev *idev)
 {
 	static DEFINE_SPINLOCK(lock);
-	static __u32 digest[SHA1_DIGEST_WORDS];
-	static __u32 workspace[SHA1_WORKSPACE_WORDS];
-
-	static union {
-		char __data[SHA1_BLOCK_SIZE];
-		struct {
-			struct in6_addr secret;
-			__be32 prefix[2];
-			unsigned char hwaddr[MAX_ADDR_LEN];
-			u8 dad_count;
-		} __packed;
-	} data;
-
+	struct {
+		struct in6_addr secret;
+		__be32 prefix[2];
+		unsigned char hwaddr[MAX_ADDR_LEN];
+		u8 dad_count;
+	} __packed data;
 	struct in6_addr secret;
 	struct in6_addr temp;
 	struct net *net = dev_net(idev->dev);
 
-	BUILD_BUG_ON(sizeof(data.__data) != sizeof(data));
-
 	if (idev->cnf.stable_secret.initialized)
 		secret = idev->cnf.stable_secret.secret;
 	else if (net->ipv6.devconf_dflt->stable_secret.initialized)
@@ -3254,20 +3245,16 @@ static int ipv6_generate_stable_address(struct in6_addr *address,
 retry:
 	spin_lock_bh(&lock);
 
-	sha1_init(digest);
 	memset(&data, 0, sizeof(data));
-	memset(workspace, 0, sizeof(workspace));
 	memcpy(data.hwaddr, idev->dev->perm_addr, idev->dev->addr_len);
 	data.prefix[0] = address->s6_addr32[0];
 	data.prefix[1] = address->s6_addr32[1];
 	data.secret = secret;
 	data.dad_count = dad_count;
 
-	sha1_transform(digest, data.__data, workspace);
-
 	temp = *address;
-	temp.s6_addr32[2] = (__force __be32)digest[0];
-	temp.s6_addr32[3] = (__force __be32)digest[1];
+	blake2s((u8 *)&temp.s6_addr32[2], (u8 *)&data, NULL,
+		sizeof(temp.s6_addr32[2]) * 2, sizeof(data), 0);
 
 	spin_unlock_bh(&lock);
 
-- 
2.34.1

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Jason A. Donenfeld]

For the record, I've been able to simplify this even more in my
remove-sha1 branch: https://git.zx2c4.com/linux-dev/log/?h=remove-sha1
. We no longer need the packed struct and we handle that secret a bit
better too. If this patchset moves onto a non-RFC v2, that'll be part
of it.

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Toke Høiland-Jørgensen]

"Jason A. Donenfeld" <Jason@zx2c4.com> writes:

> BLAKE2s is faster and more secure. SHA-1 has been broken for a long time
> now. This also removes some code complexity, and lets us potentially
> remove sha1 from lib, which would further reduce vmlinux size.

So this one is a bit less obvious than the BPF case: the "stable address
generation" is supposed to result in generating addresses that are,
well, stable. The documentation for the stable_secret sysctl implies
that this should be for the lifetime of the system:

       It is recommended to generate this secret during installation
       of a system and keep it stable after that.

However, if we make this change, systems setting a stable_secret and
using addr_gen_mode 2 or 3 will come up with a completely different
address after a kernel upgrade. Which would be bad for any operator
expecting to be able to find their machine again after a reboot,
especially if it is accessed remotely.

I haven't ever used this feature myself, though, or seen it in use. So I
don't know if this is purely a theoretical concern, or if the
stable_address feature is actually used in this way in practice. If it
is, I guess the switch would have to be opt-in, which kinda defeats the
purpose, no (i.e., we'd have to keep the SHA1 code around)?

Adding some of the people involved in the original work on stable
address generation in the hope that they can shed some light on the
real-world uses for this feature.

-Toke

> Cc: Geert Uytterhoeven <geert@linux-m68k.org>
> Cc: Herbert Xu <herbert@gondor.apana.org.au>
> Cc: Ard Biesheuvel <ardb@kernel.org>
> Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
> Cc: linux-crypto@vger.kernel.org
> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
> ---
>  net/ipv6/addrconf.c | 31 +++++++++----------------------
>  1 file changed, 9 insertions(+), 22 deletions(-)
>
> diff --git a/net/ipv6/addrconf.c b/net/ipv6/addrconf.c
> index 3445f8017430..f5cb534aa261 100644
> --- a/net/ipv6/addrconf.c
> +++ b/net/ipv6/addrconf.c
> @@ -61,7 +61,7 @@
>  #include <linux/delay.h>
>  #include <linux/notifier.h>
>  #include <linux/string.h>
> -#include <linux/hash.h>
> +#include <crypto/blake2s.h>
>  
>  #include <net/net_namespace.h>
>  #include <net/sock.h>
> @@ -3225,25 +3225,16 @@ static int ipv6_generate_stable_address(struct in6_addr *address,
>  					const struct inet6_dev *idev)
>  {
>  	static DEFINE_SPINLOCK(lock);
> -	static __u32 digest[SHA1_DIGEST_WORDS];
> -	static __u32 workspace[SHA1_WORKSPACE_WORDS];
> -
> -	static union {
> -		char __data[SHA1_BLOCK_SIZE];
> -		struct {
> -			struct in6_addr secret;
> -			__be32 prefix[2];
> -			unsigned char hwaddr[MAX_ADDR_LEN];
> -			u8 dad_count;
> -		} __packed;
> -	} data;
> -
> +	struct {
> +		struct in6_addr secret;
> +		__be32 prefix[2];
> +		unsigned char hwaddr[MAX_ADDR_LEN];
> +		u8 dad_count;
> +	} __packed data;
>  	struct in6_addr secret;
>  	struct in6_addr temp;
>  	struct net *net = dev_net(idev->dev);
>  
> -	BUILD_BUG_ON(sizeof(data.__data) != sizeof(data));
> -
>  	if (idev->cnf.stable_secret.initialized)
>  		secret = idev->cnf.stable_secret.secret;
>  	else if (net->ipv6.devconf_dflt->stable_secret.initialized)
> @@ -3254,20 +3245,16 @@ static int ipv6_generate_stable_address(struct in6_addr *address,
>  retry:
>  	spin_lock_bh(&lock);
>  
> -	sha1_init(digest);
>  	memset(&data, 0, sizeof(data));
> -	memset(workspace, 0, sizeof(workspace));
>  	memcpy(data.hwaddr, idev->dev->perm_addr, idev->dev->addr_len);
>  	data.prefix[0] = address->s6_addr32[0];
>  	data.prefix[1] = address->s6_addr32[1];
>  	data.secret = secret;
>  	data.dad_count = dad_count;
>  
> -	sha1_transform(digest, data.__data, workspace);
> -
>  	temp = *address;
> -	temp.s6_addr32[2] = (__force __be32)digest[0];
> -	temp.s6_addr32[3] = (__force __be32)digest[1];
> +	blake2s((u8 *)&temp.s6_addr32[2], (u8 *)&data, NULL,
> +		sizeof(temp.s6_addr32[2]) * 2, sizeof(data), 0);
>  
>  	spin_unlock_bh(&lock);
>  
> -- 
> 2.34.1

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Jason A. Donenfeld]

Hi Toke,

On 1/13/22, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> However, if we make this change, systems setting a stable_secret and
> using addr_gen_mode 2 or 3 will come up with a completely different
> address after a kernel upgrade. Which would be bad for any operator
> expecting to be able to find their machine again after a reboot,
> especially if it is accessed remotely.
>
> I haven't ever used this feature myself, though, or seen it in use. So I
> don't know if this is purely a theoretical concern, or if the
> stable_address feature is actually used in this way in practice. If it
> is, I guess the switch would have to be opt-in, which kinda defeats the
> purpose, no (i.e., we'd have to keep the SHA1 code around

I'm not even so sure that's true. That was my worry at first, but
actually, looking at this more closely, DAD means that the address can
be changed anyway - a byte counter is hashed in - so there's no
gurantee there.

There's also the other aspect that open coding sha1_transform like
this and prepending it with the secret (rather than a better
construction) isn't so great... Take a look at the latest version of
this in my branch to see a really nice simplification and security
improvement:

https://git.zx2c4.com/linux-dev/log/?h=remove-sha1

Jason

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Hannes Frederic Sowa]

Hello,

On 13.01.22 00:31, Jason A. Donenfeld wrote:
> On 1/13/22, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>> However, if we make this change, systems setting a stable_secret and
>> using addr_gen_mode 2 or 3 will come up with a completely different
>> address after a kernel upgrade. Which would be bad for any operator
>> expecting to be able to find their machine again after a reboot,
>> especially if it is accessed remotely.
>>
>> I haven't ever used this feature myself, though, or seen it in use. So I
>> don't know if this is purely a theoretical concern, or if the
>> stable_address feature is actually used in this way in practice. If it
>> is, I guess the switch would have to be opt-in, which kinda defeats the
>> purpose, no (i.e., we'd have to keep the SHA1 code around

Yes, it is hard to tell if such a change would have real world impact 
due to not knowing its actual usage in the field - but I would avoid 
such a change. The reason for this standard is to have stable addresses 
across reboots. The standard is widely used but most servers or desktops 
might get their stable privacy addresses being generated by user space 
network management systems (NetworkManager/networkd) nowadays. I would 
guess it could be used in embedded installations.

The impact of this change could be annoying though: users could suddenly 
lose connectivity due to e.g. changes to the default gateway after an 
upgrade.

> I'm not even so sure that's true. That was my worry at first, but
> actually, looking at this more closely, DAD means that the address can
> be changed anyway - a byte counter is hashed in - so there's no
> gurantee there.

The duplicate address detection counter is a way to merely provide basic 
network connectivity in case of duplicate addresses on the network 
(maybe some kind misconfiguration or L2 attack). Such detected addresses 
would show up in the kernel log and an administrator should investigate 
and clean up the situation. Afterwards bringing the interface down and 
up again should revert the interface to its initial (dad_counter == 0) 
address.

> There's also the other aspect that open coding sha1_transform like
> this and prepending it with the secret (rather than a better
> construction) isn't so great... Take a look at the latest version of
> this in my branch to see a really nice simplification and security
> improvement:
> 
> https://git.zx2c4.com/linux-dev/log/?h=remove-sha1

All in all, I consider the hash produced here as being part of uAPI 
unfortunately and thus cannot be changed. It is unfortunate that it 
can't easily be improved (I assume a separate mode for this is not 
reasonable). The patches definitely look like a nice cleanup.

Would this be the only user of sha_transform left?

Bye,
Hannes

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Ard Biesheuvel]

On Thu, 13 Jan 2022 at 12:15, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
>
> Hello,
>
> On 13.01.22 00:31, Jason A. Donenfeld wrote:
> > On 1/13/22, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> >> However, if we make this change, systems setting a stable_secret and
> >> using addr_gen_mode 2 or 3 will come up with a completely different
> >> address after a kernel upgrade. Which would be bad for any operator
> >> expecting to be able to find their machine again after a reboot,
> >> especially if it is accessed remotely.
> >>
> >> I haven't ever used this feature myself, though, or seen it in use. So I
> >> don't know if this is purely a theoretical concern, or if the
> >> stable_address feature is actually used in this way in practice. If it
> >> is, I guess the switch would have to be opt-in, which kinda defeats the
> >> purpose, no (i.e., we'd have to keep the SHA1 code around
>
> Yes, it is hard to tell if such a change would have real world impact
> due to not knowing its actual usage in the field - but I would avoid
> such a change. The reason for this standard is to have stable addresses
> across reboots. The standard is widely used but most servers or desktops
> might get their stable privacy addresses being generated by user space
> network management systems (NetworkManager/networkd) nowadays. I would
> guess it could be used in embedded installations.
>
> The impact of this change could be annoying though: users could suddenly
> lose connectivity due to e.g. changes to the default gateway after an
> upgrade.
>
> > I'm not even so sure that's true. That was my worry at first, but
> > actually, looking at this more closely, DAD means that the address can
> > be changed anyway - a byte counter is hashed in - so there's no
> > gurantee there.
>
> The duplicate address detection counter is a way to merely provide basic
> network connectivity in case of duplicate addresses on the network
> (maybe some kind misconfiguration or L2 attack). Such detected addresses
> would show up in the kernel log and an administrator should investigate
> and clean up the situation. Afterwards bringing the interface down and
> up again should revert the interface to its initial (dad_counter == 0)
> address.
>
> > There's also the other aspect that open coding sha1_transform like
> > this and prepending it with the secret (rather than a better
> > construction) isn't so great... Take a look at the latest version of
> > this in my branch to see a really nice simplification and security
> > improvement:
> >
> > https://git.zx2c4.com/linux-dev/log/?h=remove-sha1
>
> All in all, I consider the hash produced here as being part of uAPI
> unfortunately and thus cannot be changed. It is unfortunate that it
> can't easily be improved (I assume a separate mode for this is not
> reasonable). The patches definitely look like a nice cleanup.
>
> Would this be the only user of sha_transform left?
>

The question is not whether but when we can/will change this.

SHA-1 is broken and should be removed at *some* point, so unless the
feature itself is going to be obsolete, its implementation will need
to switch to a PRF that fulfils the requirements in RFC7217 once SHA-1
ceases to do so.

And I should also point out that the current implementation does not
even use SHA-1 correctly, as it omits the finalization step. This may
or may not matter in practice, but it deviates from crypto best
practices, as well as from RFC7217

I already pointed out to Jason (in private) that the PRF does not need
to be based on a cryptographic hash, so as far as I can tell, siphash
would be a suitable candidate here as well, and I already switched the
TCP fastopen code to that in the past. But SHA-1 definitely has to go.

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Jason A. Donenfeld]

On 1/13/22, Ard Biesheuvel <ardb@kernel.org> wrote:
>
> The question is not whether but when we can/will change this.
>
> SHA-1 is broken and should be removed at *some* point, so unless the
> feature itself is going to be obsolete, its implementation will need
> to switch to a PRF that fulfils the requirements in RFC7217 once SHA-1
> ceases to do so.
>
> And I should also point out that the current implementation does not
> even use SHA-1 correctly, as it omits the finalization step. This may
> or may not matter in practice, but it deviates from crypto best
> practices, as well as from RFC7217
>
> I already pointed out to Jason (in private) that the PRF does not need
> to be based on a cryptographic hash, so as far as I can tell, siphash
> would be a suitable candidate here as well, and I already switched the
> TCP fastopen code to that in the past. But SHA-1 definitely has to go.
>

Correction: this should be a cryptographically secure. That's part of
the point of moving away from SHA-1 of course. But fortunately,
siphash *is*
considered to be cryptographically secure. Whether you want blake2s's
keyed mode or siphash doesn't really matter to me. I thought the
former's API mapped a bit neater here.

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Ard Biesheuvel]

On Thu, 13 Jan 2022 at 13:22, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> On 1/13/22, Ard Biesheuvel <ardb@kernel.org> wrote:
> >
> > The question is not whether but when we can/will change this.
> >
> > SHA-1 is broken and should be removed at *some* point, so unless the
> > feature itself is going to be obsolete, its implementation will need
> > to switch to a PRF that fulfils the requirements in RFC7217 once SHA-1
> > ceases to do so.
> >
> > And I should also point out that the current implementation does not
> > even use SHA-1 correctly, as it omits the finalization step. This may
> > or may not matter in practice, but it deviates from crypto best
> > practices, as well as from RFC7217
> >
> > I already pointed out to Jason (in private) that the PRF does not need
> > to be based on a cryptographic hash, so as far as I can tell, siphash
> > would be a suitable candidate here as well, and I already switched the
> > TCP fastopen code to that in the past. But SHA-1 definitely has to go.
> >
>
> Correction: this should be a cryptographically secure.

Of course. I said it does not need to be based on a cryptographic *hash*.

> That's part of
> the point of moving away from SHA-1 of course. But fortunately,
> siphash *is*
> considered to be cryptographically secure. Whether you want blake2s's
> keyed mode or siphash doesn't really matter to me. I thought the
> former's API mapped a bit neater here.

Fair enough. This is not on a hot path anyway, so it doesn't really
matter performance wise.

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Toke Høiland-Jørgensen]

Ard Biesheuvel <ardb@kernel.org> writes:

> On Thu, 13 Jan 2022 at 12:15, Hannes Frederic Sowa
> <hannes@stressinduktion.org> wrote:
>>
>> Hello,
>>
>> On 13.01.22 00:31, Jason A. Donenfeld wrote:
>> > On 1/13/22, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>> >> However, if we make this change, systems setting a stable_secret and
>> >> using addr_gen_mode 2 or 3 will come up with a completely different
>> >> address after a kernel upgrade. Which would be bad for any operator
>> >> expecting to be able to find their machine again after a reboot,
>> >> especially if it is accessed remotely.
>> >>
>> >> I haven't ever used this feature myself, though, or seen it in use. So I
>> >> don't know if this is purely a theoretical concern, or if the
>> >> stable_address feature is actually used in this way in practice. If it
>> >> is, I guess the switch would have to be opt-in, which kinda defeats the
>> >> purpose, no (i.e., we'd have to keep the SHA1 code around
>>
>> Yes, it is hard to tell if such a change would have real world impact
>> due to not knowing its actual usage in the field - but I would avoid
>> such a change. The reason for this standard is to have stable addresses
>> across reboots. The standard is widely used but most servers or desktops
>> might get their stable privacy addresses being generated by user space
>> network management systems (NetworkManager/networkd) nowadays. I would
>> guess it could be used in embedded installations.
>>
>> The impact of this change could be annoying though: users could suddenly
>> lose connectivity due to e.g. changes to the default gateway after an
>> upgrade.
>>
>> > I'm not even so sure that's true. That was my worry at first, but
>> > actually, looking at this more closely, DAD means that the address can
>> > be changed anyway - a byte counter is hashed in - so there's no
>> > gurantee there.
>>
>> The duplicate address detection counter is a way to merely provide basic
>> network connectivity in case of duplicate addresses on the network
>> (maybe some kind misconfiguration or L2 attack). Such detected addresses
>> would show up in the kernel log and an administrator should investigate
>> and clean up the situation. Afterwards bringing the interface down and
>> up again should revert the interface to its initial (dad_counter == 0)
>> address.
>>
>> > There's also the other aspect that open coding sha1_transform like
>> > this and prepending it with the secret (rather than a better
>> > construction) isn't so great... Take a look at the latest version of
>> > this in my branch to see a really nice simplification and security
>> > improvement:
>> >
>> > https://git.zx2c4.com/linux-dev/log/?h=remove-sha1
>>
>> All in all, I consider the hash produced here as being part of uAPI
>> unfortunately and thus cannot be changed. It is unfortunate that it
>> can't easily be improved (I assume a separate mode for this is not
>> reasonable). The patches definitely look like a nice cleanup.
>>
>> Would this be the only user of sha_transform left?
>>
>
> The question is not whether but when we can/will change this.
>
> SHA-1 is broken and should be removed at *some* point, so unless the
> feature itself is going to be obsolete, its implementation will need
> to switch to a PRF that fulfils the requirements in RFC7217 once SHA-1
> ceases to do so.
>
> And I should also point out that the current implementation does not
> even use SHA-1 correctly, as it omits the finalization step. This may
> or may not matter in practice, but it deviates from crypto best
> practices, as well as from RFC7217

Right, but that implies we need to work on a transition mechanism. For
newly deployed systems changing the hash is obviously fine, it's the
"reboot and you have a new address" problem.

We could introduce new values to the addr_gen_mode? I.e. values of 4 and
5 would be equivalent to 2 and 3 (respectively), but with the new
hashing algorithm? And then document that 2 and 3 are considered
deprecated to be removed at some point in the future...

-Toke

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Ard Biesheuvel]

On Thu, 13 Jan 2022 at 14:30, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> Ard Biesheuvel <ardb@kernel.org> writes:
>
> > On Thu, 13 Jan 2022 at 12:15, Hannes Frederic Sowa
> > <hannes@stressinduktion.org> wrote:
> >>
> >> Hello,
> >>
> >> On 13.01.22 00:31, Jason A. Donenfeld wrote:
> >> > On 1/13/22, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> >> >> However, if we make this change, systems setting a stable_secret and
> >> >> using addr_gen_mode 2 or 3 will come up with a completely different
> >> >> address after a kernel upgrade. Which would be bad for any operator
> >> >> expecting to be able to find their machine again after a reboot,
> >> >> especially if it is accessed remotely.
> >> >>
> >> >> I haven't ever used this feature myself, though, or seen it in use. So I
> >> >> don't know if this is purely a theoretical concern, or if the
> >> >> stable_address feature is actually used in this way in practice. If it
> >> >> is, I guess the switch would have to be opt-in, which kinda defeats the
> >> >> purpose, no (i.e., we'd have to keep the SHA1 code around
> >>
> >> Yes, it is hard to tell if such a change would have real world impact
> >> due to not knowing its actual usage in the field - but I would avoid
> >> such a change. The reason for this standard is to have stable addresses
> >> across reboots. The standard is widely used but most servers or desktops
> >> might get their stable privacy addresses being generated by user space
> >> network management systems (NetworkManager/networkd) nowadays. I would
> >> guess it could be used in embedded installations.
> >>
> >> The impact of this change could be annoying though: users could suddenly
> >> lose connectivity due to e.g. changes to the default gateway after an
> >> upgrade.
> >>
> >> > I'm not even so sure that's true. That was my worry at first, but
> >> > actually, looking at this more closely, DAD means that the address can
> >> > be changed anyway - a byte counter is hashed in - so there's no
> >> > gurantee there.
> >>
> >> The duplicate address detection counter is a way to merely provide basic
> >> network connectivity in case of duplicate addresses on the network
> >> (maybe some kind misconfiguration or L2 attack). Such detected addresses
> >> would show up in the kernel log and an administrator should investigate
> >> and clean up the situation. Afterwards bringing the interface down and
> >> up again should revert the interface to its initial (dad_counter == 0)
> >> address.
> >>
> >> > There's also the other aspect that open coding sha1_transform like
> >> > this and prepending it with the secret (rather than a better
> >> > construction) isn't so great... Take a look at the latest version of
> >> > this in my branch to see a really nice simplification and security
> >> > improvement:
> >> >
> >> > https://git.zx2c4.com/linux-dev/log/?h=remove-sha1
> >>
> >> All in all, I consider the hash produced here as being part of uAPI
> >> unfortunately and thus cannot be changed. It is unfortunate that it
> >> can't easily be improved (I assume a separate mode for this is not
> >> reasonable). The patches definitely look like a nice cleanup.
> >>
> >> Would this be the only user of sha_transform left?
> >>
> >
> > The question is not whether but when we can/will change this.
> >
> > SHA-1 is broken and should be removed at *some* point, so unless the
> > feature itself is going to be obsolete, its implementation will need
> > to switch to a PRF that fulfils the requirements in RFC7217 once SHA-1
> > ceases to do so.
> >
> > And I should also point out that the current implementation does not
> > even use SHA-1 correctly, as it omits the finalization step. This may
> > or may not matter in practice, but it deviates from crypto best
> > practices, as well as from RFC7217
>
> Right, but that implies we need to work on a transition mechanism. For
> newly deployed systems changing the hash is obviously fine, it's the
> "reboot and you have a new address" problem.
>
> We could introduce new values to the addr_gen_mode? I.e. values of 4 and
> 5 would be equivalent to 2 and 3 (respectively), but with the new
> hashing algorithm? And then document that 2 and 3 are considered
> deprecated to be removed at some point in the future...
>

I guess that for the time being, we could use assignments of
stable_secret by user space as a hint that we should switch to the old
scheme. We'd also need a knob to opt into the new scheme in that case,
and maybe print a warning otherwise? That would at least give us a
path forward where we can rip it out /some/ point in the future.

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Jason A. Donenfeld]

Hi Toke,

On Thu, Jan 13, 2022 at 2:30 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> Right, but that implies we need to work on a transition mechanism. For
> newly deployed systems changing the hash is obviously fine, it's the
> "reboot and you have a new address" problem.
>
> We could introduce new values to the addr_gen_mode? I.e. values of 4 and
> 5 would be equivalent to 2 and 3 (respectively), but with the new
> hashing algorithm? And then document that 2 and 3 are considered
> deprecated to be removed at some point in the future...

Right, so this is exactly the flow of conversation I anticipated.
"Let's change it!" "No, we can't." "Okay, let's add a knob."

The knob I was thinking about, though, was actually a compile-time one
CONFIG_NET_OBSOLETE_INSECURE_ADDRCONF_HASH, which itself is a `depends
on CONFIG_OLD_N_CRUSTY` or something. This way we could gate the
inclusion of sha1.c/sha1.o on that at compile time, and shave down
vmlinux a bit, which would make Geert happy.

Then, at some point down the road, we can talk about removing
CONFIG_NET_OBSOLETE_INSECURE_ADDRCONF_HASH too.

Jason

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Ard Biesheuvel]

On Thu, 13 Jan 2022 at 14:46, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> Hi Toke,
>
> On Thu, Jan 13, 2022 at 2:30 PM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> > Right, but that implies we need to work on a transition mechanism. For
> > newly deployed systems changing the hash is obviously fine, it's the
> > "reboot and you have a new address" problem.
> >
> > We could introduce new values to the addr_gen_mode? I.e. values of 4 and
> > 5 would be equivalent to 2 and 3 (respectively), but with the new
> > hashing algorithm? And then document that 2 and 3 are considered
> > deprecated to be removed at some point in the future...
>
> Right, so this is exactly the flow of conversation I anticipated.
> "Let's change it!" "No, we can't." "Okay, let's add a knob."
>
> The knob I was thinking about, though, was actually a compile-time one
> CONFIG_NET_OBSOLETE_INSECURE_ADDRCONF_HASH, which itself is a `depends
> on CONFIG_OLD_N_CRUSTY` or something. This way we could gate the
> inclusion of sha1.c/sha1.o on that at compile time, and shave down
> vmlinux a bit, which would make Geert happy.
>
> Then, at some point down the road, we can talk about removing
> CONFIG_NET_OBSOLETE_INSECURE_ADDRCONF_HASH too.
>

What is the point of having CONFIG_OLD_N_CRUSTY if all distros are
going to enable it indefinitely?

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Jason A. Donenfeld]

On Thu, Jan 13, 2022 at 2:50 PM Ard Biesheuvel <ardb@kernel.org> wrote:
> > Then, at some point down the road, we can talk about removing
> > CONFIG_NET_OBSOLETE_INSECURE_ADDRCONF_HASH too.
> >
>
> What is the point of having CONFIG_OLD_N_CRUSTY if all distros are
> going to enable it indefinitely?

I think there's probably some combination of
CONFIG_NET_OBSOLETE_INSECURE_ADDRCONF_HASH and CONFIG_OLD_N_CRUSTY and
maybe even a CONFIG_GOD_MURDERS_KITTENS that might be sufficiently
disincentivizing? Or this ties into other general ideas on a gradual
obsolescence->removal flow for things.

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Toke Høiland-Jørgensen]

"Jason A. Donenfeld" <Jason@zx2c4.com> writes:

> On Thu, Jan 13, 2022 at 2:50 PM Ard Biesheuvel <ardb@kernel.org> wrote:
>> > Then, at some point down the road, we can talk about removing
>> > CONFIG_NET_OBSOLETE_INSECURE_ADDRCONF_HASH too.
>> >
>>
>> What is the point of having CONFIG_OLD_N_CRUSTY if all distros are
>> going to enable it indefinitely?
>
> I think there's probably some combination of
> CONFIG_NET_OBSOLETE_INSECURE_ADDRCONF_HASH and CONFIG_OLD_N_CRUSTY and
> maybe even a CONFIG_GOD_MURDERS_KITTENS that might be sufficiently
> disincentivizing? Or this ties into other general ideas on a gradual
> obsolescence->removal flow for things.

Making it a compile-time switch doesn't really solve anything, though.
It'll need to be a runtime switch for people to be able to opt-in to the
new behaviour; otherwise there would still be a flag day when
distributions switch on the new config option.

I don't think there's any reason to offload this decision on
distributions either: there's clearly a "best option" here, absent any
backwards compatibility concerns. So it's on us to design a proper
transition mechanism. Defaulting to SHA1 when stable_secret is set, as
Ard suggested, sounds like a reasonable default; then we only need a
single new value for addr_gen_mode to opt-in to using blake2s even when
setting the stable_secret.

-Toke

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Jason A. Donenfeld]

Hi Hannes,

On Thu, Jan 13, 2022 at 12:15 PM Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> > I'm not even so sure that's true. That was my worry at first, but
> > actually, looking at this more closely, DAD means that the address can
> > be changed anyway - a byte counter is hashed in - so there's no
> > guarantee there.
>
> The duplicate address detection counter is a way to merely provide basic
> network connectivity in case of duplicate addresses on the network
> (maybe some kind misconfiguration or L2 attack). Such detected addresses
> would show up in the kernel log and an administrator should investigate
> and clean up the situation.

I don't mean to belabor a point where I'm likely wrong anyway, but
this DAD business has kept me thinking...

Attacker is hanging out on the network sending DAD responses, forcing
those counters to increment, and thus making SHA1(stuff || counter)
result in a different IPv6 address than usual. Outcomes:
1) The administrator cannot handle this, did not understand the
semantics of this address generation feature, and will now have a
broken network;
2) The administrator knows what he's doing, and will be able to handle
a different IPv6 address coming up.

Do we really care about case (1)? That sounds like emacs spacebar
heating https://xkcd.com/1172/. And case (2) seems like something that
would tolerate us changing the hash function.

> Afterwards bringing the interface down and
> up again should revert the interface to its initial (dad_counter == 0)
> address.

Except the attacker is still on the network, and the administrator
can't figure it out because the mac addresses keep changing and it's
arriving from seemingly random switches! Plot twist: the attack is
being conducted from an implant in the switch firmware. There are a
lot of creative different takes on the same basic scenario. The point
is - the administrator really _can't_ rely on the address always being
the same, because it's simply out of his control.

Given that the admin already *must* be prepared for the address to
change, doesn't that give us some leeway to change the algorithm used
between kernels?

Or to put it differently, are there _actually_ braindead deployments
out there that truly rely on the address never ever changing, and
should we be going out of our way to support what is arguably a
misreading and misdeployment of the feature?

(Feel free to smack this line of argumentation down if you disagree. I
just thought it should be a bit more thoroughly explored.)

Jason

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Toke Høiland-Jørgensen]

"Jason A. Donenfeld" <Jason@zx2c4.com> writes:

> Hi Hannes,
>
> On Thu, Jan 13, 2022 at 12:15 PM Hannes Frederic Sowa
> <hannes@stressinduktion.org> wrote:
>> > I'm not even so sure that's true. That was my worry at first, but
>> > actually, looking at this more closely, DAD means that the address can
>> > be changed anyway - a byte counter is hashed in - so there's no
>> > guarantee there.
>>
>> The duplicate address detection counter is a way to merely provide basic
>> network connectivity in case of duplicate addresses on the network
>> (maybe some kind misconfiguration or L2 attack). Such detected addresses
>> would show up in the kernel log and an administrator should investigate
>> and clean up the situation.
>
> I don't mean to belabor a point where I'm likely wrong anyway, but
> this DAD business has kept me thinking...
>
> Attacker is hanging out on the network sending DAD responses, forcing
> those counters to increment, and thus making SHA1(stuff || counter)
> result in a different IPv6 address than usual. Outcomes:
> 1) The administrator cannot handle this, did not understand the
> semantics of this address generation feature, and will now have a
> broken network;
> 2) The administrator knows what he's doing, and will be able to handle
> a different IPv6 address coming up.
>
> Do we really care about case (1)? That sounds like emacs spacebar
> heating https://xkcd.com/1172/. And case (2) seems like something that
> would tolerate us changing the hash function.

Privacy addresses mostly address identification outside of the local
network (because on the local network you can see the MAC address), so I
don't think it's unreasonable for someone to enable this and not have a
procedure in place to deal with DAD causing the address to change. For
instance, they could manage their network in a way that they won't
happen (or just turn off DAD entirely on the affected boxes).

>> Afterwards bringing the interface down and
>> up again should revert the interface to its initial (dad_counter == 0)
>> address.
>
> Except the attacker is still on the network, and the administrator
> can't figure it out because the mac addresses keep changing and it's
> arriving from seemingly random switches! Plot twist: the attack is
> being conducted from an implant in the switch firmware. There are a
> lot of creative different takes on the same basic scenario. The point
> is - the administrator really _can't_ rely on the address always being
> the same, because it's simply out of his control.
>
> Given that the admin already *must* be prepared for the address to
> change, doesn't that give us some leeway to change the algorithm used
> between kernels?
>
> Or to put it differently, are there _actually_ braindead deployments
> out there that truly rely on the address never ever changing, and
> should we be going out of our way to support what is arguably a
> misreading and misdeployment of the feature?
>
> (Feel free to smack this line of argumentation down if you disagree. I
> just thought it should be a bit more thoroughly explored.)

I kinda get where you're coming from, but most systems are not actively
under attack, and those will still "break" if this is just changed.
Which is one of those "a kernel upgrade broke my system" type of events
that we want to avoid because it makes people vary of upgrading, so
they'll keep running old kernels way past their expiry dates.

-Toke

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Hannes Frederic Sowa]

Hello,

On Fri, Jan 14, 2022, at 17:07, Jason A. Donenfeld wrote:
> On Thu, Jan 13, 2022 at 12:15 PM Hannes Frederic Sowa
> <hannes@stressinduktion.org> wrote:
>> > I'm not even so sure that's true. That was my worry at first, but
>> > actually, looking at this more closely, DAD means that the address can
>> > be changed anyway - a byte counter is hashed in - so there's no
>> > guarantee there.
>>
>> The duplicate address detection counter is a way to merely provide basic
>> network connectivity in case of duplicate addresses on the network
>> (maybe some kind misconfiguration or L2 attack). Such detected addresses
>> would show up in the kernel log and an administrator should investigate
>> and clean up the situation.
>
> I don't mean to belabor a point where I'm likely wrong anyway, but
> this DAD business has kept me thinking...
>
> Attacker is hanging out on the network sending DAD responses, forcing
> those counters to increment, and thus making SHA1(stuff || counter)
> result in a different IPv6 address than usual. Outcomes:
> 1) The administrator cannot handle this, did not understand the
> semantics of this address generation feature, and will now have a
> broken network;
> 2) The administrator knows what he's doing, and will be able to handle
> a different IPv6 address coming up.
>
> Do we really care about case (1)? That sounds like emacs spacebar
> heating https://xkcd.com/1172/. And case (2) seems like something that
> would tolerate us changing the hash function.

Taking a step back, there is the base case where we don't have duplicate
addresses on the network nor an attack is on-going. We would break those
setups with that patch. And those are the ones that matter most. In
particular those stable-random addresses are being used in router
advertisements for announcing the next-hop/default gateway on the
broadcast domain. During my time in IPv6 land I have seen lots of setups
where those automatic advertisements got converted into static
configuration for the sake of getting hands on a cool looking IPv6
address on another host (I did that as well ;) ). In particular, in the
last example, you might not only have one administrator at hand to
handle the issue, but probably multiple roles are involved (host admin
and network admin maybe from different organizations - how annoying -
but that's a worst case scenario).

Furthermore most L2 attacks nowadays are stopped by smarter switches or
wifi access points(?) anyway with per-port MAC learning and other
hardening features. Obviously this only happens in more managed
environments but probably already also at smaller home networks
nowadays. Datacenters probably already limit access to the Layer 2 raw
network in such a way that this attack is probably not possible either.
Same for IoT stuff where you probably have a point-to-point IPv6
connection anyway.

The worst case scenario is someone upgrading their kernel during a
trip away from home, rebooting, and losing access to their system. If we
experience just one of those cases we have violated Linux strict uAPI
rules (in my opinion). Thus, yes, we care about both, (1) and (2) cases.

I don't think we can argue our way out of this by stating that there are
no guarantees anyway, as much as I would like to change the hash
function as well.

As much as I know about the problems with SHA1 and would like to see it
removed from the kernel as well, I fear that in this case it seems hard
to do. I would propose putting sha1 into a compilation unit and
overwrite the compiler flags to optimize the function optimized for size
and maybe add another mode or knob to switch the hashing algorithm if
necessary.

>> Afterwards bringing the interface down and
>> up again should revert the interface to its initial (dad_counter == 0)
>> address.
>
> Except the attacker is still on the network, and the administrator
> can't figure it out because the mac addresses keep changing and it's
> arriving from seemingly random switches! Plot twist: the attack is
> being conducted from an implant in the switch firmware. There are a
> lot of creative different takes on the same basic scenario. The point
> is - the administrator really _can't_ rely on the address always being
> the same, because it's simply out of his control.

This is a very pessimistic scenario bordering a nightmare. I hope the
new hashing algorithm will protect them. ;)

> Given that the admin already *must* be prepared for the address to
> change, doesn't that give us some leeway to change the algorithm used
> between kernels?
>
> Or to put it differently, are there _actually_ braindead deployments
> out there that truly rely on the address never ever changing, and
> should we be going out of our way to support what is arguably a
> misreading and misdeployment of the feature?

Given the example above, users might hardcode this generated IP address
as a default gateway in their configs on other hosts. This is actually a
very common thing to do.

> (Feel free to smack this line of argumentation down if you disagree. I
> just thought it should be a bit more thoroughly explored.)

I haven't investigated recent research into breakage of SHA1, I mostly
remember the chosen-image and collision attacks against it. Given the
particular usage of SHA1 in this case, do you think switching the
hashing function increases security? I am asking because of the desire
to decrease the instruction size of the kernel, but adding a switch
will actually increase the size in the foreseeable future (and I agree
with Toke that offloading this decision to distributions is probably
not fair).

Maybe at some point the networking subsystem will adapt a generic knob
like LD_ASSUME_KERNEL? ;)

Bye,
Hannes

Re: [PATCH RFC v1 2/3] ipv6: move from sha1 to blake2s in address calculation

[Jason A. Donenfeld]

Hi Hannes,

On Fri, Jan 14, 2022 at 6:44 PM Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> I don't think we can argue our way out of this by stating that there are
> no guarantees anyway, as much as I would like to change the hash
> function as well.

Shucks. Alright then.

> As much as I know about the problems with SHA1 and would like to see it
> removed from the kernel as well, I fear that in this case it seems hard
> to do. I would propose putting sha1 into a compilation unit and
> overwrite the compiler flags to optimize the function optimized for size
> and maybe add another mode or knob to switch the hashing algorithm if
> necessary.

Already on it! :)
https://lore.kernel.org/linux-crypto/20220114154247.99773-3-Jason@zx2c4.com/

> I haven't investigated recent research into breakage of SHA1, I mostly
> remember the chosen-image and collision attacks against it. Given the
> particular usage of SHA1 in this case, do you think switching the
> hashing function increases security?

Considering we're only using 64-bits of SHA-1 output, I don't think
the SHA-1 collision attacks give you that much here. And it seems like
there are other network-level security concerns with the whole scheme
anyway. So it might not be the largest of matters. However...

> I am asking because of the desire
> to decrease the instruction size of the kernel

Indeed this is what I was hoping for.

Jason

[PATCH RFC v1 3/3] crypto: sha1_generic - import lib/sha1.c locally

[Jason A. Donenfeld]

With no non-crypto API users of this function, we can move it into the
generic crypto/ code where it belongs.

Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: Ard Biesheuvel <ardb@kernel.org>
Cc: linux-crypto@vger.kernel.org
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 crypto/sha1_generic.c | 114 +++++++++++++++++++++++++++++++++++
 include/crypto/sha1.h |  10 ---
 lib/Makefile          |   2 +-
 lib/sha1.c            | 137 ------------------------------------------
 4 files changed, 115 insertions(+), 148 deletions(-)
 delete mode 100644 lib/sha1.c

diff --git a/crypto/sha1_generic.c b/crypto/sha1_generic.c
index 325b57fe28dc..a2b019803561 100644
--- a/crypto/sha1_generic.c
+++ b/crypto/sha1_generic.c
@@ -16,9 +16,123 @@
 #include <linux/module.h>
 #include <linux/mm.h>
 #include <linux/types.h>
+#include <linux/bitops.h>
+#include <linux/string.h>
 #include <crypto/sha1.h>
 #include <crypto/sha1_base.h>
 #include <asm/byteorder.h>
+#include <asm/unaligned.h>
+
+#define SHA1_DIGEST_WORDS	(SHA1_DIGEST_SIZE / 4)
+#define SHA1_WORKSPACE_WORDS	16
+
+/*
+ * If you have 32 registers or more, the compiler can (and should)
+ * try to change the array[] accesses into registers. However, on
+ * machines with less than ~25 registers, that won't really work,
+ * and at least gcc will make an unholy mess of it.
+ *
+ * So to avoid that mess which just slows things down, we force
+ * the stores to memory to actually happen (we might be better off
+ * with a 'W(t)=(val);asm("":"+m" (W(t))' there instead, as
+ * suggested by Artur Skawina - that will also make gcc unable to
+ * try to do the silly "optimize away loads" part because it won't
+ * see what the value will be).
+ *
+ * Ben Herrenschmidt reports that on PPC, the C version comes close
+ * to the optimized asm with this (ie on PPC you don't want that
+ * 'volatile', since there are lots of registers).
+ *
+ * On ARM we get the best code generation by forcing a full memory barrier
+ * between each SHA_ROUND, otherwise gcc happily get wild with spilling and
+ * the stack frame size simply explode and performance goes down the drain.
+ */
+
+#ifdef CONFIG_X86
+  #define setW(x, val) (*(volatile __u32 *)&W(x) = (val))
+#elif defined(CONFIG_ARM)
+  #define setW(x, val) do { W(x) = (val); __asm__("":::"memory"); } while (0)
+#else
+  #define setW(x, val) (W(x) = (val))
+#endif
+
+/* This "rolls" over the 512-bit array */
+#define W(x) (array[(x)&15])
+
+/*
+ * Where do we get the source from? The first 16 iterations get it from
+ * the input data, the next mix it from the 512-bit array.
+ */
+#define SHA_SRC(t) get_unaligned_be32((__u32 *)data + t)
+#define SHA_MIX(t) rol32(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)
+
+#define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \
+	__u32 TEMP = input(t); setW(t, TEMP); \
+	E += TEMP + rol32(A,5) + (fn) + (constant); \
+	B = ror32(B, 2); \
+	TEMP = E; E = D; D = C; C = B; B = A; A = TEMP; } while (0)
+
+#define T_0_15(t, A, B, C, D, E)  SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
+#define T_16_19(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
+#define T_20_39(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0x6ed9eba1, A, B, C, D, E )
+#define T_40_59(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, ((B&C)+(D&(B^C))) , 0x8f1bbcdc, A, B, C, D, E )
+#define T_60_79(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) ,  0xca62c1d6, A, B, C, D, E )
+
+/**
+ * sha1_transform - single block SHA1 transform (deprecated)
+ *
+ * @digest: 160 bit digest to update
+ * @data:   512 bits of data to hash
+ * @array:  16 words of workspace (see note)
+ *
+ * This function executes SHA-1's internal compression function.  It updates the
+ * 160-bit internal state (@digest) with a single 512-bit data block (@data).
+ *
+ * Don't use this function.  SHA-1 is no longer considered secure.  And even if
+ * you do have to use SHA-1, this isn't the correct way to hash something with
+ * SHA-1 as this doesn't handle padding and finalization.
+ *
+ * Note: If the hash is security sensitive, the caller should be sure
+ * to clear the workspace. This is left to the caller to avoid
+ * unnecessary clears between chained hashing operations.
+ */
+static void sha1_transform(__u32 *digest, const char *data, __u32 *array)
+{
+	__u32 A, B, C, D, E;
+	unsigned int i = 0;
+
+	A = digest[0];
+	B = digest[1];
+	C = digest[2];
+	D = digest[3];
+	E = digest[4];
+
+	/* Round 1 - iterations 0-16 take their input from 'data' */
+	for (; i < 16; ++i)
+		T_0_15(i, A, B, C, D, E);
+
+	/* Round 1 - tail. Input from 512-bit mixing array */
+	for (; i < 20; ++i)
+		T_16_19(i, A, B, C, D, E);
+
+	/* Round 2 */
+	for (; i < 40; ++i)
+		T_20_39(i, A, B, C, D, E);
+
+	/* Round 3 */
+	for (; i < 60; ++i)
+		T_40_59(i, A, B, C, D, E);
+
+	/* Round 4 */
+	for (; i < 80; ++i)
+		T_60_79(i, A, B, C, D, E);
+
+	digest[0] += A;
+	digest[1] += B;
+	digest[2] += C;
+	digest[3] += D;
+	digest[4] += E;
+}
 
 const u8 sha1_zero_message_hash[SHA1_DIGEST_SIZE] = {
 	0xda, 0x39, 0xa3, 0xee, 0x5e, 0x6b, 0x4b, 0x0d,
diff --git a/include/crypto/sha1.h b/include/crypto/sha1.h
index 044ecea60ac8..118a3cad5eb3 100644
--- a/include/crypto/sha1.h
+++ b/include/crypto/sha1.h
@@ -33,14 +33,4 @@ extern int crypto_sha1_update(struct shash_desc *desc, const u8 *data,
 extern int crypto_sha1_finup(struct shash_desc *desc, const u8 *data,
 			     unsigned int len, u8 *hash);
 
-/*
- * An implementation of SHA-1's compression function.  Don't use in new code!
- * You shouldn't be using SHA-1, and even if you *have* to use SHA-1, this isn't
- * the correct way to hash something with SHA-1 (use crypto_shash instead).
- */
-#define SHA1_DIGEST_WORDS	(SHA1_DIGEST_SIZE / 4)
-#define SHA1_WORKSPACE_WORDS	16
-void sha1_init(__u32 *buf);
-void sha1_transform(__u32 *digest, const char *data, __u32 *W);
-
 #endif /* _CRYPTO_SHA1_H */
diff --git a/lib/Makefile b/lib/Makefile
index 364c23f15578..83ac3f0c1fbe 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -29,7 +29,7 @@ endif
 
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o timerqueue.o xarray.o \
-	 idr.o extable.o sha1.o irq_regs.o argv_split.o \
+	 idr.o extable.o irq_regs.o argv_split.o \
 	 flex_proportions.o ratelimit.o show_mem.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
diff --git a/lib/sha1.c b/lib/sha1.c
deleted file mode 100644
index 0494766fc574..000000000000
--- a/lib/sha1.c
+++ /dev/null
@@ -1,137 +0,0 @@
-// SPDX-License-Identifier: GPL-2.0
-/*
- * SHA1 routine optimized to do word accesses rather than byte accesses,
- * and to avoid unnecessary copies into the context array.
- *
- * This was based on the git SHA1 implementation.
- */
-
-#include <linux/kernel.h>
-#include <linux/export.h>
-#include <linux/bitops.h>
-#include <linux/string.h>
-#include <crypto/sha1.h>
-#include <asm/unaligned.h>
-
-/*
- * If you have 32 registers or more, the compiler can (and should)
- * try to change the array[] accesses into registers. However, on
- * machines with less than ~25 registers, that won't really work,
- * and at least gcc will make an unholy mess of it.
- *
- * So to avoid that mess which just slows things down, we force
- * the stores to memory to actually happen (we might be better off
- * with a 'W(t)=(val);asm("":"+m" (W(t))' there instead, as
- * suggested by Artur Skawina - that will also make gcc unable to
- * try to do the silly "optimize away loads" part because it won't
- * see what the value will be).
- *
- * Ben Herrenschmidt reports that on PPC, the C version comes close
- * to the optimized asm with this (ie on PPC you don't want that
- * 'volatile', since there are lots of registers).
- *
- * On ARM we get the best code generation by forcing a full memory barrier
- * between each SHA_ROUND, otherwise gcc happily get wild with spilling and
- * the stack frame size simply explode and performance goes down the drain.
- */
-
-#ifdef CONFIG_X86
-  #define setW(x, val) (*(volatile __u32 *)&W(x) = (val))
-#elif defined(CONFIG_ARM)
-  #define setW(x, val) do { W(x) = (val); __asm__("":::"memory"); } while (0)
-#else
-  #define setW(x, val) (W(x) = (val))
-#endif
-
-/* This "rolls" over the 512-bit array */
-#define W(x) (array[(x)&15])
-
-/*
- * Where do we get the source from? The first 16 iterations get it from
- * the input data, the next mix it from the 512-bit array.
- */
-#define SHA_SRC(t) get_unaligned_be32((__u32 *)data + t)
-#define SHA_MIX(t) rol32(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)
-
-#define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \
-	__u32 TEMP = input(t); setW(t, TEMP); \
-	E += TEMP + rol32(A,5) + (fn) + (constant); \
-	B = ror32(B, 2); \
-	TEMP = E; E = D; D = C; C = B; B = A; A = TEMP; } while (0)
-
-#define T_0_15(t, A, B, C, D, E)  SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
-#define T_16_19(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )
-#define T_20_39(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0x6ed9eba1, A, B, C, D, E )
-#define T_40_59(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, ((B&C)+(D&(B^C))) , 0x8f1bbcdc, A, B, C, D, E )
-#define T_60_79(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) ,  0xca62c1d6, A, B, C, D, E )
-
-/**
- * sha1_transform - single block SHA1 transform (deprecated)
- *
- * @digest: 160 bit digest to update
- * @data:   512 bits of data to hash
- * @array:  16 words of workspace (see note)
- *
- * This function executes SHA-1's internal compression function.  It updates the
- * 160-bit internal state (@digest) with a single 512-bit data block (@data).
- *
- * Don't use this function.  SHA-1 is no longer considered secure.  And even if
- * you do have to use SHA-1, this isn't the correct way to hash something with
- * SHA-1 as this doesn't handle padding and finalization.
- *
- * Note: If the hash is security sensitive, the caller should be sure
- * to clear the workspace. This is left to the caller to avoid
- * unnecessary clears between chained hashing operations.
- */
-void sha1_transform(__u32 *digest, const char *data, __u32 *array)
-{
-	__u32 A, B, C, D, E;
-	unsigned int i = 0;
-
-	A = digest[0];
-	B = digest[1];
-	C = digest[2];
-	D = digest[3];
-	E = digest[4];
-
-	/* Round 1 - iterations 0-16 take their input from 'data' */
-	for (; i < 16; ++i)
-		T_0_15(i, A, B, C, D, E);
-
-	/* Round 1 - tail. Input from 512-bit mixing array */
-	for (; i < 20; ++i)
-		T_16_19(i, A, B, C, D, E);
-
-	/* Round 2 */
-	for (; i < 40; ++i)
-		T_20_39(i, A, B, C, D, E);
-
-	/* Round 3 */
-	for (; i < 60; ++i)
-		T_40_59(i, A, B, C, D, E);
-
-	/* Round 4 */
-	for (; i < 80; ++i)
-		T_60_79(i, A, B, C, D, E);
-
-	digest[0] += A;
-	digest[1] += B;
-	digest[2] += C;
-	digest[3] += D;
-	digest[4] += E;
-}
-EXPORT_SYMBOL(sha1_transform);
-
-/**
- * sha1_init - initialize the vectors for a SHA1 digest
- * @buf: vector to initialize
- */
-void sha1_init(__u32 *buf)
-{
-	buf[0] = 0x67452301;
-	buf[1] = 0xefcdab89;
-	buf[2] = 0x98badcfe;
-	buf[3] = 0x10325476;
-	buf[4] = 0xc3d2e1f0;
-}
-EXPORT_SYMBOL(sha1_init);
-- 
2.34.1

Re: [PATCH RFC v1 0/3] remove remaining users of SHA-1

[David Sterba]

On Wed, Jan 12, 2022 at 02:12:01PM +0100, Jason A. Donenfeld wrote:
> Hi,
> 
> There are currently two remaining users of SHA-1 left in the kernel: bpf
> tag generation, and ipv6 address calculation. In an effort to reduce
> code size and rid ourselves of insecure primitives, this RFC patchset
> moves to using the more secure BLAKE2s function.

What's the rationale to use 2s and not 2b? Everywhere I can find the 2s
version is said to be for 8bit up to 32bit machines and it's worse than
2b in benchmarks (reading https://bench.cr.yp.to/results-hash.html).

I'd understand you go with 2s because you also chose it for wireguard
but I'd like know why 2s again even if it's not made for 64bit
architectures that are preferred nowadays.

Re: [PATCH RFC v1 0/3] remove remaining users of SHA-1

[Jason A. Donenfeld]

On Wed, Jan 12, 2022 at 7:50 PM David Sterba <dsterba@suse.cz> wrote:
>
> On Wed, Jan 12, 2022 at 02:12:01PM +0100, Jason A. Donenfeld wrote:
> > Hi,
> >
> > There are currently two remaining users of SHA-1 left in the kernel: bpf
> > tag generation, and ipv6 address calculation. In an effort to reduce
> > code size and rid ourselves of insecure primitives, this RFC patchset
> > moves to using the more secure BLAKE2s function.
>
> What's the rationale to use 2s and not 2b? Everywhere I can find the 2s
> version is said to be for 8bit up to 32bit machines and it's worse than
> 2b in benchmarks (reading https://bench.cr.yp.to/results-hash.html).
>
> I'd understand you go with 2s because you also chose it for wireguard
> but I'd like know why 2s again even if it's not made for 64bit
> architectures that are preferred nowadays.

Fast for small inputs on all architectures, small code size. And it
performs well on Intel - there are avx512 and ssse3 implementations.
Even blake3 went with the 32-bit choice and abandoned 2b's thing.
Plus, this makes it even more similar to the well trusted chacha
permutation. As far as a general purpose high security library (keyed)
hash function for internal kernel usages, it seems pretty ideal.

Your choice for btrfs though is fine; don't let this patchset change
your thinking on that.

Anyway, I hope that's interesting to you, but I'm not so much
interested in bikeshedding about blake variants as I am in learning
from the net people on the feasibility of getting rid of sha1 in those
two places. So I'd appreciate it if we can keep the discussion focused
on that and not let this veer off into a tangential thread on blakes.

Re: [PATCH RFC v1 0/3] remove remaining users of SHA-1

[Sandy Harris]

Jason A. Donenfeld <Jason@zx2c4.com> wrote:

> There are currently two remaining users of SHA-1 left in the kernel: bpf
> tag generation, and ipv6 address calculation.

I think there are three, since drivers/char/random.c also uses it.
Moreover, there's some inefficiency there (or was last time I
looked) since it produces a 160-bit hash then folds it in half
to give an 80-bit output.

A possible fix would be to use a more modern 512-bit hash.
SHA3 would be the obvious one, but Blake2 would work,
Blake3 might be faster & there are several other possibilities.
Hash context size would then match ChaCha so you could
update the whole CC context at once, maybe even use the
same context for both.

That approach has difficulties, Extracting 512 bits every
time might drain the input pool too quickly & it is overkill
for ChaCha which should be secure with smaller rekeyings.

If you look at IPsec, SSL & other such protocols, many
have now mostly replaced the hash-based HMAC
constructions used in previous generations with things
like Galois field calculations (e.g. AES-GCM) or other
strange math (e,g. poly 1305). These have most of the
desirable properties of hashes & are much faster. As
far as I know, they all give 128-bit outputs.

I think we should replace SHA-1 with GCM. Give
ChaCha 128 bits somewhat more often than current
code gives it 256.

Re: [PATCH RFC v1 0/3] remove remaining users of SHA-1

[Ard Biesheuvel]

On Thu, 13 Jan 2022 at 04:24, Sandy Harris <sandyinchina@gmail.com> wrote:
>
> Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> > There are currently two remaining users of SHA-1 left in the kernel: bpf
> > tag generation, and ipv6 address calculation.
>
> I think there are three, since drivers/char/random.c also uses it.
> Moreover, there's some inefficiency there (or was last time I
> looked) since it produces a 160-bit hash then folds it in half
> to give an 80-bit output.
>

That code was removed, hence the two /remaining/ users.

> A possible fix would be to use a more modern 512-bit hash.
> SHA3 would be the obvious one, but Blake2 would work,
> Blake3 might be faster & there are several other possibilities.
> Hash context size would then match ChaCha so you could
> update the whole CC context at once, maybe even use the
> same context for both.
>
> That approach has difficulties, Extracting 512 bits every
> time might drain the input pool too quickly & it is overkill
> for ChaCha which should be secure with smaller rekeyings.
>
> If you look at IPsec, SSL & other such protocols, many
> have now mostly replaced the hash-based HMAC
> constructions used in previous generations with things
> like Galois field calculations (e.g. AES-GCM) or other
> strange math (e,g. poly 1305). These have most of the
> desirable properties of hashes & are much faster. As
> far as I know, they all give 128-bit outputs.
>
> I think we should replace SHA-1 with GCM. Give
> ChaCha 128 bits somewhat more often than current
> code gives it 256.

You are conflating MACs with hashes. A MAC does is not suitable for
backtrack resistance, and GHASH in particular is really only suited to
be used in the context of GCM.

Re: [PATCH RFC v1 0/3] remove remaining users of SHA-1

[Theodore Ts'o]

On Thu, Jan 13, 2022 at 11:24:10AM +0800, Sandy Harris wrote:
> Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> 
> > There are currently two remaining users of SHA-1 left in the kernel: bpf
> > tag generation, and ipv6 address calculation.
> 
> I think there are three, since drivers/char/random.c also uses it.

This was changed as of commit 9f9eff85a008 ("random: use BLAKE2s
instead of SHA1 in extraction"), which just landed in Linus's tree.

> Moreover, there's some inefficiency there (or was last time I
> looked) since it produces a 160-bit hash then folds it in half
> to give an 80-bit output.

This dates back to very early days of the /dev/random driver, back
when all that was known about SHA-1 was that it was designed by the
NSA using classified design principles, and it had not yet been as
well studied outside of the halls of the NSA.  So folding the SHA-1
hash in half was done deliberately, since at the time, performance was
*not* the primary goal; security was.

(This was also back in the days when encryption algorithms would run
you into export control difficulties, since this is around the times
when the source code of PGP was being published in an OCR font with a
barcode containing the checksum of the content of every single page
was being published by the MIT press, and we were publishing Kerberos
with all of the *calls* to the crypto stripped out and calling it
"Bones" since there were assertions that code that *called*
cryptographic algoriothms might be subject to export control, even if
it didn't have any crypto algorithms in the program themselves.  This
is also why HMAC-based constructions were so popular.  People seem to
forget how much things have changed since the late 1980's....)

       	   	       	    	    	  - Ted