---
blowfish.c | 515 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
blowfish.h | 5 +
2 files changed, 518 insertions(+), 2 deletions(-)
diff --git a/blowfish.c b/blowfish.c
index 52040f13..d0b45117 100644
--- a/blowfish.c
+++ b/blowfish.c
@@ -45,7 +45,12 @@
(from Nettle's blowfish.h), dropping the libgcrypt wrapper
functions, fixing #include's, remove support for non-16 rounds
(there are no test vectors), adding FOR_BLOCK iterations, and
- running indent on the code. */
+ running indent on the code.
+
+ The lower half of this file includes code for the computation
+ of bcrypt hashes, which was added at a later date.
+
+ */
#if HAVE_CONFIG_H
#include "config.h"
@@ -397,7 +402,7 @@ blowfish_set_key (struct blowfish_ctx *ctx,
ctx->p[i] = datal;
ctx->p[i + 1] = datar;
}
-
+
for (j = 0; j < 4; j++)
for (i = 0; i < 256; i += 2)
{
@@ -428,3 +433,509 @@ blowfish128_set_key(struct blowfish_ctx *ctx, const
uint8_t *key)
{
return blowfish_set_key (ctx, BLOWFISH128_KEY_SIZE, key);
}
+
+/*
+ * The crypt_blowfish homepage is:
+ *
+ * http://www.openwall.com/crypt/
+ *
+ * This code comes from John the Ripper password cracker, with reentrant
+ * and crypt(3) interfaces added, but optimizations specific to password
+ * cracking removed.
+ *
+ * Written by Solar Designer <solar at openwall.com> in 1998-2015.
+ * No copyright is claimed, and the software is hereby placed in the public
+ * domain. In case this attempt to disclaim copyright and place the software
+ * in the public domain is deemed null and void, then the software is
+ * Copyright (c) 1998-2015 Solar Designer and it is hereby released to the
+ * general public under the following terms:
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted.
+ *
+ * There's ABSOLUTELY NO WARRANTY, express or implied.
+ *
+ * It is my intent that you should be able to use this on your system,
+ * as part of a software package, or anywhere else to improve security,
+ * ensure compatibility, or for any other purpose. I would appreciate
+ * it if you give credit where it is due and keep your modifications in
+ * the public domain as well, but I don't require that in order to let
+ * you place this code and any modifications you make under a license
+ * of your choice.
+ *
+ * This implementation is fully compatible with OpenBSD's bcrypt.c for prefix
+ * "$2b$", originally by Niels Provos <provos at citi.umich.edu>, and it uses
+ * some of his ideas. The password hashing algorithm was designed by David
+ * Mazieres <dm at lcs.mit.edu>. For information on the level of
+ * compatibility for bcrypt hash prefixes other than "$2b$", please refer to
+ * the comments in BF_set_key() below and to the included crypt(3) man page.
+ *
+ * There's a paper on the algorithm that explains its design decisions:
+ *
+ * http://www.usenix.org/events/usenix99/provos.html
+ */
+
+#include <string.h>
+
+#include <errno.h>
+#ifndef __set_errno
+#define __set_errno(val) errno = (val)
+#endif
+
+typedef uint32_t BF_key[_BLOWFISH_ROUNDS + 2];
+
+/*
+ * Magic IV for 64 Blowfish encryptions that we do at the end.
+ * The string is "OrpheanBeholderScryDoubt" on big-endian.
+ */
+static uint32_t BF_magic_w[6] = {
+ 0x4F727068, 0x65616E42, 0x65686F6C,
+ 0x64657253, 0x63727944, 0x6F756274
+};
+
+static unsigned char BF_itoa64[64 + 1] =
+ "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
+
+static unsigned char BF_atoi64[0x60] = {
+ 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 0, 1,
+ 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 64, 64, 64, 64, 64,
+ 64, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
+ 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 64, 64, 64, 64, 64,
+ 64, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
+ 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 64, 64, 64, 64, 64
+};
+
+#define BF_safe_atoi64(dst, src) \
+{ \
+ tmp = (unsigned char)(src); \
+ if ((unsigned int)(tmp -= 0x20) >= 0x60) return -1; \
+ tmp = BF_atoi64[tmp]; \
+ if (tmp > 63) return -1; \
+ (dst) = tmp; \
+}
+
+static int BF_decode(uint32_t *dst, const char *src, int size)
+{
+ unsigned char *dptr = (unsigned char *)dst;
+ unsigned char *end = dptr + size;
+ const unsigned char *sptr = (const unsigned char *)src;
+ unsigned int tmp, c1, c2, c3, c4;
+
+ do {
+ BF_safe_atoi64(c1, *sptr++);
+ BF_safe_atoi64(c2, *sptr++);
+ *dptr++ = (c1 << 2) | ((c2 & 0x30) >> 4);
+ if (dptr >= end) break;
+
+ BF_safe_atoi64(c3, *sptr++);
+ *dptr++ = ((c2 & 0x0F) << 4) | ((c3 & 0x3C) >> 2);
+ if (dptr >= end) break;
+
+ BF_safe_atoi64(c4, *sptr++);
+ *dptr++ = ((c3 & 0x03) << 6) | c4;
+ } while (dptr < end);
+
+ if (end - dptr == size)
+ return -1;
+
+ *dptr = 0;
+
+ return 0;
+}
+
+static void BF_encode(char *dst, const uint32_t *src, int size)
+{
+ const unsigned char *sptr = (const unsigned char *)src;
+ const unsigned char *end = sptr + size;
+ unsigned char *dptr = (unsigned char *)dst;
+ unsigned int c1, c2;
+
+ do {
+ c1 = *sptr++;
+ *dptr++ = BF_itoa64[c1 >> 2];
+ c1 = (c1 & 0x03) << 4;
+ if (sptr >= end) {
+ *dptr++ = BF_itoa64[c1];
+ break;
+ }
+
+ c2 = *sptr++;
+ c1 |= c2 >> 4;
+ *dptr++ = BF_itoa64[c1];
+ c1 = (c2 & 0x0f) << 2;
+ if (sptr >= end) {
+ *dptr++ = BF_itoa64[c1];
+ break;
+ }
+
+ c2 = *sptr++;
+ c1 |= c2 >> 6;
+ *dptr++ = BF_itoa64[c1];
+ *dptr++ = BF_itoa64[c2 & 0x3f];
+ } while (sptr < end);
+}
+
+static void BF_swap(uint32_t *x, int count)
+{
+ static int endianness_check = 1;
+ char *is_little_endian = (char *)&endianness_check;
+ uint32_t tmp;
+
+ if (*is_little_endian)
+ do {
+ tmp = *x;
+ tmp = (tmp << 16) | (tmp >> 16);
+ *x++ = ((tmp & 0x00FF00FF) << 8) | ((tmp >> 8) & 0x00FF00FF);
+ } while (--count);
+}
+
+static void BF_set_key(const char *key, BF_key expanded, BF_key initial,
+ unsigned char flags)
+{
+ const char *ptr = key;
+ unsigned int bug, i, j;
+ uint32_t safety, sign, diff, tmp[2];
+
+/*
+ * There was a sign extension bug in older revisions of this function. While
+ * we would have liked to simply fix the bug and move on, we have to provide
+ * a backwards compatibility feature (essentially the bug) for some systems and
+ * a safety measure for some others. The latter is needed because for certain
+ * multiple inputs to the buggy algorithm there exist easily found inputs to
+ * the correct algorithm that produce the same hash. Thus, we optionally
+ * deviate from the correct algorithm just enough to avoid such collisions.
+ * While the bug itself affected the majority of passwords containing
+ * characters with the 8th bit set (although only a percentage of those in a
+ * collision-producing way), the anti-collision safety measure affects
+ * only a subset of passwords containing the '\xff' character (not even all of
+ * those passwords, just some of them). This character is not found in valid
+ * UTF-8 sequences and is rarely used in popular 8-bit character encodings.
+ * Thus, the safety measure is unlikely to cause much annoyance, and is a
+ * reasonable tradeoff to use when authenticating against existing hashes that
+ * are not reliably known to have been computed with the correct algorithm.
+ *
+ * We use an approach that tries to minimize side-channel leaks of password
+ * information - that is, we mostly use fixed-cost bitwise operations instead
+ * of branches or table lookups. (One conditional branch based on password
+ * length remains. It is not part of the bug aftermath, though, and is
+ * difficult and possibly unreasonable to avoid given the use of C strings by
+ * the caller, which results in similar timing leaks anyway.)
+ *
+ * For actual implementation, we set an array index in the variable "bug"
+ * (0 means no bug, 1 means sign extension bug emulation) and a flag in the
+ * variable "safety" (bit 16 is set when the safety measure is requested).
+ * Valid combinations of settings are:
+ *
+ * Prefix "$2a$": bug = 0, safety = 0x10000
+ * Prefix "$2b$": bug = 0, safety = 0
+ * Prefix "$2x$": bug = 1, safety = 0
+ * Prefix "$2y$": bug = 0, safety = 0
+ */
+ bug = (unsigned int)flags & 1;
+ safety = ((uint32_t)flags & 2) << 15;
+
+ sign = diff = 0;
+
+ for (i = 0; i < _BLOWFISH_ROUNDS + 2; i++) {
+ tmp[0] = tmp[1] = 0;
+ for (j = 0; j < 4; j++) {
+ tmp[0] <<= 8;
+ tmp[0] |= (unsigned char)*ptr; /* correct */
+ tmp[1] <<= 8;
+ tmp[1] |= (signed char)*ptr; /* bug */
+/*
+ * Sign extension in the first char has no effect - nothing to overwrite yet,
+ * and those extra 24 bits will be fully shifted out of the 32-bit word. For
+ * chars 2, 3, 4 in each four-char block, we set bit 7 of "sign" if sign
+ * extension in tmp[1] occurs. Once this flag is set, it remains set.
+ */
+ if (j)
+ sign |= tmp[1] & 0x80;
+ if (!*ptr)
+ ptr = key;
+ else
+ ptr++;
+ }
+ diff |= tmp[0] ^ tmp[1]; /* Non-zero on any differences */
+
+ expanded[i] = tmp[bug];
+ initial[i] = initial_ctx.p[i] ^ tmp[bug];
+ }
+
+/*
+ * At this point, "diff" is zero iff the correct and buggy algorithms produced
+ * exactly the same result. If so and if "sign" is non-zero, which indicates
+ * that there was a non-benign sign extension, this means that we have a
+ * collision between the correctly computed hash for this password and a set of
+ * passwords that could be supplied to the buggy algorithm. Our safety measure
+ * is meant to protect from such many-buggy to one-correct collisions, by
+ * deviating from the correct algorithm in such cases. Let's check for this.
+ */
+ diff |= diff >> 16; /* still zero iff exact match */
+ diff &= 0xffff; /* ditto */
+ diff += 0xffff; /* bit 16 set iff "diff" was non-zero (on non-match) */
+ sign <<= 9; /* move the non-benign sign extension flag to bit 16 */
+ sign &= ~diff & safety; /* action needed? */
+
+/*
+ * If we have determined that we need to deviate from the correct algorithm,
+ * flip bit 16 in initial expanded key. (The choice of 16 is arbitrary, but
+ * let's stick to it now. It came out of the approach we used above, and it's
+ * not any worse than any other choice we could make.)
+ *
+ * It is crucial that we don't do the same to the expanded key used in the main
+ * Eksblowfish loop. By doing it to only one of these two, we deviate from a
+ * state that could be directly specified by a password to the buggy algorithm
+ * (and to the fully correct one as well, but that's a side-effect).
+ */
+ initial[0] ^= sign;
+}
+
+static const unsigned char flags_by_subtype[26] =
+ {2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 0};
+
+static char *BF_crypt(const char *key, const char *settings,
+ char *output, int size,
+ uint32_t min)
+{
+ struct {
+ struct blowfish_ctx ctx;
+ BF_key expanded_key;
+ union {
+ uint32_t salt[4];
+ uint32_t output[6];
+ } binary;
+ } data;
+ uint32_t L, R;
+ uint32_t tmp1, tmp2, tmp3, tmp4;
+ uint32_t *ptr;
+ uint32_t count;
+ int i;
+
+ if (size < 7 + 22 + 31 + 1) {
+ __set_errno(ERANGE);
+ return NULL;
+ }
+
+ if (settings[0] != '$' ||
+ settings[1] != '2' ||
+ settings[2] < 'a' || settings[2] > 'z' ||
+ !flags_by_subtype[(unsigned int)(unsigned char)settings[2] - 'a'] ||
+ settings[3] != '$' ||
+ settings[4] < '0' || settings[4] > '3' ||
+ settings[5] < '0' || settings[5] > '9' ||
+ (settings[4] == '3' && settings[5] > '1') ||
+ settings[6] != '$') {
+ __set_errno(EINVAL);
+ return NULL;
+ }
+
+ count = (uint32_t)1 << ((settings[4] - '0') * 10 + (settings[5] - '0'));
+ if (count < min || BF_decode(data.binary.salt, &settings[7], 16)) {
+ __set_errno(EINVAL);
+ return NULL;
+ }
+ BF_swap(data.binary.salt, 4);
+
+ BF_set_key(key, data.expanded_key, data.ctx.p,
+ flags_by_subtype[(unsigned int)(unsigned char)settings[2] - 'a']);
+
+ memcpy(data.ctx.s, initial_ctx.s, sizeof(data.ctx.s));
+
+ L = R = 0;
+ for (i = 0; i < _BLOWFISH_ROUNDS + 2; i += 2) {
+ L ^= data.binary.salt[i & 2];
+ R ^= data.binary.salt[(i & 2) + 1];
+ encrypt(&data.ctx, &L, &R);
+ data.ctx.p[i] = L;
+ data.ctx.p[i + 1] = R;
+ }
+
+ ptr = data.ctx.s[0];
+ do {
+ ptr += 4;
+ L ^= data.binary.salt[(_BLOWFISH_ROUNDS + 2) & 3];
+ R ^= data.binary.salt[(_BLOWFISH_ROUNDS + 3) & 3];
+ encrypt(&data.ctx, &L, &R);
+ *(ptr - 4) = L;
+ *(ptr - 3) = R;
+
+ L ^= data.binary.salt[(_BLOWFISH_ROUNDS + 4) & 3];
+ R ^= data.binary.salt[(_BLOWFISH_ROUNDS + 5) & 3];
+ encrypt(&data.ctx, &L, &R);
+ *(ptr - 2) = L;
+ *(ptr - 1) = R;
+ } while (ptr < &data.ctx.s[3][0xFF]);
+
+ do {
+ int done;
+
+ for (i = 0; i < _BLOWFISH_ROUNDS + 2; i += 2) {
+ data.ctx.p[i] ^= data.expanded_key[i];
+ data.ctx.p[i + 1] ^= data.expanded_key[i + 1];
+ }
+
+ done = 0;
+ do {
+ L = R = 0;
+ ptr = data.ctx.p;
+ do {
+ ptr += 2;
+ encrypt(&data.ctx, &L, &R);
+ *(ptr - 2) = L;
+ *(ptr - 1) = R;
+ } while (ptr < &data.ctx.p[_BLOWFISH_ROUNDS + 2]);
+
+ ptr = data.ctx.s[0];
+ do {
+ ptr += 2;
+ encrypt(&data.ctx, &L, &R);
+ *(ptr - 2) = L;
+ *(ptr - 1) = R;
+ } while (ptr < &data.ctx.s[3][0xFF]);
+
+ if (done)
+ break;
+ done = 1;
+
+ tmp1 = data.binary.salt[0];
+ tmp2 = data.binary.salt[1];
+ tmp3 = data.binary.salt[2];
+ tmp4 = data.binary.salt[3];
+ for (i = 0; i < _BLOWFISH_ROUNDS; i += 4) {
+ data.ctx.p[i] ^= tmp1;
+ data.ctx.p[i + 1] ^= tmp2;
+ data.ctx.p[i + 2] ^= tmp3;
+ data.ctx.p[i + 3] ^= tmp4;
+ }
+ data.ctx.p[16] ^= tmp1;
+ data.ctx.p[17] ^= tmp2;
+ } while (1);
+ } while (--count);
+
+ for (i = 0; i < 6; i += 2) {
+ L = BF_magic_w[i];
+ R = BF_magic_w[i + 1];
+
+ count = 64;
+ do {
+ encrypt(&data.ctx, &L, &R);
+ } while (--count);
+
+ data.binary.output[i] = L;
+ data.binary.output[i + 1] = R;
+ }
+
+ memcpy(output, settings, 7 + 22 - 1);
+ output[7 + 22 - 1] = BF_itoa64[(int)
+ BF_atoi64[(int)settings[7 + 22 - 1] - 0x20] & 0x30];
+
+/* This has to be bug-compatible with the original implementation, so
+ * only encode 23 of the 24 bytes. :-) */
+ BF_swap(data.binary.output, 6);
+ BF_encode(&output[7 + 22], data.binary.output, 23);
+ output[7 + 22 + 31] = '\0';
+
+ return output;
+}
+
+static int bcrypt_output_magic(const char *settings, char *output, int size)
+{
+ if (size < 3)
+ return -1;
+
+ output[0] = '*';
+ output[1] = '0';
+ output[2] = '\0';
+
+ if (settings[0] == '*' && settings[1] == '0')
+ output[1] = '1';
+
+ return 0;
+}
+
+/*
+ * Please preserve the runtime self-test. It serves two purposes at once:
+ *
+ * 1. We really can't afford the risk of producing incompatible hashes e.g.
+ * when there's something like gcc bug 26587 again, whereas an application or
+ * library integrating this code might not also integrate our external tests or
+ * it might not run them after every build. Even if it does, the miscompile
+ * might only occur on the production build, but not on a testing build (such
+ * as because of different optimization settings). It is painful to recover
+ * from incorrectly-computed hashes - merely fixing whatever broke is not
+ * enough. Thus, a proactive measure like this self-test is needed.
+ *
+ * 2. We don't want to leave sensitive data from our actual password hash
+ * computation on the stack or in registers. Previous revisions of the code
+ * would do explicit cleanups, but simply running the self-test after hash
+ * computation is more reliable.
+ *
+ * The performance cost of this quick self-test is around 0.6% at the "$2a$08"
+ * setting.
+ */
+uint8_t *blowfish_bcrypt(const uint8_t *key, const uint8_t *settings,
+ uint8_t *dst, size_t length)
+{
+ const char *test_pw = "8b \xd0\xc1\xd2\xcf\xcc\xd8";
+ const char *test_settings = "$2a$00$abcdefghijklmnopqrstuu";
+ static const char * const test_hashes[2] =
+ {"i1D709vfamulimlGcq0qq3UvuUasvEa\0\x55", /* 'a', 'b', 'y' */
+ "VUrPmXD6q/nVSSp7pNDhCR9071IfIRe\0\x55"}; /* 'x' */
+ const char *test_hash = test_hashes[0];
+ uint8_t *retval;
+ const char *p;
+ int save_errno, ok;
+ struct {
+ char s[7 + 22 + 1];
+ char o[7 + 22 + 31 + 1 + 1 + 1];
+ } buf;
+
+/* Hash the supplied password */
+ bcrypt_output_magic(settings, dst, length);
+ retval = BF_crypt(key, settings, dst, length, 16);
+ save_errno = errno;
+
+/*
+ * Do a quick self-test. It is important that we make both calls to BF_crypt()
+ * from the same scope such that they likely use the same stack locations,
+ * which makes the second call overwrite the first call's sensitive data on the
+ * stack and makes it more likely that any alignment related issues would be
+ * detected by the self-test.
+ */
+ memcpy(buf.s, test_settings, sizeof(buf.s));
+ if (retval) {
+ unsigned int flags = flags_by_subtype[
+ (unsigned int)(unsigned char)settings[2] - 'a'];
+ test_hash = test_hashes[flags & 1];
+ buf.s[2] = settings[2];
+ }
+ memset(buf.o, 0x55, sizeof(buf.o));
+ buf.o[sizeof(buf.o) - 1] = 0;
+ p = BF_crypt(test_pw, buf.s, buf.o, sizeof(buf.o) - (1 + 1), 1);
+
+ ok = (p == buf.o &&
+ !memcmp(p, buf.s, 7 + 22) &&
+ !memcmp(p + (7 + 22), test_hash, 31 + 1 + 1 + 1));
+
+ {
+ const char *k = "\xff\xa3" "34" "\xff\xff\xff\xa3" "345";
+ BF_key ae, ai, ye, yi;
+ BF_set_key(k, ae, ai, 2); /* $2a$ */
+ BF_set_key(k, ye, yi, 4); /* $2y$ */
+ ai[0] ^= 0x10000; /* undo the safety (for comparison) */
+ ok = ok && ai[0] == 0xdb9c59bc && ye[17] == 0x33343500 &&
+ !memcmp(ae, ye, sizeof(ae)) &&
+ !memcmp(ai, yi, sizeof(ai));
+ }
+
+ __set_errno(save_errno);
+ if (ok)
+ return retval;
+
+/* Should not happen */
+ bcrypt_output_magic(settings, dst, length);
+ __set_errno(EINVAL); /* pretend we don't support this hash type */
+ return NULL;
+}
diff --git a/blowfish.h b/blowfish.h
index bcdc7cb6..ae7f5b12 100644
--- a/blowfish.h
+++ b/blowfish.h
@@ -81,6 +81,11 @@ void
blowfish_decrypt(const struct blowfish_ctx *ctx,
size_t length, uint8_t *dst,
const uint8_t *src);
+uint8_t *
+blowfish_bcrypt(const uint8_t *key,
+ const uint8_t *settings,
+ uint8_t *dst,
+ size_t length);
#ifdef __cplusplus
}
--
2.20.1
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
