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
On Fri, 14 Jan 2022 at 15:12, Jason A. Donenfeld <[email protected]> wrote:
>
> 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.
>
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. ]
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, 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 <[email protected]> wrote:
> "checksum" -- the thing is only 64-bits, and as you told Andy Polyakov
Whoops, meant Lutomirski here. x86 Andy, not crypto Andy :)
On Fri, Jan 14, 2022 at 7:08 AM Ard Biesheuvel <[email protected]> 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.
On Fri, Jan 14, 2022 at 5:19 PM Alexei Starovoitov
<[email protected]> wrote:
>
> On Fri, Jan 14, 2022 at 7:08 AM Ard Biesheuvel <[email protected]> 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/[email protected]/
Meanwhile, you have not replied to any of the substantive issues I
brought up. I'd appreciate you doing so.
Thank you,
Jason