Re: [PATCH] bpf: Fix integer overflow involving bucket_size

[Kees Cook <keescook@chromium.org>]

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@gmail.com>
> ---
>  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