On Thu, Aug 05, 2021 at 07:26:49AM -0700, Kees Cook wrote:
> On Thu, Aug 05, 2021 at 11:05:15PM +0900, Tatsuhiko Yasumatsu wrote:
> > In __htab_map_lookup_and_delete_batch(), hash buckets are iterated over
> > to count the number of elements in each bucket (bucket_size).
> > If bucket_size is large enough, the multiplication to calculate
> > kvmalloc() size could overflow, resulting in out-of-bounds write
> > as reported by KASAN.
> >
> > [...]
> > [ 104.986052] BUG: KASAN: vmalloc-out-of-bounds in __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [ 104.986489] Write of size 4194224 at addr ffffc9010503be70 by task crash/112
> > [ 104.986889]
> > [ 104.987193] CPU: 0 PID: 112 Comm: crash Not tainted 5.14.0-rc4 #13
> > [ 104.987552] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1ubuntu1.1 04/01/2014
> > [ 104.988104] Call Trace:
> > [ 104.988410] dump_stack_lvl+0x34/0x44
> > [ 104.988706] print_address_description.constprop.0+0x21/0x140
> > [ 104.988991] ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [ 104.989327] ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [ 104.989622] kasan_report.cold+0x7f/0x11b
> > [ 104.989881] ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [ 104.990239] kasan_check_range+0x17c/0x1e0
> > [ 104.990467] memcpy+0x39/0x60
> > [ 104.990670] __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [ 104.990982] ? __wake_up_common+0x4d/0x230
> > [ 104.991256] ? htab_of_map_free+0x130/0x130
> > [ 104.991541] bpf_map_do_batch+0x1fb/0x220
> > [...]
> >
> > In hashtable, if the elements' keys have the same jhash() value, the
> > elements will be put into the same bucket. By putting a lot of elements
> > into a single bucket, the value of bucket_size can be increased to
> > trigger the integer overflow.
> >
> > Triggering the overflow is possible for both callers with CAP_SYS_ADMIN
> > and callers without CAP_SYS_ADMIN.
> >
> > It will be trivial for a caller with CAP_SYS_ADMIN to intentionally
> > reach this overflow by enabling BPF_F_ZERO_SEED. As this flag will set
> > the random seed passed to jhash() to 0, it will be easy for the caller
> > to prepare keys which will be hashed into the same value, and thus put
> > all the elements into the same bucket.
> >
> > If the caller does not have CAP_SYS_ADMIN, BPF_F_ZERO_SEED cannot be
> > used. However, it will be still technically possible to trigger the
> > overflow, by guessing the random seed value passed to jhash() (32bit)
> > and repeating the attempt to trigger the overflow. In this case,
> > the probability to trigger the overflow will be low and will take
> > a very long time.
> >
> > Fix the integer overflow by casting 1 operand to u64.
> >
> > Fixes: 057996380a42 ("bpf: Add batch ops to all htab bpf map")
> > Signed-off-by: Tatsuhiko Yasumatsu <th.yasumatsu@xxxxxxxxx>
> > ---
> > kernel/bpf/hashtab.c | 4 ++--
> > 1 file changed, 2 insertions(+), 2 deletions(-)
> >
> > diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> > index 72c58cc516a3..e29283c3b17f 100644
> > --- a/kernel/bpf/hashtab.c
> > +++ b/kernel/bpf/hashtab.c
> > @@ -1565,8 +1565,8 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
> > /* We cannot do copy_from_user or copy_to_user inside
> > * the rcu_read_lock. Allocate enough space here.
> > */
> > - keys = kvmalloc(key_size * bucket_size, GFP_USER | __GFP_NOWARN);
> > - values = kvmalloc(value_size * bucket_size, GFP_USER | __GFP_NOWARN);
> > + keys = kvmalloc((u64)key_size * bucket_size, GFP_USER | __GFP_NOWARN);
> > + values = kvmalloc((u64)value_size * bucket_size, GFP_USER | __GFP_NOWARN);
>
> Please, no open-coded multiplication[1]. This should use kvmalloc_array()
> instead.
>
> -Kees
>
> [1] https://www.kernel.org/doc/html/latest/process/deprecated.html#open-coded-arithmetic-in-allocator-arguments
>
> > if (!keys || !values) {
> > ret = -ENOMEM;
> > goto after_loop;
> > --
> > 2.25.1
> >
>
> --
> Kees Cook
Thank you for pointing out.
I'll modify the patch.
Regards,
Tatsuhiko Yasumatsu
