| Message ID | 20220112131204.800307-1-Jason@zx2c4.com |
|---|---|
| Headers | show |
| Series | remove remaining users of SHA-1 | expand |
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.
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.
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.
[ 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
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
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.
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.
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.
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
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.
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.
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
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.
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
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.
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
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?
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.
"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
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
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.
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
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. ]
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. ]
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 :)
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
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)
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
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.
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
"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
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
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
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