+static int build_chain(X509_STORE_CTX *ctx)
+{
+ int (*cb) (int, X509_STORE_CTX *) = ctx->verify_cb;
+ int num = sk_X509_num(ctx->chain);
+ X509 *cert = sk_X509_value(ctx->chain, num - 1);
+ int ss = cert_self_signed(cert);
+ STACK_OF(X509) *sktmp = NULL;
+ unsigned int search;
+ int may_trusted = 1;
+ int may_alternate = 0;
+ int trust = X509_TRUST_UNTRUSTED;
+ int alt_untrusted = 0;
+ int depth;
+ int ok = 0;
+ int i;
+
+ /* Our chain starts with a single untrusted element. */
+ OPENSSL_assert(num == 1 && ctx->num_untrusted == num);
+
+#define S_DOUNTRUSTED (1 << 0) /* Search untrusted chain */
+#define S_DOTRUSTED (1 << 1) /* Search trusted store */
+#define S_DOALTERNATE (1 << 2) /* Retry with pruned alternate chain */
+ /*
+ * Set up search policy, untrusted if possible, trusted-first if enabled.
+ * If not trusted-first, and alternate chains are not disabled, try
+ * building an alternate chain if no luck with untrusted first.
+ */
+ search = (ctx->untrusted != NULL) ? S_DOUNTRUSTED : 0;
+ if (search == 0 || ctx->param->flags & X509_V_FLAG_TRUSTED_FIRST)
+ search |= S_DOTRUSTED;
+ else if (!(ctx->param->flags & X509_V_FLAG_NO_ALT_CHAINS))
+ may_alternate = 1;
+
+ /*
+ * Shallow-copy the stack of untrusted certificates (with TLS, this is
+ * typically the content of the peer's certificate message) so can make
+ * multiple passes over it, while free to remove elements as we go.
+ */
+ if (ctx->untrusted && (sktmp = sk_X509_dup(ctx->untrusted)) == NULL) {
+ X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
+ return 0;
+ }
+
+ /*
+ * Still absurdly large, but arithmetically safe, a lower hard upper bound
+ * might be reasonable.
+ */
+ if (ctx->param->depth > INT_MAX/2)
+ ctx->param->depth = INT_MAX/2;
+
+ /*
+ * Try to Extend the chain until we reach an ultimately trusted issuer.
+ * Build chains up to one longer the limit, later fail if we hit the limit,
+ * with an X509_V_ERR_CERT_CHAIN_TOO_LONG error code.
+ */
+ depth = ctx->param->depth + 1;
+
+ while (search != 0) {
+ X509 *x;
+ X509 *xtmp = NULL;
+
+ /*
+ * Look in the trust store if enabled for first lookup, or we've run
+ * out of untrusted issuers and search here is not disabled. When
+ * we exceed the depth limit, we simulate absence of a match.
+ */
+ if ((search & S_DOTRUSTED) != 0) {
+ STACK_OF(X509) *hide = ctx->chain;
+
+ i = num = sk_X509_num(ctx->chain);
+ if ((search & S_DOALTERNATE) != 0) {
+ /*
+ * As high up the chain as we can, look for an alternative
+ * trusted issuer of an untrusted certificate that currently
+ * has an untrusted issuer. We use the alt_untrusted variable
+ * to track how far up the chain we find the first match. It
+ * is only if and when we find a match, that we prune the chain
+ * and reset ctx->num_untrusted to the reduced count of
+ * untrusted certificates. While we're searching for such a
+ * match (which may never be found), it is neither safe nor
+ * wise to preemptively modify either the chain or
+ * ctx->num_untrusted.
+ *
+ * Note, like ctx->num_untrusted, alt_untrusted is a count of
+ * untrusted certificates, not a "depth".
+ */
+ i = alt_untrusted;
+ }
+ x = sk_X509_value(ctx->chain, i-1);
+
+ /* Suppress duplicate suppression */
+ ctx->chain = NULL;
+ ok = (depth < num) ? 0 : ctx->get_issuer(&xtmp, ctx, x);
+ ctx->chain = hide;
+
+ if (ok < 0) {
+ trust = X509_TRUST_REJECTED;
+ search = 0;
+ continue;
+ }
+
+ if (ok > 0) {
+ /*
+ * Alternative trusted issuer for a mid-chain untrusted cert?
+ * Pop the untrusted cert's successors and retry. We might now
+ * be able to complete a valid chain via the trust store. Note
+ * that despite the current trust-store match we might still
+ * fail complete the chain to a suitable trust-anchor, in which
+ * case we may prune some more untrusted certificates and try
+ * again. Thus the S_DOALTERNATE bit may yet be turned on
+ * again with an even shorter untrusted chain!
+ */
+ if ((search & S_DOALTERNATE) != 0) {
+ OPENSSL_assert(num > i && i > 0 && ss == 0);
+ search &= ~S_DOALTERNATE;
+ for (; num > i; --num)
+ X509_free(sk_X509_pop(ctx->chain));
+ ctx->num_untrusted = num;
+ }
+
+ /*
+ * Self-signed untrusted certificates get replaced by their
+ * trusted matching issuer. Otherwise, grow the chain.
+ */
+ if (ss == 0) {
+ if (!sk_X509_push(ctx->chain, x = xtmp)) {
+ X509_free(xtmp);
+ X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
+ trust = X509_TRUST_REJECTED;
+ search = 0;
+ continue;
+ }
+ ss = cert_self_signed(x);
+ } else if (num == ctx->num_untrusted) {
+ /*
+ * We have a self-signed certificate that has the same
+ * subject name (and perhaps keyid and/or serial number) as
+ * a trust-anchor. We must have an exact match to avoid
+ * possible impersonation via key substitution etc.
+ */
+ if (X509_cmp(x, xtmp) != 0) {
+ /* Self-signed untrusted mimic. */
+ X509_free(xtmp);
+ ok = 0;
+ } else {
+ X509_free(x);
+ ctx->num_untrusted = --num;
+ (void) sk_X509_set(ctx->chain, num, x = xtmp);
+ }
+ }
+
+ /*
+ * We've added a new trusted certificate to the chain, recheck
+ * trust. If not done, and not self-signed look deeper.
+ * Whether or not we're doing "trusted first", we no longer
+ * look for untrusted certificates from the peer's chain.
+ */
+ if (ok) {
+ OPENSSL_assert(ctx->num_untrusted <= num);
+ search &= ~S_DOUNTRUSTED;
+ switch (trust = check_trust(ctx, num)) {
+ case X509_TRUST_TRUSTED:
+ case X509_TRUST_REJECTED:
+ search = 0;
+ continue;
+ }
+ if (ss == 0)
+ continue;
+ }
+ }
+
+ /*
+ * No dispositive decision, and either self-signed or no match, if
+ * we were doing untrusted-first, and alt-chains are not disabled,
+ * do that, by repeatedly losing one untrusted element at a time,
+ * and trying to extend the shorted chain.
+ */
+ if ((search & S_DOUNTRUSTED) == 0) {
+ /* Continue search for a trusted issuer of a shorter chain? */
+ if ((search & S_DOALTERNATE) != 0 && --alt_untrusted > 0)
+ continue;
+ /* Still no luck and no fallbacks left? */
+ if (!may_alternate || (search & S_DOALTERNATE) != 0 ||
+ ctx->num_untrusted < 2)
+ break;
+ /* Search for a trusted issuer of a shorter chain */
+ search |= S_DOALTERNATE;
+ alt_untrusted = ctx->num_untrusted - 1;
+ ss = 0;
+ }
+ }
+
+ /*
+ * Extend chain with peer-provided certificates
+ */
+ if ((search & S_DOUNTRUSTED) != 0) {
+ num = sk_X509_num(ctx->chain);
+ OPENSSL_assert(num == ctx->num_untrusted);
+ x = sk_X509_value(ctx->chain, num-1);
+ xtmp = (depth < num) ? NULL : find_issuer(ctx, sktmp, x);
+
+ /*
+ * Once we run out of untrusted issuers, we stop looking for more
+ * and start looking only in the trust store if enabled.
+ */
+ if (xtmp == NULL) {
+ search &= ~S_DOUNTRUSTED;
+ if (may_trusted)
+ search |= S_DOTRUSTED;
+ continue;
+ }
+
+ if (!sk_X509_push(ctx->chain, x = xtmp)) {
+ X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
+ trust = X509_TRUST_REJECTED;
+ search = 0;
+ continue;
+ }
+ X509_up_ref(x);
+ ++ctx->num_untrusted;
+ ss = cert_self_signed(xtmp);
+
+ /*
+ * Not strictly necessary, but saves cycles looking at the same
+ * certificates over and over.
+ */
+ (void) sk_X509_delete_ptr(sktmp, x);
+ }
+ }
+ sk_X509_free(sktmp);
+
+ /*
+ * Last chance to make a trusted chain, check for direct leaf PKIX trust.
+ */
+ if (sk_X509_num(ctx->chain) <= depth) {
+ if (trust == X509_TRUST_UNTRUSTED &&
+ sk_X509_num(ctx->chain) == ctx->num_untrusted)
+ trust = check_trust(ctx, 1);
+ }
+
+ switch (trust) {
+ case X509_TRUST_TRUSTED:
+ return 1;
+ case X509_TRUST_REJECTED:
+ return 0;
+ case X509_TRUST_UNTRUSTED:
+ default:
+ num = sk_X509_num(ctx->chain);
+ ctx->current_cert = sk_X509_value(ctx->chain, num - 1);
+ ctx->error_depth = num-1;
+ if (num > depth)
+ ctx->error = X509_V_ERR_CERT_CHAIN_TOO_LONG;
+ else if (ss && sk_X509_num(ctx->chain) == 1)
+ ctx->error = X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT;
+ else if (ss)
+ ctx->error = X509_V_ERR_SELF_SIGNED_CERT_IN_CHAIN;
+ else if (ctx->num_untrusted == num)
+ ctx->error = X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT_LOCALLY;
+ else
+ ctx->error = X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT;
+ return cb(0, ctx);
+ }
+}