aboutsummaryrefslogtreecommitdiff
path: root/_orig/lib
diff options
context:
space:
mode:
Diffstat (limited to '_orig/lib')
-rw-r--r--_orig/lib/bcrypt_pbkdf.369
-rw-r--r--_orig/lib/bcrypt_pbkdf.c169
-rw-r--r--_orig/lib/ohash.c327
-rw-r--r--_orig/lib/ohash.h74
-rw-r--r--_orig/lib/ohash_init.3271
-rw-r--r--_orig/lib/ohash_interval.393
-rw-r--r--_orig/lib/sha2.h136
7 files changed, 1139 insertions, 0 deletions
diff --git a/_orig/lib/bcrypt_pbkdf.3 b/_orig/lib/bcrypt_pbkdf.3
new file mode 100644
index 0000000..eb43d43
--- /dev/null
+++ b/_orig/lib/bcrypt_pbkdf.3
@@ -0,0 +1,69 @@
+.\" $OpenBSD: bcrypt_pbkdf.3,v 1.6 2014/11/25 03:37:12 tedu Exp $
+.\"
+.\" Copyright (c) 2012 Ted Unangst <tedu@openbsd.org>
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.Dd $Mdocdate: November 25 2014 $
+.Dt BCRYPT_PBKDF 3
+.Os
+.Sh NAME
+.Nm bcrypt_pbkdf
+.Nd bcrypt password-based key derivation function
+.Sh SYNOPSIS
+.In util.h
+.Ft int
+.Fn bcrypt_pbkdf "const char *pass" "size_t pass_len" "const uint8_t *salt" \
+ "size_t salt_len" "uint8_t *key" "size_t key_len" "unsigned int rounds"
+.Sh DESCRIPTION
+The
+.Nm
+function converts a password into a byte array suitable for use as
+an encryption key.
+The password and salt values are combined and repeatedly hashed
+.Ar rounds
+times.
+The salt value should be randomly generated beforehand.
+The repeated hashing is designed to thwart discovery of the key via
+password guessing attacks.
+The higher the number of rounds, the slower each attempt will be.
+.\" A minimum value of at least 4 is recommended.
+.Sh RETURN VALUES
+The
+.Fn bcrypt_pbkdf
+function returns 0 to indicate success and \-1 for failure.
+.\" .Sh EXAMPLES
+.\" .Sh ERRORS
+.Sh SEE ALSO
+.Xr bcrypt 3
+.Sh STANDARDS
+.Rs
+.%A Niels Provos and David Mazieres
+.%D June 1999
+.%T A Future-Adaptable Password Scheme
+.Re
+.Pp
+.Rs
+.%A B. Kaliski
+.%D September 2000
+.%R RFC 2898
+.%T PKCS #5: Password-Based Cryptography Specification Version 2.0
+.Re
+.\" .Sh HISTORY
+.\" .Sh AUTHORS
+.Sh CAVEATS
+This implementation deviates slightly from the PBKDF2 standard by mixing
+output key bits nonlinearly.
+By mixing the output bytes together, an attacker is required to perform
+all of the work without taking any shortcuts.
+.\" .Sh BUGS
diff --git a/_orig/lib/bcrypt_pbkdf.c b/_orig/lib/bcrypt_pbkdf.c
new file mode 100644
index 0000000..cde347c
--- /dev/null
+++ b/_orig/lib/bcrypt_pbkdf.c
@@ -0,0 +1,169 @@
+/* $OpenBSD: bcrypt_pbkdf.c,v 1.13 2015/01/12 03:20:04 tedu Exp $ */
+/*
+ * Copyright (c) 2013 Ted Unangst <tedu@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <blf.h>
+#include <sha2.h>
+#include <string.h>
+#include <util.h>
+
+#define MINIMUM(a,b) (((a) < (b)) ? (a) : (b))
+
+/*
+ * pkcs #5 pbkdf2 implementation using the "bcrypt" hash
+ *
+ * The bcrypt hash function is derived from the bcrypt password hashing
+ * function with the following modifications:
+ * 1. The input password and salt are preprocessed with SHA512.
+ * 2. The output length is expanded to 256 bits.
+ * 3. Subsequently the magic string to be encrypted is lengthened and modifed
+ * to "OxychromaticBlowfishSwatDynamite"
+ * 4. The hash function is defined to perform 64 rounds of initial state
+ * expansion. (More rounds are performed by iterating the hash.)
+ *
+ * Note that this implementation pulls the SHA512 operations into the caller
+ * as a performance optimization.
+ *
+ * One modification from official pbkdf2. Instead of outputting key material
+ * linearly, we mix it. pbkdf2 has a known weakness where if one uses it to
+ * generate (e.g.) 512 bits of key material for use as two 256 bit keys, an
+ * attacker can merely run once through the outer loop, but the user
+ * always runs it twice. Shuffling output bytes requires computing the
+ * entirety of the key material to assemble any subkey. This is something a
+ * wise caller could do; we just do it for you.
+ */
+
+#define BCRYPT_WORDS 8
+#define BCRYPT_HASHSIZE (BCRYPT_WORDS * 4)
+
+static void
+bcrypt_hash(uint8_t *sha2pass, uint8_t *sha2salt, uint8_t *out)
+{
+ blf_ctx state;
+ uint8_t ciphertext[BCRYPT_HASHSIZE] =
+ "OxychromaticBlowfishSwatDynamite";
+ uint32_t cdata[BCRYPT_WORDS];
+ int i;
+ uint16_t j;
+ size_t shalen = SHA512_DIGEST_LENGTH;
+
+ /* key expansion */
+ Blowfish_initstate(&state);
+ Blowfish_expandstate(&state, sha2salt, shalen, sha2pass, shalen);
+ for (i = 0; i < 64; i++) {
+ Blowfish_expand0state(&state, sha2salt, shalen);
+ Blowfish_expand0state(&state, sha2pass, shalen);
+ }
+
+ /* encryption */
+ j = 0;
+ for (i = 0; i < BCRYPT_WORDS; i++)
+ cdata[i] = Blowfish_stream2word(ciphertext, sizeof(ciphertext),
+ &j);
+ for (i = 0; i < 64; i++)
+ blf_enc(&state, cdata, sizeof(cdata) / sizeof(uint64_t));
+
+ /* copy out */
+ for (i = 0; i < BCRYPT_WORDS; i++) {
+ out[4 * i + 3] = (cdata[i] >> 24) & 0xff;
+ out[4 * i + 2] = (cdata[i] >> 16) & 0xff;
+ out[4 * i + 1] = (cdata[i] >> 8) & 0xff;
+ out[4 * i + 0] = cdata[i] & 0xff;
+ }
+
+ /* zap */
+ explicit_bzero(ciphertext, sizeof(ciphertext));
+ explicit_bzero(cdata, sizeof(cdata));
+ explicit_bzero(&state, sizeof(state));
+}
+
+int
+bcrypt_pbkdf(const char *pass, size_t passlen, const uint8_t *salt, size_t saltlen,
+ uint8_t *key, size_t keylen, unsigned int rounds)
+{
+ SHA2_CTX ctx;
+ uint8_t sha2pass[SHA512_DIGEST_LENGTH];
+ uint8_t sha2salt[SHA512_DIGEST_LENGTH];
+ uint8_t out[BCRYPT_HASHSIZE];
+ uint8_t tmpout[BCRYPT_HASHSIZE];
+ uint8_t countsalt[4];
+ size_t i, j, amt, stride;
+ uint32_t count;
+ size_t origkeylen = keylen;
+
+ /* nothing crazy */
+ if (rounds < 1)
+ return -1;
+ if (passlen == 0 || saltlen == 0 || keylen == 0 ||
+ keylen > sizeof(out) * sizeof(out))
+ return -1;
+ stride = (keylen + sizeof(out) - 1) / sizeof(out);
+ amt = (keylen + stride - 1) / stride;
+
+ /* collapse password */
+ SHA512Init(&ctx);
+ SHA512Update(&ctx, pass, passlen);
+ SHA512Final(sha2pass, &ctx);
+
+
+ /* generate key, sizeof(out) at a time */
+ for (count = 1; keylen > 0; count++) {
+ countsalt[0] = (count >> 24) & 0xff;
+ countsalt[1] = (count >> 16) & 0xff;
+ countsalt[2] = (count >> 8) & 0xff;
+ countsalt[3] = count & 0xff;
+
+ /* first round, salt is salt */
+ SHA512Init(&ctx);
+ SHA512Update(&ctx, salt, saltlen);
+ SHA512Update(&ctx, countsalt, sizeof(countsalt));
+ SHA512Final(sha2salt, &ctx);
+ bcrypt_hash(sha2pass, sha2salt, tmpout);
+ memcpy(out, tmpout, sizeof(out));
+
+ for (i = 1; i < rounds; i++) {
+ /* subsequent rounds, salt is previous output */
+ SHA512Init(&ctx);
+ SHA512Update(&ctx, tmpout, sizeof(tmpout));
+ SHA512Final(sha2salt, &ctx);
+ bcrypt_hash(sha2pass, sha2salt, tmpout);
+ for (j = 0; j < sizeof(out); j++)
+ out[j] ^= tmpout[j];
+ }
+
+ /*
+ * pbkdf2 deviation: output the key material non-linearly.
+ */
+ amt = MINIMUM(amt, keylen);
+ for (i = 0; i < amt; i++) {
+ size_t dest = i * stride + (count - 1);
+ if (dest >= origkeylen)
+ break;
+ key[dest] = out[i];
+ }
+ keylen -= i;
+ }
+
+ /* zap */
+ explicit_bzero(&ctx, sizeof(ctx));
+ explicit_bzero(out, sizeof(out));
+
+ return 0;
+}
diff --git a/_orig/lib/ohash.c b/_orig/lib/ohash.c
new file mode 100644
index 0000000..74ca4fa
--- /dev/null
+++ b/_orig/lib/ohash.c
@@ -0,0 +1,327 @@
+/* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */
+
+/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+#include "ohash.h"
+
+struct _ohash_record {
+ uint32_t hv;
+ const char *p;
+};
+
+#define DELETED ((const char *)h)
+#define NONE (h->size)
+
+/* Don't bother changing the hash table if the change is small enough. */
+#define MINSIZE (1UL << 4)
+#define MINDELETED 4
+
+static void ohash_resize(struct ohash *);
+
+
+/* This handles the common case of variable length keys, where the
+ * key is stored at the end of the record.
+ */
+void *
+ohash_create_entry(struct ohash_info *i, const char *start, const char **end)
+{
+ char *p;
+
+ if (!*end)
+ *end = start + strlen(start);
+ p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
+ if (p) {
+ memcpy(p+i->key_offset, start, *end-start);
+ p[i->key_offset + (*end - start)] = '\0';
+ }
+ return (void *)p;
+}
+
+/* hash_delete only frees the hash structure. Use hash_first/hash_next
+ * to free entries as well. */
+void
+ohash_delete(struct ohash *h)
+{
+ (h->info.free)(h->t, h->info.data);
+#ifndef NDEBUG
+ h->t = NULL;
+#endif
+}
+
+static void
+ohash_resize(struct ohash *h)
+{
+ struct _ohash_record *n;
+ size_t ns;
+ unsigned int j;
+ unsigned int i, incr;
+
+ if (4 * h->deleted < h->total) {
+ if (h->size >= (UINT_MAX >> 1U))
+ ns = UINT_MAX;
+ else
+ ns = h->size << 1U;
+ } else if (3 * h->deleted > 2 * h->total)
+ ns = h->size >> 1U;
+ else
+ ns = h->size;
+ if (ns < MINSIZE)
+ ns = MINSIZE;
+#ifdef STATS_HASH
+ STAT_HASH_EXPAND++;
+ STAT_HASH_SIZE += ns - h->size;
+#endif
+
+ n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
+ if (!n)
+ return;
+
+ for (j = 0; j < h->size; j++) {
+ if (h->t[j].p != NULL && h->t[j].p != DELETED) {
+ i = h->t[j].hv % ns;
+ incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
+ while (n[i].p != NULL) {
+ i += incr;
+ if (i >= ns)
+ i -= ns;
+ }
+ n[i].hv = h->t[j].hv;
+ n[i].p = h->t[j].p;
+ }
+ }
+ (h->info.free)(h->t, h->info.data);
+ h->t = n;
+ h->size = ns;
+ h->total -= h->deleted;
+ h->deleted = 0;
+}
+
+void *
+ohash_remove(struct ohash *h, unsigned int i)
+{
+ void *result = (void *)h->t[i].p;
+
+ if (result == NULL || result == DELETED)
+ return NULL;
+
+#ifdef STATS_HASH
+ STAT_HASH_ENTRIES--;
+#endif
+ h->t[i].p = DELETED;
+ h->deleted++;
+ if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
+ ohash_resize(h);
+ return result;
+}
+
+void *
+ohash_find(struct ohash *h, unsigned int i)
+{
+ if (h->t[i].p == DELETED)
+ return NULL;
+ else
+ return (void *)h->t[i].p;
+}
+
+void *
+ohash_insert(struct ohash *h, unsigned int i, void *p)
+{
+#ifdef STATS_HASH
+ STAT_HASH_ENTRIES++;
+#endif
+ if (h->t[i].p == DELETED) {
+ h->deleted--;
+ h->t[i].p = p;
+ } else {
+ h->t[i].p = p;
+ /* Arbitrary resize boundary. Tweak if not efficient enough. */
+ if (++h->total * 4 > h->size * 3)
+ ohash_resize(h);
+ }
+ return p;
+}
+
+unsigned int
+ohash_entries(struct ohash *h)
+{
+ return h->total - h->deleted;
+}
+
+void *
+ohash_first(struct ohash *h, unsigned int *pos)
+{
+ *pos = 0;
+ return ohash_next(h, pos);
+}
+
+void *
+ohash_next(struct ohash *h, unsigned int *pos)
+{
+ for (; *pos < h->size; (*pos)++)
+ if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
+ return (void *)h->t[(*pos)++].p;
+ return NULL;
+}
+
+void
+ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)
+{
+ h->size = 1UL << size;
+ if (h->size < MINSIZE)
+ h->size = MINSIZE;
+#ifdef STATS_HASH
+ STAT_HASH_CREATION++;
+ STAT_HASH_SIZE += h->size;
+#endif
+ /* Copy info so that caller may free it. */
+ h->info.key_offset = info->key_offset;
+ h->info.calloc = info->calloc;
+ h->info.free = info->free;
+ h->info.alloc = info->alloc;
+ h->info.data = info->data;
+ h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
+ h->info.data);
+ h->total = h->deleted = 0;
+}
+
+uint32_t
+ohash_interval(const char *s, const char **e)
+{
+ uint32_t k;
+
+ if (!*e)
+ *e = s + strlen(s);
+ if (s == *e)
+ k = 0;
+ else
+ k = *s++;
+ while (s != *e)
+ k = ((k << 2) | (k >> 30)) ^ *s++;
+ return k;
+}
+
+unsigned int
+ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
+ uint32_t hv)
+{
+ unsigned int i, incr;
+ unsigned int empty;
+
+#ifdef STATS_HASH
+ STAT_HASH_LOOKUP++;
+#endif
+ empty = NONE;
+ i = hv % h->size;
+ incr = ((hv % (h->size-2)) & ~1) + 1;
+ while (h->t[i].p != NULL) {
+#ifdef STATS_HASH
+ STAT_HASH_LENGTH++;
+#endif
+ if (h->t[i].p == DELETED) {
+ if (empty == NONE)
+ empty = i;
+ } else if (h->t[i].hv == hv &&
+ strncmp(h->t[i].p+h->info.key_offset, start,
+ end - start) == 0 &&
+ (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
+ if (empty != NONE) {
+ h->t[empty].hv = hv;
+ h->t[empty].p = h->t[i].p;
+ h->t[i].p = DELETED;
+ return empty;
+ } else {
+#ifdef STATS_HASH
+ STAT_HASH_POSITIVE++;
+#endif
+ return i;
+ }
+ }
+ i += incr;
+ if (i >= h->size)
+ i -= h->size;
+ }
+
+ /* Found an empty position. */
+ if (empty != NONE)
+ i = empty;
+ h->t[i].hv = hv;
+ return i;
+}
+
+unsigned int
+ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
+{
+ unsigned int i, incr;
+ unsigned int empty;
+
+#ifdef STATS_HASH
+ STAT_HASH_LOOKUP++;
+#endif
+ empty = NONE;
+ i = hv % h->size;
+ incr = ((hv % (h->size-2)) & ~1) + 1;
+ while (h->t[i].p != NULL) {
+#ifdef STATS_HASH
+ STAT_HASH_LENGTH++;
+#endif
+ if (h->t[i].p == DELETED) {
+ if (empty == NONE)
+ empty = i;
+ } else if (h->t[i].hv == hv &&
+ memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
+ if (empty != NONE) {
+ h->t[empty].hv = hv;
+ h->t[empty].p = h->t[i].p;
+ h->t[i].p = DELETED;
+ return empty;
+ } else {
+#ifdef STATS_HASH
+ STAT_HASH_POSITIVE++;
+#endif
+ } return i;
+ }
+ i += incr;
+ if (i >= h->size)
+ i -= h->size;
+ }
+
+ /* Found an empty position. */
+ if (empty != NONE)
+ i = empty;
+ h->t[i].hv = hv;
+ return i;
+}
+
+unsigned int
+ohash_qlookup(struct ohash *h, const char *s)
+{
+ const char *e = NULL;
+ return ohash_qlookupi(h, s, &e);
+}
+
+unsigned int
+ohash_qlookupi(struct ohash *h, const char *s, const char **e)
+{
+ uint32_t hv;
+
+ hv = ohash_interval(s, e);
+ return ohash_lookup_interval(h, s, *e, hv);
+}
diff --git a/_orig/lib/ohash.h b/_orig/lib/ohash.h
new file mode 100644
index 0000000..c5f81ec
--- /dev/null
+++ b/_orig/lib/ohash.h
@@ -0,0 +1,74 @@
+/* $OpenBSD: ohash.h,v 1.2 2014/06/02 18:52:03 deraadt Exp $ */
+
+/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef OHASH_H
+#define OHASH_H
+
+/* Open hashing support.
+ * Open hashing was chosen because it is much lighter than other hash
+ * techniques, and more efficient in most cases.
+ */
+
+/* user-visible data structure */
+struct ohash_info {
+ ptrdiff_t key_offset;
+ void *data; /* user data */
+ void *(*calloc)(size_t, size_t, void *);
+ void (*free)(void *, void *);
+ void *(*alloc)(size_t, void *);
+};
+
+struct _ohash_record;
+
+/* private structure. It's there just so you can do a sizeof */
+struct ohash {
+ struct _ohash_record *t;
+ struct ohash_info info;
+ unsigned int size;
+ unsigned int total;
+ unsigned int deleted;
+};
+
+/* For this to be tweakable, we use small primitives, and leave part of the
+ * logic to the client application. e.g., hashing is left to the client
+ * application. We also provide a simple table entry lookup that yields
+ * a hashing table index (opaque) to be used in find/insert/remove.
+ * The keys are stored at a known position in the client data.
+ */
+__BEGIN_DECLS
+void ohash_init(struct ohash *, unsigned, struct ohash_info *);
+void ohash_delete(struct ohash *);
+
+unsigned int ohash_lookup_interval(struct ohash *, const char *,
+ const char *, uint32_t);
+unsigned int ohash_lookup_memory(struct ohash *, const char *,
+ size_t, uint32_t)
+ __attribute__ ((__bounded__(__string__,2,3)));
+void *ohash_find(struct ohash *, unsigned int);
+void *ohash_remove(struct ohash *, unsigned int);
+void *ohash_insert(struct ohash *, unsigned int, void *);
+void *ohash_first(struct ohash *, unsigned int *);
+void *ohash_next(struct ohash *, unsigned int *);
+unsigned int ohash_entries(struct ohash *);
+
+void *ohash_create_entry(struct ohash_info *, const char *, const char **);
+uint32_t ohash_interval(const char *, const char **);
+
+unsigned int ohash_qlookupi(struct ohash *, const char *, const char **);
+unsigned int ohash_qlookup(struct ohash *, const char *);
+__END_DECLS
+#endif
diff --git a/_orig/lib/ohash_init.3 b/_orig/lib/ohash_init.3
new file mode 100644
index 0000000..6832563
--- /dev/null
+++ b/_orig/lib/ohash_init.3
@@ -0,0 +1,271 @@
+.\" $OpenBSD: ohash_init.3,v 1.2 2014/05/13 14:01:41 jmc Exp $
+.\" Copyright (c) 1999 Marc Espie <espie@openbsd.org>
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.Dd $Mdocdate: May 13 2014 $
+.Dt OHASH_INIT 3
+.Os
+.Sh NAME
+.Nm ohash_init ,
+.Nm ohash_delete ,
+.Nm ohash_lookup_interval ,
+.Nm ohash_lookup_memory ,
+.Nm ohash_find ,
+.Nm ohash_remove ,
+.Nm ohash_insert ,
+.Nm ohash_first ,
+.Nm ohash_next ,
+.Nm ohash_entries
+.Nd light-weight open hashing
+.Sh SYNOPSIS
+.In stdint.h
+.In stddef.h
+.In ohash.h
+.Ft void
+.Fn ohash_init "struct ohash *h" "unsigned int size" "struct ohash_info *info"
+.Ft void
+.Fn ohash_delete "struct ohash *h"
+.Ft "unsigned int"
+.Fn ohash_lookup_interval "struct ohash *h" "const char *start" "const char *end" "uint32_t hv"
+.Ft "unsigned int"
+.Fn ohash_lookup_memory "struct ohash *h" "const char *k" "size_t s" "uint32_t hv"
+.Ft void *
+.Fn ohash_find "struct ohash *h" "unsigned int i"
+.Ft void *
+.Fn ohash_remove "struct ohash *h" "unsigned int i"
+.Ft void *
+.Fn ohash_insert "struct ohash *h" "unsigned int i" "void *p"
+.Ft void *
+.Fn ohash_first "struct ohash *h" "unsigned int *i"
+.Ft void *
+.Fn ohash_next "struct ohash *h" "unsigned int *i"
+.Ft "unsigned int"
+.Fn ohash_entries "struct ohash *h"
+.Sh DESCRIPTION
+These functions have been designed as a fast, extensible alternative to
+the usual hash table functions.
+They provide storage and retrieval of records indexed by keys,
+where a key is a contiguous sequence of bytes at a fixed position in
+each record.
+Keys can either be NUL-terminated strings or fixed-size memory areas.
+All functions take a pointer to an ohash structure as the
+.Fa h
+function argument.
+Storage for this structure should be provided by user code.
+.Pp
+.Fn ohash_init
+initializes the table to store roughly 2 to the power
+.Fa size
+elements.
+.Fa info
+is a pointer to a
+.Fa struct ohash_info .
+.Bd -literal -offset indent
+struct ohash_info {
+ ptrdiff_t key_offset;
+ void *data; /* user data */
+ void *(*calloc)(size_t, size_t, void *);
+ void (*free)(void *, void *);
+ void *(*alloc)(size_t, void *);
+};
+.Ed
+.Pp
+The
+.Va offset
+field holds the position of the key in each record;
+the
+.Va calloc
+and
+.Va free
+fields are pointers to
+.Xr calloc 3
+and
+.Xr free 3 Ns -like
+functions, used for managing the table internal storage;
+the
+.Va alloc
+field is only used by the utility function
+.Xr ohash_create_entry 3 .
+.Pp
+Each of these functions are called similarly to their standard counterpart,
+but with an extra
+.Ft void *
+parameter corresponding to the content of the field
+.Fa data ,
+which can be used to communicate specific information to the functions.
+.Pp
+.Fn ohash_init
+stores a copy of those fields internally, so
+.Fa info
+can be reclaimed after initialization.
+.Pp
+.Fn ohash_delete
+frees storage internal to
+.Fa h .
+Elements themselves should be freed by the user first, using for instance
+.Fn ohash_first
+and
+.Fn ohash_next .
+.Pp
+.Fn ohash_lookup_interval
+and
+.Fn ohash_lookup_memory
+are the basic look-up element functions.
+The hashing function result is provided by the user as
+.Fa hv .
+These return a
+.Qq slot
+in the ohash table
+.Fa h ,
+to be used with
+.Fn ohash_find ,
+.Fn ohash_insert ,
+or
+.Fn ohash_remove .
+This slot is only valid up to the next call to
+.Fn ohash_insert
+or
+.Fn ohash_remove .
+.Pp
+.Fn ohash_lookup_interval
+handles string-like keys.
+.Fn ohash_lookup_interval
+assumes the key is the interval between
+.Fa start
+and
+.Fa end ,
+exclusive,
+though the actual elements stored in the table should only contain
+NUL-terminated keys.
+.Pp
+.Fn ohash_lookup_memory
+assumes the key is the memory area starting at
+.Fa k
+of size
+.Fa s .
+All bytes are significant in key comparison.
+.Pp
+.Fn ohash_find
+retrieves an element from a slot
+.Fa i
+returned by the
+.Fn ohash_lookup*
+functions.
+It returns
+.Dv NULL
+if the slot is empty.
+.Pp
+.Fn ohash_insert
+inserts a new element
+.Fa p
+at slot
+.Fa i .
+Slot
+.Fa i
+must be empty and element
+.Fa p
+must have a key corresponding to the
+.Fn ohash_lookup*
+call.
+.Pp
+.Fn ohash_remove
+removes the element at slot
+.Fa i .
+It returns the removed element, for user code to dispose of, or
+.Dv NULL
+if the slot was empty.
+.Pp
+.Fn ohash_first
+and
+.Fn ohash_next
+can be used to access all elements in an ohash table, like this:
+.Bd -literal -offset indent
+for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
+ do_something_with(n);
+.Ed
+.Pp
+.Fa i
+points to an auxiliary unsigned integer used to record the current position
+in the ohash table.
+Those functions are safe to use even while entries are added to/removed
+from the table, but in such a case they don't guarantee that new entries
+will be returned.
+As a special case, they can safely be used to free elements in the table.
+.Pp
+.Fn ohash_entries
+returns the number of elements in the hash table.
+.Sh STORAGE HANDLING
+Only
+.Fn ohash_init ,
+.Fn ohash_insert ,
+.Fn ohash_remove
+and
+.Fn ohash_delete
+may call the user-supplied memory functions:
+.Bd -literal -offset indent
+p = (*info->calloc)(n, sizeof_record, info->data);
+/* copy data from old to p */
+(*info->free)(old, info->data);
+.Ed
+.Pp
+It is the responsibility of the user memory allocation code to verify
+that those calls did not fail.
+.Pp
+If memory allocation fails,
+.Fn ohash_init
+returns a useless hash table.
+.Fn ohash_insert
+and
+.Fn ohash_remove
+still perform the requested operation, but the returned table should be
+considered read-only.
+It can still be accessed by
+.Fn ohash_lookup* ,
+.Fn ohash_find ,
+.Fn ohash_first
+and
+.Fn ohash_next
+to dump relevant information to disk before aborting.
+.Sh THREAD SAFETY
+The open hashing functions are not thread-safe by design.
+In particular, in a threaded environment, there is no guarantee that a
+.Qq slot
+will not move between a
+.Fn ohash_lookup*
+and a
+.Fn ohash_find ,
+.Fn ohash_insert
+or
+.Fn ohash_remove
+call.
+.Pp
+Multi-threaded applications should explicitly protect ohash table access.
+.Sh SEE ALSO
+.Xr hcreate 3 ,
+.Xr ohash_interval 3
+.Rs
+.%A Donald E. Knuth
+.%B The Art of Computer Programming
+.%V Vol. 3
+.%P pp 506-550
+.%D 1973
+.Re
+.Sh STANDARDS
+Those functions are completely non-standard and should be avoided in
+portable programs.
+.Sh HISTORY
+Those functions were designed and written for
+.Ox
+.Xr make 1
+by Marc Espie in 1999.
diff --git a/_orig/lib/ohash_interval.3 b/_orig/lib/ohash_interval.3
new file mode 100644
index 0000000..f174a6f
--- /dev/null
+++ b/_orig/lib/ohash_interval.3
@@ -0,0 +1,93 @@
+.\" $OpenBSD: ohash_interval.3,v 1.1 2014/05/12 19:09:00 espie Exp $
+.\" Copyright (c) 2001 Marc Espie <espie@openbsd.org>
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.Dd $Mdocdate: May 12 2014 $
+.Dt OHASH_INTERVAL 3
+.Os
+.Sh NAME
+.Nm ohash_interval ,
+.Nm ohash_create_entry ,
+.Nm ohash_qlookup ,
+.Nm ohash_qlookupi
+.Nd helper functions for open hashing
+.Sh SYNOPSIS
+.In stdint.h
+.In stddef.h
+.In ohash.h
+.Ft uint32_t
+.Fn ohash_interval "const char *start" "const char **pend"
+.Ft "void *"
+.Fn ohash_create_entry "struct ohash_info *info" "const char *start" "const char **pend"
+.Ft "unsigned int"
+.Fn ohash_qlookupi "struct ohash *h" "const char *start" "const char **pend"
+.Ft "unsigned int"
+.Fn ohash_qlookup "struct ohash *h" "const char *start"
+.Sh DESCRIPTION
+These functions are commonly used to simplify open hashing usage, and use
+similar conventions.
+They operate indifferently on NUL-terminated strings
+.Po
+by setting
+.Fa *pend
+=
+.Dv NULL
+.Pc
+or memory ranges
+.Po
+delimited by
+.Fa start
+and
+.Fa *pend
+.Pc .
+For NUL-terminated strings, as a side effect, those functions
+set
+.Fa *pend
+to the terminating NUL byte.
+.Pp
+.Fn ohash_interval
+is a simple hashing function that yields good results on common data sets.
+.Pp
+.Fn ohash_create_entry
+can be used to create a new record with a given key.
+In that case,
+the alloc field of
+.Fa info
+should point to a
+.Xr malloc 3 Ns -like
+function to allocate the storage:
+.Bd -literal -offset indent
+p = (*info->alloc)(sz, info->data);
+.Ed
+.Pp
+.Fn ohash_qlookupi
+is a wrapper function that simply calls
+.Fn ohash_interval
+and
+.Fn ohash_lookup_interval .
+.Pp
+.Fn ohash_qlookup
+is a variation on
+.Fn ohash_qlookupi
+designed for NUL-terminated strings.
+.Sh SEE ALSO
+.Xr ohash_init 3
+.Sh STANDARDS
+Those functions are completely non-standard and should be avoided in
+portable programs.
+.Sh HISTORY
+Those functions were designed and written for
+.Ox
+.Xr make 1
+by Marc Espie in 1999.
diff --git a/_orig/lib/sha2.h b/_orig/lib/sha2.h
new file mode 100644
index 0000000..065c30d
--- /dev/null
+++ b/_orig/lib/sha2.h
@@ -0,0 +1,136 @@
+/* $OpenBSD: sha2.h,v 1.9 2013/04/15 15:54:17 millert Exp $ */
+
+/*
+ * FILE: sha2.h
+ * AUTHOR: Aaron D. Gifford <me@aarongifford.com>
+ *
+ * Copyright (c) 2000-2001, Aaron D. Gifford
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the copyright holder nor the names of contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTOR(S) ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTOR(S) BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $From: sha2.h,v 1.1 2001/11/08 00:02:01 adg Exp adg $
+ */
+
+#ifndef _SHA2_H
+#define _SHA2_H
+
+
+/*** SHA-256/384/512 Various Length Definitions ***********************/
+#define SHA224_BLOCK_LENGTH 64
+#define SHA224_DIGEST_LENGTH 28
+#define SHA224_DIGEST_STRING_LENGTH (SHA224_DIGEST_LENGTH * 2 + 1)
+#define SHA256_BLOCK_LENGTH 64
+#define SHA256_DIGEST_LENGTH 32
+#define SHA256_DIGEST_STRING_LENGTH (SHA256_DIGEST_LENGTH * 2 + 1)
+#define SHA384_BLOCK_LENGTH 128
+#define SHA384_DIGEST_LENGTH 48
+#define SHA384_DIGEST_STRING_LENGTH (SHA384_DIGEST_LENGTH * 2 + 1)
+#define SHA512_BLOCK_LENGTH 128
+#define SHA512_DIGEST_LENGTH 64
+#define SHA512_DIGEST_STRING_LENGTH (SHA512_DIGEST_LENGTH * 2 + 1)
+
+
+/*** SHA-224/256/384/512 Context Structure *******************************/
+typedef struct _SHA2_CTX {
+ union {
+ u_int32_t st32[8];
+ u_int64_t st64[8];
+ } state;
+ u_int64_t bitcount[2];
+ u_int8_t buffer[SHA512_BLOCK_LENGTH];
+} SHA2_CTX;
+
+__BEGIN_DECLS
+void SHA224Init(SHA2_CTX *);
+void SHA224Transform(u_int32_t state[8], const u_int8_t [SHA224_BLOCK_LENGTH]);
+void SHA224Update(SHA2_CTX *, const u_int8_t *, size_t)
+ __attribute__((__bounded__(__string__,2,3)));
+void SHA224Pad(SHA2_CTX *);
+void SHA224Final(u_int8_t [SHA224_DIGEST_LENGTH], SHA2_CTX *)
+ __attribute__((__bounded__(__minbytes__,1,SHA224_DIGEST_LENGTH)));
+char *SHA224End(SHA2_CTX *, char *)
+ __attribute__((__bounded__(__minbytes__,2,SHA224_DIGEST_STRING_LENGTH)));
+char *SHA224File(const char *, char *)
+ __attribute__((__bounded__(__minbytes__,2,SHA224_DIGEST_STRING_LENGTH)));
+char *SHA224FileChunk(const char *, char *, off_t, off_t)
+ __attribute__((__bounded__(__minbytes__,2,SHA224_DIGEST_STRING_LENGTH)));
+char *SHA224Data(const u_int8_t *, size_t, char *)
+ __attribute__((__bounded__(__string__,1,2)))
+ __attribute__((__bounded__(__minbytes__,3,SHA224_DIGEST_STRING_LENGTH)));
+
+void SHA256Init(SHA2_CTX *);
+void SHA256Transform(u_int32_t state[8], const u_int8_t [SHA256_BLOCK_LENGTH]);
+void SHA256Update(SHA2_CTX *, const u_int8_t *, size_t)
+ __attribute__((__bounded__(__string__,2,3)));
+void SHA256Pad(SHA2_CTX *);
+void SHA256Final(u_int8_t [SHA256_DIGEST_LENGTH], SHA2_CTX *)
+ __attribute__((__bounded__(__minbytes__,1,SHA256_DIGEST_LENGTH)));
+char *SHA256End(SHA2_CTX *, char *)
+ __attribute__((__bounded__(__minbytes__,2,SHA256_DIGEST_STRING_LENGTH)));
+char *SHA256File(const char *, char *)
+ __attribute__((__bounded__(__minbytes__,2,SHA256_DIGEST_STRING_LENGTH)));
+char *SHA256FileChunk(const char *, char *, off_t, off_t)
+ __attribute__((__bounded__(__minbytes__,2,SHA256_DIGEST_STRING_LENGTH)));
+char *SHA256Data(const u_int8_t *, size_t, char *)
+ __attribute__((__bounded__(__string__,1,2)))
+ __attribute__((__bounded__(__minbytes__,3,SHA256_DIGEST_STRING_LENGTH)));
+
+void SHA384Init(SHA2_CTX *);
+void SHA384Transform(u_int64_t state[8], const u_int8_t [SHA384_BLOCK_LENGTH]);
+void SHA384Update(SHA2_CTX *, const u_int8_t *, size_t)
+ __attribute__((__bounded__(__string__,2,3)));
+void SHA384Pad(SHA2_CTX *);
+void SHA384Final(u_int8_t [SHA384_DIGEST_LENGTH], SHA2_CTX *)
+ __attribute__((__bounded__(__minbytes__,1,SHA384_DIGEST_LENGTH)));
+char *SHA384End(SHA2_CTX *, char *)
+ __attribute__((__bounded__(__minbytes__,2,SHA384_DIGEST_STRING_LENGTH)));
+char *SHA384File(const char *, char *)
+ __attribute__((__bounded__(__minbytes__,2,SHA384_DIGEST_STRING_LENGTH)));
+char *SHA384FileChunk(const char *, char *, off_t, off_t)
+ __attribute__((__bounded__(__minbytes__,2,SHA384_DIGEST_STRING_LENGTH)));
+char *SHA384Data(const u_int8_t *, size_t, char *)
+ __attribute__((__bounded__(__string__,1,2)))
+ __attribute__((__bounded__(__minbytes__,3,SHA384_DIGEST_STRING_LENGTH)));
+
+void SHA512Init(SHA2_CTX *);
+void SHA512Transform(u_int64_t state[8], const u_int8_t [SHA512_BLOCK_LENGTH]);
+void SHA512Update(SHA2_CTX *, const u_int8_t *, size_t)
+ __attribute__((__bounded__(__string__,2,3)));
+void SHA512Pad(SHA2_CTX *);
+void SHA512Final(u_int8_t [SHA512_DIGEST_LENGTH], SHA2_CTX *)
+ __attribute__((__bounded__(__minbytes__,1,SHA512_DIGEST_LENGTH)));
+char *SHA512End(SHA2_CTX *, char *)
+ __attribute__((__bounded__(__minbytes__,2,SHA512_DIGEST_STRING_LENGTH)));
+char *SHA512File(const char *, char *)
+ __attribute__((__bounded__(__minbytes__,2,SHA512_DIGEST_STRING_LENGTH)));
+char *SHA512FileChunk(const char *, char *, off_t, off_t)
+ __attribute__((__bounded__(__minbytes__,2,SHA512_DIGEST_STRING_LENGTH)));
+char *SHA512Data(const u_int8_t *, size_t, char *)
+ __attribute__((__bounded__(__string__,1,2)))
+ __attribute__((__bounded__(__minbytes__,3,SHA512_DIGEST_STRING_LENGTH)));
+__END_DECLS
+
+#endif /* _SHA2_H */