#include "first.h"

#include <stdlib.h>
#include <string.h>

#include "sys-crypto-md.h" /* USE_LIB_CRYPTO */

#include "base.h"
#include "plugin.h"
#include "http_auth.h"
#include "http_header.h"
#include "log.h"
#include "safe_memclear.h"
#include "splaytree.h"

/**
 * auth framework
 */

typedef struct {
    splay_tree *sptree; /* data in nodes of tree are (http_auth_cache_entry *)*/
    time_t max_age;
} http_auth_cache;

typedef struct {
    const http_auth_backend_t *auth_backend;
    const array *auth_require;
    http_auth_cache *auth_cache;
    unsigned int auth_extern_authn;
} plugin_config;

typedef struct {
    PLUGIN_DATA;
    plugin_config defaults;
    plugin_config conf;
} plugin_data;

typedef struct {
    const struct http_auth_require_t *require;
    time_t ctime;
    int dalgo;
    uint32_t dlen;
    uint32_t ulen;
    char *username;
    char *pwdigest;
} http_auth_cache_entry;

static http_auth_cache_entry *
http_auth_cache_entry_init (const struct http_auth_require_t * const require, const int dalgo, const char *username, const uint32_t ulen, const char *pw, const uint32_t pwlen)
{
    /*(similar to buffer_copy_string_len() for each element,
     * but allocate exact lengths in single chunk of memory
     * for cache to avoid wasting space and for memory locality)*/
    /* http_auth_require_t is stored instead of copying realm
     *(store pointer to http_auth_require_t, which is persistent
     * and will be different for each realm + permissions combo)*/
    http_auth_cache_entry * const ae =
      malloc(sizeof(http_auth_cache_entry) + ulen + pwlen);
    force_assert(ae);
    ae->require = require;
    ae->ctime = log_epoch_secs;
    ae->dalgo = dalgo;
    ae->ulen = ulen;
    ae->dlen = pwlen;
    ae->username = (char *)(ae + 1);
    ae->pwdigest = ae->username + ulen;
    memcpy(ae->username, username, ulen);
    memcpy(ae->pwdigest, pw, pwlen);
    return ae;
}

static void
http_auth_cache_entry_free (void *data)
{
    http_auth_cache_entry * const ae = data;
    safe_memclear(ae->pwdigest, ae->dlen);
    free(ae);
}

static void
http_auth_cache_free (http_auth_cache *ac)
{
    splay_tree *sptree = ac->sptree;
    while (sptree) {
        http_auth_cache_entry_free(sptree->data);
        sptree = splaytree_delete(sptree, sptree->key);
    }
    free(ac);
}

static http_auth_cache *
http_auth_cache_init (const array *opts)
{
    http_auth_cache *ac = malloc(sizeof(http_auth_cache));
    force_assert(ac);
    ac->sptree = NULL;
    ac->max_age = 600; /* 10 mins */
    for (uint32_t i = 0, used = opts->used; i < used; ++i) {
        data_string *ds = (data_string *)opts->data[i];
        if (buffer_is_equal_string(&ds->key, CONST_STR_LEN("max-age"))) {
            if (ds->type == TYPE_STRING)
                ac->max_age = (time_t)strtol(ds->value.ptr, NULL, 10);
            else if (ds->type == TYPE_INTEGER)
                ac->max_age = (time_t)((data_integer *)ds)->value;
        }
    }
    return ac;
}

static int
http_auth_cache_hash (const struct http_auth_require_t * const require, const char *username, const uint32_t ulen)
{
    uint32_t h = /*(hash pointer value, which includes realm and permissions)*/
      djbhash((char *)(intptr_t)require, sizeof(intptr_t), DJBHASH_INIT);
    h = djbhash(username, ulen, h);
    /* strip highest bit of hash value for splaytree (see splaytree_djbhash())*/
    return (int32_t)(h & ~(((uint32_t)1) << 31));
}

static http_auth_cache_entry *
http_auth_cache_query (splay_tree ** const sptree, const int ndx)
{
    *sptree = splaytree_splay(*sptree, ndx);
    return (*sptree && (*sptree)->key == ndx) ? (*sptree)->data : NULL;
}

static void
http_auth_cache_insert (splay_tree ** const sptree, const int ndx, void * const data, void(data_free_fn)(void *))
{
    /*(not necessary to re-splay (with current usage) since single-threaded
     * and splaytree has not been modified since http_auth_cache_query())*/
    /* *sptree = splaytree_splay(*sptree, ndx); */
    if (NULL == *sptree || (*sptree)->key != ndx)
        *sptree = splaytree_insert(*sptree, ndx, data);
    else { /* collision; replace old entry */
        data_free_fn((*sptree)->data);
        (*sptree)->data = data;
    }
}

/* walk though cache, collect expired ids, and remove them in a second loop */
static void
mod_auth_tag_old_entries (splay_tree * const t, int * const keys, int * const ndx, const time_t max_age, const time_t cur_ts)
{
    if (*ndx == 8192) return; /*(must match num array entries in keys[])*/
    if (t->left)
        mod_auth_tag_old_entries(t->left, keys, ndx, max_age, cur_ts);
    if (t->right)
        mod_auth_tag_old_entries(t->right, keys, ndx, max_age, cur_ts);
    if (*ndx == 8192) return; /*(must match num array entries in keys[])*/

    const http_auth_cache_entry * const ae = t->data;
    if (cur_ts - ae->ctime > max_age)
        keys[(*ndx)++] = t->key;
}

__attribute_noinline__
static void
mod_auth_periodic_cleanup(splay_tree **sptree_ptr, const time_t max_age, const time_t cur_ts)
{
    splay_tree *sptree = *sptree_ptr;
    int max_ndx, i;
    int keys[8192]; /* 32k size on stack */
    do {
        if (!sptree) break;
        max_ndx = 0;
        mod_auth_tag_old_entries(sptree, keys, &max_ndx, max_age, cur_ts);
        for (i = 0; i < max_ndx; ++i) {
            int ndx = keys[i];
            sptree = splaytree_splay(sptree, ndx);
            if (sptree && sptree->key == ndx) {
                http_auth_cache_entry_free(sptree->data);
                sptree = splaytree_delete(sptree, ndx);
            }
        }
    } while (max_ndx == sizeof(keys)/sizeof(int));
    *sptree_ptr = sptree;
}

TRIGGER_FUNC(mod_auth_periodic)
{
    const plugin_data * const p = p_d;
    const time_t cur_ts = log_epoch_secs;
    if (cur_ts & 0x7) return HANDLER_GO_ON; /*(continue once each 8 sec)*/
    UNUSED(srv);

    /* future: might construct array of (http_auth_cache *) at startup
     *         to avoid the need to search for them here */
    for (int i = 0, used = p->nconfig; i < used; ++i) {
        const config_plugin_value_t *cpv = p->cvlist + p->cvlist[i].v.u2[0];
        for (; cpv->k_id != -1; ++cpv) {
            if (cpv->k_id != 3) continue; /* k_id == 3 for auth.cache */
            if (cpv->vtype != T_CONFIG_LOCAL) continue;
            http_auth_cache *ac = cpv->v.v;
            mod_auth_periodic_cleanup(&ac->sptree, ac->max_age, cur_ts);
        }
    }

    return HANDLER_GO_ON;
}




static handler_t mod_auth_check_basic(request_st *r, void *p_d, const struct http_auth_require_t *require, const struct http_auth_backend_t *backend);
static handler_t mod_auth_check_digest(request_st *r, void *p_d, const struct http_auth_require_t *require, const struct http_auth_backend_t *backend);
static handler_t mod_auth_check_extern(request_st *r, void *p_d, const struct http_auth_require_t *require, const struct http_auth_backend_t *backend);

INIT_FUNC(mod_auth_init) {
	static http_auth_scheme_t http_auth_scheme_basic  = { "basic",  mod_auth_check_basic,  NULL };
	static http_auth_scheme_t http_auth_scheme_digest = { "digest", mod_auth_check_digest, NULL };
	static const http_auth_scheme_t http_auth_scheme_extern = { "extern", mod_auth_check_extern, NULL };
	plugin_data *p = calloc(1, sizeof(*p));
	force_assert(p);

	/* register http_auth_scheme_* */
	http_auth_scheme_basic.p_d = p;
	http_auth_scheme_set(&http_auth_scheme_basic);
	http_auth_scheme_digest.p_d = p;
	http_auth_scheme_set(&http_auth_scheme_digest);
	http_auth_scheme_set(&http_auth_scheme_extern);

	return p;
}

FREE_FUNC(mod_auth_free) {
    plugin_data * const p = p_d;
    if (NULL == p->cvlist) return;
    /* (init i to 0 if global context; to 1 to skip empty global context) */
    for (int i = !p->cvlist[0].v.u2[1], used = p->nconfig; i < used; ++i) {
        config_plugin_value_t *cpv = p->cvlist + p->cvlist[i].v.u2[0];
        for (; -1 != cpv->k_id; ++cpv) {
            if (cpv->vtype != T_CONFIG_LOCAL || NULL == cpv->v.v) continue;
            switch (cpv->k_id) {
              case 1: /* auth.require */
                array_free(cpv->v.v);
                break;
              case 3: /* auth.cache */
                http_auth_cache_free(cpv->v.v);
                break;
              default:
                break;
            }
        }
    }
}

/* data type for mod_auth structured data
 * (parsed from auth.require array of strings) */
typedef struct {
    DATA_UNSET;
    http_auth_require_t *require;
} data_auth;

static void data_auth_free(data_unset *d)
{
    data_auth * const dauth = (data_auth *)d;
    free(dauth->key.ptr);
    http_auth_require_free(dauth->require);
    free(dauth);
}

static data_auth *data_auth_init(void)
{
    static const struct data_methods fn = {
      NULL, /* copy must not be called on this data */
      data_auth_free,
      NULL, /* insert_dup must not be called on this data */
      NULL  /* print must not be called on this data */
    };
    data_auth * const dauth = calloc(1, sizeof(*dauth));
    force_assert(NULL != dauth);
    dauth->type       = TYPE_OTHER;
    dauth->fn         = &fn;

    dauth->require = http_auth_require_init();

    return dauth;
}

static int mod_auth_algorithm_parse(http_auth_info_t *ai, const char *s) {
    size_t len;
    if (NULL == s) {
        ai->dalgo = HTTP_AUTH_DIGEST_MD5;
        ai->dlen  = HTTP_AUTH_DIGEST_MD5_BINLEN;
        return 1;
    }

    len = strlen(s);
    if (len > 5
        && (s[len-5]       ) == '-'
        && (s[len-4] | 0x20) == 's'
        && (s[len-3] | 0x20) == 'e'
        && (s[len-2] | 0x20) == 's'
        && (s[len-1] | 0x20) == 's') {
        ai->dalgo = HTTP_AUTH_DIGEST_SESS;
        len -= 5;
    }
    else {
        ai->dalgo = HTTP_AUTH_DIGEST_NONE;
    }

    if (3 == len
        && 'm' == (s[0] | 0x20)
        && 'd' == (s[1] | 0x20)
        && '5' == (s[2]       )) {
        ai->dalgo |= HTTP_AUTH_DIGEST_MD5;
        ai->dlen   = HTTP_AUTH_DIGEST_MD5_BINLEN;
        return 1;
    }
  #ifdef USE_LIB_CRYPTO
    else if (len >= 7
             && 's' == (s[0] | 0x20)
             && 'h' == (s[1] | 0x20)
             && 'a' == (s[2] | 0x20)
             && '-' == (s[3]       )) {
        if (len == 7 && s[4] == '2' && s[5] == '5' && s[6] == '6') {
            ai->dalgo |= HTTP_AUTH_DIGEST_SHA256;
            ai->dlen   = HTTP_AUTH_DIGEST_SHA256_BINLEN;
            return 1;
        }
      #ifdef USE_LIB_CRYPTO_SHA512_256
        if (len == 11 && 0 == memcmp(s+4, "512-256", 7)) {
            ai->dalgo |= HTTP_AUTH_DIGEST_SHA512_256;
            ai->dlen   = HTTP_AUTH_DIGEST_SHA512_256_BINLEN;
            return 1;
        }
      #endif
    }
  #endif
    return 0; /*(error)*/
}

static int mod_auth_algorithms_parse(int *algorithm, buffer *algos) {
    for (char *s = algos->ptr, *p; s; s = p ? p+1 : NULL) {
        http_auth_info_t ai;
        int rc;
        p = strchr(s, '|');
        if (p) *p = '\0';
        rc = mod_auth_algorithm_parse(&ai, s);
        if (p) *p = '|';
        if (!rc) return 0;
        *algorithm |= ai.dalgo;
    }
    return 1;
}

static int mod_auth_require_parse (http_auth_require_t * const require, const buffer *b, log_error_st *errh)
{
    /* user=name1|user=name2|group=name3|host=name4 */

    const char *str = b->ptr;
    const char *p;

    if (buffer_is_equal_string(b, CONST_STR_LEN("valid-user"))) {
        require->valid_user = 1;
        return 1; /* success */
    }

    do {
        const char *eq;
        size_t len;
        p = strchr(str, '|');
        len = NULL != p ? (size_t)(p - str) : strlen(str);
        eq = memchr(str, '=', len);
        if (NULL == eq) {
            log_error(errh, __FILE__, __LINE__,
              "error parsing auth.require 'require' field: missing '=' "
              "(expecting \"valid-user\" or \"user=a|user=b|group=g|host=h\"). "
              "error value: %s error near: %s", b->ptr, str);
            return 0;
        }
        if (eq[1] == '|' || eq[1] == '\0') {
            log_error(errh, __FILE__, __LINE__,
              "error parsing auth.require 'require' field: "
              "missing token after '=' "
              "(expecting \"valid-user\" or \"user=a|user=b|group=g|host=h\"). "
              "error value: %s error near: %s", b->ptr, str);
            return 0;
        }

        switch ((int)(eq - str)) {
          case 4:
            if (0 == memcmp(str, CONST_STR_LEN("user"))) {
                /*("user=" is 5)*/
                array_set_key_value(&require->user, str+5, len-5, CONST_STR_LEN(""));
                continue;
            }
            else if (0 == memcmp(str, CONST_STR_LEN("host"))) {
                /*("host=" is 5)*/
                array_set_key_value(&require->host, str+5, len-5, CONST_STR_LEN(""));
                log_error(errh, __FILE__, __LINE__,
                  "warning parsing auth.require 'require' field: "
                  "'host' not implemented; field value: %s", b->ptr);
                continue;
            }
            break; /* to error */
          case 5:
            if (0 == memcmp(str, CONST_STR_LEN("group"))) {
                /*("group=" is 6)*/
                array_set_key_value(&require->group, str+6, len-6, CONST_STR_LEN(""));
              #if 0/*(supported by mod_authn_ldap, but not all other backends)*/
                log_error(errh, __FILE__, __LINE__,
                  "warning parsing auth.require 'require' field: "
                  "'group' not implemented; field value: %s", b->ptr);
              #endif
                continue;
            }
            break; /* to error */
          case 10:
            if (0 == memcmp(str, CONST_STR_LEN("valid-user"))) {
                log_error(errh, __FILE__, __LINE__,
                  "error parsing auth.require 'require' field: "
                  "valid user can not be combined with other require rules "
                  "(expecting \"valid-user\" or "
                  "\"user=a|user=b|group=g|host=h\"). error value: %s", b->ptr);
                return 0;
            }
            break; /* to error */
          default:
            break; /* to error */
        }

        log_error(errh, __FILE__, __LINE__,
          "error parsing auth.require 'require' field: "
          "invalid/unsupported token "
          "(expecting \"valid-user\" or \"user=a|user=b|group=g|host=h\"). "
          "error value: %s error near: %s", b->ptr, str);
        return 0;

    } while (p && *((str = p+1)));

    return 1; /* success */
}

static handler_t mod_auth_require_parse_array(const array *value, array * const auth_require, log_error_st *errh)
{
		for (uint32_t n = 0; n < value->used; ++n) {
			size_t m;
			data_array *da_file = (data_array *)value->data[n];
			const buffer *method = NULL, *realm = NULL, *require = NULL;
			const buffer *nonce_secret = NULL;
			const http_auth_scheme_t *auth_scheme;
			buffer *algos = NULL;
			int algorithm = HTTP_AUTH_DIGEST_SESS;

			if (!array_is_kvstring(&da_file->value)) {
				log_error(errh, __FILE__, __LINE__,
				  "unexpected value for auth.require; expected "
				  "auth.require = ( \"urlpath\" => ( \"option\" => \"value\" ) )");

				return HANDLER_ERROR;
			}

			for (m = 0; m < da_file->value.used; m++) {
				if (da_file->value.data[m]->type == TYPE_STRING) {
					data_string *ds = (data_string *)da_file->value.data[m];
					if (buffer_is_equal_string(&ds->key, CONST_STR_LEN("method"))) {
						method = &ds->value;
					} else if (buffer_is_equal_string(&ds->key, CONST_STR_LEN("realm"))) {
						realm = &ds->value;
					} else if (buffer_is_equal_string(&ds->key, CONST_STR_LEN("require"))) {
						require = &ds->value;
					} else if (buffer_is_equal_string(&ds->key, CONST_STR_LEN("algorithm"))) {
						algos = &ds->value;
					} else if (buffer_is_equal_string(&ds->key, CONST_STR_LEN("nonce_secret"))
					           || buffer_is_equal_string(&ds->key, CONST_STR_LEN("nonce-secret"))) {
						nonce_secret = &ds->value;
					} else {
						log_error(errh, __FILE__, __LINE__,
						  "the field is unknown in: "
						  "auth.require = ( \"...\" => ( ..., -> \"%s\" <- => \"...\" ) )",
						  da_file->value.data[m]->key.ptr);

						return HANDLER_ERROR;
					}
				} else {
					log_error(errh, __FILE__, __LINE__,
					  "a string was expected for: "
					  "auth.require = ( \"...\" => ( ..., -> \"%s\" <- => \"...\" ) )",
					  da_file->value.data[m]->key.ptr);

					return HANDLER_ERROR;
				}
			}

			if (buffer_string_is_empty(method)) {
				log_error(errh, __FILE__, __LINE__,
				  "the method field is missing or blank in: "
				  "auth.require = ( \"...\" => ( ..., \"method\" => \"...\" ) )");
				return HANDLER_ERROR;
			} else {
				auth_scheme = http_auth_scheme_get(method);
				if (NULL == auth_scheme) {
					log_error(errh, __FILE__, __LINE__,
					  "unknown method %s (e.g. \"basic\", \"digest\" or \"extern\") in "
					  "auth.require = ( \"...\" => ( ..., \"method\" => \"...\") )", method->ptr);
					return HANDLER_ERROR;
				}
			}

			if (buffer_is_empty(realm)) {
				log_error(errh, __FILE__, __LINE__,
				  "the realm field is missing in: "
				  "auth.require = ( \"...\" => ( ..., \"realm\" => \"...\" ) )");
				return HANDLER_ERROR;
			}

			if (buffer_string_is_empty(require)) {
				log_error(errh, __FILE__, __LINE__,
				  "the require field is missing or blank in: "
				  "auth.require = ( \"...\" => ( ..., \"require\" => \"...\" ) )");
				return HANDLER_ERROR;
			}

			if (buffer_string_is_empty(algos)) {
				algorithm |= HTTP_AUTH_DIGEST_MD5;
			} else if (!mod_auth_algorithms_parse(&algorithm, algos)) {
				log_error(errh, __FILE__, __LINE__,
				  "invalid algorithm in: "
				  "auth.require = ( \"...\" => ( ..., \"algorithm\" => \"...\" ) )");
				return HANDLER_ERROR;
			}

			if (require) { /*(always true at this point)*/
				data_auth * const dauth = data_auth_init();
				buffer_copy_buffer(&dauth->key, &da_file->key);
				dauth->require->scheme = auth_scheme;
				dauth->require->algorithm = algorithm;
				dauth->require->realm = realm;
				dauth->require->nonce_secret = nonce_secret; /*(NULL is ok)*/
				if (!mod_auth_require_parse(dauth->require, require, errh)) {
					dauth->fn->free((data_unset *)dauth);
					return HANDLER_ERROR;
				}
				array_insert_unique(auth_require, (data_unset *)dauth);
			}
		}

	return HANDLER_GO_ON;
}

static void mod_auth_merge_config_cpv(plugin_config * const pconf, const config_plugin_value_t * const cpv) {
    switch (cpv->k_id) { /* index into static config_plugin_keys_t cpk[] */
      case 0: /* auth.backend */
        if (cpv->vtype == T_CONFIG_LOCAL)
            pconf->auth_backend = cpv->v.v;
        break;
      case 1: /* auth.require */
        if (cpv->vtype == T_CONFIG_LOCAL)
            pconf->auth_require = cpv->v.v;
        break;
      case 2: /* auth.extern-authn */
        pconf->auth_extern_authn = cpv->v.u;
        break;
      case 3: /* auth.cache */
        if (cpv->vtype == T_CONFIG_LOCAL)
            pconf->auth_cache = cpv->v.v;
        break;
      default:/* should not happen */
        return;
    }
}

static void mod_auth_merge_config(plugin_config * const pconf, const config_plugin_value_t *cpv) {
    do {
        mod_auth_merge_config_cpv(pconf, cpv);
    } while ((++cpv)->k_id != -1);
}

static void mod_auth_patch_config(request_st * const r, plugin_data * const p) {
    p->conf = p->defaults; /* copy small struct instead of memcpy() */
    /*memcpy(&p->conf, &p->defaults, sizeof(plugin_config));*/
    for (int i = 1, used = p->nconfig; i < used; ++i) {
        if (config_check_cond(r, (uint32_t)p->cvlist[i].k_id))
            mod_auth_merge_config(&p->conf, p->cvlist + p->cvlist[i].v.u2[0]);
    }
}

SETDEFAULTS_FUNC(mod_auth_set_defaults) {
    static const config_plugin_keys_t cpk[] = {
      { CONST_STR_LEN("auth.backend"),
        T_CONFIG_STRING,
        T_CONFIG_SCOPE_CONNECTION }
     ,{ CONST_STR_LEN("auth.require"),
        T_CONFIG_ARRAY_KVARRAY,
        T_CONFIG_SCOPE_CONNECTION }
     ,{ CONST_STR_LEN("auth.extern-authn"),
        T_CONFIG_BOOL,
        T_CONFIG_SCOPE_CONNECTION }
     ,{ CONST_STR_LEN("auth.cache"),
        T_CONFIG_ARRAY,
        T_CONFIG_SCOPE_CONNECTION }
     ,{ NULL, 0,
        T_CONFIG_UNSET,
        T_CONFIG_SCOPE_UNSET }
    };

    plugin_data * const p = p_d;
    if (!config_plugin_values_init(srv, p, cpk, "mod_auth"))
        return HANDLER_ERROR;

    /* process and validate config directives
     * (init i to 0 if global context; to 1 to skip empty global context) */
    for (int i = !p->cvlist[0].v.u2[1]; i < p->nconfig; ++i) {
        config_plugin_value_t *cpv = p->cvlist + p->cvlist[i].v.u2[0];
        for (; -1 != cpv->k_id; ++cpv) {
            switch (cpv->k_id) {
              case 0: /* auth.backend */
                if (!buffer_string_is_empty(cpv->v.b)) {
                    const http_auth_backend_t * const auth_backend =
                      http_auth_backend_get(cpv->v.b);
                    if (NULL == auth_backend) {
                        log_error(srv->errh, __FILE__, __LINE__,
                          "auth.backend not supported: %s", cpv->v.b->ptr);
                        return HANDLER_ERROR;
                    }
                    *(const http_auth_backend_t **)&cpv->v.v = auth_backend;
                    cpv->vtype = T_CONFIG_LOCAL;
                }
                break;
              case 1: /* auth.require */
                {
                    array * const a = array_init(4);
                    if (HANDLER_GO_ON !=
                        mod_auth_require_parse_array(cpv->v.a, a, srv->errh)) {
                        array_free(a);
                        return HANDLER_ERROR;
                    }
                    cpv->v.a = a;
                    cpv->vtype = T_CONFIG_LOCAL;
                }
                break;
              case 2: /* auth.extern-authn */
                break;
              case 3: /* auth.cache */
                cpv->v.v = http_auth_cache_init(cpv->v.a);
                cpv->vtype = T_CONFIG_LOCAL;
                break;
              default:/* should not happen */
                break;
            }
        }
    }

    /* initialize p->defaults from global config context */
    if (p->nconfig > 0 && p->cvlist->v.u2[1]) {
        const config_plugin_value_t *cpv = p->cvlist + p->cvlist->v.u2[0];
        if (-1 != cpv->k_id)
            mod_auth_merge_config(&p->defaults, cpv);
    }

    return HANDLER_GO_ON;
}

static handler_t mod_auth_uri_handler(request_st * const r, void *p_d) {
	plugin_data *p = p_d;
	data_auth *dauth;

	mod_auth_patch_config(r, p);

	if (p->conf.auth_require == NULL) return HANDLER_GO_ON;

	/* search auth directives for first prefix match against URL path */
	/* if we have a case-insensitive FS we have to lower-case the URI here too */
	dauth = (!r->conf.force_lowercase_filenames)
	   ? (data_auth *)array_match_key_prefix(p->conf.auth_require, &r->uri.path)
	   : (data_auth *)array_match_key_prefix_nc(p->conf.auth_require, &r->uri.path);
	if (NULL == dauth) return HANDLER_GO_ON;

	{
			const http_auth_scheme_t * const scheme = dauth->require->scheme;
			if (p->conf.auth_extern_authn) {
				const buffer *vb = http_header_env_get(r, CONST_STR_LEN("REMOTE_USER"));
				if (NULL != vb && http_auth_match_rules(dauth->require, vb->ptr, NULL, NULL)) {
					return HANDLER_GO_ON;
				}
			}
			return scheme->checkfn(r, scheme->p_d, dauth->require, p->conf.auth_backend);
	}
}


int mod_auth_plugin_init(plugin *p);
int mod_auth_plugin_init(plugin *p) {
	p->version     = LIGHTTPD_VERSION_ID;
	p->name        = "auth";
	p->init        = mod_auth_init;
	p->set_defaults = mod_auth_set_defaults;
	p->handle_trigger = mod_auth_periodic;
	p->handle_uri_clean = mod_auth_uri_handler;
	p->cleanup     = mod_auth_free;

	return 0;
}




/*
 * auth schemes (basic, digest, extern)
 *
 * (could be in separate file from mod_auth.c as long as registration occurs)
 */

#include "sys-crypto-md.h"
#include "base64.h"
#include "rand.h"
#include "http_header.h"

__attribute_cold__
static handler_t mod_auth_send_400_bad_request(request_st * const r) {

	/* a field was missing or invalid */
	r->http_status = 400; /* Bad Request */
	r->handler_module = NULL;

	return HANDLER_FINISHED;
}

static handler_t mod_auth_send_401_unauthorized_basic(request_st * const r, const buffer * const realm) {
	r->http_status = 401;
	r->handler_module = NULL;

	buffer * const tb = r->tmp_buf;
	buffer_copy_string_len(tb, CONST_STR_LEN("Basic realm=\""));
	buffer_append_string_buffer(tb, realm);
	buffer_append_string_len(tb, CONST_STR_LEN("\", charset=\"UTF-8\""));

	http_header_response_set(r, HTTP_HEADER_OTHER, CONST_STR_LEN("WWW-Authenticate"), CONST_BUF_LEN(tb));

	return HANDLER_FINISHED;
}

static handler_t mod_auth_check_basic(request_st * const r, void *p_d, const struct http_auth_require_t * const require, const struct http_auth_backend_t * const backend) {
	const buffer *b = http_header_request_get(r, HTTP_HEADER_AUTHORIZATION, CONST_STR_LEN("Authorization"));
	buffer *username;
	char *pw;
	handler_t rc = HANDLER_UNSET;

	if (NULL == backend) {
		log_error(r->conf.errh, __FILE__, __LINE__, "auth.backend not configured for %s", r->uri.path.ptr);
		r->http_status = 500;
		r->handler_module = NULL;
		return HANDLER_FINISHED;
	}

	if (NULL == b) {
		return mod_auth_send_401_unauthorized_basic(r, require->realm);
	}

	if (!buffer_eq_icase_ssn(b->ptr, CONST_STR_LEN("Basic "))) {
		return mod_auth_send_401_unauthorized_basic(r, require->realm);
	}
      #ifdef __COVERITY__
	if (buffer_string_length(b) < sizeof("Basic ")-1) {
		return mod_auth_send_400_bad_request(r);
	}
      #endif

	username = buffer_init();

	/* coverity[overflow_sink : FALSE] */
	if (!buffer_append_base64_decode(username, b->ptr+sizeof("Basic ")-1, buffer_string_length(b)-(sizeof("Basic ")-1), BASE64_STANDARD)) {
		log_error(r->conf.errh, __FILE__, __LINE__, "decoding base64-string failed %s", b->ptr+sizeof("Basic ")-1);

		buffer_free(username);
		return mod_auth_send_400_bad_request(r);
	}

	/* r2 == user:password */
	if (NULL == (pw = strchr(username->ptr, ':'))) {
		log_error(r->conf.errh, __FILE__, __LINE__, "missing ':' in %s", username->ptr);

		buffer_free(username);
		return mod_auth_send_400_bad_request(r);
	}

	uint32_t pwlen = buffer_string_length(username);
	buffer_string_set_length(username, pw - username->ptr);
	pw++;
	pwlen -= (pw - username->ptr);

	plugin_data * const p = p_d;
	splay_tree ** sptree = p->conf.auth_cache
	  ? &p->conf.auth_cache->sptree
	  : NULL;
	http_auth_cache_entry *ae = NULL;
	int ndx = -1;
	if (sptree) {
		ndx = http_auth_cache_hash(require, CONST_BUF_LEN(username));
		ae = http_auth_cache_query(sptree, ndx);
		if (ae && ae->require == require
		    && buffer_is_equal_string(username, ae->username, ae->ulen))
			rc = http_auth_const_time_memeq_pad(ae->pwdigest, ae->dlen,
			                                    pw, pwlen)
			  ? HANDLER_GO_ON
			  : HANDLER_ERROR;
		else /*(not found or hash collision)*/
			ae = NULL;
	}

	if (NULL == ae) /* (HANDLER_UNSET == rc) */
		rc = backend->basic(r, backend->p_d, require, username, pw);

	switch (rc) {
	case HANDLER_GO_ON:
		http_auth_setenv(r, CONST_BUF_LEN(username), CONST_STR_LEN("Basic"));
		if (sptree && NULL == ae) { /*(cache (new) successful result)*/
			ae = http_auth_cache_entry_init(require, 0, CONST_BUF_LEN(username),
			                                pw, pwlen);
			http_auth_cache_insert(sptree, ndx, ae, http_auth_cache_entry_free);
		}
		break;
	case HANDLER_WAIT_FOR_EVENT:
	case HANDLER_FINISHED:
		break;
	case HANDLER_ERROR:
	default:
		log_error(r->conf.errh, __FILE__, __LINE__,
		  "password doesn't match for %s username: %s IP: %s",
		  r->uri.path.ptr, username->ptr, r->con->dst_addr_buf->ptr);
		r->keep_alive = 0; /*(disable keep-alive if bad password)*/
		rc = HANDLER_UNSET;
		break;
	}

	buffer_free(username);
	return (HANDLER_UNSET != rc) ? rc : mod_auth_send_401_unauthorized_basic(r, require->realm);
}


#ifdef USE_LIB_CRYPTO

static void mod_auth_digest_mutate_sha256(http_auth_info_t *ai, const char *m, const char *uri, const char *nonce, const char *cnonce, const char *nc, const char *qop) {
    SHA256_CTX ctx;
    char a1[HTTP_AUTH_DIGEST_SHA256_BINLEN*2+1];
    char a2[HTTP_AUTH_DIGEST_SHA256_BINLEN*2+1];

    if (ai->dalgo & HTTP_AUTH_DIGEST_SESS) {
        SHA256_Init(&ctx);
        li_tohex(a1, sizeof(a1), (const char *)ai->digest, ai->dlen);
        SHA256_Update(&ctx, (unsigned char *)a1, sizeof(a1)-1);
        SHA256_Update(&ctx, CONST_STR_LEN(":"));
        SHA256_Update(&ctx, (unsigned char *)nonce, strlen(nonce));
        SHA256_Update(&ctx, CONST_STR_LEN(":"));
        SHA256_Update(&ctx, (unsigned char *)cnonce, strlen(cnonce));
        SHA256_Final(ai->digest, &ctx);
    }

    li_tohex(a1, sizeof(a1), (const char *)ai->digest, ai->dlen);

    /* calculate H(A2) */
    SHA256_Init(&ctx);
    SHA256_Update(&ctx, (unsigned char *)m, strlen(m));
    SHA256_Update(&ctx, CONST_STR_LEN(":"));
    SHA256_Update(&ctx, (unsigned char *)uri, strlen(uri));
  #if 0
    /* qop=auth-int not supported, already checked in caller */
    if (qop && buffer_eq_icase_ss(qop, strlen(qop), CONST_STR_LEN("auth-int"))){
        SHA256_Update(&ctx, CONST_STR_LEN(":"));
        SHA256_Update(&ctx, (unsigned char *) [body checksum], ai->dlen*2);
    }
  #endif
    SHA256_Final(ai->digest, &ctx);
    li_tohex(a2, sizeof(a2), (const char *)ai->digest, ai->dlen);

    /* calculate response */
    SHA256_Init(&ctx);
    SHA256_Update(&ctx, (unsigned char *)a1, sizeof(a1)-1);
    SHA256_Update(&ctx, CONST_STR_LEN(":"));
    SHA256_Update(&ctx, (unsigned char *)nonce, strlen(nonce));
    SHA256_Update(&ctx, CONST_STR_LEN(":"));
    if (qop && *qop) {
        SHA256_Update(&ctx, (unsigned char *)nc, strlen(nc));
        SHA256_Update(&ctx, CONST_STR_LEN(":"));
        SHA256_Update(&ctx, (unsigned char *)cnonce, strlen(cnonce));
        SHA256_Update(&ctx, CONST_STR_LEN(":"));
        SHA256_Update(&ctx, (unsigned char *)qop, strlen(qop));
        SHA256_Update(&ctx, CONST_STR_LEN(":"));
    }
    SHA256_Update(&ctx, (unsigned char *)a2, sizeof(a2)-1);
    SHA256_Final(ai->digest, &ctx);
}

static void mod_auth_digest_nonce_sha256(buffer *b, time_t cur_ts, int rnd, const buffer *secret) {
    SHA256_CTX ctx;
    size_t len;
    unsigned char h[HTTP_AUTH_DIGEST_SHA256_BINLEN];
    char hh[HTTP_AUTH_DIGEST_SHA256_BINLEN*2+1];
    force_assert(sizeof(hh) >= LI_ITOSTRING_LENGTH);
    SHA256_Init(&ctx);
    len = li_itostrn(hh, sizeof(hh), cur_ts);
    SHA256_Update(&ctx, (unsigned char *)hh, len);
    len = li_itostrn(hh, sizeof(hh), rnd);
    SHA256_Update(&ctx, (unsigned char *)hh, len);
    if (secret) {
        len = buffer_string_length(secret);
        SHA256_Update(&ctx, (unsigned char *)secret->ptr, len);
    }
    SHA256_Final(h, &ctx);
    li_tohex(hh, sizeof(hh), (const char *)h, sizeof(h));
    buffer_append_string_len(b, hh, sizeof(hh)-1);
}

#ifdef USE_LIB_CRYPTO_SHA512_256

static void mod_auth_digest_mutate_sha512_256(http_auth_info_t *ai, const char *m, const char *uri, const char *nonce, const char *cnonce, const char *nc, const char *qop) {
    SHA512_CTX ctx;
    char a1[HTTP_AUTH_DIGEST_SHA512_256_BINLEN*2+1];
    char a2[HTTP_AUTH_DIGEST_SHA512_256_BINLEN*2+1];

    if (ai->dalgo & HTTP_AUTH_DIGEST_SESS) {
        SHA512_256_Init(&ctx);
        li_tohex(a1, sizeof(a1), (const char *)ai->digest, ai->dlen);
        SHA512_256_Update(&ctx, (unsigned char *)a1, sizeof(a1)-1);
        SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
        SHA512_256_Update(&ctx, (unsigned char *)nonce, strlen(nonce));
        SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
        SHA512_256_Update(&ctx, (unsigned char *)cnonce, strlen(cnonce));
        SHA512_256_Final(ai->digest, &ctx);
    }

    li_tohex(a1, sizeof(a1), (const char *)ai->digest, ai->dlen);

    /* calculate H(A2) */
    SHA512_256_Init(&ctx);
    SHA512_256_Update(&ctx, (unsigned char *)m, strlen(m));
    SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
    SHA512_256_Update(&ctx, (unsigned char *)uri, strlen(uri));
  #if 0
    /* qop=auth-int not supported, already checked in caller */
    if (qop && buffer_eq_icase_ss(qop, strlen(qop), CONST_STR_LEN("auth-int"))){
        SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
        SHA512_256_Update(&ctx, (unsigned char *)[body checksum], ai->dlen*2);
    }
  #endif
    SHA512_256_Final(ai->digest, &ctx);
    li_tohex(a2, sizeof(a2), (const char *)ai->digest, ai->dlen);

    /* calculate response */
    SHA512_256_Init(&ctx);
    SHA512_256_Update(&ctx, (unsigned char *)a1, sizeof(a1)-1);
    SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
    SHA512_256_Update(&ctx, (unsigned char *)nonce, strlen(nonce));
    SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
    if (qop && *qop) {
        SHA512_256_Update(&ctx, (unsigned char *)nc, strlen(nc));
        SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
        SHA512_256_Update(&ctx, (unsigned char *)cnonce, strlen(cnonce));
        SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
        SHA512_256_Update(&ctx, (unsigned char *)qop, strlen(qop));
        SHA512_256_Update(&ctx, CONST_STR_LEN(":"));
    }
    SHA512_256_Update(&ctx, (unsigned char *)a2, sizeof(a2)-1);
    SHA512_256_Final(ai->digest, &ctx);
}

static void mod_auth_digest_nonce_sha512_256(buffer *b, time_t cur_ts, int rnd, const buffer *secret) {
    SHA512_CTX ctx;
    size_t len;
    unsigned char h[HTTP_AUTH_DIGEST_SHA512_256_BINLEN];
    char hh[HTTP_AUTH_DIGEST_SHA512_256_BINLEN*2+1];
    force_assert(sizeof(hh) >= LI_ITOSTRING_LENGTH);
    SHA512_256_Init(&ctx);
    len = li_itostrn(hh, sizeof(hh), cur_ts);
    SHA512_256_Update(&ctx, (unsigned char *)hh, len);
    len = li_itostrn(hh, sizeof(hh), rnd);
    SHA512_256_Update(&ctx, (unsigned char *)hh, len);
    if (secret) {
        len = buffer_string_length(secret);
        SHA512_256_Update(&ctx, (unsigned char *)secret->ptr, len);
    }
    SHA512_256_Final(h, &ctx);
    li_tohex(hh, sizeof(hh), (const char *)h, sizeof(h));
    buffer_append_string_len(b, hh, sizeof(hh)-1);
}

#endif /* USE_LIB_CRYPTO_SHA512_256 */

#endif /* USE_LIB_CRYPTO */

static void mod_auth_digest_mutate_md5(http_auth_info_t *ai, const char *m, const char *uri, const char *nonce, const char *cnonce, const char *nc, const char *qop) {
    li_MD5_CTX ctx;
    char a1[HTTP_AUTH_DIGEST_MD5_BINLEN*2+1];
    char a2[HTTP_AUTH_DIGEST_MD5_BINLEN*2+1];

    if (ai->dalgo & HTTP_AUTH_DIGEST_SESS) {
        li_MD5_Init(&ctx);
        /* http://www.rfc-editor.org/errata_search.php?rfc=2617
         * Errata ID: 1649 */
        li_tohex(a1, sizeof(a1), (const char *)ai->digest, ai->dlen);
        li_MD5_Update(&ctx, (unsigned char *)a1, sizeof(a1)-1);
        li_MD5_Update(&ctx, CONST_STR_LEN(":"));
        li_MD5_Update(&ctx, (unsigned char *)nonce, strlen(nonce));
        li_MD5_Update(&ctx, CONST_STR_LEN(":"));
        li_MD5_Update(&ctx, (unsigned char *)cnonce, strlen(cnonce));
        li_MD5_Final(ai->digest, &ctx);
    }

    li_tohex(a1, sizeof(a1), (const char *)ai->digest, ai->dlen);

    /* calculate H(A2) */
    li_MD5_Init(&ctx);
    li_MD5_Update(&ctx, (unsigned char *)m, strlen(m));
    li_MD5_Update(&ctx, CONST_STR_LEN(":"));
    li_MD5_Update(&ctx, (unsigned char *)uri, strlen(uri));
  #if 0
    /* qop=auth-int not supported, already checked in caller */
    if (qop && buffer_eq_icase_ss(qop, strlen(qop), CONST_STR_LEN("auth-int"))){
        li_MD5_Update(&ctx, CONST_STR_LEN(":"));
        li_MD5_Update(&ctx, (unsigned char *) [body checksum], ai->dlen*2);
    }
  #endif
    li_MD5_Final(ai->digest, &ctx);
    li_tohex(a2, sizeof(a2), (const char *)ai->digest, ai->dlen);

    /* calculate response */
    li_MD5_Init(&ctx);
    li_MD5_Update(&ctx, (unsigned char *)a1, sizeof(a1)-1);
    li_MD5_Update(&ctx, CONST_STR_LEN(":"));
    li_MD5_Update(&ctx, (unsigned char *)nonce, strlen(nonce));
    li_MD5_Update(&ctx, CONST_STR_LEN(":"));
    if (qop && *qop) {
        li_MD5_Update(&ctx, (unsigned char *)nc, strlen(nc));
        li_MD5_Update(&ctx, CONST_STR_LEN(":"));
        li_MD5_Update(&ctx, (unsigned char *)cnonce, strlen(cnonce));
        li_MD5_Update(&ctx, CONST_STR_LEN(":"));
        li_MD5_Update(&ctx, (unsigned char *)qop, strlen(qop));
        li_MD5_Update(&ctx, CONST_STR_LEN(":"));
    }
    li_MD5_Update(&ctx, (unsigned char *)a2, sizeof(a2)-1);
    li_MD5_Final(ai->digest, &ctx);
}

static void mod_auth_digest_nonce_md5(buffer *b, time_t cur_ts, int rnd, const buffer *secret) {
    li_MD5_CTX ctx;
    size_t len;
    unsigned char h[HTTP_AUTH_DIGEST_MD5_BINLEN];
    char hh[HTTP_AUTH_DIGEST_MD5_BINLEN*2+1];
    force_assert(sizeof(hh) >= LI_ITOSTRING_LENGTH);
    li_MD5_Init(&ctx);
    len = li_itostrn(hh, sizeof(hh), cur_ts);
    li_MD5_Update(&ctx, (unsigned char *)hh, len);
    len = li_itostrn(hh, sizeof(hh), rnd);
    li_MD5_Update(&ctx, (unsigned char *)hh, len);
    if (secret) {
        len = buffer_string_length(secret);
        li_MD5_Update(&ctx, (unsigned char *)secret->ptr, len);
    }
    li_MD5_Final(h, &ctx);
    li_tohex(hh, sizeof(hh), (const char *)h, sizeof(h));
    buffer_append_string_len(b, hh, sizeof(hh)-1);
}

static void mod_auth_digest_mutate(http_auth_info_t *ai, const char *m, const char *uri, const char *nonce, const char *cnonce, const char *nc, const char *qop) {
    if (ai->dalgo & HTTP_AUTH_DIGEST_MD5)
        mod_auth_digest_mutate_md5(ai, m, uri, nonce, cnonce, nc, qop);
  #ifdef USE_LIB_CRYPTO
    else if (ai->dalgo & HTTP_AUTH_DIGEST_SHA256)
        mod_auth_digest_mutate_sha256(ai, m, uri, nonce, cnonce, nc, qop);
   #ifdef USE_LIB_CRYPTO_SHA512_256
    else if (ai->dalgo & HTTP_AUTH_DIGEST_SHA512_256)
        mod_auth_digest_mutate_sha512_256(ai, m, uri, nonce, cnonce, nc, qop);
   #endif
  #endif
}

static void mod_auth_append_nonce(buffer *b, time_t cur_ts, const struct http_auth_require_t *require, int dalgo, int *rndptr) {
    buffer_append_uint_hex(b, (uintmax_t)cur_ts);
    buffer_append_string_len(b, CONST_STR_LEN(":"));
    const buffer * const nonce_secret = require->nonce_secret;
    int rnd;
    if (NULL == nonce_secret)
        rnd = rndptr ? *rndptr : li_rand_pseudo();
    else { /*(do not directly expose random number generator single value)*/
        rndptr
          ? (void)(rnd = *rndptr)
          : li_rand_pseudo_bytes((unsigned char *)&rnd, sizeof(rnd));
        buffer_append_uint_hex(b, (uintmax_t)rnd);
        buffer_append_string_len(b, CONST_STR_LEN(":"));
    }
    switch (dalgo) {
     #ifdef USE_LIB_CRYPTO
      #ifdef USE_LIB_CRYPTO_SHA512_256
      case HTTP_AUTH_DIGEST_SHA512_256:
        mod_auth_digest_nonce_sha512_256(b, cur_ts, rnd, nonce_secret);
        break;
      #endif
      case HTTP_AUTH_DIGEST_SHA256:
        mod_auth_digest_nonce_sha256(b, cur_ts, rnd, nonce_secret);
        break;
     #endif
      /*case HTTP_AUTH_DIGEST_MD5:*/
      default:
        mod_auth_digest_nonce_md5(b, cur_ts, rnd, nonce_secret);
        break;
    }
}

static void mod_auth_digest_www_authenticate(buffer *b, time_t cur_ts, const struct http_auth_require_t *require, int nonce_stale) {
    int algos = nonce_stale ? nonce_stale : require->algorithm;
    int n = 0;
    int algoid[3];
    unsigned int algolen[3];
    const char *algoname[3];
  #ifdef USE_LIB_CRYPTO
   #ifdef USE_LIB_CRYPTO_SHA512_256
    if (algos & HTTP_AUTH_DIGEST_SHA512_256) {
        algoid[n] = HTTP_AUTH_DIGEST_SHA512_256;
        algoname[n] = "SHA-512-256";
        algolen[n] = sizeof("SHA-512-256")-1;
        ++n;
    }
   #endif
    if (algos & HTTP_AUTH_DIGEST_SHA256) {
        algoid[n] = HTTP_AUTH_DIGEST_SHA256;
        algoname[n] = "SHA-256";
        algolen[n] = sizeof("SHA-256")-1;
        ++n;
    }
  #endif
    if (algos & HTTP_AUTH_DIGEST_MD5) {
        algoid[n] = HTTP_AUTH_DIGEST_MD5;
        algoname[n] = "MD5";
        algolen[n] = sizeof("MD5")-1;
        ++n;
    }

    buffer_clear(b);
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            buffer_append_string_len(b,CONST_STR_LEN("\r\nWWW-Authenticate: "));
        }
        buffer_append_string_len(b, CONST_STR_LEN("Digest realm=\""));
        buffer_append_string_buffer(b, require->realm);
        buffer_append_string_len(b, CONST_STR_LEN("\", charset=\"UTF-8\", algorithm="));
        buffer_append_string_len(b, algoname[i], algolen[i]);
        buffer_append_string_len(b, CONST_STR_LEN(", nonce=\""));
        mod_auth_append_nonce(b, cur_ts, require, algoid[i], NULL);
        buffer_append_string_len(b, CONST_STR_LEN("\", qop=\"auth\""));
        if (nonce_stale) {
            buffer_append_string_len(b, CONST_STR_LEN(", stale=true"));
        }
    }
}

static void mod_auth_digest_authentication_info(buffer *b, time_t cur_ts, const struct http_auth_require_t *require, int dalgo) {
    buffer_clear(b);
    buffer_append_string_len(b, CONST_STR_LEN("nextnonce=\""));
    mod_auth_append_nonce(b, cur_ts, require, dalgo, NULL);
    buffer_append_string_len(b, CONST_STR_LEN("\""));
}

typedef struct {
	const char *key;
	int key_len;
	char **ptr;
} digest_kv;

static handler_t mod_auth_send_401_unauthorized_digest(request_st *r, const struct http_auth_require_t *require, int nonce_stale);

static handler_t mod_auth_check_digest(request_st * const r, void *p_d, const struct http_auth_require_t * const require, const struct http_auth_backend_t * const backend) {
	const buffer *vb = http_header_request_get(r, HTTP_HEADER_AUTHORIZATION, CONST_STR_LEN("Authorization"));

	char *username = NULL;
	char *realm = NULL;
	char *nonce = NULL;
	char *uri = NULL;
	char *algorithm = NULL;
	char *qop = NULL;
	char *cnonce = NULL;
	char *nc = NULL;
	char *respons = NULL;

	char *e, *c;
	int i;
	buffer *b;
	http_auth_info_t ai;
	unsigned char rdigest[HTTP_AUTH_DIGEST_SHA256_BINLEN];


	/* init pointers */
#define S(x) \
	x, sizeof(x)-1, NULL
	digest_kv dkv[10] = {
		{ S("username=") },
		{ S("realm=") },
		{ S("nonce=") },
		{ S("uri=") },
		{ S("algorithm=") },
		{ S("qop=") },
		{ S("cnonce=") },
		{ S("nc=") },
		{ S("response=") },

		{ NULL, 0, NULL }
	};
#undef S

	dkv[0].ptr = &username;
	dkv[1].ptr = &realm;
	dkv[2].ptr = &nonce;
	dkv[3].ptr = &uri;
	dkv[4].ptr = &algorithm;
	dkv[5].ptr = &qop;
	dkv[6].ptr = &cnonce;
	dkv[7].ptr = &nc;
	dkv[8].ptr = &respons;

	if (NULL == backend) {
		log_error(r->conf.errh, __FILE__, __LINE__,
		  "auth.backend not configured for %s", r->uri.path.ptr);
		r->http_status = 500;
		r->handler_module = NULL;
		return HANDLER_FINISHED;
	}

	if (NULL == vb) {
		return mod_auth_send_401_unauthorized_digest(r, require, 0);
	}

	if (!buffer_eq_icase_ssn(vb->ptr, CONST_STR_LEN("Digest "))) {
		return mod_auth_send_401_unauthorized_digest(r, require, 0);
	} else {
		size_t n = buffer_string_length(vb);
	      #ifdef __COVERITY__
		if (n < sizeof("Digest ")-1) {
			return mod_auth_send_400_bad_request(r);
		}
	      #endif
		n -= (sizeof("Digest ")-1);
		b = buffer_init();
		buffer_copy_string_len(b,vb->ptr+sizeof("Digest ")-1,n);
	}

	/* parse credentials from client */
	for (c = b->ptr; *c; c++) {
		/* skip whitespaces */
		while (*c == ' ' || *c == '\t') c++;
		if (!*c) break;

		for (i = 0; dkv[i].key; i++) {
			if ((0 == strncmp(c, dkv[i].key, dkv[i].key_len))) {
				if ((c[dkv[i].key_len] == '"') &&
				    (NULL != (e = strchr(c + dkv[i].key_len + 1, '"')))) {
					/* value with "..." */
					*(dkv[i].ptr) = c + dkv[i].key_len + 1;
					c = e;

					*e = '\0';
				} else if (NULL != (e = strchr(c + dkv[i].key_len, ','))) {
					/* value without "...", terminated by ',' */
					*(dkv[i].ptr) = c + dkv[i].key_len;
					c = e;

					*e = '\0';
				} else {
					/* value without "...", terminated by EOL */
					*(dkv[i].ptr) = c + dkv[i].key_len;
					c += strlen(c) - 1;
				}
				break;
			}
		}
	}

	/* check if everything is transmitted */
	if (!username ||
	    !realm ||
	    !nonce ||
	    !uri ||
	    (qop && (!nc || !cnonce)) ||
	    !respons ) {
		/* missing field */

		log_error(r->conf.errh, __FILE__, __LINE__,
		  "digest: missing field");

		buffer_free(b);
		return mod_auth_send_400_bad_request(r);
	}

	ai.username = username;
	ai.ulen     = strlen(username);
	ai.realm    = realm;
	ai.rlen     = strlen(realm);

	if (!buffer_is_equal_string(require->realm, ai.realm, ai.rlen)) {
		log_error(r->conf.errh, __FILE__, __LINE__,
		  "digest: realm mismatch");
		buffer_free(b);
		return mod_auth_send_401_unauthorized_digest(r, require, 0);
	}

	if (!mod_auth_algorithm_parse(&ai, algorithm)
	    || !(require->algorithm & ai.dalgo & ~HTTP_AUTH_DIGEST_SESS)) {
		log_error(r->conf.errh, __FILE__, __LINE__,
		  "digest: (%s): invalid", algorithm);
		buffer_free(b);
		return mod_auth_send_400_bad_request(r);
	}

	/**
	 * protect the md5-sess against missing cnonce and nonce
	 */
	if ((ai.dalgo & HTTP_AUTH_DIGEST_SESS) && (!nonce || !cnonce)) {
		log_error(r->conf.errh, __FILE__, __LINE__,
		  "digest: (%s): missing field", algorithm);

		buffer_free(b);
		return mod_auth_send_400_bad_request(r);
	}

	{
		size_t resplen = strlen(respons);
		if (0 != http_auth_digest_hex2bin(respons, resplen,
						  rdigest, sizeof(rdigest))
		    || resplen != (ai.dlen << 1)) {
			log_error(r->conf.errh, __FILE__, __LINE__,
			  "digest: (%s): invalid format", respons);
			buffer_free(b);
			return mod_auth_send_400_bad_request(r);
		}
	}

	if (qop && buffer_eq_icase_ss(qop, strlen(qop), CONST_STR_LEN("auth-int"))){
		log_error(r->conf.errh, __FILE__, __LINE__,
		  "digest: qop=auth-int not supported");

		buffer_free(b);
		return mod_auth_send_400_bad_request(r);
	}

	/* detect if attacker is attempting to reuse valid digest for one uri
	 * on a different request uri.  Might also happen if intermediate proxy
	 * altered client request line.  (Altered request would not result in
	 * the same digest as that calculated by the client.)
	 * Internal redirects such as with mod_rewrite will modify request uri.
	 * Reauthentication is done to detect crossing auth realms, but this
	 * uri validation step is bypassed.  r->target_orig is
	 * original request-target sent in client request. */
	{
		const size_t ulen = strlen(uri);
		if (!buffer_is_equal_string(&r->target_orig, uri, ulen)) {
			log_error(r->conf.errh, __FILE__, __LINE__,
			  "digest: auth failed: uri mismatch (%s != %s), IP: %s",
			  r->target_orig.ptr, uri, r->con->dst_addr_buf->ptr);
			buffer_free(b);
			return mod_auth_send_400_bad_request(r);
		}
	}

	/* check age of nonce.  Note, random data is used in nonce generation
	 * in mod_auth_send_401_unauthorized_digest().  If that were replaced
	 * with nanosecond time, then nonce secret would remain unique enough
	 * for the purposes of Digest auth, and would be reproducible (and
	 * verifiable) if nanoseconds were included with seconds as part of the
	 * nonce "timestamp:secret".  However, doing so would expose a high
	 * precision timestamp of the system to attackers.  timestamp in nonce
	 * could theoretically be modified and still produce same md5sum, but
	 * that is highly unlikely within a 10 min (moving) window of valid
	 * time relative to current time (now).
	 * If it is desired to validate that nonces were generated by server,
	 * then specify auth.require = ( ... => ( "secret" => "..." ) )
	 * When secret is specified, then instead of nanoseconds, the random
	 * data value (included for unique nonces) will be exposed in the nonce
	 * along with the timestamp, and the additional secret will be used to
	 * validate that the server generated the nonce using that secret. */
	int send_nextnonce;
	{
		time_t ts = 0;
		const unsigned char * const nonce_uns = (unsigned char *)nonce;
		for (i = 0; i < 8 && light_isxdigit(nonce_uns[i]); ++i) {
			ts = (ts << 4) + hex2int(nonce_uns[i]);
		}
		const time_t cur_ts = log_epoch_secs;
		if (nonce[i] != ':'
		    || ts > cur_ts || cur_ts - ts > 600) { /*(10 mins)*/
			/* nonce is stale; have client regenerate digest */
			buffer_free(b);
			return mod_auth_send_401_unauthorized_digest(r, require, ai.dalgo);
		}

		send_nextnonce = (cur_ts - ts > 540); /*(9 mins)*/

		if (require->nonce_secret) {
			unsigned int rnd = 0;
			for (int j = i+8; i < j && light_isxdigit(nonce_uns[i]); ++i) {
				rnd = (rnd << 4) + hex2int(nonce_uns[i]);
			}
			if (nonce[i] != ':') {
				/* nonce is invalid;
				 * expect extra field w/ require->nonce_secret */
				log_error(r->conf.errh, __FILE__, __LINE__,
				  "digest: nonce invalid");
				buffer_free(b);
				return mod_auth_send_400_bad_request(r);
			}
			buffer * const tb = r->tmp_buf;
			buffer_clear(tb);
			mod_auth_append_nonce(tb, cur_ts, require, ai.dalgo, (int *)&rnd);
			if (!buffer_eq_slen(tb, nonce, strlen(nonce))) {
				/* nonce not generated using current require->nonce_secret */
				log_error(r->conf.errh, __FILE__, __LINE__,
				  "digest: nonce mismatch");
				buffer_free(b);
				return mod_auth_send_401_unauthorized_digest(r, require, 0);
			}
		}
	}

	handler_t rc = HANDLER_UNSET;

	plugin_data * const p = p_d;
	splay_tree ** sptree = p->conf.auth_cache
	  ? &p->conf.auth_cache->sptree
	  : NULL;
	http_auth_cache_entry *ae = NULL;
	int ndx = -1;
	if (sptree) {
		ndx = http_auth_cache_hash(require, ai.username, ai.ulen);
		ae = http_auth_cache_query(sptree, ndx);
		if (ae && ae->require == require
		    && ae->dalgo == ai.dalgo
		    && ae->dlen == ai.dlen
		    && ae->ulen == ai.ulen
		    && 0 == memcmp(ae->username, ai.username, ai.ulen)) {
			rc = HANDLER_GO_ON;
			memcpy(ai.digest, ae->pwdigest, ai.dlen);
		}
		else /*(not found or hash collision)*/
			ae = NULL;
	}

	if (HANDLER_UNSET == rc)
		rc = backend->digest(r, backend->p_d, &ai);

	switch (rc) {
	case HANDLER_GO_ON:
		break;
	case HANDLER_WAIT_FOR_EVENT:
		buffer_free(b);
		return HANDLER_WAIT_FOR_EVENT;
	case HANDLER_FINISHED:
		buffer_free(b);
		return HANDLER_FINISHED;
	case HANDLER_ERROR:
	default:
		r->keep_alive = 0; /*(disable keep-alive if unknown user)*/
		buffer_free(b);
		return mod_auth_send_401_unauthorized_digest(r, require, 0);
	}

	if (sptree && NULL == ae) { /*(cache digest from backend)*/
		ae = http_auth_cache_entry_init(require, ai.dalgo, ai.username, ai.ulen,
		                                (char *)ai.digest, ai.dlen);
		http_auth_cache_insert(sptree, ndx, ae, http_auth_cache_entry_free);
	}

	const char *m = get_http_method_name(r->http_method);
	force_assert(m);

	mod_auth_digest_mutate(&ai,m,uri,nonce,cnonce,nc,qop);

	if (!http_auth_const_time_memeq(rdigest, ai.digest, ai.dlen)) {
		/* digest not ok */
		log_error(r->conf.errh, __FILE__, __LINE__,
		  "digest: auth failed for %s: wrong password, IP: %s",
		  username, r->con->dst_addr_buf->ptr);
		r->keep_alive = 0; /*(disable keep-alive if bad password)*/

		buffer_free(b);
		return mod_auth_send_401_unauthorized_digest(r, require, 0);
	}

	/* value is our allow-rules */
	if (!http_auth_match_rules(require, username, NULL, NULL)) {
		buffer_free(b);
		return mod_auth_send_401_unauthorized_digest(r, require, 0);
	}

	if (send_nextnonce) {
			/*(send nextnonce when expiration is approaching)*/
			buffer * const tb = r->tmp_buf;
			const time_t cur_ts = log_epoch_secs;
			mod_auth_digest_authentication_info(tb, cur_ts, require, ai.dalgo);
			http_header_response_set(r, HTTP_HEADER_OTHER,
			                         CONST_STR_LEN("Authentication-Info"),
			                         CONST_BUF_LEN(tb));
	}

	http_auth_setenv(r, ai.username, ai.ulen, CONST_STR_LEN("Digest"));

	buffer_free(b);

	return HANDLER_GO_ON;
}

static handler_t mod_auth_send_401_unauthorized_digest(request_st * const r, const struct http_auth_require_t * const require, int nonce_stale) {
	buffer * const tb = r->tmp_buf;
	mod_auth_digest_www_authenticate(tb, log_epoch_secs, require, nonce_stale);
	http_header_response_set(r, HTTP_HEADER_OTHER, CONST_STR_LEN("WWW-Authenticate"), CONST_BUF_LEN(tb));

	r->http_status = 401;
	r->handler_module = NULL;
	return HANDLER_FINISHED;
}

static handler_t mod_auth_check_extern(request_st * const r, void *p_d, const struct http_auth_require_t * const require, const struct http_auth_backend_t * const backend) {
	/* require REMOTE_USER already set */
	const buffer *vb = http_header_env_get(r, CONST_STR_LEN("REMOTE_USER"));
	UNUSED(p_d);
	UNUSED(backend);
	if (NULL != vb && http_auth_match_rules(require, vb->ptr, NULL, NULL)) {
		return HANDLER_GO_ON;
	} else {
		r->http_status = 401;
		r->handler_module = NULL;
		return HANDLER_FINISHED;
	}
}