linux-kernel - Re: [PATCH v2 1/9] kasan: sw_tags: Use arithmetic shift for shadow computation

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CA+fCnZdjTkreTcoo+J8wMhwDuAFM4g33U5BFy0OPtE0UCvyJbQ@mail.gmail.com>
Date: Thu, 13 Feb 2025 02:21:33 +0100
From: Andrey Konovalov <andreyknvl@...il.com>
To: Maciej Wieczor-Retman <maciej.wieczor-retman@...el.com>
Cc: Samuel Holland <samuel.holland@...ive.com>, Palmer Dabbelt <palmer@...belt.com>, 
	linux-riscv@...ts.infradead.org, Andrey Ryabinin <ryabinin.a.a@...il.com>, 
	Alexander Potapenko <glider@...gle.com>, Dmitry Vyukov <dvyukov@...gle.com>, 
	Vincenzo Frascino <vincenzo.frascino@....com>, kasan-dev@...glegroups.com, 
	llvm@...ts.linux.dev, Catalin Marinas <catalin.marinas@....com>, 
	linux-kernel@...r.kernel.org, linux-mm@...ck.org, 
	Alexandre Ghiti <alexghiti@...osinc.com>, Will Deacon <will@...nel.org>, 
	Evgenii Stepanov <eugenis@...gle.com>, Andrew Morton <akpm@...ux-foundation.org>, 
	linux-arm-kernel@...ts.infradead.org
Subject: Re: [PATCH v2 1/9] kasan: sw_tags: Use arithmetic shift for shadow computation

On Tue, Feb 11, 2025 at 7:07 PM Maciej Wieczor-Retman
<maciej.wieczor-retman@...el.com> wrote:
>
> I did some experiments with multiple addresses passed through
> kasan_mem_to_shadow(). And it seems like we can get almost any address out when
> we consider any random bogus pointers.
>
> I used the KASAN_SHADOW_OFFSET from your example above. Userspace addresses seem
> to map to the range [KASAN_SHADOW_OFFSET - 0xffff8fffffffffff]. Then going
> through non-canonical addresses until 0x0007ffffffffffff we reach the end of
> kernel LA and we loop around. Then the addresses seem to go from 0 until we
> again start reaching the kernel space and then it maps into the proper shadow
> memory.
>
> It gave me the same results when using the previous version of
> kasan_mem_to_shadow() so I'm wondering whether I'm doing this experiment
> incorrectly or if there aren't any addresses we can rule out here?

By the definition of the shadow mapping, if we apply that mapping to
the whole 64-bit address space, the result will only contain 1/8th
(1/16th for SW/HW_TAGS) of that space.

For example, with the current upstream value of KASAN_SHADOW_OFFSET on
x86 and arm64, the value of the top 3 bits (4 for SW/HW_TAGS) of any
shadow address are always the same: KASAN_SHADOW_OFFSET's value is
such that the shadow address calculation never overflows. Addresses
that have a different value for those top 3 bits are the once we can
rule out.

The KASAN_SHADOW_OFFSET value from my example does rely on the
overflow (arguably, this makes things more confusing [1]). But still,
the possible values of shadow addresses should only cover 1/16th of
the address space.

So whether the address belongs to that 1/8th (1/16th) of the address
space is what we want to check in kasan_non_canonical_hook().

The current upstream version of kasan_non_canonical_hook() actually
does a simplified check by only checking for the lower bound (e.g. for
x86, there's also an upper bound: KASAN_SHADOW_OFFSET +
(0xffffffffffffffff >> 3) == 0xfffffbffffffffff), so we could improve
it.

[1] https://bugzilla.kernel.org/show_bug.cgi?id=218043