[14/16] X.509: Add an ASN.1 decoder
diff mbox series

Message ID 20120913235005.3575.46218.stgit@warthog.procyon.org.uk
State New, archived
Headers show
Series
  • Asymmetric / Public-key cryptography key type
Related show

Commit Message

David Howells Sept. 13, 2012, 11:50 p.m. UTC
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>
---

 include/linux/asn1_decoder.h |   24 ++
 lib/Makefile                 |    2 
 lib/asn1_decoder.c           |  473 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 499 insertions(+)
 create mode 100644 include/linux/asn1_decoder.h
 create mode 100644 lib/asn1_decoder.c



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Comments

Alan Cox Sept. 14, 2012, 9:39 a.m. UTC | #1
On Fri, 14 Sep 2012 00:50:05 +0100
David Howells <dhowells@redhat.com> wrote:

> 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.

Why do this in the kernel.That appears to be completely insane. Can you
prove it runs in a short bounded time for all inputs, has it been fuzz
tested extensively ?

This kind of crap belongs in user space. Parse it in userspace, pass same
structures and objects to the kernel.

Alan
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
David Howells Sept. 18, 2012, 5:34 p.m. UTC | #2
Alan Cox <alan@lxorguk.ukuu.org.uk> wrote:

> Why do this in the kernel.That appears to be completely insane.

A number of reasons:

 (1) The UEFI signature/key database may contain ASN.1 X.509 certificates and
     we may need to use those very early in the boot process, during initrd.

 (2) Even if userspace is available, offloading the key parsing to userspace
     means we have to have some way to trust what we get back.

 (3) Giving the kernel ASN.1 X.509 certs allows the kernel to verify the
     signature on that cert against a key it gets from the UEFI db.  For that,
     you need the raw cert.

> Can you prove it runs in a short bounded time for all inputs,

Possibly.  I'll have to think about that.  It may be relatively
straightforward.

 (1) The ASN.1 decoder is limited (currently) to a maximum of 64k of data to
     parse.

 (2) The decoder never goes backward through the data.

 (3) The decoder has a strictly limited recursion/nesting stack.

The decoder uses a state machine of a sort produced by the compiler.

 (1) Most nodes in this only have one transition.

 (2) Simple optional nodes are simply marked skippable.

 (3) There are some nodes that are like subroutine calls (for multiple-use
     constructed types), but these must return to the point directly after the
     call.

 (4) There are some nodes that have two transitions.  These are used for
     optional constructed type values (particularly multiple-use ones).
     Basically, they are jump-to-subroutine or skip.  The return must go back
     to the next node.

Writing a perl script to check the sanity of the compiler output should be easy
enough, though it would have to assume that the driver is sane.

> has it been fuzz tested extensively ?

Fuzz testing from a script is very easy, eg:

	#!/bin/sh
	cd /tmp
	sync
	declare -i n i j k
	while true
	do
	    n=$RANDOM
	    j=$RANDOM
	    j=j%10
	    k=0
	    echo $n $j
	    dd if=/dev/urandom of=/tmp/data bs=$n count=1
	    for ((i=1; i<n; i=i+k))
	    do
		dd if=/tmp/data bs=$i count=1 2>/dev/null |
		keyctl padd asymmetric foo @s 2>/dev/null
		k=k+1
		if [ $k -eq 10 ]
		    then
		    echo -n .
		    k=0
		fi
	    done
	    echo
	done

Though I haven't done a great deal of such testing as I want to be able to use
my test machine for other stuff too.  I can, however, run multiple fuzzers simultaneously.

I have also passed a number of bits of X.509 and PKCS#7 through it, and also
some valid ASN.1 that isn't what the decoder is expecting.

	#!/bin/sh

	file=/tmp/x509cert
	if [ "$1" != "" ]
	then
	    file=$1
	fi

	cd /tmp
	sync

	while true
	do
	    openssl req -new -x509 -outform PEM -keyout $file.pem -nodes -subj "/CN=GB/O=Red Hat/OU=Magrathea/CN=Slartibartfast" -out $file.x509 || exit $?

	    openssl x509 -in $file.x509 -inform PEM -outform DER >$file.x509.asn1 || exit $?
	    keyctl padd asymmetric bar @s <$file.x509.asn1 || exit $?

	    n=$RANDOM
	    if [ $n -lt 10 ]; then n=10; fi
	    dd if=/dev/urandom of=$file.stuff bs=$n count=1

	    openssl smime -sign -inkey $file.pem -signer $file.x509 -keyform PEM \
		-in $file.stuff -out $file.pkcs7 -binary -outform DER || exit $?

	    keyctl padd asymmetric baz @s <$file.pkcs7
	done

Unfortunately, the above is somewhat limited in what it can produce.

David
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Alan Cox Sept. 18, 2012, 6:51 p.m. UTC | #3
On Tue, 18 Sep 2012 18:34:12 +0100
David Howells <dhowells@redhat.com> wrote:

> Alan Cox <alan@lxorguk.ukuu.org.uk> wrote:
> 
> > Why do this in the kernel.That appears to be completely insane.
> 
> A number of reasons:
> 
>  (1) The UEFI signature/key database may contain ASN.1 X.509 certificates and
>      we may need to use those very early in the boot process, during initrd.

Ok that makes some sense. Presumably they've also got to fall within what
you trust and sign ?

Alan
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
David Howells Sept. 18, 2012, 10:03 p.m. UTC | #4
David Howells <dhowells@redhat.com> wrote:

> > has it been fuzz tested extensively ?

Also, here's a generator of random binary ASN.1.  I think it should mostly
produce valid X.509, but invalid ASN.1 is okay too.

Run with something like:

	while :; do ./asn1random.pl | keyctl padd asymmetric vlad @s; done

David
---
#!/usr/bin/perl -w
use strict;

my $depth = 0;
my $maxdepth = 12;
my $num_elements = 0;
my $total_elements = 30 + int(rand(400));

print STDERR "SEED: ", srand(), "\n";

###############################################################################
#
# Generate a header
#
###############################################################################
sub emit_asn1_hdr($$)
{
    my ($tag, $len) = @_;
    my $output = "";
    my $l;

    if ($len < 0x80) {
	$l = $len;
    } elsif ($len <= 0xff) {
	$l = 0x81;
    } elsif ($len <= 0xffff) {
	$l = 0x82;
    } elsif ($len <= 0xffffff) {
	$l = 0x83;
    } else {
	$l = 0x84;
    }

    $output .= pack("CC", $tag == -1 ? int(rand(255)) & ~0x20 : $tag, $l);
    if ($len < 0x80) {
    } elsif ($len <= 0xff) {
	$output .= pack("C", $len);
    } elsif ($len <= 0xffff) {
	$output .= pack("n", $len);
    } elsif ($len <= 0xffffff) {
	$output .= pack("Cn", $len >> 16, $len & 0xffff);
    } else {
	$output .= pack("N", $len);
    }

    return $output;
}

###############################################################################
#
# Generate a random primitive
#
###############################################################################
sub emit_asn1_prim($)
{
    my ($tag) = @_;
    my $output;
    my $len = int(rand(255));

    $len = 4; #####################

    $tag = int(rand(255)) & ~0x20
	if ($tag == -1);

    $output = emit_asn1_hdr($tag, $len);

    my $i = $len;
    while ($i > 16) {
	$output .= "abcdefghijklmnop";
	$i -= 16;
    }

    $output .= substr("abcdefghijklmnop", 0, $i);
    return $output;
}

###############################################################################
#
# Generate a random construct
#
###############################################################################
sub emit_asn1_cons($);
sub emit_asn1_cons($)
{
    my $output = "";
    my $count = int(rand(20));
    my ($tag) = @_;

    if ($depth >= $maxdepth) {
	return emit_asn1_prim($tag);
    }

    if ($tag == -1) {
	$tag = int(rand(255)) & ~0x20;
	if ($tag < 0x40 && $tag != 0x11) {
	    $tag = 0x10;
	}
	$tag |= 0x20;
    }

    $depth++;
    while ($count > 0) {
	if (int(rand(4 + $depth)) == 1) {
	    $output .= emit_asn1_cons(-1);
	} else {
	    $output .= emit_asn1_prim(-1);
	}
	$count--;
    }
    $depth--;

    return emit_asn1_hdr($tag, length($output)) . $output;
}

print emit_asn1_cons(-1);
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Peter Jones Sept. 18, 2012, 10:19 p.m. UTC | #5
On Tue, 2012-09-18 at 19:51 +0100, Alan Cox wrote:
> On Tue, 18 Sep 2012 18:34:12 +0100
> David Howells <dhowells@redhat.com> wrote:
> 
> > Alan Cox <alan@lxorguk.ukuu.org.uk> wrote:
> > 
> > > Why do this in the kernel.That appears to be completely insane.
> > 
> > A number of reasons:
> > 
> >  (1) The UEFI signature/key database may contain ASN.1 X.509 certificates and
> >      we may need to use those very early in the boot process, during initrd.
> 
> Ok that makes some sense. Presumably they've also got to fall within what
> you trust and sign ?

The idea is that you implicitly trust keys in the lists maintained by
your system firmware and/or shim ("mok") key databases, or else you
shouldn't have Secure Boot turned on in the first place.  Using these
keys and hashes allows you to e.g. relatively easily add a key you're
using to sign a module you're currently developing, while still *ahem*
enjoying the many benefits of signed modules, kernel, and bootloader.

(Though obviously we would never recommend adding a public key whose
private half you're normally keeping on that same machine.)
David Howells Sept. 18, 2012, 10:26 p.m. UTC | #6
David Howells <dhowells@redhat.com> wrote:

> Also, here's a generator of random binary ASN.1.  I think it should mostly
> produce valid X.509, but invalid ASN.1 is okay too.
> ...
>     $len = 4; #####################

With this line removed, obviously...

David
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
James Morris Sept. 19, 2012, 4:17 a.m. UTC | #7
On Tue, 18 Sep 2012, Alan Cox wrote:

> On Tue, 18 Sep 2012 18:34:12 +0100
> David Howells <dhowells@redhat.com> wrote:
> 
> > Alan Cox <alan@lxorguk.ukuu.org.uk> wrote:
> > 
> > > Why do this in the kernel.That appears to be completely insane.
> > 
> > A number of reasons:
> > 
> >  (1) The UEFI signature/key database may contain ASN.1 X.509 certificates and
> >      we may need to use those very early in the boot process, during initrd.
> 
> Ok that makes some sense.

I'd like to see some serious effort at code review and testing before this 
code is merged.


- James
David Howells Sept. 19, 2012, 1:05 p.m. UTC | #8
David Howells <dhowells@redhat.com> wrote:

> > has it been fuzz tested extensively ?

Here's a perl script to generate validly structured X.509 certificates with
random data in them.  It can be run as follows:

	while :; do ./x509random.pl | keyctl padd asymmetric vlad @s; done

and it can also be made to inject encoding errors:

	while :; do ./x509random.pl 1 | keyctl padd asymmetric vlad @s; done

David
---
#!/usr/bin/perl -w
use strict;

print STDERR "SEED: ", srand(), "\n";

my $do_inject = ($#ARGV == 0);

my $UNIV = 0 << 6;
my $APPL = 1 << 6;
my $CONT = 2 << 6;
my $PRIV = 3 << 6;

my $BOOLEAN	= 0x01;
my $INTEGER	= 0x02;
my $BIT_STRING	= 0x03;
my $OCTET_STRING = 0x04;
my $NULL	= 0x05;
my $OBJ_ID	= 0x06;
my $UTF8String	= 0x0c;
my $SEQUENCE	= 0x10;
my $SET		= 0x11;
my $UTCTime	= 0x17;
my $GeneralizedTime = 0x18;

sub maybe($)
{
    return (int(rand(6)) == 0) ? '' : $_[0];
}

###############################################################################
#
# Generate a header
#
###############################################################################
sub emit_asn1_hdr($$)
{
    my ($tag, $len) = @_;
    my $output = "";
    my $l;

    if ($len < 0x80) {
	$l = $len;
    } elsif ($len <= 0xff) {
	$l = 0x81;
    } elsif ($len <= 0xffff) {
	$l = 0x82;
    } elsif ($len <= 0xffffff) {
	$l = 0x83;
    } else {
	$l = 0x84;
    }

    $output .= pack("CC", $tag == -1 ? int(rand(255)) & ~0x20 : $tag, $l);
    if ($len < 0x80) {
    } elsif ($len <= 0xff) {
	$output .= pack("C", $len);
    } elsif ($len <= 0xffff) {
	$output .= pack("n", $len);
    } elsif ($len <= 0xffffff) {
	$output .= pack("Cn", $len >> 16, $len & 0xffff);
    } else {
	$output .= pack("N", $len);
    }

    return $output;
}

###############################################################################
#
# Generate random data
#
###############################################################################
sub emit_random_data($$)
{
    my ($minlen, $maxlen) = @_;
    my $output = '';

    my $len = $minlen + int(rand($maxlen - $minlen));

    my $i = $len;
    while ($i > 16) {
	$output .= "abcdefghijklmnop";
	$i -= 16;
    }

    $output .= substr("abcdefghijklmnop", 0, $i);
    return $output;
}

###############################################################################
#
# Generate a primitive containing some random data
#
###############################################################################
sub emit_asn1_prim(@)
{
    my ($class, $tag, $minlen, $maxlen) = @_;
    my $content;

    $minlen = 0 if (!$minlen);
    $maxlen = 255 if (!$maxlen);
    $content = ($tag == $NULL) ? '' : emit_random_data($minlen, $maxlen);

    $tag |= $class;
    return emit_asn1_hdr($tag, length($content)) . $content;
}

###############################################################################
#
# Generate an object identifier
#
###############################################################################
my %OIDs = (
    commonName => pack("CCC", 85, 4, 3),
    countryName => pack("CCC", 85, 4, 6),
    organizationName => pack("CCC", 85, 4, 10),
    organizationUnitName => pack("CCC", 85, 4, 11),
    rsaEncryption => pack("CCCCCCCCC", 42, 134, 72, 134, 247, 13, 1, 1, 1),
    sha1WithRSAEncryption => pack("CCCCCCCCC", 42, 134, 72, 134, 247, 13, 1, 1, 5),
    authorityKeyIdentifier => pack("CCC", 85, 29, 35),
    subjectKeyIdentifier => pack("CCC", 85, 29, 14),
    basicConstraints => pack("CCC", 85, 29, 19)
);

sub emit_asn1_OID($$$)
{
    my ($class, $tag, $oid_name) = @_;
    my $oid;
    my $len;

    if (!exists($OIDs{$oid_name})) {
	print STDERR "Unknown OID: $oid_name\n";
	exit(2);
    }

    $oid = $OIDs{$oid_name};
    $len = length($oid);

    $tag |= $class;

    return emit_asn1_hdr($tag, $len) . $oid;
}

###############################################################################
#
# Generate a UTC time
#
###############################################################################
sub emit_asn1_utctime($$)
{
    my ($class, $tag) = @_;
    my $output = "";
    my $len;

    for (my $i = 0; $i < 12; $i++) {
	$output .= pack("C", int(rand(9)) + 0x30);
    }
    $output .= 'Z';

    $len = length($output);

    $tag |= $class;

    return emit_asn1_hdr($tag, $len) . $output;
}

###############################################################################
#
# Generate a generalized time
#
###############################################################################
sub emit_asn1_gentime($$)
{
    my ($class, $tag) = @_;
    my $output = "";
    my $len;

    for (my $i = 0; $i < 14; $i++) {
	$output .= pack("C", int(rand(9)) + 0x30);
    }
    $output .= 'Z';

    $len = length($output);

    $tag |= $class;

    return emit_asn1_hdr($tag, $len) . $output;
}

###############################################################################
#
# Generate a construct
#
###############################################################################
sub emit_asn1_cons($$$)
{
    my ($class, $tag, $content) = @_;
    my $inject = '';

    if ($do_inject) {
	if (int(rand(20)) == 0) {
	    $inject = pack("C", int(rand(255)));
	}
    }

    $tag |= $class | 0x20;
    return emit_asn1_hdr($tag, length($content)) . $content . $inject;
}

###############################################################################
#
# Generate a name
#
###############################################################################
sub emit_x509_AttributeValueAssertion($@)
{
    my ($type, $min, $max) = @_;
    my $output;
    $output  = emit_asn1_OID($UNIV, $OBJ_ID, $type);	# attributeType
    $output .= emit_asn1_prim($UNIV, $UTF8String, $min, $max);	# attributeValue
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_RelativeDistinguishedName()
{
    my $output;
    # Set of AttributeValueAssertion
    $output  = emit_x509_AttributeValueAssertion("countryName", 2, 2);
    $output .= emit_x509_AttributeValueAssertion("organizationName", 3, 10);
    $output .= emit_x509_AttributeValueAssertion("organizationUnitName", 3, 10);
    $output .= emit_x509_AttributeValueAssertion("commonName", 4, 16);
    return emit_asn1_cons($UNIV, $SET, $output);
}

sub emit_x509_Name()
{
    my $output;
    # Sequence of RDN
    $output  = emit_x509_RelativeDistinguishedName();
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

###############################################################################
#
# Generate some X.509 extensions
#
###############################################################################
sub emit_x509_SubjectKeyIdentifier()
{
    my $content = emit_asn1_prim($UNIV, $OCTET_STRING, 10, 20);
    return $content;
}

sub emit_x509_AuthorityKeyIdentifier()
{
    my $content = emit_asn1_prim($CONT, 0, 10, 20);
    my $wrapper = emit_asn1_cons($UNIV, $SEQUENCE, $content);
    return $wrapper;
}

sub emit_x509_BasicConstraints()
{
    my $content = emit_asn1_prim($UNIV, $BIT_STRING, 1, 7);
    return $content;
}

sub emit_x509_Extension($)
{
    my ($ext) = @_;
    my $output;
    my $value = "";

    if ($ext eq "authorityKeyIdentifier") {
	$output = emit_asn1_OID($UNIV, $OBJ_ID, $ext);
	$value = emit_x509_AuthorityKeyIdentifier();
    } elsif ($ext eq "subjectKeyIdentifier") {
	$output = emit_asn1_OID($UNIV, $OBJ_ID, $ext);
	$value = emit_x509_SubjectKeyIdentifier();
    } elsif ($ext eq "basicConstraints") {
	$output = emit_asn1_OID($UNIV, $OBJ_ID, $ext);
	$value = emit_x509_BasicConstraints();
    } else {
	$output = emit_asn1_prim($UNIV, $OBJ_ID, 3, 10);
	$value = emit_random_data(10, 20);
    }

    $output .= maybe emit_asn1_prim($UNIV, $BOOLEAN, 1, 1);	# critical
    $output .= emit_asn1_hdr($UNIV | $OCTET_STRING, length($value)) . $value;

    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_Extensions()
{
    my $output = "";

    # Probably do want a sequence of extensions here
    $output .= maybe emit_x509_Extension("authorityKeyIdentifier");
    $output .= maybe emit_x509_Extension("subjectKeyIdentifier");
    $output .= maybe emit_x509_Extension("basicConstraints");
    $output .= maybe emit_x509_Extension("");
    $output .= maybe emit_x509_Extension("");
    $output .= maybe emit_x509_Extension("");
    $output .= maybe emit_x509_Extension("");

    return emit_asn1_cons($CONT, 3, emit_asn1_cons($UNIV, $SEQUENCE, $output));
}

###############################################################################
#
# Generate an X.509 certificate
#
###############################################################################
sub emit_x509_Time()
{
    # UTCTime or GeneralizedTime
    if (int(rand(2)) == 0) {
	return emit_asn1_utctime($UNIV, $UTCTime);
    } else {
	return emit_asn1_gentime($UNIV, $GeneralizedTime);
    }
}

sub emit_x509_Validity()
{
    my $output;
    $output  = emit_x509_Time();			# notBefore
    $output .= emit_x509_Time();			# notAfter
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_AlgorithmIdentifier($)
{
    my ($oid) = @_;
    my $output;
 
    #$output  = emit_asn1_prim($UNIV, $OBJ_ID);		# algorithm
    $output  = emit_asn1_OID($UNIV, $OBJ_ID, $oid); # algorithm
    $output .= emit_asn1_prim($UNIV, $NULL);		# parameters
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_Version()
{
    my $output = emit_asn1_prim($UNIV, $INTEGER, 0, 3);
    return emit_asn1_cons($CONT, 0, $output);
}

sub emit_x509_SubjectPublicKeyInfo()
{
    my $output;
    $output  = emit_x509_AlgorithmIdentifier("rsaEncryption");	# algorithm
    $output .= emit_asn1_prim($UNIV, $BIT_STRING);	# subjectPublicKey
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_TBSCertificate()
{
    my $output;

    $output  = emit_x509_Version;			# version
    $output .= emit_asn1_prim($UNIV, $INTEGER);		# serialNumber
    $output .= emit_x509_AlgorithmIdentifier("sha1WithRSAEncryption");	# signature
    $output .= emit_x509_Name();			# issuer
    $output .= emit_x509_Validity();			# validity
    $output .= emit_x509_Name();			# subject
    $output .= emit_x509_SubjectPublicKeyInfo();	# subjectPublicKeyInfo
    $output .= maybe emit_asn1_prim($CONT, 1);		# issuerUniqueID
    $output .= maybe emit_asn1_prim($CONT, 2);		# subjectUniqueID
    $output .= emit_x509_Extensions();			# extensions

    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_Certificate()
{
    my $output;

    $output  = emit_x509_TBSCertificate();		# tbsCertificate
    $output .= emit_x509_AlgorithmIdentifier("sha1WithRSAEncryption");	# signatureAlgorithm
    $output .= emit_asn1_prim($UNIV, $BIT_STRING);	# signature

    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

print emit_x509_Certificate();
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
David Howells Sept. 20, 2012, 9:45 a.m. UTC | #9
James Morris <jmorris@namei.org> wrote:

> I'd like to see some serious effort at code review and testing before this 
> code is merged.

With regard to testing, I've run multiple simultaneous instances of a number
of test scripts against it continuously for the best part of a day:

 (1) A script to generate completely random data and attempt to stuff that
     into a key.  The completely random data blob is fed wholly and then
     partially in decreasing amounts to keyctl padd.  Then the script loops
     and starts again.

	./fuzz-x509.sh /tmp/data1

 (2) A script to generate random valid ASN.1:

	while :; do ./asn1random.pl | keyctl padd asymmetric vlad @s; done

 (3) A script to generate correctly formatted X.509 certificates filled with
     random data, including for the RSA key and signature fields.

	while :; do ./x509random.pl | keyctl padd asymmetric vlad @s; done

 (4) A variant of (3) that injects random bytes into the structure, whilst
     correctly maintaining the length counts outside of those.

	while :; do ./x509random.pl -i | keyctl padd asymmetric vlad @s; done

 (5) A script to repeatedly generate valid X.509 certificates and stuff those
     in, and then generate valid PKCS#7 signatures over random data and try to
     stuff those in too (which should fail).

	./x509-stuffer.sh

David
#!/bin/sh
#
# Generate completely random data and attempt to stuff that into a key.
#
# Format:
#
#	fuzz-x509.sh [<tmpfile-prefix>]
#
file=/tmp/data
if [ "$1" != "" ]
then
    file=$1
fi

cd /tmp
sync

declare -i n i j k

while true
do
    n=$RANDOM
    j=$RANDOM
    j=j%10
    k=0
    echo $n $j

    dd if=/dev/urandom of=$file bs=$n count=1
    for ((i=1; i<n; i=i+k))
    do
	dd if=$file bs=$i count=1 2>/dev/null |
	keyctl padd asymmetric foo @s 2>/dev/null
	k=k+1
	if [ $k -eq 10 ]
	    then
	    echo -n .
	    k=0
	fi
    done
    echo
done
#!/usr/bin/perl -w
#
# Generate random but valid ASN.1 data.
#
# Format:
#
#	asn1random.pl >output
#
use strict;

my $depth = 0;
my $maxdepth = 12;

print STDERR "SEED: ", srand(), "\n";

###############################################################################
#
# Generate a header
#
###############################################################################
sub emit_asn1_hdr($$)
{
    my ($tag, $len) = @_;
    my $output = "";
    my $l;

    if ($len < 0x80) {
	$l = $len;
    } elsif ($len <= 0xff) {
	$l = 0x81;
    } elsif ($len <= 0xffff) {
	$l = 0x82;
    } elsif ($len <= 0xffffff) {
	$l = 0x83;
    } else {
	$l = 0x84;
    }

    $output .= pack("CC", $tag == -1 ? int(rand(255)) & ~0x20 : $tag, $l);
    if ($len < 0x80) {
    } elsif ($len <= 0xff) {
	$output .= pack("C", $len);
    } elsif ($len <= 0xffff) {
	$output .= pack("n", $len);
    } elsif ($len <= 0xffffff) {
	$output .= pack("Cn", $len >> 16, $len & 0xffff);
    } else {
	$output .= pack("N", $len);
    }

    return $output;
}

###############################################################################
#
# Generate a random primitive
#
###############################################################################
sub emit_asn1_prim($)
{
    my ($tag) = @_;
    my $output;
    my $len = int(rand(255));

    $tag = int(rand(255)) & ~0x20
	if ($tag == -1);

    $output = emit_asn1_hdr($tag, $len);

    my $i = $len;
    while ($i > 16) {
	$output .= "abcdefghijklmnop";
	$i -= 16;
    }

    $output .= substr("abcdefghijklmnop", 0, $i);
    return $output;
}

###############################################################################
#
# Generate a random construct
#
###############################################################################
sub emit_asn1_cons($);
sub emit_asn1_cons($)
{
    my $output = "";
    my $count = int(rand(20));
    my ($tag) = @_;

    if ($depth >= $maxdepth) {
	return emit_asn1_prim($tag);
    }

    if ($tag == -1) {
	$tag = int(rand(255)) & ~0x20;
	if ($tag < 0x40 && $tag != 0x11) {
	    $tag = 0x10;
	}
	$tag |= 0x20;
    }

    $depth++;
    while ($count > 0) {
	if (int(rand(4 + $depth)) == 1) {
	    $output .= emit_asn1_cons(-1);
	} else {
	    $output .= emit_asn1_prim(-1);
	}
	$count--;
    }
    $depth--;

    return emit_asn1_hdr($tag, length($output)) . $output;
}

print emit_asn1_cons(-1);
#!/usr/bin/perl -w
#
# Generate validly formatted X.509 certificates filled with mostly random data,
# including for the RSA key and signature fields (so it is extremely improbable
# that key will be useful and the signature will verify).
#
# If an argument of any sort is passed this will cause random bytes to be
# inserted into the ASN.1 structure (whilst keeping the lengths of the wrapping
# constructed elements correct).
#
# Format:
#
#	x509random.pl [-i] >output
#
use strict;

print STDERR "SEED: ", srand(), "\n";

my $do_inject = ($#ARGV == 0);

my $UNIV = 0 << 6;
my $APPL = 1 << 6;
my $CONT = 2 << 6;
my $PRIV = 3 << 6;

my $BOOLEAN	= 0x01;
my $INTEGER	= 0x02;
my $BIT_STRING	= 0x03;
my $OCTET_STRING = 0x04;
my $NULL	= 0x05;
my $OBJ_ID	= 0x06;
my $UTF8String	= 0x0c;
my $SEQUENCE	= 0x10;
my $SET		= 0x11;
my $UTCTime	= 0x17;
my $GeneralizedTime = 0x18;

sub maybe($)
{
    return (int(rand(6)) == 0) ? '' : $_[0];
}

###############################################################################
#
# Generate a header
#
###############################################################################
sub emit_asn1_hdr($$)
{
    my ($tag, $len) = @_;
    my $output = "";
    my $l;

    if ($len < 0x80) {
	$l = $len;
    } elsif ($len <= 0xff) {
	$l = 0x81;
    } elsif ($len <= 0xffff) {
	$l = 0x82;
    } elsif ($len <= 0xffffff) {
	$l = 0x83;
    } else {
	$l = 0x84;
    }

    $output .= pack("CC", $tag == -1 ? int(rand(255)) & ~0x20 : $tag, $l);
    if ($len < 0x80) {
    } elsif ($len <= 0xff) {
	$output .= pack("C", $len);
    } elsif ($len <= 0xffff) {
	$output .= pack("n", $len);
    } elsif ($len <= 0xffffff) {
	$output .= pack("Cn", $len >> 16, $len & 0xffff);
    } else {
	$output .= pack("N", $len);
    }

    return $output;
}

###############################################################################
#
# Generate random data
#
###############################################################################
sub emit_random_data($$)
{
    my ($minlen, $maxlen) = @_;
    my $output = '';

    my $len = $minlen + int(rand($maxlen - $minlen));

    my $i = $len;
    while ($i > 16) {
	$output .= "abcdefghijklmnop";
	$i -= 16;
    }

    $output .= substr("abcdefghijklmnop", 0, $i);
    return $output;
}

###############################################################################
#
# Generate a primitive containing some random data
#
###############################################################################
sub emit_asn1_prim(@)
{
    my ($class, $tag, $minlen, $maxlen) = @_;
    my $content;

    $minlen = 0 if (!$minlen);
    $maxlen = 255 if (!$maxlen);
    $content = ($tag == $NULL) ? '' : emit_random_data($minlen, $maxlen);

    $tag |= $class;
    return emit_asn1_hdr($tag, length($content)) . $content;
}

###############################################################################
#
# Generate an object identifier
#
###############################################################################
my %OIDs = (
    commonName => pack("CCC", 85, 4, 3),
    countryName => pack("CCC", 85, 4, 6),
    organizationName => pack("CCC", 85, 4, 10),
    organizationUnitName => pack("CCC", 85, 4, 11),
    rsaEncryption => pack("CCCCCCCCC", 42, 134, 72, 134, 247, 13, 1, 1, 1),
    sha1WithRSAEncryption => pack("CCCCCCCCC", 42, 134, 72, 134, 247, 13, 1, 1, 5),
    authorityKeyIdentifier => pack("CCC", 85, 29, 35),
    subjectKeyIdentifier => pack("CCC", 85, 29, 14),
    basicConstraints => pack("CCC", 85, 29, 19)
);

sub emit_asn1_OID($$$)
{
    my ($class, $tag, $oid_name) = @_;
    my $oid;
    my $len;

    if (!exists($OIDs{$oid_name})) {
	print STDERR "Unknown OID: $oid_name\n";
	exit(2);
    }

    $oid = $OIDs{$oid_name};
    $len = length($oid);

    $tag |= $class;

    return emit_asn1_hdr($tag, $len) . $oid;
}

###############################################################################
#
# Generate a UTC time
#
###############################################################################
sub emit_asn1_utctime($$)
{
    my ($class, $tag) = @_;
    my $output = "";
    my $len;

    for (my $i = 0; $i < 12; $i++) {
	$output .= pack("C", int(rand(9)) + 0x30);
    }
    $output .= 'Z';

    $len = length($output);

    $tag |= $class;

    return emit_asn1_hdr($tag, $len) . $output;
}

###############################################################################
#
# Generate a generalized time
#
###############################################################################
sub emit_asn1_gentime($$)
{
    my ($class, $tag) = @_;
    my $output = "";
    my $len;

    for (my $i = 0; $i < 14; $i++) {
	$output .= pack("C", int(rand(9)) + 0x30);
    }
    $output .= 'Z';

    $len = length($output);

    $tag |= $class;

    return emit_asn1_hdr($tag, $len) . $output;
}

###############################################################################
#
# Generate a construct
#
###############################################################################
sub emit_asn1_cons($$$)
{
    my ($class, $tag, $content) = @_;
    my $inject = '';

    if ($do_inject) {
	if (int(rand(20)) == 0) {
	    $inject = pack("C", int(rand(255)));
	}
    }

    $tag |= $class | 0x20;
    return emit_asn1_hdr($tag, length($content)) . $content . $inject;
}

###############################################################################
#
# Generate a name
#
###############################################################################
sub emit_x509_AttributeValueAssertion($@)
{
    my ($type, $min, $max) = @_;
    my $output;
    $output  = emit_asn1_OID($UNIV, $OBJ_ID, $type);	# attributeType
    $output .= emit_asn1_prim($UNIV, $UTF8String, $min, $max);	# attributeValue
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_RelativeDistinguishedName()
{
    my $output;
    # Set of AttributeValueAssertion
    $output  = emit_x509_AttributeValueAssertion("countryName", 2, 2);
    $output .= emit_x509_AttributeValueAssertion("organizationName", 3, 10);
    $output .= emit_x509_AttributeValueAssertion("organizationUnitName", 3, 10);
    $output .= emit_x509_AttributeValueAssertion("commonName", 4, 16);
    return emit_asn1_cons($UNIV, $SET, $output);
}

sub emit_x509_Name()
{
    my $output;
    # Sequence of RDN
    $output  = emit_x509_RelativeDistinguishedName();
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

###############################################################################
#
# Generate some X.509 extensions
#
###############################################################################
sub emit_x509_SubjectKeyIdentifier()
{
    my $content = emit_asn1_prim($UNIV, $OCTET_STRING, 10, 20);
    return $content;
}

sub emit_x509_AuthorityKeyIdentifier()
{
    my $content = emit_asn1_prim($CONT, 0, 10, 20);
    my $wrapper = emit_asn1_cons($UNIV, $SEQUENCE, $content);
    return $wrapper;
}

sub emit_x509_BasicConstraints()
{
    my $content = emit_asn1_prim($UNIV, $BIT_STRING, 1, 7);
    return $content;
}

sub emit_x509_Extension($)
{
    my ($ext) = @_;
    my $output;
    my $value = "";

    if ($ext eq "authorityKeyIdentifier") {
	$output = emit_asn1_OID($UNIV, $OBJ_ID, $ext);
	$value = emit_x509_AuthorityKeyIdentifier();
    } elsif ($ext eq "subjectKeyIdentifier") {
	$output = emit_asn1_OID($UNIV, $OBJ_ID, $ext);
	$value = emit_x509_SubjectKeyIdentifier();
    } elsif ($ext eq "basicConstraints") {
	$output = emit_asn1_OID($UNIV, $OBJ_ID, $ext);
	$value = emit_x509_BasicConstraints();
    } else {
	$output = emit_asn1_prim($UNIV, $OBJ_ID, 3, 10);
	$value = emit_random_data(10, 20);
    }

    $output .= maybe emit_asn1_prim($UNIV, $BOOLEAN, 1, 1);	# critical
    $output .= emit_asn1_hdr($UNIV | $OCTET_STRING, length($value)) . $value;

    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_Extensions()
{
    my $output = "";

    # Probably do want a sequence of extensions here
    $output .= maybe emit_x509_Extension("authorityKeyIdentifier");
    $output .= maybe emit_x509_Extension("subjectKeyIdentifier");
    $output .= maybe emit_x509_Extension("basicConstraints");
    $output .= maybe emit_x509_Extension("");
    $output .= maybe emit_x509_Extension("");
    $output .= maybe emit_x509_Extension("");
    $output .= maybe emit_x509_Extension("");

    return emit_asn1_cons($CONT, 3, emit_asn1_cons($UNIV, $SEQUENCE, $output));
}

###############################################################################
#
# Generate an X.509 certificate
#
###############################################################################
sub emit_x509_Time()
{
    # UTCTime or GeneralizedTime
    if (int(rand(2)) == 0) {
	return emit_asn1_utctime($UNIV, $UTCTime);
    } else {
	return emit_asn1_gentime($UNIV, $GeneralizedTime);
    }
}

sub emit_x509_Validity()
{
    my $output;
    $output  = emit_x509_Time();			# notBefore
    $output .= emit_x509_Time();			# notAfter
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_AlgorithmIdentifier($)
{
    my ($oid) = @_;
    my $output;
 
    #$output  = emit_asn1_prim($UNIV, $OBJ_ID);		# algorithm
    $output  = emit_asn1_OID($UNIV, $OBJ_ID, $oid); # algorithm
    $output .= emit_asn1_prim($UNIV, $NULL);		# parameters
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_Version()
{
    my $output = emit_asn1_prim($UNIV, $INTEGER, 0, 3);
    return emit_asn1_cons($CONT, 0, $output);
}

sub emit_x509_SubjectPublicKeyInfo()
{
    my $output;
    $output  = emit_x509_AlgorithmIdentifier("rsaEncryption");	# algorithm
    $output .= emit_asn1_prim($UNIV, $BIT_STRING);	# subjectPublicKey
    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_TBSCertificate()
{
    my $output;

    $output  = emit_x509_Version;			# version
    $output .= emit_asn1_prim($UNIV, $INTEGER);		# serialNumber
    $output .= emit_x509_AlgorithmIdentifier("sha1WithRSAEncryption");	# signature
    $output .= emit_x509_Name();			# issuer
    $output .= emit_x509_Validity();			# validity
    $output .= emit_x509_Name();			# subject
    $output .= emit_x509_SubjectPublicKeyInfo();	# subjectPublicKeyInfo
    $output .= maybe emit_asn1_prim($CONT, 1);		# issuerUniqueID
    $output .= maybe emit_asn1_prim($CONT, 2);		# subjectUniqueID
    $output .= emit_x509_Extensions();			# extensions

    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

sub emit_x509_Certificate()
{
    my $output;

    $output  = emit_x509_TBSCertificate();		# tbsCertificate
    $output .= emit_x509_AlgorithmIdentifier("sha1WithRSAEncryption");	# signatureAlgorithm
    $output .= emit_asn1_prim($UNIV, $BIT_STRING);	# signature

    return emit_asn1_cons($UNIV, $SEQUENCE, $output);
}

print emit_x509_Certificate();
#!/bin/sh
#
# Generate an X.509 certificate and stuff that into a key, then generate a
# PKCS#7 cert from that over some random data and stuff that into a key.
#
# Format:
#
#	x509-stuffer.sh [<tmpfile-prefix>]
#
file=/tmp/x509cert
if [ "$1" != "" ]
then
    file=$1
fi

cd /tmp
sync

while true
do
    openssl req -new -x509 -outform PEM -keyout $file.pem -nodes -subj "/CN=GB/O=Red Hat/OU=Magrathea/CN=Slartibartfast" -out $file.x509 || exit $?

    openssl x509 -in $file.x509 -inform PEM -outform DER >$file.x509.asn1 || exit $?
    keyctl padd asymmetric bar @s <$file.x509.asn1 || exit $?

    n=$RANDOM
    if [ $n -lt 10 ]; then n=10; fi
    dd if=/dev/urandom of=$file.stuff bs=$n count=1

    openssl smime -sign -inkey $file.pem -signer $file.x509 -keyform PEM \
	-in $file.stuff -out $file.pkcs7 -binary -outform DER || exit $?

    keyctl padd asymmetric baz @s <$file.pkcs7
done

Patch
diff mbox series

diff --git a/include/linux/asn1_decoder.h b/include/linux/asn1_decoder.h
new file mode 100644
index 0000000..fa2ff5b
--- /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 b042896..ca856b6 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 0000000..8179f3c
--- /dev/null
+++ b/lib/asn1_decoder.c
@@ -0,0 +1,473 @@ 
+/* 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;
+	const char *errmsg;
+	size_t pc = 0, dp = 0, tdp = 0, len = 0, hdr = 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];
+#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 = dp;
+
+		/* 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;
+				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;
+			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, dp - 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, dp - 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];
+		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, dp - hdr, 0, data + tdp, len);
+		}
+		pc += asn1_op_lengths[op];
+		goto next_op;
+
+	case ASN1_OP_ACT:
+		ret = actions[machine[pc + 1]](context, dp - 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);