Patchwork proc: avoid information leaks to non-privileged processes

login
register
mail settings
Submitter Jake Edge
Date May 4, 2009, 6:51 p.m.
Message ID <20090504125114.5e391564@chukar>
Download mbox | patch
Permalink /patch/21766/
State New, archived
Headers show

Comments

Jake Edge - May 4, 2009, 6:51 p.m.
This is essentially v2 of "[PATCH] proc: avoid leaking eip, esp, or
wchan to non-privileged processes", adding some of Eric Biederman's
suggestions as well as the start_stack change (only give out that
address if the process is ptrace()-able).  This has been tested with ps
and top without any ill effects being seen.

proc: avoid information leaks to non-privileged processes

By using the same test as is used for /proc/pid/maps and /proc/pid/smaps,
only allow processes that can ptrace() a given process to see information
that might be used to bypass address space layout randomization (ASLR).
These include eip, esp, wchan, and start_stack in /proc/pid/stat as well
as the non-symbolic output from /proc/pid/wchan.

ASLR can be bypassed by sampling eip as shown by the proof-of-concept code
at http://code.google.com/p/fuzzyaslr/  As part of a presentation
(http://www.cr0.org/paper/to-jt-linux-alsr-leak.pdf) esp and wchan were also
noted as possibly usable information leaks as well.  The start_stack address
also leaks potentially useful information.

Cc: Stable Team <stable@kernel.org>
Signed-off-by: Jake Edge <jake@lwn.net>
---
 fs/proc/array.c |   13 +++++++++----
 fs/proc/base.c  |    5 ++++-
 2 files changed, 13 insertions(+), 5 deletions(-)
Linus Torvalds - May 4, 2009, 7 p.m.
On Mon, 4 May 2009, Jake Edge wrote:
>
> This is essentially v2 of "[PATCH] proc: avoid leaking eip, esp, or
> wchan to non-privileged processes", adding some of Eric Biederman's
> suggestions as well as the start_stack change (only give out that
> address if the process is ptrace()-able).  This has been tested with ps
> and top without any ill effects being seen.

Looks sane to me. Anybody objects?

		Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Arjan van de Ven - May 4, 2009, 7:51 p.m.
On Mon, 4 May 2009 12:00:12 -0700 (PDT)
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> 
> 
> On Mon, 4 May 2009, Jake Edge wrote:
> >
> > This is essentially v2 of "[PATCH] proc: avoid leaking eip, esp, or
> > wchan to non-privileged processes", adding some of Eric Biederman's
> > suggestions as well as the start_stack change (only give out that
> > address if the process is ptrace()-able).  This has been tested
> > with ps and top without any ill effects being seen.
> 
> Looks sane to me. Anybody objects?
> 

Acked-by: Arjan van de Ven <arjan@linux.intel.com>
Eric W. Biederman - May 4, 2009, 8:20 p.m.
Arjan van de Ven <arjan@infradead.org> writes:

> On Mon, 4 May 2009 12:00:12 -0700 (PDT)
> Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
>> 
>> 
>> On Mon, 4 May 2009, Jake Edge wrote:
>> >
>> > This is essentially v2 of "[PATCH] proc: avoid leaking eip, esp, or
>> > wchan to non-privileged processes", adding some of Eric Biederman's
>> > suggestions as well as the start_stack change (only give out that
>> > address if the process is ptrace()-able).  This has been tested
>> > with ps and top without any ill effects being seen.
>> 
>> Looks sane to me. Anybody objects?
>> 
>
> Acked-by: Arjan van de Ven <arjan@linux.intel.com>

Looks sane here.

Acked-by: "Eric W. Biederman" <ebiederm@xmission.com>

Eric
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Linus Torvalds - May 4, 2009, 10:24 p.m.
On Mon, 4 May 2009, Eric W. Biederman wrote:

> Arjan van de Ven <arjan@infradead.org> writes:
> 
> > On Mon, 4 May 2009 12:00:12 -0700 (PDT)
> > Linus Torvalds <torvalds@linux-foundation.org> wrote:
> >
> >> 
> >> 
> >> On Mon, 4 May 2009, Jake Edge wrote:
> >> >
> >> > This is essentially v2 of "[PATCH] proc: avoid leaking eip, esp, or
> >> > wchan to non-privileged processes", adding some of Eric Biederman's
> >> > suggestions as well as the start_stack change (only give out that
> >> > address if the process is ptrace()-able).  This has been tested
> >> > with ps and top without any ill effects being seen.
> >> 
> >> Looks sane to me. Anybody objects?
> >> 
> >
> > Acked-by: Arjan van de Ven <arjan@linux.intel.com>
> 
> Looks sane here.
> 
> Acked-by: "Eric W. Biederman" <ebiederm@xmission.com>

Ok, applied.

Also, does anybody have any commentary or opinion on the patch by Matt 
Mackall to use stronger random numbers than "get_random_int()". I wonder 
what the performance impact of that is - "get_random_int()" is very cheap 
by design, and many users may consider calling "get_random_bytes()" to be 
overkill and a potential performance issue.

Quite frankly, the way "get_random_bytes()" works now (it does a _full_ 
sha thing every time), I think it's insane overkill. But I do have to 
admit that our current "get_random_int()" is insane _underkill_.

I'd like to improve the latter without going to quie the extreme that 
matt's patch did.

		Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Arjan van de Ven - May 4, 2009, 11:26 p.m.
On Mon, 4 May 2009 15:24:15 -0700 (PDT)
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> 
> 
> On Mon, 4 May 2009, Eric W. Biederman wrote:
> 
> > Arjan van de Ven <arjan@infradead.org> writes:
> > 
> > > On Mon, 4 May 2009 12:00:12 -0700 (PDT)
> > > Linus Torvalds <torvalds@linux-foundation.org> wrote:
> > >
> > >> 
> > >> 
> > >> On Mon, 4 May 2009, Jake Edge wrote:
> > >> >
> > >> > This is essentially v2 of "[PATCH] proc: avoid leaking eip,
> > >> > esp, or wchan to non-privileged processes", adding some of
> > >> > Eric Biederman's suggestions as well as the start_stack change
> > >> > (only give out that address if the process is ptrace()-able).
> > >> > This has been tested with ps and top without any ill effects
> > >> > being seen.
> > >> 
> > >> Looks sane to me. Anybody objects?
> > >> 
> > >
> > > Acked-by: Arjan van de Ven <arjan@linux.intel.com>
> > 
> > Looks sane here.
> > 
> > Acked-by: "Eric W. Biederman" <ebiederm@xmission.com>
> 
> Ok, applied.
> 
> Also, does anybody have any commentary or opinion on the patch by
> Matt Mackall to use stronger random numbers than "get_random_int()".
> I wonder what the performance impact of that is - "get_random_int()"
> is very cheap by design, and many users may consider calling
> "get_random_bytes()" to be overkill and a potential performance issue.
> 
> Quite frankly, the way "get_random_bytes()" works now (it does a
> _full_ sha thing every time), I think it's insane overkill. But I do
> have to admit that our current "get_random_int()" is insane
> _underkill_.
> 
> I'd like to improve the latter without going to quie the extreme that 
> matt's patch did.

doing something simple as hashing in the tsc will already help;
while some people are nervous about the predictability of the tsc,
in practice there's likely enough bits of unpredictability there
to be worth the very low price of 50 cycles or less....
Linus Torvalds - May 4, 2009, 11:54 p.m.
On Mon, 4 May 2009, Linus Torvalds wrote:
> 
> Quite frankly, the way "get_random_bytes()" works now (it does a _full_ 
> sha thing every time), I think it's insane overkill. But I do have to 
> admit that our current "get_random_int()" is insane _underkill_.

Actually, I don't think "get_random_int()" is underkill per se (it does 
that half md4 transform to try to hide the source of the data), but the 
data itself is simply not modified at all, and the buffers aren't updated 
in between rounds.

In fact "secure_ip_id()" (which it uses) explicityl does that private 
hash[] array so that the mixing that "half_md4_transform()" does do will 
_not_ be saved for the next round - so the next round will always start 
from the same keyptr "secret" state.

I think.

If that wasn't the case, and we actually kept mixing up the end result 
back into the next iteration, I suspect the current "get_random_int()" 
wouldn't be _nearly_ as bad as it is now. 

Or maybe I'm missing some part of the transform, and we do mix the values 
back as we do that "get_random_int()". I just don't see it. And if I'm 
right, then I think _that_ is the real weakness of our current 
get_random_int().

			Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Matt Mackall - May 5, 2009, 5:50 a.m.
On Mon, May 04, 2009 at 03:24:15PM -0700, Linus Torvalds wrote:
> 
> 
> On Mon, 4 May 2009, Eric W. Biederman wrote:
> 
> > Arjan van de Ven <arjan@infradead.org> writes:
> > 
> > > On Mon, 4 May 2009 12:00:12 -0700 (PDT)
> > > Linus Torvalds <torvalds@linux-foundation.org> wrote:
> > >
> > >> 
> > >> 
> > >> On Mon, 4 May 2009, Jake Edge wrote:
> > >> >
> > >> > This is essentially v2 of "[PATCH] proc: avoid leaking eip, esp, or
> > >> > wchan to non-privileged processes", adding some of Eric Biederman's
> > >> > suggestions as well as the start_stack change (only give out that
> > >> > address if the process is ptrace()-able).  This has been tested
> > >> > with ps and top without any ill effects being seen.
> > >> 
> > >> Looks sane to me. Anybody objects?
> > >> 
> > >
> > > Acked-by: Arjan van de Ven <arjan@linux.intel.com>
> > 
> > Looks sane here.
> > 
> > Acked-by: "Eric W. Biederman" <ebiederm@xmission.com>
> 
> Ok, applied.
> 
> Also, does anybody have any commentary or opinion on the patch by Matt 
> Mackall to use stronger random numbers than "get_random_int()". I wonder 
> what the performance impact of that is - "get_random_int()" is very cheap 
> by design, and many users may consider calling "get_random_bytes()" to be 
> overkill and a potential performance issue.
> 
> Quite frankly, the way "get_random_bytes()" works now (it does a _full_ 
> sha thing every time), I think it's insane overkill. But I do have to 
> admit that our current "get_random_int()" is insane _underkill_.
> 
> I'd like to improve the latter without going to quie the extreme that 
> matt's patch did.

ASLR aside, get_random_u32 is the right interface (strong,
well-defined type) for random.c to export and get_random_int (weak,
ambiguous type) is the wrong one.

As to what's the appropriate sort of RNG for ASLR to use, finding a
balance between too strong and too weak is tricky. I'd rather move
things to a known safe point and back it off to acceptable performance
from there if anyone complains. So let's do my patch now.

Looking forward:

A faster-but-weakened RNG for ASLR (and similar purposes) will still
need to be strong in the cryptographic sense. Which probably means
having secret state (per cpu?) that changes at every call via a strong
cipher or hash (though lighter than the full RNG). Alternately, we use
a weak primitive (eg halfmd4) with per-task secrets. Not really keen
on the latter as a user may expose outputs across task boundaries that
allow backtracking attacks against the ASLR. In other words, the
latter requires disciplined users, while the former doesn't.
Ingo Molnar - May 5, 2009, 6:31 a.m.
* Matt Mackall <mpm@selenic.com> wrote:

> As to what's the appropriate sort of RNG for ASLR to use, finding 
> a balance between too strong and too weak is tricky. [...]

In exec-shield i mixed 'easily accessible and fast' semi-random 
state to the get_random_int() result: xor-ed the cycle counter, the 
pid and a kernel address to it. That strengthened the result in a 
pretty practical way (without strengthening the theoretical 
randomless - each of those items are considered guessable) and does 
so without weakening the entropy of the random pool.

As usual, it got objected to and removed during upstream review so 
the upstream code stands on a single foot only - which is an 
obviously bad idea.

The thing is, it's very hard to argue for (and prove) security 
related complexity on an objective basis. ASLR was met with quite 
some upstream hostility, so it did not really get merged upstream, 
it barely managed to limp upstream.

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Eric W. Biederman - May 5, 2009, 7:51 a.m.
Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Mon, 4 May 2009, Linus Torvalds wrote:
>> 
>> Quite frankly, the way "get_random_bytes()" works now (it does a _full_ 
>> sha thing every time), I think it's insane overkill. But I do have to 
>> admit that our current "get_random_int()" is insane _underkill_.
>
> Actually, I don't think "get_random_int()" is underkill per se (it does 
> that half md4 transform to try to hide the source of the data), but the 
> data itself is simply not modified at all, and the buffers aren't updated 
> in between rounds.
>
> In fact "secure_ip_id()" (which it uses) explicityl does that private 
> hash[] array so that the mixing that "half_md4_transform()" does do will 
> _not_ be saved for the next round - so the next round will always start 
> from the same keyptr "secret" state.
>
> I think.
>
> If that wasn't the case, and we actually kept mixing up the end result 
> back into the next iteration, I suspect the current "get_random_int()" 
> wouldn't be _nearly_ as bad as it is now. 
>
> Or maybe I'm missing some part of the transform, and we do mix the values 
> back as we do that "get_random_int()". I just don't see it. And if I'm 
> right, then I think _that_ is the real weakness of our current 
> get_random_int().

Yes, not mixing the result back (which would give us some kind of
pseudo random number generator) is the problem.

secure_ip_id, looks to be a very different kind of thing.  A seed
that is reused periodically.  Ultimately those values do change.

For the state we are mixing back into I expect we want it to be
per cpu so we don't need locks and avoid  cache line ping pongs
when we mix the state back.

I haven't seen Matts patch and couldn't find it when I did a quick
look so I don't have any idea there.

Eric
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Eric W. Biederman - May 5, 2009, 8:14 a.m.
Ingo Molnar <mingo@elte.hu> writes:

> * Matt Mackall <mpm@selenic.com> wrote:
>
>> As to what's the appropriate sort of RNG for ASLR to use, finding 
>> a balance between too strong and too weak is tricky. [...]
>
> In exec-shield i mixed 'easily accessible and fast' semi-random 
> state to the get_random_int() result: xor-ed the cycle counter, the 
> pid and a kernel address to it. That strengthened the result in a 
> pretty practical way (without strengthening the theoretical 
> randomless - each of those items are considered guessable) and does 
> so without weakening the entropy of the random pool.

The trouble is, that thinking completely misses the problem, and I
expect that is why we have a problem.  Throwing a bunch of possibly
truly random values into the pot for luck is nice.  But you didn't
throw in a pseudo random number generator.  An unpredictable sequence
that is guaranteed to change from one invocation to the next.

In a very practical sense a pseudo random generator is completely
sufficient.  Throwing in a few truly random numbers guards against
attacks on the random number generator.

What we have now is a hash over an a value that changes every 5 minutes
and some well known values.

Eric
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Andi Kleen - May 5, 2009, 8:58 a.m.
Matt Mackall <mpm@selenic.com> writes:
>
> Looking forward:
>
> A faster-but-weakened RNG for ASLR (and similar purposes) 

We really need it for the user space interface too, right now
recent glibc drains your entropy pool on every exec, and worse
recent kernels drain it now even with old glibc too. So any
system which doesn't have a active high frequency random number
source (which is most systems) doesn't have much real entropy
left for the applications that really need it.

-Andi (who always thought it was a bad idea to let ASLR weaken
your SSL/SSH session keys)
Ingo Molnar - May 5, 2009, 7:52 p.m.
* Eric W. Biederman <ebiederm@xmission.com> wrote:

> Ingo Molnar <mingo@elte.hu> writes:
> 
> > * Matt Mackall <mpm@selenic.com> wrote:
> >
> >> As to what's the appropriate sort of RNG for ASLR to use, finding 
> >> a balance between too strong and too weak is tricky. [...]
> >
> > In exec-shield i mixed 'easily accessible and fast' semi-random 
> > state to the get_random_int() result: xor-ed the cycle counter, the 
> > pid and a kernel address to it. That strengthened the result in a 
> > pretty practical way (without strengthening the theoretical 
> > randomless - each of those items are considered guessable) and does 
> > so without weakening the entropy of the random pool.
> 
> The trouble is, that thinking completely misses the problem, and I 
> expect that is why we have a problem.  Throwing a bunch of 
> possibly truly random values into the pot for luck is nice.  But 
> you didn't throw in a pseudo random number generator.  An 
> unpredictable sequence that is guaranteed to change from one 
> invocation to the next.

Alas, i did - it got 'reviewed' out of existence ;)

I still have the backups, here's the original exec-shield RNG:

+/*
+ * Get a random word:
+ */
+static inline unsigned int get_random_int(void)
+{
+       unsigned int val = 0;
+
+       if (!exec_shield_randomize)
+               return 0;
+
+#ifdef CONFIG_X86_HAS_TSC
+       rdtscl(val);
+#endif
+       val += current->pid + jiffies + (int)&val;
+
+       /*
+        * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
+        * every second, from the entropy pool (and thus creates a limited
+        * drain on it), and uses halfMD4Transform within the second. We
+        * also spice it with the TSC (if available), jiffies, PID and the
+        * stack address:
+        */
+       return secure_ip_id(val);
+}

I thought that basing it on the networking PRNG is proper design: 
the networking folks have showed it time and again that they care 
about the PRNG not being brute-forceable easily, while still staying 
fast enough.

I added the TSC and a few other pseudo-random details to increase 
complexity of any brute-force attack. (in the hope of rendering it 
less practical, at minimal cost)

> In a very practical sense a pseudo random generator is completely 
> sufficient.  Throwing in a few truly random numbers guards against 
> attacks on the random number generator.
> 
> What we have now is a hash over an a value that changes every 5 
> minutes and some well known values.

Yes.

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Matt Mackall - May 5, 2009, 8:22 p.m.
On Tue, May 05, 2009 at 09:52:46PM +0200, Ingo Molnar wrote:
> 
> * Eric W. Biederman <ebiederm@xmission.com> wrote:
> 
> > Ingo Molnar <mingo@elte.hu> writes:
> > 
> > > * Matt Mackall <mpm@selenic.com> wrote:
> > >
> > >> As to what's the appropriate sort of RNG for ASLR to use, finding 
> > >> a balance between too strong and too weak is tricky. [...]
> > >
> > > In exec-shield i mixed 'easily accessible and fast' semi-random 
> > > state to the get_random_int() result: xor-ed the cycle counter, the 
> > > pid and a kernel address to it. That strengthened the result in a 
> > > pretty practical way (without strengthening the theoretical 
> > > randomless - each of those items are considered guessable) and does 
> > > so without weakening the entropy of the random pool.
> > 
> > The trouble is, that thinking completely misses the problem, and I 
> > expect that is why we have a problem.  Throwing a bunch of 
> > possibly truly random values into the pot for luck is nice.  But 
> > you didn't throw in a pseudo random number generator.  An 
> > unpredictable sequence that is guaranteed to change from one 
> > invocation to the next.
> 
> Alas, i did - it got 'reviewed' out of existence ;)
> 
> I still have the backups, here's the original exec-shield RNG:
> 
> +/*
> + * Get a random word:
> + */
> +static inline unsigned int get_random_int(void)
> +{
> +       unsigned int val = 0;
> +
> +       if (!exec_shield_randomize)
> +               return 0;
> +
> +#ifdef CONFIG_X86_HAS_TSC
> +       rdtscl(val);
> +#endif
> +       val += current->pid + jiffies + (int)&val;
> +
> +       /*
> +        * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
> +        * every second, from the entropy pool (and thus creates a limited
> +        * drain on it), and uses halfMD4Transform within the second. We
> +        * also spice it with the TSC (if available), jiffies, PID and the
> +        * stack address:
> +        */
> +       return secure_ip_id(val);
> +}

Ingo, what are you on about? On every architecture but X86 with TSC
this is identical to the broken code.

TSC only helps matters slightly - the timescales involved in process
creation are very short and we can probably brute-force attack it with
a useful probability of success. ie:

a) record TSC
b) fork target process
c) record TSC
d) guess TSC value 
e) attempt attack
f) repeat
Eric W. Biederman - May 5, 2009, 9:20 p.m.
Matt Mackall <mpm@selenic.com> writes:

> On Tue, May 05, 2009 at 09:52:46PM +0200, Ingo Molnar wrote:
>> 
>> * Eric W. Biederman <ebiederm@xmission.com> wrote:
>> 
>> > Ingo Molnar <mingo@elte.hu> writes:
>> > 
>> > > * Matt Mackall <mpm@selenic.com> wrote:
>> > >
>> > >> As to what's the appropriate sort of RNG for ASLR to use, finding 
>> > >> a balance between too strong and too weak is tricky. [...]
>> > >
>> > > In exec-shield i mixed 'easily accessible and fast' semi-random 
>> > > state to the get_random_int() result: xor-ed the cycle counter, the 
>> > > pid and a kernel address to it. That strengthened the result in a 
>> > > pretty practical way (without strengthening the theoretical 
>> > > randomless - each of those items are considered guessable) and does 
>> > > so without weakening the entropy of the random pool.
>> > 
>> > The trouble is, that thinking completely misses the problem, and I 
>> > expect that is why we have a problem.  Throwing a bunch of 
>> > possibly truly random values into the pot for luck is nice.  But 
>> > you didn't throw in a pseudo random number generator.  An 
>> > unpredictable sequence that is guaranteed to change from one 
>> > invocation to the next.
>> 
>> Alas, i did - it got 'reviewed' out of existence ;)
>> 
>> I still have the backups, here's the original exec-shield RNG:
>> 
>> +/*
>> + * Get a random word:
>> + */
>> +static inline unsigned int get_random_int(void)
>> +{
>> +       unsigned int val = 0;
>> +
>> +       if (!exec_shield_randomize)
>> +               return 0;
>> +
>> +#ifdef CONFIG_X86_HAS_TSC
>> +       rdtscl(val);
>> +#endif
>> +       val += current->pid + jiffies + (int)&val;
>> +
>> +       /*
>> +        * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
>> +        * every second, from the entropy pool (and thus creates a limited
>> +        * drain on it), and uses halfMD4Transform within the second. We
>> +        * also spice it with the TSC (if available), jiffies, PID and the
>> +        * stack address:
>> +        */
>> +       return secure_ip_id(val);
>> +}
>
> Ingo, what are you on about? On every architecture but X86 with TSC
> this is identical to the broken code.

Well it has the val = (int)&val bit. 

However you are quite right the original get_random_int does not have
any state that persists from one call to the next.  Ingo you failed to
copy that from the way ip uses secure_ip_id.

Which ultimately means get_random_int has never had a pseudo random
number generator in it.

Eric
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Ingo Molnar - May 6, 2009, 10:30 a.m.
* Matt Mackall <mpm@selenic.com> wrote:

> On Tue, May 05, 2009 at 09:52:46PM +0200, Ingo Molnar wrote:
> > 
> > * Eric W. Biederman <ebiederm@xmission.com> wrote:
> > 
> > > Ingo Molnar <mingo@elte.hu> writes:
> > > 
> > > > * Matt Mackall <mpm@selenic.com> wrote:
> > > >
> > > >> As to what's the appropriate sort of RNG for ASLR to use, finding 
> > > >> a balance between too strong and too weak is tricky. [...]
> > > >
> > > > In exec-shield i mixed 'easily accessible and fast' semi-random 
> > > > state to the get_random_int() result: xor-ed the cycle counter, the 
> > > > pid and a kernel address to it. That strengthened the result in a 
> > > > pretty practical way (without strengthening the theoretical 
> > > > randomless - each of those items are considered guessable) and does 
> > > > so without weakening the entropy of the random pool.
> > > 
> > > The trouble is, that thinking completely misses the problem, and I 
> > > expect that is why we have a problem.  Throwing a bunch of 
> > > possibly truly random values into the pot for luck is nice.  But 
> > > you didn't throw in a pseudo random number generator.  An 
> > > unpredictable sequence that is guaranteed to change from one 
> > > invocation to the next.
> > 
> > Alas, i did - it got 'reviewed' out of existence ;)
> > 
> > I still have the backups, here's the original exec-shield RNG:
> > 
> > +/*
> > + * Get a random word:
> > + */
> > +static inline unsigned int get_random_int(void)
> > +{
> > +       unsigned int val = 0;
> > +
> > +       if (!exec_shield_randomize)
> > +               return 0;
> > +
> > +#ifdef CONFIG_X86_HAS_TSC
> > +       rdtscl(val);
> > +#endif
> > +       val += current->pid + jiffies + (int)&val;
> > +
> > +       /*
> > +        * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
> > +        * every second, from the entropy pool (and thus creates a limited
> > +        * drain on it), and uses halfMD4Transform within the second. We
> > +        * also spice it with the TSC (if available), jiffies, PID and the
> > +        * stack address:
> > +        */
> > +       return secure_ip_id(val);
> > +}
> 
> Ingo, what are you on about? On every architecture but X86 with 
> TSC this is identical to the broken code.

Note that this was the exec-shield arch/*86/mm/mmap.c code.

(Also, obviously "only" covering 95% of the Linux systems has its 
use as well. Most other architectures have their own cycle counters 
as well.)

> TSC only helps matters slightly - the timescales involved in 
> process creation are very short and we can probably brute-force 
> attack it with a useful probability of success. ie:
> 
> a) record TSC
> b) fork target process
> c) record TSC
> d) guess TSC value 
> e) attempt attack
> f) repeat

Try that one day and see how much jitter there is in that sequence, 
even on a completely quiescent system.

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Ingo Molnar - May 6, 2009, 10:33 a.m.
* Eric W. Biederman <ebiederm@xmission.com> wrote:

> Matt Mackall <mpm@selenic.com> writes:
> 
> > On Tue, May 05, 2009 at 09:52:46PM +0200, Ingo Molnar wrote:
> >> 
> >> * Eric W. Biederman <ebiederm@xmission.com> wrote:
> >> 
> >> > Ingo Molnar <mingo@elte.hu> writes:
> >> > 
> >> > > * Matt Mackall <mpm@selenic.com> wrote:
> >> > >
> >> > >> As to what's the appropriate sort of RNG for ASLR to use, finding 
> >> > >> a balance between too strong and too weak is tricky. [...]
> >> > >
> >> > > In exec-shield i mixed 'easily accessible and fast' semi-random 
> >> > > state to the get_random_int() result: xor-ed the cycle counter, the 
> >> > > pid and a kernel address to it. That strengthened the result in a 
> >> > > pretty practical way (without strengthening the theoretical 
> >> > > randomless - each of those items are considered guessable) and does 
> >> > > so without weakening the entropy of the random pool.
> >> > 
> >> > The trouble is, that thinking completely misses the problem, and I 
> >> > expect that is why we have a problem.  Throwing a bunch of 
> >> > possibly truly random values into the pot for luck is nice.  But 
> >> > you didn't throw in a pseudo random number generator.  An 
> >> > unpredictable sequence that is guaranteed to change from one 
> >> > invocation to the next.
> >> 
> >> Alas, i did - it got 'reviewed' out of existence ;)
> >> 
> >> I still have the backups, here's the original exec-shield RNG:
> >> 
> >> +/*
> >> + * Get a random word:
> >> + */
> >> +static inline unsigned int get_random_int(void)
> >> +{
> >> +       unsigned int val = 0;
> >> +
> >> +       if (!exec_shield_randomize)
> >> +               return 0;
> >> +
> >> +#ifdef CONFIG_X86_HAS_TSC
> >> +       rdtscl(val);
> >> +#endif
> >> +       val += current->pid + jiffies + (int)&val;
> >> +
> >> +       /*
> >> +        * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
> >> +        * every second, from the entropy pool (and thus creates a limited
> >> +        * drain on it), and uses halfMD4Transform within the second. We
> >> +        * also spice it with the TSC (if available), jiffies, PID and the
> >> +        * stack address:
> >> +        */
> >> +       return secure_ip_id(val);
> >> +}
> >
> > Ingo, what are you on about? On every architecture but X86 with TSC
> > this is identical to the broken code.
> 
> Well it has the val = (int)&val bit. 
> 
> However you are quite right the original get_random_int does not 
> have any state that persists from one call to the next.  Ingo you 
> failed to copy that from the way ip uses secure_ip_id.
> 
> Which ultimately means get_random_int has never had a pseudo 
> random number generator in it.

Indeed, good point. But, practical randomness was still saved by the 
other layers. Which what it is really about: adding different 
sources of semi-random values really increases attack complexity, 
and is cheap.

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Matt Mackall - May 6, 2009, 4:25 p.m.
On Wed, May 06, 2009 at 12:30:34PM +0200, Ingo Molnar wrote:
> (Also, obviously "only" covering 95% of the Linux systems has its 
> use as well. Most other architectures have their own cycle counters 
> as well.)

X86 might be 95% of desktop. But it's a small fraction of Linux
systems once you count cell phones, video players, TVs, cameras, GPS
devices, cars, routers, etc. almost none of which are x86-based. In
fact, just Linux cell phones (with about an 8% share of a 1.2billion
devices per year market) dwarf Linux desktops (maybe 5% of a
200m/y market).
Linus Torvalds - May 6, 2009, 4:48 p.m.
On Wed, 6 May 2009, Matt Mackall wrote:

> On Wed, May 06, 2009 at 12:30:34PM +0200, Ingo Molnar wrote:
> > (Also, obviously "only" covering 95% of the Linux systems has its 
> > use as well. Most other architectures have their own cycle counters 
> > as well.)
> 
> X86 might be 95% of desktop. But it's a small fraction of Linux
> systems once you count cell phones, video players, TVs, cameras, GPS
> devices, cars, routers, etc. almost none of which are x86-based. In
> fact, just Linux cell phones (with about an 8% share of a 1.2billion
> devices per year market) dwarf Linux desktops (maybe 5% of a
> 200m/y market).

Matt, are you willing to ack my suggested patch which adds history to the 
mix? Did somebody test that? I have this memory of there being an 
"exploit" program to show the non-randomness of the values, but I can't 
recall details, and would really want to get a second opinion from 
somebody who cares about PRNG's.

			Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Matt Mackall - May 6, 2009, 5:57 p.m.
On Wed, May 06, 2009 at 09:48:20AM -0700, Linus Torvalds wrote:
> 
> Matt, are you willing to ack my suggested patch which adds history to the 
> mix? Did somebody test that? I have this memory of there being an 
> "exploit" program to show the non-randomness of the values, but I can't 
> recall details, and would really want to get a second opinion from 
> somebody who cares about PRNG's.

I still don't like it. I bounced it off some folks on the adversarial
side of things and they didn't think it looked strong enough either.
Full MD5 collisions can be generated about as fast as they can be
checked, which makes _reduced strength_ MD4 not much better than an
LFSR in terms of attack potential. So I suggest we either:

a) take my original patch 
b) respin your patch using at least SHA1 rather than halfMD4 and
changing the name to get_random_u32

If you'd prefer (b), I'll do the legwork.
Ingo Molnar - May 6, 2009, 8:25 p.m.
* Matt Mackall <mpm@selenic.com> wrote:

> On Wed, May 06, 2009 at 12:30:34PM +0200, Ingo Molnar wrote:
> > (Also, obviously "only" covering 95% of the Linux systems has its 
> > use as well. Most other architectures have their own cycle counters 
> > as well.)
> 
> X86 might be 95% of desktop. But it's a small fraction of Linux 
> systems once you count cell phones, video players, TVs, cameras, 
> GPS devices, cars, routers, etc. almost none of which are 
> x86-based. In fact, just Linux cell phones (with about an 8% share 
> of a 1.2billion devices per year market) dwarf Linux desktops 
> (maybe 5% of a 200m/y market).

Firstly, the cycle counter is just one out of several layers there. 
So it's a hyperbole to suggest that i'm somehow not caring about 
architectures that dont have a cycle counter. I'm simply making use 
of a cheaply accessed and fast-changing variable on hw that has it.

Also, are those systems really going to be attacked locally, 
brute-forcing a PRNG? Servers and desktops are the more likely 
targets. They both have the necessary computing power to run 
statistical analysis locally fast enough and have an actual value to 
be attacked.

And, even if we ignored those factors, ad argumendo, you would still 
be wrong IMHO: what matters really in this context isnt even any 
artificial 'share' metric - but the people willing to improve and 
fix the upstream kernel, and the reasons why they do that, and the 
platforms they use.

And amongst our contributors and testers, willing to run and improve 
the latest upstream kernel, x86 has a larger than 95% share. Look at 
kerneloops.org stats. Or bugzilla. Or lkml.

If embedded matters that much, make it show up as a real factor on 
those upstream forums. Lets call this Ingo's Law: if something 
doesnt improve the upstream kernel, directly or indirectly, it does 
not exist ;-)

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Matt Mackall - May 6, 2009, 8:52 p.m.
On Wed, May 06, 2009 at 10:25:17PM +0200, Ingo Molnar wrote:
> 
> * Matt Mackall <mpm@selenic.com> wrote:
> 
> > On Wed, May 06, 2009 at 12:30:34PM +0200, Ingo Molnar wrote:
> > > (Also, obviously "only" covering 95% of the Linux systems has its 
> > > use as well. Most other architectures have their own cycle counters 
> > > as well.)
> > 
> > X86 might be 95% of desktop. But it's a small fraction of Linux 
> > systems once you count cell phones, video players, TVs, cameras, 
> > GPS devices, cars, routers, etc. almost none of which are 
> > x86-based. In fact, just Linux cell phones (with about an 8% share 
> > of a 1.2billion devices per year market) dwarf Linux desktops 
> > (maybe 5% of a 200m/y market).
> 
> Firstly, the cycle counter is just one out of several layers there. 
> So it's a hyperbole to suggest that i'm somehow not caring about 
> architectures that dont have a cycle counter. I'm simply making use 
> of a cheaply accessed and fast-changing variable on hw that has it.

Whatever, I've never argued against TSC being beneficial. But it sure
as hell is not sufficient. Your original claim that this attack was
not possible in your original code: still bogus.
 
> Also, are those systems really going to be attacked locally, 
> brute-forcing a PRNG? 

Yes[1], even though my point was mostly to shoot down your bogus
statistic for reasons unrelated to this discussion. If you want to
make a new claim that '95% of Linux systems interesting to Ingo are
x86', I won't argue with that.

[1] 95% of security holes are caused by developer failures of imagination.
Matt Mackall - May 7, 2009, 12:50 a.m.
On Wed, May 06, 2009 at 12:57:17PM -0500, Matt Mackall wrote:
> On Wed, May 06, 2009 at 09:48:20AM -0700, Linus Torvalds wrote:
> > 
> > Matt, are you willing to ack my suggested patch which adds history to the 
> > mix? Did somebody test that? I have this memory of there being an 
> > "exploit" program to show the non-randomness of the values, but I can't 
> > recall details, and would really want to get a second opinion from 
> > somebody who cares about PRNG's.
> 
> I still don't like it. I bounced it off some folks on the adversarial
> side of things and they didn't think it looked strong enough either.
> Full MD5 collisions can be generated about as fast as they can be
> checked, which makes _reduced strength_ MD4 not much better than an
> LFSR in terms of attack potential. So I suggest we either:
> 
> a) take my original patch 
> b) respin your patch using at least SHA1 rather than halfMD4 and
> changing the name to get_random_u32
> 
> If you'd prefer (b), I'll do the legwork.

I've done some basic benchmarks on the primitives here in userspace:

halfMD4 get_random_int: about .326us per call or 12.2MB/s
sha1 get_random_int: about .660us per call or 6.1MB/s
dd /dev/urandom: 3.6MB/s

So I think the SHA1 solution is quite competitive on the performance
front with far fewer concerns about its strength. I'll spin a proper
patch tomorrow.
Florian Weimer - May 7, 2009, 3:16 p.m.
* Matt Mackall:

> On Wed, May 06, 2009 at 09:48:20AM -0700, Linus Torvalds wrote:
>> 
>> Matt, are you willing to ack my suggested patch which adds history to the 
>> mix? Did somebody test that? I have this memory of there being an 
>> "exploit" program to show the non-randomness of the values, but I can't 
>> recall details, and would really want to get a second opinion from 
>> somebody who cares about PRNG's.
>
> I still don't like it. I bounced it off some folks on the adversarial
> side of things and they didn't think it looked strong enough either.
> Full MD5 collisions can be generated about as fast as they can be
> checked, which makes _reduced strength_ MD4 not much better than an
> LFSR in terms of attack potential.

Well, with periodic reseeding, even that shouldn't be a problem.  You
don't need collision resistance at all, so those MD5 attacks don't
tell you anything about the difficulty of state recovery/prediction
attacks on your variant.  (The trouble with hash functions is that
they haven't got any secrets to work from.  With seeded PRNGs, this is
obviously different.)

On the other hand, most people who need a quick, unpredictable source
of randomness seem to use RC4 with a random key initialized from a
more costly source.  (If you're paranoid, you should discard the first
few hundred bytes.)  The nice thing is that you can use a well-tested
primitive, unchanged, so it's easier to avoid nasty suprises.

Oh, and you should really, really ditch that Tausworthe generator (in
lib/random32.c).
Matt Mackall - May 7, 2009, 4:55 p.m.
On Thu, May 07, 2009 at 05:16:27PM +0200, Florian Weimer wrote:
> * Matt Mackall:
> 
> > On Wed, May 06, 2009 at 09:48:20AM -0700, Linus Torvalds wrote:
> >> 
> >> Matt, are you willing to ack my suggested patch which adds history to the 
> >> mix? Did somebody test that? I have this memory of there being an 
> >> "exploit" program to show the non-randomness of the values, but I can't 
> >> recall details, and would really want to get a second opinion from 
> >> somebody who cares about PRNG's.
> >
> > I still don't like it. I bounced it off some folks on the adversarial
> > side of things and they didn't think it looked strong enough either.
> > Full MD5 collisions can be generated about as fast as they can be
> > checked, which makes _reduced strength_ MD4 not much better than an
> > LFSR in terms of attack potential.
> 
> Well, with periodic reseeding, even that shouldn't be a problem.  You
> don't need collision resistance at all, so those MD5 attacks don't
> tell you anything about the difficulty of state recovery/prediction
> attacks on your variant.

It's *not* MD5. It's a reduced-round MD4. And MD4 is already many
orders of magnitude weaker than MD5. It's so weak in fact that
collisions can be generated in O(1)[1]. Hard to get much weaker than
that, except by, say, using something like our reduced-round variant.

It's not much of a stretch of the imagination to think that such an
amazingly weak hash might reveal our hidden state quite rapidly,
especially when used in a feedback mode.

[1] http://eprint.iacr.org/2005/151.pdf

We have a better hash function handy, and it's only takes twice as long.

> On the other hand, most people who need a quick, unpredictable source
> of randomness seem to use RC4 with a random key initialized from a
> more costly source.

Using a stream cipher is a fine idea. Ted and I have recently
discussed adding this as a layer to the stock RNG. We haven't used it
historically because of a) export restrictions and b) unsuitability of
the cryptoapi interface.

> Oh, and you should really, really ditch that Tausworthe generator (in
> lib/random32.c).

I'm not responsible for that particular bad idea.
Linus Torvalds - May 7, 2009, 5:53 p.m.
On Thu, 7 May 2009, Matt Mackall wrote:
> 
> We have a better hash function handy, and it's only takes twice as long.

Matt, I really don't like your notion of "only twice as long".

I mean, really. In the kernel, we tend to never even talk about how many 
_times_ slower something is. We talk about cycles or small percentages.

The fact is, the current "get_random_int()" is a joke, and will return the 
same value over and over again for long stretches of time. I mean, really. 
Even people who don't care a lot would expect more than _that_ out of a 
PRNG.

And quite frankly, a lot of the users of get_random_int() probably use it 
not as some crypto function, but as a replacement for not having to write 
their own copy of some standard PRNG linear congruential generator.

I mean, really. The virtual address randomization was never meant to be 
"cryptographically secure" in that sense. Dammit, look at the code: it 
only takes something like 8 bits of the results _anyway_.

In other words, YOUR WHOLE ARGUMENT IS TOTALLY INSANE. You talk about 
"cryptographically secure hashes" for some 8-bit value. Listen to 
yourself. At that point, any cryptographer will just ridicule you. There's 
no point in trying to break the randomness, because you'll be much better 
off just trying a lot of different values.

So Matt, get with the program already. Don't ignore the performance 
argument by saying "it's only twice as slow". Admit it - that's just 
idiotic.

If somebody _really_ wants true randomness, teach them to use 
"get_random_bytes()" by all means. 

			Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Matt Mackall - May 7, 2009, 6:42 p.m.
On Thu, May 07, 2009 at 10:53:49AM -0700, Linus Torvalds wrote:
> So Matt, get with the program already. Don't ignore the performance 
> argument by saying "it's only twice as slow". Admit it - that's just 
> idiotic.

If you want to take it out of random.c and put it in pinhead-rng.c, be
my guest. I'm not going to put my Acked-by on it.

Patch

diff --git a/fs/proc/array.c b/fs/proc/array.c
index 7e4877d..725a650 100644
--- a/fs/proc/array.c
+++ b/fs/proc/array.c
@@ -80,6 +80,7 @@ 
 #include <linux/delayacct.h>
 #include <linux/seq_file.h>
 #include <linux/pid_namespace.h>
+#include <linux/ptrace.h>
 #include <linux/tracehook.h>
 
 #include <asm/pgtable.h>
@@ -352,6 +353,7 @@  static int do_task_stat(struct seq_file *m, struct pid_namespace *ns,
 	char state;
 	pid_t ppid = 0, pgid = -1, sid = -1;
 	int num_threads = 0;
+	int permitted;
 	struct mm_struct *mm;
 	unsigned long long start_time;
 	unsigned long cmin_flt = 0, cmaj_flt = 0;
@@ -364,11 +366,14 @@  static int do_task_stat(struct seq_file *m, struct pid_namespace *ns,
 
 	state = *get_task_state(task);
 	vsize = eip = esp = 0;
+	permitted = ptrace_may_access(task, PTRACE_MODE_READ);
 	mm = get_task_mm(task);
 	if (mm) {
 		vsize = task_vsize(mm);
-		eip = KSTK_EIP(task);
-		esp = KSTK_ESP(task);
+		if (permitted) {
+			eip = KSTK_EIP(task);
+			esp = KSTK_ESP(task);
+		}
 	}
 
 	get_task_comm(tcomm, task);
@@ -424,7 +429,7 @@  static int do_task_stat(struct seq_file *m, struct pid_namespace *ns,
 		unlock_task_sighand(task, &flags);
 	}
 
-	if (!whole || num_threads < 2)
+	if (permitted && (!whole || num_threads < 2))
 		wchan = get_wchan(task);
 	if (!whole) {
 		min_flt = task->min_flt;
@@ -476,7 +481,7 @@  static int do_task_stat(struct seq_file *m, struct pid_namespace *ns,
 		rsslim,
 		mm ? mm->start_code : 0,
 		mm ? mm->end_code : 0,
-		mm ? mm->start_stack : 0,
+		(permitted && mm) ? mm->start_stack : 0,
 		esp,
 		eip,
 		/* The signal information here is obsolete.
diff --git a/fs/proc/base.c b/fs/proc/base.c
index aa763ab..fb45615 100644
--- a/fs/proc/base.c
+++ b/fs/proc/base.c
@@ -322,7 +322,10 @@  static int proc_pid_wchan(struct task_struct *task, char *buffer)
 	wchan = get_wchan(task);
 
 	if (lookup_symbol_name(wchan, symname) < 0)
-		return sprintf(buffer, "%lu", wchan);
+		if (!ptrace_may_access(task, PTRACE_MODE_READ))
+			return 0;
+		else
+			return sprintf(buffer, "%lu", wchan);
 	else
 		return sprintf(buffer, "%s", symname);
 }