revocations.c - external/github.com/google/hiba - Git at Google

 /*
  * Copyright 2022 The HIBA Authors
  *
  * Use of this source code is governed by a BSD-style
  * license that can be found in the LICENSE file or at
  * https://developers.google.com/open-source/licenses/bsd
  */
 #include <inttypes.h>
 #include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
 #include <time.h>

 #include "errors.h"
 #include "log.h"
 #include "revocations.h"

 #define HIBA_CURRENT_GRL_VERSION	0x1
 #define HIBA_MIN_SUPPORTED_GRL_VERSION	0x1

 /* Stores a list of all the certificates with revoked grants.
  * This structure is meant to be mapped directly on top of a mmapped revocation
  * file on top of the serial list section (see PROTOCOL.grl). */
 struct serials {
 	u_int64_t serial;
 	u_int64_t offset;
 } __attribute__((packed));

 /* Parsed list of revocations. */
 struct parsed_revocations {
 	u_int64_t serial;
 	u_int16_t size;
 	char *map;

 	struct parsed_revocations *next;
 };

 /* In memory representation of the GRL.
  * The 'parsed' field is a linked list to revocations entries. The first
  * element of that list (if it exists) is the head and doesn't contain any
  * revocation information. */
 struct hibagrl {
 	u_int32_t version;
 	u_int32_t min_version;
 	u_int64_t timestamp;
 	u_int32_t n_serials;
 	u_int64_t bitmaps_size;
 	char *comment;

 	const struct serials *serials;
 	const unsigned char *bitmaps;

 	struct parsed_revocations *parsed;
 };

 void
 hibagrl_free(struct hibagrl *grl) {
 	struct parsed_revocations *r;

 	if (grl == NULL)
 		return;

 	r = grl->parsed;
 	while (r != NULL) {
 		struct parsed_revocations *tbd = r;
 		r = r->next;
 		free(tbd->map);
 		free(tbd);
 	}

 	free(grl->comment);
 	free(grl);
 }

 struct hibagrl*
 hibagrl_new() {
 	struct hibagrl *grl = calloc(sizeof(struct hibagrl), 1);
 	return grl;
 }

 void
 hibagrl_init(struct hibagrl *grl, const char *comment) {
 	if (grl == NULL)
 		return;

 	memset(grl, 0, sizeof(struct hibagrl));
 	grl->version = HIBA_CURRENT_GRL_VERSION;
 	grl->min_version = HIBA_MIN_SUPPORTED_GRL_VERSION;
 	grl->comment = strdup(comment);

 	/* Allocate the head of the parsed linked list to show this is an
 	 * editable GRL. */
 	grl->parsed = calloc(1, sizeof(struct parsed_revocations));
 }

 int
 hibagrl_version(const struct hibagrl *grl) {
 	if (grl == NULL) {
 		return HIBA_BAD_PARAMS;
 	}
 	return grl->version;
 }

 const char*
 hibagrl_comment(const struct hibagrl *grl) {
 	if (grl == NULL) {
 		return hiba_err(-HIBA_BAD_PARAMS);
 	}
 	return grl->comment;
 }

 u_int64_t
 hibagrl_timestamp(const struct hibagrl *grl) {
 	if (grl == NULL) {
 		return 0;
 	}
 	return grl->timestamp;
 }

 u_int64_t
 hibagrl_serials_count(const struct hibagrl *grl) {
 	if (grl == NULL) {
 		return 0;
 	}
 	return grl->n_serials;
 }

 int
 hibagrl_decode(struct hibagrl *grl, struct sshbuf *blob) {
 	int ret;
 	u_int32_t magic;
 	u_int64_t serials_section_size;

 	if (grl == NULL || blob == NULL)
 		return HIBA_BAD_PARAMS;

 	memset(grl, 0, sizeof(struct hibagrl));

 	if ((ret = sshbuf_get_u32(blob, &magic)) < 0) {
 		debug3("hibagrl_decode: sshbuf_get_u32 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if (magic != HIBA_GRL_MAGIC) {
 		return HIBA_INVALID_GRL;
 	}

 	if ((ret = sshbuf_get_u32(blob, &grl->version)) != 0) {
 		debug3("hibagrl_decode: sshbuf_get_u32 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if ((ret = sshbuf_get_u32(blob, &grl->min_version)) != 0) {
 		debug3("hibagrl_decode: sshbuf_get_u32 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if ((ret = sshbuf_get_u64(blob, &grl->timestamp)) != 0) {
 		debug3("hibagrl_decode: sshbuf_get_u64 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if ((ret = sshbuf_get_cstring(blob, &grl->comment, NULL)) != 0) {
 		debug3("hibagrl_decode: sshbuf_get_cstring returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}

 	/* Get the serials section. */
 	if ((ret = sshbuf_get_u64(blob, &serials_section_size)) != 0) {
 		debug3("hibagrl_decode: sshbuf_get_u64 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	grl->n_serials = serials_section_size / sizeof(struct serials);
 	debug2("hibagrl_decode: serials_section_size = %" PRIu64, serials_section_size);
 	grl->serials = (const struct serials *)sshbuf_ptr(blob);
 	if (log_level_get() >= SYSLOG_LEVEL_DEBUG3) {
 		debug3("hibagrl_decode: serial list section content");
 		sshbuf_dump_data(sshbuf_ptr(blob), serials_section_size, stderr);
 	}
 	if ((ret = sshbuf_consume(blob, serials_section_size)) != 0) {
 		debug3("hibagrl_decode: sshbuf_consume returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}

 	/* Get the bitmaps section. */
 	if ((ret = sshbuf_get_u64(blob, &grl->bitmaps_size)) != 0) {
 		debug3("hibagrl_decode: sshbuf_get_u64 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	debug2("hibagrl_decode: bitmaps_section_size = %" PRIu64, grl->bitmaps_size);
 	grl->bitmaps = sshbuf_ptr(blob);
 	if (log_level_get() >= SYSLOG_LEVEL_DEBUG3) {
 		debug3("hibagrl_decode: bitmap section content");
 		sshbuf_dump_data(sshbuf_ptr(blob), grl->bitmaps_size, stderr);
 	}
 	if ((ret = sshbuf_consume(blob, grl->bitmaps_size)) != 0) {
 		debug3("hibagrl_decode: sshbuf_consume returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}

 	if ((ret = sshbuf_get_u32(blob, &magic)) < 0) {
 		debug3("hibagrl_decode: sshbuf_get_u32 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if (magic != HIBA_GRL_MAGIC) {
 		return HIBA_INVALID_GRL;
 	}

 	/* The parsed_revocations field is left NULL on purpose and will only be
 	 * actually parsed from serials/bitmaps sections when needed using
 	 * hibagrl_map(). */
 	debug2("hibagrl_decode: grl->n_serials = %" PRIu32, grl->n_serials);

 	return HIBA_OK;
 }

 int
 hibagrl_map(struct hibagrl *grl) {
 	u_int64_t i = 0;
 	struct parsed_revocations *r;

 	if (grl == NULL)
 		return HIBA_BAD_PARAMS;
 	if (grl->parsed != NULL)
 		return HIBA_BAD_PARAMS;

 	/* The first parsed_revocation doesn't count, it is only used as the
 	 * head of the linked list. */
 	grl->parsed = calloc(1, sizeof(struct parsed_revocations));
 	r = grl->parsed;

 	debug("hibagrl_map: mapping %" PRIu32 " serials", grl->n_serials);
 	for (i = 0; i < grl->n_serials; ++i) {
 		u_int64_t offset;
 		u_int64_t next_offset = grl->bitmaps_size;

 		r->next = calloc(1, sizeof(struct parsed_revocations));
 		r = r->next;
 		r->serial = PEEK_U64(&grl->serials[i].serial);
 		offset = PEEK_U64(&grl->serials[i].offset);

 		if (i+1 < grl->n_serials) {
 			next_offset = PEEK_U64(&grl->serials[i+1].offset);
 		}
 		r->size = next_offset - offset;
 		r->map = calloc(1, r->size);
 		memcpy(r->map, grl->bitmaps + offset, r->size);
 	}

 	/* Nullify mmapped sections since we now have an editable GRL. */
 	grl->serials = NULL;
 	grl->bitmaps = NULL;
 	grl->bitmaps_size = 0;

 	return 0;
 }

 int
 hibagrl_encode(const struct hibagrl *grl, struct sshbuf *blob) {
 	int ret;
 	struct parsed_revocations *r;
 	u_int64_t serials_section_size;
 	u_int64_t i = 0;
 	u_int64_t offset = 0;

 	if (grl == NULL || blob == NULL || grl->parsed == NULL)
 		return HIBA_BAD_PARAMS;

 	/* Write the header. */
 	if ((ret = sshbuf_put_u32(blob, HIBA_GRL_MAGIC)) < 0) {
 		debug3("hibagrl_encode: sshbuf_put_u32 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if ((ret = sshbuf_put_u32(blob, grl->version)) < 0) {
 		debug3("hibagrl_encode: sshbuf_put_u32 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if ((ret = sshbuf_put_u32(blob, grl->min_version)) < 0) {
 		debug3("hibagrl_encode: sshbuf_put_u32 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if ((ret = sshbuf_put_u64(blob, time(NULL))) < 0) {
 		debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if ((ret = sshbuf_put_cstring(blob, grl->comment)) < 0) {
 		debug3("hibagrl_encode: sshbuf_put_cstring returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	serials_section_size = grl->n_serials * sizeof(struct serials);
 	debug2("hibagrl_encode: grl->n_serials = %" PRIu32, grl->n_serials);
 	debug2("hibagrl_decode: serials_section_size = %" PRIu64, serials_section_size);
 	if ((ret = sshbuf_put_u64(blob, serials_section_size)) < 0) {
 		debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}

 	/* Now we build the serial list. */
 	debug3("hibagrl_encode: serial list section @%zu", sshbuf_len(blob));
 	if ((ret = sshbuf_allocate(blob, serials_section_size)) < 0) {
 		debug3("hibagrl_encode: sshbuf_allocate(%" PRIu64 ") returned %d: %s",
 		       serials_section_size, ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}

 	/* Calculate and reserve room for the bitmap size. */
 	r = grl->parsed;
 	while (r->next != NULL) {
 		r = r->next;

 		/* Add the serial to the 1st section. */
 		if ((ret = sshbuf_put_u64(blob, r->serial)) < 0) {
 			debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
 			return HIBA_INTERNAL_ERROR;
 		}
 		if ((ret = sshbuf_put_u64(blob, offset)) < 0) {
 			debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
 			return HIBA_INTERNAL_ERROR;
 		}

 		offset += r->size;
 	}

 	if ((ret = sshbuf_put_u64(blob, offset)) < 0) {
 		debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}
 	if ((ret = sshbuf_allocate(blob, offset)) < 0) {
 		debug3("hibagrl_encode: sshbuf_allocate(%" PRIu64 ") returned %d: %s",
 		       offset, ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}

 	debug3("hibagrl_encode: bitmap section @%zu", sshbuf_len(blob));

 	r = grl->parsed;
 	while (r->next != NULL) {
 		int m;
 		r = r->next;

 		for (m = 0; m < r->size; ++m) {
 			if ((ret = sshbuf_put_u8(blob, r->map[m])) < 0) {
 				debug3("hibagrl_encode: sshbuf_put_u8 returned %d: %s", ret, ssh_err(ret));
 				return HIBA_INTERNAL_ERROR;
 			}
 		}
 		offset += r->size + sizeof(r->size);

 		++i;
 	}

 	debug2("hibagrl_encode: patch bitmap section size = %" PRIu64, offset);

 	/* Write trailer magic. */
 	if ((ret = sshbuf_put_u32(blob, HIBA_GRL_MAGIC)) < 0) {
 		debug3("hibagrl_encode: sshbuf_put_u32 returned %d: %s", ret, ssh_err(ret));
 		return HIBA_INTERNAL_ERROR;
 	}

 	return HIBA_OK;
 }

 /* The block of a grant index represents the char that contains the bit
  * representing the grant.
  * This corresponds to the floor of the position of the bit divided by 8 (size
  * of a char). */
 static __inline__ u_int32_t
 block_for_idx(u_int32_t idx) {
 	return idx >> 3;
 }

 /* The offset of a grant index represents the position of the bit representing
  * the grant inside the block.
  * This corresponds to remainder of the position of the bit divided by 8 (size
  * of a char). */
 static __inline__ u_int32_t
 offset_for_idx(u_int32_t idx) {
 	return idx & 0x7;
 }

 /* We want to update the offset in the right block. */
 static __inline__ void
 revoke_idx(struct parsed_revocations *r, u_int32_t idx) {
 	u_int32_t block = block_for_idx(idx);
 	u_int32_t offset = offset_for_idx(idx);
 	debug("REVOKE_ID(%d): map[%d] |= %02x", idx, block, offset);
 	r->map[block] |= 1 << offset;
 }

 /* A grant ID is marked as revoked if both conditions hold true:
  * - the map size is larger or equal to the grant idx.
  * - the grant ID corresponding bit is set. */
 static __inline__ int
 is_revoked_idx(const unsigned char *bitmap, u_int32_t size, u_int32_t idx) {
 	u_int32_t block = block_for_idx(idx);
 	u_int32_t offset = offset_for_idx(idx);
 	return (block <= size) && ((1 << offset) & bitmap[block]);
 }

 int
 hibagrl_revoke_grant(struct hibagrl *grl, u_int64_t serial, u_int32_t lo, u_int32_t hi) {
 	u_int32_t i;
 	int required_size = 0;
 	struct parsed_revocations *r;

 	if (grl == NULL)
 		return HIBA_BAD_PARAMS;
 	if (grl->parsed == NULL)
 		return HIBA_BAD_PARAMS;

 	/* Look for where to add the revocation. */
 	r = grl->parsed;
 	while (r->next) {
 		if (r->next->serial >= serial)
 			break;
 		r = r->next;
 	}

 	/* Maybe add a new serial to the ordered list. */
 	if ((r->next == NULL) || (r->next->serial > serial)) {
 		struct parsed_revocations *next = r->next;
 		debug2("hibagrl_revoke_grant: adding a new entry for serial 0x%" PRIx64 " after 0x%" PRIx64 , serial, r->serial);
 		r->next = calloc(1, sizeof(struct parsed_revocations));
 		r = r->next;
 		r->next = next;
 		r->serial = serial;

 		++grl->n_serials;
 	} else {
 		r = r->next;
 		debug2("hibagrl_revoke_grant: reusing existing entry for serial 0x%" PRIx64, serial);
 	}

 	required_size = block_for_idx(hi) + 1;

 	/* Allocate or update the bitmap. */
 	if (r->size < required_size) {
 		char *prev_map = r->map;
 		debug2("hibagrl_revoke_grant: resizing map to %d", required_size);
 		r->map = calloc(required_size, 1);
 		if (prev_map) {
 			/* if we already add revocations for this serial, we
 			 * must copy them. */
 			memcpy(r->map, prev_map, r->size);
 			free(prev_map);
 		}
 		r->size = required_size;
 	}
 	/* Add our grants. */
 	for (i = lo; i <= hi; ++i) {
 		revoke_idx(r, i);
 	}

 	return 0;
 }

 int
 hibagrl_check(const struct hibagrl *grl, u_int64_t serial, u_int32_t grant_idx) {
 	u_int64_t offset;
 	u_int64_t size;
 	int64_t min = 0;
 	int64_t max;
 	int64_t cur;

 	if (grl == NULL)
 		return HIBA_BAD_PARAMS;
 	if (grl->serials == NULL || grl->bitmaps == NULL)
 		return HIBA_BAD_PARAMS;

 	/* Early return if the GRL contains no serials. */
 	if (grl->n_serials == 0)
 		return HIBA_OK;

 	max = grl->n_serials - 1;

 	/* First we search through serials. */
 	while (1) {
 		u_int64_t min_serial = PEEK_U64(&grl->serials[min].serial);
 		u_int64_t max_serial = PEEK_U64(&grl->serials[max].serial);
 		u_int64_t cur_serial;

 		cur = min + ((max - min) / 2);

 		cur_serial = PEEK_U64(&grl->serials[cur].serial);
 		debug3("hibagrl_check: window [0x%" PRIx64 " (@%" PRIx64 ") - 0x%" PRIx64 " (@%" PRIx64 ")]", min_serial, min, max_serial, max);
 		debug3("hibagrl_check: target 0x%" PRIx64 " against current serial 0x%" PRIx64 "(@%" PRIx64 ")", serial, cur_serial, cur);

 		if (cur_serial == serial) {
 			/* We only break the loop when we found a matching
 			 * serial which index we store in cur. */
 			break;
 		} else if (cur_serial > serial) {
 			max = cur - 1;
 		} else if (cur_serial < serial) {
 			min = cur + 1;
 		}

 		if (max < min) {
 			debug2("hibagrl_check: serial not found in GRL");
 			return HIBA_OK;
 		}
 	}

 	debug2("hibagrl_check: found in GRL: 0x%" PRIx64, serial);

 	/* If the offset points outside of the bitmap, our GRL is invalid.
 	 * Fail closed. */
 	offset = PEEK_U64(&grl->serials[cur].offset);
 	if (offset > grl->bitmaps_size)
 		return HIBA_BAD_PARAMS;

 	if (cur >= grl->n_serials - 1)
 		size = grl->bitmaps_size - offset;
 	else
 		size = PEEK_U64(&grl->serials[cur+1].offset) - offset;

 	if (is_revoked_idx(grl->bitmaps + offset, size, grant_idx))
 		return HIBA_CHECK_REVOKED;
 	return HIBA_OK;
 }

 static void
 dump_map(const struct parsed_revocations *r, FILE *f) {
 	int i;
 	for (i = 0; i < r->size; ++i) {
 		fprintf(f, "%02X", (r->map[i] & 0xF) << 4 | r->map[i] >> 4);
 	}
 	fprintf(f, "\n");
 }

 int
 hibagrl_dump_content(const struct hibagrl *grl, u_int64_t *serial, FILE *f) {
 	struct parsed_revocations *r;

 	if (grl == NULL)
 		return HIBA_BAD_PARAMS;
 	if (grl->parsed == NULL)
 		return HIBA_BAD_PARAMS;

 	r = grl->parsed;
 	while (r->next != NULL) {
 		r = r->next;
 		if (serial == NULL || r->serial == *serial) {
 			fprintf(f, "  [0x%.16" PRIx64 "]: ", r->serial);
 			dump_map(r, f);

 			/* When filtering on serial, we can early exit as each
 			 * serial appears at most once. */
 			if (serial)
 				break;
 		}
 	}
 	fprintf(f, "\n");

 	return HIBA_OK;
 }
	/*
	* Copyright 2022 The HIBA Authors
	*
	* Use of this source code is governed by a BSD-style
	* license that can be found in the LICENSE file or at
	* https://developers.google.com/open-source/licenses/bsd
	*/
	#include <inttypes.h>
	#include <stddef.h>
	#include <stdlib.h>
	#include <string.h>
	#include <time.h>

	#include "errors.h"
	#include "log.h"
	#include "revocations.h"

	#define HIBA_CURRENT_GRL_VERSION 0x1
	#define HIBA_MIN_SUPPORTED_GRL_VERSION 0x1

	/* Stores a list of all the certificates with revoked grants.
	* This structure is meant to be mapped directly on top of a mmapped revocation
	* file on top of the serial list section (see PROTOCOL.grl). */
	struct serials {
	u_int64_t serial;
	u_int64_t offset;
	} __attribute__((packed));

	/* Parsed list of revocations. */
	struct parsed_revocations {
	u_int64_t serial;
	u_int16_t size;
	char *map;

	struct parsed_revocations *next;
	};

	/* In memory representation of the GRL.
	* The 'parsed' field is a linked list to revocations entries. The first
	* element of that list (if it exists) is the head and doesn't contain any
	* revocation information. */
	struct hibagrl {
	u_int32_t version;
	u_int32_t min_version;
	u_int64_t timestamp;
	u_int32_t n_serials;
	u_int64_t bitmaps_size;
	char *comment;

	const struct serials *serials;
	const unsigned char *bitmaps;

	struct parsed_revocations *parsed;
	};

	void
	hibagrl_free(struct hibagrl *grl) {
	struct parsed_revocations *r;

	if (grl == NULL)
	return;

	r = grl->parsed;
	while (r != NULL) {
	struct parsed_revocations *tbd = r;
	r = r->next;
	free(tbd->map);
	free(tbd);
	}

	free(grl->comment);
	free(grl);
	}

	struct hibagrl*
	hibagrl_new() {
	struct hibagrl *grl = calloc(sizeof(struct hibagrl), 1);
	return grl;
	}

	void
	hibagrl_init(struct hibagrl grl, const char comment) {
	if (grl == NULL)
	return;

	memset(grl, 0, sizeof(struct hibagrl));
	grl->version = HIBA_CURRENT_GRL_VERSION;
	grl->min_version = HIBA_MIN_SUPPORTED_GRL_VERSION;
	grl->comment = strdup(comment);

	/* Allocate the head of the parsed linked list to show this is an
	* editable GRL. */
	grl->parsed = calloc(1, sizeof(struct parsed_revocations));
	}

	int
	hibagrl_version(const struct hibagrl *grl) {
	if (grl == NULL) {
	return HIBA_BAD_PARAMS;
	}
	return grl->version;
	}

	const char*
	hibagrl_comment(const struct hibagrl *grl) {
	if (grl == NULL) {
	return hiba_err(-HIBA_BAD_PARAMS);
	}
	return grl->comment;
	}

	u_int64_t
	hibagrl_timestamp(const struct hibagrl *grl) {
	if (grl == NULL) {
	return 0;
	}
	return grl->timestamp;
	}

	u_int64_t
	hibagrl_serials_count(const struct hibagrl *grl) {
	if (grl == NULL) {
	return 0;
	}
	return grl->n_serials;
	}

	int
	hibagrl_decode(struct hibagrl grl, struct sshbuf blob) {
	int ret;
	u_int32_t magic;
	u_int64_t serials_section_size;

	if (grl == NULL \|\| blob == NULL)
	return HIBA_BAD_PARAMS;

	memset(grl, 0, sizeof(struct hibagrl));

	if ((ret = sshbuf_get_u32(blob, &magic)) < 0) {
	debug3("hibagrl_decode: sshbuf_get_u32 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if (magic != HIBA_GRL_MAGIC) {
	return HIBA_INVALID_GRL;
	}

	if ((ret = sshbuf_get_u32(blob, &grl->version)) != 0) {
	debug3("hibagrl_decode: sshbuf_get_u32 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_get_u32(blob, &grl->min_version)) != 0) {
	debug3("hibagrl_decode: sshbuf_get_u32 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_get_u64(blob, &grl->timestamp)) != 0) {
	debug3("hibagrl_decode: sshbuf_get_u64 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_get_cstring(blob, &grl->comment, NULL)) != 0) {
	debug3("hibagrl_decode: sshbuf_get_cstring returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}

	/* Get the serials section. */
	if ((ret = sshbuf_get_u64(blob, &serials_section_size)) != 0) {
	debug3("hibagrl_decode: sshbuf_get_u64 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	grl->n_serials = serials_section_size / sizeof(struct serials);
	debug2("hibagrl_decode: serials_section_size = %" PRIu64, serials_section_size);
	grl->serials = (const struct serials *)sshbuf_ptr(blob);
	if (log_level_get() >= SYSLOG_LEVEL_DEBUG3) {
	debug3("hibagrl_decode: serial list section content");
	sshbuf_dump_data(sshbuf_ptr(blob), serials_section_size, stderr);
	}
	if ((ret = sshbuf_consume(blob, serials_section_size)) != 0) {
	debug3("hibagrl_decode: sshbuf_consume returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}

	/* Get the bitmaps section. */
	if ((ret = sshbuf_get_u64(blob, &grl->bitmaps_size)) != 0) {
	debug3("hibagrl_decode: sshbuf_get_u64 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	debug2("hibagrl_decode: bitmaps_section_size = %" PRIu64, grl->bitmaps_size);
	grl->bitmaps = sshbuf_ptr(blob);
	if (log_level_get() >= SYSLOG_LEVEL_DEBUG3) {
	debug3("hibagrl_decode: bitmap section content");
	sshbuf_dump_data(sshbuf_ptr(blob), grl->bitmaps_size, stderr);
	}
	if ((ret = sshbuf_consume(blob, grl->bitmaps_size)) != 0) {
	debug3("hibagrl_decode: sshbuf_consume returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}

	if ((ret = sshbuf_get_u32(blob, &magic)) < 0) {
	debug3("hibagrl_decode: sshbuf_get_u32 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if (magic != HIBA_GRL_MAGIC) {
	return HIBA_INVALID_GRL;
	}

	/* The parsed_revocations field is left NULL on purpose and will only be
	* actually parsed from serials/bitmaps sections when needed using
	* hibagrl_map(). */
	debug2("hibagrl_decode: grl->n_serials = %" PRIu32, grl->n_serials);

	return HIBA_OK;
	}

	int
	hibagrl_map(struct hibagrl *grl) {
	u_int64_t i = 0;
	struct parsed_revocations *r;

	if (grl == NULL)
	return HIBA_BAD_PARAMS;
	if (grl->parsed != NULL)
	return HIBA_BAD_PARAMS;

	/* The first parsed_revocation doesn't count, it is only used as the
	* head of the linked list. */
	grl->parsed = calloc(1, sizeof(struct parsed_revocations));
	r = grl->parsed;

	debug("hibagrl_map: mapping %" PRIu32 " serials", grl->n_serials);
	for (i = 0; i < grl->n_serials; ++i) {
	u_int64_t offset;
	u_int64_t next_offset = grl->bitmaps_size;

	r->next = calloc(1, sizeof(struct parsed_revocations));
	r = r->next;
	r->serial = PEEK_U64(&grl->serials[i].serial);
	offset = PEEK_U64(&grl->serials[i].offset);

	if (i+1 < grl->n_serials) {
	next_offset = PEEK_U64(&grl->serials[i+1].offset);
	}
	r->size = next_offset - offset;
	r->map = calloc(1, r->size);
	memcpy(r->map, grl->bitmaps + offset, r->size);
	}

	/* Nullify mmapped sections since we now have an editable GRL. */
	grl->serials = NULL;
	grl->bitmaps = NULL;
	grl->bitmaps_size = 0;

	return 0;
	}

	int
	hibagrl_encode(const struct hibagrl grl, struct sshbuf blob) {
	int ret;
	struct parsed_revocations *r;
	u_int64_t serials_section_size;
	u_int64_t i = 0;
	u_int64_t offset = 0;

	if (grl == NULL \|\| blob == NULL \|\| grl->parsed == NULL)
	return HIBA_BAD_PARAMS;

	/* Write the header. */
	if ((ret = sshbuf_put_u32(blob, HIBA_GRL_MAGIC)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u32 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_put_u32(blob, grl->version)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u32 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_put_u32(blob, grl->min_version)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u32 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_put_u64(blob, time(NULL))) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_put_cstring(blob, grl->comment)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_cstring returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	serials_section_size = grl->n_serials * sizeof(struct serials);
	debug2("hibagrl_encode: grl->n_serials = %" PRIu32, grl->n_serials);
	debug2("hibagrl_decode: serials_section_size = %" PRIu64, serials_section_size);
	if ((ret = sshbuf_put_u64(blob, serials_section_size)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}

	/* Now we build the serial list. */
	debug3("hibagrl_encode: serial list section @%zu", sshbuf_len(blob));
	if ((ret = sshbuf_allocate(blob, serials_section_size)) < 0) {
	debug3("hibagrl_encode: sshbuf_allocate(%" PRIu64 ") returned %d: %s",
	serials_section_size, ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}

	/* Calculate and reserve room for the bitmap size. */
	r = grl->parsed;
	while (r->next != NULL) {
	r = r->next;

	/* Add the serial to the 1st section. */
	if ((ret = sshbuf_put_u64(blob, r->serial)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_put_u64(blob, offset)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}

	offset += r->size;
	}

	if ((ret = sshbuf_put_u64(blob, offset)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u64 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	if ((ret = sshbuf_allocate(blob, offset)) < 0) {
	debug3("hibagrl_encode: sshbuf_allocate(%" PRIu64 ") returned %d: %s",
	offset, ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}

	debug3("hibagrl_encode: bitmap section @%zu", sshbuf_len(blob));

	r = grl->parsed;
	while (r->next != NULL) {
	int m;
	r = r->next;

	for (m = 0; m < r->size; ++m) {
	if ((ret = sshbuf_put_u8(blob, r->map[m])) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u8 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}
	}
	offset += r->size + sizeof(r->size);

	++i;
	}

	debug2("hibagrl_encode: patch bitmap section size = %" PRIu64, offset);

	/* Write trailer magic. */
	if ((ret = sshbuf_put_u32(blob, HIBA_GRL_MAGIC)) < 0) {
	debug3("hibagrl_encode: sshbuf_put_u32 returned %d: %s", ret, ssh_err(ret));
	return HIBA_INTERNAL_ERROR;
	}

	return HIBA_OK;
	}

	/* The block of a grant index represents the char that contains the bit
	* representing the grant.
	* This corresponds to the floor of the position of the bit divided by 8 (size
	* of a char). */
	static __inline__ u_int32_t
	block_for_idx(u_int32_t idx) {
	return idx >> 3;
	}

	/* The offset of a grant index represents the position of the bit representing
	* the grant inside the block.
	* This corresponds to remainder of the position of the bit divided by 8 (size
	* of a char). */
	static __inline__ u_int32_t
	offset_for_idx(u_int32_t idx) {
	return idx & 0x7;
	}

	/* We want to update the offset in the right block. */
	static __inline__ void
	revoke_idx(struct parsed_revocations *r, u_int32_t idx) {
	u_int32_t block = block_for_idx(idx);
	u_int32_t offset = offset_for_idx(idx);
	debug("REVOKE_ID(%d): map[%d] \|= %02x", idx, block, offset);
	r->map[block] \|= 1 << offset;
	}

	/* A grant ID is marked as revoked if both conditions hold true:
	* - the map size is larger or equal to the grant idx.
	* - the grant ID corresponding bit is set. */
	static __inline__ int
	is_revoked_idx(const unsigned char *bitmap, u_int32_t size, u_int32_t idx) {
	u_int32_t block = block_for_idx(idx);
	u_int32_t offset = offset_for_idx(idx);
	return (block <= size) && ((1 << offset) & bitmap[block]);
	}

	int
	hibagrl_revoke_grant(struct hibagrl *grl, u_int64_t serial, u_int32_t lo, u_int32_t hi) {
	u_int32_t i;
	int required_size = 0;
	struct parsed_revocations *r;

	if (grl == NULL)
	return HIBA_BAD_PARAMS;
	if (grl->parsed == NULL)
	return HIBA_BAD_PARAMS;

	/* Look for where to add the revocation. */
	r = grl->parsed;
	while (r->next) {
	if (r->next->serial >= serial)
	break;
	r = r->next;
	}

	/* Maybe add a new serial to the ordered list. */
	if ((r->next == NULL) \|\| (r->next->serial > serial)) {
	struct parsed_revocations *next = r->next;
	debug2("hibagrl_revoke_grant: adding a new entry for serial 0x%" PRIx64 " after 0x%" PRIx64 , serial, r->serial);
	r->next = calloc(1, sizeof(struct parsed_revocations));
	r = r->next;
	r->next = next;
	r->serial = serial;

	++grl->n_serials;
	} else {
	r = r->next;
	debug2("hibagrl_revoke_grant: reusing existing entry for serial 0x%" PRIx64, serial);
	}

	required_size = block_for_idx(hi) + 1;

	/* Allocate or update the bitmap. */
	if (r->size < required_size) {
	char *prev_map = r->map;
	debug2("hibagrl_revoke_grant: resizing map to %d", required_size);
	r->map = calloc(required_size, 1);
	if (prev_map) {
	/* if we already add revocations for this serial, we
	* must copy them. */
	memcpy(r->map, prev_map, r->size);
	free(prev_map);
	}
	r->size = required_size;
	}
	/* Add our grants. */
	for (i = lo; i <= hi; ++i) {
	revoke_idx(r, i);
	}

	return 0;
	}

	int
	hibagrl_check(const struct hibagrl *grl, u_int64_t serial, u_int32_t grant_idx) {
	u_int64_t offset;
	u_int64_t size;
	int64_t min = 0;
	int64_t max;
	int64_t cur;

	if (grl == NULL)
	return HIBA_BAD_PARAMS;
	if (grl->serials == NULL \|\| grl->bitmaps == NULL)
	return HIBA_BAD_PARAMS;

	/* Early return if the GRL contains no serials. */
	if (grl->n_serials == 0)
	return HIBA_OK;

	max = grl->n_serials - 1;

	/* First we search through serials. */
	while (1) {
	u_int64_t min_serial = PEEK_U64(&grl->serials[min].serial);
	u_int64_t max_serial = PEEK_U64(&grl->serials[max].serial);
	u_int64_t cur_serial;

	cur = min + ((max - min) / 2);

	cur_serial = PEEK_U64(&grl->serials[cur].serial);
	debug3("hibagrl_check: window [0x%" PRIx64 " (@%" PRIx64 ") - 0x%" PRIx64 " (@%" PRIx64 ")]", min_serial, min, max_serial, max);
	debug3("hibagrl_check: target 0x%" PRIx64 " against current serial 0x%" PRIx64 "(@%" PRIx64 ")", serial, cur_serial, cur);

	if (cur_serial == serial) {
	/* We only break the loop when we found a matching
	* serial which index we store in cur. */
	break;
	} else if (cur_serial > serial) {
	max = cur - 1;
	} else if (cur_serial < serial) {
	min = cur + 1;
	}

	if (max < min) {
	debug2("hibagrl_check: serial not found in GRL");
	return HIBA_OK;
	}
	}

	debug2("hibagrl_check: found in GRL: 0x%" PRIx64, serial);

	/* If the offset points outside of the bitmap, our GRL is invalid.
	* Fail closed. */
	offset = PEEK_U64(&grl->serials[cur].offset);
	if (offset > grl->bitmaps_size)
	return HIBA_BAD_PARAMS;

	if (cur >= grl->n_serials - 1)
	size = grl->bitmaps_size - offset;
	else
	size = PEEK_U64(&grl->serials[cur+1].offset) - offset;

	if (is_revoked_idx(grl->bitmaps + offset, size, grant_idx))
	return HIBA_CHECK_REVOKED;
	return HIBA_OK;
	}

	static void
	dump_map(const struct parsed_revocations r, FILE f) {
	int i;
	for (i = 0; i < r->size; ++i) {
	fprintf(f, "%02X", (r->map[i] & 0xF) << 4 \| r->map[i] >> 4);
	}
	fprintf(f, "\n");
	}

	int
	hibagrl_dump_content(const struct hibagrl grl, u_int64_t serial, FILE *f) {
	struct parsed_revocations *r;

	if (grl == NULL)
	return HIBA_BAD_PARAMS;
	if (grl->parsed == NULL)
	return HIBA_BAD_PARAMS;

	r = grl->parsed;
	while (r->next != NULL) {
	r = r->next;
	if (serial == NULL \|\| r->serial == *serial) {
	fprintf(f, " [0x%.16" PRIx64 "]: ", r->serial);
	dump_map(r, f);

	/* When filtering on serial, we can early exit as each
	* serial appears at most once. */
	if (serial)
	break;
	}
	}
	fprintf(f, "\n");

	return HIBA_OK;
	}