netdev - Re: [PATCH] bpf: Fix integer overflow involving bucket

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:   Fri, 6 Aug 2021 23:25:32 +0900
From:   Tatsuhiko Yasumatsu <th.yasumatsu@...il.com>
To:     Kees Cook <keescook@...omium.org>
Cc:     Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        Andrii Nakryiko <andrii@...nel.org>,
        Martin KaFai Lau <kafai@...com>,
        Song Liu <songliubraving@...com>, Yonghong Song <yhs@...com>,
        John Fastabend <john.fastabend@...il.com>,
        KP Singh <kpsingh@...nel.org>, netdev@...r.kernel.org,
        bpf@...r.kernel.org
Subject: Re: [PATCH] bpf: Fix integer overflow involving bucket_size

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@...il.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
Thank you for pointing out.
I'll modify the patch.

Regards,
Tatsuhiko Yasumatsu