authentication / encryption key retention

Hi Linus,

I'm looking at implementing authentication token and encryption key retention for the 2.7 kernel again.

I can implement keyrings and sequences of keyrings, but the problem I'm not sure about it how to attach them to a process. Are you willing to advise me on my ideas?

I think the best way is to have a stack of "personae" attached to a process. Each persona would then have an identity (UID) and a sequence of keys.

Personae would be acquired by way of SUID programs, AF_UNIX credential passing, and directly by way of syscalls.

The top persona on the stack would define what the process looked like to other processes - controlling access to the process by signal and ptrace.

One of the personae on the stack would be elected to be the "effective" one - the one that gets attached to newly opened files, and is used to specify access to other processes for signal and ptrace.

Syscalls would be provided to reorder and modify the contents of the persona stack.

Each struct file would have a pointer to the persona that contains the identity and keys governing access to the underlying data.

Syscalls would also be provided to subscribe a persona to new keyrings (persona would be shared as long as possible, but would be forked on modification).

Each Keyring would contain a set of distinguishable keys of various types, eg:
UNIX groups list, kerberos TGT for a particular domain, encryption key, process access key. Each keyring would have an ACL that governs which UIDs/GIDs are allowed to subscribe to it or modify it. Whilst keyrings would be visible through sysfs, they would not be persistent once no longer in use.

However, all this makes for a few problems:

(1) setuid()

This can be made to manipulate the personae stack in various ways, but it'd be hard to get it'd work exactly as before.

This is especially true with respect to GIDs. I think I'd have to attach a GID to each persona, however this would mean these UID manipulating syscalls would _also_ manipulate GIDs.

(2) setreuid(), setresuid()

As with setuid(), except that these would then manipulate multiple personae simultaneously, which probably won't be a problem - except if the "effective" UID is not a member of the stack...

The top two entries on the stack can be viewed as real (TOS) and saved (2OS) UIDs.

(3) setgid()

GIDs would no longer be independent of UIDs, so this would change the GID on both the TOS and the effective persona.

(4) setregid(), setresgid()

These give the worst problems. I could duplicate personae to make sure I can store all the GIDs if they are all different, but that then has consequences for setre*uid().

(5) setfsuid()

This would then select the first persona on the stack that matches the UID, but what if there is no match? Should it then create a new persona with a different UID?

What I don't know is how attached we are to the current interface.

David

I don't know if UID helps much. What would you use it for?

The UID is already used to index into the "struct user" thing, and that can (and probably should) contain a set of keys associated with that user. That implies that we _already_ have a UID -> set-of-key translation, without actually mixing the UID with the keys themselves.

This is what we do have UID's for, and changing that would break a lot of existing security-conscious programs potentially very badly. Another reason not to mix up the uid/key concepts.

You really want the "file open" part to be the thing that decides which key or bunch of keys are relevant to that file open. And I don't think it would have anything to do with a persona: a file open will care about the particular keys needed for that connection/filesystem/file, not about "persons".

While a person will want to have keys associated with multiple _different_ filesystems or connections.

So there is no 1:1 relationship there.

So my suggestion boils down to:

- do _not_ mix up current uid/gid issues with key management. It will only cause untold pain for programs that expect to care only about uids.

So uid/group changes would happen exactly like they do now: and they would result only in _purely_ uid/gid-related security elevation.

Of course, since we can have uid/gid-specific key bunches (ie the "struct user" thing), when you have a setuid program that switches to another user, you may implicitly get access to that users keys. But that is only a direct result of the setuid itself, and doesn't change the security model of setuid. It's 100% equivalent.

- For "group of key management", I do think you want to have your "persona", but not because you want to associate them directly with uid/gid issues, but because you would need to have some mechanism to pass many unrelated keys around, without having to pass around _all_ your own keys.

And also, probably more importantly, it would also be the way to invalidate a bunch of keys (ie the security deamon that gave you a particular bucket because you identified yourself to it can invalidate the whole bucket without actually having to invalidate each key separately).

So it would be just a "bucket of keys" you got from somewhere. Maybe you get a couple of buckets as part of your login, and maybe you have to do some strong authentication to a security server to get another "bucket".

But "two buckets" would not make "one larger bucket".

My personal favourite would actually be to allow "buckets of buckets of [buckets of] keys". The reason you may want this is:

- it must _not_ be possible to read out a key just because you have access to it. In networked filesystems, keys don't have any specific relevance (they're just random bits), but in many other cases they _do_ have special relevance (ie they could be somebody's private key that he gave you temporary access to).

- this means that once you get a key or a "bucket of keys", you can't just re-create it. The only thing you can do is to create another reference to it. So if you want to pass off the keys you got to some third party, together with a few new keys of your own, you'd really need to create a new "bucket" that contains a pointer to the old bucket along with the new keys.

(disallowing recursive buckets is an issue, but is pretty trivial)

So the data structures could be something really trivial, like

	struct key_bucket {
		int type;	/* bucket or individual key */
		atomic_t count;	/* reference count */
		int valid;
		char *name;	/* identifier of creator of this bucket */
		union {
			struct key *key;
			struct bucket *bucket;
		}
	};

	struct key {
		int type;
		atomic_t count;
		const char *description;
		const char *blob;
	};

	struct bucket {
		int entries;
		struct key_bucket *list[];
	};

and now "struct key_bucket" can be just a single key, or it can be a bucket of single keys, or it can be a bucket of mixed keys/buckets.

(Yeah, the contents of "struct key" are totally made-up. The "blob" is the content-dependent part of the key, but they will obviusly depend on what kind of key it is, so you need some higher-level description of the key so that the _users_ of the key can search for a key they are interested in.)

And notice how you can invalidate an arbitrary bucket by just marking it "invalid" - that doesn't invalidate any of the keys contained within, but it just means that the key_bucket cannot be searched/looked up any more, and thus it's effectively disabled.

What I really care about is:

- the data structure/mechanism should be totally agnostic about the kind of keys you hide in there. The only thing that should be contained in the keys/buckets (apart from the key blob itself) is enough meta-data that we can have an a sane "look up keys of type xxx" operation.

- you do _not_ depend on "read the keys, duplicate them, write them out again as a new bunch" as a maintenance operation. That does _not_work_ for keys that are supposed to be private. If I give somebody else my key, that does not mean that he can read it. He can use it, but he can't make a copy.

With the straw-man bucket-of-buckets proposals, you can now endow _any_ data structure with any random collection of keys by just adding a

	struct key_bucket *keys;

entry to it.

(And I'm carefully staying out of guessing what functions we want to have to iterate over all keys of a specific type. But it doesn't look impossible).

Linus

Sorry, I was using UID and user_struct interchangably.

It is also an access key and an identification token. It is used for some local filesystems. It is also used to drive access control on /proc/<pid>/ and for signal and ptrace targetting.

I agree, but... each UID brings with it a set of keys, so they are linked at least a little.

Agreed. But there are some issues:

(1) Which key does it pick? There needs to be some ordering on the keys attached to a process, and it must be possible for the process to either rearrange these keys or to have a say in which key file->open() selects.

Remember, keys can come from three sources potentially:

(*) SUID programs
(*) UID default
(*) GID default
(*) credential passing
(*) manual subscription

Which one you want to apply to the opening of a file will vary.

(2) Key retirement. If file->open() selects a key that subsequently gets retired, should the filesystem be able to select another key from the original set of keyrings? Or should it thenceforth return an error?

I think an argument can be made for the filesystem being allowed to build its own keyring in file->open() by filtering all the keys available to the parent process. When all those keys have been retired, it then returns an error.

UID, GID and groups would be kept in the keyring as three individual keys, if the filesystem required them.

(3) Memory. You've only got so much. Do you want every open() call to go and build a keyring containing a subset of a process's keys.

Except that the UID is also a key for some filesystems.

Fair enough. It'd be, as you say, an untold pain otherwise.

How about this? Taking your suggestion for nested keyrings, a process has a ring of private keyrings labelled uniquely within that process that define all the keys it currently has access to:

Keyring "_process.11374"
Keyring "_uid.4043" # UID default keyring
Keyring "_gid.100" # GID default keyring
Keyring "_groups" # GROUPS keyring
Keyring "_leant.0" # keyring acquired from another program
Keyring "KDE-dhowells1" # user specified keyring
Keyring "AFS-dhowells" # user specified keyring

Anything that changes the process's UID or GID (such as setuid()) substitutes alternative keyrings for "_uid*" and "_gid*", but without changing the ordering or the keyrings.

The UNIX groups list could then be replaced with a keyring containing GIDs and GID keyrings perhaps:

Keyring "_groups" # GROUPS keyring

    Keyring "_gid.4043"
      Key GID 4043		# undeletable key
      Key DES "/dev/hda5" "2d189a4891c8218f9248904"
      Key DES "/dev/hda6" "89052852098290423789042"
      Key DES "/dev/hda7" "08983847892323987243987"
    Keyring "_gid.4040"
      Key GID 4040
    Keyring "_gid.4041"
      Key GID 4041
    Keyring "_gid.4007"
      Key GID 4007

And then if, say, ext3_file_open() filtered these for its own nefarious purposes, you might end up with:

Keyring "_file"

    Key UID 4043
    Key GID 100
    Key GID 4043
    Key DES "/dev/hda5" "2d189a4891c8218f9248904"
    Key GID 4040
    Key GID 4041
    Key GID 4007

Attached to file->f_keyring.

Of course, that may rule out filtering keyrings in file->open() to build a private keyring for the FD.

The big problem with this is dealing with them without recursive functions, but I do like the idea.

Agreed (from userspace at least). However, you might want to be able to see the key descriptions if not the payload.

But you do need to be able to modify a bucket, at the very least by adding things to it, retiring it or retiring keys from within it. Also you need to be able to subscribe to it.

I think that each bucket will require an ACL, and possibly keys should have ACLs too.

The problem with that is you can't pass a subset, only a complete set. Hmmm... I think it ought to be possible to filter on description, but that the data should not ever return to userspace.

I like that.

Yes.

I think an ACL is a must (as I've said before). The ACL should provide the following rights:

(*) Subscribe to Keyring
(*) Enumerate
(*) Add keys
(*) Retire keys
(*) Retire Keyring
(*) Change ACL

And should be able to use either UID or GID as required.

If key ACLs are also to be used, they should have the following rights available:

(*) Use key
(*) Copy key to another keyring
(*) Retire key
(*) Read payload from userspace
(*) Change ACL

If keyrings are just special keys, then the two sets of rights can be merged.

Normally ACLs would be trivial - just give all rights to their owner, and nothing to anybody else. In the case of UID or GID default rings, the owner is UID or GID in question.

I wasn't advocating that userspace _should_ necessarily be allowed to read the payload of a key. If at all possible, then it should strictly be under the control of an ACL.

I also don't like the idea that you're suggesting, and wasn't suggesting it myself.

Okay... I'll have a look at implementing this.

Thanks,
David

I would think we can do this by just having a well-known search order. For example, if we just end up with a "tree of buckets", we just make the search order be depth-first, and you can this pick and choose which buckets you access first by just ordering how you add a new bucket.

But I think it ends up being a secondary issue, because _most_ of the time you're likely to have just one key that "fits the lock".

So I wouldn't worry about it _too_ much, at least until we have code that works and is used by multiple subsystems.

I think you have to return an error in the general case. You may have done actions with the key that are hard to just move over to another one.

Again, if that ends up being a real problem, maybe the solution is just "don't do that then". Or maybe the solution ends up being to have infrastructure to switch keys on the fly.

But don't overdesign. Start from a small set of basic requirments, and make a simple implementation. Go from there.

No, usually it would just search the keyring, and increment the reference count for the key it finds (or the whole bucket. Or a sub-bucket. Some subsystems might want to just say "I want it all" - it's the only sane thing to do if the subsystem really decides that it wants to be able to switch keys around on failure, I suspect).

Yes, but those filesystems will NOT use the "extended key" functionality at all.

It would be silly to make existing ext2 users use the new keys. They'll just use "uid" and "gid" like they always have been.

Purists go "hey, that's having two totally different mechanisms for the same thing - security". But sane people go "why complicate the issue unnecessarily".

I'd actually suggest keeping the uid/gid keyrings off the "process keyring".

So each process would have a a few different keyrings:

- the process-local one: "current->keyring"

- the UID-local one: either "current->fsuid->keyring" (ie maintaining a "fsuid" structure pointer over fsuid changes) or just having a hash function from "uid" -> "keyring"

- the group-local one: "current->group->keyring" or "gid" -> "keyring" hash function.

and they'd be all separate (they could have overlap, of course, but the difference is that this makes it very easy to change groups and uid's:
such changes would _not_ touch the "process-local" keys at all).

So part of the search order would be the order these are used in looking stuff up. My "obvious" order would be to do process-local first, then user-local, and finally group-local.

But some parts of the kernel might look at only the process-local keys ("does this process have rights to do that?") or look at other localities ("does this socket have the keys to do that?") entirely.

Yes. You definitely want to have an extended "id" program that allows you to see the descriptions and types.

No, you can certainly pass subsets too, by just having a "create a new bucket that contains these other buckets" (which you got from the lookup operation). You never see what the actual keys are, but each bucket and each key do have an ID field, so you can create buckets by reference that way.

Who not just make ACL's part of the "bucket of keys", but make them basically "conditional keys" (in the "type field", the same way we distinguish between buckets and keys). A conditional key is a key in itself, but it's a requirement thing: you can do this operation on the tree of keys only if you also have access to the non-conditional version of this key.

I think it would be a mistake to have _another_ level of keys/ACL's just to keep track of what keys you can modify. "Quid custodiet ipsos custodies?". Where would it end?

Having the tree-of-keys have branches that can be conditional on another key solves the problem. It would be a "you can only add this keyring to your tree if you already have that other key" kind of thing. All self-contained within the architecture.

Well, that was how the previous key management approach worked. I just wanted to make clear that this was one reason I considered it unusable.

Linus

So each process should have three keyrings:

- Process level (inherited over fork/exec, but not SUID)
- UID level (fixed to whichever UID a process currently is)
- GID level (fixed to whichever GID a process currently is)

So the search would proceed through the above list top-down, depth first (each key can itself be another keyring).

But what about:

- setuid() and related UID syscalls?
- setgid() and related GID syscalls?
- SGID programs?
- The GROUPS list? Each GID there could have a keyring...

I think changes to UID should cause the process level keyring to be exchanged for a new empty one, but changes in GID/GROUPS should not. Also I think GROUPS list specified keyrings can be ignored for now.

If your subset is but a single pre-existing key (where this includes a keyring as a specialisation of a key), then yes; but if the filesystem is permitted to select multiple keys from different sources, then no.

I think for the moment, however, we can assume there will be a single key.

Fair enough.

Because not doing so complicates things in other ways. But don't lets worry about that.

Why? If a process has access to appropriate UID-level or GID-level keys, then surely it has the rights to do "that", even if it hasn't copied them into its process level keyring...

Hmmm... if I'm using these keys for AFS, say, then I don't want to have to search a complete tree of keyrings every time I perform secure operation (every RxRPC operation possibly). I would like to have the applicable keys immediately to hand - and only those keys - with as little structure as possible.

Um. I'm not sure that what you describe is of much use... I'm not sure I understand correctly what your suggestion is. Can you give an example please?

Exactly there. The ACL would contain a right to (dis)allow modifications to itself.

Actually, it's more a problem of controlling subscription to arbitrarily subscribable "named" keys.

For example, say that a process (owned by dwmw2) says "give me access to the keyring named 'dhowells-session-1275'", then what's to prohibit it from gaining access to all my keys _unless_ I can add an ACL?

Of course, access control could also be performed UID/GID and mode_t settings, but that's just a very simple ACL.

But how do you get that other key in the first place?

This sounds a lot more complicated than it needs to be, and slow... To perform subscription, you then have to search the process's three keyrings for a match for every conditional key in the target tree...

David

How is the key choice different to say selinux roles ?

I'm not sure. After a quick overview of SE Linux, it doesn't seem that it would be able to support this.

David

Well, selinux *does* support the concept of a "role" - Alan's question was whether it's safe to assume that "a single key" is a safe assumption, or if it's reasonable to have multiple keys.

Because not every process that runs under your identity should have your full set of rights. You should be able to confine a given process based on more than just the associated user identity, e.g. the role and clearance in which the user is operating, the function and trustworthiness of the program that the process is executing, etc. Otherwise, you have no protection against flawed or malicious programs executed from any of your sessions.

Stephen Smalley <[email protected]>
National Security Agency

Hi Linus,

Here's an incomplete patch that introduces basic key retention services into the kernel.

What it does:

- manages key creation / destruction
- manages keyrings as special keys
- creates a default UID keyring attached to user_struct
- permits a per-thread keyring that isn't inherited across fork, clone or execve
- creates a per-process keyring that is inherited across clone + CLONE_THREAD, but is not inherited across fork, clone or execve
- creates a "per-session" keyring that is inherited across fork, clone and exec (non-SUID). this is also cleared when switch_uid() is called.
- permits the set of system keys to be viewed in /proc/keys
- assigns every key a unique ID

What it doesn't yet do or hasn't yet been tested:

- GID default keyrings
- key addition and retirement
- key searching
- keyring subscription

David

diff -uNr linux-2.6.0-test4/fs/exec.c linux-2.6.0-test4-keys/fs/exec.c
@@ -45,6 +45,7 @@
 #include <linux/mount.h>
 #include <linux/security.h>
 #include <linux/rmap-locking.h>
+#include <linux/key.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgalloc.h>

@@ -889,10 +890,15 @@
 
 void compute_creds(struct linux_binprm *bprm) 
 {
+	if (bprm->e_uid != current->uid)
+		suid_keys(current);
+	exec_keys(current);
+
 	task_lock(current);
 	if (bprm->e_uid != current->uid || bprm->e_gid != current->gid) {
                 current->mm->dumpable = 0;
-		
+		suid_keys(current);
+
 		if (must_not_trace_exec(current)
 		    || atomic_read(&current->fs->count) > 1
 		    || atomic_read(&current->files->count) > 1

diff -uNr linux-2.6.0-test4/include/linux/sched.h linux-2.6.0-test4-keys/include/linux/sched.h
@@ -290,6 +290,8 @@
 	atomic_t processes;	/* How many processes does this user have? */
 	atomic_t files;		/* How many open files does this user have? */
 
+	struct key *keyring;	/* UID specific keyring */
+
 	/* Hash table maintenance information */
 	struct list_head uidhash_list;
 	uid_t uid;

@@ -402,6 +404,9 @@
 	kernel_cap_t   cap_effective, cap_inheritable, cap_permitted;
 	int keep_capabilities:1;
 	struct user_struct *user;
+	struct key *session_keyring;	/* keyring inherited over fork */
+	struct key *process_keyring;	/* keyring private to this process (CLONE_THREAD) */
+	struct key *thread_keyring;	/* keyring private to this thread */
 /* limits */
 	struct rlimit rlim[RLIM_NLIMITS];
 	unsigned short used_math;

diff -uNr linux-2.6.0-test4/kernel/exit.c linux-2.6.0-test4-keys/kernel/exit.c
@@ -22,6 +22,7 @@
 #include <linux/profile.h>
 #include <linux/mount.h>
 #include <linux/proc_fs.h>
+#include <linux/key.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>

@@ -711,6 +712,7 @@
 	exit_namespace(tsk);
 	exit_itimers(tsk);
 	exit_thread();
+	exit_keys(tsk);
 
 	if (tsk->leader)
 		disassociate_ctty(1);

diff -uNr linux-2.6.0-test4/kernel/fork.c linux-2.6.0-test4-keys/kernel/fork.c
@@ -30,6 +30,7 @@
 #include <linux/futex.h>
 #include <linux/ptrace.h>
 #include <linux/mount.h>
+#include <linux/key.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>

@@ -884,8 +885,10 @@
 		goto bad_fork_cleanup_sighand;
 	if ((retval = copy_mm(clone_flags, p)))
 		goto bad_fork_cleanup_signal;
-	if ((retval = copy_namespace(clone_flags, p)))
+	if ((retval = copy_keys(clone_flags, p)))
 		goto bad_fork_cleanup_mm;
+	if ((retval = copy_namespace(clone_flags, p)))
+		goto bad_fork_cleanup_keys;
 	retval = copy_thread(0, clone_flags, stack_start, stack_size, p, regs);
 	if (retval)
 		goto bad_fork_cleanup_namespace;

@@ -1021,6 +1024,8 @@
 
 bad_fork_cleanup_namespace:
 	exit_namespace(p);
+bad_fork_cleanup_keys:
+	exit_keys(p);
 bad_fork_cleanup_mm:
 	exit_mm(p);
 bad_fork_cleanup_signal:

diff -uNr linux-2.6.0-test4/kernel/Makefile linux-2.6.0-test4-keys/kernel/Makefile
@@ -6,7 +6,7 @@
 	    exit.o itimer.o time.o softirq.o resource.o \
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
-	    rcupdate.o intermodule.o extable.o params.o posix-timers.o
+	    rcupdate.o intermodule.o extable.o params.o posix-timers.o key.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o

diff -uNr linux-2.6.0-test4/kernel/user.c linux-2.6.0-test4-keys/kernel/user.c
@@ -12,6 +12,7 @@
 #include <linux/sched.h>
 #include <linux/slab.h>
 #include <linux/bitops.h>
+#include <linux/key.h>
 
 /*
  * UID task count cache, to get fast user lookup in "alloc_uid"

@@ -30,7 +31,8 @@
 struct user_struct root_user = {
 	.__count	= ATOMIC_INIT(1),
 	.processes	= ATOMIC_INIT(1),
-	.files		= ATOMIC_INIT(0)
+	.files		= ATOMIC_INIT(0),
+	.keyring	= &root_user_keyring,
 };
 
 /*

@@ -73,6 +75,7 @@
 {
 	if (up && atomic_dec_and_lock(&up->__count, &uidhash_lock)) {
 		uid_hash_remove(up);
+		key_put(up->keyring);
 		kmem_cache_free(uid_cachep, up);
 		spin_unlock(&uidhash_lock);
 	}

@@ -98,6 +101,17 @@
 		atomic_set(&new->processes, 0);
 		atomic_set(&new->files, 0);
 
+		if (keyring_alloc(NULL, &new->keyring) < 0) {
+			kmem_cache_free(uid_cachep, up);
+			return NULL;
+		}
+
+		if (keyring_set_name(new->keyring, "_uid.%u", uid) < 0) {
+			key_put(new->keyring);
+			kmem_cache_free(uid_cachep, up);
+			return NULL;
+		}
+
 		/*
 		 * Before adding this, check whether we raced
 		 * on adding the same user already..

@@ -130,6 +144,7 @@
 	atomic_dec(&old_user->processes);
 	current->user = new_user;
 	free_uid(old_user);
+	suid_keys(current);
 }