/*
 * authkeys.c - routines to manage the storage of authentication keys
 */
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

#include <math.h>
#include <stdio.h>

#include "ntp.h"
#include "ntp_fp.h"
#include "ntpd.h"
#include "ntp_lists.h"
#include "ntp_string.h"
#include "ntp_malloc.h"
#include "ntp_stdlib.h"
#include "ntp_keyacc.h"

/*
 * Structure to store keys in in the hash table.
 */
typedef struct savekey symkey;

struct savekey {
	symkey *	hlink;		/* next in hash bucket */
	DECL_DLIST_LINK(symkey, llink);	/* for overall & free lists */
	u_char *	secret;		/* shared secret */
	KeyAccT *	keyacclist;	/* Private key access list */
	u_long		lifetime;	/* remaining lifetime */
	keyid_t		keyid;		/* key identifier */
	u_short		type;		/* OpenSSL digest NID */
	size_t		secretsize;	/* secret octets */
	u_short		flags;		/* KEY_ flags that wave */
};

/* define the payload region of symkey beyond the list pointers */
#define symkey_payload	secret

#define	KEY_TRUSTED	0x001	/* this key is trusted */

#ifdef DEBUG
typedef struct symkey_alloc_tag symkey_alloc;

struct symkey_alloc_tag {
	symkey_alloc *	link;
	void *		mem;		/* enable free() atexit */
};

symkey_alloc *	authallocs;
#endif	/* DEBUG */

static u_short	auth_log2(size_t);
static void		auth_resize_hashtable(void);
static void		allocsymkey(keyid_t,	u_short,
				    u_short, u_long, size_t, u_char *, KeyAccT *);
static void		freesymkey(symkey *);
#ifdef DEBUG
static void		free_auth_mem(void);
#endif

symkey	key_listhead;		/* list of all in-use keys */;
/*
 * The hash table. This is indexed by the low order bits of the
 * keyid. We make this fairly big for potentially busy servers.
 */
#define	DEF_AUTHHASHSIZE	64
/*#define	HASHMASK	((HASHSIZE)-1)*/
#define	KEYHASH(keyid)	((keyid) & authhashmask)

int	authhashdisabled;
u_short	authhashbuckets = DEF_AUTHHASHSIZE;
u_short authhashmask = DEF_AUTHHASHSIZE - 1;
symkey **key_hash;

u_long authkeynotfound;		/* keys not found */
u_long authkeylookups;		/* calls to lookup keys */
u_long authnumkeys;		/* number of active keys */
u_long authkeyexpired;		/* key lifetime expirations */
u_long authkeyuncached;		/* cache misses */
u_long authnokey;		/* calls to encrypt with no key */
u_long authencryptions;		/* calls to encrypt */
u_long authdecryptions;		/* calls to decrypt */

/*
 * Storage for free symkey structures.  We malloc() such things but
 * never free them.
 */
symkey *authfreekeys;
int authnumfreekeys;

#define	MEMINC	16		/* number of new free ones to get */

/*
 * The key cache. We cache the last key we looked at here.
 * Note: this should hold the last *trusted* key. Also the
 * cache is only loaded when the digest type / MAC algorithm
 * is valid.
 */
keyid_t	cache_keyid;		/* key identifier */
u_char *cache_secret;		/* secret */
size_t	cache_secretsize;	/* secret length */
int	cache_type;		/* OpenSSL digest NID */
u_short cache_flags;		/* flags that wave */
KeyAccT *cache_keyacclist;	/* key access list */

/* --------------------------------------------------------------------
 * manage key access lists
 * --------------------------------------------------------------------
 */
/* allocate and populate new access node and pushes it on the list.
 * Returns the new head.
 */
KeyAccT*
keyacc_new_push(
	KeyAccT          * head,
	const sockaddr_u * addr,
	unsigned int	   subnetbits
	)
{
	KeyAccT *	node = emalloc(sizeof(KeyAccT));
	
	memcpy(&node->addr, addr, sizeof(sockaddr_u));
	node->subnetbits = subnetbits;
	node->next = head;

	return node;
}

/* ----------------------------------------------------------------- */
/* pop and deallocate the first node of a list of access nodes, if
 * the list is not empty. Returns the tail of the list.
 */
KeyAccT*
keyacc_pop_free(
	KeyAccT *head
	)
{
	KeyAccT *	next = NULL;
	if (head) {
		next = head->next;
		free(head);
	}
	return next;
}

/* ----------------------------------------------------------------- */
/* deallocate the list; returns an empty list. */
KeyAccT*
keyacc_all_free(
	KeyAccT * head
	)
{
	while (head)
		head = keyacc_pop_free(head);
	return head;
}

/* ----------------------------------------------------------------- */
/* scan a list to see if it contains a given address. Return the
 * default result value in case of an empty list.
 */
int /*BOOL*/
keyacc_contains(
	const KeyAccT    *head,
	const sockaddr_u *addr,
	int               defv)
{
	if (head) {
		do {
			if (keyacc_amatch(&head->addr, addr,
					  head->subnetbits))
				return TRUE;
		} while (NULL != (head = head->next));
		return FALSE;
	} else {
		return !!defv;
	}
}

#if CHAR_BIT != 8
# error "don't know how to handle bytes with that bit size"
#endif

/* ----------------------------------------------------------------- */
/* check two addresses for a match, taking a prefix length into account
 * when doing the compare.
 *
 * The ISC lib contains a similar function with not entirely specified
 * semantics, so it seemed somewhat cleaner to do this from scratch.
 *
 * Note 1: It *is* assumed that the addresses are stored in network byte
 * order, that is, most significant byte first!
 *
 * Note 2: "no address" compares unequal to all other addresses, even to
 * itself. This has the same semantics as NaNs have for floats: *any*
 * relational or equality operation involving a NaN returns FALSE, even
 * equality with itself. "no address" is either a NULL pointer argument
 * or an address of type AF_UNSPEC.
 */
int/*BOOL*/
keyacc_amatch(
	const sockaddr_u *	a1,
	const sockaddr_u *	a2,
	unsigned int		mbits
	)
{
	const uint8_t * pm1;
	const uint8_t * pm2;
	uint8_t         msk;
	unsigned int    len;

	/* 1st check: If any address is not an address, it's inequal. */
	if ( !a1 || (AF_UNSPEC == AF(a1)) ||
	     !a2 || (AF_UNSPEC == AF(a2))  )
		return FALSE;

	/* We could check pointers for equality here and shortcut the
	 * other checks if we find object identity. But that use case is
	 * too rare to care for it.
	 */
	
	/* 2nd check: Address families must be the same. */
	if (AF(a1) != AF(a2))
		return FALSE;

	/* type check: address family determines buffer & size */
	switch (AF(a1)) {
	case AF_INET:
		/* IPv4 is easy: clamp size, get byte pointers */
		if (mbits > sizeof(NSRCADR(a1)) * 8)
			mbits = sizeof(NSRCADR(a1)) * 8;
		pm1 = (const void*)&NSRCADR(a1);
		pm2 = (const void*)&NSRCADR(a2);
		break;

	case AF_INET6:
		/* IPv6 is slightly different: Both scopes must match,
		 * too, before we even consider doing a match!
		 */
		if ( ! SCOPE_EQ(a1, a2))
			return FALSE;
		if (mbits > sizeof(NSRCADR6(a1)) * 8)
			mbits = sizeof(NSRCADR6(a1)) * 8;
		pm1 = (const void*)&NSRCADR6(a1);
		pm2 = (const void*)&NSRCADR6(a2);
		break;

	default:
		/* don't know how to compare that!?! */
		return FALSE;
	}

	/* Split bit length into byte length and partial byte mask.
	 * Note that the byte mask extends from the MSB of a byte down,
	 * and that zero shift (--> mbits % 8 == 0) results in an
	 * all-zero mask.
	 */
	msk = 0xFFu ^ (0xFFu >> (mbits & 7));
	len = mbits >> 3;

	/* 3rd check: Do memcmp() over full bytes, if any */
	if (len && memcmp(pm1, pm2, len))
		return FALSE;

	/* 4th check: compare last incomplete byte, if any */
	if (msk && ((pm1[len] ^ pm2[len]) & msk))
		return FALSE;

	/* If none of the above failed, we're successfully through. */
	return TRUE;
}

/*
 * init_auth - initialize internal data
 */
void
init_auth(void)
{
	size_t newalloc;

	/*
	 * Initialize hash table and free list
	 */
	newalloc = authhashbuckets * sizeof(key_hash[0]);

	key_hash = erealloc(key_hash, newalloc);
	memset(key_hash, '\0', newalloc);

	INIT_DLIST(key_listhead, llink);

#ifdef DEBUG
	atexit(&free_auth_mem);
#endif
}


/*
 * free_auth_mem - assist in leak detection by freeing all dynamic
 *		   allocations from this module.
 */
#ifdef DEBUG
static void
free_auth_mem(void)
{
	symkey *	sk;
	symkey_alloc *	alloc;
	symkey_alloc *	next_alloc;

	while (NULL != (sk = HEAD_DLIST(key_listhead, llink))) {
		freesymkey(sk);
	}
	free(key_hash);
	key_hash = NULL;
	cache_keyid = 0;
	cache_flags = 0;
	cache_keyacclist = NULL;
	for (alloc = authallocs; alloc != NULL; alloc = next_alloc) {
		next_alloc = alloc->link;
		free(alloc->mem);	
	}
	authfreekeys = NULL;
	authnumfreekeys = 0;
}
#endif	/* DEBUG */


/*
 * auth_moremem - get some more free key structures
 */
void
auth_moremem(
	int	keycount
	)
{
	symkey *	sk;
	int		i;
#ifdef DEBUG
	void *		base;
	symkey_alloc *	allocrec;
# define MOREMEM_EXTRA_ALLOC	(sizeof(*allocrec))
#else
# define MOREMEM_EXTRA_ALLOC	(0)
#endif

	i = (keycount > 0)
		? keycount
		: MEMINC;
	sk = eallocarrayxz(i, sizeof(*sk), MOREMEM_EXTRA_ALLOC);
#ifdef DEBUG
	base = sk;
#endif
	authnumfreekeys += i;

	for (; i > 0; i--, sk++) {
		LINK_SLIST(authfreekeys, sk, llink.f);
	}

#ifdef DEBUG
	allocrec = (void *)sk;
	allocrec->mem = base;
	LINK_SLIST(authallocs, allocrec, link);
#endif
}


/*
 * auth_prealloc_symkeys
 */
void
auth_prealloc_symkeys(
	int	keycount
	)
{
	int	allocated;
	int	additional;

	allocated = authnumkeys + authnumfreekeys;
	additional = keycount - allocated;
	if (additional > 0)
		auth_moremem(additional);
	auth_resize_hashtable();
}


static u_short
auth_log2(size_t x)
{
	/*
	** bithack to calculate floor(log2(x))
	**
	** This assumes
	**   - (sizeof(size_t) is a power of two
	**   - CHAR_BITS is a power of two
	**   - returning zero for arguments <= 0 is OK.
	**
	** Does only shifts, masks and sums in integer arithmetic in
	** log2(CHAR_BIT*sizeof(size_t)) steps. (that is, 5/6 steps for
	** 32bit/64bit size_t)
	*/
	int	s;
	int	r = 0;
	size_t  m = ~(size_t)0;

	for (s = sizeof(size_t) / 2 * CHAR_BIT; s != 0; s >>= 1) {
		m <<= s;
		if (x & m)
			r += s;
		else
			x <<= s;
	}
	return (u_short)r;
}

int/*BOOL*/
ipaddr_match_masked(const sockaddr_u *,const sockaddr_u *,
		    unsigned int mbits);

static void
authcache_flush_id(
	keyid_t id
	)
{
	if (cache_keyid == id) {
		cache_keyid = 0;
		cache_type = 0;
		cache_flags = 0;
		cache_secret = NULL;
		cache_secretsize = 0;
		cache_keyacclist = NULL;
	}
}


/*
 * auth_resize_hashtable
 *
 * Size hash table to average 4 or fewer entries per bucket initially,
 * within the bounds of at least 4 and no more than 15 bits for the hash
 * table index.  Populate the hash table.
 */
static void
auth_resize_hashtable(void)
{
	u_long		totalkeys;
	u_short		hashbits;
	u_short		hash;
	size_t		newalloc;
	symkey *	sk;

	totalkeys = authnumkeys + authnumfreekeys;
	hashbits = auth_log2(totalkeys / 4) + 1;
	hashbits = max(4, hashbits);
	hashbits = min(15, hashbits);

	authhashbuckets = 1 << hashbits;
	authhashmask = authhashbuckets - 1;
	newalloc = authhashbuckets * sizeof(key_hash[0]);

	key_hash = erealloc(key_hash, newalloc);
	memset(key_hash, '\0', newalloc);

	ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
		hash = KEYHASH(sk->keyid);
		LINK_SLIST(key_hash[hash], sk, hlink);
	ITER_DLIST_END()
}


/*
 * allocsymkey - common code to allocate and link in symkey
 *
 * secret must be allocated with a free-compatible allocator.  It is
 * owned by the referring symkey structure, and will be free()d by
 * freesymkey().
 */
static void
allocsymkey(
	keyid_t		id,
	u_short		flags,
	u_short		type,
	u_long		lifetime,
	size_t		secretsize,
	u_char *	secret,
	KeyAccT *	ka
	)
{
	symkey *	sk;
	symkey **	bucket;

	bucket = &key_hash[KEYHASH(id)];


	if (authnumfreekeys < 1)
		auth_moremem(-1);
	UNLINK_HEAD_SLIST(sk, authfreekeys, llink.f);
	DEBUG_ENSURE(sk != NULL);
	sk->keyid = id;
	sk->flags = flags;
	sk->type = type;
	sk->secretsize = secretsize;
	sk->secret = secret;
	sk->keyacclist = ka;
	sk->lifetime = lifetime;
	LINK_SLIST(*bucket, sk, hlink);
	LINK_TAIL_DLIST(key_listhead, sk, llink);
	authnumfreekeys--;
	authnumkeys++;
}


/*
 * freesymkey - common code to remove a symkey and recycle its entry.
 */
static void
freesymkey(
	symkey *	sk
	)
{
	symkey **	bucket;
	symkey *	unlinked;

	if (NULL == sk)
		return;

	authcache_flush_id(sk->keyid);
	keyacc_all_free(sk->keyacclist);
	
	bucket = &key_hash[KEYHASH(sk->keyid)];
	if (sk->secret != NULL) {
		memset(sk->secret, '\0', sk->secretsize);
		free(sk->secret);
	}
	UNLINK_SLIST(unlinked, *bucket, sk, hlink, symkey);
	DEBUG_ENSURE(sk == unlinked);
	UNLINK_DLIST(sk, llink);
	memset((char *)sk + offsetof(symkey, symkey_payload), '\0',
	       sizeof(*sk) - offsetof(symkey, symkey_payload));
	LINK_SLIST(authfreekeys, sk, llink.f);
	authnumkeys--;
	authnumfreekeys++;
}


/*
 * auth_findkey - find a key in the hash table
 */
struct savekey *
auth_findkey(
	keyid_t		id
	)
{
	symkey *	sk;

	for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink)
		if (id == sk->keyid)
			return sk;
	return NULL;
}


/*
 * auth_havekey - return TRUE if the key id is zero or known. The
 * key needs not to be trusted.
 */
int
auth_havekey(
	keyid_t		id
	)
{
	return
	    (0           == id) ||
	    (cache_keyid == id) ||
	    (NULL        != auth_findkey(id));
}


/*
 * authhavekey - return TRUE and cache the key, if zero or both known
 *		 and trusted.
 */
int
authhavekey(
	keyid_t		id
	)
{
	symkey *	sk;

	authkeylookups++;
	if (0 == id || cache_keyid == id)
		return !!(KEY_TRUSTED & cache_flags);

	/*
	 * Search the bin for the key. If not found, or found but the key
	 * type is zero, somebody marked it trusted without specifying a
	 * key or key type. In this case consider the key missing.
	 */
	authkeyuncached++;
	sk = auth_findkey(id);
	if ((sk == NULL) || (sk->type == 0)) {
		authkeynotfound++;
		return FALSE;
	}

	/*
	 * If the key is not trusted, the key is not considered found.
	 */
	if ( ! (KEY_TRUSTED & sk->flags)) {
		authnokey++;
		return FALSE;
	}

	/*
	 * The key is found and trusted. Initialize the key cache.
	 */
	cache_keyid = sk->keyid;
	cache_type = sk->type;
	cache_flags = sk->flags;
	cache_secret = sk->secret;
	cache_secretsize = sk->secretsize;
	cache_keyacclist = sk->keyacclist;

	return TRUE;
}


/*
 * authtrust - declare a key to be trusted/untrusted
 */
void
authtrust(
	keyid_t		id,
	u_long		trust
	)
{
	symkey *	sk;
	u_long		lifetime;

	/*
	 * Search bin for key; if it does not exist and is untrusted,
	 * forget it.
	 */

	sk = auth_findkey(id);
	if (!trust && sk == NULL)
		return;

	/*
	 * There are two conditions remaining. Either it does not
	 * exist and is to be trusted or it does exist and is or is
	 * not to be trusted.
	 */	
	if (sk != NULL) {
		/*
		 * Key exists. If it is to be trusted, say so and update
		 * its lifetime. If no longer trusted, return it to the
		 * free list. Flush the cache first to be sure there are
		 * no discrepancies.
		 */
		authcache_flush_id(id);
		if (trust > 0) {
			sk->flags |= KEY_TRUSTED;
			if (trust > 1)
				sk->lifetime = current_time + trust;
			else
				sk->lifetime = 0;
		} else {
			freesymkey(sk);
		}
		return;
	}

	/*
	 * keyid is not present, but the is to be trusted.  We allocate
	 * a new key, but do not specify a key type or secret.
	 */
	if (trust > 1) {
		lifetime = current_time + trust;
	} else {
		lifetime = 0;
	}
	allocsymkey(id, KEY_TRUSTED, 0, lifetime, 0, NULL, NULL);
}


/*
 * authistrusted - determine whether a key is trusted
 */
int
authistrusted(
	keyid_t		id
	)
{
	symkey *	sk;

	if (id == cache_keyid)
		return !!(KEY_TRUSTED & cache_flags);

	authkeyuncached++;
	sk = auth_findkey(id);
	if (sk == NULL || !(KEY_TRUSTED & sk->flags)) {
		authkeynotfound++;
		return FALSE;
	}
	return TRUE;
}


/*
 * authistrustedip - determine if the IP is OK for the keyid
 */
 int
 authistrustedip(
 	keyid_t		keyno,
	sockaddr_u *	sau
	)
{
	symkey *	sk;

	if (keyno == cache_keyid) {
		return (KEY_TRUSTED & cache_flags) &&
		    keyacc_contains(cache_keyacclist, sau, TRUE);
	}

	if (NULL != (sk = auth_findkey(keyno))) {
		authkeyuncached++;
		return (KEY_TRUSTED & sk->flags) &&
		    keyacc_contains(sk->keyacclist, sau, TRUE);
	}
	
	authkeynotfound++;
	return FALSE;    
}

/* Note: There are two locations below where 'strncpy()' is used. While
 * this function is a hazard by itself, it's essential that it is used
 * here. Bug 1243 involved that the secret was filled with NUL bytes
 * after the first NUL encountered, and 'strlcpy()' simply does NOT have
 * this behaviour. So disabling the fix and reverting to the buggy
 * behaviour due to compatibility issues MUST also fill with NUL and
 * this needs 'strncpy'. Also, the secret is managed as a byte blob of a
 * given size, and eventually truncating it and replacing the last byte
 * with a NUL would be a bug.
 * perlinger@ntp.org 2015-10-10
 */
void
MD5auth_setkey(
	keyid_t keyno,
	int	keytype,
	const u_char *key,
	size_t secretsize,
	KeyAccT *ka
	)
{
	symkey *	sk;
	u_char *	secret;
	
	DEBUG_ENSURE(keytype <= USHRT_MAX);
	DEBUG_ENSURE(secretsize < 4 * 1024);
	/*
	 * See if we already have the key.  If so just stick in the
	 * new value.
	 */
	sk = auth_findkey(keyno);
	if (sk != NULL && keyno == sk->keyid) {
			/* TALOS-CAN-0054: make sure we have a new buffer! */
		if (NULL != sk->secret) {
			memset(sk->secret, 0, sk->secretsize);
			free(sk->secret);
		}
		sk->secret = emalloc(secretsize + 1);
		sk->type = (u_short)keytype;
		sk->secretsize = secretsize;
		/* make sure access lists don't leak here! */
		if (ka != sk->keyacclist) {
			keyacc_all_free(sk->keyacclist);
			sk->keyacclist = ka;
		}
#ifndef DISABLE_BUG1243_FIX
		memcpy(sk->secret, key, secretsize);
#else
		/* >MUST< use 'strncpy()' here! See above! */
		strncpy((char *)sk->secret, (const char *)key,
			secretsize);
#endif
		authcache_flush_id(keyno);
		return;
	}

	/*
	 * Need to allocate new structure.  Do it.
	 */
	secret = emalloc(secretsize + 1);
#ifndef DISABLE_BUG1243_FIX
	memcpy(secret, key, secretsize);
#else
	/* >MUST< use 'strncpy()' here! See above! */
	strncpy((char *)secret, (const char *)key, secretsize);
#endif
	allocsymkey(keyno, 0, (u_short)keytype, 0,
		    secretsize, secret, ka);
#ifdef DEBUG
	if (debug >= 4) {
		size_t	j;

		printf("auth_setkey: key %d type %d len %d ", (int)keyno,
		    keytype, (int)secretsize);
		for (j = 0; j < secretsize; j++) {
			printf("%02x", secret[j]);
		}
		printf("\n");
	}	
#endif
}


/*
 * auth_delkeys - delete non-autokey untrusted keys, and clear all info
 *                except the trusted bit of non-autokey trusted keys, in
 *		  preparation for rereading the keys file.
 */
void
auth_delkeys(void)
{
	symkey *	sk;

	ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
		if (sk->keyid > NTP_MAXKEY) {	/* autokey */
			continue;
		}

		/*
		 * Don't lose info as to which keys are trusted. Make
		 * sure there are no dangling pointers!
		 */
		if (KEY_TRUSTED & sk->flags) {
			if (sk->secret != NULL) {
				memset(sk->secret, 0, sk->secretsize);
				free(sk->secret);
				sk->secret = NULL; /* TALOS-CAN-0054 */
			}
			sk->keyacclist = keyacc_all_free(sk->keyacclist);
			sk->secretsize = 0;
			sk->lifetime = 0;
		} else {
			freesymkey(sk);
		}
	ITER_DLIST_END()
}


/*
 * auth_agekeys - delete keys whose lifetimes have expired
 */
void
auth_agekeys(void)
{
	symkey *	sk;

	ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
		if (sk->lifetime > 0 && current_time > sk->lifetime) {
			freesymkey(sk);
			authkeyexpired++;
		}
	ITER_DLIST_END()
	DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n",
		    current_time, authnumkeys, authkeyexpired));
}


/*
 * authencrypt - generate message authenticator
 *
 * Returns length of authenticator field, zero if key not found.
 */
size_t
authencrypt(
	keyid_t		keyno,
	u_int32 *	pkt,
	size_t		length
	)
{
	/*
	 * A zero key identifier means the sender has not verified
	 * the last message was correctly authenticated. The MAC
	 * consists of a single word with value zero.
	 */
	authencryptions++;
	pkt[length / 4] = htonl(keyno);
	if (0 == keyno) {
		return 4;
	}
	if (!authhavekey(keyno)) {
		return 0;
	}

	return MD5authencrypt(cache_type,
			      cache_secret, cache_secretsize,
			      pkt, length);
}


/*
 * authdecrypt - verify message authenticator
 *
 * Returns TRUE if authenticator valid, FALSE if invalid or not found.
 */
int
authdecrypt(
	keyid_t		keyno,
	u_int32 *	pkt,
	size_t		length,
	size_t		size
	)
{
	/*
	 * A zero key identifier means the sender has not verified
	 * the last message was correctly authenticated.  For our
	 * purpose this is an invalid authenticator.
	 */
	authdecryptions++;
	if (0 == keyno || !authhavekey(keyno) || size < 4) {
		return FALSE;
	}

	return MD5authdecrypt(cache_type,
			      cache_secret, cache_secretsize,
			      pkt, length, size);
}