Hashed pointer issues

Hashed pointer issues

[Anna-Maria Gleixner]

Hi,

I stumbled over an issue with hashed pointers and tracing. 

I'm using trace points for examination and on error the trace buffers
are dumped. The error occurs when entropy has not been set up, so the
pointers are not hashed and only (ptrval) is printed instead. The
pointers are required to distinguish the different objects in the
trace.

Beside workarounds like patching lib/vsprintf.c helpers before testing
or dumping trace buffers later (given that kernel comes up properly
and entropy is set up), is there a possible generic solution for this
issue? A commandline option for disabling the pointer obfuscation
would be a pretty handy tool.


Thanks,

      Anna-Maria

Re: Hashed pointer issues

[Kees Cook]

On Mon, Apr 30, 2018 at 8:50 AM, Anna-Maria Gleixner
<anna-maria@linutronix.de> wrote:
> Hi,
>
> I stumbled over an issue with hashed pointers and tracing.
>
> I'm using trace points for examination and on error the trace buffers
> are dumped. The error occurs when entropy has not been set up, so the
> pointers are not hashed and only (ptrval) is printed instead. The
> pointers are required to distinguish the different objects in the
> trace.
>
> Beside workarounds like patching lib/vsprintf.c helpers before testing
> or dumping trace buffers later (given that kernel comes up properly
> and entropy is set up), is there a possible generic solution for this
> issue? A commandline option for disabling the pointer obfuscation
> would be a pretty handy tool.

I (or other folks?) had proposed this before, but, AIUI, Linus remains
opposed. I still think something like this would be useful:

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 30c0cb8cc9bc..22bf631395d1 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1703,12 +1703,27 @@ static int __init initialize_ptr_random(void)
 }
 early_initcall(initialize_ptr_random);

+static bool bypass_pointer_hashing __ro_after_init;
+
+static int __init early_bypass_pointer_hashing_param(char *buf)
+{
+       if (!buf)
+               return -EINVAL;
+       return strtobool(buf, &bypass_pointer_hashing);
+}
+early_param("bypass_pointer_hashing", early_bypass_pointer_hashing_param);
+
 /* Maps a pointer to a 32 bit unique identifier. */
 static char *ptr_to_id(char *buf, char *end, void *ptr, struct
printf_spec spec)
 {
        unsigned long hashval;
        const int default_width = 2 * sizeof(ptr);

+       if (unlikely(bypass_pointer_hashing)) {
+               hashval = (uintptr_t)ptr;
+               goto bypass;
+       }
+
        if (unlikely(!have_filled_random_ptr_key)) {
                spec.field_width = default_width;
                /* string length must be less than default_width */
@@ -1726,6 +1741,7 @@ static char *ptr_to_id(char *buf, char *end,
void *ptr, struct printf_spec spec)
        hashval = (unsigned long)siphash_1u32((u32)ptr, &ptr_key);
 #endif

+bypass:
        spec.flags |= SMALL;
        if (spec.field_width == -1) {
                spec.field_width = default_width;


(apologies for gmail-induced whitespace damage...)

-- 
Kees Cook
Pixel Security

Re: Hashed pointer issues

[Linus Torvalds]

On Mon, Apr 30, 2018 at 9:11 AM Kees Cook <keescook@chromium.org> wrote:

> I (or other folks?) had proposed this before, but, AIUI, Linus remains
> opposed.

Yeah, I hate this, because it will make people paper over their problems by
just booting with that option.

I think it should just be fixed.

Is there really any reason why trace buffers have to be dumped so early
that the entropy hasn't even taken yet?

And if we really want a command line option, can we make that still hash
the pointer, just force the entropy early. That way kernel developers that
test that command line option are still testing the *hashing*, they just
are missing the good entropy.

                 Linus

Re: Hashed pointer issues

[Steven Rostedt]

On Mon, 30 Apr 2018 16:31:52 +0000
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Mon, Apr 30, 2018 at 9:11 AM Kees Cook <keescook@chromium.org> wrote:
> 
> > I (or other folks?) had proposed this before, but, AIUI, Linus remains
> > opposed.  
> 
> Yeah, I hate this, because it will make people paper over their problems by
> just booting with that option.
> 
> I think it should just be fixed.
> 
> Is there really any reason why trace buffers have to be dumped so early
> that the entropy hasn't even taken yet?

In this case, an RCU stall was triggering and a "dump on oops" would
dump the trace buffers, (before entropy was established).

> 
> And if we really want a command line option, can we make that still hash
> the pointer, just force the entropy early. That way kernel developers that
> test that command line option are still testing the *hashing*, they just
> are missing the good entropy.
> 

That may work too. Even with bad entropy, pointers at start up are hard
to come by, and I can't see a hacker being able to use them as it only
happens once during boot.

-- Steve

Re: Hashed pointer issues

[Linus Torvalds]

On Mon, Apr 30, 2018 at 9:41 AM Steven Rostedt <rostedt@goodmis.org> wrote:

> >
> > And if we really want a command line option, can we make that still hash
> > the pointer, just force the entropy early. That way kernel developers
that
> > test that command line option are still testing the *hashing*, they just
> > are missing the good entropy.

> That may work too. Even with bad entropy, pointers at start up are hard
> to come by, and I can't see a hacker being able to use them as it only
> happens once during boot.

No, if people use the command line option, *all* pointers - not just the
boot-time ones - would get cryptographically bad hashes, since you don't
want to change the hash once it's picked (because then you couldn't use the
hashing to identify objects).

So the boot command line wouldn't affect just the bootup hashing, it would
be bad at runtime too.

But at least a person booting with that option would get the same
*behavior* as everybody else, and they wouldn't be testing something
fundamnetally different (it's still hashing, just not cryptographically
strong).

Although in *practice* we'd have tons of entropy on any modern development
CPU too, since any new hardware will have the hardware random number
generation. Some overly cautious person might not trust it, of course.

                Linus

Re: Hashed pointer issues

[Linus Torvalds]

On Mon, Apr 30, 2018 at 9:57 AM Linus Torvalds <
torvalds@linux-foundation.org> wrote:

> Although in *practice* we'd have tons of entropy on any modern development
> CPU too, since any new hardware will have the hardware random number
> generation. Some overly cautious person might not trust it, of course.

In fact, maybe that's the right policy. Avoid a boot-time parameter by just
saying

  "if you have hardware random number generation, we can fill entropy
immediately"

No kernel command line needed in practice any more. That's assuming any
kernel developer will have an IvyBridge or newer.

The "I don't trust my hardware" people can still disable that with
"nordrand".

Hmm?

                    Linus

Re: Hashed pointer issues

[Randy Dunlap]

On 04/30/2018 10:01 AM, Linus Torvalds wrote:
> On Mon, Apr 30, 2018 at 9:57 AM Linus Torvalds <
> torvalds@linux-foundation.org> wrote:
> 
>> Although in *practice* we'd have tons of entropy on any modern development
>> CPU too, since any new hardware will have the hardware random number
>> generation. Some overly cautious person might not trust it, of course.
> 
> In fact, maybe that's the right policy. Avoid a boot-time parameter by just
> saying
> 
>   "if you have hardware random number generation, we can fill entropy
> immediately"
> 
> No kernel command line needed in practice any more. That's assuming any
> kernel developer will have an IvyBridge or newer.

any paid kernel developer :)

> 
> The "I don't trust my hardware" people can still disable that with
> "nordrand".
> 
> Hmm?


-- 
~Randy

Re: Hashed pointer issues

[Linus Torvalds]

On Mon, Apr 30, 2018 at 10:06 AM Randy Dunlap <rdunlap@infradead.org> wrote:
> On 04/30/2018 10:01 AM, Linus Torvalds wrote:
> >
> > No kernel command line needed in practice any more. That's assuming any
> > kernel developer will have an IvyBridge or newer.

> any paid kernel developer :)

I suspect a lot of hobbyists too - it's not like ivy bridge is particularly
new.

But if not, we can burn that bridge when we get to it.

Also, if you're not paid to do it, I don't think you'll be working a lot of
error trace buffers during bootup. There are definitely more interesting
parts of the kernel to play with ;)

               Linus

Re: Hashed pointer issues

[tcharding]

On Mon, Apr 30, 2018 at 05:12:05PM +0000, Linus Torvalds wrote:
> On Mon, Apr 30, 2018 at 10:06 AM Randy Dunlap <rdunlap@infradead.org> wrote:
> > On 04/30/2018 10:01 AM, Linus Torvalds wrote:
> > >
> > > No kernel command line needed in practice any more. That's assuming any
> > > kernel developer will have an IvyBridge or newer.
> 
> > any paid kernel developer :)
> 
> I suspect a lot of hobbyists too - it's not like ivy bridge is particularly
> new.
> 
> But if not, we can burn that bridge when we get to it.
> 
> Also, if you're not paid to do it, I don't think you'll be working a lot of
> error trace buffers during bootup. There are definitely more interesting
> parts of the kernel to play with ;)

Turns out my desktop (dev) machine is pretty old. RDRAND is only
available on 'newer' Core i5  

	"Intel Secure Key was added in Broadwell, so you need that or any later
	generation. Broadwell generation means Intel Core i5 or i7 where the
	4-digit number appended to it starts with a "5"."

	https://superuser.com/questions/999515/what-instruction-set-architecture-isa-is-rdrand-and-rdseed-part-of


Lucky the laptop is newer, RDRAND is supported on core M5Y70.


	Tobin

Re: Hashed pointer issues

[Geert Uytterhoeven]

On Mon, Apr 30, 2018 at 7:06 PM, Randy Dunlap <rdunlap@infradead.org> wrote:
> On 04/30/2018 10:01 AM, Linus Torvalds wrote:
>> On Mon, Apr 30, 2018 at 9:57 AM Linus Torvalds <
>> torvalds@linux-foundation.org> wrote:
>>
>>> Although in *practice* we'd have tons of entropy on any modern development
>>> CPU too, since any new hardware will have the hardware random number
>>> generation. Some overly cautious person might not trust it, of course.
>>
>> In fact, maybe that's the right policy. Avoid a boot-time parameter by just
>> saying
>>
>>   "if you have hardware random number generation, we can fill entropy
>> immediately"
>>
>> No kernel command line needed in practice any more. That's assuming any
>> kernel developer will have an IvyBridge or newer.
>
> any paid kernel developer :)

Developing for x86...

It takes several seconds to have collected sufficient entropy on e.g. some
ARM/ARM64 systems.

Gr{oetje,eeting}s,

                        Geert

-- 
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: Hashed pointer issues

[Kees Cook]

On Mon, Apr 30, 2018 at 10:01 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Mon, Apr 30, 2018 at 9:57 AM Linus Torvalds <
> torvalds@linux-foundation.org> wrote:
>
>> Although in *practice* we'd have tons of entropy on any modern development
>> CPU too, since any new hardware will have the hardware random number
>> generation. Some overly cautious person might not trust it, of course.
>
> In fact, maybe that's the right policy. Avoid a boot-time parameter by just
> saying
>
>   "if you have hardware random number generation, we can fill entropy
> immediately"

Something like this? (Untested.)

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 30c0cb8cc9bc..2d8615f14dc9 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1672,9 +1672,8 @@ char *pointer_string(char *buf, char *end, const
void *ptr,
 static bool have_filled_random_ptr_key __read_mostly;
 static siphash_key_t ptr_key __read_mostly;

-static void fill_random_ptr_key(struct random_ready_callback *unused)
+static void ptr_key_ready(void)
 {
-       get_random_bytes(&ptr_key, sizeof(ptr_key));
        /*
         * have_filled_random_ptr_key==true is dependent on get_random_bytes().
         * ptr_to_id() needs to see have_filled_random_ptr_key==true
@@ -1684,14 +1683,28 @@ static void fill_random_ptr_key(struct
random_ready_callback *unused)
        WRITE_ONCE(have_filled_random_ptr_key, true);
 }

+static void fill_random_ptr_key(struct random_ready_callback *unused)
+{
+       get_random_bytes(&ptr_key, sizeof(ptr_key));
+       ptr_key_ready();
+}
+
 static struct random_ready_callback random_ready = {
        .func = fill_random_ptr_key
 };

 static int __init initialize_ptr_random(void)
 {
-       int ret = add_random_ready_callback(&random_ready);
+       int ret;
+
+       /* If we have hw RNG, start hashing immediately. */
+       if (arch_has_random()) {
+               get_random_bytes_arch(&ptr_key, sizeof(ptr_key));
+               ptr_key_ready();
+               return 0;
+       }

+       ret = add_random_ready_callback(&random_ready);
        if (!ret) {
                return 0;
        } else if (ret == -EALREADY) {


>
> No kernel command line needed in practice any more. That's assuming any
> kernel developer will have an IvyBridge or newer.
>
> The "I don't trust my hardware" people can still disable that with
> "nordrand".
>
> Hmm?
>
>                     Linus



-- 
Kees Cook
Pixel Security

Re: Hashed pointer issues

[Linus Torvalds]

On Mon, Apr 30, 2018 at 11:38 AM Kees Cook <keescook@chromium.org> wrote:

> Something like this? (Untested.)

Looks workable.

> +       /* If we have hw RNG, start hashing immediately. */
> +       if (arch_has_random()) {
> +               get_random_bytes_arch(&ptr_key, sizeof(ptr_key));
> +               ptr_key_ready();
> +               return 0;
> +       }

Small tweak: you should check the return value of get_random_bytes_arch(),
because in theory it can fail.

Sadly, that's not actually how get_random_bytes_arch() really works - it
falls back on "get_random_bytes()" on failure instead, which is explicitly
against the whole point here.

So I think it would need some tweaking, with a new function entirely
(get_random_bytes_arch() with a failure return for "cannot fill buffer").

But that would be just a few more lines, because we could make the existing
get_random_bytes_arch() just use the failure-case thing.

So add a "get_hw_random_bytes()" that does that same loop in
get_random_bytes_arch(), but returns the number of bytes it filled in.

Then get_random_bytes_arch() turns into

     got = get_hw_random_bytes(p, nbytes);
     if (got < nbytes)
         get_random_bytes(p+got, nbytes-got);

and the initialize_ptr_random() use would be something like

     if (get_hw_random_bytes(&ptr_key, sizeof(ptr_key)) == sizeof(ptr_key)) {
         ptr_key_ready();
         return 0;
    }

Hmm?

Maybe we could call the "get_hw_random_bytes()" something like
"get_early_random_bytes()" and the "use HW for it" is purely an
implementation detail?

                Linus

Re: Hashed pointer issues

[Kees Cook]

On Mon, Apr 30, 2018 at 12:00 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Mon, Apr 30, 2018 at 11:38 AM Kees Cook <keescook@chromium.org> wrote:
>
>> Something like this? (Untested.)
>
> Looks workable.
>
>> +       /* If we have hw RNG, start hashing immediately. */
>> +       if (arch_has_random()) {
>> +               get_random_bytes_arch(&ptr_key, sizeof(ptr_key));
>> +               ptr_key_ready();
>> +               return 0;
>> +       }
>
> Small tweak: you should check the return value of get_random_bytes_arch(),
> because in theory it can fail.
>
> Sadly, that's not actually how get_random_bytes_arch() really works - it
> falls back on "get_random_bytes()" on failure instead, which is explicitly
> against the whole point here.

I just noticed: there are _no_ users of get_random_bytes_arch() ...
didn't we once use it to feed entropy to the CRNG?

> So I think it would need some tweaking, with a new function entirely
> (get_random_bytes_arch() with a failure return for "cannot fill buffer").
>
> But that would be just a few more lines, because we could make the existing
> get_random_bytes_arch() just use the failure-case thing.
>
> So add a "get_hw_random_bytes()" that does that same loop in
> get_random_bytes_arch(), but returns the number of bytes it filled in.
>
> Then get_random_bytes_arch() turns into
>
>      got = get_hw_random_bytes(p, nbytes);
>      if (got < nbytes)
>          get_random_bytes(p+got, nbytes-got);
>
> and the initialize_ptr_random() use would be something like
>
>      if (get_hw_random_bytes(&ptr_key, sizeof(ptr_key)) == sizeof(ptr_key)) {
>          ptr_key_ready();
>          return 0;
>     }
>
> Hmm?
>
> Maybe we could call the "get_hw_random_bytes()" something like
> "get_early_random_bytes()" and the "use HW for it" is purely an
> implementation detail?

Yeah, and if we add __must_check, I think this should be fine. Ted,
any thoughts on this?

Tobin, is this something you've got time to implement and test?

-Kees

-- 
Kees Cook
Pixel Security

Re: Hashed pointer issues

[Linus Torvalds]

On Mon, Apr 30, 2018 at 12:16 PM Kees Cook <keescook@chromium.org> wrote:

> I just noticed: there are _no_ users of get_random_bytes_arch() ...
> didn't we once use it to feed entropy to the CRNG?

We use arch_get_random_long() for that. See "crng_initialize()".

But if there are no actual users of get_random_bytes_arch(), maybe we can
just remove the fallback to the non-arch code, and add that return value
(and the __must_check()).

                    Linus

Re: Hashed pointer issues

[Linus Torvalds]

On Mon, Apr 30, 2018 at 1:01 PM Linus Torvalds <
torvalds@linux-foundation.org> wrote:

> But if there are no actual users of get_random_bytes_arch(), maybe we can
> just remove the fallback to the non-arch code, and add that return value
> (and the __must_check()).

Hmm. It is exported, so maybe there is some crazy module out there.

Also, I have to admit that I hate the idea of people using that function
for a "fast random number generator". I think it's fine for this kind of
"initialize hashing state" thing, but I would hate for somebody to actually
use "get_random_bytes_arch()" as an actual source of random bytes.

Even when the "real" random number generator uses it, at least it washes
the result through chacha20 and has other sources or entropy mixed in too.

So let's rename it regardless. Both to see if any external module actually
uses that get_random_bytes_arch() function, and to discourage people to use
it as direct random data.

Maybe call it something like "get_seed_bytes_arch()" or something.

And maybe I'm just being silly.

                  Linus

Re: Hashed pointer issues

[Tobin C. Harding]

On Mon, Apr 30, 2018 at 12:16:45PM -0700, Kees Cook wrote:
> On Mon, Apr 30, 2018 at 12:00 PM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> > On Mon, Apr 30, 2018 at 11:38 AM Kees Cook <keescook@chromium.org> wrote:
> >
> >> Something like this? (Untested.)
> >
> > Looks workable.
> >
> >> +       /* If we have hw RNG, start hashing immediately. */
> >> +       if (arch_has_random()) {
> >> +               get_random_bytes_arch(&ptr_key, sizeof(ptr_key));
> >> +               ptr_key_ready();
> >> +               return 0;
> >> +       }
> >
> > Small tweak: you should check the return value of get_random_bytes_arch(),
> > because in theory it can fail.
> >
> > Sadly, that's not actually how get_random_bytes_arch() really works - it
> > falls back on "get_random_bytes()" on failure instead, which is explicitly
> > against the whole point here.
> 
> I just noticed: there are _no_ users of get_random_bytes_arch() ...
> didn't we once use it to feed entropy to the CRNG?
> 
> > So I think it would need some tweaking, with a new function entirely
> > (get_random_bytes_arch() with a failure return for "cannot fill buffer").
> >
> > But that would be just a few more lines, because we could make the existing
> > get_random_bytes_arch() just use the failure-case thing.
> >
> > So add a "get_hw_random_bytes()" that does that same loop in
> > get_random_bytes_arch(), but returns the number of bytes it filled in.
> >
> > Then get_random_bytes_arch() turns into
> >
> >      got = get_hw_random_bytes(p, nbytes);
> >      if (got < nbytes)
> >          get_random_bytes(p+got, nbytes-got);
> >
> > and the initialize_ptr_random() use would be something like
> >
> >      if (get_hw_random_bytes(&ptr_key, sizeof(ptr_key)) == sizeof(ptr_key)) {
> >          ptr_key_ready();
> >          return 0;
> >     }
> >
> > Hmm?
> >
> > Maybe we could call the "get_hw_random_bytes()" something like
> > "get_early_random_bytes()" and the "use HW for it" is purely an
> > implementation detail?
> 
> Yeah, and if we add __must_check, I think this should be fine. Ted,
> any thoughts on this?
> 
> Tobin, is this something you've got time to implement and test?

Sure thing, thanks for the opportunity.

	Tobin