Improved GHASH pclmul implementation (parallel processing of four blocks, +70% speed).

[BearSSL] / src / x509 / x509_minimal.t0

\ Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
\
\ Permission is hereby granted, free of charge, to any person obtaining 
\ a copy of this software and associated documentation files (the
\ "Software"), to deal in the Software without restriction, including
\ without limitation the rights to use, copy, modify, merge, publish,
\ distribute, sublicense, and/or sell copies of the Software, and to
\ permit persons to whom the Software is furnished to do so, subject to
\ the following conditions:
\
\ The above copyright notice and this permission notice shall be 
\ included in all copies or substantial portions of the Software.
\
\ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
\ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
\ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
\ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
\ BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
\ ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
\ CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
\ SOFTWARE.

preamble {

#include "inner.h"

/*
 * Implementation Notes
 * --------------------
 *
 * The C code pushes the data by chunks; all decoding is done in the
 * T0 code. The cert_length value is set to the certificate length when
 * a new certificate is started; the T0 code picks it up as outer limit,
 * and decoding functions use it to ensure that no attempt is made at
 * reading past it. The T0 code also checks that once the certificate is
 * decoded, there are no trailing bytes.
 *
 * The T0 code sets cert_length to 0 when the certificate is fully
 * decoded.
 *
 * The C code must still perform two checks:
 *
 *  -- If the certificate length is 0, then the T0 code will not be
 *  invoked at all. This invalid condition must thus be reported by the
 *  C code.
 *
 *  -- When reaching the end of certificate, the C code must verify that
 *  the certificate length has been set to 0, thereby signaling that
 *  the T0 code properly decoded a certificate.
 *
 * Processing of a chain works in the following way:
 *
 *  -- The error flag is set to a non-zero value when validation is
 *  finished. The value is either BR_ERR_X509_OK (validation is
 *  successful) or another non-zero error code. When a non-zero error
 *  code is obtained, the remaining bytes in the current certificate and
 *  the subsequent certificates (if any) are completely ignored.
 *
 *  -- Each certificate is decoded in due course, with the following
 *  "interesting points":
 *
 *     -- Start of the TBS: the multihash engine is reset and activated.
 *
 *     -- Start of the issuer DN: the secondary hash engine is started,
 *     to process the encoded issuer DN.
 *
 *     -- End of the issuer DN: the secondary hash engine is stopped. The
 *     resulting hash value is computed and then copied into the
 *     next_dn_hash[] buffer.
 *
 *     -- Start of the subject DN: the secondary hash engine is started,
 *     to process the encoded subject DN.
 *
 *     -- For the EE certificate only: the Common Name, if any, is matched
 *     against the expected server name.
 *
 *     -- End of the subject DN: the secondary hash engine is stopped. The
 *     resulting hash value is computed into the pad. It is then processed:
 *
 *        -- If this is the EE certificate, then the hash is ignored
 *        (except for direct trust processing, see later; the hash is
 *        simply left in current_dn_hash[]).
 *
 *        -- Otherwise, the hashed subject DN is compared with the saved
 *        hash value (in saved_dn_hash[]). They must match.
 *
 *     Either way, the next_dn_hash[] value is then copied into the
 *     saved_dn_hash[] value. Thus, at that point, saved_dn_hash[]
 *     contains the hash of the issuer DN for the current certificate,
 *     and current_dn_hash[] contains the hash of the subject DN for the
 *     current certificate.
 *
 *     -- Public key: it is decoded into the cert_pkey[] buffer. Unknown
 *     key types are reported at that point.
 *
 *        -- If this is the EE certificate, then the key type is compared
 *        with the expected key type (initialization parameter). The public
 *        key data is copied to ee_pkey_data[]. The key and hashed subject
 *        DN are also compared with the "direct trust" keys; if the key
 *        and DN are matched, then validation ends with a success.
 *
 *        -- Otherwise, the saved signature (cert_sig[]) is verified
 *        against the saved TBS hash (tbs_hash[]) and that freshly
 *        decoded public key. Failure here ends validation with an error.
 *
 *     -- Extensions: extension values are processed in due order.
 *
 *        -- Basic Constraints: for all certificates except EE, must be
 *        present, indicate a CA, and have a path legnth compatible with
 *        the chain length so far.
 *
 *        -- Key Usage: for the EE, if present, must allow signatures
 *        or encryption/key exchange, as required for the cipher suite.
 *        For non-EE, if present, must have the "certificate sign" bit.
 *
 *        -- Subject Alt Name: for the EE, dNSName names are matched
 *        against the server name. Ignored for non-EE.
 *
 *        -- Authority Key Identifier, Subject Key Identifier, Issuer
 *        Alt Name, Subject Directory Attributes, CRL Distribution Points
 *        Freshest CRL, Authority Info Access and Subject Info Access
 *        extensions are always ignored: they either contain only
 *        informative data, or they relate to revocation processing, which
 *        we explicitly do not support.
 *
 *        -- All other extensions are ignored if non-critical. If a
 *        critical extension other than the ones above is encountered,
 *        then a failure is reported.
 *
 *     -- End of the TBS: the multihash engine is stopped.
 *
 *     -- Signature algorithm: the signature algorithm on the
 *     certificate is decoded. A failure is reported if that algorithm
 *     is unknown. The hashed TBS corresponding to the signature hash
 *     function is computed and stored in tbs_hash[] (if not supported,
 *     then a failure is reported). The hash OID and length are stored
 *     in cert_sig_hash_oid and cert_sig_hash_len.
 *
 *     -- Signature value: the signature value is copied into the
 *     cert_sig[] array.
 *
 *     -- Certificate end: the hashed issuer DN (saved_dn_hash[]) is
 *     looked up in the trust store (CA trust anchors only); for all
 *     that match, the signature (cert_sig[]) is verified against the
 *     anchor public key (hashed TBS is in tbs_hash[]). If one of these
 *     signatures is valid, then validation ends with a success.
 *
 *  -- If the chain end is reached without obtaining a validation success,
 *  then validation is reported as failed.
 */

#ifndef BR_USE_UNIX_TIME
#if defined __unix__ || defined __linux__ \
        || defined _POSIX_SOURCE || defined _POSIX_C_SOURCE \
        || (defined __APPLE__ && defined __MACH__)
#define BR_USE_UNIX_TIME   1
#endif
#endif

#ifndef BR_USE_WIN32_TIME
#if defined _WIN32 || defined _WIN64
#define BR_USE_WIN32_TIME   1
#endif
#endif

#if BR_USE_UNIX_TIME
#include <time.h>
#endif

#if BR_USE_WIN32_TIME
#include <windows.h>
#endif

void br_x509_minimal_init_main(void *ctx);
void br_x509_minimal_run(void *ctx);

/* see bearssl_x509.h */
void
br_x509_minimal_init(br_x509_minimal_context *ctx,
        const br_hash_class *dn_hash_impl,
        const br_x509_trust_anchor *trust_anchors, size_t trust_anchors_num)
{
        memset(ctx, 0, sizeof *ctx);
        ctx->vtable = &br_x509_minimal_vtable;
        ctx->dn_hash_impl = dn_hash_impl;
        ctx->trust_anchors = trust_anchors;
        ctx->trust_anchors_num = trust_anchors_num;
}

static void
xm_start_chain(const br_x509_class **ctx, const char *server_name)
{
        br_x509_minimal_context *cc;
        size_t u;

        cc = (br_x509_minimal_context *)ctx;
        for (u = 0; u < cc->num_name_elts; u ++) {
                cc->name_elts[u].status = 0;
                cc->name_elts[u].buf[0] = 0;
        }
        memset(&cc->pkey, 0, sizeof cc->pkey);
        cc->num_certs = 0;
        cc->err = 0;
        cc->cpu.dp = cc->dp_stack;
        cc->cpu.rp = cc->rp_stack;
        br_x509_minimal_init_main(&cc->cpu);
        if (server_name == NULL || *server_name == 0) {
                cc->server_name = NULL;
        } else {
                cc->server_name = server_name;
        }
}

static void
xm_start_cert(const br_x509_class **ctx, uint32_t length)
{
        br_x509_minimal_context *cc;

        cc = (br_x509_minimal_context *)ctx;
        if (cc->err != 0) {
                return;
        }
        if (length == 0) {
                cc->err = BR_ERR_X509_TRUNCATED;
                return;
        }
        cc->cert_length = length;
}

static void
xm_append(const br_x509_class **ctx, const unsigned char *buf, size_t len)
{
        br_x509_minimal_context *cc;

        cc = (br_x509_minimal_context *)ctx;
        if (cc->err != 0) {
                return;
        }
        cc->hbuf = buf;
        cc->hlen = len;
        br_x509_minimal_run(&cc->cpu);
}

static void
xm_end_cert(const br_x509_class **ctx)
{
        br_x509_minimal_context *cc;

        cc = (br_x509_minimal_context *)ctx;
        if (cc->err == 0 && cc->cert_length != 0) {
                cc->err = BR_ERR_X509_TRUNCATED;
        }
        cc->num_certs ++;
}

static unsigned
xm_end_chain(const br_x509_class **ctx)
{
        br_x509_minimal_context *cc;

        cc = (br_x509_minimal_context *)ctx;
        if (cc->err == 0) {
                if (cc->num_certs == 0) {
                        cc->err = BR_ERR_X509_EMPTY_CHAIN;
                } else {
                        cc->err = BR_ERR_X509_NOT_TRUSTED;
                }
        } else if (cc->err == BR_ERR_X509_OK) {
                return 0;
        }
        return (unsigned)cc->err;
}

static const br_x509_pkey *
xm_get_pkey(const br_x509_class *const *ctx, unsigned *usages)
{
        br_x509_minimal_context *cc;

        cc = (br_x509_minimal_context *)ctx;
        if (cc->err == BR_ERR_X509_OK
                || cc->err == BR_ERR_X509_NOT_TRUSTED)
        {
                if (usages != NULL) {
                        *usages = cc->key_usages;
                }
                return &((br_x509_minimal_context *)ctx)->pkey;
        } else {
                return NULL;
        }
}

/* see bearssl_x509.h */
const br_x509_class br_x509_minimal_vtable = {
        sizeof(br_x509_minimal_context),
        xm_start_chain,
        xm_start_cert,
        xm_append,
        xm_end_cert,
        xm_end_chain,
        xm_get_pkey
};

#define CTX   ((br_x509_minimal_context *)((unsigned char *)t0ctx - offsetof(br_x509_minimal_context, cpu)))
#define CONTEXT_NAME   br_x509_minimal_context

#define DNHASH_LEN   ((CTX->dn_hash_impl->desc >> BR_HASHDESC_OUT_OFF) & BR_HASHDESC_OUT_MASK)

/*
 * Hash a DN (from a trust anchor) into the provided buffer. This uses the
 * DN hash implementation and context structure from the X.509 engine
 * context.
 */
static void
hash_dn(br_x509_minimal_context *ctx, const void *dn, size_t len,
        unsigned char *out)
{
        ctx->dn_hash_impl->init(&ctx->dn_hash.vtable);
        ctx->dn_hash_impl->update(&ctx->dn_hash.vtable, dn, len);
        ctx->dn_hash_impl->out(&ctx->dn_hash.vtable, out);
}

/*
 * Compare two big integers for equality. The integers use unsigned big-endian
 * encoding; extra leading bytes (of value 0) are allowed.
 */
static int
eqbigint(const unsigned char *b1, size_t len1,
        const unsigned char *b2, size_t len2)
{
        while (len1 > 0 && *b1 == 0) {
                b1 ++;
                len1 --;
        }
        while (len2 > 0 && *b2 == 0) {
                b2 ++;
                len2 --;
        }
        if (len1 != len2) {
                return 0;
        }
        return memcmp(b1, b2, len1) == 0;
}

/*
 * Compare two strings for equality, in a case-insensitive way. This
 * function handles casing only for ASCII letters.
 */
static int
eqnocase(const void *s1, const void *s2, size_t len)
{
        const unsigned char *buf1, *buf2;

        buf1 = s1;
        buf2 = s2;
        while (len -- > 0) {
                int x1, x2;

                x1 = *buf1 ++;
                x2 = *buf2 ++;
                if (x1 >= 'A' && x1 <= 'Z') {
                        x1 += 'a' - 'A';
                }
                if (x2 >= 'A' && x2 <= 'Z') {
                        x2 += 'a' - 'A';
                }
                if (x1 != x2) {
                        return 0;
                }
        }
        return 1;
}

static int verify_signature(br_x509_minimal_context *ctx,
        const br_x509_pkey *pk);

}

postamble {

/*
 * Verify the signature on the certificate with the provided public key.
 * This function checks the public key type with regards to the expected
 * type. Returned value is either 0 on success, or a non-zero error code.
 */
static int
verify_signature(br_x509_minimal_context *ctx, const br_x509_pkey *pk)
{
        int kt;

        kt = ctx->cert_signer_key_type;
        if ((pk->key_type & 0x0F) != kt) {
                return BR_ERR_X509_WRONG_KEY_TYPE;
        }
        switch (kt) {
                unsigned char tmp[64];

        case BR_KEYTYPE_RSA:
                if (ctx->irsa == 0) {
                        return BR_ERR_X509_UNSUPPORTED;
                }
                if (!ctx->irsa(ctx->cert_sig, ctx->cert_sig_len,
                        &t0_datablock[ctx->cert_sig_hash_oid],
                        ctx->cert_sig_hash_len, &pk->key.rsa, tmp))
                {
                        return BR_ERR_X509_BAD_SIGNATURE;
                }
                if (memcmp(ctx->tbs_hash, tmp, ctx->cert_sig_hash_len) != 0) {
                        return BR_ERR_X509_BAD_SIGNATURE;
                }
                return 0;

        case BR_KEYTYPE_EC:
                if (ctx->iecdsa == 0) {
                        return BR_ERR_X509_UNSUPPORTED;
                }
                if (!ctx->iecdsa(ctx->iec, ctx->tbs_hash,
                        ctx->cert_sig_hash_len, &pk->key.ec,
                        ctx->cert_sig, ctx->cert_sig_len))
                {
                        return BR_ERR_X509_BAD_SIGNATURE;
                }
                return 0;

        default:
                return BR_ERR_X509_UNSUPPORTED;
        }
}

}

cc: read8-low ( -- x ) {
        if (CTX->hlen == 0) {
                T0_PUSHi(-1);
        } else {
                unsigned char x = *CTX->hbuf ++;
                if (CTX->do_mhash) {
                        br_multihash_update(&CTX->mhash, &x, 1);
                }
                if (CTX->do_dn_hash) {
                        CTX->dn_hash_impl->update(&CTX->dn_hash.vtable, &x, 1);
                }
                CTX->hlen --;
                T0_PUSH(x);
        }
}

addr: cert_length
addr: num_certs

cc: read-blob-inner ( addr len -- addr len ) {
        uint32_t len = T0_POP();
        uint32_t addr = T0_POP();
        size_t clen = CTX->hlen;
        if (clen > len) {
                clen = (size_t)len;
        }
        if (addr != 0) {
                memcpy((unsigned char *)CTX + addr, CTX->hbuf, clen);
        }
        if (CTX->do_mhash) {
                br_multihash_update(&CTX->mhash, CTX->hbuf, clen);
        }
        if (CTX->do_dn_hash) {
                CTX->dn_hash_impl->update(
                        &CTX->dn_hash.vtable, CTX->hbuf, clen);
        }
        CTX->hbuf += clen;
        CTX->hlen -= clen;
        T0_PUSH(addr + clen);
        T0_PUSH(len - clen);
}

\ Compute the TBS hash, using the provided hash ID. The hash value is
\ written in the tbs_hash[] array, and the hash length is returned. If
\ the requested hash function is not supported, then 0 is returned.
cc: compute-tbs-hash ( id -- hashlen ) {
        int id = T0_POPi();
        size_t len;
        len = br_multihash_out(&CTX->mhash, id, CTX->tbs_hash);
        T0_PUSH(len);
}

\ Push true (-1) if no server name is expected in the EE certificate.
cc: zero-server-name ( -- bool ) {
        T0_PUSHi(-(CTX->server_name == NULL));
}

addr: key_usages
addr: cert_sig
addr: cert_sig_len
addr: cert_signer_key_type
addr: cert_sig_hash_oid
addr: cert_sig_hash_len
addr: tbs_hash
addr: min_rsa_size

\ Start TBS hash computation. The hash functions are reinitialised.
cc: start-tbs-hash ( -- ) {
        br_multihash_init(&CTX->mhash);
        CTX->do_mhash = 1;
}

\ Stop TBS hash computation.
cc: stop-tbs-hash ( -- ) {
        CTX->do_mhash = 0;
}

\ Start DN hash computation.
cc: start-dn-hash ( -- ) {
        CTX->dn_hash_impl->init(&CTX->dn_hash.vtable);
        CTX->do_dn_hash = 1;
}

\ Terminate DN hash computation and write the DN hash into the
\ current_dn_hash buffer.
cc: compute-dn-hash ( -- ) {
        CTX->dn_hash_impl->out(&CTX->dn_hash.vtable, CTX->current_dn_hash);
        CTX->do_dn_hash = 0;
}

\ Get the length of hash values obtained with the DN hasher.
cc: dn-hash-length ( -- len ) {
        T0_PUSH(DNHASH_LEN);
}

\ Copy data between two areas in the context.
cc: blobcopy ( addr-dst addr-src len -- ) {
        size_t len = T0_POP();
        unsigned char *src = (unsigned char *)CTX + T0_POP();
        unsigned char *dst = (unsigned char *)CTX + T0_POP();
        memcpy(dst, src, len);
}

addr: current_dn_hash
addr: next_dn_hash
addr: saved_dn_hash

\ Read a DN, hashing it into current_dn_hash. The DN contents are not
\ inspected (only the outer tag, for SEQUENCE, is checked).
: read-DN ( lim -- lim )
        start-dn-hash
        read-sequence-open skip-close-elt
        compute-dn-hash ;

cc: offset-name-element ( san -- n ) {
        unsigned san = T0_POP();
        size_t u;

        for (u = 0; u < CTX->num_name_elts; u ++) {
                if (CTX->name_elts[u].status == 0) {
                        const unsigned char *oid;
                        size_t len, off;

                        oid = CTX->name_elts[u].oid;
                        if (san) {
                                if (oid[0] != 0 || oid[1] != 0) {
                                        continue;
                                }
                                off = 2;
                        } else {
                                off = 0;
                        }
                        len = oid[off];
                        if (len != 0 && len == CTX->pad[0]
                                && memcmp(oid + off + 1,
                                        CTX->pad + 1, len) == 0)
                        {
                                T0_PUSH(u);
                                T0_RET();
                        }
                }
        }
        T0_PUSHi(-1);
}

cc: copy-name-element ( bool offbuf -- ) {
        size_t len;
        int32_t off = T0_POPi();
        int ok = T0_POPi();

        if (off >= 0) {
                br_name_element *ne = &CTX->name_elts[off];

                if (ok) {
                        len = CTX->pad[0];
                        if (len < ne->len) {
                                memcpy(ne->buf, CTX->pad + 1, len);
                                ne->buf[len] = 0;
                                ne->status = 1;
                        } else {
                                ne->status = -1;
                        }
                } else {
                        ne->status = -1;
                }
        }
}

cc: copy-name-SAN ( bool tag -- ) {
        unsigned tag = T0_POP();
        unsigned ok = T0_POP();
        size_t u, len;

        len = CTX->pad[0];
        for (u = 0; u < CTX->num_name_elts; u ++) {
                br_name_element *ne;

                ne = &CTX->name_elts[u];
                if (ne->status == 0 && ne->oid[0] == 0 && ne->oid[1] == tag) {
                        if (ok && ne->len > len) {
                                memcpy(ne->buf, CTX->pad + 1, len);
                                ne->buf[len] = 0;
                                ne->status = 1;
                        } else {
                                ne->status = -1;
                        }
                        break;
                }
        }
}

\ Read a value, decoding string types. If the string type is recognised
\ and the value could be converted to UTF-8 into the pad, then true (-1)
\ is returned; in all other cases, false (0) is returned. Either way, the
\ object is consumed.
: read-string ( lim -- lim bool )
        read-tag case
                \ UTF8String
                12 of check-primitive read-value-UTF8 endof
                \ NumericString
                18 of check-primitive read-value-latin1 endof
                \ PrintableString
                19 of check-primitive read-value-latin1 endof
                \ TeletexString
                20 of check-primitive read-value-latin1 endof
                \ IA5String
                22 of check-primitive read-value-latin1 endof
                \ BMPString
                30 of check-primitive read-value-UTF16 endof
                2drop read-length-skip 0 0
        endcase ;

\ Read a DN for the EE. The normalized DN hash is computed and stored in the
\ current_dn_hash.
\ Name elements are gathered. Also, the Common Name is matched against the
\ intended server name.
\ Returned value is true (-1) if the CN matches the intended server name,
\ false (0) otherwise.
: read-DN-EE ( lim -- lim bool )
        \ Flag will be set to true if there is a CN and it matches the
        \ intended server name.
        0 { eename-matches }

        \ Activate DN hashing.
        start-dn-hash

        \ Parse the DN structure: it is a SEQUENCE of SET of
        \ AttributeTypeAndValue. Each AttributeTypeAndValue is a
        \ SEQUENCE { OBJECT IDENTIFIER, ANY }.
        read-sequence-open
        begin
                dup while

                read-tag 0x11 check-tag-constructed read-length-open-elt
                dup ifnot ERR_X509_BAD_DN fail then
                begin
                        dup while

                        read-sequence-open

                        \ Read the OID. If the OID could not be read (too
                        \ long) then the first pad byte will be 0.
                        read-OID drop

                        \ If it is the Common Name then we'll need to
                        \ match it against the intended server name (if
                        \ applicable).
                        id-at-commonName eqOID { isCN }

                        \ Get offset for reception buffer for that element
                        \ (or -1).
                        0 offset-name-element { offbuf }

                        \ Try to read the value as a string.
                        read-string

                        \ If the value could be decoded as a string,
                        \ copy it and/or match it, as appropriate.
                        dup isCN and if
                                match-server-name if
                                        -1 >eename-matches
                                then
                        then
                        offbuf copy-name-element

                        \ Close the SEQUENCE
                        close-elt

                repeat
                close-elt
        repeat
        close-elt

        \ Compute DN hash and deactivate DN hashing.
        compute-dn-hash

        \ Return the CN match flag.
        eename-matches ;

\ Get the validation date and time from the context or system.
cc: get-system-date ( -- days seconds ) {
        if (CTX->days == 0 && CTX->seconds == 0) {
#if BR_USE_UNIX_TIME
                time_t x = time(NULL);

                T0_PUSH((uint32_t)(x / 86400) + 719528);
                T0_PUSH((uint32_t)(x % 86400));
#elif BR_USE_WIN32_TIME
                FILETIME ft;
                uint64_t x;

                GetSystemTimeAsFileTime(&ft);
                x = ((uint64_t)ft.dwHighDateTime << 32)
                        + (uint64_t)ft.dwLowDateTime;
                x = (x / 10000000);
                T0_PUSH((uint32_t)(x / 86400) + 584754);
                T0_PUSH((uint32_t)(x % 86400));
#else
                CTX->err = BR_ERR_X509_TIME_UNKNOWN;
                T0_CO();
#endif
        } else {
                T0_PUSH(CTX->days);
                T0_PUSH(CTX->seconds);
        }
}

\ Compare two dates (days+seconds) together.
: before ( days1 seconds1 days2 seconds2 -- bool )
        { d1 s1 d2 s2 }
        d1 d2 = if s1 s2 < else d1 d2 < then ;

: after ( days1 seconds1 days2 seconds2 -- bool )
        swap2 before ;

\ Swap the top two elements with the two elements immediately below.
: swap2 ( a b c d -- c d a b )
        3 roll 3 roll ;

\ Match the name in the pad with the expected server name. Returned value
\ is true (-1) on match, false (0) otherwise. If there is no expected
\ server name, then 0 is returned.
\ Match conditions: either an exact match (case insensitive), or a
\ wildcard match, if the found name starts with "*.". We only match a
\ starting wildcard, and only against a complete DN name component.
cc: match-server-name ( -- bool ) {
        size_t n1, n2;

        if (CTX->server_name == NULL) {
                T0_PUSH(0);
                T0_RET();
        }
        n1 = strlen(CTX->server_name);
        n2 = CTX->pad[0];
        if (n1 == n2 && eqnocase(&CTX->pad[1], CTX->server_name, n1)) {
                T0_PUSHi(-1);
                T0_RET();
        }
        if (n2 >= 2 && CTX->pad[1] == '*' && CTX->pad[2] == '.') {
                size_t u;

                u = 0;
                while (u < n1 && CTX->server_name[u] != '.') {
                        u ++;
                }
                u ++;
                n1 -= u;
                if ((n2 - 2) == n1
                        && eqnocase(&CTX->pad[3], CTX->server_name + u, n1))
                {
                        T0_PUSHi(-1);
                        T0_RET();
                }
        }
        T0_PUSH(0);
}

\ Get the address and length for the pkey_data buffer.
: addr-len-pkey_data ( -- addr len )
        CX 0 8191 { offsetof(br_x509_minimal_context, pkey_data) }
        CX 0 8191 { BR_X509_BUFSIZE_KEY } ;

\ Copy the EE public key to the permanent buffer (RSA).
cc: copy-ee-rsa-pkey ( nlen elen -- ) {
        size_t elen = T0_POP();
        size_t nlen = T0_POP();
        memcpy(CTX->ee_pkey_data, CTX->pkey_data, nlen + elen);
        CTX->pkey.key_type = BR_KEYTYPE_RSA;
        CTX->pkey.key.rsa.n = CTX->ee_pkey_data;
        CTX->pkey.key.rsa.nlen = nlen;
        CTX->pkey.key.rsa.e = CTX->ee_pkey_data + nlen;
        CTX->pkey.key.rsa.elen = elen;
}

\ Copy the EE public key to the permanent buffer (EC).
cc: copy-ee-ec-pkey ( curve qlen -- ) {
        size_t qlen = T0_POP();
        uint32_t curve = T0_POP();
        memcpy(CTX->ee_pkey_data, CTX->pkey_data, qlen);
        CTX->pkey.key_type = BR_KEYTYPE_EC;
        CTX->pkey.key.ec.curve = curve;
        CTX->pkey.key.ec.q = CTX->ee_pkey_data;
        CTX->pkey.key.ec.qlen = qlen;
}

\ Check whether the current certificate (EE) is directly trusted.
cc: check-direct-trust ( -- ) {
        size_t u;

        for (u = 0; u < CTX->trust_anchors_num; u ++) {
                const br_x509_trust_anchor *ta;
                unsigned char hashed_DN[64];
                int kt;

                ta = &CTX->trust_anchors[u];
                if (ta->flags & BR_X509_TA_CA) {
                        continue;
                }
                hash_dn(CTX, ta->dn.data, ta->dn.len, hashed_DN);
                if (memcmp(hashed_DN, CTX->current_dn_hash, DNHASH_LEN)) {
                        continue;
                }
                kt = CTX->pkey.key_type;
                if ((ta->pkey.key_type & 0x0F) != kt) {
                        continue;
                }
                switch (kt) {

                case BR_KEYTYPE_RSA:
                        if (!eqbigint(CTX->pkey.key.rsa.n,
                                CTX->pkey.key.rsa.nlen,
                                ta->pkey.key.rsa.n,
                                ta->pkey.key.rsa.nlen)
                                || !eqbigint(CTX->pkey.key.rsa.e,
                                CTX->pkey.key.rsa.elen,
                                ta->pkey.key.rsa.e,
                                ta->pkey.key.rsa.elen))
                        {
                                continue;
                        }
                        break;

                case BR_KEYTYPE_EC:
                        if (CTX->pkey.key.ec.curve != ta->pkey.key.ec.curve
                                || CTX->pkey.key.ec.qlen != ta->pkey.key.ec.qlen
                                || memcmp(CTX->pkey.key.ec.q,
                                        ta->pkey.key.ec.q,
                                        ta->pkey.key.ec.qlen) != 0)
                        {
                                continue;
                        }
                        break;

                default:
                        continue;
                }

                /*
                 * Direct trust match!
                 */
                CTX->err = BR_ERR_X509_OK;
                T0_CO();
        }
}

\ Check the signature on the certificate with regards to all trusted CA.
\ We use the issuer hash (in saved_dn_hash[]) as CA identifier.
cc: check-trust-anchor-CA ( -- ) {
        size_t u;

        for (u = 0; u < CTX->trust_anchors_num; u ++) {
                const br_x509_trust_anchor *ta;
                unsigned char hashed_DN[64];

                ta = &CTX->trust_anchors[u];
                if (!(ta->flags & BR_X509_TA_CA)) {
                        continue;
                }
                hash_dn(CTX, ta->dn.data, ta->dn.len, hashed_DN);
                if (memcmp(hashed_DN, CTX->saved_dn_hash, DNHASH_LEN)) {
                        continue;
                }
                if (verify_signature(CTX, &ta->pkey) == 0) {
                        CTX->err = BR_ERR_X509_OK;
                        T0_CO();
                }
        }
}

\ Verify RSA signature. This uses the public key that was just decoded
\ into CTX->pkey_data; the modulus and exponent length are provided as
\ parameters. The resulting hash value is compared with the one in
\ tbs_hash. Returned value is 0 on success, or a non-zero error code.
cc: do-rsa-vrfy ( nlen elen -- err ) {
        size_t elen = T0_POP();
        size_t nlen = T0_POP();
        br_x509_pkey pk;

        pk.key_type = BR_KEYTYPE_RSA;
        pk.key.rsa.n = CTX->pkey_data;
        pk.key.rsa.nlen = nlen;
        pk.key.rsa.e = CTX->pkey_data + nlen;
        pk.key.rsa.elen = elen;
        T0_PUSH(verify_signature(CTX, &pk));
}

\ Verify ECDSA signature. This uses the public key that was just decoded
\ into CTX->pkey_dayta; the curve ID and public point length are provided
\ as parameters. The hash value in tbs_hash is used. Returned value is 0
\ on success, or non-zero error code.
cc: do-ecdsa-vrfy ( curve qlen -- err ) {
        size_t qlen = T0_POP();
        int curve = T0_POP();
        br_x509_pkey pk;

        pk.key_type = BR_KEYTYPE_EC;
        pk.key.ec.curve = curve;
        pk.key.ec.q = CTX->pkey_data;
        pk.key.ec.qlen = qlen;
        T0_PUSH(verify_signature(CTX, &pk));
}

cc: print-bytes ( addr len -- ) {
        extern int printf(const char *fmt, ...);
        size_t len = T0_POP();
        unsigned char *buf = (unsigned char *)CTX + T0_POP();
        size_t u;

        for (u = 0; u < len; u ++) {
                printf("%02X", buf[u]);
        }
}

cc: printOID ( -- ) {
        extern int printf(const char *fmt, ...);
        size_t u, len;

        len = CTX->pad[0];
        if (len == 0) {
                printf("*");
                T0_RET();
        }
        printf("%u.%u", CTX->pad[1] / 40, CTX->pad[1] % 40);
        u = 2;
        while (u <= len) {
                unsigned long ul;

                ul = 0;
                for (;;) {
                        int x;

                        if (u > len) {
                                printf("BAD");
                                T0_RET();
                        }
                        x = CTX->pad[u ++];
                        ul = (ul << 7) + (x & 0x7F);
                        if (!(x & 0x80)) {
                                break;
                        }
                }
                printf(".%lu", ul);
        }
}

\ Extensions with specific processing.
OID: basicConstraints    2.5.29.19
OID: keyUsage            2.5.29.15
OID: subjectAltName      2.5.29.17

\ Extensions which are ignored when encountered, even if critical.
OID: authorityKeyIdentifier        2.5.29.35
OID: subjectKeyIdentifier          2.5.29.14
OID: issuerAltName                 2.5.29.18
OID: subjectDirectoryAttributes    2.5.29.9
OID: crlDistributionPoints         2.5.29.31
OID: freshestCRL                   2.5.29.46
OID: authorityInfoAccess           1.3.6.1.5.5.7.1.1
OID: subjectInfoAccess             1.3.6.1.5.5.7.1.11

\ Process a Basic Constraints extension. This should be called only if
\ the certificate is not the EE. We check that the extension contains
\ the "CA" flag, and that the path length, if specified, is compatible
\ with the current chain length.
: process-basicConstraints ( lim -- lim )
        read-sequence-open
        read-tag-or-end
        dup 0x01 = if
                read-boolean ifnot ERR_X509_NOT_CA fail then
                read-tag-or-end
        else
                ERR_X509_NOT_CA fail
        then
        dup 0x02 = if
                drop check-primitive read-small-int-value
                addr-num_certs get32 1- < if ERR_X509_NOT_CA fail then
                read-tag-or-end
        then
        -1 <> if ERR_X509_UNEXPECTED fail then
        drop
        close-elt
        ;

\ Process a Key Usage extension.
\ For the EE certificate:
\   -- if the key usage contains keyEncipherment (2), dataEncipherment (3)
\      or keyAgreement (4), then the "key exchange" usage is allowed;
\   -- if the key usage contains digitalSignature (0) or nonRepudiation (1),
\      then the "signature" usage is allowed.
\ For CA certificates, the extension must contain keyCertSign (5).
: process-keyUsage ( lim ee -- lim )
        { ee }

        \ Read tag for the BIT STRING and open it.
        read-tag 0x03 check-tag-primitive
        read-length-open-elt
        \ First byte indicates number of ignored bits in the last byte. It
        \ must be between 0 and 7.
        read8 { ign }
        ign 7 > if ERR_X509_UNEXPECTED fail then
        \ Depending on length, we have either 0, 1 or more bytes to read.
        dup case
                0 of ERR_X509_FORBIDDEN_KEY_USAGE fail endof
                1 of read8 ign >> ign << endof
                drop read8 0
        endcase

        \ Check bits.
        ee if
                \ EE: get usages.
                0
                over 0x38 and if 0x10 or then
                swap 0xC0 and if 0x20 or then
                addr-key_usages set8
        else
                \ Not EE: keyCertSign must be set.
                0x04 and ifnot ERR_X509_FORBIDDEN_KEY_USAGE fail then
        then

        \ We don't care about subsequent bytes.
        skip-close-elt ;

\ Process a Subject Alt Name extension. Returned value is a boolean set
\ to true if the expected server name was matched against a dNSName in
\ the extension.
: process-SAN ( lim -- lim bool )
        0 { m }
        read-sequence-open
        begin dup while
                \ Read the tag. If the tag is context-0, then parse an
                \ 'otherName'. If the tag is context-2, then parse a
                \ dNSName. If the tag is context-1 or context-6,
                \ parse 
                read-tag case
                        \ OtherName
                        0x20 of
                                \ OtherName ::= SEQUENCE {
                                \     type-id   OBJECT IDENTIFIER,
                                \     value     [0] EXPLICIT ANY
                                \ }
                                check-constructed read-length-open-elt
                                read-OID drop
                                -1 offset-name-element { offbuf }
                                read-tag 0x20 check-tag-constructed
                                read-length-open-elt
                                read-string offbuf copy-name-element
                                close-elt
                                close-elt
                        endof
                        \ rfc822Name (IA5String)
                        0x21 of
                                check-primitive
                                read-value-UTF8 1 copy-name-SAN
                        endof
                        \ dNSName (IA5String)
                        0x22 of
                                check-primitive
                                read-value-UTF8
                                dup if match-server-name m or >m then
                                2 copy-name-SAN
                        endof
                        \ uniformResourceIdentifier (IA5String)
                        0x26 of
                                check-primitive
                                read-value-UTF8 6 copy-name-SAN
                        endof
                        2drop read-length-skip 0
                endcase

                \ We check only names of type dNSName; they use IA5String,
                \ which is basically ASCII.
                \ read-tag 0x22 = if
                \       check-primitive
                \       read-small-value drop
                \       match-server-name m or >m
                \ else
                \       drop read-length-skip
                \ then
        repeat
        close-elt
        m ;

\ Decode a certificate. The "ee" boolean must be true for the EE.
: decode-certificate ( ee -- )
        { ee }

        \ Obtain the total certificate length.
        addr-cert_length get32

        \ Open the outer SEQUENCE.
        read-sequence-open

        \ TBS
        \ Activate hashing.
        start-tbs-hash
        read-sequence-open

        \ First element may be an explicit version. We accept only
        \ versions 0 to 2 (certificates v1 to v3).
        read-tag dup 0x20 = if
                drop check-constructed read-length-open-elt
                read-tag
                0x02 check-tag-primitive
                read-small-int-value
                2 > if ERR_X509_UNSUPPORTED fail then
                close-elt
                read-tag
        then

        \ Serial number. We just check that the tag is correct.
        0x02 check-tag-primitive
        read-length-skip

        \ Signature algorithm. This structure is redundant with the one
        \ on the outside; we just skip it.
        read-sequence-open skip-close-elt

        \ Issuer name: hashed, then copied into next_dn_hash[].
        read-DN
        addr-next_dn_hash addr-current_dn_hash dn-hash-length blobcopy

        \ Validity dates.
        read-sequence-open
        read-date get-system-date after if ERR_X509_EXPIRED fail then
        read-date get-system-date before if ERR_X509_EXPIRED fail then
        close-elt

        \ Subject name.
        ee if
                \ For the EE, we must check whether the Common Name, if
                \ any, matches the expected server name.
                read-DN-EE { eename }
        else
                \ For a non-EE certificate, the hashed subject DN must match
                \ the saved hashed issuer DN from the previous certificate.
                read-DN
                addr-current_dn_hash addr-saved_dn_hash dn-hash-length eqblob
                ifnot ERR_X509_DN_MISMATCH fail then
        then
        \ Move the hashed issuer DN for this certificate into the
        \ saved_dn_hash[] array.
        addr-saved_dn_hash addr-next_dn_hash dn-hash-length blobcopy

        \ Public Key.
        read-sequence-open
        \ Algorithm Identifier. Right now we are only interested in the
        \ OID, since we only support RSA keys.
        read-sequence-open
        read-OID ifnot ERR_X509_UNSUPPORTED fail then
        { ; pkey-type }
        choice
                \ RSA public key.
                rsaEncryption eqOID uf
                        skip-close-elt
                        \ Public key itself: the BIT STRING contains bytes
                        \ (no partial byte) and these bytes encode the
                        \ actual value.
                        read-bits-open
                                \ RSA public key is a SEQUENCE of two
                                \ INTEGER. We get both INTEGER values into
                                \ the pkey_data[] buffer, if they fit.
                                read-sequence-open
                                addr-len-pkey_data
                                read-integer { nlen }
                                addr-len-pkey_data swap nlen + swap nlen -
                                read-integer { elen }
                                close-elt

                                \ Check that the public key fits our minimal
                                \ size requirements. Note that the integer
                                \ decoder already skipped the leading bytes
                                \ of value 0, so we are working on the true
                                \ modulus length here.
                                addr-min_rsa_size get16 128 + nlen > if
                                        ERR_X509_WEAK_PUBLIC_KEY fail
                                then
                        close-elt
                        KEYTYPE_RSA >pkey-type
                enduf

                \ EC public key.
                id-ecPublicKey eqOID uf
                        \ We support only named curves, for which the
                        \ "parameters" field in the AlgorithmIdentifier
                        \ field should be an OID.
                        read-OID ifnot ERR_X509_UNSUPPORTED fail then
                        choice
                                ansix9p256r1 eqOID uf 23 enduf
                                ansix9p384r1 eqOID uf 24 enduf
                                ansix9p521r1 eqOID uf 25 enduf
                                ERR_X509_UNSUPPORTED fail
                        endchoice
                        { curve }
                        close-elt
                        read-bits-open
                        dup { qlen }
                        dup addr-len-pkey_data rot < if
                                ERR_X509_LIMIT_EXCEEDED fail
                        then
                        read-blob
                        KEYTYPE_EC >pkey-type
                enduf

                \ Not a recognised public key type.
                ERR_X509_UNSUPPORTED fail
        endchoice
        close-elt

        \ Process public key.
        ee if
                \ For the EE certificate, copy the key data to the
                \ relevant buffer.
                pkey-type case
                        KEYTYPE_RSA of nlen elen copy-ee-rsa-pkey endof
                        KEYTYPE_EC of curve qlen copy-ee-ec-pkey endof
                        ERR_X509_UNSUPPORTED fail
                endcase
        else
                \ Verify signature on previous certificate. We invoke
                \ the RSA implementation.
                pkey-type case
                        KEYTYPE_RSA of nlen elen do-rsa-vrfy endof
                        KEYTYPE_EC of curve qlen do-ecdsa-vrfy endof
                        ERR_X509_UNSUPPORTED fail
                endcase
                dup if fail then
                drop
        then

        \ This flag will be set to true if the Basic Constraints extension
        \ is encountered.
        0 { seenBC }

        \ Skip issuerUniqueID and subjectUniqueID, and process extensions
        \ if present. Extensions are an explicit context tag of value 3
        \ around a SEQUENCE OF extensions. Each extension is a SEQUENCE
        \ with an OID, an optional boolean, and a value; the value is
        \ an OCTET STRING.
        read-tag-or-end
        0x21 iftag-skip
        0x22 iftag-skip
        dup 0x23 = if
                drop
                check-constructed read-length-open-elt
                read-sequence-open
                begin dup while
                        0 { critical }
                        read-sequence-open
                        read-OID drop
                        read-tag dup 0x01 = if
                                read-boolean >critical
                                read-tag
                        then
                        0x04 check-tag-primitive read-length-open-elt
                        choice
                                \ Extensions with specific processing.
                                basicConstraints eqOID uf
                                        ee if
                                                skip-remaining
                                        else
                                                process-basicConstraints
                                                -1 >seenBC
                                        then
                                enduf
                                keyUsage         eqOID uf
                                        ee process-keyUsage
                                enduf
                                subjectAltName   eqOID uf
                                        ee if
                                                0 >eename
                                                process-SAN >eename
                                        else
                                                skip-remaining
                                        then
                                enduf

                                \ Extensions which are always ignored,
                                \ even if critical.
                                authorityKeyIdentifier     eqOID uf
                                        skip-remaining
                                enduf
                                subjectKeyIdentifier       eqOID uf
                                        skip-remaining
                                enduf
                                issuerAltName              eqOID uf
                                        skip-remaining
                                enduf
                                subjectDirectoryAttributes eqOID uf
                                        skip-remaining
                                enduf
                                crlDistributionPoints      eqOID uf
                                        skip-remaining
                                enduf
                                freshestCRL                eqOID uf
                                        skip-remaining
                                enduf
                                authorityInfoAccess        eqOID uf
                                        skip-remaining
                                enduf
                                subjectInfoAccess          eqOID uf
                                        skip-remaining
                                enduf

                                \ Unrecognized extensions trigger a failure
                                \ if critical; otherwise, they are just
                                \ ignored.
                                critical if
                                        ERR_X509_CRITICAL_EXTENSION fail
                                then
                                skip-remaining
                        endchoice
                        close-elt
                        close-elt
                repeat
                close-elt
                close-elt
        else
                -1 = ifnot ERR_X509_UNEXPECTED fail then
                drop
        then

        close-elt
        \ Terminate hashing.
        stop-tbs-hash

        \ For the EE certificate, verify that the intended server name
        \ was matched.
        ee if
                eename zero-server-name or ifnot
                        ERR_X509_BAD_SERVER_NAME fail
                then
        then

        \ If this is the EE certificate, then direct trust may apply.
        \ Note: we do this at this point, not immediately after decoding
        \ the public key, because even in case of direct trust we still
        \ want to check the server name with regards to the SAN extension.
        \ However, we want to check direct trust before trying to decode
        \ the signature algorithm, because it should work even if that
        \ algorithm is not supported.
        ee if check-direct-trust then

        \ Non-EE certificates MUST have a Basic Constraints extension
        \ (that marks them as being CA).
        ee seenBC or ifnot ERR_X509_NOT_CA fail then

        \ signature algorithm
        read-tag check-sequence read-length-open-elt
        \ Read and understand the OID. Right now, we support only
        \ RSA with PKCS#1 v1.5 padding, and hash functions SHA-1,
        \ SHA-224, SHA-256, SHA-384 and SHA-512. We purposely do NOT
        \ support MD5 here.
        \ TODO: add support for RSA/PSS
        read-OID if
                \ Based on the signature OID, we get:
                \ -- the signing key type
                \ -- the hash function numeric identifier
                \ -- the hash function OID
                choice
                        sha1WithRSAEncryption   eqOID
                                uf 2 KEYTYPE_RSA id-sha1   enduf
                        sha224WithRSAEncryption eqOID
                                uf 3 KEYTYPE_RSA id-sha224 enduf
                        sha256WithRSAEncryption eqOID
                                uf 4 KEYTYPE_RSA id-sha256 enduf
                        sha384WithRSAEncryption eqOID
                                uf 5 KEYTYPE_RSA id-sha384 enduf
                        sha512WithRSAEncryption eqOID
                                uf 6 KEYTYPE_RSA id-sha512 enduf

                        ecdsa-with-SHA1   eqOID
                                uf 2 KEYTYPE_EC id-sha1 enduf
                        ecdsa-with-SHA224 eqOID
                                uf 3 KEYTYPE_EC id-sha224 enduf
                        ecdsa-with-SHA256 eqOID
                                uf 4 KEYTYPE_EC id-sha256 enduf
                        ecdsa-with-SHA384 eqOID
                                uf 5 KEYTYPE_EC id-sha384 enduf
                        ecdsa-with-SHA512 eqOID
                                uf 6 KEYTYPE_EC id-sha512 enduf
                        ERR_X509_UNSUPPORTED fail
                endchoice
                addr-cert_sig_hash_oid set16
                addr-cert_signer_key_type set8

                \ Compute the TBS hash into tbs_hash.
                compute-tbs-hash
                dup ifnot ERR_X509_UNSUPPORTED fail then
                addr-cert_sig_hash_len set8
        else
                ERR_X509_UNSUPPORTED fail
        then
        \ We ignore the parameters, whether they are present or not,
        \ because we got all the information from the OID.
        skip-close-elt

        \ signature value
        read-bits-open
        dup CX 0 8191 { BR_X509_BUFSIZE_SIG } > if
                ERR_X509_LIMIT_EXCEEDED fail
        then
        dup addr-cert_sig_len set16
        addr-cert_sig read-blob

        \ Close the outer SEQUENCE.
        close-elt

        \ Close the advertised total certificate length. This checks that
        \ there is no trailing garbage after the certificate.
        close-elt

        \ Flag the certificate as fully processed.
        0 addr-cert_length set32

        \ Check whether the issuer for the current certificate is known
        \ as a trusted CA; in which case, verify the signature.
        check-trust-anchor-CA ;

: main
        \ Unless restricted by a Key Usage extension, all usages are
        \ deemed allowed.
        0x30 addr-key_usages set8
        -1 decode-certificate
        co
        begin
                0 decode-certificate co
        again
        ;