Return to sshsig.c CVS log

Up to [local] / src / usr.bin / ssh

support for user-verified FIDO keys

FIDO2 supports a notion of "user verification" where the user is
required to demonstrate their identity to the token before particular
operations (e.g. signing). Typically this is done by authenticating
themselves using a PIN that has been set on the token.

This adds support for generating and using user verified keys where
the verification happens via PIN (other options might be added in the
future, but none are in common use now). Practically, this adds
another key generation option "verify-required" that yields a key that
requires a PIN before each authentication.

feedback markus@ and Pedro Martelletto; ok markus@

/*
 * Copyright (c) 2019 Google LLC
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <errno.h>
#include <string.h>
#include <unistd.h>

#include "authfd.h"
#include "authfile.h"
#include "log.h"
#include "misc.h"
#include "sshbuf.h"
#include "sshsig.h"
#include "ssherr.h"
#include "sshkey.h"
#include "match.h"
#include "digest.h"

#define SIG_VERSION		0x01
#define MAGIC_PREAMBLE		"SSHSIG"
#define MAGIC_PREAMBLE_LEN	(sizeof(MAGIC_PREAMBLE) - 1)
#define BEGIN_SIGNATURE		"-----BEGIN SSH SIGNATURE-----\n"
#define END_SIGNATURE		"-----END SSH SIGNATURE-----"
#define RSA_SIGN_ALG		"rsa-sha2-512" /* XXX maybe make configurable */
#define RSA_SIGN_ALLOWED	"rsa-sha2-512,rsa-sha2-256"
#define HASHALG_DEFAULT		"sha512" /* XXX maybe make configurable */
#define HASHALG_ALLOWED		"sha256,sha512"

int
sshsig_armor(const struct sshbuf *blob, struct sshbuf **out)
{
	struct sshbuf *buf = NULL;
	int r = SSH_ERR_INTERNAL_ERROR;

	*out = NULL;

	if ((buf = sshbuf_new()) == NULL) {
		error("%s: sshbuf_new failed", __func__);
		r = SSH_ERR_ALLOC_FAIL;
		goto out;
	}

	if ((r = sshbuf_put(buf, BEGIN_SIGNATURE,
	    sizeof(BEGIN_SIGNATURE)-1)) != 0) {
		error("%s: sshbuf_putf failed: %s", __func__, ssh_err(r));
		goto out;
	}

	if ((r = sshbuf_dtob64(blob, buf, 1)) != 0) {
		error("%s: Couldn't base64 encode signature blob: %s",
		    __func__, ssh_err(r));
		goto out;
	}

	if ((r = sshbuf_put(buf, END_SIGNATURE,
	    sizeof(END_SIGNATURE)-1)) != 0 ||
	    (r = sshbuf_put_u8(buf, '\n')) != 0) {
		error("%s: sshbuf_put failed: %s", __func__, ssh_err(r));
		goto out;
	}
	/* success */
	*out = buf;
	buf = NULL; /* transferred */
	r = 0;
 out:
	sshbuf_free(buf);
	return r;
}

int
sshsig_dearmor(struct sshbuf *sig, struct sshbuf **out)
{
	int r;
	size_t eoffset = 0;
	struct sshbuf *buf = NULL;
	struct sshbuf *sbuf = NULL;
	char *b64 = NULL;

	if ((sbuf = sshbuf_fromb(sig)) == NULL) {
		error("%s: sshbuf_fromb failed", __func__);
		return SSH_ERR_ALLOC_FAIL;
	}

	if ((r = sshbuf_cmp(sbuf, 0,
	    BEGIN_SIGNATURE, sizeof(BEGIN_SIGNATURE)-1)) != 0) {
		error("Couldn't parse signature: missing header");
		goto done;
	}

	if ((r = sshbuf_consume(sbuf, sizeof(BEGIN_SIGNATURE)-1)) != 0) {
		error("%s: sshbuf_consume failed: %s", __func__, ssh_err(r));
		goto done;
	}

	if ((r = sshbuf_find(sbuf, 0, "\n" END_SIGNATURE,
	    sizeof("\n" END_SIGNATURE)-1, &eoffset)) != 0) {
		error("Couldn't parse signature: missing footer");
		goto done;
	}

	if ((r = sshbuf_consume_end(sbuf, sshbuf_len(sbuf)-eoffset)) != 0) {
		error("%s: sshbuf_consume failed: %s", __func__, ssh_err(r));
		goto done;
	}

	if ((b64 = sshbuf_dup_string(sbuf)) == NULL) {
		error("%s: sshbuf_dup_string failed", __func__);
		r = SSH_ERR_ALLOC_FAIL;
		goto done;
	}

	if ((buf = sshbuf_new()) == NULL) {
		error("%s: sshbuf_new() failed", __func__);
		r = SSH_ERR_ALLOC_FAIL;
		goto done;
	}

	if ((r = sshbuf_b64tod(buf, b64)) != 0) {
		error("Couldn't decode signature: %s", ssh_err(r));
		goto done;
	}

	/* success */
	*out = buf;
	r = 0;
	buf = NULL; /* transferred */
done:
	sshbuf_free(buf);
	sshbuf_free(sbuf);
	free(b64);
	return r;
}

static int
sshsig_wrap_sign(struct sshkey *key, const char *hashalg,
    const char *sk_provider, const char *sk_pin, const struct sshbuf *h_message,
    const char *sig_namespace, struct sshbuf **out,
    sshsig_signer *signer, void *signer_ctx)
{
	int r;
	size_t slen = 0;
	u_char *sig = NULL;
	struct sshbuf *blob = NULL;
	struct sshbuf *tosign = NULL;
	const char *sign_alg = NULL;

	if ((tosign = sshbuf_new()) == NULL ||
	    (blob = sshbuf_new()) == NULL) {
		error("%s: sshbuf_new failed", __func__);
		r = SSH_ERR_ALLOC_FAIL;
		goto done;
	}

	if ((r = sshbuf_put(tosign, MAGIC_PREAMBLE, MAGIC_PREAMBLE_LEN)) != 0 ||
	    (r = sshbuf_put_cstring(tosign, sig_namespace)) != 0 ||
	    (r = sshbuf_put_string(tosign, NULL, 0)) != 0 || /* reserved */
	    (r = sshbuf_put_cstring(tosign, hashalg)) != 0 ||
	    (r = sshbuf_put_stringb(tosign, h_message)) != 0) {
		error("Couldn't construct message to sign: %s", ssh_err(r));
		goto done;
	}

	/* If using RSA keys then default to a good signature algorithm */
	if (sshkey_type_plain(key->type) == KEY_RSA)
		sign_alg = RSA_SIGN_ALG;

	if (signer != NULL) {
		if ((r = signer(key, &sig, &slen,
		    sshbuf_ptr(tosign), sshbuf_len(tosign),
		    sign_alg, sk_provider, sk_pin, 0, signer_ctx)) != 0) {
			error("Couldn't sign message: %s", ssh_err(r));
			goto done;
		}
	} else {
		if ((r = sshkey_sign(key, &sig, &slen,
		    sshbuf_ptr(tosign), sshbuf_len(tosign),
		    sign_alg, sk_provider, sk_pin, 0)) != 0) {
			error("Couldn't sign message: %s", ssh_err(r));
			goto done;
		}
	}

	if ((r = sshbuf_put(blob, MAGIC_PREAMBLE, MAGIC_PREAMBLE_LEN)) != 0 ||
	    (r = sshbuf_put_u32(blob, SIG_VERSION)) != 0 ||
	    (r = sshkey_puts(key, blob)) != 0 ||
	    (r = sshbuf_put_cstring(blob, sig_namespace)) != 0 ||
	    (r = sshbuf_put_string(blob, NULL, 0)) != 0 || /* reserved */
	    (r = sshbuf_put_cstring(blob, hashalg)) != 0 ||
	    (r = sshbuf_put_string(blob, sig, slen)) != 0) {
		error("Couldn't populate blob: %s", ssh_err(r));
		goto done;
	}

	if (out != NULL) {
		*out = blob;
		blob = NULL;
	}
	r = 0;
done:
	free(sig);
	sshbuf_free(blob);
	sshbuf_free(tosign);
	return r;
}

/* Check preamble and version. */
static int
sshsig_parse_preamble(struct sshbuf *buf)
{
	int r = SSH_ERR_INTERNAL_ERROR;
	uint32_t sversion;

	if ((r = sshbuf_cmp(buf, 0, MAGIC_PREAMBLE, MAGIC_PREAMBLE_LEN)) != 0 ||
	    (r = sshbuf_consume(buf, (sizeof(MAGIC_PREAMBLE)-1))) != 0 ||
	    (r = sshbuf_get_u32(buf, &sversion)) != 0) {
		error("Couldn't verify signature: invalid format");
		return r;
	}

	if (sversion > SIG_VERSION) {
		error("Signature version %lu is larger than supported "
		    "version %u", (unsigned long)sversion, SIG_VERSION);
		return SSH_ERR_INVALID_FORMAT;
	}
	return 0;
}

static int
sshsig_check_hashalg(const char *hashalg)
{
	if (hashalg == NULL ||
	    match_pattern_list(hashalg, HASHALG_ALLOWED, 0) == 1)
		return 0;
	error("%s: unsupported hash algorithm \"%.100s\"", __func__, hashalg);
	return SSH_ERR_SIGN_ALG_UNSUPPORTED;
}

static int
sshsig_peek_hashalg(struct sshbuf *signature, char **hashalgp)
{
	struct sshbuf *buf = NULL;
	char *hashalg = NULL;
	int r = SSH_ERR_INTERNAL_ERROR;

	if (hashalgp != NULL)
		*hashalgp = NULL;
	if ((buf = sshbuf_fromb(signature)) == NULL)
		return SSH_ERR_ALLOC_FAIL;
	if ((r = sshsig_parse_preamble(buf)) != 0)
		goto done;
	if ((r = sshbuf_get_string_direct(buf, NULL, NULL)) != 0 ||
	    (r = sshbuf_get_string_direct(buf, NULL, NULL)) != 0 ||
	    (r = sshbuf_get_string(buf, NULL, NULL)) != 0 ||
	    (r = sshbuf_get_cstring(buf, &hashalg, NULL)) != 0 ||
	    (r = sshbuf_get_string_direct(buf, NULL, NULL)) != 0) {
		error("Couldn't parse signature blob: %s", ssh_err(r));
		goto done;
	}

	/* success */
	r = 0;
	*hashalgp = hashalg;
	hashalg = NULL;
 done:
	free(hashalg);
	sshbuf_free(buf);
	return r;
}

static int
sshsig_wrap_verify(struct sshbuf *signature, const char *hashalg,
    const struct sshbuf *h_message, const char *expect_namespace,
    struct sshkey **sign_keyp, struct sshkey_sig_details **sig_details)
{
	int r = SSH_ERR_INTERNAL_ERROR;
	struct sshbuf *buf = NULL, *toverify = NULL;
	struct sshkey *key = NULL;
	const u_char *sig;
	char *got_namespace = NULL, *sigtype = NULL, *sig_hashalg = NULL;
	size_t siglen;

	debug("%s: verify message length %zu", __func__, sshbuf_len(h_message));
	if (sig_details != NULL)
		*sig_details = NULL;
	if (sign_keyp != NULL)
		*sign_keyp = NULL;

	if ((toverify = sshbuf_new()) == NULL) {
		error("%s: sshbuf_new failed", __func__);
		r = SSH_ERR_ALLOC_FAIL;
		goto done;
	}
	if ((r = sshbuf_put(toverify, MAGIC_PREAMBLE,
	    MAGIC_PREAMBLE_LEN)) != 0 ||
	    (r = sshbuf_put_cstring(toverify, expect_namespace)) != 0 ||
	    (r = sshbuf_put_string(toverify, NULL, 0)) != 0 || /* reserved */
	    (r = sshbuf_put_cstring(toverify, hashalg)) != 0 ||
	    (r = sshbuf_put_stringb(toverify, h_message)) != 0) {
		error("Couldn't construct message to verify: %s", ssh_err(r));
		goto done;
	}

	if ((r = sshsig_parse_preamble(signature)) != 0)
		goto done;

	if ((r = sshkey_froms(signature, &key)) != 0 ||
	    (r = sshbuf_get_cstring(signature, &got_namespace, NULL)) != 0 ||
	    (r = sshbuf_get_string(signature, NULL, NULL)) != 0 ||
	    (r = sshbuf_get_cstring(signature, &sig_hashalg, NULL)) != 0 ||
	    (r = sshbuf_get_string_direct(signature, &sig, &siglen)) != 0) {
		error("Couldn't parse signature blob: %s", ssh_err(r));
		goto done;
	}

	if (sshbuf_len(signature) != 0) {
		error("Signature contains trailing data");
		r = SSH_ERR_INVALID_FORMAT;
		goto done;
	}

	if (strcmp(expect_namespace, got_namespace) != 0) {
		error("Couldn't verify signature: namespace does not match");
		debug("%s: expected namespace \"%s\" received \"%s\"",
		    __func__, expect_namespace, got_namespace);
		r = SSH_ERR_SIGNATURE_INVALID;
		goto done;
	}
	if (strcmp(hashalg, sig_hashalg) != 0) {
		error("Couldn't verify signature: hash algorithm mismatch");
		debug("%s: expected algorithm \"%s\" received \"%s\"",
		    __func__, hashalg, sig_hashalg);
		r = SSH_ERR_SIGNATURE_INVALID;
		goto done;
	}
	/* Ensure that RSA keys use an acceptable signature algorithm */
	if (sshkey_type_plain(key->type) == KEY_RSA) {
		if ((r = sshkey_get_sigtype(sig, siglen, &sigtype)) != 0) {
			error("Couldn't verify signature: unable to get "
			    "signature type: %s", ssh_err(r));
			goto done;
		}
		if (match_pattern_list(sigtype, RSA_SIGN_ALLOWED, 0) != 1) {
			error("Couldn't verify signature: unsupported RSA "
			    "signature algorithm %s", sigtype);
			r = SSH_ERR_SIGN_ALG_UNSUPPORTED;
			goto done;
		}
	}
	if ((r = sshkey_verify(key, sig, siglen, sshbuf_ptr(toverify),
	    sshbuf_len(toverify), NULL, 0, sig_details)) != 0) {
		error("Signature verification failed: %s", ssh_err(r));
		goto done;
	}

	/* success */
	r = 0;
	if (sign_keyp != NULL) {
		*sign_keyp = key;
		key = NULL; /* transferred */
	}
done:
	free(got_namespace);
	free(sigtype);
	free(sig_hashalg);
	sshbuf_free(buf);
	sshbuf_free(toverify);
	sshkey_free(key);
	return r;
}

static int
hash_buffer(const struct sshbuf *m, const char *hashalg, struct sshbuf **bp)
{
	char *hex, hash[SSH_DIGEST_MAX_LENGTH];
	int alg, r = SSH_ERR_INTERNAL_ERROR;
	struct sshbuf *b = NULL;

	*bp = NULL;
	memset(hash, 0, sizeof(hash));

	if ((r = sshsig_check_hashalg(hashalg)) != 0)
		return r;
	if ((alg = ssh_digest_alg_by_name(hashalg)) == -1) {
		error("%s: can't look up hash algorithm %s",
		    __func__, hashalg);
		return SSH_ERR_INTERNAL_ERROR;
	}
	if ((r = ssh_digest_buffer(alg, m, hash, sizeof(hash))) != 0) {
		error("%s: ssh_digest_buffer failed: %s", __func__, ssh_err(r));
		return r;
	}
	if ((hex = tohex(hash, ssh_digest_bytes(alg))) != NULL) {
		debug3("%s: final hash: %s", __func__, hex);
		freezero(hex, strlen(hex));
	}
	if ((b = sshbuf_new()) == NULL) {
		r = SSH_ERR_ALLOC_FAIL;
		goto out;
	}
	if ((r = sshbuf_put(b, hash, ssh_digest_bytes(alg))) != 0) {
		error("%s: sshbuf_put: %s", __func__, ssh_err(r));
		goto out;
	}
	*bp = b;
	b = NULL; /* transferred */
	/* success */
	r = 0;
 out:
	sshbuf_free(b);
	explicit_bzero(hash, sizeof(hash));
	return r;
}

int
sshsig_signb(struct sshkey *key, const char *hashalg,
    const char *sk_provider, const char *sk_pin,
    const struct sshbuf *message, const char *sig_namespace,
    struct sshbuf **out, sshsig_signer *signer, void *signer_ctx)
{
	struct sshbuf *b = NULL;
	int r = SSH_ERR_INTERNAL_ERROR;

	if (hashalg == NULL)
		hashalg = HASHALG_DEFAULT;
	if (out != NULL)
		*out = NULL;
	if ((r = hash_buffer(message, hashalg, &b)) != 0) {
		error("%s: hash_buffer failed: %s", __func__, ssh_err(r));
		goto out;
	}
	if ((r = sshsig_wrap_sign(key, hashalg, sk_provider, sk_pin, b,
	    sig_namespace, out, signer, signer_ctx)) != 0)
		goto out;
	/* success */
	r = 0;
 out:
	sshbuf_free(b);
	return r;
}

int
sshsig_verifyb(struct sshbuf *signature, const struct sshbuf *message,
    const char *expect_namespace, struct sshkey **sign_keyp,
    struct sshkey_sig_details **sig_details)
{
	struct sshbuf *b = NULL;
	int r = SSH_ERR_INTERNAL_ERROR;
	char *hashalg = NULL;

	if (sig_details != NULL)
		*sig_details = NULL;
	if (sign_keyp != NULL)
		*sign_keyp = NULL;
	if ((r = sshsig_peek_hashalg(signature, &hashalg)) != 0)
		return r;
	debug("%s: signature made with hash \"%s\"", __func__, hashalg);
	if ((r = hash_buffer(message, hashalg, &b)) != 0) {
		error("%s: hash_buffer failed: %s", __func__, ssh_err(r));
		goto out;
	}
	if ((r = sshsig_wrap_verify(signature, hashalg, b, expect_namespace,
	    sign_keyp, sig_details)) != 0)
		goto out;
	/* success */
	r = 0;
 out:
	sshbuf_free(b);
	free(hashalg);
	return r;
}

static int
hash_file(int fd, const char *hashalg, struct sshbuf **bp)
{
	char *hex, rbuf[8192], hash[SSH_DIGEST_MAX_LENGTH];
	ssize_t n, total = 0;
	struct ssh_digest_ctx *ctx;
	int alg, oerrno, r = SSH_ERR_INTERNAL_ERROR;
	struct sshbuf *b = NULL;

	*bp = NULL;
	memset(hash, 0, sizeof(hash));

	if ((r = sshsig_check_hashalg(hashalg)) != 0)
		return r;
	if ((alg = ssh_digest_alg_by_name(hashalg)) == -1) {
		error("%s: can't look up hash algorithm %s",
		    __func__, hashalg);
		return SSH_ERR_INTERNAL_ERROR;
	}
	if ((ctx = ssh_digest_start(alg)) == NULL) {
		error("%s: ssh_digest_start failed", __func__);
		return SSH_ERR_INTERNAL_ERROR;
	}
	for (;;) {
		if ((n = read(fd, rbuf, sizeof(rbuf))) == -1) {
			if (errno == EINTR || errno == EAGAIN)
				continue;
			oerrno = errno;
			error("%s: read: %s", __func__, strerror(errno));
			ssh_digest_free(ctx);
			errno = oerrno;
			r = SSH_ERR_SYSTEM_ERROR;
			goto out;
		} else if (n == 0) {
			debug2("%s: hashed %zu bytes", __func__, total);
			break; /* EOF */
		}
		total += (size_t)n;
		if ((r = ssh_digest_update(ctx, rbuf, (size_t)n)) != 0) {
			error("%s: ssh_digest_update: %s",
			    __func__, ssh_err(r));
			goto out;
		}
	}
	if ((r = ssh_digest_final(ctx, hash, sizeof(hash))) != 0) {
		error("%s: ssh_digest_final: %s", __func__, ssh_err(r));
		goto out;
	}
	if ((hex = tohex(hash, ssh_digest_bytes(alg))) != NULL) {
		debug3("%s: final hash: %s", __func__, hex);
		freezero(hex, strlen(hex));
	}
	if ((b = sshbuf_new()) == NULL) {
		r = SSH_ERR_ALLOC_FAIL;
		goto out;
	}
	if ((r = sshbuf_put(b, hash, ssh_digest_bytes(alg))) != 0) {
		error("%s: sshbuf_put: %s", __func__, ssh_err(r));
		goto out;
	}
	*bp = b;
	b = NULL; /* transferred */
	/* success */
	r = 0;
 out:
	sshbuf_free(b);
	ssh_digest_free(ctx);
	explicit_bzero(hash, sizeof(hash));
	return r;
}

int
sshsig_sign_fd(struct sshkey *key, const char *hashalg,
    const char *sk_provider, const char *sk_pin,
    int fd, const char *sig_namespace, struct sshbuf **out,
    sshsig_signer *signer, void *signer_ctx)
{
	struct sshbuf *b = NULL;
	int r = SSH_ERR_INTERNAL_ERROR;

	if (hashalg == NULL)
		hashalg = HASHALG_DEFAULT;
	if (out != NULL)
		*out = NULL;
	if ((r = hash_file(fd, hashalg, &b)) != 0) {
		error("%s: hash_file failed: %s", __func__, ssh_err(r));
		return r;
	}
	if ((r = sshsig_wrap_sign(key, hashalg, sk_provider, sk_pin, b,
	    sig_namespace, out, signer, signer_ctx)) != 0)
		goto out;
	/* success */
	r = 0;
 out:
	sshbuf_free(b);
	return r;
}

int
sshsig_verify_fd(struct sshbuf *signature, int fd,
    const char *expect_namespace, struct sshkey **sign_keyp,
    struct sshkey_sig_details **sig_details)
{
	struct sshbuf *b = NULL;
	int r = SSH_ERR_INTERNAL_ERROR;
	char *hashalg = NULL;

	if (sig_details != NULL)
		*sig_details = NULL;
	if (sign_keyp != NULL)
		*sign_keyp = NULL;
	if ((r = sshsig_peek_hashalg(signature, &hashalg)) != 0)
		return r;
	debug("%s: signature made with hash \"%s\"", __func__, hashalg);
	if ((r = hash_file(fd, hashalg, &b)) != 0) {
		error("%s: hash_file failed: %s", __func__, ssh_err(r));
		goto out;
	}
	if ((r = sshsig_wrap_verify(signature, hashalg, b, expect_namespace,
	    sign_keyp, sig_details)) != 0)
		goto out;
	/* success */
	r = 0;
 out:
	sshbuf_free(b);
	free(hashalg);
	return r;
}

struct sshsigopt {
	int ca;
	char *namespaces;
};

struct sshsigopt *
sshsigopt_parse(const char *opts, const char *path, u_long linenum,
    const char **errstrp)
{
	struct sshsigopt *ret;
	int r;
	const char *errstr = NULL;

	if ((ret = calloc(1, sizeof(*ret))) == NULL)
		return NULL;
	if (opts == NULL || *opts == '\0')
		return ret; /* Empty options yields empty options :) */

	while (*opts && *opts != ' ' && *opts != '\t') {
		/* flag options */
		if ((r = opt_flag("cert-authority", 0, &opts)) != -1) {
			ret->ca = 1;
		} else if (opt_match(&opts, "namespaces")) {
			if (ret->namespaces != NULL) {
				errstr = "multiple \"namespaces\" clauses";
				goto fail;
			}
			ret->namespaces = opt_dequote(&opts, &errstr);
			if (ret->namespaces == NULL)
				goto fail;
		}
		/*
		 * Skip the comma, and move to the next option
		 * (or break out if there are no more).
		 */
		if (*opts == '\0' || *opts == ' ' || *opts == '\t')
			break;		/* End of options. */
		/* Anything other than a comma is an unknown option */
		if (*opts != ',') {
			errstr = "unknown key option";
			goto fail;
		}
		opts++;
		if (*opts == '\0') {
			errstr = "unexpected end-of-options";
			goto fail;
		}
	}
	/* success */
	return ret;
 fail:
	if (errstrp != NULL)
		*errstrp = errstr;
	sshsigopt_free(ret);
	return NULL;
}

void
sshsigopt_free(struct sshsigopt *opts)
{
	if (opts == NULL)
		return;
	free(opts->namespaces);
	free(opts);
}

static int
parse_principals_key_and_options(const char *path, u_long linenum, char *line,
    const char *required_principal, char **principalsp, struct sshkey **keyp,
    struct sshsigopt **sigoptsp)
{
	char *opts = NULL, *tmp, *cp, *principals = NULL;
	const char *reason = NULL;
	struct sshsigopt *sigopts = NULL;
	struct sshkey *key = NULL;
	int r = SSH_ERR_INTERNAL_ERROR;

	if (principalsp != NULL)
		*principalsp = NULL;
	if (sigoptsp != NULL)
		*sigoptsp = NULL;
	if (keyp != NULL)
		*keyp = NULL;

	cp = line;
	cp = cp + strspn(cp, " \t"); /* skip leading whitespace */
	if (*cp == '#' || *cp == '\0')
		return SSH_ERR_KEY_NOT_FOUND; /* blank or all-comment line */

	/* format: identity[,identity...] [option[,option...]] key */
	if ((tmp = strdelimw(&cp)) == NULL) {
		error("%s:%lu: invalid line", path, linenum);
		r = SSH_ERR_INVALID_FORMAT;
		goto out;
	}
	if ((principals = strdup(tmp)) == NULL) {
		error("%s: strdup failed", __func__);
		r = SSH_ERR_ALLOC_FAIL;
		goto out;
	}
	/*
	 * Bail out early if we're looking for a particular principal and this
	 * line does not list it.
	 */
	if (required_principal != NULL) {
		if (match_pattern_list(required_principal,
		    principals, 0) != 1) {
			/* principal didn't match */
			r = SSH_ERR_KEY_NOT_FOUND;
			goto out;
		}
		debug("%s: %s:%lu: matched principal \"%s\"",
		    __func__, path, linenum, required_principal);
	}

	if ((key = sshkey_new(KEY_UNSPEC)) == NULL) {
		error("%s: sshkey_new failed", __func__);
		r = SSH_ERR_ALLOC_FAIL;
		goto out;
	}
	if (sshkey_read(key, &cp) != 0) {
		/* no key? Check for options */
		opts = cp;
		if (sshkey_advance_past_options(&cp) != 0) {
			error("%s:%lu: invalid options", path, linenum);
			r = SSH_ERR_INVALID_FORMAT;
			goto out;
		}
		*cp++ = '\0';
		skip_space(&cp);
		if (sshkey_read(key, &cp) != 0) {
			error("%s:%lu: invalid key", path, linenum);
			r = SSH_ERR_INVALID_FORMAT;
			goto out;
		}
	}
	debug3("%s:%lu: options %s", path, linenum, opts == NULL ? "" : opts);
	if ((sigopts = sshsigopt_parse(opts, path, linenum, &reason)) == NULL) {
		error("%s:%lu: bad options: %s", path, linenum, reason);
		r = SSH_ERR_INVALID_FORMAT;
		goto out;
	}
	/* success */
	if (principalsp != NULL) {
		*principalsp = principals;
		principals = NULL; /* transferred */
	}
	if (sigoptsp != NULL) {
		*sigoptsp = sigopts;
		sigopts = NULL; /* transferred */
	}
	if (keyp != NULL) {
		*keyp = key;
		key = NULL; /* transferred */
	}
	r = 0;
 out:
	free(principals);
	sshsigopt_free(sigopts);
	sshkey_free(key);
	return r;
}

static int
check_allowed_keys_line(const char *path, u_long linenum, char *line,
    const struct sshkey *sign_key, const char *principal,
    const char *sig_namespace)
{
	struct sshkey *found_key = NULL;
	int r, found = 0;
	const char *reason = NULL;
	struct sshsigopt *sigopts = NULL;

	/* Parse the line */
	if ((r = parse_principals_key_and_options(path, linenum, line,
	    principal, NULL, &found_key, &sigopts)) != 0) {
		/* error already logged */
		goto done;
	}

	/* Check whether options preclude the use of this key */
	if (sigopts->namespaces != NULL &&
	    match_pattern_list(sig_namespace, sigopts->namespaces, 0) != 1) {
		error("%s:%lu: key is not permitted for use in signature "
		    "namespace \"%s\"", path, linenum, sig_namespace);
		goto done;
	}

	if (!sigopts->ca && sshkey_equal(found_key, sign_key)) {
		/* Exact match of key */
		debug("%s:%lu: matched key and principal", path, linenum);
		/* success */
		found = 1;
	} else if (sigopts->ca && sshkey_is_cert(sign_key) &&
	    sshkey_equal_public(sign_key->cert->signature_key, found_key)) {
		/* Match of certificate's CA key */
		if ((r = sshkey_cert_check_authority(sign_key, 0, 1,
		    principal, &reason)) != 0) {
			error("%s:%lu: certificate not authorized: %s",
			    path, linenum, reason);
			goto done;
		}
		debug("%s:%lu: matched certificate CA key", path, linenum);
		/* success */
		found = 1;
	} else {
		/* Principal matched but key didn't */
		goto done;
	}
 done:
	sshkey_free(found_key);
	sshsigopt_free(sigopts);
	return found ? 0 : SSH_ERR_KEY_NOT_FOUND;
}

int
sshsig_check_allowed_keys(const char *path, const struct sshkey *sign_key,
    const char *principal, const char *sig_namespace)
{
	FILE *f = NULL;
	char *line = NULL;
	size_t linesize = 0;
	u_long linenum = 0;
	int r = SSH_ERR_INTERNAL_ERROR, oerrno;

	/* Check key and principal against file */
	if ((f = fopen(path, "r")) == NULL) {
		oerrno = errno;
		error("Unable to open allowed keys file \"%s\": %s",
		    path, strerror(errno));
		errno = oerrno;
		return SSH_ERR_SYSTEM_ERROR;
	}

	while (getline(&line, &linesize, f) != -1) {
		linenum++;
		r = check_allowed_keys_line(path, linenum, line, sign_key,
		    principal, sig_namespace);
		free(line);
		line = NULL;
		if (r == SSH_ERR_KEY_NOT_FOUND)
			continue;
		else if (r == 0) {
			/* success */
			fclose(f);
			return 0;
		} else
			break;
	}
	/* Either we hit an error parsing or we simply didn't find the key */
	fclose(f);
	free(line);
	return r == 0 ? SSH_ERR_KEY_NOT_FOUND : r;
}

static int
cert_filter_principals(const char *path, u_long linenum,
    char **principalsp, const struct sshkey *cert)
{
	char *cp, *oprincipals, *principals;
	const char *reason;
	struct sshbuf *nprincipals;
	int r = SSH_ERR_INTERNAL_ERROR, success = 0;

	oprincipals = principals = *principalsp;
	*principalsp = NULL;

	if ((nprincipals = sshbuf_new()) == NULL) {
		r = SSH_ERR_ALLOC_FAIL;
		goto out;
	}

	while ((cp = strsep(&principals, ",")) != NULL && *cp != '\0') {
		if (strcspn(cp, "!?*") != strlen(cp)) {
			debug("%s:%lu: principal \"%s\" not authorized: "
			    "contains wildcards", path, linenum, cp);
			continue;
		}
		/* Check against principals list in certificate */
		if ((r = sshkey_cert_check_authority(cert, 0, 1,
		    cp, &reason)) != 0) {
			debug("%s:%lu: principal \"%s\" not authorized: %s",
			    path, linenum, cp, reason);
			continue;
		}
		if ((r = sshbuf_putf(nprincipals, "%s%s",
		    sshbuf_len(nprincipals) != 0 ? "," : "", cp)) != 0) {
			error("%s: buffer error", __func__);
			goto out;
		}
	}
	if (sshbuf_len(nprincipals) == 0) {
		error("%s:%lu: no valid principals found", path, linenum);
		r = SSH_ERR_KEY_CERT_INVALID;
		goto out;
	}
	if ((principals = sshbuf_dup_string(nprincipals)) == NULL) {
		error("%s: buffer error", __func__);
		goto out;
	}
	/* success */
	success = 1;
	*principalsp = principals;
 out:
	sshbuf_free(nprincipals);
	free(oprincipals);
	return success ? 0 : r;
}

static int
get_matching_principals_from_line(const char *path, u_long linenum, char *line,
    const struct sshkey *sign_key, char **principalsp)
{
	struct sshkey *found_key = NULL;
	char *principals = NULL;
	int r, found = 0;
	struct sshsigopt *sigopts = NULL;

	if (principalsp != NULL)
		*principalsp = NULL;

	/* Parse the line */
	if ((r = parse_principals_key_and_options(path, linenum, line,
	    NULL, &principals, &found_key, &sigopts)) != 0) {
		/* error already logged */
		goto done;
	}

	if (!sigopts->ca && sshkey_equal(found_key, sign_key)) {
		/* Exact match of key */
		debug("%s:%lu: matched key", path, linenum);
		/* success */
		found = 1;
	} else if (sigopts->ca && sshkey_is_cert(sign_key) &&
	    sshkey_equal_public(sign_key->cert->signature_key, found_key)) {
		/* Remove principals listed in file but not allowed by cert */
		if ((r = cert_filter_principals(path, linenum,
		    &principals, sign_key)) != 0) {
			/* error already displayed */
			debug("%s:%lu: cert_filter_principals: %s",
			    path, linenum, ssh_err(r));
			goto done;
		}
		debug("%s:%lu: matched certificate CA key", path, linenum);
		/* success */
		found = 1;
	} else {
		/* Key didn't match */
		goto done;
	}
 done:
	if (found && principalsp != NULL) {
		*principalsp = principals;
		principals = NULL; /* transferred */
	}
	free(principals);
	sshkey_free(found_key);
	sshsigopt_free(sigopts);
	return found ? 0 : SSH_ERR_KEY_NOT_FOUND;
}

int
sshsig_find_principals(const char *path, const struct sshkey *sign_key,
    char **principals)
{
	FILE *f = NULL;
	char *line = NULL;
	size_t linesize = 0;
	u_long linenum = 0;
	int r = SSH_ERR_INTERNAL_ERROR, oerrno;

	if ((f = fopen(path, "r")) == NULL) {
		oerrno = errno;
		error("Unable to open allowed keys file \"%s\": %s",
		    path, strerror(errno));
		errno = oerrno;
		return SSH_ERR_SYSTEM_ERROR;
	}

	while (getline(&line, &linesize, f) != -1) {
		linenum++;
		r = get_matching_principals_from_line(path, linenum, line,
		    sign_key, principals);
		free(line);
		line = NULL;
		if (r == SSH_ERR_KEY_NOT_FOUND)
			continue;
		else if (r == 0) {
			/* success */
			fclose(f);
			return 0;
		} else
			break;
	}
	free(line);
	/* Either we hit an error parsing or we simply didn't find the key */
	if (ferror(f) != 0) {
		oerrno = errno;
		fclose(f);
		error("Unable to read allowed keys file \"%s\": %s",
		    path, strerror(errno));
		errno = oerrno;
		return SSH_ERR_SYSTEM_ERROR;
	}
	fclose(f);
	return r == 0 ? SSH_ERR_KEY_NOT_FOUND : r;
}

int
sshsig_get_pubkey(struct sshbuf *signature, struct sshkey **pubkey)
{
	struct sshkey *pk = NULL;
	int r = SSH_ERR_SIGNATURE_INVALID;

	if (pubkey == NULL)
		return SSH_ERR_INTERNAL_ERROR;
	if ((r = sshsig_parse_preamble(signature)) != 0)
		return r;
	if ((r = sshkey_froms(signature, &pk)) != 0)
		return r;

	*pubkey = pk;
	pk = NULL;
	return 0;
}