Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1411503 > unrolled thread

Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin Andrew Morton <akpm@linux-foundation.org> - 2016-06-01 21:50 +0200
    Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin Emese Revfy <re.emese@gmail.com> - 2016-06-03 19:40 +0200
      Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc  plugin David Brown <david.brown@linaro.org> - 2016-06-06 15:40 +0200
        Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin Kees Cook <keescook@chromium.org> - 2016-06-06 18:00 +0200
        Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin "PaX Team" <pageexec@freemail.hu> - 2016-06-06 21:40 +0200
          Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc  plugin Theodore Ts'o <tytso@mit.edu> - 2016-06-07 01:20 +0200
            Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin "PaX Team" <pageexec@freemail.hu> - 2016-06-07 14:30 +0200
              Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc  plugin Theodore Ts'o <tytso@mit.edu> - 2016-06-07 16:00 +0200
                Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin "PaX Team" <pageexec@freemail.hu> - 2016-06-09 19:30 +0200
                  Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc  plugin Theodore Ts'o <tytso@mit.edu> - 2016-06-09 22:00 +0200
                    Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin Kees Cook <keescook@chromium.org> - 2016-06-09 22:10 +0200

#1411503 — Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On Tue, 31 May 2016 01:31:45 +0200 Emese Revfy <re.emese@gmail.com> wrote:

> This plugin mitigates the problem of the kernel having too little entropy during
> and after boot for generating crypto keys.
> 
> It creates a local variable in every marked function. The value of this variable is
> modified by randomly chosen operations (add, xor and rol) and
> random values (gcc generates them at compile time and the stack pointer at runtime).
> It depends on the control flow (e.g., loops, conditions).
> 
> Before the function returns the plugin writes this local variable
> into the latent_entropy global variable. The value of this global variable is
> added to the kernel entropy pool in do_one_initcall() and _do_fork().

I don't think I'm really understanding.  Won't this produce the same
value on each and every boot?

[toc] | [next] | [standalone]

#1413378

On Wed, 1 Jun 2016 12:42:27 -0700
Andrew Morton <akpm@linux-foundation.org> wrote:

> On Tue, 31 May 2016 01:31:45 +0200 Emese Revfy <re.emese@gmail.com> wrote:
> 
> > This plugin mitigates the problem of the kernel having too little entropy during
> > and after boot for generating crypto keys.
> > 
> > It creates a local variable in every marked function. The value of this variable is
> > modified by randomly chosen operations (add, xor and rol) and
> > random values (gcc generates them at compile time and the stack pointer at runtime).
> > It depends on the control flow (e.g., loops, conditions).
> > 
> > Before the function returns the plugin writes this local variable
> > into the latent_entropy global variable. The value of this global variable is
> > added to the kernel entropy pool in do_one_initcall() and _do_fork().
> 
> I don't think I'm really understanding.  Won't this produce the same
> value on each and every boot?

No, because of interrupts and intentional data races.

-- 
Emese

[toc] | [prev] | [next] | [standalone]

#1415040 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On Fri, Jun 03, 2016 at 07:42:52PM +0200, Emese Revfy wrote:
>On Wed, 1 Jun 2016 12:42:27 -0700
>Andrew Morton <akpm@linux-foundation.org> wrote:
>
>> On Tue, 31 May 2016 01:31:45 +0200 Emese Revfy <re.emese@gmail.com> wrote:
>>
>> > This plugin mitigates the problem of the kernel having too little entropy during
>> > and after boot for generating crypto keys.
>> >
>> > It creates a local variable in every marked function. The value of this variable is
>> > modified by randomly chosen operations (add, xor and rol) and
>> > random values (gcc generates them at compile time and the stack pointer at runtime).
>> > It depends on the control flow (e.g., loops, conditions).
>> >
>> > Before the function returns the plugin writes this local variable
>> > into the latent_entropy global variable. The value of this global variable is
>> > added to the kernel entropy pool in do_one_initcall() and _do_fork().
>>
>> I don't think I'm really understanding.  Won't this produce the same
>> value on each and every boot?
>
>No, because of interrupts and intentional data races.

Wouldn't that result in the value having one of a small number of
values, then?  Even if it was just one of thousands or millions of
values, it would make the search space quite small.

David

[toc] | [prev] | [next] | [standalone]

#1415245 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On Mon, Jun 6, 2016 at 6:38 AM, David Brown <david.brown@linaro.org> wrote:
> On Fri, Jun 03, 2016 at 07:42:52PM +0200, Emese Revfy wrote:
>>
>> On Wed, 1 Jun 2016 12:42:27 -0700
>> Andrew Morton <akpm@linux-foundation.org> wrote:
>>
>>> On Tue, 31 May 2016 01:31:45 +0200 Emese Revfy <re.emese@gmail.com>
>>> wrote:
>>>
>>> > This plugin mitigates the problem of the kernel having too little
>>> > entropy during
>>> > and after boot for generating crypto keys.
>>> >
>>> > It creates a local variable in every marked function. The value of this
>>> > variable is
>>> > modified by randomly chosen operations (add, xor and rol) and
>>> > random values (gcc generates them at compile time and the stack pointer
>>> > at runtime).
>>> > It depends on the control flow (e.g., loops, conditions).
>>> >
>>> > Before the function returns the plugin writes this local variable
>>> > into the latent_entropy global variable. The value of this global
>>> > variable is
>>> > added to the kernel entropy pool in do_one_initcall() and _do_fork().
>>>
>>> I don't think I'm really understanding.  Won't this produce the same
>>> value on each and every boot?
>>
>>
>> No, because of interrupts and intentional data races.
>
>
> Wouldn't that result in the value having one of a small number of
> values, then?  Even if it was just one of thousands or millions of
> values, it would make the search space quite small.

My understanding is that it's not cryptographically secure, but it
provides a way for different machines and different boots to end up
with different seeds here, which is a big improvement over some of the
embedded devices that all boot with the same entropy every time.

I would, however, like to see the documentation improved to describe
the "How" and "Why". The "What" is pretty well covered. Adding
comments to the plugin for kernel developers (not compiler developers)
would help a lot: assume the reader knows nothing about gcc plugins.
:)

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

[toc] | [prev] | [next] | [standalone]

#1415388 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On 6 Jun 2016 at 7:38, David Brown wrote:

> On Fri, Jun 03, 2016 at 07:42:52PM +0200, Emese Revfy wrote:
> >On Wed, 1 Jun 2016 12:42:27 -0700
> >Andrew Morton <akpm@linux-foundation.org> wrote:
> >
> >> I don't think I'm really understanding.  Won't this produce the same
> >> value on each and every boot?
> >
> >No, because of interrupts and intentional data races.
> 
> Wouldn't that result in the value having one of a small number of
> values, then?  Even if it was just one of thousands or millions of
> values, it would make the search space quite small.

what matters for latent entropy is not the actual values fed into the entropy
pool (they're effectively compile time constants save for runtime data dependent
computations) but the precise sequence of them. interrupts stir this sequence
and thus extract entropy. perhaps as a small example imagine that an uninterrupted
kernel boot sequence feeds these values into the entropy pool:
  A B C

now imagine that a single interrupt can occur around any one of these values:
  I A B C
  A I B C
  A B I C
  A B C I

this way we can obtain 4 different final pool states that translate into up
to 2 bits of latent entropy (depends on how probable each sequence is). note
that this works regardless whether the underlying hardware has a high resolution
timer whose values the interrupt handler would feed into the pool.

the kernel boot process executes many of the above sequences with each sequence
potentially having a different length (the number of __init functions and initcalls
depends on the kernel config, initcalls execute for different lengths of time,
interrupt windows have different lengths, etc). how all this translates into
something measurable is a good question as i said elsewhere in the thread, my
completely unscientific guess would be that the number of interrupts is somehow
proportional to the extracted latent entropy.

cheers,
 PaX Team

[toc] | [prev] | [next] | [standalone]

#1415560 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On Mon, Jun 06, 2016 at 09:30:12PM +0200, PaX Team wrote:
> 
> what matters for latent entropy is not the actual values fed into the entropy
> pool (they're effectively compile time constants save for runtime data dependent
> computations) but the precise sequence of them. interrupts stir this sequence
> and thus extract entropy. perhaps as a small example imagine that an uninterrupted
> kernel boot sequence feeds these values into the entropy pool:
>   A B C
> 
> now imagine that a single interrupt can occur around any one of these values:
>   I A B C
>   A I B C
>   A B I C
>   A B C I
> 
> this way we can obtain 4 different final pool states that translate into up
> to 2 bits of latent entropy (depends on how probable each sequence is). note
> that this works regardless whether the underlying hardware has a high resolution
> timer whose values the interrupt handler would feed into the pool.

Right, but if it's only about interrupts, we're doing this already
inside modern Linux kernels.  On every single interrupt we are mixing
into a per-CPU "fast mix" pool the IP from the interrupt registers.

Since we're not claiming any additional entropy, I suppose it won't
hurt to do it twice, two different ways, but I'm not sure how much it
will actually help, and by doing the instrumentation in every single
basic block, instead of in the interrupt handler, I would think it
would be cheaper to do it in the interrupt handler.

      	 	       	     - Ted

[toc] | [prev] | [next] | [standalone]

#1416121 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On 6 Jun 2016 at 19:13, Theodore Ts'o wrote:

> On Mon, Jun 06, 2016 at 09:30:12PM +0200, PaX Team wrote:
> > 
> > what matters for latent entropy is not the actual values fed into the entropy
> > pool (they're effectively compile time constants save for runtime data dependent
> > computations) but the precise sequence of them. interrupts stir this sequence
> > and thus extract entropy. perhaps as a small example imagine that an uninterrupted
> > kernel boot sequence feeds these values into the entropy pool:
> >   A B C
> > 
> > now imagine that a single interrupt can occur around any one of these values:
> >   I A B C
> >   A I B C
> >   A B I C
> >   A B C I
> > 
> > this way we can obtain 4 different final pool states that translate into up
> > to 2 bits of latent entropy (depends on how probable each sequence is). note
> > that this works regardless whether the underlying hardware has a high resolution
> > timer whose values the interrupt handler would feed into the pool.
> 
> Right, but if it's only about interrupts,

(i believe that) latent entropy is found in more than just interrupt timing, there're
also data dependent computations that can have entropy, either on a single system or
across a population of them.

> we're doing this already inside modern Linux kernels.  On every single
> interrupt we are mixing into a per-CPU "fast mix" pool the IP from the
> interrupt registers. 

i agree that sampling the kernel register state can have entropy (the plugin
already extracts the current stack pointer) but i'm much less sure about
userland (at least i see no dependence on !user_mode(...)) since an attacker
could feed no entropy into the pool but still get it credited.

cheers,
 PaX Team

[toc] | [prev] | [next] | [standalone]

#1416213 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On Tue, Jun 07, 2016 at 02:19:14PM +0200, PaX Team wrote:
> (i believe that) latent entropy is found in more than just interrupt timing, there're
> also data dependent computations that can have entropy, either on a single system or
> across a population of them.

It's not clear how much data dependent computations you would have in
kernel space that's not introduced by interrupts, but there would
some, I'm sure.

> > we're doing this already inside modern Linux kernels.  On every single
> > interrupt we are mixing into a per-CPU "fast mix" pool the IP from the
> > interrupt registers. 
> 
> i agree that sampling the kernel register state can have entropy (the plugin
> already extracts the current stack pointer) but i'm much less sure about
> userland (at least i see no dependence on !user_mode(...)) since an attacker
> could feed no entropy into the pool but still get it credited.

Well, the attacker can't control when the interrupts happen, but it
could try to burn power by simply having a thread spin in an infinite
loop ("0: jmp 0"), sure.  Of course, this would be rather noticeable,
and if there were any other jobs running, the attacker would be
degrading the amount of entropy that would be gathered, but not
eliminating it.

All of this goes into the question of how much entropy we can assume
can be gathered per interrupt (or in the case of basic block
instrumentation, per basic block).  IIRC, in the latent_entropy
patches, the assumption is that zero entropy should be credited,
correct?

In the case Linux's current get_interrupt_randomness(), there's a
reason I'm using a very conservative 1/64th of a bit per interrupt.
In practice, on most modern CPU where we have a cycle counter, even if
the bad guy was doing a "0: jmp 0" spinning loop, we would still get
entropy via the cycle counter interacting with what is hopefully a
certain amount of entropy from the interrupt timing.

On a crappy $50 Android phone/tablet from China, using an ancient ARM
chip that doesn't have any cycle counting facilities, we're kind of
screwed, but those devices have lousy batteries, so if you have an
attacker that has disabled the wakelocks and is spinning in an
infinite loop, the battery life won't last long, so the problem will
mostly solve itself when the phone dies.  :-)

       	     	    	     	   	  - Ted

[toc] | [prev] | [next] | [standalone]

#1418512 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On 7 Jun 2016 at 9:58, Theodore Ts'o wrote:

> On Tue, Jun 07, 2016 at 02:19:14PM +0200, PaX Team wrote:
> > (i believe that) latent entropy is found in more than just interrupt timing, there're
> > also data dependent computations that can have entropy, either on a single system or
> > across a population of them.
> 
> It's not clear how much data dependent computations you would have in
> kernel space that's not introduced by interrupts, but there would
> some, I'm sure.

there's plenty of such computations both during boot and later as well. starting
with kernel command line options through parsing firmware provided data to hardware
configurations to processing various queues, lists, trees, file systems, network
packets, etc. as for interrupts specifically, latent entropy can be extracted from
polled devices as well (e.g., i think even modern NICs can be turned into polling
mode under sufficient load as processing packets that way is more efficient).

> > i agree that sampling the kernel register state can have entropy (the plugin
> > already extracts the current stack pointer) but i'm much less sure about
> > userland (at least i see no dependence on !user_mode(...)) since an attacker
> > could feed no entropy into the pool but still get it credited.
> 
> Well, the attacker can't control when the interrupts happen, but it
> could try to burn power by simply having a thread spin in an infinite
> loop ("0: jmp 0"), sure.

yes, that's one obvious way to accomplish it but even normal applications can
behave in a similar way, think about spinning event loops, media decoding, etc
whose sampled insn ptrs may provide less entropy than they get credited for.

> All of this goes into the question of how much entropy we can assume
> can be gathered per interrupt (or in the case of basic block
> instrumentation, per basic block).  IIRC, in the latent_entropy
> patches, the assumption is that zero entropy should be credited,
> correct?

yes, no entropy is credited since i don't know how much there is and i tend to err
on the side of safety which means crediting 0 entropy for latent entropy. of course
the expectation is that it's not actually 0 but to prove any specific value or limit
is beyond my skills at least.

> In the case Linux's current get_interrupt_randomness(), there's a
> reason I'm using a very conservative 1/64th of a bit per interrupt.

i think it's not just per 64 interrupts but also after each elapsed second (i.e.,
whichever condition occurs first), so on an idle system (which i believe is more
likely to occur on exactly those small systems that the referenced paper was concerned
about) the credited entropy could be overestimated.

> In practice, on most modern CPU where we have a cycle counter,

a quick check for get_cycles shows that at least these archs seem to return 0:
arc, avr32, cris, frv, m32r, m68k, xtensa. now you may not think of them as modern,
but they're still used in real life devices. i think that latent entropy is still
an option on them.

cheers,
 PaX Team

[toc] | [prev] | [next] | [standalone]

#1418616 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On Thu, Jun 09, 2016 at 07:22:29PM +0200, PaX Team wrote:
> > Well, the attacker can't control when the interrupts happen, but it
> > could try to burn power by simply having a thread spin in an infinite
> > loop ("0: jmp 0"), sure.
> 
> yes, that's one obvious way to accomplish it but even normal applications can
> behave in a similar way, think about spinning event loops, media decoding, etc
> whose sampled insn ptrs may provide less entropy than they get credited for.

Sure, as long as we're assuming less than one bit of entropy per
interrupt, even for a loop which which is:

1:   cmpl    $1, -8(%rsp)
     jz	     1b

there would still be *some* uncertainty.  And with an event loop there
would be more instructions to sample.  Granted, the number of cycles
spent in each will be different, so there will be some biasing, but
that's one of the reason why we've been using 1/64 bit per interrupt.

> yes, no entropy is credited since i don't know how much there is and i tend to err
> on the side of safety which means crediting 0 entropy for latent entropy. of course
> the expectation is that it's not actually 0 but to prove any specific value or limit
> is beyond my skills at least.

Sure, that's fair.

> i think it's not just per 64 interrupts but also after each elapsed second (i.e.,
> whichever condition occurs first), so on an idle system (which i believe is more
> likely to occur on exactly those small systems that the referenced paper was concerned
> about) the credited entropy could be overestimated.

That's a fair concern.  It might be that we should enforce some
minimum (at least 8 interrupts in all cases), but this is where it's
all about hueristics, especially on those systems that don't have random_get_entropy().

> > In practice, on most modern CPU where we have a cycle counter,
> 
> a quick check for get_cycles shows that at least these archs seem to return 0:
> arc, avr32, cris, frv, m32r, m68k, xtensa. now you may not think of them as modern,
> but they're still used in real life devices. i think that latent entropy is still
> an option on them.

It's possible for a system not to have a cycle counter, but to have
something that can be used instead for random_get_entropy.  That's
only being used for the m68k/amiga and mips/R6000[A] cases, but I keep
hoping that the archiecture maintainers for osme of these other
oddball platform (is that better than "non-modern"? :-) will come up
with something, but yes, it is those platforms where I've always been
the most worried.  On the one hand, if the hardware is crap, there's
very little you can do.  Unfortnuately, very often these crap
architectures have a very low BOM cost, so they are most likely to be
used in IOT devices.   :-(

One could try to claim that these IOT devics won't have upgradeable
firmware and, so they'll probably be security disasters even without a
good random number generators, but oddly, that doesn't give me much
solace...

And in the end, that may be the strongest argment for the
latent_entropy plugin.  Even if it doesn't provide a lot of extra
entropy, on those platforms we're going to be so starved of real
entropy that almost anything will be better than what we have today.

	     	    	     	     	    	 - Ted

[toc] | [prev] | [next] | [standalone]

#1418619 — Re: [kernel-hardening] Re: [PATCH v2 1/3] Add the latent_entropy gcc plugin

On Thu, Jun 9, 2016 at 12:55 PM, Theodore Ts'o <tytso@mit.edu> wrote:
> On Thu, Jun 09, 2016 at 07:22:29PM +0200, PaX Team wrote:
>> > Well, the attacker can't control when the interrupts happen, but it
>> > could try to burn power by simply having a thread spin in an infinite
>> > loop ("0: jmp 0"), sure.
>>
>> yes, that's one obvious way to accomplish it but even normal applications can
>> behave in a similar way, think about spinning event loops, media decoding, etc
>> whose sampled insn ptrs may provide less entropy than they get credited for.
>
> Sure, as long as we're assuming less than one bit of entropy per
> interrupt, even for a loop which which is:
>
> 1:   cmpl    $1, -8(%rsp)
>      jz      1b
>
> there would still be *some* uncertainty.  And with an event loop there
> would be more instructions to sample.  Granted, the number of cycles
> spent in each will be different, so there will be some biasing, but
> that's one of the reason why we've been using 1/64 bit per interrupt.
>
>> yes, no entropy is credited since i don't know how much there is and i tend to err
>> on the side of safety which means crediting 0 entropy for latent entropy. of course
>> the expectation is that it's not actually 0 but to prove any specific value or limit
>> is beyond my skills at least.
>
> Sure, that's fair.
>
>> i think it's not just per 64 interrupts but also after each elapsed second (i.e.,
>> whichever condition occurs first), so on an idle system (which i believe is more
>> likely to occur on exactly those small systems that the referenced paper was concerned
>> about) the credited entropy could be overestimated.
>
> That's a fair concern.  It might be that we should enforce some
> minimum (at least 8 interrupts in all cases), but this is where it's
> all about hueristics, especially on those systems that don't have random_get_entropy().
>
>> > In practice, on most modern CPU where we have a cycle counter,
>>
>> a quick check for get_cycles shows that at least these archs seem to return 0:
>> arc, avr32, cris, frv, m32r, m68k, xtensa. now you may not think of them as modern,
>> but they're still used in real life devices. i think that latent entropy is still
>> an option on them.
>
> It's possible for a system not to have a cycle counter, but to have
> something that can be used instead for random_get_entropy.  That's
> only being used for the m68k/amiga and mips/R6000[A] cases, but I keep
> hoping that the archiecture maintainers for osme of these other
> oddball platform (is that better than "non-modern"? :-) will come up
> with something, but yes, it is those platforms where I've always been
> the most worried.  On the one hand, if the hardware is crap, there's
> very little you can do.  Unfortnuately, very often these crap
> architectures have a very low BOM cost, so they are most likely to be
> used in IOT devices.   :-(
>
> One could try to claim that these IOT devics won't have upgradeable
> firmware and, so they'll probably be security disasters even without a
> good random number generators, but oddly, that doesn't give me much
> solace...
>
> And in the end, that may be the strongest argment for the
> latent_entropy plugin.  Even if it doesn't provide a lot of extra
> entropy, on those platforms we're going to be so starved of real
> entropy that almost anything will be better than what we have today.

Yeah, that's been my thinking around this. And on more sane systems,
using latent_entropy doesn't make things worse. :)

-Kees

-- 
Kees Cook
Chrome OS & Brillo Security

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web