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 <[email protected]>
Cc: Herbert Xu <[email protected]>
Cc: Ard Biesheuvel <[email protected]>
Cc: Jean-Philippe Aumasson <[email protected]>
Cc: [email protected]
Signed-off-by: Jason A. Donenfeld <[email protected]>
---
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
[ 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" <[email protected]> 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 <[email protected]>
> Cc: Herbert Xu <[email protected]>
> Cc: Ard Biesheuvel <[email protected]>
> Cc: Jean-Philippe Aumasson <[email protected]>
> Cc: [email protected]
> Signed-off-by: Jason A. Donenfeld <[email protected]>
> ---
> 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
On Wed, Jan 12, 2022 at 5:14 PM Toke Høiland-Jørgensen <[email protected]> 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" <[email protected]> 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.
Hi Alexei,
On 1/13/22, Alexei Starovoitov <[email protected]> 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
On Thu, Jan 13, 2022 at 4:27 AM Jason A. Donenfeld <[email protected]> wrote:
>
> Hi Alexei,
>
> On 1/13/22, Alexei Starovoitov <[email protected]> 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.
Hi Alexei,
On Thu, Jan 13, 2022 at 11:45 PM Alexei Starovoitov
<[email protected]> wrote:
> On Thu, Jan 13, 2022 at 4:27 AM Jason A. Donenfeld <[email protected]> wrote:
> > On 1/13/22, Alexei Starovoitov <[email protected]> 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 -- [email protected]
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
Hi Alexei,
On Thu, Jan 13, 2022 at 11:45 PM Alexei Starovoitov
<[email protected]> wrote:
> On Thu, Jan 13, 2022 at 4:27 AM Jason A. Donenfeld <[email protected]> wrote:
> >
> > Hi Alexei,
> >
> > On 1/13/22, Alexei Starovoitov <[email protected]> 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. ]
Hi Jason,
On Fri, Jan 14, 2022 at 4:20 PM Jason A. Donenfeld <[email protected]> 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 -- [email protected]
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
From: Jason A. Donenfeld
> Sent: 14 January 2022 15:21
>
> On Fri, Jan 14, 2022 at 4:08 PM Ard Biesheuvel <[email protected]> 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)
On Wed, Jan 12, 2022 at 8:13 PM Toke Høiland-Jørgensen <[email protected]> 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" <[email protected]> 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