r20640: Commit part 2/2

Update Heimdal to match current lorikeet-heimdal.  This includes
integrated PAC hooks, so Samba doesn't have to handle this any more.

This also brings in the PKINIT code, hence so many new files.

Andrew Bartlett
(This used to be commit 351f7040f7bb73b9a60b22b564686f7c2f98a729)

1 files changed, 2214 insertions, 0 deletions

diff --git a/source4/heimdal/lib/hx509/cert.c b/source4/heimdal/lib/hx509/cert.c
new file mode 100644
index 0000000000..f84c61a798
--- /dev/null
+++ b/source4/heimdal/lib/hx509/cert.c
@@ -0,0 +1,2214 @@
+/*
+ * Copyright (c) 2004 - 2007 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden). 
+ * All rights reserved. 
+ *
+ * Redistribution and use in source and binary forms, with or without 
+ * modification, are permitted provided that the following conditions 
+ * are met: 
+ *
+ * 1. Redistributions of source code must retain the above copyright 
+ *    notice, this list of conditions and the following disclaimer. 
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright 
+ *    notice, this list of conditions and the following disclaimer in the 
+ *    documentation and/or other materials provided with the distribution. 
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors 
+ *    may be used to endorse or promote products derived from this software 
+ *    without specific prior written permission. 
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 
+ * SUCH DAMAGE. 
+ */
+
+#include "hx_locl.h"
+RCSID("$Id: cert.c,v 1.82 2007/01/09 10:52:03 lha Exp $");
+#include "crypto-headers.h"
+
+struct hx509_verify_ctx_data {
+    hx509_certs trust_anchors;
+    int flags;
+#define HX509_VERIFY_CTX_F_TIME_SET			1
+#define HX509_VERIFY_CTX_F_ALLOW_PROXY_CERTIFICATE	2
+#define HX509_VERIFY_CTX_F_REQUIRE_RFC3280		4
+#define HX509_VERIFY_CTX_F_CHECK_TRUST_ANCHORS		8
+    time_t time_now;
+    unsigned int max_depth;
+#define HX509_VERIFY_MAX_DEPTH 30
+    hx509_revoke_ctx revoke_ctx;
+};
+
+#define REQUIRE_RFC3280(ctx) ((ctx)->flags & HX509_VERIFY_CTX_F_REQUIRE_RFC3280)
+#define CHECK_TA(ctx) ((ctx)->flags & HX509_VERIFY_CTX_F_CHECK_TRUST_ANCHORS)
+
+struct _hx509_cert_attrs {
+    size_t len;
+    hx509_cert_attribute *val;
+};
+
+struct hx509_cert_data {
+    unsigned int ref;
+    char *friendlyname;
+    Certificate *data;
+    hx509_private_key private_key;
+    struct _hx509_cert_attrs attrs;
+    hx509_name basename;
+    _hx509_cert_release_func release;
+    void *ctx;
+};
+
+typedef struct hx509_name_constraints {
+    NameConstraints *val;
+    size_t len;
+} hx509_name_constraints;
+
+#define GeneralSubtrees_SET(g,var) \
+	(g)->len = (var)->len, (g)->val = (var)->val;
+
+/*
+ *
+ */
+
+void
+_hx509_abort(const char *fmt, ...)
+{
+    va_list ap;
+    va_start(ap, fmt);
+    vprintf(fmt, ap);
+    va_end(ap);
+    printf("\n");
+    fflush(stdout);
+    abort();
+}
+
+/*
+ *
+ */
+
+int
+hx509_context_init(hx509_context *context)
+{
+    *context = calloc(1, sizeof(**context));
+    if (*context == NULL)
+	return ENOMEM;
+
+    _hx509_ks_mem_register(*context);
+    _hx509_ks_file_register(*context);
+    _hx509_ks_pkcs12_register(*context);
+    _hx509_ks_pkcs11_register(*context);
+    _hx509_ks_dir_register(*context);
+
+    ENGINE_add_conf_module();
+    OpenSSL_add_all_algorithms();
+
+    (*context)->ocsp_time_diff = HX509_DEFAULT_OCSP_TIME_DIFF;
+
+    initialize_hx_error_table_r(&(*context)->et_list);
+    initialize_asn1_error_table_r(&(*context)->et_list);
+
+    return 0;
+}
+
+void
+hx509_context_set_missing_revoke(hx509_context context, int flag)
+{
+    if (flag)
+	context->flags |= HX509_CTX_VERIFY_MISSING_OK;
+    else
+	context->flags &= ~HX509_CTX_VERIFY_MISSING_OK;
+}
+
+void
+hx509_context_free(hx509_context *context)
+{
+    hx509_clear_error_string(*context);
+    if ((*context)->ks_ops) {
+	free((*context)->ks_ops);
+	(*context)->ks_ops = NULL;
+    }
+    (*context)->ks_num_ops = 0;
+    free_error_table ((*context)->et_list);
+    free(*context);
+    *context = NULL;
+}
+
+
+/*
+ *
+ */
+
+Certificate *
+_hx509_get_cert(hx509_cert cert)
+{
+    return cert->data;
+}
+
+/*
+ *
+ */
+
+#if 0
+void
+_hx509_print_cert_subject(hx509_cert cert)
+{
+    char *subject_name;
+    hx509_name name;
+    int ret;
+
+    ret = hx509_cert_get_subject(cert, &name);
+    if (ret)
+	abort();
+	
+    ret = hx509_name_to_string(name, &subject_name);
+    hx509_name_free(&name);
+    if (ret)
+	abort();
+
+    printf("name: %s\n", subject_name);
+
+    free(subject_name);
+}
+#endif
+
+/*
+ *
+ */
+
+int
+_hx509_cert_get_version(const Certificate *t)
+{
+    return t->tbsCertificate.version ? *t->tbsCertificate.version + 1 : 1;
+}
+
+int
+hx509_cert_init(hx509_context context, const Certificate *c, hx509_cert *cert)
+{
+    int ret;
+
+    *cert = malloc(sizeof(**cert));
+    if (*cert == NULL)
+	return ENOMEM;
+    (*cert)->ref = 1;
+    (*cert)->friendlyname = NULL;
+    (*cert)->attrs.len = 0;
+    (*cert)->attrs.val = NULL;
+    (*cert)->private_key = NULL;
+    (*cert)->basename = NULL;
+    (*cert)->release = NULL;
+    (*cert)->ctx = NULL;
+
+    (*cert)->data = calloc(1, sizeof(*(*cert)->data));
+    if ((*cert)->data == NULL) {
+	free(*cert);
+	return ENOMEM;
+    }
+    ret = copy_Certificate(c, (*cert)->data);
+    if (ret) {
+	free((*cert)->data);
+	free(*cert);
+    }
+    return ret;
+}
+
+void
+_hx509_cert_set_release(hx509_cert cert, 
+			_hx509_cert_release_func release,
+			void *ctx)
+{
+    cert->release = release;
+    cert->ctx = ctx;
+}
+
+
+/* Doesn't make a copy of `private_key'. */
+
+int
+_hx509_cert_assign_key(hx509_cert cert, hx509_private_key private_key)
+{
+    if (cert->private_key)
+	_hx509_private_key_free(&cert->private_key);
+    cert->private_key = _hx509_private_key_ref(private_key);
+    return 0;
+}
+
+void
+hx509_cert_free(hx509_cert cert)
+{
+    int i;
+
+    if (cert == NULL)
+	return;
+
+    if (cert->ref <= 0)
+	_hx509_abort("refcount <= 0");
+    if (--cert->ref > 0)
+	return;
+
+    if (cert->release)
+	(cert->release)(cert, cert->ctx);
+
+    if (cert->private_key)
+	_hx509_private_key_free(&cert->private_key);
+
+    free_Certificate(cert->data);
+    free(cert->data);
+
+    for (i = 0; i < cert->attrs.len; i++) {
+	der_free_octet_string(&cert->attrs.val[i]->data);
+	der_free_oid(&cert->attrs.val[i]->oid);
+	free(cert->attrs.val[i]);
+    }
+    free(cert->attrs.val);
+    free(cert->friendlyname);
+    if (cert->basename)
+	hx509_name_free(&cert->basename);
+    memset(cert, 0, sizeof(cert));
+    free(cert);
+}
+
+hx509_cert
+hx509_cert_ref(hx509_cert cert)
+{
+    if (cert->ref <= 0)
+	_hx509_abort("refcount <= 0");
+    cert->ref++;
+    if (cert->ref == 0)
+	_hx509_abort("refcount == 0");
+    return cert;
+}
+
+int
+hx509_verify_init_ctx(hx509_context context, hx509_verify_ctx *ctx)
+{
+    hx509_verify_ctx c;
+
+    c = calloc(1, sizeof(*c));
+    if (c == NULL)
+	return ENOMEM;
+
+    c->max_depth = HX509_VERIFY_MAX_DEPTH;
+
+    *ctx = c;
+    
+    return 0;
+}
+
+void
+hx509_verify_destroy_ctx(hx509_verify_ctx ctx)
+{
+    if (ctx)
+	memset(ctx, 0, sizeof(*ctx));
+    free(ctx);
+}
+
+void
+hx509_verify_attach_anchors(hx509_verify_ctx ctx, hx509_certs set)
+{
+    ctx->trust_anchors = set;
+}
+
+void
+hx509_verify_attach_revoke(hx509_verify_ctx ctx, hx509_revoke_ctx revoke_ctx)
+{
+    ctx->revoke_ctx = revoke_ctx;
+}
+
+void
+hx509_verify_set_time(hx509_verify_ctx ctx, time_t t)
+{
+    ctx->flags |= HX509_VERIFY_CTX_F_TIME_SET;
+    ctx->time_now = t;
+}
+
+void
+hx509_verify_set_proxy_certificate(hx509_verify_ctx ctx, int boolean)
+{
+    if (boolean)
+	ctx->flags |= HX509_VERIFY_CTX_F_ALLOW_PROXY_CERTIFICATE;
+    else
+	ctx->flags &= ~HX509_VERIFY_CTX_F_ALLOW_PROXY_CERTIFICATE;
+}
+
+void
+hx509_verify_set_strict_rfc3280_verification(hx509_verify_ctx ctx, int boolean)
+{
+    if (boolean)
+	ctx->flags |= HX509_VERIFY_CTX_F_REQUIRE_RFC3280;
+    else
+	ctx->flags &= ~HX509_VERIFY_CTX_F_REQUIRE_RFC3280;
+}
+
+static const Extension *
+find_extension(const Certificate *cert, const heim_oid *oid, int *idx)
+{
+    const TBSCertificate *c = &cert->tbsCertificate;
+
+    if (c->version == NULL || *c->version < 2 || c->extensions == NULL)
+	return NULL;
+    
+    for (;*idx < c->extensions->len; (*idx)++) {
+	if (der_heim_oid_cmp(&c->extensions->val[*idx].extnID, oid) == 0)
+	    return &c->extensions->val[(*idx)++];
+    }
+    return NULL;
+}
+
+static int
+find_extension_auth_key_id(const Certificate *subject, 
+			   AuthorityKeyIdentifier *ai)
+{
+    const Extension *e;
+    size_t size;
+    int i = 0;
+
+    memset(ai, 0, sizeof(*ai));
+
+    e = find_extension(subject, oid_id_x509_ce_authorityKeyIdentifier(), &i);
+    if (e == NULL)
+	return HX509_EXTENSION_NOT_FOUND;
+    
+    return decode_AuthorityKeyIdentifier(e->extnValue.data, 
+					 e->extnValue.length, 
+					 ai, &size);
+}
+
+int
+_hx509_find_extension_subject_key_id(const Certificate *issuer,
+				     SubjectKeyIdentifier *si)
+{
+    const Extension *e;
+    size_t size;
+    int i = 0;
+
+    memset(si, 0, sizeof(*si));
+
+    e = find_extension(issuer, oid_id_x509_ce_subjectKeyIdentifier(), &i);
+    if (e == NULL)
+	return HX509_EXTENSION_NOT_FOUND;
+    
+    return decode_SubjectKeyIdentifier(e->extnValue.data, 
+				       e->extnValue.length,
+				       si, &size);
+}
+
+static int
+find_extension_name_constraints(const Certificate *subject, 
+				NameConstraints *nc)
+{
+    const Extension *e;
+    size_t size;
+    int i = 0;
+
+    memset(nc, 0, sizeof(*nc));
+
+    e = find_extension(subject, oid_id_x509_ce_nameConstraints(), &i);
+    if (e == NULL)
+	return HX509_EXTENSION_NOT_FOUND;
+    
+    return decode_NameConstraints(e->extnValue.data, 
+				  e->extnValue.length, 
+				  nc, &size);
+}
+
+static int
+find_extension_subject_alt_name(const Certificate *cert, int *i,
+				GeneralNames *sa)
+{
+    const Extension *e;
+    size_t size;
+
+    memset(sa, 0, sizeof(*sa));
+
+    e = find_extension(cert, oid_id_x509_ce_subjectAltName(), i);
+    if (e == NULL)
+	return HX509_EXTENSION_NOT_FOUND;
+    
+    return decode_GeneralNames(e->extnValue.data, 
+			       e->extnValue.length,
+			       sa, &size);
+}
+
+static int
+find_extension_eku(const Certificate *cert, ExtKeyUsage *eku)
+{
+    const Extension *e;
+    size_t size;
+    int i = 0;
+
+    memset(eku, 0, sizeof(*eku));
+
+    e = find_extension(cert, oid_id_x509_ce_extKeyUsage(), &i);
+    if (e == NULL)
+	return HX509_EXTENSION_NOT_FOUND;
+    
+    return decode_ExtKeyUsage(e->extnValue.data, 
+			      e->extnValue.length,
+			      eku, &size);
+}
+
+static int
+add_to_list(hx509_octet_string_list *list, const heim_octet_string *entry)
+{
+    void *p;
+    int ret;
+
+    p = realloc(list->val, (list->len + 1) * sizeof(list->val[0]));
+    if (p == NULL)
+	return ENOMEM;
+    list->val = p;
+    ret = der_copy_octet_string(entry, &list->val[list->len]);
+    if (ret)
+	return ret;
+    list->len++;
+    return 0;
+}
+
+void
+hx509_free_octet_string_list(hx509_octet_string_list *list)
+{
+    int i;
+    for (i = 0; i < list->len; i++)
+	der_free_octet_string(&list->val[i]);
+    free(list->val);
+    list->val = NULL;
+    list->len = 0;
+}
+
+int
+hx509_cert_find_subjectAltName_otherName(hx509_cert cert,
+					 const heim_oid *oid,
+					 hx509_octet_string_list *list)
+{
+    GeneralNames sa;
+    int ret, i, j;
+
+    list->val = NULL;
+    list->len = 0;
+
+    i = 0;
+    while (1) {
+	ret = find_extension_subject_alt_name(_hx509_get_cert(cert), &i, &sa);
+	i++;
+	if (ret == HX509_EXTENSION_NOT_FOUND) {
+	    ret = 0;
+	    break;
+	} else if (ret != 0)
+	    break;
+
+
+	for (j = 0; j < sa.len; j++) {
+	    if (sa.val[j].element == choice_GeneralName_otherName &&
+		der_heim_oid_cmp(&sa.val[j].u.otherName.type_id, oid) == 0) 
+	    {
+		ret = add_to_list(list, &sa.val[j].u.otherName.value);
+		if (ret) {
+		    free_GeneralNames(&sa);
+		    return ret;
+		}
+	    }
+	}
+	free_GeneralNames(&sa);
+    }
+    return ret;
+}
+
+
+static int
+check_key_usage(hx509_context context, const Certificate *cert, 
+		unsigned flags, int req_present)
+{
+    const Extension *e;
+    KeyUsage ku;
+    size_t size;
+    int ret, i = 0;
+    unsigned ku_flags;
+
+    if (_hx509_cert_get_version(cert) < 3)
+	return 0;
+
+    e = find_extension(cert, oid_id_x509_ce_keyUsage(), &i);
+    if (e == NULL) {
+	if (req_present) {
+	    hx509_set_error_string(context, 0, HX509_KU_CERT_MISSING,
+				   "Required extension key "
+				   "usage missing from certifiate");
+	    return HX509_KU_CERT_MISSING;
+	}
+	return 0;
+    }
+    
+    ret = decode_KeyUsage(e->extnValue.data, e->extnValue.length, &ku, &size);
+    if (ret)
+	return ret;
+    ku_flags = KeyUsage2int(ku);
+    if ((ku_flags & flags) != flags) {
+	unsigned missing = (~ku_flags) & flags;
+	char buf[256], *name;
+
+	unparse_flags(missing, asn1_KeyUsage_units(), buf, sizeof(buf));
+	_hx509_unparse_Name(&cert->tbsCertificate.subject, &name);
+	hx509_set_error_string(context, 0, HX509_KU_CERT_MISSING,
+			       "Key usage %s required but missing "
+			       "from certifiate %s", buf, name);
+	free(name);
+	return HX509_KU_CERT_MISSING;
+    }
+    return 0;
+}
+
+int
+_hx509_check_key_usage(hx509_context context, hx509_cert cert, 
+		       unsigned flags, int req_present)
+{
+    return check_key_usage(context, _hx509_get_cert(cert), flags, req_present);
+}
+
+enum certtype { PROXY_CERT, EE_CERT, CA_CERT };
+
+static int
+check_basic_constraints(hx509_context context, const Certificate *cert, 
+			enum certtype type, int depth)
+{
+    BasicConstraints bc;
+    const Extension *e;
+    size_t size;
+    int ret, i = 0;
+
+    if (_hx509_cert_get_version(cert) < 3)
+	return 0;
+
+    e = find_extension(cert, oid_id_x509_ce_basicConstraints(), &i);
+    if (e == NULL) {
+	switch(type) {
+	case PROXY_CERT:
+	case EE_CERT:
+	    return 0;
+	case CA_CERT: {
+	    char *name;
+	    ret = _hx509_unparse_Name(&cert->tbsCertificate.subject, &name);
+	    assert(ret == 0);
+	    hx509_set_error_string(context, 0, HX509_EXTENSION_NOT_FOUND,
+				   "basicConstraints missing from "
+				   "CA certifiacte %s", name);
+	    free(name);
+	    return HX509_EXTENSION_NOT_FOUND;
+	}
+	}
+    }
+    
+    ret = decode_BasicConstraints(e->extnValue.data, 
+				  e->extnValue.length, &bc,
+				  &size);
+    if (ret)
+	return ret;
+    switch(type) {
+    case PROXY_CERT:
+	if (bc.cA != NULL && *bc.cA)
+	    ret = HX509_PARENT_IS_CA;
+	break;
+    case EE_CERT:
+	ret = 0;
+	break;
+    case CA_CERT:
+	if (bc.cA == NULL || !*bc.cA)
+	    ret = HX509_PARENT_NOT_CA;
+	else if (bc.pathLenConstraint)
+	    if (depth - 1 > *bc.pathLenConstraint)
+		ret = HX509_CA_PATH_TOO_DEEP;
+	break;
+    }
+    free_BasicConstraints(&bc);
+    return ret;
+}
+
+int
+_hx509_cert_is_parent_cmp(const Certificate *subject,
+			  const Certificate *issuer,
+			  int allow_self_signed)
+{
+    int diff;
+    AuthorityKeyIdentifier ai;
+    SubjectKeyIdentifier si;
+    int ret_ai, ret_si;
+
+    diff = _hx509_name_cmp(&issuer->tbsCertificate.subject, 
+			   &subject->tbsCertificate.issuer);
+    if (diff)
+	return diff;
+    
+    memset(&ai, 0, sizeof(ai));
+    memset(&si, 0, sizeof(si));
+
+    /*
+     * Try to find AuthorityKeyIdentifier, if its not present in the
+     * subject certificate nor the parent.
+     */
+
+    ret_ai = find_extension_auth_key_id(subject, &ai);
+    if (ret_ai && ret_ai != HX509_EXTENSION_NOT_FOUND)
+	return 1;
+    ret_si = _hx509_find_extension_subject_key_id(issuer, &si);
+    if (ret_si && ret_si != HX509_EXTENSION_NOT_FOUND)
+	return -1;
+
+    if (ret_si && ret_ai)
+	goto out;
+    if (ret_ai)
+	goto out;
+    if (ret_si) {
+	if (allow_self_signed) {
+	    diff = 0;
+	    goto out;
+	} else if (ai.keyIdentifier) {
+	    diff = -1;
+	    goto out;
+	}
+    }
+    
+    if (ai.keyIdentifier == NULL) {
+	Name name;
+
+	if (ai.authorityCertIssuer == NULL)
+	    return -1;
+	if (ai.authorityCertSerialNumber == NULL)
+	    return -1;
+
+	diff = der_heim_integer_cmp(ai.authorityCertSerialNumber, 
+				    &issuer->tbsCertificate.serialNumber);
+	if (diff)
+	    return diff;
+	if (ai.authorityCertIssuer->len != 1)
+	    return -1;
+	if (ai.authorityCertIssuer->val[0].element != choice_GeneralName_directoryName)
+	    return -1;
+	
+	name.element = 
+	    ai.authorityCertIssuer->val[0].u.directoryName.element;
+	name.u.rdnSequence = 
+	    ai.authorityCertIssuer->val[0].u.directoryName.u.rdnSequence;
+
+	diff = _hx509_name_cmp(&issuer->tbsCertificate.subject, 
+			       &name);
+	if (diff)
+	    return diff;
+	diff = 0;
+    } else
+	diff = der_heim_octet_string_cmp(ai.keyIdentifier, &si);
+    if (diff)
+	goto out;
+
+ out:
+    free_AuthorityKeyIdentifier(&ai);
+    free_SubjectKeyIdentifier(&si);
+    return diff;
+}
+
+static int
+certificate_is_anchor(hx509_context context,
+		      hx509_certs trust_anchors,
+		      const hx509_cert cert)
+{
+    hx509_query q;
+    hx509_cert c;
+    int ret;
+
+    if (trust_anchors == NULL)
+	return 0;
+
+    _hx509_query_clear(&q);
+
+    q.match = HX509_QUERY_MATCH_CERTIFICATE;
+    q.certificate = _hx509_get_cert(cert);
+
+    ret = hx509_certs_find(context, trust_anchors, &q, &c);
+    if (ret == 0)
+	hx509_cert_free(c);
+    return ret == 0;
+}
+
+static int
+certificate_is_self_signed(const Certificate *cert)
+{
+    return _hx509_cert_is_parent_cmp(cert, cert, 1) == 0;
+}
+
+/*
+ * The subjectName is "null" when its empty set of relative DBs.
+ */
+
+static int
+subject_null_p(const Certificate *c)
+{
+    return c->tbsCertificate.subject.u.rdnSequence.len == 0;
+}
+
+
+static int
+find_parent(hx509_context context,
+	    time_t time_now,
+	    hx509_certs trust_anchors,
+	    hx509_path *path,
+	    hx509_certs pool, 
+	    hx509_cert current,
+	    hx509_cert *parent)
+{
+    AuthorityKeyIdentifier ai;
+    hx509_query q;
+    int ret;
+
+    *parent = NULL;
+    memset(&ai, 0, sizeof(ai));
+    
+    _hx509_query_clear(&q);
+
+    if (!subject_null_p(current->data)) {
+	q.match |= HX509_QUERY_FIND_ISSUER_CERT;
+	q.subject = _hx509_get_cert(current);
+    } else {
+	ret = find_extension_auth_key_id(current->data, &ai);
+	if (ret) {
+	    hx509_set_error_string(context, 0, HX509_CERTIFICATE_MALFORMED,
+				   "Subjectless certificate missing AuthKeyID");
+	    return HX509_CERTIFICATE_MALFORMED;
+	}
+
+	if (ai.keyIdentifier == NULL) {
+	    free_AuthorityKeyIdentifier(&ai);
+	    hx509_set_error_string(context, 0, HX509_CERTIFICATE_MALFORMED,
+				   "Subjectless certificate missing keyIdentifier "
+				   "inside AuthKeyID");
+	    return HX509_CERTIFICATE_MALFORMED;
+	}
+
+	q.subject_id = ai.keyIdentifier;
+	q.match = HX509_QUERY_MATCH_SUBJECT_KEY_ID;
+    }
+
+    q.path = path;
+    q.match |= HX509_QUERY_NO_MATCH_PATH;
+
+    if (pool) {
+	q.timenow = time_now;
+	q.match |= HX509_QUERY_MATCH_TIME;
+
+	ret = hx509_certs_find(context, pool, &q, parent);
+	if (ret == 0) {
+	    free_AuthorityKeyIdentifier(&ai);
+	    return 0;
+	}
+	q.match &= ~HX509_QUERY_MATCH_TIME;
+    }
+
+    if (trust_anchors) {
+	ret = hx509_certs_find(context, trust_anchors, &q, parent);
+	if (ret == 0) {
+	    free_AuthorityKeyIdentifier(&ai);
+	    return ret;
+	}
+    }
+    free_AuthorityKeyIdentifier(&ai);
+
+    {
+	hx509_name name;
+	char *str;
+
+	ret = hx509_cert_get_subject(current, &name);
+	if (ret) {
+	    hx509_clear_error_string(context);
+	    return HX509_ISSUER_NOT_FOUND;
+	}
+	ret = hx509_name_to_string(name, &str);
+	hx509_name_free(&name);
+	if (ret) {
+	    hx509_clear_error_string(context);
+	    return HX509_ISSUER_NOT_FOUND;
+	}
+	
+	hx509_set_error_string(context, 0, HX509_ISSUER_NOT_FOUND,
+			       "Failed to find issuer for "
+			       "certificate with subject: %s", str);
+	free(str);
+    }
+    return HX509_ISSUER_NOT_FOUND;
+}
+
+/*
+ *
+ */
+
+static int
+is_proxy_cert(hx509_context context, const Certificate *cert, ProxyCertInfo *rinfo)
+{
+    ProxyCertInfo info;
+    const Extension *e;
+    size_t size;
+    int ret, i = 0;
+
+    if (rinfo)
+	memset(rinfo, 0, sizeof(*rinfo));
+
+    e = find_extension(cert, oid_id_pe_proxyCertInfo(), &i);
+    if (e == NULL) {
+	hx509_clear_error_string(context);
+	return HX509_EXTENSION_NOT_FOUND;
+    }
+
+    ret = decode_ProxyCertInfo(e->extnValue.data, 
+			       e->extnValue.length, 
+			       &info,
+			       &size);
+    if (ret) {
+	hx509_clear_error_string(context);
+	return ret;
+    }
+    if (size != e->extnValue.length) {
+	free_ProxyCertInfo(&info);
+	hx509_clear_error_string(context);
+	return HX509_EXTRA_DATA_AFTER_STRUCTURE; 
+    }
+    if (rinfo)
+	*rinfo = info;
+
+    return 0;
+}
+
+/*
+ * Path operations are like MEMORY based keyset, but with exposed
+ * internal so we can do easy searches.
+ */
+
+int
+_hx509_path_append(hx509_context context, hx509_path *path, hx509_cert cert)
+{
+    hx509_cert *val;
+    val = realloc(path->val, (path->len + 1) * sizeof(path->val[0]));
+    if (val == NULL) {
+	hx509_set_error_string(context, 0, ENOMEM, "out of memory");
+	return ENOMEM;
+    }
+
+    path->val = val;
+    path->val[path->len] = hx509_cert_ref(cert);
+    path->len++;
+
+    return 0;
+}
+
+void
+_hx509_path_free(hx509_path *path)
+{
+    unsigned i;
+    
+    for (i = 0; i < path->len; i++)
+	hx509_cert_free(path->val[i]);
+    free(path->val);
+    path->val = NULL;
+    path->len = 0;
+}
+
+/*
+ * Find path by looking up issuer for the top certificate and continue
+ * until an anchor certificate is found or max limit is found. A
+ * certificate never included twice in the path.
+ *
+ * If the trust anchors are not given, calculate optimistic path, just
+ * follow the chain upward until we no longer find a parent or we hit
+ * the max path limit. In this case, a failure will always be returned
+ * depending on what error condition is hit first.
+ *
+ * The path includes a path from the top certificate to the anchor
+ * certificate.
+ *
+ * The caller needs to free `path´ both on successful built path and
+ * failure.
+ */
+
+int
+_hx509_calculate_path(hx509_context context,
+		      int flags,
+		      time_t time_now,
+		      hx509_certs anchors,
+		      unsigned int max_depth,
+		      hx509_cert cert,
+		      hx509_certs pool,
+		      hx509_path *path)
+{
+    hx509_cert parent, current;
+    int ret;
+
+    if (max_depth == 0)
+	max_depth = HX509_VERIFY_MAX_DEPTH;
+
+    ret = _hx509_path_append(context, path, cert);
+    if (ret)
+	return ret;
+
+    current = hx509_cert_ref(cert);
+
+    while (!certificate_is_anchor(context, anchors, current)) {
+
+	ret = find_parent(context, time_now, anchors, path, 
+			  pool, current, &parent);
+	hx509_cert_free(current);
+	if (ret)
+	    return ret;
+
+	ret = _hx509_path_append(context, path, parent);
+	if (ret)
+	    return ret;
+	current = parent;
+
+	if (path->len > max_depth) {
+	    hx509_set_error_string(context, 0, HX509_PATH_TOO_LONG,
+				   "Path too long while bulding certificate chain");
+	    return HX509_PATH_TOO_LONG;
+	}
+    }
+
+    if ((flags & HX509_CALCULATE_PATH_NO_ANCHOR) && 
+	path->len > 0 && 
+	certificate_is_anchor(context, anchors, path->val[path->len - 1]))
+    {
+	hx509_cert_free(path->val[path->len - 1]);
+	path->len--;
+    }
+
+    hx509_cert_free(current);
+    return 0;
+}
+
+static int
+AlgorithmIdentifier_cmp(const AlgorithmIdentifier *p,
+			const AlgorithmIdentifier *q)
+{
+    int diff;
+    diff = der_heim_oid_cmp(&p->algorithm, &q->algorithm);
+    if (diff)
+	return diff;
+    if (p->parameters) {
+	if (q->parameters)
+	    return heim_any_cmp(p->parameters,
+				q->parameters);
+	else
+	    return 1;
+    } else {
+	if (q->parameters)
+	    return -1;
+	else
+	    return 0;
+    }
+}
+
+int
+_hx509_Certificate_cmp(const Certificate *p, const Certificate *q)
+{
+    int diff;
+    diff = der_heim_bit_string_cmp(&p->signatureValue, &q->signatureValue);
+    if (diff)
+	return diff;
+    diff = AlgorithmIdentifier_cmp(&p->signatureAlgorithm, 
+				   &q->signatureAlgorithm);
+    if (diff)
+	return diff;
+    diff = der_heim_octet_string_cmp(&p->tbsCertificate._save,
+				     &q->tbsCertificate._save);
+    return diff;
+}
+
+int
+hx509_cert_cmp(hx509_cert p, hx509_cert q)
+{
+    return _hx509_Certificate_cmp(p->data, q->data);
+}
+
+int
+hx509_cert_get_issuer(hx509_cert p, hx509_name *name)
+{
+    return _hx509_name_from_Name(&p->data->tbsCertificate.issuer, name);
+}
+
+int
+hx509_cert_get_subject(hx509_cert p, hx509_name *name)
+{
+    return _hx509_name_from_Name(&p->data->tbsCertificate.subject, name);
+}
+
+int
+hx509_cert_get_base_subject(hx509_context context, hx509_cert c,
+			    hx509_name *name)
+{
+    if (c->basename)
+	return hx509_name_copy(context, c->basename, name);
+    if (is_proxy_cert(context, c->data, NULL) == 0) {
+	int ret = HX509_PROXY_CERTIFICATE_NOT_CANONICALIZED;
+	hx509_set_error_string(context, 0, ret,
+			       "Proxy certificate have not been "
+			       "canonicalize yet, no base name");
+	return ret;
+    }
+    return _hx509_name_from_Name(&c->data->tbsCertificate.subject, name);
+}
+
+int
+hx509_cert_get_serialnumber(hx509_cert p, heim_integer *i)
+{
+    return der_copy_heim_integer(&p->data->tbsCertificate.serialNumber, i);
+}
+
+hx509_private_key
+_hx509_cert_private_key(hx509_cert p)
+{
+    return p->private_key;
+}
+
+int
+_hx509_cert_private_key_exportable(hx509_cert p)
+{
+    if (p->private_key == NULL)
+	return 0;
+    return _hx509_private_key_exportable(p->private_key);
+}
+
+int
+_hx509_cert_private_decrypt(hx509_context context,
+			    const heim_octet_string *ciphertext,
+			    const heim_oid *encryption_oid,
+			    hx509_cert p,
+			    heim_octet_string *cleartext)
+{
+    cleartext->data = NULL;
+    cleartext->length = 0;
+
+    if (p->private_key == NULL) {
+	hx509_set_error_string(context, 0, HX509_PRIVATE_KEY_MISSING,
+			       "Private key missing");
+	return HX509_PRIVATE_KEY_MISSING;
+    }
+
+    return _hx509_private_key_private_decrypt(context,
+					      ciphertext,
+					      encryption_oid,
+					      p->private_key, 
+					      cleartext);
+}
+
+int
+_hx509_cert_public_encrypt(hx509_context context,
+			   const heim_octet_string *cleartext,
+			   const hx509_cert p,
+			   heim_oid *encryption_oid,
+			   heim_octet_string *ciphertext)
+{
+    return _hx509_public_encrypt(context,
+				 cleartext, p->data,
+				 encryption_oid, ciphertext);
+}
+
+/*
+ *
+ */
+
+time_t
+_hx509_Time2time_t(const Time *t)
+{
+    switch(t->element) {
+    case choice_Time_utcTime:
+	return t->u.utcTime;
+    case choice_Time_generalTime:
+	return t->u.generalTime;
+    }
+    return 0;
+}
+
+/*
+ *
+ */
+
+static int
+init_name_constraints(hx509_name_constraints *nc)
+{
+    memset(nc, 0, sizeof(*nc));
+    return 0;
+}
+
+static int
+add_name_constraints(hx509_context context, const Certificate *c, int not_ca,
+		     hx509_name_constraints *nc)
+{
+    NameConstraints tnc;
+    int ret;
+
+    ret = find_extension_name_constraints(c, &tnc);
+    if (ret == HX509_EXTENSION_NOT_FOUND)
+	return 0;
+    else if (ret) {
+	hx509_set_error_string(context, 0, ret, "Failed getting NameConstraints");
+	return ret;
+    } else if (not_ca) {
+	ret = HX509_VERIFY_CONSTRAINTS;
+	hx509_set_error_string(context, 0, ret, "Not a CA and "
+			       "have NameConstraints");
+    } else {
+	NameConstraints *val;
+	val = realloc(nc->val, sizeof(nc->val[0]) * (nc->len + 1));
+	if (val == NULL) {
+	    hx509_clear_error_string(context);
+	    ret = ENOMEM;
+	    goto out;
+	}
+	nc->val = val;
+	ret = copy_NameConstraints(&tnc, &nc->val[nc->len]);
+	if (ret) {
+	    hx509_clear_error_string(context);
+	    goto out;
+	}
+	nc->len += 1;
+    }
+out:
+    free_NameConstraints(&tnc);
+    return ret;
+}
+
+static int
+match_RDN(const RelativeDistinguishedName *c,
+	  const RelativeDistinguishedName *n)
+{
+    int i;
+
+    if (c->len != n->len)
+	return HX509_NAME_CONSTRAINT_ERROR;
+    
+    for (i = 0; i < n->len; i++) {
+	if (der_heim_oid_cmp(&c->val[i].type, &n->val[i].type) != 0)
+	    return HX509_NAME_CONSTRAINT_ERROR;
+	if (_hx509_name_ds_cmp(&c->val[i].value, &n->val[i].value) != 0)
+	    return HX509_NAME_CONSTRAINT_ERROR;
+    }
+    return 0;
+}
+
+static int
+match_X501Name(const Name *c, const Name *n)
+{
+    int i, ret;
+
+    if (c->element != choice_Name_rdnSequence
+	|| n->element != choice_Name_rdnSequence)
+	return 0;
+    if (c->u.rdnSequence.len > n->u.rdnSequence.len)
+	return HX509_NAME_CONSTRAINT_ERROR;
+    for (i = 0; i < c->u.rdnSequence.len; i++) {
+	ret = match_RDN(&c->u.rdnSequence.val[i], &n->u.rdnSequence.val[i]);
+	if (ret)
+	    return ret;
+    }
+    return 0;
+} 
+
+
+static int
+match_general_name(const GeneralName *c, const GeneralName *n, int *match)
+{
+    /* 
+     * Name constraints only apply to the same name type, see RFC3280,
+     * 4.2.1.11.
+     */
+    assert(c->element == n->element);
+
+    switch(c->element) {
+    case choice_GeneralName_otherName:
+	if (der_heim_oid_cmp(&c->u.otherName.type_id,
+			 &n->u.otherName.type_id) != 0)
+	    return HX509_NAME_CONSTRAINT_ERROR;
+	if (heim_any_cmp(&c->u.otherName.value,
+			 &n->u.otherName.value) != 0)
+	    return HX509_NAME_CONSTRAINT_ERROR;
+	*match = 1;
+	return 0;
+    case choice_GeneralName_rfc822Name: {
+	const char *s;
+	size_t len1, len2;
+	s = strchr(c->u.rfc822Name, '@');
+	if (s) {
+	    if (strcasecmp(c->u.rfc822Name, n->u.rfc822Name) != 0)
+		return HX509_NAME_CONSTRAINT_ERROR;
+	} else {
+	    s = strchr(n->u.rfc822Name, '@');
+	    if (s == NULL)
+		return HX509_NAME_CONSTRAINT_ERROR;
+	    len1 = strlen(c->u.rfc822Name);
+	    len2 = strlen(s + 1);
+	    if (len1 > len2)
+		return HX509_NAME_CONSTRAINT_ERROR;
+	    if (strcasecmp(s + 1 + len2 - len1, c->u.rfc822Name) != 0)
+		return HX509_NAME_CONSTRAINT_ERROR;
+	    if (len1 < len2 && s[len2 - len1] != '.')
+		return HX509_NAME_CONSTRAINT_ERROR;
+	}
+	*match = 1;
+	return 0;
+    }
+    case choice_GeneralName_dNSName: {
+	size_t len1, len2;
+
+	len1 = strlen(c->u.dNSName);
+	len2 = strlen(n->u.dNSName);
+	if (len1 > len2)
+	    return HX509_NAME_CONSTRAINT_ERROR;
+	if (strcasecmp(&n->u.dNSName[len2 - len1], c->u.dNSName) != 0)
+	    return HX509_NAME_CONSTRAINT_ERROR;
+	*match = 1;
+	return 0;
+    }
+    case choice_GeneralName_directoryName: {
+	Name c_name, n_name;
+	int ret;
+
+	c_name._save.data = NULL;
+	c_name._save.length = 0;
+	c_name.element = c->u.directoryName.element;
+	c_name.u.rdnSequence = c->u.directoryName.u.rdnSequence;
+
+	n_name._save.data = NULL;
+	n_name._save.length = 0;
+	n_name.element = n->u.directoryName.element;
+	n_name.u.rdnSequence = n->u.directoryName.u.rdnSequence;
+
+	ret = match_X501Name(&c_name, &n_name);
+	if (ret == 0)
+	    *match = 1;
+	return ret;
+    }
+    case choice_GeneralName_uniformResourceIdentifier:
+    case choice_GeneralName_iPAddress:
+    case choice_GeneralName_registeredID:
+    default:
+	return HX509_NAME_CONSTRAINT_ERROR;
+    }
+}
+
+static int
+match_alt_name(const GeneralName *n, const Certificate *c, 
+	       int *same, int *match)
+{
+    GeneralNames sa;
+    int ret, i, j;
+
+    i = 0;
+    do {
+	ret = find_extension_subject_alt_name(c, &i, &sa);
+	if (ret == HX509_EXTENSION_NOT_FOUND) {
+	    ret = 0;
+	    break;
+	} else if (ret != 0)
+	    break;
+
+	for (j = 0; j < sa.len; j++) {
+	    if (n->element == sa.val[j].element) {
+		*same = 1;
+		ret = match_general_name(n, &sa.val[j], match);
+	    }
+	}
+	free_GeneralNames(&sa);
+    } while (1);
+
+    return ret;
+}
+
+
+static int
+match_tree(const GeneralSubtrees *t, const Certificate *c, int *match)
+{
+    int name, alt_name, same;
+    unsigned int i;
+    int ret = 0;
+
+    name = alt_name = same = *match = 0;
+    for (i = 0; i < t->len; i++) {
+	if (t->val[i].minimum && t->val[i].maximum)
+	    return HX509_RANGE;
+
+	/*
+	 * If the constraint apply to directoryNames, test is with
+	 * subjectName of the certificate if the certificate have a
+	 * non-null (empty) subjectName.
+	 */
+
+	if (t->val[i].base.element == choice_GeneralName_directoryName
+	    && !subject_null_p(c))
+	{
+	    GeneralName certname;
+	    
+	    
+	    certname.element = choice_GeneralName_directoryName;
+	    certname.u.directoryName.element = 
+		c->tbsCertificate.subject.element;
+	    certname.u.directoryName.u.rdnSequence = 
+		c->tbsCertificate.subject.u.rdnSequence;
+    
+	    ret = match_general_name(&t->val[i].base, &certname, &name);
+	}
+
+	/* Handle subjectAltNames, this is icky since they
+	 * restrictions only apply if the subjectAltName is of the
+	 * same type. So if there have been a match of type, require
+	 * altname to be set.
+	 */
+	ret = match_alt_name(&t->val[i].base, c, &same, &alt_name);
+    }
+    if (name && (!same || alt_name))
+	*match = 1;
+    return ret;
+}
+
+static int
+check_name_constraints(hx509_context context, 
+		       const hx509_name_constraints *nc,
+		       const Certificate *c)
+{
+    int match, ret;
+    int i;
+
+    for (i = 0 ; i < nc->len; i++) {
+	GeneralSubtrees gs;
+
+	if (nc->val[i].permittedSubtrees) {
+	    GeneralSubtrees_SET(&gs, nc->val[i].permittedSubtrees);
+	    ret = match_tree(&gs, c, &match);
+	    if (ret) {
+		hx509_clear_error_string(context);
+		return ret;
+	    }
+	    /* allow null subjectNames, they wont matches anything */
+	    if (match == 0 && !subject_null_p(c)) {
+		hx509_clear_error_string(context);
+		return HX509_VERIFY_CONSTRAINTS;
+	    }
+	}
+	if (nc->val[i].excludedSubtrees) {
+	    GeneralSubtrees_SET(&gs, nc->val[i].excludedSubtrees);
+	    ret = match_tree(&gs, c, &match);
+	    if (ret) {
+		hx509_clear_error_string(context);
+		return ret;
+	    }
+	    if (match) {
+		hx509_clear_error_string(context);
+		return HX509_VERIFY_CONSTRAINTS;
+	    }
+	}
+    }
+    return 0;
+}
+
+static void
+free_name_constraints(hx509_name_constraints *nc)
+{
+    int i;
+
+    for (i = 0 ; i < nc->len; i++)
+	free_NameConstraints(&nc->val[i]);
+    free(nc->val);
+}
+
+int
+hx509_verify_path(hx509_context context,
+		  hx509_verify_ctx ctx,
+		  hx509_cert cert,
+		  hx509_certs pool)
+{
+    hx509_name_constraints nc;
+    hx509_path path;
+#if 0
+    const AlgorithmIdentifier *alg_id;
+#endif
+    int ret, i, proxy_cert_depth;
+    enum certtype type;
+    Name proxy_issuer;
+
+    memset(&proxy_issuer, 0, sizeof(proxy_issuer));
+
+    ret = init_name_constraints(&nc);
+    if (ret)	
+	return ret;
+
+    path.val = NULL;
+    path.len = 0;
+
+    if ((ctx->flags & HX509_VERIFY_CTX_F_TIME_SET) == 0)
+	ctx->time_now = time(NULL);
+
+    /*
+     * Calculate the path from the certificate user presented to the
+     * to an anchor.
+     */
+    ret = _hx509_calculate_path(context, 0, ctx->time_now,
+				ctx->trust_anchors, ctx->max_depth,
+				cert, pool, &path);
+    if (ret)
+	goto out;
+
+#if 0
+    alg_id = path.val[path->len - 1]->data->tbsCertificate.signature;
+#endif
+
+    /*
+     * Check CA and proxy certificate chain from the top of the
+     * certificate chain. Also check certificate is valid with respect
+     * to the current time.
+     *
+     */
+
+    proxy_cert_depth = 0;
+
+    if (ctx->flags & HX509_VERIFY_CTX_F_ALLOW_PROXY_CERTIFICATE)
+	type = PROXY_CERT;
+    else
+	type = EE_CERT;
+
+    for (i = 0; i < path.len; i++) {
+	Certificate *c;
+	time_t t;
+
+	c = _hx509_get_cert(path.val[i]);
+	
+	/*
+	 * Lets do some basic check on issuer like
+	 * keyUsage.keyCertSign and basicConstraints.cA bit depending
+	 * on what type of certificate this is.
+	 */
+
+	switch (type) {
+	case CA_CERT:
+	    /* XXX make constants for keyusage */
+	    ret = check_key_usage(context, c, 1 << 5,
+				  REQUIRE_RFC3280(ctx) ? TRUE : FALSE);
+	    if (ret) {
+		hx509_set_error_string(context, HX509_ERROR_APPEND, ret,
+				       "Key usage missing from CA certificate");
+		goto out;
+	    }
+	    break;
+	case PROXY_CERT: {
+	    ProxyCertInfo info;	    
+
+	    if (is_proxy_cert(context, c, &info) == 0) {
+		int j;
+
+		if (info.pCPathLenConstraint != NULL &&
+		    *info.pCPathLenConstraint < i)
+		{
+		    free_ProxyCertInfo(&info);
+		    ret = HX509_PATH_TOO_LONG;
+		    hx509_set_error_string(context, 0, ret,
+					   "Proxy certificate chain "
+					   "longer then allowed");
+		    goto out;
+		}
+		/* XXX MUST check info.proxyPolicy */
+		free_ProxyCertInfo(&info);
+		
+		j = 0;
+		if (find_extension(c, oid_id_x509_ce_subjectAltName(), &j)) {
+		    ret = HX509_PROXY_CERT_INVALID;
+		    hx509_set_error_string(context, 0, ret, 
+					   "Proxy certificate have explicity "
+					   "forbidden subjectAltName");
+		    goto out;
+		}
+
+		j = 0;
+		if (find_extension(c, oid_id_x509_ce_issuerAltName(), &j)) {
+		    ret = HX509_PROXY_CERT_INVALID;
+		    hx509_set_error_string(context, 0, ret, 
+					   "Proxy certificate have explicity "
+					   "forbidden issuerAltName");
+		    goto out;
+		}
+			
+		/* 
+		 * The subject name of the proxy certificate should be
+		 * CN=XXX,<proxy issuer>, prune of CN and check if its
+		 * the same over the whole chain of proxy certs and
+		 * then check with the EE cert when we get to it.
+		 */
+
+		if (proxy_cert_depth) {
+		    ret = _hx509_name_cmp(&proxy_issuer, &c->tbsCertificate.subject);
+		    if (ret) {
+			ret = HX509_PROXY_CERT_NAME_WRONG;
+			hx509_set_error_string(context, 0, ret,
+					       "Base proxy name not right");
+			goto out;
+		    }
+		}
+
+		free_Name(&proxy_issuer);
+
+		ret = copy_Name(&c->tbsCertificate.subject, &proxy_issuer);
+		if (ret) {
+		    hx509_clear_error_string(context);
+		    goto out;
+		}
+
+		j = proxy_issuer.u.rdnSequence.len;
+		if (proxy_issuer.u.rdnSequence.len < 2 
+		    || proxy_issuer.u.rdnSequence.val[j - 1].len > 1
+		    || der_heim_oid_cmp(&proxy_issuer.u.rdnSequence.val[j - 1].val[0].type,
+					oid_id_at_commonName()))
+		{
+		    ret = HX509_PROXY_CERT_NAME_WRONG;
+		    hx509_set_error_string(context, 0, ret,
+					   "Proxy name too short or "
+					   "does not have Common name "
+					   "at the top");
+		    goto out;
+		}
+
+		free_RelativeDistinguishedName(&proxy_issuer.u.rdnSequence.val[j - 1]);
+		proxy_issuer.u.rdnSequence.len -= 1;
+
+		ret = _hx509_name_cmp(&proxy_issuer, &c->tbsCertificate.issuer);
+		if (ret != 0) {
+		    ret = HX509_PROXY_CERT_NAME_WRONG;
+		    hx509_set_error_string(context, 0, ret,
+					   "Proxy issuer name not as expected");
+		    goto out;
+		}
+
+		break;
+	    } else {
+		/* 
+		 * Now we are done with the proxy certificates, this
+		 * cert was an EE cert and we we will fall though to
+		 * EE checking below.
+		 */
+		type = EE_CERT;
+		/* FALLTHOUGH */
+	    }
+	}
+	case EE_CERT:
+	    /*
+	     * If there where any proxy certificates in the chain
+	     * (proxy_cert_depth > 0), check that the proxy issuer
+	     * matched proxy certificates "base" subject.
+	     */
+	    if (proxy_cert_depth) {
+
+		ret = _hx509_name_cmp(&proxy_issuer,
+				      &c->tbsCertificate.subject);
+		if (ret) {
+		    ret = HX509_PROXY_CERT_NAME_WRONG;
+		    hx509_clear_error_string(context);
+		    goto out;
+		}
+		if (cert->basename)
+		    hx509_name_free(&cert->basename);
+		
+		ret = _hx509_name_from_Name(&proxy_issuer, &cert->basename);
+		if (ret) {
+		    hx509_clear_error_string(context);
+		    goto out;
+		}
+	    }
+
+	    break;
+	}
+
+	ret = check_basic_constraints(context, c, type, i - proxy_cert_depth);
+	if (ret)
+	    goto out;
+	    
+	/*
+	 * Don't check the trust anchors expiration time since they
+	 * are transported out of band, from RFC3820.
+	 */
+	if (i + 1 != path.len || CHECK_TA(ctx)) {
+
+	    t = _hx509_Time2time_t(&c->tbsCertificate.validity.notBefore);
+	    if (t > ctx->time_now) {
+		ret = HX509_CERT_USED_BEFORE_TIME;
+		hx509_clear_error_string(context);
+		goto out;
+	    }
+	    t = _hx509_Time2time_t(&c->tbsCertificate.validity.notAfter);
+	    if (t < ctx->time_now) {
+		ret = HX509_CERT_USED_AFTER_TIME;
+		hx509_clear_error_string(context);
+		goto out;
+	    }
+	}
+
+	if (type == EE_CERT)
+	    type = CA_CERT;
+	else if (type == PROXY_CERT)
+	    proxy_cert_depth++;
+    }
+
+    /*
+     * Verify constraints, do this backward so path constraints are
+     * checked in the right order.
+     */
+
+    for (ret = 0, i = path.len - 1; i >= 0; i--) {
+	Certificate *c;
+
+	c = _hx509_get_cert(path.val[i]);
+
+#if 0
+	/* check that algorithm and parameters is the same */
+	/* XXX this is wrong */
+	ret = alg_cmp(&c->tbsCertificate.signature, alg_id);
+	if (ret) {
+	    hx509_clear_error_string(context);
+	    ret = HX509_PATH_ALGORITHM_CHANGED;
+	    goto out;
+	}
+#endif
+
+	/* verify name constraints, not for selfsigned and anchor */
+	if (!certificate_is_self_signed(c) || i == path.len - 1) {
+	    ret = check_name_constraints(context, &nc, c);
+	    if (ret) {
+		goto out;
+	    }
+	}
+	ret = add_name_constraints(context, c, i == 0, &nc);
+	if (ret)
+	    goto out;
+
+	/* XXX verify all other silly constraints */
+
+    }
+
+    /*
+     * Verify that no certificates has been revoked.
+     */
+
+    if (ctx->revoke_ctx) {
+	hx509_certs certs;
+
+	ret = hx509_certs_init(context, "MEMORY:revoke-certs", 0,
+			       NULL, &certs);
+	if (ret)
+	    goto out;
+
+	for (i = 0; i < path.len; i++) {
+	    ret = hx509_certs_add(context, certs, path.val[i]);
+	    if (ret) {
+		hx509_certs_free(&certs);
+		goto out;
+	    }
+	}
+	ret = hx509_certs_merge(context, certs, pool);
+	if (ret) {
+	    hx509_certs_free(&certs);
+	    goto out;
+	}
+
+	for (i = 0; i < path.len - 1; i++) {
+	    int parent = (i < path.len - 1) ? i + 1 : i;
+
+	    ret = hx509_revoke_verify(context,
+				      ctx->revoke_ctx, 
+				      certs,
+				      ctx->time_now,
+				      path.val[i],
+				      path.val[parent]);
+	    if (ret) {
+		hx509_certs_free(&certs);
+		goto out;
+	    }
+	}
+	hx509_certs_free(&certs);
+    }
+
+#if 0
+    for (i = path.len - 1; i >= 0; i--) {
+	_hx509_print_cert_subject(path.val[i]);
+    }
+#endif
+
+    /*
+     * Verify signatures, do this backward so public key working
+     * parameter is passed up from the anchor up though the chain.
+     */
+
+    for (i = path.len - 1; i >= 0; i--) {
+	Certificate *signer, *c;
+
+	c = _hx509_get_cert(path.val[i]);
+
+	/* is last in chain (trust anchor) */
+	if (i == path.len - 1) {
+	    signer = path.val[i]->data;
+
+	    /* if trust anchor is not self signed, don't check sig */
+	    if (!certificate_is_self_signed(signer))
+		continue;
+	} else {
+	    /* take next certificate in chain */
+	    signer = path.val[i + 1]->data;
+	}
+
+	/* verify signatureValue */
+	ret = _hx509_verify_signature_bitstring(context,
+						signer,
+						&c->signatureAlgorithm,
+						&c->tbsCertificate._save,
+						&c->signatureValue);
+	if (ret) {
+	    hx509_set_error_string(context, HX509_ERROR_APPEND, ret,
+				   "Failed to verify signature of certificate");
+	    goto out;
+	}
+    }
+
+out:
+    free_Name(&proxy_issuer);
+    free_name_constraints(&nc);
+    _hx509_path_free(&path);
+
+    return ret;
+}
+
+int
+hx509_verify_signature(hx509_context context,
+		       const hx509_cert signer,
+		       const AlgorithmIdentifier *alg,
+		       const heim_octet_string *data,
+		       const heim_octet_string *sig)
+{
+    return _hx509_verify_signature(context, signer->data, alg, data, sig);
+}
+
+int
+hx509_verify_hostname(hx509_context context,
+		      const hx509_cert cert,
+		      int require_match,
+		      const char *hostname,
+		      const struct sockaddr *sa,
+		      /* XXX krb5_socklen_t */ int sa_size) 
+{
+    if (sa && sa_size <= 0)
+	return EINVAL;
+    return 0;
+}
+
+int
+_hx509_set_cert_attribute(hx509_context context,
+			  hx509_cert cert, 
+			  const heim_oid *oid, 
+			  const heim_octet_string *attr)
+{
+    hx509_cert_attribute a;
+    void *d;
+
+    if (hx509_cert_get_attribute(cert, oid) != NULL)
+	return 0;
+
+    d = realloc(cert->attrs.val, 
+		sizeof(cert->attrs.val[0]) * (cert->attrs.len + 1));
+    if (d == NULL) {
+	hx509_clear_error_string(context);
+	return ENOMEM;
+    }
+    cert->attrs.val = d;
+
+    a = malloc(sizeof(*a));
+    if (a == NULL)
+	return ENOMEM;
+
+    der_copy_octet_string(attr, &a->data);
+    der_copy_oid(oid, &a->oid);
+    
+    cert->attrs.val[cert->attrs.len] = a;
+    cert->attrs.len++;
+
+    return 0;
+}
+
+hx509_cert_attribute
+hx509_cert_get_attribute(hx509_cert cert, const heim_oid *oid)
+{
+    int i;
+    for (i = 0; i < cert->attrs.len; i++)
+	if (der_heim_oid_cmp(oid, &cert->attrs.val[i]->oid) == 0)
+	    return cert->attrs.val[i];
+    return NULL;
+}
+
+int
+hx509_cert_set_friendly_name(hx509_cert cert, const char *name)
+{
+    if (cert->friendlyname)
+	free(cert->friendlyname);
+    cert->friendlyname = strdup(name);
+    if (cert->friendlyname == NULL)
+	return ENOMEM;
+    return 0;
+}
+
+
+const char *
+hx509_cert_get_friendly_name(hx509_cert cert)
+{
+    hx509_cert_attribute a;
+    PKCS9_friendlyName n;
+    size_t sz;
+    int ret, i;
+
+    if (cert->friendlyname)
+	return cert->friendlyname;
+
+    a = hx509_cert_get_attribute(cert, oid_id_pkcs_9_at_friendlyName());
+    if (a == NULL) {
+	/* XXX use subject name ? */
+	return NULL; 
+    }
+
+    ret = decode_PKCS9_friendlyName(a->data.data, a->data.length, &n, &sz);
+    if (ret)
+	return NULL;
+	
+    if (n.len != 1) {
+	free_PKCS9_friendlyName(&n);
+	return NULL;
+    }
+    
+    cert->friendlyname = malloc(n.val[0].length + 1);
+    if (cert->friendlyname == NULL) {
+	free_PKCS9_friendlyName(&n);
+	return NULL;
+    }
+    
+    for (i = 0; i < n.val[0].length; i++) {
+	if (n.val[0].data[i] <= 0xff)
+	    cert->friendlyname[i] = n.val[0].data[i] & 0xff;
+	else
+	    cert->friendlyname[i] = 'X';
+    }
+    cert->friendlyname[i] = '\0';
+    free_PKCS9_friendlyName(&n);
+
+    return cert->friendlyname;
+}
+
+void
+_hx509_query_clear(hx509_query *q)
+{
+    memset(q, 0, sizeof(*q));
+}
+
+int
+hx509_query_alloc(hx509_context context, hx509_query **q)
+{
+    *q = calloc(1, sizeof(**q));
+    if (*q == NULL)
+	return ENOMEM;
+    return 0;
+}
+
+void
+hx509_query_match_option(hx509_query *q, hx509_query_option option)
+{
+    switch(option) {
+    case HX509_QUERY_OPTION_PRIVATE_KEY:
+	q->match |= HX509_QUERY_PRIVATE_KEY;
+	break;
+    case HX509_QUERY_OPTION_KU_ENCIPHERMENT:
+	q->match |= HX509_QUERY_KU_ENCIPHERMENT;
+	break;
+    case HX509_QUERY_OPTION_KU_DIGITALSIGNATURE:
+	q->match |= HX509_QUERY_KU_DIGITALSIGNATURE;
+	break;
+    case HX509_QUERY_OPTION_KU_KEYCERTSIGN:
+	q->match |= HX509_QUERY_KU_KEYCERTSIGN;
+	break;
+    case HX509_QUERY_OPTION_END:
+    default:
+	break;
+    }
+}
+
+int
+hx509_query_match_issuer_serial(hx509_query *q,
+				const Name *issuer, 
+				const heim_integer *serialNumber)
+{
+    int ret;
+    if (q->serial) {
+	der_free_heim_integer(q->serial);
+	free(q->serial);
+    }
+    q->serial = malloc(sizeof(*q->serial));
+    if (q->serial == NULL)
+	return ENOMEM;
+    ret = der_copy_heim_integer(serialNumber, q->serial);
+    if (ret) {
+	free(q->serial);
+	q->serial = NULL;
+	return ret;
+    }
+    if (q->issuer_name) {
+	free_Name(q->issuer_name);
+	free(q->issuer_name);
+    }
+    q->issuer_name = malloc(sizeof(*q->issuer_name));
+    if (q->issuer_name == NULL)
+	return ENOMEM;
+    ret = copy_Name(issuer, q->issuer_name);
+    if (ret) {
+	free(q->issuer_name);
+	q->issuer_name = NULL;
+	return ret;
+    }
+    q->match |= HX509_QUERY_MATCH_SERIALNUMBER|HX509_QUERY_MATCH_ISSUER_NAME;
+    return 0;
+}
+
+
+int
+hx509_query_match_friendly_name(hx509_query *q, const char *name)
+{
+    if (q->friendlyname)
+	free(q->friendlyname);
+    q->friendlyname = strdup(name);
+    if (q->friendlyname == NULL)
+	return ENOMEM;
+    q->match |= HX509_QUERY_MATCH_FRIENDLY_NAME;
+    return 0;
+}
+
+int
+hx509_query_match_cmp_func(hx509_query *q,
+			   int (*func)(void *, hx509_cert),
+			   void *ctx)
+{
+    if (func)
+	q->match |= HX509_QUERY_MATCH_FUNCTION;
+    else
+	q->match &= ~HX509_QUERY_MATCH_FUNCTION;
+    q->cmp_func = func;
+    q->cmp_func_ctx = ctx;
+    return 0;
+}
+
+
+void
+hx509_query_free(hx509_context context, hx509_query *q)
+{
+    if (q->serial) {
+	der_free_heim_integer(q->serial);
+	free(q->serial);
+	q->serial = NULL;
+    }
+    if (q->issuer_name) {
+	free_Name(q->issuer_name);
+	free(q->issuer_name);
+	q->issuer_name = NULL;
+    }
+    if (q) {
+	free(q->friendlyname);
+	memset(q, 0, sizeof(*q));
+    }
+    free(q);
+}
+
+int
+_hx509_query_match_cert(hx509_context context, const hx509_query *q, hx509_cert cert)
+{
+    Certificate *c = _hx509_get_cert(cert);
+
+    if ((q->match & HX509_QUERY_FIND_ISSUER_CERT) &&
+	_hx509_cert_is_parent_cmp(q->subject, c, 0) != 0)
+	return 0;
+
+    if ((q->match & HX509_QUERY_MATCH_CERTIFICATE) &&
+	_hx509_Certificate_cmp(q->certificate, c) != 0)
+	return 0;
+
+    if ((q->match & HX509_QUERY_MATCH_SERIALNUMBER)
+	&& der_heim_integer_cmp(&c->tbsCertificate.serialNumber, q->serial) != 0)
+	return 0;
+
+    if ((q->match & HX509_QUERY_MATCH_ISSUER_NAME)
+	&& _hx509_name_cmp(&c->tbsCertificate.issuer, q->issuer_name) != 0)
+	return 0;
+
+    if ((q->match & HX509_QUERY_MATCH_SUBJECT_NAME)
+	&& _hx509_name_cmp(&c->tbsCertificate.subject, q->subject_name) != 0)
+	return 0;
+
+    if (q->match & HX509_QUERY_MATCH_SUBJECT_KEY_ID) {
+	SubjectKeyIdentifier si;
+	int ret;
+
+	ret = _hx509_find_extension_subject_key_id(c, &si);
+	if (ret == 0) {
+	    if (der_heim_octet_string_cmp(&si, q->subject_id) != 0)
+		ret = 1;
+	    free_SubjectKeyIdentifier(&si);
+	}
+	if (ret)
+	    return 0;
+    }
+    if ((q->match & HX509_QUERY_MATCH_ISSUER_ID))
+	return 0;
+    if ((q->match & HX509_QUERY_PRIVATE_KEY) && 
+	_hx509_cert_private_key(cert) == NULL)
+	return 0;
+
+    {
+	unsigned ku = 0;
+	if (q->match & HX509_QUERY_KU_DIGITALSIGNATURE)
+	    ku |= (1 << 0);
+	if (q->match & HX509_QUERY_KU_NONREPUDIATION)
+	    ku |= (1 << 1);
+	if (q->match & HX509_QUERY_KU_ENCIPHERMENT)
+	    ku |= (1 << 2);
+	if (q->match & HX509_QUERY_KU_DATAENCIPHERMENT)
+	    ku |= (1 << 3);
+	if (q->match & HX509_QUERY_KU_KEYAGREEMENT)
+	    ku |= (1 << 4);
+	if (q->match & HX509_QUERY_KU_KEYCERTSIGN)
+	    ku |= (1 << 5);
+	if (q->match & HX509_QUERY_KU_CRLSIGN)
+	    ku |= (1 << 6);
+	if (ku && check_key_usage(context, c, ku, TRUE))
+	    return 0;
+    }
+    if ((q->match & HX509_QUERY_ANCHOR))
+	return 0;
+
+    if (q->match & HX509_QUERY_MATCH_LOCAL_KEY_ID) {
+	hx509_cert_attribute a;
+
+	a = hx509_cert_get_attribute(cert, oid_id_pkcs_9_at_localKeyId());
+	if (a == NULL)
+	    return 0;
+	if (der_heim_octet_string_cmp(&a->data, q->local_key_id) != 0)
+	    return 0;
+    }
+
+    if (q->match & HX509_QUERY_NO_MATCH_PATH) {
+	size_t i;
+
+	for (i = 0; i < q->path->len; i++)
+	    if (hx509_cert_cmp(q->path->val[i], cert) == 0)
+		return 0;
+    }
+    if (q->match & HX509_QUERY_MATCH_FRIENDLY_NAME) {
+	const char *name = hx509_cert_get_friendly_name(cert);
+	if (name == NULL)
+	    return 0;
+	if (strcasecmp(q->friendlyname, name) != 0)
+	    return 0;
+    }
+    if (q->match & HX509_QUERY_MATCH_FUNCTION) {
+	int ret = (*q->cmp_func)(q->cmp_func_ctx, cert);
+	if (ret != 0)
+	    return 0;
+    }
+
+    if (q->match & HX509_QUERY_MATCH_KEY_HASH_SHA1) {
+	heim_octet_string os;
+	int ret;
+
+	os.data = c->tbsCertificate.subjectPublicKeyInfo.subjectPublicKey.data;
+	os.length = 
+	    c->tbsCertificate.subjectPublicKeyInfo.subjectPublicKey.length / 8;
+
+	ret = _hx509_verify_signature(context,
+				      NULL,
+				      hx509_signature_sha1(),
+				      &os,
+				      q->keyhash_sha1);
+	if (ret != 0)
+	    return 0;
+    }
+
+    if (q->match & HX509_QUERY_MATCH_TIME) {
+	time_t t;
+	t = _hx509_Time2time_t(&c->tbsCertificate.validity.notBefore);
+	if (t > q->timenow)
+	    return 0;
+	t = _hx509_Time2time_t(&c->tbsCertificate.validity.notAfter);
+	if (t < q->timenow)
+	    return 0;
+    }
+
+    if (q->match & ~HX509_QUERY_MASK)
+	return 0;
+
+    return 1;
+}
+
+int
+hx509_cert_check_eku(hx509_context context, hx509_cert cert,
+		     const heim_oid *eku, int allow_any_eku)
+{
+    ExtKeyUsage e;
+    int ret, i;
+
+    ret = find_extension_eku(_hx509_get_cert(cert), &e);
+    if (ret) {
+	hx509_clear_error_string(context);
+	return ret;
+    }
+
+    for (i = 0; i < e.len; i++) {
+	if (der_heim_oid_cmp(eku, &e.val[i]) == 0) {
+	    free_ExtKeyUsage(&e);
+	    return 0;
+	}
+	if (allow_any_eku) {
+#if 0
+	    if (der_heim_oid_cmp(id_any_eku, &e.val[i]) == 0) {
+		free_ExtKeyUsage(&e);
+		return 0;
+	    }
+#endif
+	}
+    }
+    free_ExtKeyUsage(&e);
+    hx509_clear_error_string(context);
+    return HX509_CERTIFICATE_MISSING_EKU;
+}
+
+int
+_hx509_cert_get_keyusage(hx509_context context,
+			 hx509_cert c,
+			 KeyUsage *ku)
+{
+    Certificate *cert;
+    const Extension *e;
+    size_t size;
+    int ret, i = 0;
+
+    memset(ku, 0, sizeof(*ku));
+
+    cert = _hx509_get_cert(c);
+
+    if (_hx509_cert_get_version(cert) < 3)
+	return 0;
+
+    e = find_extension(cert, oid_id_x509_ce_keyUsage(), &i);
+    if (e == NULL)
+	return HX509_KU_CERT_MISSING;
+    
+    ret = decode_KeyUsage(e->extnValue.data, e->extnValue.length, ku, &size);
+    if (ret)
+	return ret;
+    return 0;
+}