1263783Sdelphij/* $OpenBSD: bcrypt.c,v 1.29 2014/02/24 19:45:43 tedu Exp $ */ 2263783Sdelphij 374106Smarkm/* 474106Smarkm * Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de> 574106Smarkm * All rights reserved. 674106Smarkm * 774106Smarkm * Redistribution and use in source and binary forms, with or without 874106Smarkm * modification, are permitted provided that the following conditions 974106Smarkm * are met: 1074106Smarkm * 1. Redistributions of source code must retain the above copyright 1174106Smarkm * notice, this list of conditions and the following disclaimer. 1274106Smarkm * 2. Redistributions in binary form must reproduce the above copyright 1374106Smarkm * notice, this list of conditions and the following disclaimer in the 1474106Smarkm * documentation and/or other materials provided with the distribution. 1574106Smarkm * 3. All advertising materials mentioning features or use of this software 1674106Smarkm * must display the following acknowledgement: 1774106Smarkm * This product includes software developed by Niels Provos. 1874106Smarkm * 4. The name of the author may not be used to endorse or promote products 1974106Smarkm * derived from this software without specific prior written permission. 2074106Smarkm * 2174106Smarkm * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2274106Smarkm * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2374106Smarkm * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2474106Smarkm * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2574106Smarkm * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2674106Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2774106Smarkm * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2874106Smarkm * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2974106Smarkm * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 3074106Smarkm * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3174106Smarkm */ 3274106Smarkm 3385358Speter#include <sys/cdefs.h> 3485358Speter__FBSDID("$FreeBSD$"); 3585358Speter 3674106Smarkm/* This password hashing algorithm was designed by David Mazieres 3774106Smarkm * <dm@lcs.mit.edu> and works as follows: 3874106Smarkm * 3974106Smarkm * 1. state := InitState () 40263783Sdelphij * 2. state := ExpandKey (state, salt, password) 41263783Sdelphij * 3. REPEAT rounds: 42263783Sdelphij * state := ExpandKey (state, 0, password) 4374106Smarkm * state := ExpandKey (state, 0, salt) 4474106Smarkm * 4. ctext := "OrpheanBeholderScryDoubt" 4574106Smarkm * 5. REPEAT 64: 4674106Smarkm * ctext := Encrypt_ECB (state, ctext); 4774106Smarkm * 6. RETURN Concatenate (salt, ctext); 4874106Smarkm * 4974106Smarkm */ 5074106Smarkm 5174106Smarkm/* 5274106Smarkm * FreeBSD implementation by Paul Herman <pherman@frenchfries.net> 53263783Sdelphij * and updated by Xin Li <delphij@FreeBSD.org> 5474106Smarkm */ 5574106Smarkm 5674106Smarkm#include <stdio.h> 5774106Smarkm#include <stdlib.h> 5874106Smarkm#include <sys/types.h> 5974106Smarkm#include <string.h> 6074106Smarkm#include <pwd.h> 6174106Smarkm#include "blowfish.h" 6291754Smarkm#include "crypt.h" 6374106Smarkm 6474106Smarkm/* This implementation is adaptable to current computing power. 6574106Smarkm * You can have up to 2^31 rounds which should be enough for some 6674106Smarkm * time to come. 6774106Smarkm */ 6874106Smarkm 6974106Smarkm#define BCRYPT_VERSION '2' 7074106Smarkm#define BCRYPT_MAXSALT 16 /* Precomputation is just so nice */ 7174106Smarkm#define BCRYPT_BLOCKS 6 /* Ciphertext blocks */ 72263783Sdelphij#define BCRYPT_MINLOGROUNDS 4 /* we have log2(rounds) in salt */ 7374106Smarkm 74263783Sdelphij 7591754Smarkmstatic void encode_base64(u_int8_t *, u_int8_t *, u_int16_t); 7691754Smarkmstatic void decode_base64(u_int8_t *, u_int16_t, const u_int8_t *); 7774106Smarkm 7874106Smarkmstatic char encrypted[_PASSWORD_LEN]; 7974106Smarkm 80263783Sdelphijconst static u_int8_t Base64Code[] = 8174106Smarkm"./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; 8274106Smarkm 83263783Sdelphijconst static u_int8_t index_64[128] = { 8474106Smarkm 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 8574106Smarkm 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 8674106Smarkm 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 8774106Smarkm 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 8874106Smarkm 255, 255, 255, 255, 255, 255, 0, 1, 54, 55, 8974106Smarkm 56, 57, 58, 59, 60, 61, 62, 63, 255, 255, 9074106Smarkm 255, 255, 255, 255, 255, 2, 3, 4, 5, 6, 9174106Smarkm 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 9274106Smarkm 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 9374106Smarkm 255, 255, 255, 255, 255, 255, 28, 29, 30, 9474106Smarkm 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 9574106Smarkm 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 9674106Smarkm 51, 52, 53, 255, 255, 255, 255, 255 9774106Smarkm}; 9874106Smarkm#define CHAR64(c) ( (c) > 127 ? 255 : index_64[(c)]) 9974106Smarkm 10074106Smarkmstatic void 10191754Smarkmdecode_base64(u_int8_t *buffer, u_int16_t len, const u_int8_t *data) 10274106Smarkm{ 10374106Smarkm u_int8_t *bp = buffer; 10491754Smarkm const u_int8_t *p = data; 10574106Smarkm u_int8_t c1, c2, c3, c4; 10674106Smarkm while (bp < buffer + len) { 10774106Smarkm c1 = CHAR64(*p); 10874106Smarkm c2 = CHAR64(*(p + 1)); 10974106Smarkm 11074106Smarkm /* Invalid data */ 11174106Smarkm if (c1 == 255 || c2 == 255) 11274106Smarkm break; 11374106Smarkm 114263783Sdelphij *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4); 11574106Smarkm if (bp >= buffer + len) 11674106Smarkm break; 11774106Smarkm 11874106Smarkm c3 = CHAR64(*(p + 2)); 11974106Smarkm if (c3 == 255) 12074106Smarkm break; 12174106Smarkm 12274106Smarkm *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2); 12374106Smarkm if (bp >= buffer + len) 12474106Smarkm break; 12574106Smarkm 12674106Smarkm c4 = CHAR64(*(p + 3)); 12774106Smarkm if (c4 == 255) 12874106Smarkm break; 12974106Smarkm *bp++ = ((c3 & 0x03) << 6) | c4; 13074106Smarkm 13174106Smarkm p += 4; 13274106Smarkm } 13374106Smarkm} 13474106Smarkm 13574106Smarkm/* We handle $Vers$log2(NumRounds)$salt+passwd$ 13674106Smarkm i.e. $2$04$iwouldntknowwhattosayetKdJ6iFtacBqJdKe6aW7ou */ 13774106Smarkm 13874106Smarkmchar * 13991754Smarkmcrypt_blowfish(const char *key, const char *salt) 14074106Smarkm{ 14174106Smarkm blf_ctx state; 14274106Smarkm u_int32_t rounds, i, k; 14374106Smarkm u_int16_t j; 144263783Sdelphij size_t key_len; 145263783Sdelphij u_int8_t salt_len, logr, minr; 14674106Smarkm u_int8_t ciphertext[4 * BCRYPT_BLOCKS] = "OrpheanBeholderScryDoubt"; 14774106Smarkm u_int8_t csalt[BCRYPT_MAXSALT]; 14874106Smarkm u_int32_t cdata[BCRYPT_BLOCKS]; 149263783Sdelphij char arounds[3]; 150263783Sdelphij 151263783Sdelphij /* Defaults */ 152266816Sdelphij minr = 'b'; 153263783Sdelphij logr = BCRYPT_MINLOGROUNDS; 154263783Sdelphij rounds = 1U << logr; 15574106Smarkm 156263783Sdelphij if (*salt == '$') { 15774106Smarkm /* Discard "$" identifier */ 15874106Smarkm salt++; 15974106Smarkm 16074106Smarkm if (*salt > BCRYPT_VERSION) { 161231986Skevlo /* How do I handle errors ? Return NULL */ 162231986Skevlo return NULL; 16374106Smarkm } 16474106Smarkm 16574106Smarkm /* Check for minor versions */ 16674106Smarkm if (salt[1] != '$') { 16774106Smarkm switch (salt[1]) { 168263783Sdelphij case 'a': /* 'ab' should not yield the same as 'abab' */ 169263783Sdelphij case 'b': /* cap input length at 72 bytes */ 170263783Sdelphij minr = salt[1]; 17174106Smarkm salt++; 17274106Smarkm break; 17374106Smarkm default: 174231986Skevlo return NULL; 17574106Smarkm } 17674106Smarkm } else 17791754Smarkm minr = 0; 17874106Smarkm 17974106Smarkm /* Discard version + "$" identifier */ 18074106Smarkm salt += 2; 18174106Smarkm 18274106Smarkm if (salt[2] != '$') 18374106Smarkm /* Out of sync with passwd entry */ 184231986Skevlo return NULL; 18574106Smarkm 186263783Sdelphij memcpy(arounds, salt, sizeof(arounds)); 187263783Sdelphij if (arounds[sizeof(arounds) - 1] != '$') 188231986Skevlo return NULL; 189263783Sdelphij arounds[sizeof(arounds) - 1] = 0; 190263783Sdelphij logr = strtonum(arounds, BCRYPT_MINLOGROUNDS, 31, NULL); 191263783Sdelphij if (logr == 0) 192263783Sdelphij return NULL; 193263783Sdelphij /* Computer power doesn't increase linearly, 2^x should be fine */ 194263783Sdelphij rounds = 1U << logr; 19574106Smarkm 19674106Smarkm /* Discard num rounds + "$" identifier */ 19774106Smarkm salt += 3; 19874106Smarkm } 19974106Smarkm 200263783Sdelphij if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT) 201263783Sdelphij return NULL; 20274106Smarkm 20374106Smarkm /* We dont want the base64 salt but the raw data */ 204263783Sdelphij decode_base64(csalt, BCRYPT_MAXSALT, (const u_int8_t *) salt); 20574106Smarkm salt_len = BCRYPT_MAXSALT; 206263783Sdelphij if (minr <= 'a') 207263783Sdelphij key_len = (u_int8_t)(strlen(key) + (minr >= 'a' ? 1 : 0)); 208263783Sdelphij else { 209263783Sdelphij /* strlen() returns a size_t, but the function calls 210263783Sdelphij * below result in implicit casts to a narrower integer 211263783Sdelphij * type, so cap key_len at the actual maximum supported 212263783Sdelphij * length here to avoid integer wraparound */ 213263783Sdelphij key_len = strlen(key); 214263783Sdelphij if (key_len > 72) 215263783Sdelphij key_len = 72; 216263783Sdelphij key_len++; /* include the NUL */ 217263783Sdelphij } 21874106Smarkm 21974106Smarkm /* Setting up S-Boxes and Subkeys */ 22074106Smarkm Blowfish_initstate(&state); 22174106Smarkm Blowfish_expandstate(&state, csalt, salt_len, 22291754Smarkm (const u_int8_t *) key, key_len); 22374106Smarkm for (k = 0; k < rounds; k++) { 22491754Smarkm Blowfish_expand0state(&state, (const u_int8_t *) key, key_len); 22574106Smarkm Blowfish_expand0state(&state, csalt, salt_len); 22674106Smarkm } 22774106Smarkm 22874106Smarkm /* This can be precomputed later */ 22974106Smarkm j = 0; 23074106Smarkm for (i = 0; i < BCRYPT_BLOCKS; i++) 23174106Smarkm cdata[i] = Blowfish_stream2word(ciphertext, 4 * BCRYPT_BLOCKS, &j); 23274106Smarkm 23374106Smarkm /* Now do the encryption */ 23474106Smarkm for (k = 0; k < 64; k++) 23574106Smarkm blf_enc(&state, cdata, BCRYPT_BLOCKS / 2); 23674106Smarkm 23774106Smarkm for (i = 0; i < BCRYPT_BLOCKS; i++) { 23874106Smarkm ciphertext[4 * i + 3] = cdata[i] & 0xff; 23974106Smarkm cdata[i] = cdata[i] >> 8; 24074106Smarkm ciphertext[4 * i + 2] = cdata[i] & 0xff; 24174106Smarkm cdata[i] = cdata[i] >> 8; 24274106Smarkm ciphertext[4 * i + 1] = cdata[i] & 0xff; 24374106Smarkm cdata[i] = cdata[i] >> 8; 24474106Smarkm ciphertext[4 * i + 0] = cdata[i] & 0xff; 24574106Smarkm } 24674106Smarkm 24774106Smarkm 24874106Smarkm i = 0; 24974106Smarkm encrypted[i++] = '$'; 25074106Smarkm encrypted[i++] = BCRYPT_VERSION; 25191754Smarkm if (minr) 252263783Sdelphij encrypted[i++] = minr; 25374106Smarkm encrypted[i++] = '$'; 25474106Smarkm 25574106Smarkm snprintf(encrypted + i, 4, "%2.2u$", logr); 25674106Smarkm 25774106Smarkm encode_base64((u_int8_t *) encrypted + i + 3, csalt, BCRYPT_MAXSALT); 25874106Smarkm encode_base64((u_int8_t *) encrypted + strlen(encrypted), ciphertext, 25974106Smarkm 4 * BCRYPT_BLOCKS - 1); 260263783Sdelphij memset(&state, 0, sizeof(state)); 261263783Sdelphij memset(ciphertext, 0, sizeof(ciphertext)); 262263783Sdelphij memset(csalt, 0, sizeof(csalt)); 263263783Sdelphij memset(cdata, 0, sizeof(cdata)); 26474106Smarkm return encrypted; 26574106Smarkm} 26674106Smarkm 26774106Smarkmstatic void 26874106Smarkmencode_base64(u_int8_t *buffer, u_int8_t *data, u_int16_t len) 26974106Smarkm{ 27074106Smarkm u_int8_t *bp = buffer; 27174106Smarkm u_int8_t *p = data; 27274106Smarkm u_int8_t c1, c2; 27374106Smarkm while (p < data + len) { 27474106Smarkm c1 = *p++; 27574106Smarkm *bp++ = Base64Code[(c1 >> 2)]; 27674106Smarkm c1 = (c1 & 0x03) << 4; 27774106Smarkm if (p >= data + len) { 27874106Smarkm *bp++ = Base64Code[c1]; 27974106Smarkm break; 28074106Smarkm } 28174106Smarkm c2 = *p++; 28274106Smarkm c1 |= (c2 >> 4) & 0x0f; 28374106Smarkm *bp++ = Base64Code[c1]; 28474106Smarkm c1 = (c2 & 0x0f) << 2; 28574106Smarkm if (p >= data + len) { 28674106Smarkm *bp++ = Base64Code[c1]; 28774106Smarkm break; 28874106Smarkm } 28974106Smarkm c2 = *p++; 29074106Smarkm c1 |= (c2 >> 6) & 0x03; 29174106Smarkm *bp++ = Base64Code[c1]; 29274106Smarkm *bp++ = Base64Code[c2 & 0x3f]; 29374106Smarkm } 29474106Smarkm *bp = '\0'; 29574106Smarkm} 29674106Smarkm#if 0 29774106Smarkmvoid 29874106Smarkmmain() 29974106Smarkm{ 30074106Smarkm char blubber[73]; 30174106Smarkm char salt[100]; 30274106Smarkm char *p; 30374106Smarkm salt[0] = '$'; 30474106Smarkm salt[1] = BCRYPT_VERSION; 30574106Smarkm salt[2] = '$'; 30674106Smarkm 30774106Smarkm snprintf(salt + 3, 4, "%2.2u$", 5); 30874106Smarkm 30974106Smarkm printf("24 bytes of salt: "); 310263783Sdelphij fgets(salt + 6, sizeof(salt) - 6, stdin); 31174106Smarkm salt[99] = 0; 31274106Smarkm printf("72 bytes of password: "); 31374106Smarkm fpurge(stdin); 314263783Sdelphij fgets(blubber, sizeof(blubber), stdin); 31574106Smarkm blubber[72] = 0; 31674106Smarkm 31774106Smarkm p = crypt(blubber, salt); 31874106Smarkm printf("Passwd entry: %s\n\n", p); 31974106Smarkm 32074106Smarkm p = bcrypt_gensalt(5); 32174106Smarkm printf("Generated salt: %s\n", p); 32274106Smarkm p = crypt(blubber, p); 32374106Smarkm printf("Passwd entry: %s\n", p); 32474106Smarkm} 32574106Smarkm#endif 326