[PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Pavel Emelyanov]

While doing the checkpoint-restore in the userspace one need to determine
whether various kernel objects (like mm_struct-s of file_struct-s) are shared
between tasks and restore this state.

The 2nd step can for now be solved by using respective CLONE_XXX flags and
the unshare syscall, while there's currently no ways for solving the 1st one.

One of the ways for checking whether two tasks share e.g. an mm_struct is to
provide some mm_struct ID of a task to its proc file. The best from the
performance point of view ID is the object address in the kernel, but showing
them to the userspace is not good for security reasons.

Thus the object address is XOR-ed with a "random" value of the same size and 
then shown in proc. Providing this poison is not leaked into the userspace then
ID seem to be safe. The objects for which the IDs are shown are:

* all namespaces living in /proc/pid/ns/
* open files (shown in /proc/pid/fdinfo/)
* objects, that can be shared with CLONE_XXX flags (except for namespaces)

Changes since
v1: * Tejun worried about the single poison value was a weak side - leaking one
      makes all the IDs vulnerable. To address this several poison values - one
      per object type - are introduced. They are stored in a plain array. Tejun, 
      is this enough from your POV, or you'd like to see them widely scattered 
      over the memory?
    * Pekka proposed to initialized poison values in the late_initcall callback
    * ... and move the code to mm/util.c

Signed-off-by: Pavel Emelyanov <xemul@parallels.com>

[PATCH 1/4] Routine for generating a safe ID for kernel pointer

[Pavel Emelyanov]

The routine XORs the given pointer with a random value thus producing
an ID (32 or 64 bit, depending on the arch) which can be shown even to
unprivileged user space processes without risking of leaking kernel
information.

Signed-off-by: Pavel Emelyanov <xemul@parallels.com>

---
 include/linux/mm.h |   13 +++++++++++++
 mm/Kconfig         |    7 +++++++
 mm/util.c          |   28 ++++++++++++++++++++++++++++
 3 files changed, 48 insertions(+), 0 deletions(-)

diff --git a/include/linux/mm.h b/include/linux/mm.h
index 7438071..80ea327 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -1627,5 +1627,18 @@ extern void copy_user_huge_page(struct page *dst, struct page *src,
 				unsigned int pages_per_huge_page);
 #endif /* CONFIG_TRANSPARENT_HUGEPAGE || CONFIG_HUGETLBFS */
 
+enum {
+	GEN_OBJ_ID_TYPES,
+};
+
+#ifdef CONFIG_GENERIC_OBJECT_IDS
+unsigned long gen_object_id(void *ptr, int type);
+#else
+static inline unsigned long gen_object_id(void *ptr, int type)
+{
+	return 0;
+}
+#endif
+
 #endif /* __KERNEL__ */
 #endif /* _LINUX_MM_H */
diff --git a/mm/Kconfig b/mm/Kconfig
index f2f1ca1..1480cbf 100644
--- a/mm/Kconfig
+++ b/mm/Kconfig
@@ -370,3 +370,10 @@ config CLEANCACHE
 	  in a negligible performance hit.
 
 	  If unsure, say Y to enable cleancache
+
+config GENERIC_OBJECT_IDS
+	bool "Enable generic object ids infrastructure"
+	default n
+	help
+	  Turn on the (quite simple) funtionality that can generate IDs for
+	  kernel objects which is safe to export to the userspace.
diff --git a/mm/util.c b/mm/util.c
index 88ea1bd..1bcde18 100644
--- a/mm/util.c
+++ b/mm/util.c
@@ -4,6 +4,7 @@
 #include <linux/module.h>
 #include <linux/err.h>
 #include <linux/sched.h>
+#include <linux/random.h>
 #include <asm/uaccess.h>
 
 #include "internal.h"
@@ -307,3 +308,30 @@ EXPORT_TRACEPOINT_SYMBOL(kmalloc_node);
 EXPORT_TRACEPOINT_SYMBOL(kmem_cache_alloc_node);
 EXPORT_TRACEPOINT_SYMBOL(kfree);
 EXPORT_TRACEPOINT_SYMBOL(kmem_cache_free);
+
+#ifdef CONFIG_GENERIC_OBJECT_IDS
+static unsigned long ptr_poison[GEN_OBJ_ID_TYPES] __read_mostly;
+
+unsigned long gen_object_id(void *ptr, int type)
+{
+	if (!ptr)
+		return 0;
+
+	BUG_ON(type >= GEN_OBJ_ID_TYPES);
+	WARN_ON_ONCE(ptr_poison[type] == 0);
+
+	return ((unsigned long)ptr) ^ ptr_poison[type];
+}
+
+static int gen_object_poison_init(void)
+{
+	int i;
+
+	for (i = 0; i < GEN_OBJ_ID_TYPES; i++)
+		get_random_bytes(&ptr_poison[i], sizeof(unsigned long));
+
+	return 0;
+}
+
+late_initcall(gen_object_poison_init);
+#endif
-- 
1.5.5.6

[PATCH 2/4] proc: Show namespaces IDs in /proc/pid/ns/* files

[Pavel Emelyanov]

Signed-off-by: Pavel Emelyanov <xemul@parallels.com>

---
 fs/proc/namespaces.c |   12 ++++++++++++
 include/linux/mm.h   |    1 +
 2 files changed, 13 insertions(+), 0 deletions(-)

diff --git a/fs/proc/namespaces.c b/fs/proc/namespaces.c
index be177f7..48c64ab 100644
--- a/fs/proc/namespaces.c
+++ b/fs/proc/namespaces.c
@@ -27,8 +27,20 @@ static const struct proc_ns_operations *ns_entries[] = {
 #endif
 };
 
+static ssize_t proc_ns_read(struct file *file, char __user *buf,
+				      size_t len, loff_t *ppos)
+{
+	char tmp[32];
+	struct proc_inode *ei = PROC_I(file->f_dentry->d_inode);
+
+	snprintf(tmp, sizeof(tmp), "id:\t%lu\n",
+			gen_object_id(ei->ns, GEN_OBJ_ID_NS));
+	return simple_read_from_buffer(buf, len, ppos, tmp, strlen(tmp));
+}
+
 static const struct file_operations ns_file_operations = {
 	.llseek		= no_llseek,
+	.read		= proc_ns_read,
 };
 
 static struct dentry *proc_ns_instantiate(struct inode *dir,
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 80ea327..cd4d727 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -1628,6 +1628,7 @@ extern void copy_user_huge_page(struct page *dst, struct page *src,
 #endif /* CONFIG_TRANSPARENT_HUGEPAGE || CONFIG_HUGETLBFS */
 
 enum {
+	GEN_OBJ_ID_NS,
 	GEN_OBJ_ID_TYPES,
 };
 
-- 
1.5.5.6

[PATCH 3/4] proc: Show open file ID in /proc/pid/fdinfo/*

[Pavel Emelyanov]

Signed-off-by: Pavel Emelyanov <xemul@parallels.com>

---
 fs/proc/base.c     |    6 ++++--
 include/linux/mm.h |    1 +
 2 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/fs/proc/base.c b/fs/proc/base.c
index 5eb0206..cb3e34c 100644
--- a/fs/proc/base.c
+++ b/fs/proc/base.c
@@ -1934,9 +1934,11 @@ static int proc_fd_info(struct inode *inode, struct path *path, char *info)
 			if (info)
 				snprintf(info, PROC_FDINFO_MAX,
 					 "pos:\t%lli\n"
-					 "flags:\t0%o\n",
+					 "flags:\t0%o\n"
+					 "id:\t%lu\n",
 					 (long long) file->f_pos,
-					 f_flags);
+					 f_flags,
+					 gen_object_id(file, GEN_OBJ_ID_FILE));
 			spin_unlock(&files->file_lock);
 			put_files_struct(files);
 			return 0;
diff --git a/include/linux/mm.h b/include/linux/mm.h
index cd4d727..caa42ca 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -1629,6 +1629,7 @@ extern void copy_user_huge_page(struct page *dst, struct page *src,
 
 enum {
 	GEN_OBJ_ID_NS,
+	GEN_OBJ_ID_FILE,
 	GEN_OBJ_ID_TYPES,
 };
 
-- 
1.5.5.6

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Andrew Morton]

On Thu, 17 Nov 2011 13:55:33 +0400
Pavel Emelyanov <xemul@parallels.com> wrote:

> While doing the checkpoint-restore in the userspace one need to determine
> whether various kernel objects (like mm_struct-s of file_struct-s) are shared
> between tasks and restore this state.
> 
> The 2nd step can for now be solved by using respective CLONE_XXX flags and
> the unshare syscall, while there's currently no ways for solving the 1st one.
> 
> One of the ways for checking whether two tasks share e.g. an mm_struct is to
> provide some mm_struct ID of a task to its proc file. The best from the
> performance point of view ID is the object address in the kernel, but showing
> them to the userspace is not good for security reasons.
> 
> Thus the object address is XOR-ed with a "random" value of the same size and 
> then shown in proc. Providing this poison is not leaked into the userspace then
> ID seem to be safe. The objects for which the IDs are shown are:
> 
> * all namespaces living in /proc/pid/ns/
> * open files (shown in /proc/pid/fdinfo/)
> * objects, that can be shared with CLONE_XXX flags (except for namespaces)
> 
> Changes since
> v1: * Tejun worried about the single poison value was a weak side - leaking one
>       makes all the IDs vulnerable. To address this several poison values - one
>       per object type - are introduced. They are stored in a plain array. Tejun, 
>       is this enough from your POV, or you'd like to see them widely scattered 
>       over the memory?
>     * Pekka proposed to initialized poison values in the late_initcall callback
>     * ... and move the code to mm/util.c
> 
> Signed-off-by: Pavel Emelyanov <xemul@parallels.com>

It doesn't *sound* terribly secure.  There might be clever ways in
which userspace can determine the secret mask, dunno.  We should ask
evil-minded security people to review this proposal.

Why not simply use a sequence number, increment it each time we create
an mm_struct?  On could use an idr tree to prevent duplicates but it
would be simpler and sufficient to make it 64-bit and we never have to
worry about wraparound causing duplicates.

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Pavel Emelyanov]

>> One of the ways for checking whether two tasks share e.g. an mm_struct is to
>> provide some mm_struct ID of a task to its proc file. The best from the
>> performance point of view ID is the object address in the kernel, but showing
>> them to the userspace is not good for security reasons.
>>
>> Thus the object address is XOR-ed with a "random" value of the same size and 
>> then shown in proc. Providing this poison is not leaked into the userspace then
>> ID seem to be safe. The objects for which the IDs are shown are:
>>
>> * all namespaces living in /proc/pid/ns/
>> * open files (shown in /proc/pid/fdinfo/)
>> * objects, that can be shared with CLONE_XXX flags (except for namespaces)
>> 
>> Signed-off-by: Pavel Emelyanov <xemul@parallels.com>
> 
> It doesn't *sound* terribly secure.  There might be clever ways in
> which userspace can determine the secret mask, dunno.  We should ask
> evil-minded security people to review this proposal.

Can you please propose some particular persons we should put in Cc for this thread?

> Why not simply use a sequence number, increment it each time we create
> an mm_struct?  On could use an idr tree to prevent duplicates but it
> would be simpler and sufficient to make it 64-bit and we never have to
> worry about wraparound causing duplicates.

IDR is not OK for me, since we'll have to call it on every fork() thus penalizing
its performance. 64bit increasing numbers are perfectly fine with me (I did this
in the 1st proposal, but put the ID on slub to save space - 64bits per page, not per
object).

But I have one question regarding storing these long IDs per-object. Are we OK with
adding 64-bit field on *all* the structures we need for this? I'm mostly worried 
about these small ones like sem_undo_list and fs_struct.

Thanks,
Pavel

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Andrew Morton]

On Fri, 18 Nov 2011 13:24:58 +0400
Pavel Emelyanov <xemul@parallels.com> wrote:

> >> One of the ways for checking whether two tasks share e.g. an mm_struct is to
> >> provide some mm_struct ID of a task to its proc file. The best from the
> >> performance point of view ID is the object address in the kernel, but showing
> >> them to the userspace is not good for security reasons.
> >>
> >> Thus the object address is XOR-ed with a "random" value of the same size and 
> >> then shown in proc. Providing this poison is not leaked into the userspace then
> >> ID seem to be safe. The objects for which the IDs are shown are:
> >>
> >> * all namespaces living in /proc/pid/ns/
> >> * open files (shown in /proc/pid/fdinfo/)
> >> * objects, that can be shared with CLONE_XXX flags (except for namespaces)
> >> 
> >> Signed-off-by: Pavel Emelyanov <xemul@parallels.com>
> > 
> > It doesn't *sound* terribly secure.  There might be clever ways in
> > which userspace can determine the secret mask, dunno.  We should ask
> > evil-minded security people to review this proposal.
> 
> Can you please propose some particular persons we should put in Cc for this thread?

Perhaps Vasily could review this proposal for us?

> > Why not simply use a sequence number, increment it each time we create
> > an mm_struct?  On could use an idr tree to prevent duplicates but it
> > would be simpler and sufficient to make it 64-bit and we never have to
> > worry about wraparound causing duplicates.
> 
> IDR is not OK for me, since we'll have to call it on every fork() thus penalizing
> its performance.

fork() is a pretty heavyweight operation so that won't hurt noticeably.
However it sounds like you're presented with the same issue for more
frequently-created objects.

> 64bit increasing numbers are perfectly fine with me (I did this
> in the 1st proposal, but put the ID on slub to save space - 64bits per page, not per
> object).
> 
> But I have one question regarding storing these long IDs per-object. Are we OK with
> adding 64-bit field on *all* the structures we need for this? I'm mostly worried 
> about these small ones like sem_undo_list and fs_struct.

OK.  Using the object's kernel virtual address is certainly very
attractive.

It is the case that we're causing difficulty with this longer-term plan
to make c/r available to unprivileged processes?  Because it's OK to
expose kernel addresses to CAP_SYS_ADMIN (or similar) tasks (isn't it?).

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Cyrill Gorcunov]

On Fri, Nov 18, 2011 at 11:07:16AM -0800, Andrew Morton wrote:
...
> 
> OK.  Using the object's kernel virtual address is certainly very
> attractive.
> 
> It is the case that we're causing difficulty with this longer-term plan
> to make c/r available to unprivileged processes?  Because it's OK to
> expose kernel addresses to CAP_SYS_ADMIN (or similar) tasks (isn't it?).
> 

Actually the address is not exposed in open-form but rather xor'ed with
a random number, still from security pov it's not clear if it's really useful
for attacker to obtain inverted low bits of the former random number (which
might happen on aligned addresses).

	Cyrill

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Andrew Morton]

On Sat, 19 Nov 2011 00:03:42 +0400
Cyrill Gorcunov <gorcunov@gmail.com> wrote:

> On Fri, Nov 18, 2011 at 11:07:16AM -0800, Andrew Morton wrote:
> ...
> > 
> > OK.  Using the object's kernel virtual address is certainly very
> > attractive.
> > 
> > It is the case that we're causing difficulty with this longer-term plan
> > to make c/r available to unprivileged processes?  Because it's OK to
> > expose kernel addresses to CAP_SYS_ADMIN (or similar) tasks (isn't it?).
> > 
> 
> Actually the address is not exposed in open-form but rather xor'ed with
> a random number, still from security pov it's not clear if it's really useful
> for attacker to obtain inverted low bits of the former random number (which
> might happen on aligned addresses).
> 

Of course.  But

a) I'm not sure that this scheme actually protects the kernel
   addresses - there may be way in which cunning userspace can work out
   the random mask.

b) If we can export these addresses only to CAP_SYS_ADMIN tasks then
   we don't need to obfuscate them anyway.

   Which takes me back to again asking: why not make c/r root-only? 
   And provide non-root access via a carefully-written setuid
   front-end?

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Cyrill Gorcunov]

On Fri, Nov 18, 2011 at 12:37:28PM -0800, Andrew Morton wrote:
...
> > 
> > Actually the address is not exposed in open-form but rather xor'ed with
> > a random number, still from security pov it's not clear if it's really useful
> > for attacker to obtain inverted low bits of the former random number (which
> > might happen on aligned addresses).
> > 
> 
> Of course.  But
> 
> a) I'm not sure that this scheme actually protects the kernel
>    addresses - there may be way in which cunning userspace can work out
>    the random mask.
> 

Well, in case of hw-rng it should not be that easy, still of course
there is no 100% guarantee that there is absolutely no way to predict
this mask (espec since it's generated once at lives here forever). But
whatever makes attacker life harder -- is a good thing. After all we might
simply take some hash on kernel address here (such as sha256) since it's
not a time-critical operation and as far as I know collision is not found
for it yet (??).

> b) If we can export these addresses only to CAP_SYS_ADMIN tasks then
>    we don't need to obfuscate them anyway.
> 
>    Which takes me back to again asking: why not make c/r root-only?
>    And provide non-root access via a carefully-written setuid
>    front-end?
> 

I think non-root approach is a win in a long term (even if it requires
some new CAP_ for that). The less root priviledge needed -- then better.
Having it root-only is easier of course and solves the problem of masking
kernel addresses from untrusted user-space agents, but still. Pavel, what
do you think about root-only?

	Cyrill

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Pekka Enberg]

On Fri, Nov 18, 2011 at 11:03 PM, Cyrill Gorcunov <gorcunov@gmail.com> wrote:
>> Of course.  But
>>
>> a) I'm not sure that this scheme actually protects the kernel
>>    addresses - there may be way in which cunning userspace can work out
>>    the random mask.
>
> Well, in case of hw-rng it should not be that easy, still of course
> there is no 100% guarantee that there is absolutely no way to predict
> this mask (espec since it's generated once at lives here forever). But
> whatever makes attacker life harder -- is a good thing. After all we might
> simply take some hash on kernel address here (such as sha256) since it's
> not a time-critical operation and as far as I know collision is not found
> for it yet (??).

XOR cipher is very easy to crack with frequency analysis. I'd also
consider using SHA256 or similar hash for this.

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Kyle Moffett]

On Fri, Nov 18, 2011 at 16:09, Pekka Enberg <penberg@kernel.org> wrote:
> On Fri, Nov 18, 2011 at 11:03 PM, Cyrill Gorcunov <gorcunov@gmail.com> wrote:
>>> Of course.  But
>>>
>>> a) I'm not sure that this scheme actually protects the kernel
>>>    addresses - there may be way in which cunning userspace can work out
>>>    the random mask.
>>
>> Well, in case of hw-rng it should not be that easy, still of course
>> there is no 100% guarantee that there is absolutely no way to predict
>> this mask (espec since it's generated once at lives here forever). But
>> whatever makes attacker life harder -- is a good thing. After all we might
>> simply take some hash on kernel address here (such as sha256) since it's
>> not a time-critical operation and as far as I know collision is not found
>> for it yet (??).
>
> XOR cipher is very easy to crack with frequency analysis. I'd also
> consider using SHA256 or similar hash for this.

Some of the bits you don't even need to guess.  On 32-bit PPC, for
example, all kernel addresses have the top two bits set (0xC0000000 -
0xFFFFFFFF) and some of that space is reserved for virtual maps and
kernel code.  Additionally, all your significant datastructures are
probably allocated with kmalloc() and have 16-byte alignment or more,
so you only have maybe 24 or 25 bits (out of 32) with relevant
randomness.

Even then I'm sure you can brute-force that primitive XOR masking
pretty easily.  Just use memory pressure to get some large contiguous
chunks of free memory and then create lots of the relevant
datastructures... which will occur in linearly ascending order!
Examine the values from each "cookie" after large numbers of
allocations, if the highest bit to change was bit 20 and almost all of
the bits underneath it flip at the same time, then you know the real
value of bit X just changed from a 0 to a 1, so you know what the XOR
value for that bit is.

The #1 rule of one-time pads is never use it for more than one thing,
and you use it here for every object in the system.

If you actually want to be able to compare uniqueness without exposing
anything vulnerable to various kinds of guessing, you should generate
a random 64-bit value for each class of object and then use a proper
cryptographic hash function on it:
  crypto_hash(concat(object_ptr, random_value))

Even given the best possible practical attacks against SHA1 or MD5
today both still provides more than enough security to prevent someone
from guessing "object_ptr" in less than an absurd amount of time.

Cheers,
Kyle Moffett

-- 
Curious about my work on the Debian powerpcspe port?
I'm keeping a blog here: http://pureperl.blogspot.com/

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Tejun Heo]

Hello,

On Fri, Nov 18, 2011 at 05:10:37PM -0500, Kyle Moffett wrote:
> The #1 rule of one-time pads is never use it for more than one thing,
> and you use it here for every object in the system.

The new version is using different poison for different types of
objects.

> If you actually want to be able to compare uniqueness without exposing
> anything vulnerable to various kinds of guessing, you should generate
> a random 64-bit value for each class of object and then use a proper
> cryptographic hash function on it:
>   crypto_hash(concat(object_ptr, random_value))
> 
> Even given the best possible practical attacks against SHA1 or MD5
> today both still provides more than enough security to prevent someone
> from guessing "object_ptr" in less than an absurd amount of time.

So, per-type poison + crypto hash, it is then.

Thank you very much.

-- 
tejun

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Kyle Moffett]

On Fri, Nov 18, 2011 at 18:46, Tejun Heo <tj@kernel.org> wrote:
> Hello,
>
> On Fri, Nov 18, 2011 at 05:10:37PM -0500, Kyle Moffett wrote:
>> The #1 rule of one-time pads is never use it for more than one thing,
>> and you use it here for every object in the system.
>
> The new version is using different poison for different types of
> objects.

Even still, if you use a one-time pad (IE: XOR with a random data
value) to obscure more than exactly 1 object total, ever, all of its
security properties are null and void.


>> If you actually want to be able to compare uniqueness without exposing
>> anything vulnerable to various kinds of guessing, you should generate
>> a random 64-bit value for each class of object and then use a proper
>> cryptographic hash function on it:
>>   crypto_hash(concat(object_ptr, random_value))
>>
>> Even given the best possible practical attacks against SHA1 or MD5
>> today both still provides more than enough security to prevent someone
>> from guessing "object_ptr" in less than an absurd amount of time.
>
> So, per-type poison + crypto hash, it is then.

Yes.  I haven't thought through whether or not you would ever care
about a system giving out the same number for two different kinds of
object.  The only possible vulnerability I can think of would be if
the kernel had a use-after-free bug... You could allocate and free a
bunch of the vulnerable objects and use this data-structure-ID system
to find an allocated data-structure of a different type which matches
up with one of the used-after-freed ones.  Then in theory you could
compromise something, I suppose.

Sort of an off-the-wall scenario, I will admit.

The per-type random value is certainly a safe bet and should have zero
actual impact on performance.  Good luck!

Cheers,
Kyle Moffett

-- 
Curious about my work on the Debian powerpcspe port?
I'm keeping a blog here: http://pureperl.blogspot.com/

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Cyrill Gorcunov]

On Fri, Nov 18, 2011 at 08:09:12PM -0500, Kyle Moffett wrote:
...
> >
> > The new version is using different poison for different types of
> > objects.
> 
> Even still, if you use a one-time pad (IE: XOR with a random data
> value) to obscure more than exactly 1 object total, ever, all of its
> security properties are null and void.
>

True. It's not one-time pads there.

> 
> >> If you actually want to be able to compare uniqueness without exposing
> >> anything vulnerable to various kinds of guessing, you should generate
> >> a random 64-bit value for each class of object and then use a proper
> >> cryptographic hash function on it:
> >>   crypto_hash(concat(object_ptr, random_value))
> >>
> >> Even given the best possible practical attacks against SHA1 or MD5
> >> today both still provides more than enough security to prevent someone
> >> from guessing "object_ptr" in less than an absurd amount of time.
> >
> > So, per-type poison + crypto hash, it is then.
> 
> Yes.  I haven't thought through whether or not you would ever care
> about a system giving out the same number for two different kinds of
> object.  The only possible vulnerability I can think of would be if
> the kernel had a use-after-free bug... You could allocate and free a
> bunch of the vulnerable objects and use this data-structure-ID system
> to find an allocated data-structure of a different type which matches
> up with one of the used-after-freed ones.  Then in theory you could
> compromise something, I suppose.
> 
> Sort of an off-the-wall scenario, I will admit.
> 
> The per-type random value is certainly a safe bet and should have zero
> actual impact on performance.  Good luck!
> 

Thanks for all comments Kyle! Of course address allocation specifics with
simple xor wont give us enough obscurity here. If we stick with root-only
approach then we don't need this scheme at all but could expose plain
addresses. I'm waiting for Pavel's comment on such approach.

	Cyrill

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Matt Helsley]

On Sat, Nov 19, 2011 at 01:03:22AM +0400, Cyrill Gorcunov wrote:
> On Fri, Nov 18, 2011 at 12:37:28PM -0800, Andrew Morton wrote:
> ...
> > > 
> > > Actually the address is not exposed in open-form but rather xor'ed with
> > > a random number, still from security pov it's not clear if it's really useful
> > > for attacker to obtain inverted low bits of the former random number (which
> > > might happen on aligned addresses).
> > > 
> > 
> > Of course.  But
> > 
> > a) I'm not sure that this scheme actually protects the kernel
> >    addresses - there may be way in which cunning userspace can work out
> >    the random mask.
> > 
> 
> Well, in case of hw-rng it should not be that easy, still of course
> there is no 100% guarantee that there is absolutely no way to predict
> this mask (espec since it's generated once at lives here forever). But

The random number itself could be of the best quality and the obfuscation
could still be completely broken from a security standpoint. Put another
way, we don't need to attack the method the random number was generated.
We could probably utilize information we have about how the addresses
themselves are generated.

That said, this is pure speculation on my part. Getting someone with real
skill at attacking cryptographic systems to analyze the idea would be the
right way to go if you still want to pursue this scheme.

> whatever makes attacker life harder -- is a good thing. After all we might
> simply take some hash on kernel address here (such as sha256) since it's
> not a time-critical operation and as far as I know collision is not found
> for it yet (??).

Yes, cryptographic hashing seems much better than a highly suspect ad-hoc
scheme which has barely been analyzed.

> 
> > b) If we can export these addresses only to CAP_SYS_ADMIN tasks then
> >    we don't need to obfuscate them anyway.
> > 
> >    Which takes me back to again asking: why not make c/r root-only?
> >    And provide non-root access via a carefully-written setuid
> >    front-end?
> > 
> 
> I think non-root approach is a win in a long term (even if it requires

You could go with the root approach for now and make things more
permissive later.

Cheers,
	-Matt

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Cyrill Gorcunov]

On Fri, Nov 18, 2011 at 03:38:40PM -0800, Matt Helsley wrote:
...
> > 
> > Well, in case of hw-rng it should not be that easy, still of course
> > there is no 100% guarantee that there is absolutely no way to predict
> > this mask (espec since it's generated once at lives here forever). But
> 
> The random number itself could be of the best quality and the obfuscation
> could still be completely broken from a security standpoint. Put another
> way, we don't need to attack the method the random number was generated.
> We could probably utilize information we have about how the addresses
> themselves are generated.
> 

Agreed.

> > whatever makes attacker life harder -- is a good thing. After all we might
> > simply take some hash on kernel address here (such as sha256) since it's
> > not a time-critical operation and as far as I know collision is not found
> > for it yet (??).
> 
> Yes, cryptographic hashing seems much better than a highly suspect ad-hoc
> scheme which has barely been analyzed.
>

I'm surely fine with using crypto-hashes here.

> > 
> > > b) If we can export these addresses only to CAP_SYS_ADMIN tasks then
> > >    we don't need to obfuscate them anyway.
> > > 
> > >    Which takes me back to again asking: why not make c/r root-only?
> > >    And provide non-root access via a carefully-written setuid
> > >    front-end?
> > > 
> > 
> > I think non-root approach is a win in a long term (even if it requires
> 
> You could go with the root approach for now and make things more
> permissive later.
> 

Root-only makes all things easier, but I fear if we don't start with
non-root from the very beginning it'll remain root-only forever ;)

	Cyrill

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Vasiliy Kulikov]

Hello,

On Fri, Nov 18, 2011 at 11:07 -0800, Andrew Morton wrote:
> On Fri, 18 Nov 2011 13:24:58 +0400
> Pavel Emelyanov <xemul@parallels.com> wrote:
> 
> > >> One of the ways for checking whether two tasks share e.g. an mm_struct is to
> > >> provide some mm_struct ID of a task to its proc file. The best from the
> > >> performance point of view ID is the object address in the kernel, but showing
> > >> them to the userspace is not good for security reasons.
> > >>
> > >> Thus the object address is XOR-ed with a "random" value of the same size and 
> > >> then shown in proc. Providing this poison is not leaked into the userspace then
> > >> ID seem to be safe. The objects for which the IDs are shown are:
> > >>
> > >> * all namespaces living in /proc/pid/ns/
> > >> * open files (shown in /proc/pid/fdinfo/)
> > >> * objects, that can be shared with CLONE_XXX flags (except for namespaces)
> > >> 
> > >> Signed-off-by: Pavel Emelyanov <xemul@parallels.com>
> > > 
> > > It doesn't *sound* terribly secure.  There might be clever ways in
> > > which userspace can determine the secret mask, dunno.  We should ask
> > > evil-minded security people to review this proposal.
> > 
> > Can you please propose some particular persons we should put in Cc for this thread?
> 
> Perhaps Vasily could review this proposal for us?

Some thoughts:

1) Objects created early in the boot process usually has predictable
addresses.  If an attacker knows the address of one such object, he may
learn the cookie.

2) Lower bits of this cookie don't make sense as object addresses are
aligned.

3) I'm afraid addresses of objects of different types which were
kmalloc'ed still depend on each other.  I.e:

    OBJ1 is type A
    OBJ2 is type B

    OBJ2 = OBJ1 + 0x20

    (OBJ1^COOKIE1) ^ (OBJ2^COOKIE2) =
    = (COOKIE1^COOKIE2) ^ (OBJ1^(OBJ1+0x20)) = (COOKIE1^COOKIE2)^(0x20+Carry_bits)

3) I'm afraid the weakest property of XOR can be used by an attacker:

(OBJ1^COOKIE) ^ (OBJ2^COOKIE) = OBJ1^OBJ2


As was said previously, one could create multiple objects which have
linearly increasing addresses and learn cookie lower bits.


Doing something like hash(cookie1 ++ obj ++ cookie) would leak only the
equation of two objects, but it can be still dangerous - learn hashes of
(a) objects created at boot time (their addresses are known) and (b)
some objects, which allocation scheme is known (i.e. we know
kmem_cache_alloc() gives us specific addresses with high probability),
and then compare the hashes against other objects after (a) and (b)
objects are kfree'd.


What is the highest timeframe which must maintain the property of unique
ids?  Is it the whole system lifetime or probably [dump start; dump
end] and we can change the cookie many times?  Can we probably shorten
the time even?  Can we ensure that during this timeframe no new kernel
objects will be created (unrealistic, but would be great)?

Also, I didn't understand from the quoted text who will use it - only
the dumper or this interface is exposed to all userspace processes and
anybody may learn hash(&kern_obj) for any kern_obj he may reference?

Thanks,

-- 
Vasiliy Kulikov
http://www.openwall.com - bringing security into open computing environments

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Vasiliy Kulikov]

On Sat, Nov 19, 2011 at 11:57 +0400, Vasiliy Kulikov wrote:
> Doing something like hash(cookie1 ++ obj ++ cookie) would leak only the
> equation of two objects, but it can be still dangerous - learn hashes of
> (a) objects created at boot time (their addresses are known) and (b)
> some objects, which allocation scheme is known (i.e. we know
> kmem_cache_alloc() gives us specific addresses with high probability),
> and then compare the hashes against other objects after (a) and (b)
> objects are kfree'd.
> 
> 
> What is the highest timeframe which must maintain the property of unique
> ids?  Is it the whole system lifetime or probably [dump start; dump
> end] and we can change the cookie many times?  Can we probably shorten
> the time even?  Can we ensure that during this timeframe no new kernel
> objects will be created (unrealistic, but would be great)?
> 
> Also, I didn't understand from the quoted text who will use it - only
> the dumper or this interface is exposed to all userspace processes and
> anybody may learn hash(&kern_obj) for any kern_obj he may reference?

Also, if one should have an ability to learn IDs of specific object
types and the set of types is very limited, it's much safer to have one
increasing u64 counter for each created object of one of these types.
The exposed to userspace data will be:

    ID = hash(counter ^ cookie)

    cookie is generated at boot time, once.  counter is a single
    variable, one for all exposed kernel object types.

ID will be unpredictable if hash() is cryptographically secure, and
counter is not duplicated.  So, for each newly created object the ID is
the new random value, which is unique and says nothing to userspace about
either kernel object addresses or the counter itself.

The cost:

1) counter storing for each kernel object exposed through this interface.

2) object creation will be slowed down by hash().


Also, one thought - is it safe to say two kernel objects are the same to
userspace? :)  I don't see anything obviously dangerous, though.

Thanks,

-- 
Vasiliy Kulikov
http://www.openwall.com - bringing security into open computing environments

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Vasiliy Kulikov]

On Sat, Nov 19, 2011 at 12:10 +0400, Vasiliy Kulikov wrote:
> Also, if one should have an ability to learn IDs of specific object
> types and the set of types is very limited, it's much safer to have one
> increasing u64 counter for each created object of one of these types.
> The exposed to userspace data will be:
> 
>     ID = hash(counter ^ cookie)

Even hash(counter) without any cookie and counter is randomly generated at boot time.


-- 
Vasiliy Kulikov
http://www.openwall.com - bringing security into open computing environments

Re: [PATCH v2 0/4] Checkpoint/Restore: Show in proc IDs of objects that can be shared between tasks

[Cyrill Gorcunov]

On Sat, Nov 19, 2011 at 12:10:12PM +0400, Vasiliy Kulikov wrote:
> On Sat, Nov 19, 2011 at 11:57 +0400, Vasiliy Kulikov wrote:
> > Doing something like hash(cookie1 ++ obj ++ cookie) would leak only the
> > equation of two objects, but it can be still dangerous - learn hashes of
> > (a) objects created at boot time (their addresses are known) and (b)
> > some objects, which allocation scheme is known (i.e. we know
> > kmem_cache_alloc() gives us specific addresses with high probability),
> > and then compare the hashes against other objects after (a) and (b)
> > objects are kfree'd.
> > 

First of all, thanks a *huge* for comments Vasiliy! Yes, agreed that plain
single xor is not sufficient here.

> > 
> > What is the highest timeframe which must maintain the property of unique
> > ids?  Is it the whole system lifetime or probably [dump start; dump
> > end] and we can change the cookie many times?  Can we probably shorten

Yes, dump-start/dump-end is a mininum timeframe.

> > the time even?  Can we ensure that during this timeframe no new kernel
> > objects will be created (unrealistic, but would be great)?
> > 

We might use PT_SEIZED as such flag and don't allow to allocate new kernel
objects but it will bring too much complexity into kernel code I think,
which is not what we want eventually ;)

> > Also, I didn't understand from the quoted text who will use it - only
> > the dumper or this interface is exposed to all userspace processes and
> > anybody may learn hash(&kern_obj) for any kern_obj he may reference?
> 

It's limited to /proc/$pid/

> Also, if one should have an ability to learn IDs of specific object
> types and the set of types is very limited, it's much safer to have one
> increasing u64 counter for each created object of one of these types.
> The exposed to userspace data will be:
> 
>     ID = hash(counter ^ cookie)
> 
>     cookie is generated at boot time, once.  counter is a single
>     variable, one for all exposed kernel object types.
> 
> ID will be unpredictable if hash() is cryptographically secure, and
> counter is not duplicated.  So, for each newly created object the ID is
> the new random value, which is unique and says nothing to userspace about
> either kernel object addresses or the counter itself.
> 
> The cost:
> 
> 1) counter storing for each kernel object exposed through this interface.
> 

Yes, this is main concern.

> 2) object creation will be slowed down by hash().
> 

This is not that important I think, since it's not a time-critical operation.

> Also, one thought - is it safe to say two kernel objects are the same to
> userspace? :)  I don't see anything obviously dangerous, though.
> 

	Cyrill