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
