From 786d35d45cc40b2a51a18f73e14e135d47fdced7 Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Fri, 28 Sep 2012 14:31:03 +0930
Subject: Make most arch asm/module.h files use asm-generic/module.h

Use the mapping of Elf_[SPE]hdr, Elf_Addr, Elf_Sym, Elf_Dyn, Elf_Rel/Rela,
ELF_R_TYPE() and ELF_R_SYM() to either the 32-bit version or the 64-bit version
into asm-generic/module.h for all arches bar MIPS.

Also, use the generic definition mod_arch_specific where possible.

To this end, I've defined three new config bools:

 (*) HAVE_MOD_ARCH_SPECIFIC

     Arches define this if they don't want to use the empty generic
     mod_arch_specific struct.

 (*) MODULES_USE_ELF_RELA

     Arches define this if their modules can contain RELA records.  This causes
     the Elf_Rela mapping to be emitted and allows apply_relocate_add() to be
     defined by the arch rather than have the core emit an error message.

 (*) MODULES_USE_ELF_REL

     Arches define this if their modules can contain REL records.  This causes
     the Elf_Rel mapping to be emitted and allows apply_relocate() to be
     defined by the arch rather than have the core emit an error message.

Note that it is possible to allow both REL and RELA records: m68k and mips are
two arches that do this.

With this, some arch asm/module.h files can be deleted entirely and replaced
with a generic-y marker in the arch Kbuild file.

Additionally, I have removed the bits from m32r and score that handle the
unsupported type of relocation record as that's now handled centrally.

Signed-off-by: David Howells <dhowells@redhat.com>
Acked-by: Sam Ravnborg <sam@ravnborg.org>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 include/asm-generic/module.h | 40 +++++++++++++++++++++++++++++++++-------
 include/linux/moduleloader.h | 36 ++++++++++++++++++++++++++++++++----
 2 files changed, 65 insertions(+), 11 deletions(-)

(limited to 'include')

diff --git a/include/asm-generic/module.h b/include/asm-generic/module.h
index ed5b44de4c91..14dc41d185a7 100644
--- a/include/asm-generic/module.h
+++ b/include/asm-generic/module.h
@@ -5,18 +5,44 @@
  * Many architectures just need a simple module
  * loader without arch specific data.
  */
+#ifndef CONFIG_HAVE_MOD_ARCH_SPECIFIC
 struct mod_arch_specific
 {
 };
+#endif
 
 #ifdef CONFIG_64BIT
-#define Elf_Shdr Elf64_Shdr
-#define Elf_Sym Elf64_Sym
-#define Elf_Ehdr Elf64_Ehdr
-#else
-#define Elf_Shdr Elf32_Shdr
-#define Elf_Sym Elf32_Sym
-#define Elf_Ehdr Elf32_Ehdr
+#define Elf_Shdr	Elf64_Shdr
+#define Elf_Phdr	Elf64_Phdr
+#define Elf_Sym		Elf64_Sym
+#define Elf_Dyn		Elf64_Dyn
+#define Elf_Ehdr	Elf64_Ehdr
+#define Elf_Addr	Elf64_Addr
+#ifdef CONFIG_MODULES_USE_ELF_REL
+#define Elf_Rel		Elf64_Rel
+#endif
+#ifdef CONFIG_MODULES_USE_ELF_RELA
+#define Elf_Rela	Elf64_Rela
+#endif
+#define ELF_R_TYPE(X)	ELF64_R_TYPE(X)
+#define ELF_R_SYM(X)	ELF64_R_SYM(X)
+
+#else /* CONFIG_64BIT */
+
+#define Elf_Shdr	Elf32_Shdr
+#define Elf_Phdr	Elf32_Phdr
+#define Elf_Sym		Elf32_Sym
+#define Elf_Dyn		Elf32_Dyn
+#define Elf_Ehdr	Elf32_Ehdr
+#define Elf_Addr	Elf32_Addr
+#ifdef CONFIG_MODULES_USE_ELF_REL
+#define Elf_Rel		Elf32_Rel
+#endif
+#ifdef CONFIG_MODULES_USE_ELF_RELA
+#define Elf_Rela	Elf32_Rela
+#endif
+#define ELF_R_TYPE(X)	ELF32_R_TYPE(X)
+#define ELF_R_SYM(X)	ELF32_R_SYM(X)
 #endif
 
 #endif /* __ASM_GENERIC_MODULE_H */
diff --git a/include/linux/moduleloader.h b/include/linux/moduleloader.h
index b2be02ebf453..560ca53a75fa 100644
--- a/include/linux/moduleloader.h
+++ b/include/linux/moduleloader.h
@@ -28,21 +28,49 @@ void *module_alloc(unsigned long size);
 /* Free memory returned from module_alloc. */
 void module_free(struct module *mod, void *module_region);
 
-/* Apply the given relocation to the (simplified) ELF.  Return -error
-   or 0. */
+/*
+ * Apply the given relocation to the (simplified) ELF.  Return -error
+ * or 0.
+ */
+#ifdef CONFIG_MODULES_USE_ELF_REL
 int apply_relocate(Elf_Shdr *sechdrs,
 		   const char *strtab,
 		   unsigned int symindex,
 		   unsigned int relsec,
 		   struct module *mod);
+#else
+static inline int apply_relocate(Elf_Shdr *sechdrs,
+				 const char *strtab,
+				 unsigned int symindex,
+				 unsigned int relsec,
+				 struct module *me)
+{
+	printk(KERN_ERR "module %s: REL relocation unsupported\n", me->name);
+	return -ENOEXEC;
+}
+#endif
 
-/* Apply the given add relocation to the (simplified) ELF.  Return
-   -error or 0 */
+/*
+ * Apply the given add relocation to the (simplified) ELF.  Return
+ * -error or 0
+ */
+#ifdef CONFIG_MODULES_USE_ELF_RELA
 int apply_relocate_add(Elf_Shdr *sechdrs,
 		       const char *strtab,
 		       unsigned int symindex,
 		       unsigned int relsec,
 		       struct module *mod);
+#else
+static inline int apply_relocate_add(Elf_Shdr *sechdrs,
+				     const char *strtab,
+				     unsigned int symindex,
+				     unsigned int relsec,
+				     struct module *me)
+{
+	printk(KERN_ERR "module %s: REL relocation unsupported\n", me->name);
+	return -ENOEXEC;
+}
+#endif
 
 /* Any final processing of module before access.  Return -error or 0. */
 int module_finalize(const Elf_Ehdr *hdr,
-- 
cgit v1.2.3-59-g8ed1b


From cf7f601c067994f371ba77721d1e45fce61a4569 Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Thu, 13 Sep 2012 13:06:29 +0100
Subject: KEYS: Add payload preparsing opportunity prior to key instantiate or
 update

Give the key type the opportunity to preparse the payload prior to the
instantiation and update routines being called.  This is done with the
provision of two new key type operations:

	int (*preparse)(struct key_preparsed_payload *prep);
	void (*free_preparse)(struct key_preparsed_payload *prep);

If the first operation is present, then it is called before key creation (in
the add/update case) or before the key semaphore is taken (in the update and
instantiate cases).  The second operation is called to clean up if the first
was called.

preparse() is given the opportunity to fill in the following structure:

	struct key_preparsed_payload {
		char		*description;
		void		*type_data[2];
		void		*payload;
		const void	*data;
		size_t		datalen;
		size_t		quotalen;
	};

Before the preparser is called, the first three fields will have been cleared,
the payload pointer and size will be stored in data and datalen and the default
quota size from the key_type struct will be stored into quotalen.

The preparser may parse the payload in any way it likes and may store data in
the type_data[] and payload fields for use by the instantiate() and update()
ops.

The preparser may also propose a description for the key by attaching it as a
string to the description field.  This can be used by passing a NULL or ""
description to the add_key() system call or the key_create_or_update()
function.  This cannot work with request_key() as that required the description
to tell the upcall about the key to be created.

This, for example permits keys that store PGP public keys to generate their own
name from the user ID and public key fingerprint in the key.

The instantiate() and update() operations are then modified to look like this:

	int (*instantiate)(struct key *key, struct key_preparsed_payload *prep);
	int (*update)(struct key *key, struct key_preparsed_payload *prep);

and the new payload data is passed in *prep, whether or not it was preparsed.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 Documentation/security/keys.txt          |  50 +++++++++++++-
 fs/cifs/cifs_spnego.c                    |   6 +-
 fs/cifs/cifsacl.c                        |   8 +--
 include/keys/user-type.h                 |   6 +-
 include/linux/key-type.h                 |  35 +++++++++-
 net/ceph/crypto.c                        |   9 +--
 net/dns_resolver/dns_key.c               |   6 +-
 net/rxrpc/ar-key.c                       |  40 +++++------
 security/keys/encrypted-keys/encrypted.c |  16 +++--
 security/keys/key.c                      | 114 ++++++++++++++++++++++---------
 security/keys/keyctl.c                   |  18 +++--
 security/keys/keyring.c                  |   6 +-
 security/keys/request_key_auth.c         |   8 +--
 security/keys/trusted.c                  |  16 +++--
 security/keys/user_defined.c             |  14 ++--
 15 files changed, 250 insertions(+), 102 deletions(-)

(limited to 'include')

diff --git a/Documentation/security/keys.txt b/Documentation/security/keys.txt
index aa0dbd74b71b..7d9ca92022d8 100644
--- a/Documentation/security/keys.txt
+++ b/Documentation/security/keys.txt
@@ -412,6 +412,10 @@ The main syscalls are:
      to the keyring. In this case, an error will be generated if the process
      does not have permission to write to the keyring.
 
+     If the key type supports it, if the description is NULL or an empty
+     string, the key type will try and generate a description from the content
+     of the payload.
+
      The payload is optional, and the pointer can be NULL if not required by
      the type. The payload is plen in size, and plen can be zero for an empty
      payload.
@@ -1114,12 +1118,53 @@ The structure has a number of fields, some of which are mandatory:
      it should return 0.
 
 
- (*) int (*instantiate)(struct key *key, const void *data, size_t datalen);
+ (*) int (*preparse)(struct key_preparsed_payload *prep);
+
+     This optional method permits the key type to attempt to parse payload
+     before a key is created (add key) or the key semaphore is taken (update or
+     instantiate key).  The structure pointed to by prep looks like:
+
+	struct key_preparsed_payload {
+		char		*description;
+		void		*type_data[2];
+		void		*payload;
+		const void	*data;
+		size_t		datalen;
+		size_t		quotalen;
+	};
+
+     Before calling the method, the caller will fill in data and datalen with
+     the payload blob parameters; quotalen will be filled in with the default
+     quota size from the key type and the rest will be cleared.
+
+     If a description can be proposed from the payload contents, that should be
+     attached as a string to the description field.  This will be used for the
+     key description if the caller of add_key() passes NULL or "".
+
+     The method can attach anything it likes to type_data[] and payload.  These
+     are merely passed along to the instantiate() or update() operations.
+
+     The method should return 0 if success ful or a negative error code
+     otherwise.
+
+     
+ (*) void (*free_preparse)(struct key_preparsed_payload *prep);
+
+     This method is only required if the preparse() method is provided,
+     otherwise it is unused.  It cleans up anything attached to the
+     description, type_data and payload fields of the key_preparsed_payload
+     struct as filled in by the preparse() method.
+
+
+ (*) int (*instantiate)(struct key *key, struct key_preparsed_payload *prep);
 
      This method is called to attach a payload to a key during construction.
      The payload attached need not bear any relation to the data passed to this
      function.
 
+     The prep->data and prep->datalen fields will define the original payload
+     blob.  If preparse() was supplied then other fields may be filled in also.
+
      If the amount of data attached to the key differs from the size in
      keytype->def_datalen, then key_payload_reserve() should be called.
 
@@ -1135,6 +1180,9 @@ The structure has a number of fields, some of which are mandatory:
      If this type of key can be updated, then this method should be provided.
      It is called to update a key's payload from the blob of data provided.
 
+     The prep->data and prep->datalen fields will define the original payload
+     blob.  If preparse() was supplied then other fields may be filled in also.
+
      key_payload_reserve() should be called if the data length might change
      before any changes are actually made. Note that if this succeeds, the type
      is committed to changing the key because it's already been altered, so all
diff --git a/fs/cifs/cifs_spnego.c b/fs/cifs/cifs_spnego.c
index e622863b292f..086f381d6489 100644
--- a/fs/cifs/cifs_spnego.c
+++ b/fs/cifs/cifs_spnego.c
@@ -31,18 +31,18 @@
 
 /* create a new cifs key */
 static int
-cifs_spnego_key_instantiate(struct key *key, const void *data, size_t datalen)
+cifs_spnego_key_instantiate(struct key *key, struct key_preparsed_payload *prep)
 {
 	char *payload;
 	int ret;
 
 	ret = -ENOMEM;
-	payload = kmalloc(datalen, GFP_KERNEL);
+	payload = kmalloc(prep->datalen, GFP_KERNEL);
 	if (!payload)
 		goto error;
 
 	/* attach the data */
-	memcpy(payload, data, datalen);
+	memcpy(payload, prep->data, prep->datalen);
 	key->payload.data = payload;
 	ret = 0;
 
diff --git a/fs/cifs/cifsacl.c b/fs/cifs/cifsacl.c
index 05f4dc263a23..f3c60e264ca8 100644
--- a/fs/cifs/cifsacl.c
+++ b/fs/cifs/cifsacl.c
@@ -167,17 +167,17 @@ static struct shrinker cifs_shrinker = {
 };
 
 static int
-cifs_idmap_key_instantiate(struct key *key, const void *data, size_t datalen)
+cifs_idmap_key_instantiate(struct key *key, struct key_preparsed_payload *prep)
 {
 	char *payload;
 
-	payload = kmalloc(datalen, GFP_KERNEL);
+	payload = kmalloc(prep->datalen, GFP_KERNEL);
 	if (!payload)
 		return -ENOMEM;
 
-	memcpy(payload, data, datalen);
+	memcpy(payload, prep->data, prep->datalen);
 	key->payload.data = payload;
-	key->datalen = datalen;
+	key->datalen = prep->datalen;
 	return 0;
 }
 
diff --git a/include/keys/user-type.h b/include/keys/user-type.h
index bc9ec1d7698c..5e452c84f1e6 100644
--- a/include/keys/user-type.h
+++ b/include/keys/user-type.h
@@ -35,8 +35,10 @@ struct user_key_payload {
 extern struct key_type key_type_user;
 extern struct key_type key_type_logon;
 
-extern int user_instantiate(struct key *key, const void *data, size_t datalen);
-extern int user_update(struct key *key, const void *data, size_t datalen);
+struct key_preparsed_payload;
+
+extern int user_instantiate(struct key *key, struct key_preparsed_payload *prep);
+extern int user_update(struct key *key, struct key_preparsed_payload *prep);
 extern int user_match(const struct key *key, const void *criterion);
 extern void user_revoke(struct key *key);
 extern void user_destroy(struct key *key);
diff --git a/include/linux/key-type.h b/include/linux/key-type.h
index f0c651cda7b0..518a53afb9ea 100644
--- a/include/linux/key-type.h
+++ b/include/linux/key-type.h
@@ -26,6 +26,27 @@ struct key_construction {
 	struct key	*authkey;/* authorisation for key being constructed */
 };
 
+/*
+ * Pre-parsed payload, used by key add, update and instantiate.
+ *
+ * This struct will be cleared and data and datalen will be set with the data
+ * and length parameters from the caller and quotalen will be set from
+ * def_datalen from the key type.  Then if the preparse() op is provided by the
+ * key type, that will be called.  Then the struct will be passed to the
+ * instantiate() or the update() op.
+ *
+ * If the preparse() op is given, the free_preparse() op will be called to
+ * clear the contents.
+ */
+struct key_preparsed_payload {
+	char		*description;	/* Proposed key description (or NULL) */
+	void		*type_data[2];	/* Private key-type data */
+	void		*payload;	/* Proposed payload */
+	const void	*data;		/* Raw data */
+	size_t		datalen;	/* Raw datalen */
+	size_t		quotalen;	/* Quota length for proposed payload */
+};
+
 typedef int (*request_key_actor_t)(struct key_construction *key,
 				   const char *op, void *aux);
 
@@ -45,18 +66,28 @@ struct key_type {
 	/* vet a description */
 	int (*vet_description)(const char *description);
 
+	/* Preparse the data blob from userspace that is to be the payload,
+	 * generating a proposed description and payload that will be handed to
+	 * the instantiate() and update() ops.
+	 */
+	int (*preparse)(struct key_preparsed_payload *prep);
+
+	/* Free a preparse data structure.
+	 */
+	void (*free_preparse)(struct key_preparsed_payload *prep);
+
 	/* instantiate a key of this type
 	 * - this method should call key_payload_reserve() to determine if the
 	 *   user's quota will hold the payload
 	 */
-	int (*instantiate)(struct key *key, const void *data, size_t datalen);
+	int (*instantiate)(struct key *key, struct key_preparsed_payload *prep);
 
 	/* update a key of this type (optional)
 	 * - this method should call key_payload_reserve() to recalculate the
 	 *   quota consumption
 	 * - the key must be locked against read when modifying
 	 */
-	int (*update)(struct key *key, const void *data, size_t datalen);
+	int (*update)(struct key *key, struct key_preparsed_payload *prep);
 
 	/* match a key against a description */
 	int (*match)(const struct key *key, const void *desc);
diff --git a/net/ceph/crypto.c b/net/ceph/crypto.c
index 9da7fdd3cd8a..af14cb425164 100644
--- a/net/ceph/crypto.c
+++ b/net/ceph/crypto.c
@@ -423,14 +423,15 @@ int ceph_encrypt2(struct ceph_crypto_key *secret, void *dst, size_t *dst_len,
 	}
 }
 
-int ceph_key_instantiate(struct key *key, const void *data, size_t datalen)
+int ceph_key_instantiate(struct key *key, struct key_preparsed_payload *prep)
 {
 	struct ceph_crypto_key *ckey;
+	size_t datalen = prep->datalen;
 	int ret;
 	void *p;
 
 	ret = -EINVAL;
-	if (datalen <= 0 || datalen > 32767 || !data)
+	if (datalen <= 0 || datalen > 32767 || !prep->data)
 		goto err;
 
 	ret = key_payload_reserve(key, datalen);
@@ -443,8 +444,8 @@ int ceph_key_instantiate(struct key *key, const void *data, size_t datalen)
 		goto err;
 
 	/* TODO ceph_crypto_key_decode should really take const input */
-	p = (void *)data;
-	ret = ceph_crypto_key_decode(ckey, &p, (char*)data+datalen);
+	p = (void *)prep->data;
+	ret = ceph_crypto_key_decode(ckey, &p, (char*)prep->data+datalen);
 	if (ret < 0)
 		goto err_ckey;
 
diff --git a/net/dns_resolver/dns_key.c b/net/dns_resolver/dns_key.c
index d9507dd05818..859ab8b6ec34 100644
--- a/net/dns_resolver/dns_key.c
+++ b/net/dns_resolver/dns_key.c
@@ -59,13 +59,13 @@ const struct cred *dns_resolver_cache;
  *        "ip1,ip2,...#foo=bar"
  */
 static int
-dns_resolver_instantiate(struct key *key, const void *_data, size_t datalen)
+dns_resolver_instantiate(struct key *key, struct key_preparsed_payload *prep)
 {
 	struct user_key_payload *upayload;
 	unsigned long derrno;
 	int ret;
-	size_t result_len = 0;
-	const char *data = _data, *end, *opt;
+	size_t datalen = prep->datalen, result_len = 0;
+	const char *data = prep->data, *end, *opt;
 
 	kenter("%%%d,%s,'%*.*s',%zu",
 	       key->serial, key->description,
diff --git a/net/rxrpc/ar-key.c b/net/rxrpc/ar-key.c
index 8b1f9f49960f..106c5a6b1ab2 100644
--- a/net/rxrpc/ar-key.c
+++ b/net/rxrpc/ar-key.c
@@ -26,8 +26,8 @@
 #include "ar-internal.h"
 
 static int rxrpc_vet_description_s(const char *);
-static int rxrpc_instantiate(struct key *, const void *, size_t);
-static int rxrpc_instantiate_s(struct key *, const void *, size_t);
+static int rxrpc_instantiate(struct key *, struct key_preparsed_payload *);
+static int rxrpc_instantiate_s(struct key *, struct key_preparsed_payload *);
 static void rxrpc_destroy(struct key *);
 static void rxrpc_destroy_s(struct key *);
 static void rxrpc_describe(const struct key *, struct seq_file *);
@@ -678,7 +678,7 @@ error:
  *
  * if no data is provided, then a no-security key is made
  */
-static int rxrpc_instantiate(struct key *key, const void *data, size_t datalen)
+static int rxrpc_instantiate(struct key *key, struct key_preparsed_payload *prep)
 {
 	const struct rxrpc_key_data_v1 *v1;
 	struct rxrpc_key_token *token, **pp;
@@ -686,26 +686,26 @@ static int rxrpc_instantiate(struct key *key, const void *data, size_t datalen)
 	u32 kver;
 	int ret;
 
-	_enter("{%x},,%zu", key_serial(key), datalen);
+	_enter("{%x},,%zu", key_serial(key), prep->datalen);
 
 	/* handle a no-security key */
-	if (!data && datalen == 0)
+	if (!prep->data && prep->datalen == 0)
 		return 0;
 
 	/* determine if the XDR payload format is being used */
-	if (datalen > 7 * 4) {
-		ret = rxrpc_instantiate_xdr(key, data, datalen);
+	if (prep->datalen > 7 * 4) {
+		ret = rxrpc_instantiate_xdr(key, prep->data, prep->datalen);
 		if (ret != -EPROTO)
 			return ret;
 	}
 
 	/* get the key interface version number */
 	ret = -EINVAL;
-	if (datalen <= 4 || !data)
+	if (prep->datalen <= 4 || !prep->data)
 		goto error;
-	memcpy(&kver, data, sizeof(kver));
-	data += sizeof(kver);
-	datalen -= sizeof(kver);
+	memcpy(&kver, prep->data, sizeof(kver));
+	prep->data += sizeof(kver);
+	prep->datalen -= sizeof(kver);
 
 	_debug("KEY I/F VERSION: %u", kver);
 
@@ -715,11 +715,11 @@ static int rxrpc_instantiate(struct key *key, const void *data, size_t datalen)
 
 	/* deal with a version 1 key */
 	ret = -EINVAL;
-	if (datalen < sizeof(*v1))
+	if (prep->datalen < sizeof(*v1))
 		goto error;
 
-	v1 = data;
-	if (datalen != sizeof(*v1) + v1->ticket_length)
+	v1 = prep->data;
+	if (prep->datalen != sizeof(*v1) + v1->ticket_length)
 		goto error;
 
 	_debug("SCIX: %u", v1->security_index);
@@ -784,17 +784,17 @@ error:
  * instantiate a server secret key
  * data should be a pointer to the 8-byte secret key
  */
-static int rxrpc_instantiate_s(struct key *key, const void *data,
-			       size_t datalen)
+static int rxrpc_instantiate_s(struct key *key,
+			       struct key_preparsed_payload *prep)
 {
 	struct crypto_blkcipher *ci;
 
-	_enter("{%x},,%zu", key_serial(key), datalen);
+	_enter("{%x},,%zu", key_serial(key), prep->datalen);
 
-	if (datalen != 8)
+	if (prep->datalen != 8)
 		return -EINVAL;
 
-	memcpy(&key->type_data, data, 8);
+	memcpy(&key->type_data, prep->data, 8);
 
 	ci = crypto_alloc_blkcipher("pcbc(des)", 0, CRYPTO_ALG_ASYNC);
 	if (IS_ERR(ci)) {
@@ -802,7 +802,7 @@ static int rxrpc_instantiate_s(struct key *key, const void *data,
 		return PTR_ERR(ci);
 	}
 
-	if (crypto_blkcipher_setkey(ci, data, 8) < 0)
+	if (crypto_blkcipher_setkey(ci, prep->data, 8) < 0)
 		BUG();
 
 	key->payload.data = ci;
diff --git a/security/keys/encrypted-keys/encrypted.c b/security/keys/encrypted-keys/encrypted.c
index 2d1bb8af7696..9e1e005c7596 100644
--- a/security/keys/encrypted-keys/encrypted.c
+++ b/security/keys/encrypted-keys/encrypted.c
@@ -773,8 +773,8 @@ static int encrypted_init(struct encrypted_key_payload *epayload,
  *
  * On success, return 0. Otherwise return errno.
  */
-static int encrypted_instantiate(struct key *key, const void *data,
-				 size_t datalen)
+static int encrypted_instantiate(struct key *key,
+				 struct key_preparsed_payload *prep)
 {
 	struct encrypted_key_payload *epayload = NULL;
 	char *datablob = NULL;
@@ -782,16 +782,17 @@ static int encrypted_instantiate(struct key *key, const void *data,
 	char *master_desc = NULL;
 	char *decrypted_datalen = NULL;
 	char *hex_encoded_iv = NULL;
+	size_t datalen = prep->datalen;
 	int ret;
 
-	if (datalen <= 0 || datalen > 32767 || !data)
+	if (datalen <= 0 || datalen > 32767 || !prep->data)
 		return -EINVAL;
 
 	datablob = kmalloc(datalen + 1, GFP_KERNEL);
 	if (!datablob)
 		return -ENOMEM;
 	datablob[datalen] = 0;
-	memcpy(datablob, data, datalen);
+	memcpy(datablob, prep->data, datalen);
 	ret = datablob_parse(datablob, &format, &master_desc,
 			     &decrypted_datalen, &hex_encoded_iv);
 	if (ret < 0)
@@ -834,16 +835,17 @@ static void encrypted_rcu_free(struct rcu_head *rcu)
  *
  * On success, return 0. Otherwise return errno.
  */
-static int encrypted_update(struct key *key, const void *data, size_t datalen)
+static int encrypted_update(struct key *key, struct key_preparsed_payload *prep)
 {
 	struct encrypted_key_payload *epayload = key->payload.data;
 	struct encrypted_key_payload *new_epayload;
 	char *buf;
 	char *new_master_desc = NULL;
 	const char *format = NULL;
+	size_t datalen = prep->datalen;
 	int ret = 0;
 
-	if (datalen <= 0 || datalen > 32767 || !data)
+	if (datalen <= 0 || datalen > 32767 || !prep->data)
 		return -EINVAL;
 
 	buf = kmalloc(datalen + 1, GFP_KERNEL);
@@ -851,7 +853,7 @@ static int encrypted_update(struct key *key, const void *data, size_t datalen)
 		return -ENOMEM;
 
 	buf[datalen] = 0;
-	memcpy(buf, data, datalen);
+	memcpy(buf, prep->data, datalen);
 	ret = datablob_parse(buf, &format, &new_master_desc, NULL, NULL);
 	if (ret < 0)
 		goto out;
diff --git a/security/keys/key.c b/security/keys/key.c
index 50d96d4e06f2..1d039af99f50 100644
--- a/security/keys/key.c
+++ b/security/keys/key.c
@@ -412,8 +412,7 @@ EXPORT_SYMBOL(key_payload_reserve);
  * key_construction_mutex.
  */
 static int __key_instantiate_and_link(struct key *key,
-				      const void *data,
-				      size_t datalen,
+				      struct key_preparsed_payload *prep,
 				      struct key *keyring,
 				      struct key *authkey,
 				      unsigned long *_prealloc)
@@ -431,7 +430,7 @@ static int __key_instantiate_and_link(struct key *key,
 	/* can't instantiate twice */
 	if (!test_bit(KEY_FLAG_INSTANTIATED, &key->flags)) {
 		/* instantiate the key */
-		ret = key->type->instantiate(key, data, datalen);
+		ret = key->type->instantiate(key, prep);
 
 		if (ret == 0) {
 			/* mark the key as being instantiated */
@@ -482,22 +481,37 @@ int key_instantiate_and_link(struct key *key,
 			     struct key *keyring,
 			     struct key *authkey)
 {
+	struct key_preparsed_payload prep;
 	unsigned long prealloc;
 	int ret;
 
+	memset(&prep, 0, sizeof(prep));
+	prep.data = data;
+	prep.datalen = datalen;
+	prep.quotalen = key->type->def_datalen;
+	if (key->type->preparse) {
+		ret = key->type->preparse(&prep);
+		if (ret < 0)
+			goto error;
+	}
+
 	if (keyring) {
 		ret = __key_link_begin(keyring, key->type, key->description,
 				       &prealloc);
 		if (ret < 0)
-			return ret;
+			goto error_free_preparse;
 	}
 
-	ret = __key_instantiate_and_link(key, data, datalen, keyring, authkey,
+	ret = __key_instantiate_and_link(key, &prep, keyring, authkey,
 					 &prealloc);
 
 	if (keyring)
 		__key_link_end(keyring, key->type, prealloc);
 
+error_free_preparse:
+	if (key->type->preparse)
+		key->type->free_preparse(&prep);
+error:
 	return ret;
 }
 
@@ -706,7 +720,7 @@ void key_type_put(struct key_type *ktype)
  * if we get an error.
  */
 static inline key_ref_t __key_update(key_ref_t key_ref,
-				     const void *payload, size_t plen)
+				     struct key_preparsed_payload *prep)
 {
 	struct key *key = key_ref_to_ptr(key_ref);
 	int ret;
@@ -722,7 +736,7 @@ static inline key_ref_t __key_update(key_ref_t key_ref,
 
 	down_write(&key->sem);
 
-	ret = key->type->update(key, payload, plen);
+	ret = key->type->update(key, prep);
 	if (ret == 0)
 		/* updating a negative key instantiates it */
 		clear_bit(KEY_FLAG_NEGATIVE, &key->flags);
@@ -774,6 +788,7 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
 			       unsigned long flags)
 {
 	unsigned long prealloc;
+	struct key_preparsed_payload prep;
 	const struct cred *cred = current_cred();
 	struct key_type *ktype;
 	struct key *keyring, *key = NULL;
@@ -789,8 +804,9 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
 	}
 
 	key_ref = ERR_PTR(-EINVAL);
-	if (!ktype->match || !ktype->instantiate)
-		goto error_2;
+	if (!ktype->match || !ktype->instantiate ||
+	    (!description && !ktype->preparse))
+		goto error_put_type;
 
 	keyring = key_ref_to_ptr(keyring_ref);
 
@@ -798,18 +814,37 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
 
 	key_ref = ERR_PTR(-ENOTDIR);
 	if (keyring->type != &key_type_keyring)
-		goto error_2;
+		goto error_put_type;
+
+	memset(&prep, 0, sizeof(prep));
+	prep.data = payload;
+	prep.datalen = plen;
+	prep.quotalen = ktype->def_datalen;
+	if (ktype->preparse) {
+		ret = ktype->preparse(&prep);
+		if (ret < 0) {
+			key_ref = ERR_PTR(ret);
+			goto error_put_type;
+		}
+		if (!description)
+			description = prep.description;
+		key_ref = ERR_PTR(-EINVAL);
+		if (!description)
+			goto error_free_prep;
+	}
 
 	ret = __key_link_begin(keyring, ktype, description, &prealloc);
-	if (ret < 0)
-		goto error_2;
+	if (ret < 0) {
+		key_ref = ERR_PTR(ret);
+		goto error_free_prep;
+	}
 
 	/* if we're going to allocate a new key, we're going to have
 	 * to modify the keyring */
 	ret = key_permission(keyring_ref, KEY_WRITE);
 	if (ret < 0) {
 		key_ref = ERR_PTR(ret);
-		goto error_3;
+		goto error_link_end;
 	}
 
 	/* if it's possible to update this type of key, search for an existing
@@ -840,25 +875,27 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
 			perm, flags);
 	if (IS_ERR(key)) {
 		key_ref = ERR_CAST(key);
-		goto error_3;
+		goto error_link_end;
 	}
 
 	/* instantiate it and link it into the target keyring */
-	ret = __key_instantiate_and_link(key, payload, plen, keyring, NULL,
-					 &prealloc);
+	ret = __key_instantiate_and_link(key, &prep, keyring, NULL, &prealloc);
 	if (ret < 0) {
 		key_put(key);
 		key_ref = ERR_PTR(ret);
-		goto error_3;
+		goto error_link_end;
 	}
 
 	key_ref = make_key_ref(key, is_key_possessed(keyring_ref));
 
- error_3:
+error_link_end:
 	__key_link_end(keyring, ktype, prealloc);
- error_2:
+error_free_prep:
+	if (ktype->preparse)
+		ktype->free_preparse(&prep);
+error_put_type:
 	key_type_put(ktype);
- error:
+error:
 	return key_ref;
 
  found_matching_key:
@@ -866,10 +903,9 @@ key_ref_t key_create_or_update(key_ref_t keyring_ref,
 	 * - we can drop the locks first as we have the key pinned
 	 */
 	__key_link_end(keyring, ktype, prealloc);
-	key_type_put(ktype);
 
-	key_ref = __key_update(key_ref, payload, plen);
-	goto error;
+	key_ref = __key_update(key_ref, &prep);
+	goto error_free_prep;
 }
 EXPORT_SYMBOL(key_create_or_update);
 
@@ -888,6 +924,7 @@ EXPORT_SYMBOL(key_create_or_update);
  */
 int key_update(key_ref_t key_ref, const void *payload, size_t plen)
 {
+	struct key_preparsed_payload prep;
 	struct key *key = key_ref_to_ptr(key_ref);
 	int ret;
 
@@ -900,18 +937,31 @@ int key_update(key_ref_t key_ref, const void *payload, size_t plen)
 
 	/* attempt to update it if supported */
 	ret = -EOPNOTSUPP;
-	if (key->type->update) {
-		down_write(&key->sem);
-
-		ret = key->type->update(key, payload, plen);
-		if (ret == 0)
-			/* updating a negative key instantiates it */
-			clear_bit(KEY_FLAG_NEGATIVE, &key->flags);
+	if (!key->type->update)
+		goto error;
 
-		up_write(&key->sem);
+	memset(&prep, 0, sizeof(prep));
+	prep.data = payload;
+	prep.datalen = plen;
+	prep.quotalen = key->type->def_datalen;
+	if (key->type->preparse) {
+		ret = key->type->preparse(&prep);
+		if (ret < 0)
+			goto error;
 	}
 
- error:
+	down_write(&key->sem);
+
+	ret = key->type->update(key, &prep);
+	if (ret == 0)
+		/* updating a negative key instantiates it */
+		clear_bit(KEY_FLAG_NEGATIVE, &key->flags);
+
+	up_write(&key->sem);
+
+	if (key->type->preparse)
+		key->type->free_preparse(&prep);
+error:
 	return ret;
 }
 EXPORT_SYMBOL(key_update);
diff --git a/security/keys/keyctl.c b/security/keys/keyctl.c
index 3364fbf46807..505d40be196c 100644
--- a/security/keys/keyctl.c
+++ b/security/keys/keyctl.c
@@ -46,6 +46,9 @@ static int key_get_type_from_user(char *type,
  * Extract the description of a new key from userspace and either add it as a
  * new key to the specified keyring or update a matching key in that keyring.
  *
+ * If the description is NULL or an empty string, the key type is asked to
+ * generate one from the payload.
+ *
  * The keyring must be writable so that we can attach the key to it.
  *
  * If successful, the new key's serial number is returned, otherwise an error
@@ -72,10 +75,17 @@ SYSCALL_DEFINE5(add_key, const char __user *, _type,
 	if (ret < 0)
 		goto error;
 
-	description = strndup_user(_description, PAGE_SIZE);
-	if (IS_ERR(description)) {
-		ret = PTR_ERR(description);
-		goto error;
+	description = NULL;
+	if (_description) {
+		description = strndup_user(_description, PAGE_SIZE);
+		if (IS_ERR(description)) {
+			ret = PTR_ERR(description);
+			goto error;
+		}
+		if (!*description) {
+			kfree(description);
+			description = NULL;
+		}
 	}
 
 	/* pull the payload in if one was supplied */
diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index 81e7852d281d..f04d8cf81f3c 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -66,7 +66,7 @@ static inline unsigned keyring_hash(const char *desc)
  * operations.
  */
 static int keyring_instantiate(struct key *keyring,
-			       const void *data, size_t datalen);
+			       struct key_preparsed_payload *prep);
 static int keyring_match(const struct key *keyring, const void *criterion);
 static void keyring_revoke(struct key *keyring);
 static void keyring_destroy(struct key *keyring);
@@ -121,12 +121,12 @@ static void keyring_publish_name(struct key *keyring)
  * Returns 0 on success, -EINVAL if given any data.
  */
 static int keyring_instantiate(struct key *keyring,
-			       const void *data, size_t datalen)
+			       struct key_preparsed_payload *prep)
 {
 	int ret;
 
 	ret = -EINVAL;
-	if (datalen == 0) {
+	if (prep->datalen == 0) {
 		/* make the keyring available by name if it has one */
 		keyring_publish_name(keyring);
 		ret = 0;
diff --git a/security/keys/request_key_auth.c b/security/keys/request_key_auth.c
index 60d4e3f5e4bb..85730d5a5a59 100644
--- a/security/keys/request_key_auth.c
+++ b/security/keys/request_key_auth.c
@@ -19,7 +19,8 @@
 #include <asm/uaccess.h>
 #include "internal.h"
 
-static int request_key_auth_instantiate(struct key *, const void *, size_t);
+static int request_key_auth_instantiate(struct key *,
+					struct key_preparsed_payload *);
 static void request_key_auth_describe(const struct key *, struct seq_file *);
 static void request_key_auth_revoke(struct key *);
 static void request_key_auth_destroy(struct key *);
@@ -42,10 +43,9 @@ struct key_type key_type_request_key_auth = {
  * Instantiate a request-key authorisation key.
  */
 static int request_key_auth_instantiate(struct key *key,
-					const void *data,
-					size_t datalen)
+					struct key_preparsed_payload *prep)
 {
-	key->payload.data = (struct request_key_auth *) data;
+	key->payload.data = (struct request_key_auth *)prep->data;
 	return 0;
 }
 
diff --git a/security/keys/trusted.c b/security/keys/trusted.c
index 2d5d041f2049..42036c7a0856 100644
--- a/security/keys/trusted.c
+++ b/security/keys/trusted.c
@@ -927,22 +927,23 @@ static struct trusted_key_payload *trusted_payload_alloc(struct key *key)
  *
  * On success, return 0. Otherwise return errno.
  */
-static int trusted_instantiate(struct key *key, const void *data,
-			       size_t datalen)
+static int trusted_instantiate(struct key *key,
+			       struct key_preparsed_payload *prep)
 {
 	struct trusted_key_payload *payload = NULL;
 	struct trusted_key_options *options = NULL;
+	size_t datalen = prep->datalen;
 	char *datablob;
 	int ret = 0;
 	int key_cmd;
 
-	if (datalen <= 0 || datalen > 32767 || !data)
+	if (datalen <= 0 || datalen > 32767 || !prep->data)
 		return -EINVAL;
 
 	datablob = kmalloc(datalen + 1, GFP_KERNEL);
 	if (!datablob)
 		return -ENOMEM;
-	memcpy(datablob, data, datalen);
+	memcpy(datablob, prep->data, datalen);
 	datablob[datalen] = '\0';
 
 	options = trusted_options_alloc();
@@ -1011,17 +1012,18 @@ static void trusted_rcu_free(struct rcu_head *rcu)
 /*
  * trusted_update - reseal an existing key with new PCR values
  */
-static int trusted_update(struct key *key, const void *data, size_t datalen)
+static int trusted_update(struct key *key, struct key_preparsed_payload *prep)
 {
 	struct trusted_key_payload *p = key->payload.data;
 	struct trusted_key_payload *new_p;
 	struct trusted_key_options *new_o;
+	size_t datalen = prep->datalen;
 	char *datablob;
 	int ret = 0;
 
 	if (!p->migratable)
 		return -EPERM;
-	if (datalen <= 0 || datalen > 32767 || !data)
+	if (datalen <= 0 || datalen > 32767 || !prep->data)
 		return -EINVAL;
 
 	datablob = kmalloc(datalen + 1, GFP_KERNEL);
@@ -1038,7 +1040,7 @@ static int trusted_update(struct key *key, const void *data, size_t datalen)
 		goto out;
 	}
 
-	memcpy(datablob, data, datalen);
+	memcpy(datablob, prep->data, datalen);
 	datablob[datalen] = '\0';
 	ret = datablob_parse(datablob, new_p, new_o);
 	if (ret != Opt_update) {
diff --git a/security/keys/user_defined.c b/security/keys/user_defined.c
index c7660a25a3e4..55dc88939185 100644
--- a/security/keys/user_defined.c
+++ b/security/keys/user_defined.c
@@ -58,13 +58,14 @@ EXPORT_SYMBOL_GPL(key_type_logon);
 /*
  * instantiate a user defined key
  */
-int user_instantiate(struct key *key, const void *data, size_t datalen)
+int user_instantiate(struct key *key, struct key_preparsed_payload *prep)
 {
 	struct user_key_payload *upayload;
+	size_t datalen = prep->datalen;
 	int ret;
 
 	ret = -EINVAL;
-	if (datalen <= 0 || datalen > 32767 || !data)
+	if (datalen <= 0 || datalen > 32767 || !prep->data)
 		goto error;
 
 	ret = key_payload_reserve(key, datalen);
@@ -78,7 +79,7 @@ int user_instantiate(struct key *key, const void *data, size_t datalen)
 
 	/* attach the data */
 	upayload->datalen = datalen;
-	memcpy(upayload->data, data, datalen);
+	memcpy(upayload->data, prep->data, datalen);
 	rcu_assign_keypointer(key, upayload);
 	ret = 0;
 
@@ -92,13 +93,14 @@ EXPORT_SYMBOL_GPL(user_instantiate);
  * update a user defined key
  * - the key's semaphore is write-locked
  */
-int user_update(struct key *key, const void *data, size_t datalen)
+int user_update(struct key *key, struct key_preparsed_payload *prep)
 {
 	struct user_key_payload *upayload, *zap;
+	size_t datalen = prep->datalen;
 	int ret;
 
 	ret = -EINVAL;
-	if (datalen <= 0 || datalen > 32767 || !data)
+	if (datalen <= 0 || datalen > 32767 || !prep->data)
 		goto error;
 
 	/* construct a replacement payload */
@@ -108,7 +110,7 @@ int user_update(struct key *key, const void *data, size_t datalen)
 		goto error;
 
 	upayload->datalen = datalen;
-	memcpy(upayload->data, data, datalen);
+	memcpy(upayload->data, prep->data, datalen);
 
 	/* check the quota and attach the new data */
 	zap = upayload;
-- 
cgit v1.2.3-59-g8ed1b


From aacf29bf1bf133f6219e6f8969d4ebc2ac76458f Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Thu, 13 Sep 2012 13:09:33 +0100
Subject: MPILIB: Provide count_leading/trailing_zeros() based on arch
 functions

Provide count_leading/trailing_zeros() macros based on extant arch bit scanning
functions rather than reimplementing from scratch in MPILIB.

Whilst we're at it, turn count_foo_zeros(n, x) into n = count_foo_zeros(x).

Also move the definition to asm-generic as other people may be interested in
using it.

Signed-off-by: David Howells <dhowells@redhat.com>
Cc: David S. Miller <davem@davemloft.net>
Cc: Dmitry Kasatkin <dmitry.kasatkin@intel.com>
Cc: Arnd Bergmann <arnd@arndb.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 include/asm-generic/bitops/count_zeros.h |  57 +++++++++++++
 lib/mpi/longlong.h                       | 138 +------------------------------
 lib/mpi/mpi-bit.c                        |   2 +-
 lib/mpi/mpi-pow.c                        |   4 +-
 4 files changed, 62 insertions(+), 139 deletions(-)
 create mode 100644 include/asm-generic/bitops/count_zeros.h

(limited to 'include')

diff --git a/include/asm-generic/bitops/count_zeros.h b/include/asm-generic/bitops/count_zeros.h
new file mode 100644
index 000000000000..97520d21fe62
--- /dev/null
+++ b/include/asm-generic/bitops/count_zeros.h
@@ -0,0 +1,57 @@
+/* Count leading and trailing zeros functions
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_
+#define _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_
+
+#include <asm/bitops.h>
+
+/**
+ * count_leading_zeros - Count the number of zeros from the MSB back
+ * @x: The value
+ *
+ * Count the number of leading zeros from the MSB going towards the LSB in @x.
+ *
+ * If the MSB of @x is set, the result is 0.
+ * If only the LSB of @x is set, then the result is BITS_PER_LONG-1.
+ * If @x is 0 then the result is COUNT_LEADING_ZEROS_0.
+ */
+static inline int count_leading_zeros(unsigned long x)
+{
+	if (sizeof(x) == 4)
+		return BITS_PER_LONG - fls(x);
+	else
+		return BITS_PER_LONG - fls64(x);
+}
+
+#define COUNT_LEADING_ZEROS_0 BITS_PER_LONG
+
+/**
+ * count_trailing_zeros - Count the number of zeros from the LSB forwards
+ * @x: The value
+ *
+ * Count the number of trailing zeros from the LSB going towards the MSB in @x.
+ *
+ * If the LSB of @x is set, the result is 0.
+ * If only the MSB of @x is set, then the result is BITS_PER_LONG-1.
+ * If @x is 0 then the result is COUNT_TRAILING_ZEROS_0.
+ */
+static inline int count_trailing_zeros(unsigned long x)
+{
+#define COUNT_TRAILING_ZEROS_0 (-1)
+
+	if (sizeof(x) == 4)
+		return ffs(x);
+	else
+		return (x != 0) ? __ffs(x) : COUNT_TRAILING_ZEROS_0;
+}
+
+#endif /* _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_ */
diff --git a/lib/mpi/longlong.h b/lib/mpi/longlong.h
index 29f98624ef93..678ce4f1e124 100644
--- a/lib/mpi/longlong.h
+++ b/lib/mpi/longlong.h
@@ -19,6 +19,8 @@
  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  * MA 02111-1307, USA. */
 
+#include <asm-generic/bitops/count_zeros.h>
+
 /* You have to define the following before including this file:
  *
  * UWtype -- An unsigned type, default type for operations (typically a "word")
@@ -146,12 +148,6 @@ do { \
 	: "1" ((USItype)(n1)), \
 		"r" ((USItype)(n0)), \
 		"r" ((USItype)(d)))
-
-#define count_leading_zeros(count, x) \
-	__asm__ ("clz %0,%1" \
-	: "=r" ((USItype)(count)) \
-	: "r" ((USItype)(x)))
-#define COUNT_LEADING_ZEROS_0 32
 #endif /* __a29k__ */
 
 #if defined(__alpha) && W_TYPE_SIZE == 64
@@ -298,11 +294,6 @@ extern UDItype __udiv_qrnnd();
 	: "1" ((USItype)(nh)), \
 		"0" ((USItype)(nl)), \
 		"g" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-	__asm__ ("bsch/1 %1,%0" \
-	: "=g" (count) \
-	: "g" ((USItype)(x)), \
-	     "0" ((USItype)0))
 #endif
 
 /***************************************
@@ -354,27 +345,6 @@ do { USItype __r; \
 } while (0)
 extern USItype __udiv_qrnnd();
 #endif /* LONGLONG_STANDALONE */
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __tmp; \
-	__asm__ ( \
-	"ldi             1,%0\n" \
-	"extru,=	%1,15,16,%%r0  ; Bits 31..16 zero?\n" \
-	"extru,tr	%1,15,16,%1    ; No.  Shift down, skip add.\n" \
-	"ldo		16(%0),%0      ; Yes.	Perform add.\n" \
-	"extru,=	%1,23,8,%%r0   ; Bits 15..8 zero?\n" \
-	"extru,tr	%1,23,8,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		8(%0),%0       ; Yes.	Perform add.\n" \
-	"extru,=	%1,27,4,%%r0   ; Bits 7..4 zero?\n" \
-	"extru,tr	%1,27,4,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		4(%0),%0       ; Yes.	Perform add.\n" \
-	"extru,=	%1,29,2,%%r0   ; Bits 3..2 zero?\n" \
-	"extru,tr	%1,29,2,%1     ; No.  Shift down, skip add.\n" \
-	"ldo		2(%0),%0       ; Yes.	Perform add.\n" \
-	"extru		%1,30,1,%1     ; Extract bit 1.\n" \
-	"sub		%0,%1,%0       ; Subtract it.              " \
-	: "=r" (count), "=r" (__tmp) : "1" (x)); \
-} while (0)
 #endif /* hppa */
 
 /***************************************
@@ -457,15 +427,6 @@ do { \
 	: "0" ((USItype)(n0)), \
 	     "1" ((USItype)(n1)), \
 	     "rm" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("bsrl %1,%0" \
-	: "=r" (__cbtmp) : "rm" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define count_trailing_zeros(count, x) \
-	__asm__ ("bsfl %1,%0" : "=r" (count) : "rm" ((USItype)(x)))
 #ifndef UMUL_TIME
 #define UMUL_TIME 40
 #endif
@@ -536,15 +497,6 @@ do { \
 	     "dI" ((USItype)(d))); \
 	(r) = __rq.__i.__l; (q) = __rq.__i.__h; \
 } while (0)
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("scanbit %1,%0" \
-	: "=r" (__cbtmp) \
-	: "r" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define COUNT_LEADING_ZEROS_0 (-32)	/* sic */
 #if defined(__i960mx)		/* what is the proper symbol to test??? */
 #define rshift_rhlc(r, h, l, c) \
 do { \
@@ -603,11 +555,6 @@ do { \
 	: "0" ((USItype)(n0)), \
 	     "1" ((USItype)(n1)), \
 	     "dmi" ((USItype)(d)))
-#define count_leading_zeros(count, x) \
-	__asm__ ("bfffo %1{%b2:%b2},%0" \
-	: "=d" ((USItype)(count)) \
-	: "od" ((USItype)(x)), "n" (0))
-#define COUNT_LEADING_ZEROS_0 32
 #else /* not mc68020 */
 #define umul_ppmm(xh, xl, a, b) \
 do { USItype __umul_tmp1, __umul_tmp2; \
@@ -664,15 +611,6 @@ do { USItype __umul_tmp1, __umul_tmp2; \
 	     "rJ" ((USItype)(bh)), \
 	     "rJ" ((USItype)(al)), \
 	     "rJ" ((USItype)(bl)))
-#define count_leading_zeros(count, x) \
-do { \
-	USItype __cbtmp; \
-	__asm__ ("ff1 %0,%1" \
-	: "=r" (__cbtmp) \
-	: "r" ((USItype)(x))); \
-	(count) = __cbtmp ^ 31; \
-} while (0)
-#define COUNT_LEADING_ZEROS_0 63	/* sic */
 #if defined(__m88110__)
 #define umul_ppmm(wh, wl, u, v) \
 do { \
@@ -779,12 +717,6 @@ do { \
 	: "0" (__xx.__ll), \
 	     "g" ((USItype)(d))); \
 	(r) = __xx.__i.__l; (q) = __xx.__i.__h; })
-#define count_trailing_zeros(count, x) \
-do { \
-	__asm__("ffsd      %2,%0" \
-	: "=r"((USItype) (count)) \
-	: "0"((USItype) 0), "r"((USItype) (x))); \
-	} while (0)
 #endif /* __ns32000__ */
 
 /***************************************
@@ -855,11 +787,6 @@ do { \
 		"rI" ((USItype)(al)), \
 		"r" ((USItype)(bl))); \
 } while (0)
-#define count_leading_zeros(count, x) \
-	__asm__ ("{cntlz|cntlzw} %0,%1" \
-	: "=r" ((USItype)(count)) \
-	: "r" ((USItype)(x)))
-#define COUNT_LEADING_ZEROS_0 32
 #if defined(_ARCH_PPC)
 #define umul_ppmm(ph, pl, m0, m1) \
 do { \
@@ -1001,19 +928,6 @@ do { \
 } while (0)
 #define UMUL_TIME 20
 #define UDIV_TIME 200
-#define count_leading_zeros(count, x) \
-do { \
-	if ((x) >= 0x10000) \
-		__asm__ ("clz     %0,%1" \
-		: "=r" ((USItype)(count)) \
-		: "r" ((USItype)(x) >> 16)); \
-	else { \
-		__asm__ ("clz   %0,%1" \
-		: "=r" ((USItype)(count)) \
-		: "r" ((USItype)(x))); \
-		(count) += 16; \
-	} \
-} while (0)
 #endif /* RT/ROMP */
 
 /***************************************
@@ -1142,13 +1056,6 @@ do { \
 	"rI" ((USItype)(d)) \
 	: "%g1" __AND_CLOBBER_CC)
 #define UDIV_TIME 37
-#define count_leading_zeros(count, x) \
-	__asm__ ("scan %1,0,%0" \
-	: "=r" ((USItype)(x)) \
-	: "r" ((USItype)(count)))
-/* Early sparclites return 63 for an argument of 0, but they warn that future
-	implementations might change this.  Therefore, leave COUNT_LEADING_ZEROS_0
-	undefined.  */
 #endif /* __sparclite__ */
 #endif /* __sparc_v8__ */
 	/* Default to sparc v7 versions of umul_ppmm and udiv_qrnnd.  */
@@ -1454,47 +1361,6 @@ do { \
 #define udiv_qrnnd __udiv_qrnnd_c
 #endif
 
-#undef count_leading_zeros
-#if !defined(count_leading_zeros)
-	extern
-#ifdef __STDC__
-			const
-#endif
-			unsigned char __clz_tab[];
-#define count_leading_zeros(count, x) \
-do { \
-	UWtype __xr = (x); \
-	UWtype __a; \
-	\
-	if (W_TYPE_SIZE <= 32) { \
-		__a = __xr < ((UWtype) 1 << 2*__BITS4) \
-		? (__xr < ((UWtype) 1 << __BITS4) ? 0 : __BITS4) \
-		: (__xr < ((UWtype) 1 << 3*__BITS4) ?  2*__BITS4 : 3*__BITS4); \
-	} \
-	else { \
-		for (__a = W_TYPE_SIZE - 8; __a > 0; __a -= 8) \
-			if (((__xr >> __a) & 0xff) != 0) \
-				break; \
-	} \
-	\
-	(count) = W_TYPE_SIZE - (__clz_tab[__xr >> __a] + __a); \
-} while (0)
-	/* This version gives a well-defined value for zero. */
-#define COUNT_LEADING_ZEROS_0 W_TYPE_SIZE
-#endif
-
-#if !defined(count_trailing_zeros)
-/* Define count_trailing_zeros using count_leading_zeros.  The latter might be
-	defined in asm, but if it is not, the C version above is good enough.  */
-#define count_trailing_zeros(count, x) \
-do { \
-	UWtype __ctz_x = (x); \
-	UWtype __ctz_c; \
-	count_leading_zeros(__ctz_c, __ctz_x & -__ctz_x); \
-	(count) = W_TYPE_SIZE - 1 - __ctz_c; \
-} while (0)
-#endif
-
 #ifndef UDIV_NEEDS_NORMALIZATION
 #define UDIV_NEEDS_NORMALIZATION 0
 #endif
diff --git a/lib/mpi/mpi-bit.c b/lib/mpi/mpi-bit.c
index 568724804f29..503537e08436 100644
--- a/lib/mpi/mpi-bit.c
+++ b/lib/mpi/mpi-bit.c
@@ -45,7 +45,7 @@ unsigned mpi_get_nbits(MPI a)
 	if (a->nlimbs) {
 		mpi_limb_t alimb = a->d[a->nlimbs - 1];
 		if (alimb)
-			count_leading_zeros(n, alimb);
+			n = count_leading_zeros(alimb);
 		else
 			n = BITS_PER_MPI_LIMB;
 		n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
diff --git a/lib/mpi/mpi-pow.c b/lib/mpi/mpi-pow.c
index 67f3e79af914..5464c8744ea9 100644
--- a/lib/mpi/mpi-pow.c
+++ b/lib/mpi/mpi-pow.c
@@ -77,7 +77,7 @@ int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
 	mp = mp_marker = mpi_alloc_limb_space(msize);
 	if (!mp)
 		goto enomem;
-	count_leading_zeros(mod_shift_cnt, mod->d[msize - 1]);
+	mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);
 	if (mod_shift_cnt)
 		mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);
 	else
@@ -169,7 +169,7 @@ int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
 
 		i = esize - 1;
 		e = ep[i];
-		count_leading_zeros(c, e);
+		c = count_leading_zeros(e);
 		e = (e << c) << 1;	/* shift the exp bits to the left, lose msb */
 		c = BITS_PER_MPI_LIMB - 1 - c;
 
-- 
cgit v1.2.3-59-g8ed1b


From 964f3b3bf49eb84b5831121446a28b76de3fb23a Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Thu, 13 Sep 2012 15:17:21 +0100
Subject: KEYS: Implement asymmetric key type

Create a key type that can be used to represent an asymmetric key type for use
in appropriate cryptographic operations, such as encryption, decryption,
signature generation and signature verification.

The key type is "asymmetric" and can provide access to a variety of
cryptographic algorithms.

Possibly, this would be better as "public_key" - but that has the disadvantage
that "public key" is an overloaded term.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 crypto/Kconfig                           |   1 +
 crypto/Makefile                          |   1 +
 crypto/asymmetric_keys/Kconfig           |  13 +++
 crypto/asymmetric_keys/Makefile          |   7 ++
 crypto/asymmetric_keys/asymmetric_keys.h |  15 +++
 crypto/asymmetric_keys/asymmetric_type.c | 156 +++++++++++++++++++++++++++++++
 include/keys/asymmetric-subtype.h        |  55 +++++++++++
 include/keys/asymmetric-type.h           |  25 +++++
 8 files changed, 273 insertions(+)
 create mode 100644 crypto/asymmetric_keys/Kconfig
 create mode 100644 crypto/asymmetric_keys/Makefile
 create mode 100644 crypto/asymmetric_keys/asymmetric_keys.h
 create mode 100644 crypto/asymmetric_keys/asymmetric_type.c
 create mode 100644 include/keys/asymmetric-subtype.h
 create mode 100644 include/keys/asymmetric-type.h

(limited to 'include')

diff --git a/crypto/Kconfig b/crypto/Kconfig
index a3238051b03e..1ca0b246f29f 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -1043,5 +1043,6 @@ config CRYPTO_USER_API_SKCIPHER
 	  key cipher algorithms.
 
 source "drivers/crypto/Kconfig"
+source crypto/asymmetric_keys/Kconfig
 
 endif	# if CRYPTO
diff --git a/crypto/Makefile b/crypto/Makefile
index 30f33d675330..ced472e18fc3 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -96,3 +96,4 @@ obj-$(CONFIG_CRYPTO_USER_API_SKCIPHER) += algif_skcipher.o
 #
 obj-$(CONFIG_XOR_BLOCKS) += xor.o
 obj-$(CONFIG_ASYNC_CORE) += async_tx/
+obj-$(CONFIG_ASYMMETRIC_KEY_TYPE) += asymmetric_keys/
diff --git a/crypto/asymmetric_keys/Kconfig b/crypto/asymmetric_keys/Kconfig
new file mode 100644
index 000000000000..cad29b3efa0e
--- /dev/null
+++ b/crypto/asymmetric_keys/Kconfig
@@ -0,0 +1,13 @@
+menuconfig ASYMMETRIC_KEY_TYPE
+	tristate "Asymmetric (public-key cryptographic) key type"
+	depends on KEYS
+	help
+	  This option provides support for a key type that holds the data for
+	  the asymmetric keys used for public key cryptographic operations such
+	  as encryption, decryption, signature generation and signature
+	  verification.
+
+if ASYMMETRIC_KEY_TYPE
+
+
+endif # ASYMMETRIC_KEY_TYPE
diff --git a/crypto/asymmetric_keys/Makefile b/crypto/asymmetric_keys/Makefile
new file mode 100644
index 000000000000..b725bcce4cfd
--- /dev/null
+++ b/crypto/asymmetric_keys/Makefile
@@ -0,0 +1,7 @@
+#
+# Makefile for asymmetric cryptographic keys
+#
+
+obj-$(CONFIG_ASYMMETRIC_KEY_TYPE) += asymmetric_keys.o
+
+asymmetric_keys-y := asymmetric_type.o
diff --git a/crypto/asymmetric_keys/asymmetric_keys.h b/crypto/asymmetric_keys/asymmetric_keys.h
new file mode 100644
index 000000000000..515b63430812
--- /dev/null
+++ b/crypto/asymmetric_keys/asymmetric_keys.h
@@ -0,0 +1,15 @@
+/* Internal definitions for asymmetric key type
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+static inline const char *asymmetric_key_id(const struct key *key)
+{
+	return key->type_data.p[1];
+}
diff --git a/crypto/asymmetric_keys/asymmetric_type.c b/crypto/asymmetric_keys/asymmetric_type.c
new file mode 100644
index 000000000000..bfb0424026aa
--- /dev/null
+++ b/crypto/asymmetric_keys/asymmetric_type.c
@@ -0,0 +1,156 @@
+/* Asymmetric public-key cryptography key type
+ *
+ * See Documentation/security/asymmetric-keys.txt
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+#include <keys/asymmetric-subtype.h>
+#include <linux/seq_file.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include "asymmetric_keys.h"
+
+MODULE_LICENSE("GPL");
+
+/*
+ * Match asymmetric keys on (part of) their name
+ * We have some shorthand methods for matching keys.  We allow:
+ *
+ *	"<desc>"	- request a key by description
+ *	"id:<id>"	- request a key matching the ID
+ *	"<subtype>:<id>" - request a key of a subtype
+ */
+static int asymmetric_key_match(const struct key *key, const void *description)
+{
+	const struct asymmetric_key_subtype *subtype = asymmetric_key_subtype(key);
+	const char *spec = description;
+	const char *id, *kid;
+	ptrdiff_t speclen;
+	size_t idlen, kidlen;
+
+	if (!subtype || !spec || !*spec)
+		return 0;
+
+	/* See if the full key description matches as is */
+	if (key->description && strcmp(key->description, description) == 0)
+		return 1;
+
+	/* All tests from here on break the criterion description into a
+	 * specifier, a colon and then an identifier.
+	 */
+	id = strchr(spec, ':');
+	if (!id)
+		return 0;
+
+	speclen = id - spec;
+	id++;
+
+	/* Anything after here requires a partial match on the ID string */
+	kid = asymmetric_key_id(key);
+	if (!kid)
+		return 0;
+
+	idlen = strlen(id);
+	kidlen = strlen(kid);
+	if (idlen > kidlen)
+		return 0;
+
+	kid += kidlen - idlen;
+	if (strcasecmp(id, kid) != 0)
+		return 0;
+
+	if (speclen == 2 &&
+	    memcmp(spec, "id", 2) == 0)
+		return 1;
+
+	if (speclen == subtype->name_len &&
+	    memcmp(spec, subtype->name, speclen) == 0)
+		return 1;
+
+	return 0;
+}
+
+/*
+ * Describe the asymmetric key
+ */
+static void asymmetric_key_describe(const struct key *key, struct seq_file *m)
+{
+	const struct asymmetric_key_subtype *subtype = asymmetric_key_subtype(key);
+	const char *kid = asymmetric_key_id(key);
+	size_t n;
+
+	seq_puts(m, key->description);
+
+	if (subtype) {
+		seq_puts(m, ": ");
+		subtype->describe(key, m);
+
+		if (kid) {
+			seq_putc(m, ' ');
+			n = strlen(kid);
+			if (n <= 8)
+				seq_puts(m, kid);
+			else
+				seq_puts(m, kid + n - 8);
+		}
+
+		seq_puts(m, " [");
+		/* put something here to indicate the key's capabilities */
+		seq_putc(m, ']');
+	}
+}
+
+/*
+ * Instantiate a asymmetric_key defined key.  The key was preparsed, so we just
+ * have to transfer the data here.
+ */
+static int asymmetric_key_instantiate(struct key *key, struct key_preparsed_payload *prep)
+{
+	return -EOPNOTSUPP;
+}
+
+/*
+ * dispose of the data dangling from the corpse of a asymmetric key
+ */
+static void asymmetric_key_destroy(struct key *key)
+{
+	struct asymmetric_key_subtype *subtype = asymmetric_key_subtype(key);
+	if (subtype) {
+		subtype->destroy(key->payload.data);
+		module_put(subtype->owner);
+		key->type_data.p[0] = NULL;
+	}
+	kfree(key->type_data.p[1]);
+	key->type_data.p[1] = NULL;
+}
+
+struct key_type key_type_asymmetric = {
+	.name		= "asymmetric",
+	.instantiate	= asymmetric_key_instantiate,
+	.match		= asymmetric_key_match,
+	.destroy	= asymmetric_key_destroy,
+	.describe	= asymmetric_key_describe,
+};
+EXPORT_SYMBOL_GPL(key_type_asymmetric);
+
+/*
+ * Module stuff
+ */
+static int __init asymmetric_key_init(void)
+{
+	return register_key_type(&key_type_asymmetric);
+}
+
+static void __exit asymmetric_key_cleanup(void)
+{
+	unregister_key_type(&key_type_asymmetric);
+}
+
+module_init(asymmetric_key_init);
+module_exit(asymmetric_key_cleanup);
diff --git a/include/keys/asymmetric-subtype.h b/include/keys/asymmetric-subtype.h
new file mode 100644
index 000000000000..4b840e822209
--- /dev/null
+++ b/include/keys/asymmetric-subtype.h
@@ -0,0 +1,55 @@
+/* Asymmetric public-key cryptography key subtype
+ *
+ * See Documentation/security/asymmetric-keys.txt
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _KEYS_ASYMMETRIC_SUBTYPE_H
+#define _KEYS_ASYMMETRIC_SUBTYPE_H
+
+#include <linux/seq_file.h>
+#include <keys/asymmetric-type.h>
+
+struct public_key_signature;
+
+/*
+ * Keys of this type declare a subtype that indicates the handlers and
+ * capabilities.
+ */
+struct asymmetric_key_subtype {
+	struct module		*owner;
+	const char		*name;
+	unsigned short		name_len;	/* length of name */
+
+	/* Describe a key of this subtype for /proc/keys */
+	void (*describe)(const struct key *key, struct seq_file *m);
+
+	/* Destroy a key of this subtype */
+	void (*destroy)(void *payload);
+
+	/* Verify the signature on a key of this subtype (optional) */
+	int (*verify_signature)(const struct key *key,
+				const struct public_key_signature *sig);
+};
+
+/**
+ * asymmetric_key_subtype - Get the subtype from an asymmetric key
+ * @key: The key of interest.
+ *
+ * Retrieves and returns the subtype pointer of the asymmetric key from the
+ * type-specific data attached to the key.
+ */
+static inline
+struct asymmetric_key_subtype *asymmetric_key_subtype(const struct key *key)
+{
+	return key->type_data.p[0];
+}
+
+#endif /* _KEYS_ASYMMETRIC_SUBTYPE_H */
diff --git a/include/keys/asymmetric-type.h b/include/keys/asymmetric-type.h
new file mode 100644
index 000000000000..7dd473496180
--- /dev/null
+++ b/include/keys/asymmetric-type.h
@@ -0,0 +1,25 @@
+/* Asymmetric Public-key cryptography key type interface
+ *
+ * See Documentation/security/asymmetric-keys.txt
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _KEYS_ASYMMETRIC_TYPE_H
+#define _KEYS_ASYMMETRIC_TYPE_H
+
+#include <linux/key-type.h>
+
+extern struct key_type key_type_asymmetric;
+
+/*
+ * The payload is at the discretion of the subtype.
+ */
+
+#endif /* _KEYS_ASYMMETRIC_TYPE_H */
-- 
cgit v1.2.3-59-g8ed1b


From 46c6f1776e2f53eebb1fc361946877bab7533227 Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Thu, 13 Sep 2012 15:17:32 +0100
Subject: KEYS: Asymmetric key pluggable data parsers

The instantiation data passed to the asymmetric key type are expected to be
formatted in some way, and there are several possible standard ways to format
the data.

The two obvious standards are OpenPGP keys and X.509 certificates.  The latter
is especially useful when dealing with UEFI, and the former might be useful
when dealing with, say, eCryptfs.

Further, it might be desirable to provide formatted blobs that indicate
hardware is to be accessed to retrieve the keys or that the keys live
unretrievably in a hardware store, but that the keys can be used by means of
the hardware.

From userspace, the keys can be loaded using the keyctl command, for example,
an X.509 binary certificate:

	keyctl padd asymmetric foo @s <dhowells.pem

or a PGP key:

	keyctl padd asymmetric bar @s <dhowells.pub

or a pointer into the contents of the TPM:

	keyctl add asymmetric zebra "TPM:04982390582905f8" @s

Inside the kernel, pluggable parsers register themselves and then get to
examine the payload data to see if they can handle it.  If they can, they get
to:

  (1) Propose a name for the key, to be used it the name is "" or NULL.

  (2) Specify the key subtype.

  (3) Provide the data for the subtype.

The key type asks the parser to do its stuff before a key is allocated and thus
before the name is set.  If successful, the parser stores the suggested data
into the key_preparsed_payload struct, which will be either used (if the key is
successfully created and instantiated or updated) or discarded.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 crypto/asymmetric_keys/asymmetric_type.c | 120 ++++++++++++++++++++++++++++++-
 include/keys/asymmetric-parser.h         |  37 ++++++++++
 2 files changed, 156 insertions(+), 1 deletion(-)
 create mode 100644 include/keys/asymmetric-parser.h

(limited to 'include')

diff --git a/crypto/asymmetric_keys/asymmetric_type.c b/crypto/asymmetric_keys/asymmetric_type.c
index bfb0424026aa..cf807654d221 100644
--- a/crypto/asymmetric_keys/asymmetric_type.c
+++ b/crypto/asymmetric_keys/asymmetric_type.c
@@ -11,6 +11,7 @@
  * 2 of the Licence, or (at your option) any later version.
  */
 #include <keys/asymmetric-subtype.h>
+#include <keys/asymmetric-parser.h>
 #include <linux/seq_file.h>
 #include <linux/module.h>
 #include <linux/slab.h>
@@ -18,6 +19,9 @@
 
 MODULE_LICENSE("GPL");
 
+static LIST_HEAD(asymmetric_key_parsers);
+static DECLARE_RWSEM(asymmetric_key_parsers_sem);
+
 /*
  * Match asymmetric keys on (part of) their name
  * We have some shorthand methods for matching keys.  We allow:
@@ -106,13 +110,80 @@ static void asymmetric_key_describe(const struct key *key, struct seq_file *m)
 	}
 }
 
+/*
+ * Preparse a asymmetric payload to get format the contents appropriately for the
+ * internal payload to cut down on the number of scans of the data performed.
+ *
+ * We also generate a proposed description from the contents of the key that
+ * can be used to name the key if the user doesn't want to provide one.
+ */
+static int asymmetric_key_preparse(struct key_preparsed_payload *prep)
+{
+	struct asymmetric_key_parser *parser;
+	int ret;
+
+	pr_devel("==>%s()\n", __func__);
+
+	if (prep->datalen == 0)
+		return -EINVAL;
+
+	down_read(&asymmetric_key_parsers_sem);
+
+	ret = -EBADMSG;
+	list_for_each_entry(parser, &asymmetric_key_parsers, link) {
+		pr_debug("Trying parser '%s'\n", parser->name);
+
+		ret = parser->parse(prep);
+		if (ret != -EBADMSG) {
+			pr_debug("Parser recognised the format (ret %d)\n",
+				 ret);
+			break;
+		}
+	}
+
+	up_read(&asymmetric_key_parsers_sem);
+	pr_devel("<==%s() = %d\n", __func__, ret);
+	return ret;
+}
+
+/*
+ * Clean up the preparse data
+ */
+static void asymmetric_key_free_preparse(struct key_preparsed_payload *prep)
+{
+	struct asymmetric_key_subtype *subtype = prep->type_data[0];
+
+	pr_devel("==>%s()\n", __func__);
+
+	if (subtype) {
+		subtype->destroy(prep->payload);
+		module_put(subtype->owner);
+	}
+	kfree(prep->type_data[1]);
+	kfree(prep->description);
+}
+
 /*
  * Instantiate a asymmetric_key defined key.  The key was preparsed, so we just
  * have to transfer the data here.
  */
 static int asymmetric_key_instantiate(struct key *key, struct key_preparsed_payload *prep)
 {
-	return -EOPNOTSUPP;
+	int ret;
+
+	pr_devel("==>%s()\n", __func__);
+
+	ret = key_payload_reserve(key, prep->quotalen);
+	if (ret == 0) {
+		key->type_data.p[0] = prep->type_data[0];
+		key->type_data.p[1] = prep->type_data[1];
+		key->payload.data = prep->payload;
+		prep->type_data[0] = NULL;
+		prep->type_data[1] = NULL;
+		prep->payload = NULL;
+	}
+	pr_devel("<==%s() = %d\n", __func__, ret);
+	return ret;
 }
 
 /*
@@ -132,6 +203,8 @@ static void asymmetric_key_destroy(struct key *key)
 
 struct key_type key_type_asymmetric = {
 	.name		= "asymmetric",
+	.preparse	= asymmetric_key_preparse,
+	.free_preparse	= asymmetric_key_free_preparse,
 	.instantiate	= asymmetric_key_instantiate,
 	.match		= asymmetric_key_match,
 	.destroy	= asymmetric_key_destroy,
@@ -139,6 +212,51 @@ struct key_type key_type_asymmetric = {
 };
 EXPORT_SYMBOL_GPL(key_type_asymmetric);
 
+/**
+ * register_asymmetric_key_parser - Register a asymmetric key blob parser
+ * @parser: The parser to register
+ */
+int register_asymmetric_key_parser(struct asymmetric_key_parser *parser)
+{
+	struct asymmetric_key_parser *cursor;
+	int ret;
+
+	down_write(&asymmetric_key_parsers_sem);
+
+	list_for_each_entry(cursor, &asymmetric_key_parsers, link) {
+		if (strcmp(cursor->name, parser->name) == 0) {
+			pr_err("Asymmetric key parser '%s' already registered\n",
+			       parser->name);
+			ret = -EEXIST;
+			goto out;
+		}
+	}
+
+	list_add_tail(&parser->link, &asymmetric_key_parsers);
+
+	pr_notice("Asymmetric key parser '%s' registered\n", parser->name);
+	ret = 0;
+
+out:
+	up_write(&asymmetric_key_parsers_sem);
+	return ret;
+}
+EXPORT_SYMBOL_GPL(register_asymmetric_key_parser);
+
+/**
+ * unregister_asymmetric_key_parser - Unregister a asymmetric key blob parser
+ * @parser: The parser to unregister
+ */
+void unregister_asymmetric_key_parser(struct asymmetric_key_parser *parser)
+{
+	down_write(&asymmetric_key_parsers_sem);
+	list_del(&parser->link);
+	up_write(&asymmetric_key_parsers_sem);
+
+	pr_notice("Asymmetric key parser '%s' unregistered\n", parser->name);
+}
+EXPORT_SYMBOL_GPL(unregister_asymmetric_key_parser);
+
 /*
  * Module stuff
  */
diff --git a/include/keys/asymmetric-parser.h b/include/keys/asymmetric-parser.h
new file mode 100644
index 000000000000..09b3b4807f5c
--- /dev/null
+++ b/include/keys/asymmetric-parser.h
@@ -0,0 +1,37 @@
+/* Asymmetric public-key cryptography data parser
+ *
+ * See Documentation/crypto/asymmetric-keys.txt
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _KEYS_ASYMMETRIC_PARSER_H
+#define _KEYS_ASYMMETRIC_PARSER_H
+
+/*
+ * Key data parser.  Called during key instantiation.
+ */
+struct asymmetric_key_parser {
+	struct list_head	link;
+	struct module		*owner;
+	const char		*name;
+
+	/* Attempt to parse a key from the data blob passed to add_key() or
+	 * keyctl_instantiate().  Should also generate a proposed description
+	 * that the caller can optionally use for the key.
+	 *
+	 * Return EBADMSG if not recognised.
+	 */
+	int (*parse)(struct key_preparsed_payload *prep);
+};
+
+extern int register_asymmetric_key_parser(struct asymmetric_key_parser *);
+extern void unregister_asymmetric_key_parser(struct asymmetric_key_parser *);
+
+#endif /* _KEYS_ASYMMETRIC_PARSER_H */
-- 
cgit v1.2.3-59-g8ed1b


From a9681bf3dd7ccd2b32eba27d327ab76607429f7a Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Fri, 21 Sep 2012 23:24:55 +0100
Subject: KEYS: Asymmetric public-key algorithm crypto key subtype

Add a subtype for supporting asymmetric public-key encryption algorithms such
as DSA (FIPS-186) and RSA (PKCS#1 / RFC1337).

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 crypto/asymmetric_keys/Kconfig      |   8 +++
 crypto/asymmetric_keys/Makefile     |   2 +
 crypto/asymmetric_keys/public_key.c | 108 ++++++++++++++++++++++++++++++++++++
 crypto/asymmetric_keys/public_key.h |  28 ++++++++++
 include/crypto/public_key.h         | 104 ++++++++++++++++++++++++++++++++++
 5 files changed, 250 insertions(+)
 create mode 100644 crypto/asymmetric_keys/public_key.c
 create mode 100644 crypto/asymmetric_keys/public_key.h
 create mode 100644 include/crypto/public_key.h

(limited to 'include')

diff --git a/crypto/asymmetric_keys/Kconfig b/crypto/asymmetric_keys/Kconfig
index cad29b3efa0e..bbfccaa35293 100644
--- a/crypto/asymmetric_keys/Kconfig
+++ b/crypto/asymmetric_keys/Kconfig
@@ -9,5 +9,13 @@ menuconfig ASYMMETRIC_KEY_TYPE
 
 if ASYMMETRIC_KEY_TYPE
 
+config ASYMMETRIC_PUBLIC_KEY_SUBTYPE
+	tristate "Asymmetric public-key crypto algorithm subtype"
+	select MPILIB
+	help
+	  This option provides support for asymmetric public key type handling.
+	  If signature generation and/or verification are to be used,
+	  appropriate hash algorithms (such as SHA-1) must be available.
+	  ENOPKG will be reported if the requisite algorithm is unavailable.
 
 endif # ASYMMETRIC_KEY_TYPE
diff --git a/crypto/asymmetric_keys/Makefile b/crypto/asymmetric_keys/Makefile
index b725bcce4cfd..5ed46eecb299 100644
--- a/crypto/asymmetric_keys/Makefile
+++ b/crypto/asymmetric_keys/Makefile
@@ -5,3 +5,5 @@
 obj-$(CONFIG_ASYMMETRIC_KEY_TYPE) += asymmetric_keys.o
 
 asymmetric_keys-y := asymmetric_type.o
+
+obj-$(CONFIG_ASYMMETRIC_PUBLIC_KEY_SUBTYPE) += public_key.o
diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/public_key.c
new file mode 100644
index 000000000000..cb2e29180a87
--- /dev/null
+++ b/crypto/asymmetric_keys/public_key.c
@@ -0,0 +1,108 @@
+/* In-software asymmetric public-key crypto subtype
+ *
+ * See Documentation/crypto/asymmetric-keys.txt
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#define pr_fmt(fmt) "PKEY: "fmt
+#include <linux/module.h>
+#include <linux/export.h>
+#include <linux/kernel.h>
+#include <linux/slab.h>
+#include <linux/seq_file.h>
+#include <keys/asymmetric-subtype.h>
+#include "public_key.h"
+
+MODULE_LICENSE("GPL");
+
+const char *const pkey_algo[PKEY_ALGO__LAST] = {
+	[PKEY_ALGO_DSA]		= "DSA",
+	[PKEY_ALGO_RSA]		= "RSA",
+};
+EXPORT_SYMBOL_GPL(pkey_algo);
+
+const char *const pkey_hash_algo[PKEY_HASH__LAST] = {
+	[PKEY_HASH_MD4]		= "md4",
+	[PKEY_HASH_MD5]		= "md5",
+	[PKEY_HASH_SHA1]	= "sha1",
+	[PKEY_HASH_RIPE_MD_160]	= "rmd160",
+	[PKEY_HASH_SHA256]	= "sha256",
+	[PKEY_HASH_SHA384]	= "sha384",
+	[PKEY_HASH_SHA512]	= "sha512",
+	[PKEY_HASH_SHA224]	= "sha224",
+};
+EXPORT_SYMBOL_GPL(pkey_hash_algo);
+
+const char *const pkey_id_type[PKEY_ID_TYPE__LAST] = {
+	[PKEY_ID_PGP]		= "PGP",
+	[PKEY_ID_X509]		= "X509",
+};
+EXPORT_SYMBOL_GPL(pkey_id_type);
+
+/*
+ * Provide a part of a description of the key for /proc/keys.
+ */
+static void public_key_describe(const struct key *asymmetric_key,
+				struct seq_file *m)
+{
+	struct public_key *key = asymmetric_key->payload.data;
+
+	if (key)
+		seq_printf(m, "%s.%s",
+			   pkey_id_type[key->id_type], key->algo->name);
+}
+
+/*
+ * Destroy a public key algorithm key.
+ */
+void public_key_destroy(void *payload)
+{
+	struct public_key *key = payload;
+	int i;
+
+	if (key) {
+		for (i = 0; i < ARRAY_SIZE(key->mpi); i++)
+			mpi_free(key->mpi[i]);
+		kfree(key);
+	}
+}
+EXPORT_SYMBOL_GPL(public_key_destroy);
+
+/*
+ * Verify a signature using a public key.
+ */
+static int public_key_verify_signature(const struct key *key,
+				       const struct public_key_signature *sig)
+{
+	const struct public_key *pk = key->payload.data;
+
+	if (!pk->algo->verify_signature)
+		return -ENOTSUPP;
+
+	if (sig->nr_mpi != pk->algo->n_sig_mpi) {
+		pr_debug("Signature has %u MPI not %u\n",
+			 sig->nr_mpi, pk->algo->n_sig_mpi);
+		return -EINVAL;
+	}
+
+	return pk->algo->verify_signature(pk, sig);
+}
+
+/*
+ * Public key algorithm asymmetric key subtype
+ */
+struct asymmetric_key_subtype public_key_subtype = {
+	.owner			= THIS_MODULE,
+	.name			= "public_key",
+	.describe		= public_key_describe,
+	.destroy		= public_key_destroy,
+	.verify_signature	= public_key_verify_signature,
+};
+EXPORT_SYMBOL_GPL(public_key_subtype);
diff --git a/crypto/asymmetric_keys/public_key.h b/crypto/asymmetric_keys/public_key.h
new file mode 100644
index 000000000000..1f86aad31003
--- /dev/null
+++ b/crypto/asymmetric_keys/public_key.h
@@ -0,0 +1,28 @@
+/* Public key algorithm internals
+ *
+ * See Documentation/crypto/asymmetric-keys.txt
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <crypto/public_key.h>
+
+extern struct asymmetric_key_subtype public_key_subtype;
+
+/*
+ * Public key algorithm definition.
+ */
+struct public_key_algorithm {
+	const char	*name;
+	u8		n_pub_mpi;	/* Number of MPIs in public key */
+	u8		n_sec_mpi;	/* Number of MPIs in secret key */
+	u8		n_sig_mpi;	/* Number of MPIs in a signature */
+	int (*verify_signature)(const struct public_key *key,
+				const struct public_key_signature *sig);
+};
diff --git a/include/crypto/public_key.h b/include/crypto/public_key.h
new file mode 100644
index 000000000000..4b8b6c16eac6
--- /dev/null
+++ b/include/crypto/public_key.h
@@ -0,0 +1,104 @@
+/* Asymmetric public-key algorithm definitions
+ *
+ * See Documentation/crypto/asymmetric-keys.txt
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _LINUX_PUBLIC_KEY_H
+#define _LINUX_PUBLIC_KEY_H
+
+#include <linux/mpi.h>
+
+enum pkey_algo {
+	PKEY_ALGO_DSA,
+	PKEY_ALGO_RSA,
+	PKEY_ALGO__LAST
+};
+
+extern const char *const pkey_algo[PKEY_ALGO__LAST];
+
+enum pkey_hash_algo {
+	PKEY_HASH_MD4,
+	PKEY_HASH_MD5,
+	PKEY_HASH_SHA1,
+	PKEY_HASH_RIPE_MD_160,
+	PKEY_HASH_SHA256,
+	PKEY_HASH_SHA384,
+	PKEY_HASH_SHA512,
+	PKEY_HASH_SHA224,
+	PKEY_HASH__LAST
+};
+
+extern const char *const pkey_hash_algo[PKEY_HASH__LAST];
+
+enum pkey_id_type {
+	PKEY_ID_PGP,		/* OpenPGP generated key ID */
+	PKEY_ID_X509,		/* X.509 arbitrary subjectKeyIdentifier */
+	PKEY_ID_TYPE__LAST
+};
+
+extern const char *const pkey_id_type[PKEY_ID_TYPE__LAST];
+
+/*
+ * Cryptographic data for the public-key subtype of the asymmetric key type.
+ *
+ * Note that this may include private part of the key as well as the public
+ * part.
+ */
+struct public_key {
+	const struct public_key_algorithm *algo;
+	u8	capabilities;
+#define PKEY_CAN_ENCRYPT	0x01
+#define PKEY_CAN_DECRYPT	0x02
+#define PKEY_CAN_SIGN		0x04
+#define PKEY_CAN_VERIFY		0x08
+	enum pkey_id_type id_type : 8;
+	union {
+		MPI	mpi[5];
+		struct {
+			MPI	p;	/* DSA prime */
+			MPI	q;	/* DSA group order */
+			MPI	g;	/* DSA group generator */
+			MPI	y;	/* DSA public-key value = g^x mod p */
+			MPI	x;	/* DSA secret exponent (if present) */
+		} dsa;
+		struct {
+			MPI	n;	/* RSA public modulus */
+			MPI	e;	/* RSA public encryption exponent */
+			MPI	d;	/* RSA secret encryption exponent (if present) */
+			MPI	p;	/* RSA secret prime (if present) */
+			MPI	q;	/* RSA secret prime (if present) */
+		} rsa;
+	};
+};
+
+extern void public_key_destroy(void *payload);
+
+/*
+ * Public key cryptography signature data
+ */
+struct public_key_signature {
+	u8 *digest;
+	u8 digest_size;			/* Number of bytes in digest */
+	u8 nr_mpi;			/* Occupancy of mpi[] */
+	enum pkey_hash_algo pkey_hash_algo : 8;
+	union {
+		MPI mpi[2];
+		struct {
+			MPI s;		/* m^d mod n */
+		} rsa;
+		struct {
+			MPI r;
+			MPI s;
+		} dsa;
+	};
+};
+
+#endif /* _LINUX_PUBLIC_KEY_H */
-- 
cgit v1.2.3-59-g8ed1b


From 4ae71c1dce1e3d2270a0755988033e236b8e45d6 Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Fri, 21 Sep 2012 23:25:04 +0100
Subject: KEYS: Provide signature verification with an asymmetric key

Provide signature verification using an asymmetric-type key to indicate the
public key to be used.

The API is a single function that can be found in crypto/public_key.h:

	int verify_signature(const struct key *key,
			     const struct public_key_signature *sig)

The first argument is the appropriate key to be used and the second argument
is the parsed signature data:

	struct public_key_signature {
		u8 *digest;
		u16 digest_size;
		enum pkey_hash_algo pkey_hash_algo : 8;
		union {
			MPI mpi[2];
			struct {
				MPI s;		/* m^d mod n */
			} rsa;
			struct {
				MPI r;
				MPI s;
			} dsa;
		};
	};

This should be filled in prior to calling the function.  The hash algorithm
should already have been called and the hash finalised and the output should
be in a buffer pointed to by the 'digest' member.

Any extra data to be added to the hash by the hash format (eg. PGP) should
have been added by the caller prior to finalising the hash.

It is assumed that the signature is made up of a number of MPI values.  If an
algorithm becomes available for which this is not the case, the above structure
will have to change.

It is also assumed that it will have been checked that the signature algorithm
matches the key algorithm.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 crypto/asymmetric_keys/Makefile    |  2 +-
 crypto/asymmetric_keys/signature.c | 49 ++++++++++++++++++++++++++++++++++++++
 include/crypto/public_key.h        |  4 ++++
 3 files changed, 54 insertions(+), 1 deletion(-)
 create mode 100644 crypto/asymmetric_keys/signature.c

(limited to 'include')

diff --git a/crypto/asymmetric_keys/Makefile b/crypto/asymmetric_keys/Makefile
index 5ed46eecb299..8dcdf0cdb261 100644
--- a/crypto/asymmetric_keys/Makefile
+++ b/crypto/asymmetric_keys/Makefile
@@ -4,6 +4,6 @@
 
 obj-$(CONFIG_ASYMMETRIC_KEY_TYPE) += asymmetric_keys.o
 
-asymmetric_keys-y := asymmetric_type.o
+asymmetric_keys-y := asymmetric_type.o signature.o
 
 obj-$(CONFIG_ASYMMETRIC_PUBLIC_KEY_SUBTYPE) += public_key.o
diff --git a/crypto/asymmetric_keys/signature.c b/crypto/asymmetric_keys/signature.c
new file mode 100644
index 000000000000..50b3f880b4ff
--- /dev/null
+++ b/crypto/asymmetric_keys/signature.c
@@ -0,0 +1,49 @@
+/* Signature verification with an asymmetric key
+ *
+ * See Documentation/security/asymmetric-keys.txt
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <keys/asymmetric-subtype.h>
+#include <linux/module.h>
+#include <linux/err.h>
+#include <crypto/public_key.h>
+#include "asymmetric_keys.h"
+
+/**
+ * verify_signature - Initiate the use of an asymmetric key to verify a signature
+ * @key: The asymmetric key to verify against
+ * @sig: The signature to check
+ *
+ * Returns 0 if successful or else an error.
+ */
+int verify_signature(const struct key *key,
+		     const struct public_key_signature *sig)
+{
+	const struct asymmetric_key_subtype *subtype;
+	int ret;
+
+	pr_devel("==>%s()\n", __func__);
+
+	if (key->type != &key_type_asymmetric)
+		return -EINVAL;
+	subtype = asymmetric_key_subtype(key);
+	if (!subtype ||
+	    !key->payload.data)
+		return -EINVAL;
+	if (!subtype->verify_signature)
+		return -ENOTSUPP;
+
+	ret = subtype->verify_signature(key, sig);
+
+	pr_devel("<==%s() = %d\n", __func__, ret);
+	return ret;
+}
+EXPORT_SYMBOL_GPL(verify_signature);
diff --git a/include/crypto/public_key.h b/include/crypto/public_key.h
index 4b8b6c16eac6..f5b0224c9967 100644
--- a/include/crypto/public_key.h
+++ b/include/crypto/public_key.h
@@ -101,4 +101,8 @@ struct public_key_signature {
 	};
 };
 
+struct key;
+extern int verify_signature(const struct key *key,
+			    const struct public_key_signature *sig);
+
 #endif /* _LINUX_PUBLIC_KEY_H */
-- 
cgit v1.2.3-59-g8ed1b


From a77ad6ea0b0bb1f9d1f52ed494bd72a5fdde208e Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Fri, 21 Sep 2012 23:30:46 +0100
Subject: X.509: Implement simple static OID registry

Implement a simple static OID registry that allows the mapping of an encoded
OID to an enum value for ease of use.

The OID registry index enum appears in the:

	linux/oid_registry.h

header file.  A script generates the registry from lines in the header file
that look like:

	<sp*>OID_foo,<sp*>/*<sp*>1.2.3.4<sp*>*/

The actual OID is taken to be represented by the numbers with interpolated
dots in the comment.

All other lines in the header are ignored.

The registry is queries by calling:

	OID look_up_oid(const void *data, size_t datasize);

This returns a number from the registry enum representing the OID if found or
OID__NR if not.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 include/linux/oid_registry.h |  90 +++++++++++++++++++
 lib/.gitignore               |   2 +-
 lib/Kconfig                  |   5 ++
 lib/Makefile                 |  16 ++++
 lib/build_OID_registry       | 209 +++++++++++++++++++++++++++++++++++++++++++
 lib/oid_registry.c           |  89 ++++++++++++++++++
 6 files changed, 410 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/oid_registry.h
 create mode 100755 lib/build_OID_registry
 create mode 100644 lib/oid_registry.c

(limited to 'include')

diff --git a/include/linux/oid_registry.h b/include/linux/oid_registry.h
new file mode 100644
index 000000000000..5928546bf00a
--- /dev/null
+++ b/include/linux/oid_registry.h
@@ -0,0 +1,90 @@
+/* ASN.1 Object identifier (OID) registry
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _LINUX_OID_REGISTRY_H
+#define _LINUX_OID_REGISTRY_H
+
+#include <linux/types.h>
+
+/*
+ * OIDs are turned into these values if possible, or OID__NR if not held here.
+ *
+ * NOTE!  Do not mess with the format of each line as this is read by
+ *	  build_OID_registry.pl to generate the data for look_up_OID().
+ */
+enum OID {
+	OID_id_dsa_with_sha1,		/* 1.2.840.10030.4.3 */
+	OID_id_dsa,			/* 1.2.840.10040.4.1 */
+	OID_id_ecdsa_with_sha1,		/* 1.2.840.10045.4.1 */
+	OID_id_ecPublicKey,		/* 1.2.840.10045.2.1 */
+
+	/* PKCS#1 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1)} */
+	OID_rsaEncryption,		/* 1.2.840.113549.1.1.1 */
+	OID_md2WithRSAEncryption,	/* 1.2.840.113549.1.1.2 */
+	OID_md3WithRSAEncryption,	/* 1.2.840.113549.1.1.3 */
+	OID_md4WithRSAEncryption,	/* 1.2.840.113549.1.1.4 */
+	OID_sha1WithRSAEncryption,	/* 1.2.840.113549.1.1.5 */
+	OID_sha256WithRSAEncryption,	/* 1.2.840.113549.1.1.11 */
+	OID_sha384WithRSAEncryption,	/* 1.2.840.113549.1.1.12 */
+	OID_sha512WithRSAEncryption,	/* 1.2.840.113549.1.1.13 */
+	OID_sha224WithRSAEncryption,	/* 1.2.840.113549.1.1.14 */
+	/* PKCS#7 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-7(7)} */
+	OID_data,			/* 1.2.840.113549.1.7.1 */
+	OID_signed_data,		/* 1.2.840.113549.1.7.2 */
+	/* PKCS#9 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-9(9)} */
+	OID_email_address,		/* 1.2.840.113549.1.9.1 */
+	OID_content_type,		/* 1.2.840.113549.1.9.3 */
+	OID_messageDigest,		/* 1.2.840.113549.1.9.4 */
+	OID_signingTime,		/* 1.2.840.113549.1.9.5 */
+	OID_smimeCapabilites,		/* 1.2.840.113549.1.9.15 */
+	OID_smimeAuthenticatedAttrs,	/* 1.2.840.113549.1.9.16.2.11 */
+
+	/* {iso(1) member-body(2) us(840) rsadsi(113549) digestAlgorithm(2)} */
+	OID_md2,			/* 1.2.840.113549.2.2 */
+	OID_md4,			/* 1.2.840.113549.2.4 */
+	OID_md5,			/* 1.2.840.113549.2.5 */
+
+	OID_certAuthInfoAccess,		/* 1.3.6.1.5.5.7.1.1 */
+	OID_msOutlookExpress,		/* 1.3.6.1.4.1.311.16.4 */
+	OID_sha1,			/* 1.3.14.3.2.26 */
+
+	/* Distinguished Name attribute IDs [RFC 2256] */
+	OID_commonName,			/* 2.5.4.3 */
+	OID_surname,			/* 2.5.4.4 */
+	OID_countryName,		/* 2.5.4.6 */
+	OID_locality,			/* 2.5.4.7 */
+	OID_stateOrProvinceName,	/* 2.5.4.8 */
+	OID_organizationName,		/* 2.5.4.10 */
+	OID_organizationUnitName,	/* 2.5.4.11 */
+	OID_title,			/* 2.5.4.12 */
+	OID_description,		/* 2.5.4.13 */
+	OID_name,			/* 2.5.4.41 */
+	OID_givenName,			/* 2.5.4.42 */
+	OID_initials,			/* 2.5.4.43 */
+	OID_generationalQualifier,	/* 2.5.4.44 */
+
+	/* Certificate extension IDs */
+	OID_subjectKeyIdentifier,	/* 2.5.29.14 */
+	OID_keyUsage,			/* 2.5.29.15 */
+	OID_subjectAltName,		/* 2.5.29.17 */
+	OID_issuerAltName,		/* 2.5.29.18 */
+	OID_basicConstraints,		/* 2.5.29.19 */
+	OID_crlDistributionPoints,	/* 2.5.29.31 */
+	OID_certPolicies,		/* 2.5.29.32 */
+	OID_authorityKeyIdentifier,	/* 2.5.29.35 */
+	OID_extKeyUsage,		/* 2.5.29.37 */
+
+	OID__NR
+};
+
+extern enum OID look_up_OID(const void *data, size_t datasize);
+
+#endif /* _LINUX_OID_REGISTRY_H */
diff --git a/lib/.gitignore b/lib/.gitignore
index 3bef1ea94c99..09aae85418ab 100644
--- a/lib/.gitignore
+++ b/lib/.gitignore
@@ -3,4 +3,4 @@
 #
 gen_crc32table
 crc32table.h
-
+oid_registry_data.c
diff --git a/lib/Kconfig b/lib/Kconfig
index bb94c1ba616a..4b31a46fb307 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -396,4 +396,9 @@ config SIGNATURE
 config LIBFDT
 	bool
 
+config OID_REGISTRY
+	tristate
+	help
+	  Enable fast lookup object identifier registry.
+
 endmenu
diff --git a/lib/Makefile b/lib/Makefile
index 42d283edc4d3..b0428960939f 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -150,3 +150,19 @@ quiet_cmd_crc32 = GEN     $@
 
 $(obj)/crc32table.h: $(obj)/gen_crc32table
 	$(call cmd,crc32)
+
+#
+# Build a fast OID lookip registry from include/linux/oid_registry.h
+#
+obj-$(CONFIG_OID_REGISTRY) += oid_registry.o
+
+$(obj)/oid_registry.c: $(obj)/oid_registry_data.c
+
+$(obj)/oid_registry_data.c: $(srctree)/include/linux/oid_registry.h \
+			    $(src)/build_OID_registry
+	$(call cmd,build_OID_registry)
+
+quiet_cmd_build_OID_registry = GEN     $@
+      cmd_build_OID_registry = perl $(srctree)/$(src)/build_OID_registry $< $@
+
+clean-files	+= oid_registry_data.c
diff --git a/lib/build_OID_registry b/lib/build_OID_registry
new file mode 100755
index 000000000000..dfbdaab81bc8
--- /dev/null
+++ b/lib/build_OID_registry
@@ -0,0 +1,209 @@
+#!/usr/bin/perl -w
+#
+# Build a static ASN.1 Object Identified (OID) registry
+#
+# Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+# Written by David Howells (dhowells@redhat.com)
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public Licence
+# as published by the Free Software Foundation; either version
+# 2 of the Licence, or (at your option) any later version.
+#
+
+use strict;
+
+my @names = ();
+my @oids = ();
+
+if ($#ARGV != 1) {
+    print STDERR "Format: ", $0, " <in-h-file> <out-c-file>\n";
+    exit(2);
+}
+
+#
+# Open the file to read from
+#
+open IN_FILE, "<$ARGV[0]" || die;
+while (<IN_FILE>) {
+    chomp;
+    if (m!\s+OID_([a-zA-z][a-zA-Z0-9_]+),\s+/[*]\s+([012][.0-9]*)\s+[*]/!) {
+	push @names, $1;
+	push @oids, $2;
+    }
+}
+close IN_FILE || die;
+
+#
+# Open the files to write into
+#
+open C_FILE, ">$ARGV[1]" or die;
+print C_FILE "/*\n";
+print C_FILE " * Automatically generated by ", $0, ".  Do not edit\n";
+print C_FILE " */\n";
+
+#
+# Split the data up into separate lists and also determine the lengths of the
+# encoded data arrays.
+#
+my @indices = ();
+my @lengths = ();
+my $total_length = 0;
+
+print "Compiling ", $#names + 1, " OIDs\n";
+
+for (my $i = 0; $i <= $#names; $i++) {
+    my $name = $names[$i];
+    my $oid = $oids[$i];
+
+    my @components = split(/[.]/, $oid);
+
+    # Determine the encoded length of this OID
+    my $size = $#components;
+    for (my $loop = 2; $loop <= $#components; $loop++) {
+	my $c = $components[$loop];
+
+	# We will base128 encode the number
+	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
+	$tmp = int($tmp / 7);
+	$size += $tmp;
+    }
+    push @lengths, $size;
+    push @indices, $total_length;
+    $total_length += $size;
+}
+
+#
+# Emit the look-up-by-OID index table
+#
+print C_FILE "\n";
+if ($total_length <= 255) {
+    print C_FILE "static const unsigned char oid_index[OID__NR + 1] = {\n";
+} else {
+    print C_FILE "static const unsigned short oid_index[OID__NR + 1] = {\n";
+}
+for (my $i = 0; $i <= $#names; $i++) {
+    print C_FILE "\t[OID_", $names[$i], "] = ", $indices[$i], ",\n"
+}
+print C_FILE "\t[OID__NR] = ", $total_length, "\n";
+print C_FILE "};\n";
+
+#
+# Encode the OIDs
+#
+my @encoded_oids = ();
+
+for (my $i = 0; $i <= $#names; $i++) {
+    my @octets = ();
+
+    my @components = split(/[.]/, $oids[$i]);
+
+    push @octets, $components[0] * 40 + $components[1];
+
+    for (my $loop = 2; $loop <= $#components; $loop++) {
+	my $c = $components[$loop];
+
+	# Base128 encode the number
+	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
+	$tmp = int($tmp / 7);
+
+	for (; $tmp > 0; $tmp--) {
+	    push @octets, (($c >> $tmp * 7) & 0x7f) | 0x80;
+	}
+	push @octets, $c & 0x7f;
+    }
+
+    push @encoded_oids, \@octets;
+}
+
+#
+# Create a hash value for each OID
+#
+my @hash_values = ();
+for (my $i = 0; $i <= $#names; $i++) {
+    my @octets = @{$encoded_oids[$i]};
+
+    my $hash = $#octets;
+    foreach (@octets) {
+	$hash += $_ * 33;
+    }
+
+    $hash = ($hash >> 24) ^ ($hash >> 16) ^ ($hash >> 8) ^ ($hash);
+
+    push @hash_values, $hash & 0xff;
+}
+
+#
+# Emit the OID data
+#
+print C_FILE "\n";
+print C_FILE "static const unsigned char oid_data[", $total_length, "] = {\n";
+for (my $i = 0; $i <= $#names; $i++) {
+    my @octets = @{$encoded_oids[$i]};
+    print C_FILE "\t";
+    print C_FILE $_, ", " foreach (@octets);
+    print C_FILE "\t// ", $names[$i];
+    print C_FILE "\n";
+}
+print C_FILE "};\n";
+
+#
+# Build the search index table (ordered by length then hash then content)
+#
+my @index_table = ( 0 .. $#names );
+
+@index_table = sort {
+    my @octets_a = @{$encoded_oids[$a]};
+    my @octets_b = @{$encoded_oids[$b]};
+
+    return $hash_values[$a] <=> $hash_values[$b]
+	if ($hash_values[$a] != $hash_values[$b]);
+    return $#octets_a <=> $#octets_b
+	if ($#octets_a != $#octets_b);
+    for (my $i = $#octets_a; $i >= 0; $i--) {
+	return $octets_a[$i] <=> $octets_b[$i]
+	    if ($octets_a[$i] != $octets_b[$i]);
+    }
+    return 0;
+
+} @index_table;
+
+#
+# Emit the search index and hash value table
+#
+print C_FILE "\n";
+print C_FILE "static const struct {\n";
+print C_FILE "\tunsigned char hash;\n";
+if ($#names <= 255) {
+    print C_FILE "\tenum OID oid : 8;\n";
+} else {
+    print C_FILE "\tenum OID oid : 16;\n";
+}
+print C_FILE "} oid_search_table[OID__NR] = {\n";
+for (my $i = 0; $i <= $#names; $i++) {
+    my @octets = @{$encoded_oids[$index_table[$i]]};
+    printf(C_FILE "\t[%3u] = { %3u, OID_%-35s }, // ",
+	   $i,
+	   $hash_values[$index_table[$i]],
+	   $names[$index_table[$i]]);
+    printf C_FILE "%02x", $_ foreach (@octets);
+    print C_FILE "\n";
+}
+print C_FILE "};\n";
+
+#
+# Emit the OID debugging name table
+#
+#print C_FILE "\n";
+#print C_FILE "const char *const oid_name_table[OID__NR + 1] = {\n";
+#
+#for (my $i = 0; $i <= $#names; $i++) {
+#    print C_FILE "\t\"", $names[$i], "\",\n"
+#}
+#print C_FILE "\t\"Unknown-OID\"\n";
+#print C_FILE "};\n";
+
+#
+# Polish off
+#
+close C_FILE or die;
diff --git a/lib/oid_registry.c b/lib/oid_registry.c
new file mode 100644
index 000000000000..33cfd171f627
--- /dev/null
+++ b/lib/oid_registry.c
@@ -0,0 +1,89 @@
+/* ASN.1 Object identifier (OID) registry
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <linux/export.h>
+#include <linux/oid_registry.h>
+#include "oid_registry_data.c"
+
+/**
+ * look_up_OID - Find an OID registration for the specified data
+ * @data: Binary representation of the OID
+ * @datasize: Size of the binary representation
+ */
+enum OID look_up_OID(const void *data, size_t datasize)
+{
+	const unsigned char *octets = data;
+	enum OID oid;
+	unsigned char xhash;
+	unsigned i, j, k, hash;
+	size_t len;
+
+	/* Hash the OID data */
+	hash = datasize - 1;
+
+	for (i = 0; i < datasize; i++)
+		hash += octets[i] * 33;
+	hash = (hash >> 24) ^ (hash >> 16) ^ (hash >> 8) ^ hash;
+	hash &= 0xff;
+
+	/* Binary search the OID registry.  OIDs are stored in ascending order
+	 * of hash value then ascending order of size and then in ascending
+	 * order of reverse value.
+	 */
+	i = 0;
+	k = OID__NR;
+	while (i < k) {
+		j = (i + k) / 2;
+
+		xhash = oid_search_table[j].hash;
+		if (xhash > hash) {
+			k = j;
+			continue;
+		}
+		if (xhash < hash) {
+			i = j + 1;
+			continue;
+		}
+
+		oid = oid_search_table[j].oid;
+		len = oid_index[oid + 1] - oid_index[oid];
+		if (len > datasize) {
+			k = j;
+			continue;
+		}
+		if (len < datasize) {
+			i = j + 1;
+			continue;
+		}
+
+		/* Variation is most likely to be at the tail end of the
+		 * OID, so do the comparison in reverse.
+		 */
+		while (len > 0) {
+			unsigned char a = oid_data[oid_index[oid] + --len];
+			unsigned char b = octets[len];
+			if (a > b) {
+				k = j;
+				goto next;
+			}
+			if (a < b) {
+				i = j + 1;
+				goto next;
+			}
+		}
+		return oid;
+	next:
+		;
+	}
+
+	return OID__NR;
+}
+EXPORT_SYMBOL_GPL(look_up_OID);
-- 
cgit v1.2.3-59-g8ed1b


From 4f73175d0375a7c1b3ae625e76acee8b39741f28 Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Fri, 21 Sep 2012 23:30:51 +0100
Subject: X.509: Add utility functions to render OIDs as strings

Add a pair of utility functions to render OIDs as strings.  The first takes an
encoded OID and turns it into a "a.b.c.d" form string:

	int sprint_oid(const void *data, size_t datasize,
		       char *buffer, size_t bufsize);

The second takes an OID enum index and calls the first on the data held
therein:

	int sprint_OID(enum OID oid, char *buffer, size_t bufsize);

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 include/linux/oid_registry.h |  2 ++
 lib/oid_registry.c           | 81 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 83 insertions(+)

(limited to 'include')

diff --git a/include/linux/oid_registry.h b/include/linux/oid_registry.h
index 5928546bf00a..6926db724258 100644
--- a/include/linux/oid_registry.h
+++ b/include/linux/oid_registry.h
@@ -86,5 +86,7 @@ enum OID {
 };
 
 extern enum OID look_up_OID(const void *data, size_t datasize);
+extern int sprint_oid(const void *, size_t, char *, size_t);
+extern int sprint_OID(enum OID, char *, size_t);
 
 #endif /* _LINUX_OID_REGISTRY_H */
diff --git a/lib/oid_registry.c b/lib/oid_registry.c
index 33cfd171f627..d8de11f45908 100644
--- a/lib/oid_registry.c
+++ b/lib/oid_registry.c
@@ -11,6 +11,9 @@
 
 #include <linux/export.h>
 #include <linux/oid_registry.h>
+#include <linux/kernel.h>
+#include <linux/errno.h>
+#include <linux/bug.h>
 #include "oid_registry_data.c"
 
 /**
@@ -87,3 +90,81 @@ enum OID look_up_OID(const void *data, size_t datasize)
 	return OID__NR;
 }
 EXPORT_SYMBOL_GPL(look_up_OID);
+
+/*
+ * sprint_OID - Print an Object Identifier into a buffer
+ * @data: The encoded OID to print
+ * @datasize: The size of the encoded OID
+ * @buffer: The buffer to render into
+ * @bufsize: The size of the buffer
+ *
+ * The OID is rendered into the buffer in "a.b.c.d" format and the number of
+ * bytes is returned.  -EBADMSG is returned if the data could not be intepreted
+ * and -ENOBUFS if the buffer was too small.
+ */
+int sprint_oid(const void *data, size_t datasize, char *buffer, size_t bufsize)
+{
+	const unsigned char *v = data, *end = v + datasize;
+	unsigned long num;
+	unsigned char n;
+	size_t ret;
+	int count;
+
+	if (v >= end)
+		return -EBADMSG;
+
+	n = *v++;
+	ret = count = snprintf(buffer, bufsize, "%u.%u", n / 40, n % 40);
+	buffer += count;
+	bufsize -= count;
+	if (bufsize == 0)
+		return -ENOBUFS;
+
+	while (v < end) {
+		num = 0;
+		n = *v++;
+		if (!(n & 0x80)) {
+			num = n;
+		} else {
+			num = n & 0x7f;
+			do {
+				if (v >= end)
+					return -EBADMSG;
+				n = *v++;
+				num <<= 7;
+				num |= n & 0x7f;
+			} while (n & 0x80);
+		}
+		ret += count = snprintf(buffer, bufsize, ".%lu", num);
+		buffer += count;
+		bufsize -= count;
+		if (bufsize == 0)
+			return -ENOBUFS;
+	}
+
+	return ret;
+}
+EXPORT_SYMBOL_GPL(sprint_oid);
+
+/**
+ * sprint_OID - Print an Object Identifier into a buffer
+ * @oid: The OID to print
+ * @buffer: The buffer to render into
+ * @bufsize: The size of the buffer
+ *
+ * The OID is rendered into the buffer in "a.b.c.d" format and the number of
+ * bytes is returned.
+ */
+int sprint_OID(enum OID oid, char *buffer, size_t bufsize)
+{
+	int ret;
+
+	BUG_ON(oid >= OID__NR);
+
+	ret = sprint_oid(oid_data + oid_index[oid],
+			 oid_index[oid + 1] - oid_index[oid],
+			 buffer, bufsize);
+	BUG_ON(ret == -EBADMSG);
+	return ret;
+}
+EXPORT_SYMBOL_GPL(sprint_OID);
-- 
cgit v1.2.3-59-g8ed1b


From 4520c6a49af833c83de6c74525ce8e07bbe6d783 Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Fri, 21 Sep 2012 23:31:13 +0100
Subject: X.509: Add simple ASN.1 grammar compiler

Add a simple ASN.1 grammar compiler.  This produces a bytecode output that can
be fed to a decoder to inform the decoder how to interpret the ASN.1 stream it
is trying to parse.

Action functions can be specified in the grammar by interpolating:

	({ foo })

after a type, for example:

	SubjectPublicKeyInfo ::= SEQUENCE {
		algorithm		AlgorithmIdentifier,
		subjectPublicKey	BIT STRING ({ do_key_data })
		}

The decoder is expected to call these after matching this type and parsing the
contents if it is a constructed type.

The grammar compiler does not currently support the SET type (though it does
support SET OF) as I can't see a good way of tracking which members have been
encountered yet without using up extra stack space.

Currently, the grammar compiler will fail if more than 256 bytes of bytecode
would be produced or more than 256 actions have been specified as it uses
8-bit jump values and action indices to keep space usage down.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 include/linux/asn1.h              |   67 ++
 include/linux/asn1_ber_bytecode.h |   87 +++
 init/Kconfig                      |    8 +
 scripts/.gitignore                |    1 +
 scripts/Makefile                  |    2 +
 scripts/Makefile.build            |   11 +
 scripts/asn1_compiler.c           | 1545 +++++++++++++++++++++++++++++++++++++
 7 files changed, 1721 insertions(+)
 create mode 100644 include/linux/asn1.h
 create mode 100644 include/linux/asn1_ber_bytecode.h
 create mode 100644 scripts/asn1_compiler.c

(limited to 'include')

diff --git a/include/linux/asn1.h b/include/linux/asn1.h
new file mode 100644
index 000000000000..5c3f4e4b9a23
--- /dev/null
+++ b/include/linux/asn1.h
@@ -0,0 +1,67 @@
+/* ASN.1 BER/DER/CER encoding definitions
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _LINUX_ASN1_H
+#define _LINUX_ASN1_H
+
+/* Class */
+enum asn1_class {
+	ASN1_UNIV	= 0,	/* Universal */
+	ASN1_APPL	= 1,	/* Application */
+	ASN1_CONT	= 2,	/* Context */
+	ASN1_PRIV	= 3	/* Private */
+};
+#define ASN1_CLASS_BITS	0xc0
+
+
+enum asn1_method {
+	ASN1_PRIM	= 0,	/* Primitive */
+	ASN1_CONS	= 1	/* Constructed */
+};
+#define ASN1_CONS_BIT	0x20
+
+/* Tag */
+enum asn1_tag {
+	ASN1_EOC	= 0,	/* End Of Contents or N/A */
+	ASN1_BOOL	= 1,	/* Boolean */
+	ASN1_INT	= 2,	/* Integer */
+	ASN1_BTS	= 3,	/* Bit String */
+	ASN1_OTS	= 4,	/* Octet String */
+	ASN1_NULL	= 5,	/* Null */
+	ASN1_OID	= 6,	/* Object Identifier  */
+	ASN1_ODE	= 7,	/* Object Description */
+	ASN1_EXT	= 8,	/* External */
+	ASN1_REAL	= 9,	/* Real float */
+	ASN1_ENUM	= 10,	/* Enumerated */
+	ASN1_EPDV	= 11,	/* Embedded PDV */
+	ASN1_UTF8STR	= 12,	/* UTF8 String */
+	ASN1_RELOID	= 13,	/* Relative OID */
+	/* 14 - Reserved */
+	/* 15 - Reserved */
+	ASN1_SEQ	= 16,	/* Sequence and Sequence of */
+	ASN1_SET	= 17,	/* Set and Set of */
+	ASN1_NUMSTR	= 18,	/* Numerical String */
+	ASN1_PRNSTR	= 19,	/* Printable String */
+	ASN1_TEXSTR	= 20,	/* T61 String / Teletext String */
+	ASN1_VIDSTR	= 21,	/* Videotex String */
+	ASN1_IA5STR	= 22,	/* IA5 String */
+	ASN1_UNITIM	= 23,	/* Universal Time */
+	ASN1_GENTIM	= 24,	/* General Time */
+	ASN1_GRASTR	= 25,	/* Graphic String */
+	ASN1_VISSTR	= 26,	/* Visible String */
+	ASN1_GENSTR	= 27,	/* General String */
+	ASN1_UNISTR	= 28,	/* Universal String */
+	ASN1_CHRSTR	= 29,	/* Character String */
+	ASN1_BMPSTR	= 30,	/* BMP String */
+	ASN1_LONG_TAG	= 31	/* Long form tag */
+};
+
+#endif /* _LINUX_ASN1_H */
diff --git a/include/linux/asn1_ber_bytecode.h b/include/linux/asn1_ber_bytecode.h
new file mode 100644
index 000000000000..945d44ae529c
--- /dev/null
+++ b/include/linux/asn1_ber_bytecode.h
@@ -0,0 +1,87 @@
+/* ASN.1 BER/DER/CER parsing state machine internal definitions
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _LINUX_ASN1_BER_BYTECODE_H
+#define _LINUX_ASN1_BER_BYTECODE_H
+
+#ifdef __KERNEL__
+#include <linux/types.h>
+#endif
+#include <linux/asn1.h>
+
+typedef int (*asn1_action_t)(void *context,
+			     size_t hdrlen, /* In case of ANY type */
+			     unsigned char tag, /* In case of ANY type */
+			     const void *value, size_t vlen);
+
+struct asn1_decoder {
+	const unsigned char *machine;
+	size_t machlen;
+	const asn1_action_t *actions;
+};
+
+enum asn1_opcode {
+	/* The tag-matching ops come first and the odd-numbered slots
+	 * are for OR_SKIP ops.
+	 */
+#define ASN1_OP_MATCH__SKIP		  0x01
+#define ASN1_OP_MATCH__ACT		  0x02
+#define ASN1_OP_MATCH__JUMP		  0x04
+#define ASN1_OP_MATCH__ANY		  0x08
+#define ASN1_OP_MATCH__COND		  0x10
+
+	ASN1_OP_MATCH			= 0x00,
+	ASN1_OP_MATCH_OR_SKIP		= 0x01,
+	ASN1_OP_MATCH_ACT		= 0x02,
+	ASN1_OP_MATCH_ACT_OR_SKIP	= 0x03,
+	ASN1_OP_MATCH_JUMP		= 0x04,
+	ASN1_OP_MATCH_JUMP_OR_SKIP	= 0x05,
+	ASN1_OP_MATCH_ANY		= 0x08,
+	ASN1_OP_MATCH_ANY_ACT		= 0x0a,
+	/* Everything before here matches unconditionally */
+
+	ASN1_OP_COND_MATCH_OR_SKIP	= 0x11,
+	ASN1_OP_COND_MATCH_ACT_OR_SKIP	= 0x13,
+	ASN1_OP_COND_MATCH_JUMP_OR_SKIP	= 0x15,
+	ASN1_OP_COND_MATCH_ANY		= 0x18,
+	ASN1_OP_COND_MATCH_ANY_ACT	= 0x1a,
+
+	/* Everything before here will want a tag from the data */
+#define ASN1_OP__MATCHES_TAG ASN1_OP_COND_MATCH_ANY_ACT
+
+	/* These are here to help fill up space */
+	ASN1_OP_COND_FAIL		= 0x1b,
+	ASN1_OP_COMPLETE		= 0x1c,
+	ASN1_OP_ACT			= 0x1d,
+	ASN1_OP_RETURN			= 0x1e,
+
+	/* The following eight have bit 0 -> SET, 1 -> OF, 2 -> ACT */
+	ASN1_OP_END_SEQ			= 0x20,
+	ASN1_OP_END_SET			= 0x21,
+	ASN1_OP_END_SEQ_OF		= 0x22,
+	ASN1_OP_END_SET_OF		= 0x23,
+	ASN1_OP_END_SEQ_ACT		= 0x24,
+	ASN1_OP_END_SET_ACT		= 0x25,
+	ASN1_OP_END_SEQ_OF_ACT		= 0x26,
+	ASN1_OP_END_SET_OF_ACT		= 0x27,
+#define ASN1_OP_END__SET		  0x01
+#define ASN1_OP_END__OF			  0x02
+#define ASN1_OP_END__ACT		  0x04
+
+	ASN1_OP__NR
+};
+
+#define _tag(CLASS, CP, TAG) ((ASN1_##CLASS << 6) | (ASN1_##CP << 5) | ASN1_##TAG)
+#define _tagn(CLASS, CP, TAG) ((ASN1_##CLASS << 6) | (ASN1_##CP << 5) | TAG)
+#define _jump_target(N) (N)
+#define _action(N) (N)
+
+#endif /* _LINUX_ASN1_BER_BYTECODE_H */
diff --git a/init/Kconfig b/init/Kconfig
index af6c7f8ba019..66cc885abbc6 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1612,4 +1612,12 @@ config PADATA
 	depends on SMP
 	bool
 
+config ASN1
+	tristate
+	help
+	  Build a simple ASN.1 grammar compiler that produces a bytecode output
+	  that can be interpreted by the ASN.1 stream decoder and used to
+	  inform it as to what tags are to be expected in a stream and what
+	  functions to call on what tags.
+
 source "kernel/Kconfig.locks"
diff --git a/scripts/.gitignore b/scripts/.gitignore
index 65f362d931b5..fb070fa1038f 100644
--- a/scripts/.gitignore
+++ b/scripts/.gitignore
@@ -10,3 +10,4 @@ ihex2fw
 recordmcount
 docproc
 sortextable
+asn1_compiler
diff --git a/scripts/Makefile b/scripts/Makefile
index a55b0067758a..01e7adb838d9 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -16,8 +16,10 @@ hostprogs-$(CONFIG_VT)           += conmakehash
 hostprogs-$(CONFIG_IKCONFIG)     += bin2c
 hostprogs-$(BUILD_C_RECORDMCOUNT) += recordmcount
 hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable
+hostprogs-$(CONFIG_ASN1)	 += asn1_compiler
 
 HOSTCFLAGS_sortextable.o = -I$(srctree)/tools/include
+HOSTCFLAGS_asn1_compiler.o = -I$(srctree)/include
 
 always		:= $(hostprogs-y) $(hostprogs-m)
 
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index ff1720d28d0c..0e801c3cdaf8 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -354,6 +354,17 @@ quiet_cmd_cpp_lds_S = LDS     $@
 $(obj)/%.lds: $(src)/%.lds.S FORCE
 	$(call if_changed_dep,cpp_lds_S)
 
+# ASN.1 grammar
+# ---------------------------------------------------------------------------
+quiet_cmd_asn1_compiler = ASN.1   $@
+      cmd_asn1_compiler = $(objtree)/scripts/asn1_compiler $< \
+				$(subst .h,.c,$@) $(subst .c,.h,$@)
+
+.PRECIOUS: $(objtree)/$(obj)/%-asn1.c $(objtree)/$(obj)/%-asn1.h
+
+$(obj)/%-asn1.c $(obj)/%-asn1.h: $(src)/%.asn1 $(objtree)/scripts/asn1_compiler
+	$(call cmd,asn1_compiler)
+
 # Build the compiled-in targets
 # ---------------------------------------------------------------------------
 
diff --git a/scripts/asn1_compiler.c b/scripts/asn1_compiler.c
new file mode 100644
index 000000000000..db0e5cd34c70
--- /dev/null
+++ b/scripts/asn1_compiler.c
@@ -0,0 +1,1545 @@
+/* Simplified ASN.1 notation parser
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <ctype.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <linux/asn1_ber_bytecode.h>
+
+enum token_type {
+	DIRECTIVE_ABSENT,
+	DIRECTIVE_ALL,
+	DIRECTIVE_ANY,
+	DIRECTIVE_APPLICATION,
+	DIRECTIVE_AUTOMATIC,
+	DIRECTIVE_BEGIN,
+	DIRECTIVE_BIT,
+	DIRECTIVE_BMPString,
+	DIRECTIVE_BOOLEAN,
+	DIRECTIVE_BY,
+	DIRECTIVE_CHARACTER,
+	DIRECTIVE_CHOICE,
+	DIRECTIVE_CLASS,
+	DIRECTIVE_COMPONENT,
+	DIRECTIVE_COMPONENTS,
+	DIRECTIVE_CONSTRAINED,
+	DIRECTIVE_CONTAINING,
+	DIRECTIVE_DEFAULT,
+	DIRECTIVE_DEFINED,
+	DIRECTIVE_DEFINITIONS,
+	DIRECTIVE_EMBEDDED,
+	DIRECTIVE_ENCODED,
+	DIRECTIVE_ENCODING_CONTROL,
+	DIRECTIVE_END,
+	DIRECTIVE_ENUMERATED,
+	DIRECTIVE_EXCEPT,
+	DIRECTIVE_EXPLICIT,
+	DIRECTIVE_EXPORTS,
+	DIRECTIVE_EXTENSIBILITY,
+	DIRECTIVE_EXTERNAL,
+	DIRECTIVE_FALSE,
+	DIRECTIVE_FROM,
+	DIRECTIVE_GeneralString,
+	DIRECTIVE_GeneralizedTime,
+	DIRECTIVE_GraphicString,
+	DIRECTIVE_IA5String,
+	DIRECTIVE_IDENTIFIER,
+	DIRECTIVE_IMPLICIT,
+	DIRECTIVE_IMPLIED,
+	DIRECTIVE_IMPORTS,
+	DIRECTIVE_INCLUDES,
+	DIRECTIVE_INSTANCE,
+	DIRECTIVE_INSTRUCTIONS,
+	DIRECTIVE_INTEGER,
+	DIRECTIVE_INTERSECTION,
+	DIRECTIVE_ISO646String,
+	DIRECTIVE_MAX,
+	DIRECTIVE_MIN,
+	DIRECTIVE_MINUS_INFINITY,
+	DIRECTIVE_NULL,
+	DIRECTIVE_NumericString,
+	DIRECTIVE_OBJECT,
+	DIRECTIVE_OCTET,
+	DIRECTIVE_OF,
+	DIRECTIVE_OPTIONAL,
+	DIRECTIVE_ObjectDescriptor,
+	DIRECTIVE_PATTERN,
+	DIRECTIVE_PDV,
+	DIRECTIVE_PLUS_INFINITY,
+	DIRECTIVE_PRESENT,
+	DIRECTIVE_PRIVATE,
+	DIRECTIVE_PrintableString,
+	DIRECTIVE_REAL,
+	DIRECTIVE_RELATIVE_OID,
+	DIRECTIVE_SEQUENCE,
+	DIRECTIVE_SET,
+	DIRECTIVE_SIZE,
+	DIRECTIVE_STRING,
+	DIRECTIVE_SYNTAX,
+	DIRECTIVE_T61String,
+	DIRECTIVE_TAGS,
+	DIRECTIVE_TRUE,
+	DIRECTIVE_TeletexString,
+	DIRECTIVE_UNION,
+	DIRECTIVE_UNIQUE,
+	DIRECTIVE_UNIVERSAL,
+	DIRECTIVE_UTCTime,
+	DIRECTIVE_UTF8String,
+	DIRECTIVE_UniversalString,
+	DIRECTIVE_VideotexString,
+	DIRECTIVE_VisibleString,
+	DIRECTIVE_WITH,
+	NR__DIRECTIVES,
+	TOKEN_ASSIGNMENT = NR__DIRECTIVES,
+	TOKEN_OPEN_CURLY,
+	TOKEN_CLOSE_CURLY,
+	TOKEN_OPEN_SQUARE,
+	TOKEN_CLOSE_SQUARE,
+	TOKEN_OPEN_ACTION,
+	TOKEN_CLOSE_ACTION,
+	TOKEN_COMMA,
+	TOKEN_NUMBER,
+	TOKEN_TYPE_NAME,
+	TOKEN_ELEMENT_NAME,
+	NR__TOKENS
+};
+
+static const unsigned char token_to_tag[NR__TOKENS] = {
+	/* EOC goes first */
+	[DIRECTIVE_BOOLEAN]		= ASN1_BOOL,
+	[DIRECTIVE_INTEGER]		= ASN1_INT,
+	[DIRECTIVE_BIT]			= ASN1_BTS,
+	[DIRECTIVE_OCTET]		= ASN1_OTS,
+	[DIRECTIVE_NULL]		= ASN1_NULL,
+	[DIRECTIVE_OBJECT]		= ASN1_OID,
+	[DIRECTIVE_ObjectDescriptor]	= ASN1_ODE,
+	[DIRECTIVE_EXTERNAL]		= ASN1_EXT,
+	[DIRECTIVE_REAL]		= ASN1_REAL,
+	[DIRECTIVE_ENUMERATED]		= ASN1_ENUM,
+	[DIRECTIVE_EMBEDDED]		= 0,
+	[DIRECTIVE_UTF8String]		= ASN1_UTF8STR,
+	[DIRECTIVE_RELATIVE_OID]	= ASN1_RELOID,
+	/* 14 */
+	/* 15 */
+	[DIRECTIVE_SEQUENCE]		= ASN1_SEQ,
+	[DIRECTIVE_SET]			= ASN1_SET,
+	[DIRECTIVE_NumericString]	= ASN1_NUMSTR,
+	[DIRECTIVE_PrintableString]	= ASN1_PRNSTR,
+	[DIRECTIVE_T61String]		= ASN1_TEXSTR,
+	[DIRECTIVE_TeletexString]	= ASN1_TEXSTR,
+	[DIRECTIVE_VideotexString]	= ASN1_VIDSTR,
+	[DIRECTIVE_IA5String]		= ASN1_IA5STR,
+	[DIRECTIVE_UTCTime]		= ASN1_UNITIM,
+	[DIRECTIVE_GeneralizedTime]	= ASN1_GENTIM,
+	[DIRECTIVE_GraphicString]	= ASN1_GRASTR,
+	[DIRECTIVE_VisibleString]	= ASN1_VISSTR,
+	[DIRECTIVE_GeneralString]	= ASN1_GENSTR,
+	[DIRECTIVE_UniversalString]	= ASN1_UNITIM,
+	[DIRECTIVE_CHARACTER]		= ASN1_CHRSTR,
+	[DIRECTIVE_BMPString]		= ASN1_BMPSTR,
+};
+
+static const char asn1_classes[4][5] = {
+	[ASN1_UNIV]	= "UNIV",
+	[ASN1_APPL]	= "APPL",
+	[ASN1_CONT]	= "CONT",
+	[ASN1_PRIV]	= "PRIV"
+};
+
+static const char asn1_methods[2][5] = {
+	[ASN1_UNIV]	= "PRIM",
+	[ASN1_APPL]	= "CONS"
+};
+
+static const char *const asn1_universal_tags[32] = {
+	"EOC",
+	"BOOL",
+	"INT",
+	"BTS",
+	"OTS",
+	"NULL",
+	"OID",
+	"ODE",
+	"EXT",
+	"REAL",
+	"ENUM",
+	"EPDV",
+	"UTF8STR",
+	"RELOID",
+	NULL,		/* 14 */
+	NULL,		/* 15 */
+	"SEQ",
+	"SET",
+	"NUMSTR",
+	"PRNSTR",
+	"TEXSTR",
+	"VIDSTR",
+	"IA5STR",
+	"UNITIM",
+	"GENTIM",
+	"GRASTR",
+	"VISSTR",
+	"GENSTR",
+	"UNISTR",
+	"CHRSTR",
+	"BMPSTR",
+	NULL		/* 31 */
+};
+
+static const char *filename;
+static const char *grammar_name;
+static const char *outputname;
+static const char *headername;
+
+static const char *const directives[NR__DIRECTIVES] = {
+#define _(X) [DIRECTIVE_##X] = #X
+	_(ABSENT),
+	_(ALL),
+	_(ANY),
+	_(APPLICATION),
+	_(AUTOMATIC),
+	_(BEGIN),
+	_(BIT),
+	_(BMPString),
+	_(BOOLEAN),
+	_(BY),
+	_(CHARACTER),
+	_(CHOICE),
+	_(CLASS),
+	_(COMPONENT),
+	_(COMPONENTS),
+	_(CONSTRAINED),
+	_(CONTAINING),
+	_(DEFAULT),
+	_(DEFINED),
+	_(DEFINITIONS),
+	_(EMBEDDED),
+	_(ENCODED),
+	[DIRECTIVE_ENCODING_CONTROL] = "ENCODING-CONTROL",
+	_(END),
+	_(ENUMERATED),
+	_(EXCEPT),
+	_(EXPLICIT),
+	_(EXPORTS),
+	_(EXTENSIBILITY),
+	_(EXTERNAL),
+	_(FALSE),
+	_(FROM),
+	_(GeneralString),
+	_(GeneralizedTime),
+	_(GraphicString),
+	_(IA5String),
+	_(IDENTIFIER),
+	_(IMPLICIT),
+	_(IMPLIED),
+	_(IMPORTS),
+	_(INCLUDES),
+	_(INSTANCE),
+	_(INSTRUCTIONS),
+	_(INTEGER),
+	_(INTERSECTION),
+	_(ISO646String),
+	_(MAX),
+	_(MIN),
+	[DIRECTIVE_MINUS_INFINITY] = "MINUS-INFINITY",
+	[DIRECTIVE_NULL] = "NULL",
+	_(NumericString),
+	_(OBJECT),
+	_(OCTET),
+	_(OF),
+	_(OPTIONAL),
+	_(ObjectDescriptor),
+	_(PATTERN),
+	_(PDV),
+	[DIRECTIVE_PLUS_INFINITY] = "PLUS-INFINITY",
+	_(PRESENT),
+	_(PRIVATE),
+	_(PrintableString),
+	_(REAL),
+	[DIRECTIVE_RELATIVE_OID] = "RELATIVE-OID",
+	_(SEQUENCE),
+	_(SET),
+	_(SIZE),
+	_(STRING),
+	_(SYNTAX),
+	_(T61String),
+	_(TAGS),
+	_(TRUE),
+	_(TeletexString),
+	_(UNION),
+	_(UNIQUE),
+	_(UNIVERSAL),
+	_(UTCTime),
+	_(UTF8String),
+	_(UniversalString),
+	_(VideotexString),
+	_(VisibleString),
+	_(WITH)
+};
+
+struct action {
+	struct action	*next;
+	unsigned char	index;
+	char		name[];
+};
+
+static struct action *action_list;
+static unsigned nr_actions;
+
+struct token {
+	unsigned short	line;
+	enum token_type	token_type : 8;
+	unsigned char	size;
+	struct action	*action;
+	const char	*value;
+	struct type	*type;
+};
+
+static struct token *token_list;
+static unsigned nr_tokens;
+
+static int directive_compare(const void *_key, const void *_pdir)
+{
+	const struct token *token = _key;
+	const char *const *pdir = _pdir, *dir = *pdir;
+	size_t dlen, clen;
+	int val;
+
+	dlen = strlen(dir);
+	clen = (dlen < token->size) ? dlen : token->size;
+
+	//printf("cmp(%*.*s,%s) = ",
+	//       (int)token->size, (int)token->size, token->value,
+	//       dir);
+
+	val = memcmp(token->value, dir, clen);
+	if (val != 0) {
+		//printf("%d [cmp]\n", val);
+		return val;
+	}
+
+	if (dlen == token->size) {
+		//printf("0\n");
+		return 0;
+	}
+	//printf("%d\n", (int)dlen - (int)token->size);
+	return dlen - token->size; /* shorter -> negative */
+}
+
+/*
+ * Tokenise an ASN.1 grammar
+ */
+static void tokenise(char *buffer, char *end)
+{
+	struct token *tokens;
+	char *line, *nl, *p, *q;
+	unsigned tix, lineno;
+
+	/* Assume we're going to have half as many tokens as we have
+	 * characters
+	 */
+	token_list = tokens = calloc((end - buffer) / 2, sizeof(struct token));
+	if (!tokens) {
+		perror(NULL);
+		exit(1);
+	}
+	tix = 0;
+
+	lineno = 0;
+	while (buffer < end) {
+		/* First of all, break out a line */
+		lineno++;
+		line = buffer;
+		nl = memchr(line, '\n', end - buffer);
+		if (!nl) {
+			buffer = nl = end;
+		} else {
+			buffer = nl + 1;
+			*nl = '\0';
+		}
+
+		/* Remove "--" comments */
+		p = line;
+	next_comment:
+		while ((p = memchr(p, '-', nl - p))) {
+			if (p[1] == '-') {
+				/* Found a comment; see if there's a terminator */
+				q = p + 2;
+				while ((q = memchr(q, '-', nl - q))) {
+					if (q[1] == '-') {
+						/* There is - excise the comment */
+						q += 2;
+						memmove(p, q, nl - q);
+						goto next_comment;
+					}
+					q++;
+				}
+				*p = '\0';
+				nl = p;
+				break;
+			} else {
+				p++;
+			}
+		}
+
+		p = line;
+		while (p < nl) {
+			/* Skip white space */
+			while (p < nl && isspace(*p))
+				*(p++) = 0;
+			if (p >= nl)
+				break;
+
+			tokens[tix].line = lineno;
+			tokens[tix].value = p;
+
+			/* Handle string tokens */
+			if (isalpha(*p)) {
+				const char **dir;
+
+				/* Can be a directive, type name or element
+				 * name.  Find the end of the name.
+				 */
+				q = p + 1;
+				while (q < nl && (isalnum(*q) || *q == '-' || *q == '_'))
+					q++;
+				tokens[tix].size = q - p;
+				p = q;
+
+				/* If it begins with a lowercase letter then
+				 * it's an element name
+				 */
+				if (islower(tokens[tix].value[0])) {
+					tokens[tix++].token_type = TOKEN_ELEMENT_NAME;
+					continue;
+				}
+
+				/* Otherwise we need to search the directive
+				 * table
+				 */
+				dir = bsearch(&tokens[tix], directives,
+					      sizeof(directives) / sizeof(directives[1]),
+					      sizeof(directives[1]),
+					      directive_compare);
+				if (dir) {
+					tokens[tix++].token_type = dir - directives;
+					continue;
+				}
+
+				tokens[tix++].token_type = TOKEN_TYPE_NAME;
+				continue;
+			}
+
+			/* Handle numbers */
+			if (isdigit(*p)) {
+				/* Find the end of the number */
+				q = p + 1;
+				while (q < nl && (isdigit(*q)))
+					q++;
+				tokens[tix].size = q - p;
+				p = q;
+				tokens[tix++].token_type = TOKEN_NUMBER;
+				continue;
+			}
+
+			if (nl - p >= 3) {
+				if (memcmp(p, "::=", 3) == 0) {
+					p += 3;
+					tokens[tix].size = 3;
+					tokens[tix++].token_type = TOKEN_ASSIGNMENT;
+					continue;
+				}
+			}
+
+			if (nl - p >= 2) {
+				if (memcmp(p, "({", 2) == 0) {
+					p += 2;
+					tokens[tix].size = 2;
+					tokens[tix++].token_type = TOKEN_OPEN_ACTION;
+					continue;
+				}
+				if (memcmp(p, "})", 2) == 0) {
+					p += 2;
+					tokens[tix].size = 2;
+					tokens[tix++].token_type = TOKEN_CLOSE_ACTION;
+					continue;
+				}
+			}
+
+			if (nl - p >= 1) {
+				tokens[tix].size = 1;
+				switch (*p) {
+				case '{':
+					p += 1;
+					tokens[tix++].token_type = TOKEN_OPEN_CURLY;
+					continue;
+				case '}':
+					p += 1;
+					tokens[tix++].token_type = TOKEN_CLOSE_CURLY;
+					continue;
+				case '[':
+					p += 1;
+					tokens[tix++].token_type = TOKEN_OPEN_SQUARE;
+					continue;
+				case ']':
+					p += 1;
+					tokens[tix++].token_type = TOKEN_CLOSE_SQUARE;
+					continue;
+				case ',':
+					p += 1;
+					tokens[tix++].token_type = TOKEN_COMMA;
+					continue;
+				default:
+					break;
+				}
+			}
+
+			fprintf(stderr, "%s:%u: Unknown character in grammar: '%c'\n",
+				filename, lineno, *p);
+			exit(1);
+		}
+	}
+
+	nr_tokens = tix;
+	printf("Extracted %u tokens\n", nr_tokens);
+
+#if 0
+	{
+		int n;
+		for (n = 0; n < nr_tokens; n++)
+			printf("Token %3u: '%*.*s'\n",
+			       n,
+			       (int)token_list[n].size, (int)token_list[n].size,
+			       token_list[n].value);
+	}
+#endif
+}
+
+static void build_type_list(void);
+static void parse(void);
+static void render(FILE *out, FILE *hdr);
+
+/*
+ *
+ */
+int main(int argc, char **argv)
+{
+	struct stat st;
+	ssize_t readlen;
+	FILE *out, *hdr;
+	char *buffer, *p;
+	int fd;
+
+	if (argc != 4) {
+		fprintf(stderr, "Format: %s <grammar-file> <c-file> <hdr-file>\n",
+			argv[0]);
+		exit(2);
+	}
+
+	filename = argv[1];
+	outputname = argv[2];
+	headername = argv[3];
+
+	fd = open(filename, O_RDONLY);
+	if (fd < 0) {
+		perror(filename);
+		exit(1);
+	}
+
+	if (fstat(fd, &st) < 0) {
+		perror(filename);
+		exit(1);
+	}
+
+	if (!(buffer = malloc(st.st_size + 1))) {
+		perror(NULL);
+		exit(1);
+	}
+
+	if ((readlen = read(fd, buffer, st.st_size)) < 0) {
+		perror(filename);
+		exit(1);
+	}
+
+	if (close(fd) < 0) {
+		perror(filename);
+		exit(1);
+	}
+
+	if (readlen != st.st_size) {
+		fprintf(stderr, "%s: Short read\n", filename);
+		exit(1);
+	}
+
+	p = strrchr(argv[1], '/');
+	p = p ? p + 1 : argv[1];
+	grammar_name = strdup(p);
+	if (!p) {
+		perror(NULL);
+		exit(1);
+	}
+	p = strchr(grammar_name, '.');
+	if (p)
+		*p = '\0';
+
+	buffer[readlen] = 0;
+	tokenise(buffer, buffer + readlen);
+	build_type_list();
+	parse();
+
+	out = fopen(outputname, "w");
+	if (!out) {
+		perror(outputname);
+		exit(1);
+	}
+
+	hdr = fopen(headername, "w");
+	if (!out) {
+		perror(headername);
+		exit(1);
+	}
+
+	render(out, hdr);
+
+	if (fclose(out) < 0) {
+		perror(outputname);
+		exit(1);
+	}
+
+	if (fclose(hdr) < 0) {
+		perror(headername);
+		exit(1);
+	}
+
+	return 0;
+}
+
+enum compound {
+	NOT_COMPOUND,
+	SET,
+	SET_OF,
+	SEQUENCE,
+	SEQUENCE_OF,
+	CHOICE,
+	ANY,
+	TYPE_REF,
+	TAG_OVERRIDE
+};
+
+struct element {
+	struct type	*type_def;
+	struct token	*name;
+	struct token	*type;
+	struct action	*action;
+	struct element	*children;
+	struct element	*next;
+	struct element	*render_next;
+	struct element	*list_next;
+	uint8_t		n_elements;
+	enum compound	compound : 8;
+	enum asn1_class	class : 8;
+	enum asn1_method method : 8;
+	uint8_t		tag;
+	unsigned	entry_index;
+	unsigned	flags;
+#define ELEMENT_IMPLICIT	0x0001
+#define ELEMENT_EXPLICIT	0x0002
+#define ELEMENT_MARKED		0x0004
+#define ELEMENT_RENDERED	0x0008
+#define ELEMENT_SKIPPABLE	0x0010
+#define ELEMENT_CONDITIONAL	0x0020
+};
+
+struct type {
+	struct token	*name;
+	struct token	*def;
+	struct element	*element;
+	unsigned	ref_count;
+	unsigned	flags;
+#define TYPE_STOP_MARKER	0x0001
+#define TYPE_BEGIN		0x0002
+};
+
+static struct type *type_list;
+static struct type **type_index;
+static unsigned nr_types;
+
+static int type_index_compare(const void *_a, const void *_b)
+{
+	const struct type *const *a = _a, *const *b = _b;
+
+	if ((*a)->name->size != (*b)->name->size)
+		return (*a)->name->size - (*b)->name->size;
+	else
+		return memcmp((*a)->name->value, (*b)->name->value,
+			      (*a)->name->size);
+}
+
+static int type_finder(const void *_key, const void *_ti)
+{
+	const struct token *token = _key;
+	const struct type *const *ti = _ti;
+	const struct type *type = *ti;
+
+	if (token->size != type->name->size)
+		return token->size - type->name->size;
+	else
+		return memcmp(token->value, type->name->value,
+			      token->size);
+}
+
+/*
+ * Build up a list of types and a sorted index to that list.
+ */
+static void build_type_list(void)
+{
+	struct type *types;
+	unsigned nr, t, n;
+
+	nr = 0;
+	for (n = 0; n < nr_tokens - 1; n++)
+		if (token_list[n + 0].token_type == TOKEN_TYPE_NAME &&
+		    token_list[n + 1].token_type == TOKEN_ASSIGNMENT)
+			nr++;
+
+	if (nr == 0) {
+		fprintf(stderr, "%s: No defined types\n", filename);
+		exit(1);
+	}
+
+	nr_types = nr;
+	types = type_list = calloc(nr + 1, sizeof(type_list[0]));
+	if (!type_list) {
+		perror(NULL);
+		exit(1);
+	}
+	type_index = calloc(nr, sizeof(type_index[0]));
+	if (!type_index) {
+		perror(NULL);
+		exit(1);
+	}
+
+	t = 0;
+	types[t].flags |= TYPE_BEGIN;
+	for (n = 0; n < nr_tokens - 1; n++) {
+		if (token_list[n + 0].token_type == TOKEN_TYPE_NAME &&
+		    token_list[n + 1].token_type == TOKEN_ASSIGNMENT) {
+			types[t].name = &token_list[n];
+			type_index[t] = &types[t];
+			t++;
+		}
+	}
+	types[t].name = &token_list[n + 1];
+	types[t].flags |= TYPE_STOP_MARKER;
+
+	qsort(type_index, nr, sizeof(type_index[0]), type_index_compare);
+
+	printf("Extracted %u types\n", nr_types);
+#if 0
+	for (n = 0; n < nr_types; n++) {
+		struct type *type = type_index[n];
+		printf("- %*.*s\n",
+		       (int)type->name->size,
+		       (int)type->name->size,
+		       type->name->value);
+	}
+#endif
+}
+
+static struct element *parse_type(struct token **_cursor, struct token *stop,
+				  struct token *name);
+
+/*
+ * Parse the token stream
+ */
+static void parse(void)
+{
+	struct token *cursor;
+	struct type *type;
+
+	/* Parse one type definition statement at a time */
+	type = type_list;
+	do {
+		cursor = type->name;
+
+		if (cursor[0].token_type != TOKEN_TYPE_NAME ||
+		    cursor[1].token_type != TOKEN_ASSIGNMENT)
+			abort();
+		cursor += 2;
+
+		type->element = parse_type(&cursor, type[1].name, NULL);
+		type->element->type_def = type;
+
+		if (cursor != type[1].name) {
+			fprintf(stderr, "%s:%d: Parse error at token '%*.*s'\n",
+				filename, cursor->line,
+				(int)cursor->size, (int)cursor->size, cursor->value);
+			exit(1);
+		}
+
+	} while (type++, !(type->flags & TYPE_STOP_MARKER));
+
+	printf("Extracted %u actions\n", nr_actions);
+}
+
+static struct element *element_list;
+
+static struct element *alloc_elem(struct token *type)
+{
+	struct element *e = calloc(1, sizeof(*e));
+	if (!e) {
+		perror(NULL);
+		exit(1);
+	}
+	e->list_next = element_list;
+	element_list = e;
+	return e;
+}
+
+static struct element *parse_compound(struct token **_cursor, struct token *end,
+				      int alternates);
+
+/*
+ * Parse one type definition statement
+ */
+static struct element *parse_type(struct token **_cursor, struct token *end,
+				  struct token *name)
+{
+	struct element *top, *element;
+	struct action *action, **ppaction;
+	struct token *cursor = *_cursor;
+	struct type **ref;
+	char *p;
+	int labelled = 0, implicit = 0;
+
+	top = element = alloc_elem(cursor);
+	element->class = ASN1_UNIV;
+	element->method = ASN1_PRIM;
+	element->tag = token_to_tag[cursor->token_type];
+	element->name = name;
+
+	/* Extract the tag value if one given */
+	if (cursor->token_type == TOKEN_OPEN_SQUARE) {
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+		switch (cursor->token_type) {
+		case DIRECTIVE_UNIVERSAL:
+			element->class = ASN1_UNIV;
+			cursor++;
+			break;
+		case DIRECTIVE_APPLICATION:
+			element->class = ASN1_APPL;
+			cursor++;
+			break;
+		case TOKEN_NUMBER:
+			element->class = ASN1_CONT;
+			break;
+		case DIRECTIVE_PRIVATE:
+			element->class = ASN1_PRIV;
+			cursor++;
+			break;
+		default:
+			fprintf(stderr, "%s:%d: Unrecognised tag class token '%*.*s'\n",
+				filename, cursor->line,
+				(int)cursor->size, (int)cursor->size, cursor->value);
+			exit(1);
+		}
+
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type != TOKEN_NUMBER) {
+			fprintf(stderr, "%s:%d: Missing tag number '%*.*s'\n",
+				filename, cursor->line,
+				(int)cursor->size, (int)cursor->size, cursor->value);
+			exit(1);
+		}
+
+		element->tag &= ~0x1f;
+		element->tag |= strtoul(cursor->value, &p, 10);
+		if (p - cursor->value != cursor->size)
+			abort();
+		cursor++;
+
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type != TOKEN_CLOSE_SQUARE) {
+			fprintf(stderr, "%s:%d: Missing closing square bracket '%*.*s'\n",
+				filename, cursor->line,
+				(int)cursor->size, (int)cursor->size, cursor->value);
+			exit(1);
+		}
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+		labelled = 1;
+	}
+
+	/* Handle implicit and explicit markers */
+	if (cursor->token_type == DIRECTIVE_IMPLICIT) {
+		element->flags |= ELEMENT_IMPLICIT;
+		implicit = 1;
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+	} else if (cursor->token_type == DIRECTIVE_EXPLICIT) {
+		element->flags |= ELEMENT_EXPLICIT;
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+	}
+
+	if (labelled) {
+		if (!implicit)
+			element->method |= ASN1_CONS;
+		element->compound = implicit ? TAG_OVERRIDE : SEQUENCE;
+		element->children = alloc_elem(cursor);
+		element = element->children;
+		element->class = ASN1_UNIV;
+		element->method = ASN1_PRIM;
+		element->tag = token_to_tag[cursor->token_type];
+		element->name = name;
+	}
+
+	/* Extract the type we're expecting here */
+	element->type = cursor;
+	switch (cursor->token_type) {
+	case DIRECTIVE_ANY:
+		element->compound = ANY;
+		cursor++;
+		break;
+
+	case DIRECTIVE_NULL:
+	case DIRECTIVE_BOOLEAN:
+	case DIRECTIVE_ENUMERATED:
+	case DIRECTIVE_INTEGER:
+		element->compound = NOT_COMPOUND;
+		cursor++;
+		break;
+
+	case DIRECTIVE_EXTERNAL:
+		element->method = ASN1_CONS;
+
+	case DIRECTIVE_BMPString:
+	case DIRECTIVE_GeneralString:
+	case DIRECTIVE_GraphicString:
+	case DIRECTIVE_IA5String:
+	case DIRECTIVE_ISO646String:
+	case DIRECTIVE_NumericString:
+	case DIRECTIVE_PrintableString:
+	case DIRECTIVE_T61String:
+	case DIRECTIVE_TeletexString:
+	case DIRECTIVE_UniversalString:
+	case DIRECTIVE_UTF8String:
+	case DIRECTIVE_VideotexString:
+	case DIRECTIVE_VisibleString:
+	case DIRECTIVE_ObjectDescriptor:
+	case DIRECTIVE_GeneralizedTime:
+	case DIRECTIVE_UTCTime:
+		element->compound = NOT_COMPOUND;
+		cursor++;
+		break;
+
+	case DIRECTIVE_BIT:
+	case DIRECTIVE_OCTET:
+		element->compound = NOT_COMPOUND;
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type != DIRECTIVE_STRING)
+			goto parse_error;
+		cursor++;
+		break;
+
+	case DIRECTIVE_OBJECT:
+		element->compound = NOT_COMPOUND;
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type != DIRECTIVE_IDENTIFIER)
+			goto parse_error;
+		cursor++;
+		break;
+
+	case TOKEN_TYPE_NAME:
+		element->compound = TYPE_REF;
+		ref = bsearch(cursor, type_index, nr_types, sizeof(type_index[0]),
+			      type_finder);
+		if (!ref) {
+			fprintf(stderr, "%s:%d: Type '%*.*s' undefined\n",
+				filename, cursor->line,
+				(int)cursor->size, (int)cursor->size, cursor->value);
+			exit(1);
+		}
+		cursor->type = *ref;
+		(*ref)->ref_count++;
+		cursor++;
+		break;
+
+	case DIRECTIVE_CHOICE:
+		element->compound = CHOICE;
+		cursor++;
+		element->children = parse_compound(&cursor, end, 1);
+		break;
+
+	case DIRECTIVE_SEQUENCE:
+		element->compound = SEQUENCE;
+		element->method = ASN1_CONS;
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type == DIRECTIVE_OF) {
+			element->compound = SEQUENCE_OF;
+			cursor++;
+			if (cursor >= end)
+				goto overrun_error;
+			element->children = parse_type(&cursor, end, NULL);
+		} else {
+			element->children = parse_compound(&cursor, end, 0);
+		}
+		break;
+
+	case DIRECTIVE_SET:
+		element->compound = SET;
+		element->method = ASN1_CONS;
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type == DIRECTIVE_OF) {
+			element->compound = SET_OF;
+			cursor++;
+			if (cursor >= end)
+				goto parse_error;
+			element->children = parse_type(&cursor, end, NULL);
+		} else {
+			element->children = parse_compound(&cursor, end, 1);
+		}
+		break;
+
+	default:
+		fprintf(stderr, "%s:%d: Token '%*.*s' does not introduce a type\n",
+			filename, cursor->line,
+			(int)cursor->size, (int)cursor->size, cursor->value);
+		exit(1);
+	}
+
+	/* Handle elements that are optional */
+	if (cursor < end && (cursor->token_type == DIRECTIVE_OPTIONAL ||
+			     cursor->token_type == DIRECTIVE_DEFAULT)
+	    ) {
+		cursor++;
+		top->flags |= ELEMENT_SKIPPABLE;
+	}
+
+	if (cursor < end && cursor->token_type == TOKEN_OPEN_ACTION) {
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type != TOKEN_ELEMENT_NAME) {
+			fprintf(stderr, "%s:%d: Token '%*.*s' is not an action function name\n",
+				filename, cursor->line,
+				(int)cursor->size, (int)cursor->size, cursor->value);
+			exit(1);
+		}
+
+		action = malloc(sizeof(struct action) + cursor->size + 1);
+		if (!action) {
+			perror(NULL);
+			exit(1);
+		}
+		action->index = 0;
+		memcpy(action->name, cursor->value, cursor->size);
+		action->name[cursor->size] = 0;
+
+		for (ppaction = &action_list;
+		     *ppaction;
+		     ppaction = &(*ppaction)->next
+		     ) {
+			int cmp = strcmp(action->name, (*ppaction)->name);
+			if (cmp == 0) {
+				free(action);
+				action = *ppaction;
+				goto found;
+			}
+			if (cmp < 0) {
+				action->next = *ppaction;
+				*ppaction = action;
+				nr_actions++;
+				goto found;
+			}
+		}
+		action->next = NULL;
+		*ppaction = action;
+		nr_actions++;
+	found:
+
+		element->action = action;
+		cursor->action = action;
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type != TOKEN_CLOSE_ACTION) {
+			fprintf(stderr, "%s:%d: Missing close action, got '%*.*s'\n",
+				filename, cursor->line,
+				(int)cursor->size, (int)cursor->size, cursor->value);
+			exit(1);
+		}
+		cursor++;
+	}
+
+	*_cursor = cursor;
+	return top;
+
+parse_error:
+	fprintf(stderr, "%s:%d: Unexpected token '%*.*s'\n",
+		filename, cursor->line,
+		(int)cursor->size, (int)cursor->size, cursor->value);
+	exit(1);
+
+overrun_error:
+	fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
+	exit(1);
+}
+
+/*
+ * Parse a compound type list
+ */
+static struct element *parse_compound(struct token **_cursor, struct token *end,
+				      int alternates)
+{
+	struct element *children, **child_p = &children, *element;
+	struct token *cursor = *_cursor, *name;
+
+	if (cursor->token_type != TOKEN_OPEN_CURLY) {
+		fprintf(stderr, "%s:%d: Expected compound to start with brace not '%*.*s'\n",
+			filename, cursor->line,
+			(int)cursor->size, (int)cursor->size, cursor->value);
+		exit(1);
+	}
+	cursor++;
+	if (cursor >= end)
+		goto overrun_error;
+
+	if (cursor->token_type == TOKEN_OPEN_CURLY) {
+		fprintf(stderr, "%s:%d: Empty compound\n",
+			filename, cursor->line);
+		exit(1);
+	}
+
+	for (;;) {
+		name = NULL;
+		if (cursor->token_type == TOKEN_ELEMENT_NAME) {
+			name = cursor;
+			cursor++;
+			if (cursor >= end)
+				goto overrun_error;
+		}
+
+		element = parse_type(&cursor, end, name);
+		if (alternates)
+			element->flags |= ELEMENT_SKIPPABLE | ELEMENT_CONDITIONAL;
+
+		*child_p = element;
+		child_p = &element->next;
+
+		if (cursor >= end)
+			goto overrun_error;
+		if (cursor->token_type != TOKEN_COMMA)
+			break;
+		cursor++;
+		if (cursor >= end)
+			goto overrun_error;
+	}
+
+	children->flags &= ~ELEMENT_CONDITIONAL;
+
+	if (cursor->token_type != TOKEN_CLOSE_CURLY) {
+		fprintf(stderr, "%s:%d: Expected compound closure, got '%*.*s'\n",
+			filename, cursor->line,
+			(int)cursor->size, (int)cursor->size, cursor->value);
+		exit(1);
+	}
+	cursor++;
+
+	*_cursor = cursor;
+	return children;
+
+overrun_error:
+	fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
+	exit(1);
+}
+
+static void render_element(FILE *out, struct element *e, struct element *tag);
+static void render_out_of_line_list(FILE *out);
+
+static int nr_entries;
+static int render_depth = 1;
+static struct element *render_list, **render_list_p = &render_list;
+
+__attribute__((format(printf, 2, 3)))
+static void render_opcode(FILE *out, const char *fmt, ...)
+{
+	va_list va;
+
+	if (out) {
+		fprintf(out, "\t[%4d] =%*s", nr_entries, render_depth, "");
+		va_start(va, fmt);
+		vfprintf(out, fmt, va);
+		va_end(va);
+	}
+	nr_entries++;
+}
+
+__attribute__((format(printf, 2, 3)))
+static void render_more(FILE *out, const char *fmt, ...)
+{
+	va_list va;
+
+	if (out) {
+		va_start(va, fmt);
+		vfprintf(out, fmt, va);
+		va_end(va);
+	}
+}
+
+/*
+ * Render the grammar into a state machine definition.
+ */
+static void render(FILE *out, FILE *hdr)
+{
+	struct element *e;
+	struct action *action;
+	struct type *root;
+	int index;
+
+	fprintf(hdr, "/*\n");
+	fprintf(hdr, " * Automatically generated by asn1_compiler.  Do not edit\n");
+	fprintf(hdr, " *\n");
+	fprintf(hdr, " * ASN.1 parser for %s\n", grammar_name);
+	fprintf(hdr, " */\n");
+	fprintf(hdr, "#include <linux/asn1_decoder.h>\n");
+	fprintf(hdr, "\n");
+	fprintf(hdr, "extern const struct asn1_decoder %s_decoder;\n", grammar_name);
+	if (ferror(hdr)) {
+		perror(headername);
+		exit(1);
+	}
+
+	fprintf(out, "/*\n");
+	fprintf(out, " * Automatically generated by asn1_compiler.  Do not edit\n");
+	fprintf(out, " *\n");
+	fprintf(out, " * ASN.1 parser for %s\n", grammar_name);
+	fprintf(out, " */\n");
+	fprintf(out, "#include <linux/asn1_ber_bytecode.h>\n");
+	fprintf(out, "#include \"%s-asn1.h\"\n", grammar_name);
+	fprintf(out, "\n");
+	if (ferror(out)) {
+		perror(outputname);
+		exit(1);
+	}
+
+	/* Tabulate the action functions we might have to call */
+	fprintf(hdr, "\n");
+	index = 0;
+	for (action = action_list; action; action = action->next) {
+		action->index = index++;
+		fprintf(hdr,
+			"extern int %s(void *, size_t, unsigned char,"
+			" const void *, size_t);\n",
+			action->name);
+	}
+	fprintf(hdr, "\n");
+
+	fprintf(out, "enum %s_actions {\n", grammar_name);
+	for (action = action_list; action; action = action->next)
+		fprintf(out, "\tACT_%s = %u,\n",
+			action->name, action->index);
+	fprintf(out, "\tNR__%s_actions = %u\n", grammar_name, nr_actions);
+	fprintf(out, "};\n");
+
+	fprintf(out, "\n");
+	fprintf(out, "static const asn1_action_t %s_action_table[NR__%s_actions] = {\n",
+		grammar_name, grammar_name);
+	for (action = action_list; action; action = action->next)
+		fprintf(out, "\t[%4u] = %s,\n", action->index, action->name);
+	fprintf(out, "};\n");
+
+	if (ferror(out)) {
+		perror(outputname);
+		exit(1);
+	}
+
+	/* We do two passes - the first one calculates all the offsets */
+	printf("Pass 1\n");
+	nr_entries = 0;
+	root = &type_list[0];
+	render_element(NULL, root->element, NULL);
+	render_opcode(NULL, "ASN1_OP_COMPLETE,\n");
+	render_out_of_line_list(NULL);
+
+	for (e = element_list; e; e = e->list_next)
+		e->flags &= ~ELEMENT_RENDERED;
+
+	/* And then we actually render */
+	printf("Pass 2\n");
+	fprintf(out, "\n");
+	fprintf(out, "static const unsigned char %s_machine[] = {\n",
+		grammar_name);
+
+	nr_entries = 0;
+	root = &type_list[0];
+	render_element(out, root->element, NULL);
+	render_opcode(out, "ASN1_OP_COMPLETE,\n");
+	render_out_of_line_list(out);
+
+	fprintf(out, "};\n");
+
+	fprintf(out, "\n");
+	fprintf(out, "const struct asn1_decoder %s_decoder = {\n", grammar_name);
+	fprintf(out, "\t.machine = %s_machine,\n", grammar_name);
+	fprintf(out, "\t.machlen = sizeof(%s_machine),\n", grammar_name);
+	fprintf(out, "\t.actions = %s_action_table,\n", grammar_name);
+	fprintf(out, "};\n");
+}
+
+/*
+ * Render the out-of-line elements
+ */
+static void render_out_of_line_list(FILE *out)
+{
+	struct element *e, *ce;
+	const char *act;
+	int entry;
+
+	while ((e = render_list)) {
+		render_list = e->render_next;
+		if (!render_list)
+			render_list_p = &render_list;
+
+		render_more(out, "\n");
+		e->entry_index = entry = nr_entries;
+		render_depth++;
+		for (ce = e->children; ce; ce = ce->next)
+			render_element(out, ce, NULL);
+		render_depth--;
+
+		act = e->action ? "_ACT" : "";
+		switch (e->compound) {
+		case SEQUENCE:
+			render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
+			break;
+		case SEQUENCE_OF:
+			render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
+			render_opcode(out, "_jump_target(%u),\n", entry);
+			break;
+		case SET:
+			render_opcode(out, "ASN1_OP_END_SET%s,\n", act);
+			break;
+		case SET_OF:
+			render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
+			render_opcode(out, "_jump_target(%u),\n", entry);
+			break;
+		}
+		if (e->action)
+			render_opcode(out, "_action(ACT_%s),\n",
+				      e->action->name);
+		render_opcode(out, "ASN1_OP_RETURN,\n");
+	}
+}
+
+/*
+ * Render an element.
+ */
+static void render_element(FILE *out, struct element *e, struct element *tag)
+{
+	struct element *ec;
+	const char *cond, *act;
+	int entry, skippable = 0, outofline = 0;
+
+	if (e->flags & ELEMENT_SKIPPABLE ||
+	    (tag && tag->flags & ELEMENT_SKIPPABLE))
+		skippable = 1;
+
+	if ((e->type_def && e->type_def->ref_count > 1) ||
+	    skippable)
+		outofline = 1;
+
+	if (e->type_def && out) {
+		render_more(out, "\t// %*.*s\n",
+			    (int)e->type_def->name->size, (int)e->type_def->name->size,
+			    e->type_def->name->value);
+	}
+
+	/* Render the operation */
+	cond = (e->flags & ELEMENT_CONDITIONAL ||
+		(tag && tag->flags & ELEMENT_CONDITIONAL)) ? "COND_" : "";
+	act = e->action ? "_ACT" : "";
+	switch (e->compound) {
+	case ANY:
+		render_opcode(out, "ASN1_OP_%sMATCH_ANY%s,", cond, act);
+		if (e->name)
+			render_more(out, "\t\t// %*.*s",
+				    (int)e->name->size, (int)e->name->size,
+				    e->name->value);
+		render_more(out, "\n");
+		goto dont_render_tag;
+
+	case TAG_OVERRIDE:
+		render_element(out, e->children, e);
+		return;
+
+	case SEQUENCE:
+	case SEQUENCE_OF:
+	case SET:
+	case SET_OF:
+		render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
+			      cond,
+			      outofline ? "_JUMP" : "",
+			      skippable ? "_OR_SKIP" : "");
+		break;
+
+	case CHOICE:
+		goto dont_render_tag;
+
+	case TYPE_REF:
+		if (e->class == ASN1_UNIV && e->method == ASN1_PRIM && e->tag == 0)
+			goto dont_render_tag;
+	default:
+		render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
+			      cond, act,
+			      skippable ? "_OR_SKIP" : "");
+		break;
+	}
+
+	if (e->name)
+		render_more(out, "\t\t// %*.*s",
+			    (int)e->name->size, (int)e->name->size,
+			    e->name->value);
+	render_more(out, "\n");
+
+	/* Render the tag */
+	if (!tag)
+		tag = e;
+	if (tag->class == ASN1_UNIV &&
+	    tag->tag != 14 &&
+	    tag->tag != 15 &&
+	    tag->tag != 31)
+		render_opcode(out, "_tag(%s, %s, %s),\n",
+			      asn1_classes[tag->class],
+			      asn1_methods[tag->method | e->method],
+			      asn1_universal_tags[tag->tag]);
+	else
+		render_opcode(out, "_tagn(%s, %s, %2u),\n",
+			      asn1_classes[tag->class],
+			      asn1_methods[tag->method | e->method],
+			      tag->tag);
+	tag = NULL;
+dont_render_tag:
+
+	/* Deal with compound types */
+	switch (e->compound) {
+	case TYPE_REF:
+		render_element(out, e->type->type->element, tag);
+		if (e->action)
+			render_opcode(out, "ASN1_OP_ACT,\n");
+		break;
+
+	case SEQUENCE:
+		if (outofline) {
+			/* Render out-of-line for multiple use or
+			 * skipability */
+			render_opcode(out, "_jump_target(%u),", e->entry_index);
+			if (e->type_def && e->type_def->name)
+				render_more(out, "\t\t// --> %*.*s",
+					    (int)e->type_def->name->size,
+					    (int)e->type_def->name->size,
+					    e->type_def->name->value);
+			render_more(out, "\n");
+			if (!(e->flags & ELEMENT_RENDERED)) {
+				e->flags |= ELEMENT_RENDERED;
+				*render_list_p = e;
+				render_list_p = &e->render_next;
+			}
+			return;
+		} else {
+			/* Render inline for single use */
+			render_depth++;
+			for (ec = e->children; ec; ec = ec->next)
+				render_element(out, ec, NULL);
+			render_depth--;
+			render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
+		}
+		break;
+
+	case SEQUENCE_OF:
+	case SET_OF:
+		if (outofline) {
+			/* Render out-of-line for multiple use or
+			 * skipability */
+			render_opcode(out, "_jump_target(%u),", e->entry_index);
+			if (e->type_def && e->type_def->name)
+				render_more(out, "\t\t// --> %*.*s",
+					    (int)e->type_def->name->size,
+					    (int)e->type_def->name->size,
+					    e->type_def->name->value);
+			render_more(out, "\n");
+			if (!(e->flags & ELEMENT_RENDERED)) {
+				e->flags |= ELEMENT_RENDERED;
+				*render_list_p = e;
+				render_list_p = &e->render_next;
+			}
+			return;
+		} else {
+			/* Render inline for single use */
+			entry = nr_entries;
+			render_depth++;
+			render_element(out, e->children, NULL);
+			render_depth--;
+			if (e->compound == SEQUENCE_OF)
+				render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
+			else
+				render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
+			render_opcode(out, "_jump_target(%u),\n", entry);
+		}
+		break;
+
+	case SET:
+		/* I can't think of a nice way to do SET support without having
+		 * a stack of bitmasks to make sure no element is repeated.
+		 * The bitmask has also to be checked that no non-optional
+		 * elements are left out whilst not preventing optional
+		 * elements from being left out.
+		 */
+		fprintf(stderr, "The ASN.1 SET type is not currently supported.\n");
+		exit(1);
+
+	case CHOICE:
+		for (ec = e->children; ec; ec = ec->next)
+			render_element(out, ec, NULL);
+		if (!skippable)
+			render_opcode(out, "ASN1_OP_COND_FAIL,\n");
+		if (e->action)
+			render_opcode(out, "ASN1_OP_ACT,\n");
+		break;
+
+	default:
+		break;
+	}
+
+	if (e->action)
+		render_opcode(out, "_action(ACT_%s),\n", e->action->name);
+}
-- 
cgit v1.2.3-59-g8ed1b


From 42d5ec27f873c654a68f7f865dcd7737513e9508 Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Mon, 24 Sep 2012 17:11:16 +0100
Subject: X.509: Add an ASN.1 decoder

Add an ASN.1 BER/DER/CER decoder.  This uses the bytecode from the ASN.1
compiler in the previous patch to inform it as to what to expect to find in the
encoded byte stream.  The output from the compiler also tells it what functions
to call on what tags, thus allowing the caller to retrieve information.

The decoder is called as follows:

	int asn1_decoder(const struct asn1_decoder *decoder,
			 void *context,
			 const unsigned char *data,
			 size_t datalen);

The decoder argument points to the bytecode from the ASN.1 compiler.  context
is the caller's context and is passed to the action functions.  data and
datalen define the byte stream to be decoded.

Note that the decoder is currently limited to datalen being less than 64K.
This reduces the amount of stack space used by the decoder because ASN.1 is a
nested construct.  Similarly, the decoder is limited to a maximum of 10 levels
of constructed data outside of a leaf node also in an effort to keep stack
usage down.

These restrictions can be raised if necessary.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 include/linux/asn1_decoder.h |  24 +++
 lib/Makefile                 |   2 +
 lib/asn1_decoder.c           | 477 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 503 insertions(+)
 create mode 100644 include/linux/asn1_decoder.h
 create mode 100644 lib/asn1_decoder.c

(limited to 'include')

diff --git a/include/linux/asn1_decoder.h b/include/linux/asn1_decoder.h
new file mode 100644
index 000000000000..fa2ff5bc0483
--- /dev/null
+++ b/include/linux/asn1_decoder.h
@@ -0,0 +1,24 @@
+/* ASN.1 decoder
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#ifndef _LINUX_ASN1_DECODER_H
+#define _LINUX_ASN1_DECODER_H
+
+#include <linux/asn1.h>
+
+struct asn1_decoder;
+
+extern int asn1_ber_decoder(const struct asn1_decoder *decoder,
+			    void *context,
+			    const unsigned char *data,
+			    size_t datalen);
+
+#endif /* _LINUX_ASN1_DECODER_H */
diff --git a/lib/Makefile b/lib/Makefile
index b0428960939f..ca856b69a21d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -140,6 +140,8 @@ $(foreach file, $(libfdt_files), \
 	$(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt))
 lib-$(CONFIG_LIBFDT) += $(libfdt_files)
 
+obj-$(CONFIG_ASN1) += asn1_decoder.o
+
 hostprogs-y	:= gen_crc32table
 clean-files	:= crc32table.h
 
diff --git a/lib/asn1_decoder.c b/lib/asn1_decoder.c
new file mode 100644
index 000000000000..2e4196ddf06f
--- /dev/null
+++ b/lib/asn1_decoder.c
@@ -0,0 +1,477 @@
+/* Decoder for ASN.1 BER/DER/CER encoded bytestream
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <linux/export.h>
+#include <linux/kernel.h>
+#include <linux/errno.h>
+#include <linux/asn1_decoder.h>
+#include <linux/asn1_ber_bytecode.h>
+
+static const unsigned char asn1_op_lengths[ASN1_OP__NR] = {
+	/*					OPC TAG JMP ACT */
+	[ASN1_OP_MATCH]				= 1 + 1,
+	[ASN1_OP_MATCH_OR_SKIP]			= 1 + 1,
+	[ASN1_OP_MATCH_ACT]			= 1 + 1     + 1,
+	[ASN1_OP_MATCH_ACT_OR_SKIP]		= 1 + 1     + 1,
+	[ASN1_OP_MATCH_JUMP]			= 1 + 1 + 1,
+	[ASN1_OP_MATCH_JUMP_OR_SKIP]		= 1 + 1 + 1,
+	[ASN1_OP_MATCH_ANY]			= 1,
+	[ASN1_OP_MATCH_ANY_ACT]			= 1         + 1,
+	[ASN1_OP_COND_MATCH_OR_SKIP]		= 1 + 1,
+	[ASN1_OP_COND_MATCH_ACT_OR_SKIP]	= 1 + 1     + 1,
+	[ASN1_OP_COND_MATCH_JUMP_OR_SKIP]	= 1 + 1 + 1,
+	[ASN1_OP_COND_MATCH_ANY]		= 1,
+	[ASN1_OP_COND_MATCH_ANY_ACT]		= 1         + 1,
+	[ASN1_OP_COND_FAIL]			= 1,
+	[ASN1_OP_COMPLETE]			= 1,
+	[ASN1_OP_ACT]				= 1         + 1,
+	[ASN1_OP_RETURN]			= 1,
+	[ASN1_OP_END_SEQ]			= 1,
+	[ASN1_OP_END_SEQ_OF]			= 1     + 1,
+	[ASN1_OP_END_SET]			= 1,
+	[ASN1_OP_END_SET_OF]			= 1     + 1,
+	[ASN1_OP_END_SEQ_ACT]			= 1         + 1,
+	[ASN1_OP_END_SEQ_OF_ACT]		= 1     + 1 + 1,
+	[ASN1_OP_END_SET_ACT]			= 1         + 1,
+	[ASN1_OP_END_SET_OF_ACT]		= 1     + 1 + 1,
+};
+
+/*
+ * Find the length of an indefinite length object
+ */
+static int asn1_find_indefinite_length(const unsigned char *data, size_t datalen,
+				       const char **_errmsg, size_t *_err_dp)
+{
+	unsigned char tag, tmp;
+	size_t dp = 0, len, n;
+	int indef_level = 1;
+
+next_tag:
+	if (unlikely(datalen - dp < 2)) {
+		if (datalen == dp)
+			goto missing_eoc;
+		goto data_overrun_error;
+	}
+
+	/* Extract a tag from the data */
+	tag = data[dp++];
+	if (tag == 0) {
+		/* It appears to be an EOC. */
+		if (data[dp++] != 0)
+			goto invalid_eoc;
+		if (--indef_level <= 0)
+			return dp;
+		goto next_tag;
+	}
+
+	if (unlikely((tag & 0x1f) == 0x1f)) {
+		do {
+			if (unlikely(datalen - dp < 2))
+				goto data_overrun_error;
+			tmp = data[dp++];
+		} while (tmp & 0x80);
+	}
+
+	/* Extract the length */
+	len = data[dp++];
+	if (len < 0x7f) {
+		dp += len;
+		goto next_tag;
+	}
+
+	if (unlikely(len == 0x80)) {
+		/* Indefinite length */
+		if (unlikely((tag & ASN1_CONS_BIT) == ASN1_PRIM << 5))
+			goto indefinite_len_primitive;
+		indef_level++;
+		goto next_tag;
+	}
+
+	n = len - 0x80;
+	if (unlikely(n > sizeof(size_t) - 1))
+		goto length_too_long;
+	if (unlikely(n > datalen - dp))
+		goto data_overrun_error;
+	for (len = 0; n > 0; n--) {
+		len <<= 8;
+		len |= data[dp++];
+	}
+	dp += len;
+	goto next_tag;
+
+length_too_long:
+	*_errmsg = "Unsupported length";
+	goto error;
+indefinite_len_primitive:
+	*_errmsg = "Indefinite len primitive not permitted";
+	goto error;
+invalid_eoc:
+	*_errmsg = "Invalid length EOC";
+	goto error;
+data_overrun_error:
+	*_errmsg = "Data overrun error";
+	goto error;
+missing_eoc:
+	*_errmsg = "Missing EOC in indefinite len cons";
+error:
+	*_err_dp = dp;
+	return -1;
+}
+
+/**
+ * asn1_ber_decoder - Decoder BER/DER/CER ASN.1 according to pattern
+ * @decoder: The decoder definition (produced by asn1_compiler)
+ * @context: The caller's context (to be passed to the action functions)
+ * @data: The encoded data
+ * @datasize: The size of the encoded data
+ *
+ * Decode BER/DER/CER encoded ASN.1 data according to a bytecode pattern
+ * produced by asn1_compiler.  Action functions are called on marked tags to
+ * allow the caller to retrieve significant data.
+ *
+ * LIMITATIONS:
+ *
+ * To keep down the amount of stack used by this function, the following limits
+ * have been imposed:
+ *
+ *  (1) This won't handle datalen > 65535 without increasing the size of the
+ *	cons stack elements and length_too_long checking.
+ *
+ *  (2) The stack of constructed types is 10 deep.  If the depth of non-leaf
+ *	constructed types exceeds this, the decode will fail.
+ *
+ *  (3) The SET type (not the SET OF type) isn't really supported as tracking
+ *	what members of the set have been seen is a pain.
+ */
+int asn1_ber_decoder(const struct asn1_decoder *decoder,
+		     void *context,
+		     const unsigned char *data,
+		     size_t datalen)
+{
+	const unsigned char *machine = decoder->machine;
+	const asn1_action_t *actions = decoder->actions;
+	size_t machlen = decoder->machlen;
+	enum asn1_opcode op;
+	unsigned char tag = 0, csp = 0, jsp = 0, optag = 0, hdr = 0;
+	const char *errmsg;
+	size_t pc = 0, dp = 0, tdp = 0, len = 0;
+	int ret;
+
+	unsigned char flags = 0;
+#define FLAG_INDEFINITE_LENGTH	0x01
+#define FLAG_MATCHED		0x02
+#define FLAG_CONS		0x20 /* Corresponds to CONS bit in the opcode tag
+				      * - ie. whether or not we are going to parse
+				      *   a compound type.
+				      */
+
+#define NR_CONS_STACK 10
+	unsigned short cons_dp_stack[NR_CONS_STACK];
+	unsigned short cons_datalen_stack[NR_CONS_STACK];
+	unsigned char cons_hdrlen_stack[NR_CONS_STACK];
+#define NR_JUMP_STACK 10
+	unsigned char jump_stack[NR_JUMP_STACK];
+
+	if (datalen > 65535)
+		return -EMSGSIZE;
+
+next_op:
+	pr_debug("next_op: pc=\e[32m%zu\e[m/%zu dp=\e[33m%zu\e[m/%zu C=%d J=%d\n",
+		 pc, machlen, dp, datalen, csp, jsp);
+	if (unlikely(pc >= machlen))
+		goto machine_overrun_error;
+	op = machine[pc];
+	if (unlikely(pc + asn1_op_lengths[op] > machlen))
+		goto machine_overrun_error;
+
+	/* If this command is meant to match a tag, then do that before
+	 * evaluating the command.
+	 */
+	if (op <= ASN1_OP__MATCHES_TAG) {
+		unsigned char tmp;
+
+		/* Skip conditional matches if possible */
+		if ((op & ASN1_OP_MATCH__COND &&
+		     flags & FLAG_MATCHED) ||
+		    dp == datalen) {
+			pc += asn1_op_lengths[op];
+			goto next_op;
+		}
+
+		flags = 0;
+		hdr = 2;
+
+		/* Extract a tag from the data */
+		if (unlikely(dp >= datalen - 1))
+			goto data_overrun_error;
+		tag = data[dp++];
+		if (unlikely((tag & 0x1f) == 0x1f))
+			goto long_tag_not_supported;
+
+		if (op & ASN1_OP_MATCH__ANY) {
+			pr_debug("- any %02x\n", tag);
+		} else {
+			/* Extract the tag from the machine
+			 * - Either CONS or PRIM are permitted in the data if
+			 *   CONS is not set in the op stream, otherwise CONS
+			 *   is mandatory.
+			 */
+			optag = machine[pc + 1];
+			flags |= optag & FLAG_CONS;
+
+			/* Determine whether the tag matched */
+			tmp = optag ^ tag;
+			tmp &= ~(optag & ASN1_CONS_BIT);
+			pr_debug("- match? %02x %02x %02x\n", tag, optag, tmp);
+			if (tmp != 0) {
+				/* All odd-numbered tags are MATCH_OR_SKIP. */
+				if (op & ASN1_OP_MATCH__SKIP) {
+					pc += asn1_op_lengths[op];
+					dp--;
+					goto next_op;
+				}
+				goto tag_mismatch;
+			}
+		}
+		flags |= FLAG_MATCHED;
+
+		len = data[dp++];
+		if (len > 0x7f) {
+			if (unlikely(len == 0x80)) {
+				/* Indefinite length */
+				if (unlikely(!(tag & ASN1_CONS_BIT)))
+					goto indefinite_len_primitive;
+				flags |= FLAG_INDEFINITE_LENGTH;
+				if (unlikely(2 > datalen - dp))
+					goto data_overrun_error;
+			} else {
+				int n = len - 0x80;
+				if (unlikely(n > 2))
+					goto length_too_long;
+				if (unlikely(dp >= datalen - n))
+					goto data_overrun_error;
+				hdr += n;
+				for (len = 0; n > 0; n--) {
+					len <<= 8;
+					len |= data[dp++];
+				}
+				if (unlikely(len > datalen - dp))
+					goto data_overrun_error;
+			}
+		}
+
+		if (flags & FLAG_CONS) {
+			/* For expected compound forms, we stack the positions
+			 * of the start and end of the data.
+			 */
+			if (unlikely(csp >= NR_CONS_STACK))
+				goto cons_stack_overflow;
+			cons_dp_stack[csp] = dp;
+			cons_hdrlen_stack[csp] = hdr;
+			if (!(flags & FLAG_INDEFINITE_LENGTH)) {
+				cons_datalen_stack[csp] = datalen;
+				datalen = dp + len;
+			} else {
+				cons_datalen_stack[csp] = 0;
+			}
+			csp++;
+		}
+
+		pr_debug("- TAG: %02x %zu%s\n",
+			 tag, len, flags & FLAG_CONS ? " CONS" : "");
+		tdp = dp;
+	}
+
+	/* Decide how to handle the operation */
+	switch (op) {
+	case ASN1_OP_MATCH_ANY_ACT:
+	case ASN1_OP_COND_MATCH_ANY_ACT:
+		ret = actions[machine[pc + 1]](context, hdr, tag, data + dp, len);
+		if (ret < 0)
+			return ret;
+		goto skip_data;
+
+	case ASN1_OP_MATCH_ACT:
+	case ASN1_OP_MATCH_ACT_OR_SKIP:
+	case ASN1_OP_COND_MATCH_ACT_OR_SKIP:
+		ret = actions[machine[pc + 2]](context, hdr, tag, data + dp, len);
+		if (ret < 0)
+			return ret;
+		goto skip_data;
+
+	case ASN1_OP_MATCH:
+	case ASN1_OP_MATCH_OR_SKIP:
+	case ASN1_OP_MATCH_ANY:
+	case ASN1_OP_COND_MATCH_OR_SKIP:
+	case ASN1_OP_COND_MATCH_ANY:
+	skip_data:
+		if (!(flags & FLAG_CONS)) {
+			if (flags & FLAG_INDEFINITE_LENGTH) {
+				len = asn1_find_indefinite_length(
+					data + dp, datalen - dp, &errmsg, &dp);
+				if (len < 0)
+					goto error;
+			}
+			pr_debug("- LEAF: %zu\n", len);
+			dp += len;
+		}
+		pc += asn1_op_lengths[op];
+		goto next_op;
+
+	case ASN1_OP_MATCH_JUMP:
+	case ASN1_OP_MATCH_JUMP_OR_SKIP:
+	case ASN1_OP_COND_MATCH_JUMP_OR_SKIP:
+		pr_debug("- MATCH_JUMP\n");
+		if (unlikely(jsp == NR_JUMP_STACK))
+			goto jump_stack_overflow;
+		jump_stack[jsp++] = pc + asn1_op_lengths[op];
+		pc = machine[pc + 2];
+		goto next_op;
+
+	case ASN1_OP_COND_FAIL:
+		if (unlikely(!(flags & FLAG_MATCHED)))
+			goto tag_mismatch;
+		pc += asn1_op_lengths[op];
+		goto next_op;
+
+	case ASN1_OP_COMPLETE:
+		if (unlikely(jsp != 0 || csp != 0)) {
+			pr_err("ASN.1 decoder error: Stacks not empty at completion (%u, %u)\n",
+			       jsp, csp);
+			return -EBADMSG;
+		}
+		return 0;
+
+	case ASN1_OP_END_SET:
+	case ASN1_OP_END_SET_ACT:
+		if (unlikely(!(flags & FLAG_MATCHED)))
+			goto tag_mismatch;
+	case ASN1_OP_END_SEQ:
+	case ASN1_OP_END_SET_OF:
+	case ASN1_OP_END_SEQ_OF:
+	case ASN1_OP_END_SEQ_ACT:
+	case ASN1_OP_END_SET_OF_ACT:
+	case ASN1_OP_END_SEQ_OF_ACT:
+		if (unlikely(csp <= 0))
+			goto cons_stack_underflow;
+		csp--;
+		tdp = cons_dp_stack[csp];
+		hdr = cons_hdrlen_stack[csp];
+		len = datalen;
+		datalen = cons_datalen_stack[csp];
+		pr_debug("- end cons t=%zu dp=%zu l=%zu/%zu\n",
+			 tdp, dp, len, datalen);
+		if (datalen == 0) {
+			/* Indefinite length - check for the EOC. */
+			datalen = len;
+			if (unlikely(datalen - dp < 2))
+				goto data_overrun_error;
+			if (data[dp++] != 0) {
+				if (op & ASN1_OP_END__OF) {
+					dp--;
+					csp++;
+					pc = machine[pc + 1];
+					pr_debug("- continue\n");
+					goto next_op;
+				}
+				goto missing_eoc;
+			}
+			if (data[dp++] != 0)
+				goto invalid_eoc;
+			len = dp - tdp - 2;
+		} else {
+			if (dp < len && (op & ASN1_OP_END__OF)) {
+				datalen = len;
+				csp++;
+				pc = machine[pc + 1];
+				pr_debug("- continue\n");
+				goto next_op;
+			}
+			if (dp != len)
+				goto cons_length_error;
+			len -= tdp;
+			pr_debug("- cons len l=%zu d=%zu\n", len, dp - tdp);
+		}
+
+		if (op & ASN1_OP_END__ACT) {
+			unsigned char act;
+			if (op & ASN1_OP_END__OF)
+				act = machine[pc + 2];
+			else
+				act = machine[pc + 1];
+			ret = actions[act](context, hdr, 0, data + tdp, len);
+		}
+		pc += asn1_op_lengths[op];
+		goto next_op;
+
+	case ASN1_OP_ACT:
+		ret = actions[machine[pc + 1]](context, hdr, tag, data + tdp, len);
+		pc += asn1_op_lengths[op];
+		goto next_op;
+
+	case ASN1_OP_RETURN:
+		if (unlikely(jsp <= 0))
+			goto jump_stack_underflow;
+		pc = jump_stack[--jsp];
+		goto next_op;
+
+	default:
+		break;
+	}
+
+	/* Shouldn't reach here */
+	pr_err("ASN.1 decoder error: Found reserved opcode (%u)\n", op);
+	return -EBADMSG;
+
+data_overrun_error:
+	errmsg = "Data overrun error";
+	goto error;
+machine_overrun_error:
+	errmsg = "Machine overrun error";
+	goto error;
+jump_stack_underflow:
+	errmsg = "Jump stack underflow";
+	goto error;
+jump_stack_overflow:
+	errmsg = "Jump stack overflow";
+	goto error;
+cons_stack_underflow:
+	errmsg = "Cons stack underflow";
+	goto error;
+cons_stack_overflow:
+	errmsg = "Cons stack overflow";
+	goto error;
+cons_length_error:
+	errmsg = "Cons length error";
+	goto error;
+missing_eoc:
+	errmsg = "Missing EOC in indefinite len cons";
+	goto error;
+invalid_eoc:
+	errmsg = "Invalid length EOC";
+	goto error;
+length_too_long:
+	errmsg = "Unsupported length";
+	goto error;
+indefinite_len_primitive:
+	errmsg = "Indefinite len primitive not permitted";
+	goto error;
+tag_mismatch:
+	errmsg = "Unexpected tag";
+	goto error;
+long_tag_not_supported:
+	errmsg = "Long tag not supported";
+error:
+	pr_debug("\nASN1: %s [m=%zu d=%zu ot=%02x t=%02x l=%zu]\n",
+		 errmsg, pc, dp, optag, tag, len);
+	return -EBADMSG;
+}
+EXPORT_SYMBOL_GPL(asn1_ber_decoder);
-- 
cgit v1.2.3-59-g8ed1b


From e1045992949160b56309b730b8bdc428f2f8b69e Mon Sep 17 00:00:00 2001
From: David Howells <dhowells@redhat.com>
Date: Mon, 24 Sep 2012 17:11:27 +0100
Subject: MPILIB: Provide a function to read raw data into an MPI

Provide a function to read raw data of a predetermined size into an MPI rather
than expecting the size to be encoded within the data.  The data is assumed to
represent an unsigned integer, and the resulting MPI will be positive.

The function looks like this:

	MPI mpi_read_raw_data(const void *, size_t);

This is useful for reading ASN.1 integer primitives where the length is encoded
in the ASN.1 metadata.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 include/linux/mpi.h |  1 +
 lib/mpi/mpicoder.c  | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 56 insertions(+)

(limited to 'include')

diff --git a/include/linux/mpi.h b/include/linux/mpi.h
index d02cca6cc8ce..5af1b81def49 100644
--- a/include/linux/mpi.h
+++ b/include/linux/mpi.h
@@ -76,6 +76,7 @@ void mpi_swap(MPI a, MPI b);
 
 /*-- mpicoder.c --*/
 MPI do_encode_md(const void *sha_buffer, unsigned nbits);
+MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes);
 MPI mpi_read_from_buffer(const void *buffer, unsigned *ret_nread);
 int mpi_fromstr(MPI val, const char *str);
 u32 mpi_get_keyid(MPI a, u32 *keyid);
diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c
index f0fa65995800..3962b7f7fe3f 100644
--- a/lib/mpi/mpicoder.c
+++ b/lib/mpi/mpicoder.c
@@ -18,10 +18,65 @@
  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  */
 
+#include <linux/bitops.h>
+#include <asm-generic/bitops/count_zeros.h>
 #include "mpi-internal.h"
 
 #define MAX_EXTERN_MPI_BITS 16384
 
+/**
+ * mpi_read_raw_data - Read a raw byte stream as a positive integer
+ * @xbuffer: The data to read
+ * @nbytes: The amount of data to read
+ */
+MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes)
+{
+	const uint8_t *buffer = xbuffer;
+	int i, j;
+	unsigned nbits, nlimbs;
+	mpi_limb_t a;
+	MPI val = NULL;
+
+	while (nbytes >= 0 && buffer[0] == 0) {
+		buffer++;
+		nbytes--;
+	}
+
+	nbits = nbytes * 8;
+	if (nbits > MAX_EXTERN_MPI_BITS) {
+		pr_info("MPI: mpi too large (%u bits)\n", nbits);
+		return NULL;
+	}
+	if (nbytes > 0)
+		nbits -= count_leading_zeros(buffer[0]);
+	else
+		nbits = 0;
+
+	nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
+	val = mpi_alloc(nlimbs);
+	if (!val)
+		return NULL;
+	val->nbits = nbits;
+	val->sign = 0;
+	val->nlimbs = nlimbs;
+
+	if (nbytes > 0) {
+		i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
+		i %= BYTES_PER_MPI_LIMB;
+		for (j = nlimbs; j > 0; j--) {
+			a = 0;
+			for (; i < BYTES_PER_MPI_LIMB; i++) {
+				a <<= 8;
+				a |= *buffer++;
+			}
+			i = 0;
+			val->d[j - 1] = a;
+		}
+	}
+	return val;
+}
+EXPORT_SYMBOL_GPL(mpi_read_raw_data);
+
 MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread)
 {
 	const uint8_t *buffer = xbuffer;
-- 
cgit v1.2.3-59-g8ed1b


From 106a4ee258d14818467829bf0e12aeae14c16cd7 Mon Sep 17 00:00:00 2001
From: Rusty Russell <rusty@rustcorp.com.au>
Date: Wed, 26 Sep 2012 10:09:40 +0100
Subject: module: signature checking hook

We do a very simple search for a particular string appended to the module
(which is cache-hot and about to be SHA'd anyway).  There's both a config
option and a boot parameter which control whether we accept or fail with
unsigned modules and modules that are signed with an unknown key.

If module signing is enabled, the kernel will be tainted if a module is
loaded that is unsigned or has a signature for which we don't have the
key.

(Useful feedback and tweaks by David Howells <dhowells@redhat.com>)

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 Documentation/kernel-parameters.txt |  6 +++
 include/linux/module.h              |  8 ++++
 init/Kconfig                        | 14 ++++++
 kernel/Makefile                     |  1 +
 kernel/module-internal.h            | 13 ++++++
 kernel/module.c                     | 93 ++++++++++++++++++++++++++++++++++++-
 kernel/module_signing.c             | 23 +++++++++
 7 files changed, 157 insertions(+), 1 deletion(-)
 create mode 100644 kernel/module-internal.h
 create mode 100644 kernel/module_signing.c

(limited to 'include')

diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt
index ad7e2e5088c1..9b2b8d3ae3e0 100644
--- a/Documentation/kernel-parameters.txt
+++ b/Documentation/kernel-parameters.txt
@@ -1582,6 +1582,12 @@ bytes respectively. Such letter suffixes can also be entirely omitted.
 			log everything. Information is printed at KERN_DEBUG
 			so loglevel=8 may also need to be specified.
 
+	module.sig_enforce
+			[KNL] When CONFIG_MODULE_SIG is set, this means that
+			modules without (valid) signatures will fail to load.
+			Note that if CONFIG_MODULE_SIG_ENFORCE is set, that
+			is always true, so this option does nothing.
+
 	mousedev.tap_time=
 			[MOUSE] Maximum time between finger touching and
 			leaving touchpad surface for touch to be considered
diff --git a/include/linux/module.h b/include/linux/module.h
index fbcafe2ee13e..7760c6d344a3 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -21,6 +21,9 @@
 #include <linux/percpu.h>
 #include <asm/module.h>
 
+/* In stripped ARM and x86-64 modules, ~ is surprisingly rare. */
+#define MODULE_SIG_STRING "~Module signature appended~\n"
+
 /* Not Yet Implemented */
 #define MODULE_SUPPORTED_DEVICE(name)
 
@@ -260,6 +263,11 @@ struct module
 	const unsigned long *unused_gpl_crcs;
 #endif
 
+#ifdef CONFIG_MODULE_SIG
+	/* Signature was verified. */
+	bool sig_ok;
+#endif
+
 	/* symbols that will be GPL-only in the near future. */
 	const struct kernel_symbol *gpl_future_syms;
 	const unsigned long *gpl_future_crcs;
diff --git a/init/Kconfig b/init/Kconfig
index 66cc885abbc6..fa8ccad1ea43 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1585,6 +1585,20 @@ config MODULE_SRCVERSION_ALL
 	  the version).  With this option, such a "srcversion" field
 	  will be created for all modules.  If unsure, say N.
 
+config MODULE_SIG
+	bool "Module signature verification"
+	depends on MODULES
+	help
+	  Check modules for valid signatures upon load: the signature
+	  is simply appended to the module. For more information see
+	  Documentation/module-signing.txt.
+
+config MODULE_SIG_FORCE
+	bool "Require modules to be validly signed"
+	depends on MODULE_SIG
+	help
+	  Reject unsigned modules or signed modules for which we don't have a
+	  key.  Without this, such modules will simply taint the kernel.
 endif # MODULES
 
 config INIT_ALL_POSSIBLE
diff --git a/kernel/Makefile b/kernel/Makefile
index c0cc67ad764c..08ba8a6abd1c 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -55,6 +55,7 @@ obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
 obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += module.o
+obj-$(CONFIG_MODULE_SIG) += module_signing.o
 obj-$(CONFIG_KALLSYMS) += kallsyms.o
 obj-$(CONFIG_BSD_PROCESS_ACCT) += acct.o
 obj-$(CONFIG_KEXEC) += kexec.o
diff --git a/kernel/module-internal.h b/kernel/module-internal.h
new file mode 100644
index 000000000000..033c17fd70ef
--- /dev/null
+++ b/kernel/module-internal.h
@@ -0,0 +1,13 @@
+/* Module internals
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+extern int mod_verify_sig(const void *mod, unsigned long modlen,
+			  const void *sig, unsigned long siglen);
diff --git a/kernel/module.c b/kernel/module.c
index 74bc19562ca3..68c564edb2c1 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -58,6 +58,7 @@
 #include <linux/jump_label.h>
 #include <linux/pfn.h>
 #include <linux/bsearch.h>
+#include "module-internal.h"
 
 #define CREATE_TRACE_POINTS
 #include <trace/events/module.h>
@@ -102,6 +103,43 @@ static LIST_HEAD(modules);
 struct list_head *kdb_modules = &modules; /* kdb needs the list of modules */
 #endif /* CONFIG_KGDB_KDB */
 
+#ifdef CONFIG_MODULE_SIG
+#ifdef CONFIG_MODULE_SIG_FORCE
+static bool sig_enforce = true;
+#else
+static bool sig_enforce = false;
+
+static int param_set_bool_enable_only(const char *val,
+				      const struct kernel_param *kp)
+{
+	int err;
+	bool test;
+	struct kernel_param dummy_kp = *kp;
+
+	dummy_kp.arg = &test;
+
+	err = param_set_bool(val, &dummy_kp);
+	if (err)
+		return err;
+
+	/* Don't let them unset it once it's set! */
+	if (!test && sig_enforce)
+		return -EROFS;
+
+	if (test)
+		sig_enforce = true;
+	return 0;
+}
+
+static const struct kernel_param_ops param_ops_bool_enable_only = {
+	.set = param_set_bool_enable_only,
+	.get = param_get_bool,
+};
+#define param_check_bool_enable_only param_check_bool
+
+module_param(sig_enforce, bool_enable_only, 0644);
+#endif /* !CONFIG_MODULE_SIG_FORCE */
+#endif /* CONFIG_MODULE_SIG */
 
 /* Block module loading/unloading? */
 int modules_disabled = 0;
@@ -136,6 +174,7 @@ struct load_info {
 	unsigned long symoffs, stroffs;
 	struct _ddebug *debug;
 	unsigned int num_debug;
+	bool sig_ok;
 	struct {
 		unsigned int sym, str, mod, vers, info, pcpu;
 	} index;
@@ -2379,7 +2418,49 @@ static inline void kmemleak_load_module(const struct module *mod,
 }
 #endif
 
-/* Sets info->hdr and info->len. */
+#ifdef CONFIG_MODULE_SIG
+static int module_sig_check(struct load_info *info,
+			    const void *mod, unsigned long *len)
+{
+	int err = -ENOKEY;
+	const unsigned long markerlen = sizeof(MODULE_SIG_STRING) - 1;
+	const void *p = mod, *end = mod + *len;
+
+	/* Poor man's memmem. */
+	while ((p = memchr(p, MODULE_SIG_STRING[0], end - p))) {
+		if (p + markerlen > end)
+			break;
+
+		if (memcmp(p, MODULE_SIG_STRING, markerlen) == 0) {
+			const void *sig = p + markerlen;
+			/* Truncate module up to signature. */
+			*len = p - mod;
+			err = mod_verify_sig(mod, *len, sig, end - sig);
+			break;
+		}
+		p++;
+	}
+
+	if (!err) {
+		info->sig_ok = true;
+		return 0;
+	}
+
+	/* Not having a signature is only an error if we're strict. */
+	if (err == -ENOKEY && !sig_enforce)
+		err = 0;
+
+	return err;
+}
+#else /* !CONFIG_MODULE_SIG */
+static int module_sig_check(struct load_info *info,
+			    void *mod, unsigned long *len)
+{
+	return 0;
+}
+#endif /* !CONFIG_MODULE_SIG */
+
+/* Sets info->hdr, info->len and info->sig_ok. */
 static int copy_and_check(struct load_info *info,
 			  const void __user *umod, unsigned long len,
 			  const char __user *uargs)
@@ -2399,6 +2480,10 @@ static int copy_and_check(struct load_info *info,
 		goto free_hdr;
 	}
 
+	err = module_sig_check(info, hdr, &len);
+	if (err)
+		goto free_hdr;
+
 	/* Sanity checks against insmoding binaries or wrong arch,
 	   weird elf version */
 	if (memcmp(hdr->e_ident, ELFMAG, SELFMAG) != 0
@@ -2884,6 +2969,12 @@ static struct module *load_module(void __user *umod,
 		goto free_copy;
 	}
 
+#ifdef CONFIG_MODULE_SIG
+	mod->sig_ok = info.sig_ok;
+	if (!mod->sig_ok)
+		add_taint_module(mod, TAINT_FORCED_MODULE);
+#endif
+
 	/* Now module is in final location, initialize linked lists, etc. */
 	err = module_unload_init(mod);
 	if (err)
diff --git a/kernel/module_signing.c b/kernel/module_signing.c
new file mode 100644
index 000000000000..499728aecafb
--- /dev/null
+++ b/kernel/module_signing.c
@@ -0,0 +1,23 @@
+/* Module signature checker
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <linux/kernel.h>
+#include <linux/err.h>
+#include "module-internal.h"
+
+/*
+ * Verify the signature on a module.
+ */
+int mod_verify_sig(const void *mod, unsigned long modlen,
+		   const void *sig, unsigned long siglen)
+{
+	return -ENOKEY;
+}
-- 
cgit v1.2.3-59-g8ed1b