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

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