Back to index

php5  5.3.10
Classes | Defines | Typedefs | Functions | Variables
crypt_blowfish.c File Reference
#include <string.h>
#include <errno.h>
#include "crypt_blowfish.h"

Go to the source code of this file.

Classes

struct  BF_ctx

Defines

#define __set_errno(val)   errno = (val)
#define BF_ASM   0
#define BF_SCALE   0
#define BF_N   16
#define BF_safe_atoi64(dst, src)
#define BF_INDEX(S, i)   (*((BF_word *)(((unsigned char *)S) + (i))))
#define BF_ROUND(L, R, N)
#define BF_ENCRYPT
#define BF_body()

Typedefs

typedef unsigned int BF_word
typedef signed int BF_word_signed
typedef BF_word BF_key [BF_N+2]

Functions

static int BF_decode (BF_word *dst, const char *src, int size)
static void BF_encode (char *dst, const BF_word *src, int size)
static void BF_swap (BF_word *x, int count)
static void BF_set_key (const char *key, BF_key expanded, BF_key initial, unsigned char flags)
static char * BF_crypt (const char *key, const char *setting, char *output, int size, BF_word min)
static int _crypt_output_magic (const char *setting, char *output, int size)
char * php_crypt_blowfish_rn (const char *key, const char *setting, char *output, int size)

Variables

static BF_word BF_magic_w [6]
static BF_ctx BF_init_state
static unsigned char BF_itoa64 [64+1] = "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
static unsigned char BF_atoi64 [0x60]

Class Documentation

struct BF_ctx

Definition at line 76 of file crypt_blowfish.c.

Class Members
BF_key P
BF_word S

Define Documentation

#define __set_errno (   val)    errno = (val)

Definition at line 51 of file crypt_blowfish.c.

#define BF_ASM   0

Definition at line 64 of file crypt_blowfish.c.

#define BF_body ( )
Value:
L = R = 0; \
	ptr = data.ctx.P; \
       do { \
		ptr += 2; \
              BF_ENCRYPT; \
              *(ptr - 2) = L; \
              *(ptr - 1) = R; \
       } while (ptr < &data.ctx.P[BF_N + 2]); \
\
	ptr = data.ctx.S[0]; \
       do { \
		ptr += 2; \
              BF_ENCRYPT; \
              *(ptr - 2) = L; \
              *(ptr - 1) = R; \
       } while (ptr < &data.ctx.S[3][0xFF]);

Definition at line 529 of file crypt_blowfish.c.

#define BF_ENCRYPT
Value:
L ^= data.ctx.P[0]; \
       BF_ROUND(L, R, 0); \
       BF_ROUND(R, L, 1); \
       BF_ROUND(L, R, 2); \
       BF_ROUND(R, L, 3); \
       BF_ROUND(L, R, 4); \
       BF_ROUND(R, L, 5); \
       BF_ROUND(L, R, 6); \
       BF_ROUND(R, L, 7); \
       BF_ROUND(L, R, 8); \
       BF_ROUND(R, L, 9); \
       BF_ROUND(L, R, 10); \
       BF_ROUND(R, L, 11); \
       BF_ROUND(L, R, 12); \
       BF_ROUND(R, L, 13); \
       BF_ROUND(L, R, 14); \
       BF_ROUND(R, L, 15); \
       tmp4 = R; \
       R = L; \
       L = tmp4 ^ data.ctx.P[BF_N + 1];

Definition at line 503 of file crypt_blowfish.c.

#define BF_INDEX (   S,
 
)    (*((BF_word *)(((unsigned char *)S) + (i))))

Definition at line 479 of file crypt_blowfish.c.

#define BF_N   16

Definition at line 72 of file crypt_blowfish.c.

#define BF_ROUND (   L,
  R,
  N 
)
Value:
tmp1 = L & 0xFF; \
       tmp1 <<= 2; \
       tmp2 = L >> 6; \
       tmp2 &= 0x3FC; \
       tmp3 = L >> 14; \
       tmp3 &= 0x3FC; \
       tmp4 = L >> 22; \
       tmp4 &= 0x3FC; \
       tmp1 = BF_INDEX(data.ctx.S[3], tmp1); \
       tmp2 = BF_INDEX(data.ctx.S[2], tmp2); \
       tmp3 = BF_INDEX(data.ctx.S[1], tmp3); \
       tmp3 += BF_INDEX(data.ctx.S[0], tmp4); \
       tmp3 ^= tmp2; \
       R ^= data.ctx.P[N + 1]; \
       tmp3 += tmp1; \
       R ^= tmp3;

Definition at line 481 of file crypt_blowfish.c.

#define BF_safe_atoi64 (   dst,
  src 
)
Value:
{ \
       tmp = (unsigned char)(src); \
       if (tmp == '$') break; /* PHP hack */ \
       if ((unsigned int)(tmp -= 0x20) >= 0x60) return -1; \
       tmp = BF_atoi64[tmp]; \
       if (tmp > 63) return -1; \
       (dst) = tmp; \
}

Definition at line 377 of file crypt_blowfish.c.

#define BF_SCALE   0

Definition at line 65 of file crypt_blowfish.c.


Typedef Documentation

typedef BF_word BF_key[BF_N+2]

Definition at line 74 of file crypt_blowfish.c.

typedef unsigned int BF_word

Definition at line 68 of file crypt_blowfish.c.

typedef signed int BF_word_signed

Definition at line 69 of file crypt_blowfish.c.


Function Documentation

static int _crypt_output_magic ( const char *  setting,
char *  output,
int  size 
) [static]

Definition at line 784 of file crypt_blowfish.c.

{
       if (size < 3)
              return -1;

       output[0] = '*';
       output[1] = '0';
       output[2] = '\0';

       if (setting[0] == '*' && setting[1] == '0')
              output[1] = '1';

       return 0;
}

Here is the caller graph for this function:

static char* BF_crypt ( const char *  key,
const char *  setting,
char *  output,
int  size,
BF_word  min 
) [static]

Definition at line 649 of file crypt_blowfish.c.

{
#if BF_ASM
       extern void _BF_body_r(BF_ctx *ctx);
#endif
       static const unsigned char flags_by_subtype[26] =
              {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
              0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 0};
       struct {
              BF_ctx ctx;
              BF_key expanded_key;
              union {
                     BF_word salt[4];
                     BF_word output[6];
              } binary;
       } data;
       BF_word L, R;
       BF_word tmp1, tmp2, tmp3, tmp4;
       BF_word *ptr;
       BF_word count;
       int i;

       if (size < 7 + 22 + 31 + 1) {
              __set_errno(ERANGE);
              return NULL;
       }

       if (setting[0] != '$' ||
           setting[1] != '2' ||
           setting[2] < 'a' || setting[2] > 'z' ||
           !flags_by_subtype[(unsigned int)(unsigned char)setting[2] - 'a'] ||
           setting[3] != '$' ||
           setting[4] < '0' || setting[4] > '3' ||
           setting[5] < '0' || setting[5] > '9' ||
           (setting[4] == '3' && setting[5] > '1') ||
           setting[6] != '$') {
              __set_errno(EINVAL);
              return NULL;
       }

       count = (BF_word)1 << ((setting[4] - '0') * 10 + (setting[5] - '0'));
       if (count < min || BF_decode(data.binary.salt, &setting[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)setting[2] - 'a']);

       memcpy(data.ctx.S, BF_init_state.S, sizeof(data.ctx.S));

       L = R = 0;
       for (i = 0; i < BF_N + 2; i += 2) {
              L ^= data.binary.salt[i & 2];
              R ^= data.binary.salt[(i & 2) + 1];
              BF_ENCRYPT;
              data.ctx.P[i] = L;
              data.ctx.P[i + 1] = R;
       }

       ptr = data.ctx.S[0];
       do {
              ptr += 4;
              L ^= data.binary.salt[(BF_N + 2) & 3];
              R ^= data.binary.salt[(BF_N + 3) & 3];
              BF_ENCRYPT;
              *(ptr - 4) = L;
              *(ptr - 3) = R;

              L ^= data.binary.salt[(BF_N + 4) & 3];
              R ^= data.binary.salt[(BF_N + 5) & 3];
              BF_ENCRYPT;
              *(ptr - 2) = L;
              *(ptr - 1) = R;
       } while (ptr < &data.ctx.S[3][0xFF]);

       do {
              int done;

              for (i = 0; i < BF_N + 2; i += 2) {
                     data.ctx.P[i] ^= data.expanded_key[i];
                     data.ctx.P[i + 1] ^= data.expanded_key[i + 1];
              }

              done = 0;
              do {
                     BF_body();
                     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 < BF_N; 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 {
                     BF_ENCRYPT;
              } while (--count);

              data.binary.output[i] = L;
              data.binary.output[i + 1] = R;
       }

       memcpy(output, setting, 7 + 22 - 1);
       output[7 + 22 - 1] = BF_itoa64[(int)
              BF_atoi64[(int)setting[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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int BF_decode ( BF_word dst,
const char *  src,
int  size 
) [static]

Definition at line 387 of file crypt_blowfish.c.

{
       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);

       while (dptr < end) /* PHP hack */
              *dptr++ = 0;

       return 0;
}

Here is the caller graph for this function:

static void BF_encode ( char *  dst,
const BF_word src,
int  size 
) [static]

Definition at line 414 of file crypt_blowfish.c.

{
       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);
}

Here is the caller graph for this function:

static void BF_set_key ( const char *  key,
BF_key  expanded,
BF_key  initial,
unsigned char  flags 
) [static]

Definition at line 548 of file crypt_blowfish.c.

{
       const char *ptr = key;
       unsigned int bug, i, j;
       BF_word 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 "$2x$": bug = 1, safety = 0
 * Prefix "$2y$": bug = 0, safety = 0
 */
       bug = (unsigned int)flags & 1;
       safety = ((BF_word)flags & 2) << 15;

       sign = diff = 0;

       for (i = 0; i < BF_N + 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] |= (BF_word_signed)(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] = BF_init_state.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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void BF_swap ( BF_word x,
int  count 
) [static]

Definition at line 446 of file crypt_blowfish.c.

{
       static int endianness_check = 1;
       char *is_little_endian = (char *)&endianness_check;
       BF_word tmp;

       if (*is_little_endian)
       do {
              tmp = *x;
              tmp = (tmp << 16) | (tmp >> 16);
              *x++ = ((tmp & 0x00FF00FF) << 8) | ((tmp >> 8) & 0x00FF00FF);
       } while (--count);
}

Here is the caller graph for this function:

char* php_crypt_blowfish_rn ( const char *  key,
const char *  setting,
char *  output,
int  size 
)

Definition at line 819 of file crypt_blowfish.c.

{
       const char *test_key = "8b \xd0\xc1\xd2\xcf\xcc\xd8";
       const char *test_setting = "$2a$00$abcdefghijklmnopqrstuu";
       static const char * const test_hash[2] =
              {"VUrPmXD6q/nVSSp7pNDhCR9071IfIRe\0\x55", /* $2x$ */
              "i1D709vfamulimlGcq0qq3UvuUasvEa\0\x55"}; /* $2a$, $2y$ */
       char *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 */
       _crypt_output_magic(setting, output, size);
       retval = BF_crypt(key, setting, output, size, 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_setting, sizeof(buf.s));
       if (retval)
              buf.s[2] = setting[2];
       memset(buf.o, 0x55, sizeof(buf.o));
       buf.o[sizeof(buf.o) - 1] = 0;
       p = BF_crypt(test_key, 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[(unsigned int)(unsigned char)buf.s[2] & 1],
           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 */
       _crypt_output_magic(setting, output, size);
       __set_errno(EINVAL); /* pretend we don't support this hash type */
       return NULL;
}

Here is the call graph for this function:


Variable Documentation

unsigned char BF_atoi64[0x60] [static]
Initial value:
 {
       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
}

Definition at line 368 of file crypt_blowfish.c.

Definition at line 93 of file crypt_blowfish.c.

unsigned char BF_itoa64[64+1] = "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" [static]

Definition at line 365 of file crypt_blowfish.c.

BF_word BF_magic_w[6] [static]
Initial value:
 {
       0x4F727068, 0x65616E42, 0x65686F6C,
       0x64657253, 0x63727944, 0x6F756274
}

Definition at line 85 of file crypt_blowfish.c.