Back to index

python-bcrypt  0.2
bcrypt.c
Go to the documentation of this file.
00001 /*     $OpenBSD: bcrypt.c,v 1.20 2006/04/03 19:55:49 deraadt Exp $    */
00002 
00003 /*
00004  * Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de>
00005  * All rights reserved.
00006  *
00007  * Redistribution and use in source and binary forms, with or without
00008  * modification, are permitted provided that the following conditions
00009  * are met:
00010  * 1. Redistributions of source code must retain the above copyright
00011  *    notice, this list of conditions and the following disclaimer.
00012  * 2. Redistributions in binary form must reproduce the above copyright
00013  *    notice, this list of conditions and the following disclaimer in the
00014  *    documentation and/or other materials provided with the distribution.
00015  * 3. All advertising materials mentioning features or use of this software
00016  *    must display the following acknowledgement:
00017  *      This product includes software developed by Niels Provos.
00018  * 4. The name of the author may not be used to endorse or promote products
00019  *    derived from this software without specific prior written permission.
00020  *
00021  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00022  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00023  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00024  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00025  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00026  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00027  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00028  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00029  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00030  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031  */
00032 
00033 /* This password hashing algorithm was designed by David Mazieres
00034  * <dm@lcs.mit.edu> and works as follows:
00035  *
00036  * 1. state := InitState ()
00037  * 2. state := ExpandKey (state, salt, password) 3.
00038  * REPEAT rounds:
00039  *     state := ExpandKey (state, 0, salt)
00040  *      state := ExpandKey(state, 0, password)
00041  * 4. ctext := "OrpheanBeholderScryDoubt"
00042  * 5. REPEAT 64:
00043  *     ctext := Encrypt_ECB (state, ctext);
00044  * 6. RETURN Concatenate (salt, ctext);
00045  *
00046  */
00047 
00048 #include <stdio.h>
00049 #include <stdlib.h>
00050 #include <sys/types.h>
00051 #include <string.h>
00052 
00053 #include "pybc_blf.h"
00054 
00055 #if defined(_MSC_VER)
00056 #define snprintf _snprintf
00057 #endif
00058 
00059 /* This implementation is adaptable to current computing power.
00060  * You can have up to 2^31 rounds which should be enough for some
00061  * time to come.
00062  */
00063 
00064 #define BCRYPT_VERSION '2'
00065 #define BCRYPT_MAXSALT 16   /* Precomputation is just so nice */
00066 #define BCRYPT_BLOCKS 6            /* Ciphertext blocks */
00067 #define BCRYPT_MINROUNDS 16 /* we have log2(rounds) in salt */
00068 
00069 char *pybc_bcrypt(const char *, const char *);
00070 void encode_salt(char *, u_int8_t *, u_int16_t, u_int8_t);
00071 
00072 static void encode_base64(u_int8_t *, u_int8_t *, u_int16_t);
00073 static void decode_base64(u_int8_t *, u_int16_t, u_int8_t *);
00074 
00075 static char    encrypted[128];
00076 static char    error[] = ":";
00077 
00078 const static u_int8_t Base64Code[] =
00079 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
00080 
00081 const static u_int8_t index_64[128] = {
00082        255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
00083        255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
00084        255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
00085        255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
00086        255, 255, 255, 255, 255, 255, 0, 1, 54, 55,
00087        56, 57, 58, 59, 60, 61, 62, 63, 255, 255,
00088        255, 255, 255, 255, 255, 2, 3, 4, 5, 6,
00089        7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
00090        17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
00091        255, 255, 255, 255, 255, 255, 28, 29, 30,
00092        31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
00093        41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
00094        51, 52, 53, 255, 255, 255, 255, 255
00095 };
00096 #define CHAR64(c)  ( (c) > 127 ? 255 : index_64[(c)])
00097 
00098 static void
00099 decode_base64(u_int8_t *buffer, u_int16_t len, u_int8_t *data)
00100 {
00101        u_int8_t *bp = buffer;
00102        u_int8_t *p = data;
00103        u_int8_t c1, c2, c3, c4;
00104        while (bp < buffer + len) {
00105               c1 = CHAR64(*p);
00106               c2 = CHAR64(*(p + 1));
00107 
00108               /* Invalid data */
00109               if (c1 == 255 || c2 == 255)
00110                      break;
00111 
00112               *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4);
00113               if (bp >= buffer + len)
00114                      break;
00115 
00116               c3 = CHAR64(*(p + 2));
00117               if (c3 == 255)
00118                      break;
00119 
00120               *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2);
00121               if (bp >= buffer + len)
00122                      break;
00123 
00124               c4 = CHAR64(*(p + 3));
00125               if (c4 == 255)
00126                      break;
00127               *bp++ = ((c3 & 0x03) << 6) | c4;
00128 
00129               p += 4;
00130        }
00131 }
00132 
00133 void
00134 encode_salt(char *salt, u_int8_t *csalt, u_int16_t clen, u_int8_t logr)
00135 {
00136        salt[0] = '$';
00137        salt[1] = BCRYPT_VERSION;
00138        salt[2] = 'a';
00139        salt[3] = '$';
00140 
00141        snprintf(salt + 4, 4, "%2.2u$", logr);
00142 
00143        encode_base64((u_int8_t *) salt + 7, csalt, clen);
00144 }
00145 
00146 /* We handle $Vers$log2(NumRounds)$salt+passwd$
00147    i.e. $2$04$iwouldntknowwhattosayetKdJ6iFtacBqJdKe6aW7ou */
00148 
00149 char   *
00150 pybc_bcrypt(const char *key, const char *salt)
00151 {
00152        pybc_blf_ctx state;
00153        u_int32_t rounds, i, k;
00154        u_int16_t j;
00155        u_int8_t key_len, salt_len, logr, minor;
00156        u_int8_t ciphertext[4 * BCRYPT_BLOCKS] = "OrpheanBeholderScryDoubt";
00157        u_int8_t csalt[BCRYPT_MAXSALT];
00158        u_int32_t cdata[BCRYPT_BLOCKS];
00159        int n;
00160 
00161        /* Discard "$" identifier */
00162        salt++;
00163 
00164        if (*salt > BCRYPT_VERSION) {
00165               /* How do I handle errors ? Return ':' */
00166               return error;
00167        }
00168 
00169        /* Check for minor versions */
00170        if (salt[1] != '$') {
00171                switch (salt[1]) {
00172                case 'a':
00173                       /* 'ab' should not yield the same as 'abab' */
00174                       minor = salt[1];
00175                       salt++;
00176                       break;
00177                default:
00178                       return error;
00179                }
00180        } else
00181                minor = 0;
00182 
00183        /* Discard version + "$" identifier */
00184        salt += 2;
00185 
00186        if (salt[2] != '$')
00187               /* Out of sync with passwd entry */
00188               return error;
00189 
00190        /* Computer power doesn't increase linear, 2^x should be fine */
00191        n = atoi(salt);
00192        if (n > 31 || n < 0)
00193               return error;
00194        logr = (u_int8_t)n;
00195        if ((rounds = (u_int32_t) 1 << logr) < BCRYPT_MINROUNDS)
00196               return error;
00197 
00198        /* Discard num rounds + "$" identifier */
00199        salt += 3;
00200 
00201        if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT)
00202               return error;
00203 
00204        /* We dont want the base64 salt but the raw data */
00205        decode_base64(csalt, BCRYPT_MAXSALT, (u_int8_t *) salt);
00206        salt_len = BCRYPT_MAXSALT;
00207        key_len = strlen(key) + (minor >= 'a' ? 1 : 0);
00208 
00209        /* Setting up S-Boxes and Subkeys */
00210        pybc_Blowfish_initstate(&state);
00211        pybc_Blowfish_expandstate(&state, csalt, salt_len,
00212            (u_int8_t *) key, key_len);
00213        for (k = 0; k < rounds; k++) {
00214               pybc_Blowfish_expand0state(&state, (u_int8_t *) key, key_len);
00215               pybc_Blowfish_expand0state(&state, csalt, salt_len);
00216        }
00217 
00218        /* This can be precomputed later */
00219        j = 0;
00220        for (i = 0; i < BCRYPT_BLOCKS; i++) {
00221               cdata[i] = pybc_Blowfish_stream2word(ciphertext,
00222                   4 * BCRYPT_BLOCKS, &j);
00223        }
00224 
00225        /* Now do the encryption */
00226        for (k = 0; k < 64; k++)
00227               pybc_blf_enc(&state, cdata, BCRYPT_BLOCKS / 2);
00228 
00229        for (i = 0; i < BCRYPT_BLOCKS; i++) {
00230               ciphertext[4 * i + 3] = cdata[i] & 0xff;
00231               cdata[i] = cdata[i] >> 8;
00232               ciphertext[4 * i + 2] = cdata[i] & 0xff;
00233               cdata[i] = cdata[i] >> 8;
00234               ciphertext[4 * i + 1] = cdata[i] & 0xff;
00235               cdata[i] = cdata[i] >> 8;
00236               ciphertext[4 * i + 0] = cdata[i] & 0xff;
00237        }
00238 
00239 
00240        i = 0;
00241        encrypted[i++] = '$';
00242        encrypted[i++] = BCRYPT_VERSION;
00243        if (minor)
00244               encrypted[i++] = minor;
00245        encrypted[i++] = '$';
00246 
00247        snprintf(encrypted + i, 4, "%2.2u$", logr);
00248 
00249        encode_base64((u_int8_t *) encrypted + i + 3, csalt, BCRYPT_MAXSALT);
00250        encode_base64((u_int8_t *) encrypted + strlen(encrypted), ciphertext,
00251            4 * BCRYPT_BLOCKS - 1);
00252        return encrypted;
00253 }
00254 
00255 static void
00256 encode_base64(u_int8_t *buffer, u_int8_t *data, u_int16_t len)
00257 {
00258        u_int8_t *bp = buffer;
00259        u_int8_t *p = data;
00260        u_int8_t c1, c2;
00261        while (p < data + len) {
00262               c1 = *p++;
00263               *bp++ = Base64Code[(c1 >> 2)];
00264               c1 = (c1 & 0x03) << 4;
00265               if (p >= data + len) {
00266                      *bp++ = Base64Code[c1];
00267                      break;
00268               }
00269               c2 = *p++;
00270               c1 |= (c2 >> 4) & 0x0f;
00271               *bp++ = Base64Code[c1];
00272               c1 = (c2 & 0x0f) << 2;
00273               if (p >= data + len) {
00274                      *bp++ = Base64Code[c1];
00275                      break;
00276               }
00277               c2 = *p++;
00278               c1 |= (c2 >> 6) & 0x03;
00279               *bp++ = Base64Code[c1];
00280               *bp++ = Base64Code[c2 & 0x3f];
00281        }
00282        *bp = '\0';
00283 }
00284