[PATCH 0/3] add %pX specifier

[PATCH 0/3] add %pX specifier

[Tobin C. Harding]

This series is a result of the recent thread on LKML regarding kpt_restrict

https://lkml.org/lkml/2017/9/30/224

It seems we have not reached total consensus. This patch set does not claim to solve the whole issue
but rather take a small step forward without taking any steps backwards.

It may be that, since this issue is security related, there is no total solution only trade offs?

I am quite new to kernel development, which implies, neither am I a kernel security expert. In order
that my understanding of the issue is explicit I am listing here the things we all seem to agree on.

1. We are leaking addresses.

2. There are _some_ use cases for printing addresses.

3. Printing kernel pointers with %p and %x is bad.

4. We could reduce the number of leaked addresses if we had a mechanism to print unique identifiers.

If I am badly mistaken please feel free to yell at me, here to learn, happy to be corrected.

This patch set solves point 4 (above) by adding a printk specifier %pX to print a unique identifier
(hash) based on a pointer. This was suggested by Linus (in the above thread) as; 

  +        hashval = hash_three_words(
  +                (unsigned long)ptr,
  +                (unsigned long)ptr >> 16 >> 16,
  +                boot_time_random_int);


I did not understand the code (specifically why the right shift of 16 twice?). I therefore chose to
use an algorithm from kernel/kcmp.h for creating the hash (suggested by Tycho Anderson).

This patch is a softer version of Linus' suggestion because it does not change the behaviour of the
%p specifier. I don't see the benefit in making such a breaking change without addressing the issue
of %x (and I don't the balls to right now).

Patch 2 and 3 of the series give an example usage of the new specifier.

Thanks for taking the time to read this. All criticism and advice willingly accepted. 

thanks,
Tobin.


Tobin C. Harding (3):
  lib/vsprintf: add 'X' specifier to hash pointers
  KVM: use %pX to print token identifier
  vfio_pci: use %pX to print token identifier

 Documentation/printk-formats.txt  |  9 +++++++++
 drivers/vfio/pci/vfio_pci_intrs.c |  2 +-
 include/linux/printk.h            | 17 +++++++++++++++++
 lib/vsprintf.c                    | 33 +++++++++++++++++++++++++++++++++
 scripts/checkpatch.pl             |  2 +-
 virt/kvm/eventfd.c                |  2 +-
 6 files changed, 62 insertions(+), 3 deletions(-)

-- 
2.7.4

Re: [PATCH 0/3] add %pX specifier

[Linus Torvalds]

On Tue, Oct 10, 2017 at 4:09 PM, Tobin C. Harding <me@tobin.cc> wrote:
>
> I did not understand the code (specifically why the right shift of 16 twice?)

It's a traditional trick to get the upper 32 bits.

So it basically splits the (possibly 64-bit) pointer into the lower 32
bits and the upper 32 bits for a hash such as "jhash()" that takes
data that is "unsigned int".

(NOTE! Using jhash here is not acceptable, since it's not
cryptographically safe, but think of it as an example of a hash that
takes 32-bit input).

Doing ">> 32" is undefined on 32-bit architectures, and wouldn't work.

But doing >> 16 >> 16 is a fine way to say "shift right by 32 on a
64-bit architecture" while also being well-defined on a 32-bit one.

               Linus

Re: [PATCH 0/3] add %pX specifier

[Tobin C. Harding]

On Tue, Oct 10, 2017 at 04:15:01PM -0700, Linus Torvalds wrote:
> On Tue, Oct 10, 2017 at 4:09 PM, Tobin C. Harding <me@tobin.cc> wrote:
> >
> > I did not understand the code (specifically why the right shift of 16 twice?)
> 
> It's a traditional trick to get the upper 32 bits.
> 
> So it basically splits the (possibly 64-bit) pointer into the lower 32
> bits and the upper 32 bits for a hash such as "jhash()" that takes
> data that is "unsigned int".
> 
> (NOTE! Using jhash here is not acceptable, since it's not
> cryptographically safe, but think of it as an example of a hash that
> takes 32-bit input).
> 
> Doing ">> 32" is undefined on 32-bit architectures, and wouldn't work.
> 
> But doing >> 16 >> 16 is a fine way to say "shift right by 32 on a
> 64-bit architecture" while also being well-defined on a 32-bit one.
> 
>                Linus

Awesome, thanks.

Tobin.

Re: [PATCH 0/3] add %pX specifier

[Joe Perches]

On Wed, 2017-10-11 at 10:32 +1100, Tobin C. Harding wrote:
> On Tue, Oct 10, 2017 at 04:15:01PM -0700, Linus Torvalds wrote:
> > On Tue, Oct 10, 2017 at 4:09 PM, Tobin C. Harding <me@tobin.cc> wrote:
> > > 
> > > I did not understand the code (specifically why the right shift of 16 twice?)
> > 
> > It's a traditional trick to get the upper 32 bits.
> > 
> > So it basically splits the (possibly 64-bit) pointer into the lower 32
> > bits and the upper 32 bits for a hash such as "jhash()" that takes
> > data that is "unsigned int".
> > 
> > (NOTE! Using jhash here is not acceptable, since it's not
> > cryptographically safe, but think of it as an example of a hash that
> > takes 32-bit input).
> > 
> > Doing ">> 32" is undefined on 32-bit architectures, and wouldn't work.
> > 
> > But doing >> 16 >> 16 is a fine way to say "shift right by 32 on a
> > 64-bit architecture" while also being well-defined on a 32-bit one.
> > 
> >                Linus
> 
> Awesome, thanks.

Another way is using the upper_32_bits() macro.
It's perhaps a bit more readable.

Re: [PATCH 0/3] add %pX specifier

[Jason A. Donenfeld]

Hi Linus,

On Wed, Oct 11, 2017 at 1:15 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> (NOTE! Using jhash here is not acceptable, since it's not
> cryptographically safe, but think of it as an example of a hash that
> takes 32-bit input).

Ahh, yes, I should have continued to read the thread before replying
my first reply.

Indeed the correct functions to use would be siphash_1u32 or
siphash_1u64, depending. Depending on the popularity of that, we might
even consider making a siphash_1ulong helper, I suppose.

Jason

Re: [PATCH 0/3] add %pX specifier

[Linus Torvalds]

On Wed, Oct 11, 2017 at 1:11 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> Indeed the correct functions to use would be siphash_1u32 or
> siphash_1u64, depending. Depending on the popularity of that, we might
> even consider making a siphash_1ulong helper, I suppose.

Yeah, siphash is probably the sanest thing to use.

How bad would it be to use HalfSipHash on 32-bit architectures?

On a 32-bit machine, the full siphash is pretty expensive - big
constants, and lots of 64-bit shifts. And 32-bit machines also tend to
mean "slow machines" these days.

I suspect there's little point in worrying a ton about the 64-bit key,
considering that I think the *input* is generally more guessable than
the output or the key.

           Linus

Re: [PATCH 0/3] add %pX specifier

[Jason A. Donenfeld]

On Wed, Oct 11, 2017 at 11:29 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> Yeah, siphash is probably the sanest thing to use.
>
> How bad would it be to use HalfSipHash on 32-bit architectures?
>
> On a 32-bit machine, the full siphash is pretty expensive - big
> constants, and lots of 64-bit shifts. And 32-bit machines also tend to
> mean "slow machines" these days.
>
> I suspect there's little point in worrying a ton about the 64-bit key,
> considering that I think the *input* is generally more guessable than
> the output or the key.

[1.0000] Warning: kernel object at address A has a problem
[2.0000] Warning: kernel object at address B has a problem

A and B are known to be in the interval [M, N] ("they're both 128 byte
GFP_KERNEL allocations") and |A-B| is in the smaller interval [m, n]
("they're successive net_devices"). With a 64-bit key (as in
hsiphash), A and B can probably be bruteforced. If you can bruteforce
the key, then %pX==%p, so no good. While this still requires likely
>2^64 computation, this can be offloaded from a victim box and
parallelized.

So we probably want to stick with the 128-bit key of full SipHash for
both platforms. Fortunately, it's still pretty fast.



On another topic: the approach we're discussing here is using a PRF
(pseudo-random function), also known as a keyed hash function. It's
not reversible; it isn't encryption. Mapping 64-bit inputs to 64-bit
outputs means there _might_ be collisions. Not a very huge chance,
considering kernel pointers are nowhere near the full 64-bit domain,
but there's a non-zero chance. Of course, this kind of silly tiny
possibility doesn't actually matter at all for us, since it means
there'd just be an extremely rare confusing dmesg message. So who
cares.

But there is something slightly different that you might be interested
in: a PRP (psuedo-random permutation), also known as a block cipher.
In this case, there'd be a 64-bit to 64-bit reversible map, based on a
secret key, with no collisions. In other words, pointer encryption,
rather than hashing. Aarch64 has some special instructions for this,
with the QARMA tweakable block cipher being built-in. Might be fun to
nerd out about, but I don't know that we actually need this or would
want the complexity, and probably a PRF like SipHash is sufficient.
But thought I'd make you aware of the possibility, in case you're
interested.

Re: [PATCH 0/3] add %pX specifier

[Linus Torvalds]

On Wed, Oct 11, 2017 at 3:11 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> On another topic: the approach we're discussing here is using a PRF
> (pseudo-random function), also known as a keyed hash function. It's
> not reversible; it isn't encryption. Mapping 64-bit inputs to 64-bit
> outputs means there _might_ be collisions.

I really wouldn't worry about it.

In fact, I'd prefer mapping the pointer to a 32-bit value, even on
64-bit architectures. When people use these things for debugging and
for identifying which device node or socket or whatever they are
tracking, we're generally talking a (small) handful of different
devices or whatever.

Tobin did the statistics, most of the %p users are in drivers, and
they tend to be things like identifying *which* ACPI descriptor we're
talking about, or which command/request we're tracing, or which device
we're probing etc.  So _when_ we're talking about identities (as
opposed to when people actually want the true physical device address
or whatever), we're generally talking just a few entries. Maybe tens.

Can we get collisions when unlucky? Sure. But most of the time it's
literally about trying to track the commands to one particular device,
or track one particular command through the debug output. A 32-bit
hash is fine, because if we have so many different things going on at
the same time that you'd have a noticeable risk of collisions, you'd
not depend on debug traces etc anyway, you'd start doing fancier
tracing (ie start filtering using ebpf etc).

> But there is something slightly different that you might be interested
> in: a PRP (psuedo-random permutation), also known as a block cipher.
> In this case, there'd be a 64-bit to 64-bit reversible map, based on a
> secret key, with no collisions. In other words, pointer encryption,
> rather than hashing. Aarch64 has some special instructions for this,
> with the QARMA tweakable block cipher being built-in. Might be fun to
> nerd out about, but I don't know that we actually need this or would
> want the complexity, and probably a PRF like SipHash is sufficient.
> But thought I'd make you aware of the possibility, in case you're
> interested.

My guess would be that something like that might be nice if it would
mean that we'd get hw acceleration for the hashing, and that the
reversibility would be entirely secondary.

But I assume that even when you do have some hardware support for
something like that, the kernel would likely not really be able to use
it, for the simple reason that people would expect it to be used for
other things (and then setup/teardown costs would likely make it more
expensive than just doing the software SipHash() or equivalent). The
kernel use would likely simply be too rare and occasional to warrant
dedicated hardware use.

                     Linus

Re: [PATCH 0/3] add %pX specifier

[Linus Torvalds]

On Tue, Oct 10, 2017 at 4:09 PM, Tobin C. Harding <me@tobin.cc> wrote:
>
> This patch is a softer version of Linus' suggestion because it does not change the behaviour of the
> %p specifier. I don't see the benefit in making such a breaking change without addressing the issue
> of %x (and I don't the balls to right now).

The thing is, this continues to have the exact same issue that %pK has
- because it is opt-in, effectively nobody will actually use it.

That's why I would suggest that if we do this way, we really change %p
and %pa to use the hashed value, to convert *everybody*. And then
people who have a good reason to actually expose the pointer have to
do the extra work and opt out.

                  Linus

Re: [PATCH 0/3] add %pX specifier

[Tobin C. Harding]

On Tue, Oct 10, 2017 at 04:16:55PM -0700, Linus Torvalds wrote:
> On Tue, Oct 10, 2017 at 4:09 PM, Tobin C. Harding <me@tobin.cc> wrote:
> >
> > This patch is a softer version of Linus' suggestion because it does not change the behaviour of the
> > %p specifier. I don't see the benefit in making such a breaking change without addressing the issue
> > of %x (and I don't the balls to right now).
> 
> The thing is, this continues to have the exact same issue that %pK has
> - because it is opt-in, effectively nobody will actually use it.
> 
> That's why I would suggest that if we do this way, we really change %p
> and %pa to use the hashed value, to convert *everybody*. And then
> people who have a good reason to actually expose the pointer have to
> do the extra work and opt out.
> 
>                   Linus

Righto, I'll wait 24 hours and submit v2 with the change as suggested. I guess now is as good a time
as any annoy everybody and cause them to do work (for the greater good :)

Then I can direct effort at finding any users of %x for kernel addresses.

thanks,
Tobin.

RE: [PATCH 0/3] add %pX specifier

[Roberts, William C]

> -----Original Message-----
> From: linus971@gmail.com [mailto:linus971@gmail.com] On Behalf Of Linus
> Torvalds
> Sent: Tuesday, October 10, 2017 4:17 PM
> To: Tobin C. Harding <me@tobin.cc>
> Cc: kernel-hardening@lists.openwall.com; KVM list <kvm@vger.kernel.org>;
> Linux Kernel Mailing List <linux-kernel@vger.kernel.org>; Kees Cook
> <keescook@chromium.org>; Paolo Bonzini <pbonzini@redhat.com>; Tycho
> Andersen <tycho@docker.com>; Roberts, William C
> <william.c.roberts@intel.com>; Tejun Heo <tj@kernel.org>; Jordan Glover
> <Golden_Miller83@protonmail.ch>; Greg KH <gregkh@linuxfoundation.org>;
> Petr Mladek <pmladek@suse.com>; Joe Perches <joe@perches.com>; Ian
> Campbell <ijc@hellion.org.uk>; Sergey Senozhatsky
> <sergey.senozhatsky@gmail.com>; Catalin Marinas <catalin.marinas@arm.com>;
> Will Deacon <will.deacon@arm.com>; Steven Rostedt <rostedt@goodmis.org>;
> Chris Fries <cfries@google.com>; Dave Weinstein <olorin@google.com>; Daniel
> Micay <danielmicay@gmail.com>; Djalal Harouni <tixxdz@gmail.com>
> Subject: Re: [PATCH 0/3] add %pX specifier
> 
> On Tue, Oct 10, 2017 at 4:09 PM, Tobin C. Harding <me@tobin.cc> wrote:
> >
> > This patch is a softer version of Linus' suggestion because it does
> > not change the behaviour of the %p specifier. I don't see the benefit
> > in making such a breaking change without addressing the issue of %x (and I
> don't the balls to right now).
> 
> The thing is, this continues to have the exact same issue that %pK has
> - because it is opt-in, effectively nobody will actually use it.
> 
> That's why I would suggest that if we do this way, we really change %p and %pa
> to use the hashed value, to convert *everybody*. And then people who have a
> good reason to actually expose the pointer have to do the extra work and opt
> out.

Yes we cannot make this opt in or there is really no point in doing it. %pK and mistakes
got us here to this point. I see there is multiple threads, this getting really fun to follow.

> 
>                   Linus

Re: [PATCH 0/3] add %pX specifier

[Tobin Harding]

On Sat, Oct 14, 2017, at 04:54, Roberts, William C wrote:
> 
> 
> > -----Original Message-----
> > From: linus971@gmail.com [mailto:linus971@gmail.com] On Behalf Of Linus
> > Torvalds
> > Sent: Tuesday, October 10, 2017 4:17 PM
> > To: Tobin C. Harding <me@tobin.cc>
> > Cc: kernel-hardening@lists.openwall.com; KVM list <kvm@vger.kernel.org>;
> > Linux Kernel Mailing List <linux-kernel@vger.kernel.org>; Kees Cook
> > <keescook@chromium.org>; Paolo Bonzini <pbonzini@redhat.com>; Tycho
> > Andersen <tycho@docker.com>; Roberts, William C
> > <william.c.roberts@intel.com>; Tejun Heo <tj@kernel.org>; Jordan Glover
> > <Golden_Miller83@protonmail.ch>; Greg KH <gregkh@linuxfoundation.org>;
> > Petr Mladek <pmladek@suse.com>; Joe Perches <joe@perches.com>; Ian
> > Campbell <ijc@hellion.org.uk>; Sergey Senozhatsky
> > <sergey.senozhatsky@gmail.com>; Catalin Marinas <catalin.marinas@arm.com>;
> > Will Deacon <will.deacon@arm.com>; Steven Rostedt <rostedt@goodmis.org>;
> > Chris Fries <cfries@google.com>; Dave Weinstein <olorin@google.com>; Daniel
> > Micay <danielmicay@gmail.com>; Djalal Harouni <tixxdz@gmail.com>
> > Subject: Re: [PATCH 0/3] add %pX specifier
> > 
> > On Tue, Oct 10, 2017 at 4:09 PM, Tobin C. Harding <me@tobin.cc> wrote:
> > >
> > > This patch is a softer version of Linus' suggestion because it does
> > > not change the behaviour of the %p specifier. I don't see the benefit
> > > in making such a breaking change without addressing the issue of %x (and I
> > don't the balls to right now).
> > 
> > The thing is, this continues to have the exact same issue that %pK has
> > - because it is opt-in, effectively nobody will actually use it.
> > 
> > That's why I would suggest that if we do this way, we really change %p and %pa
> > to use the hashed value, to convert *everybody*. And then people who have a
> > good reason to actually expose the pointer have to do the extra work and opt
> > out.
> 
> Yes we cannot make this opt in or there is really no point in doing it.
> %pK and mistakes
> got us here to this point. I see there is multiple threads, this getting
> really fun to follow.

The threading split is my fault. I have never worked on a patch series
with this many comments. How could I have gone about things differently
to prevent the thread separation? Should I have posted the second patch
set as a reply to the first (I did not because it was not a version 2). 
Further splitting occurred because I botched the `git send-email` and
sent only a cover-letter, this got some replies that lead to another
single patch (again it was quite different and seemed not to be a
version 2)? So we are left with three threads all discussing the same
changes. Is there anything one can do to rectify this position now?

thanks,
Tobin.

Re: [PATCH 0/3] add %pX specifier

[Jason A. Donenfeld]

Hi Tobin,

On Wed, Oct 11, 2017 at 1:09 AM, Tobin C. Harding <me@tobin.cc> wrote:
>
>   +        hashval = hash_three_words(
>   +                (unsigned long)ptr,
>   +                (unsigned long)ptr >> 16 >> 16,
>   +                boot_time_random_int);

This is most likely not what you want to be using. Take a look at the
siphash_* set of functions. If you're just hashing 1 64-bit pointer
with some secret, use siphash_1u64, for example. That's the right
interface for this purpose.

Regards,
Jason